TiDB cartesian join significantly slower than MySQL, SQLite and DuckDB (10.11s v.s. 1.69s v.s. 0.763s v.s. 0.0014s)
- Dominant language
- Go
- Stars
- 40.5k
- Forks
- 6.2k
- PR merge metrics
- PR metrics pending
Description
## Enhancement
data
[t1.sql.txt](https://github.com/pingcap/tidb/files/8684817/t1.sql.txt)
on tidb (master)
```
explain analyze SELECT count(*) FROM t1 im WHERE EXISTS ( SELECT 1 FROM t1 im_ps WHERE 1 = 1 AND locate(concat(im.c,'|'),im_ps.c)>0);
+-------------------------------+----------+---------+-----------+---------------+------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+----------------------------------------------------------------------------------+----------+---------+
| id | estRows | actRows | task | access object | execution info | operator info | memory | disk |
+-------------------------------+----------+---------+-----------+---------------+------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+----------------------------------------------------------------------------------+----------+---------+
| HashAgg_10 | 1.00 | 1 | root | | time:10.1s, loops:2, partial_worker:{wall_time:10.10997325s, concurrency:5, task_num:10, tot_wait:50.536126292s, tot_exec:465.918µs, tot_time:50.536601958s, max:10.107438208s, p95:10.107438208s}, final_worker:{wall_time:10.1099755s, concurrency:5, task_num:5, tot_wait:50.536316709s, tot_exec:20.001µs, tot_time:50.5363405s, max:10.107288583s, p95:10.107288583s} | funcs:count(1)->Column#10 | 83.7 KB | N/A |
| └─HashJoin_12 | 8192.00 | 9216 | root | | time:10.1s, loops:11, build_hash_table:{total:2.3ms, fetch:1.99ms, build:317.2µs}, probe:{concurrency:5, total:50.4s, max:10.1s, probe:50.4s, fetch:15.2ms} | CARTESIAN semi join, other cond:gt(locate(concat(test.t1.c, "|"), test.t1.c), 0) | 417.6 KB | 0 Bytes |
| ├─TableReader_16(Build) | 10240.00 | 10240 | root | | time:2.1ms, loops:11, cop_task: {num: 1, max: 1.96ms, proc_keys: 0, tot_proc: 1ms, rpc_num: 1, rpc_time: 1.94ms, copr_cache_hit_ratio: 0.00} | data:TableFullScan_15 | 66.0 KB | N/A |
| │ └─TableFullScan_15 | 10240.00 | 10240 | cop[tikv] | table:im_ps | tikv_task:{time:1.92ms, loops:0} | keep order:false | N/A | N/A |
| └─TableReader_14(Probe) | 10240.00 | 10240 | root | | time:1.23ms, loops:11, cop_task: {num: 1, max: 3.51ms, proc_keys: 0, tot_proc: 3ms, rpc_num: 1, rpc_time: 3.48ms, copr_cache_hit_ratio: 0.00} | data:TableFullScan_13 | 66.0 KB | N/A |
| └─TableFullScan_13 | 10240.00 | 10240 | cop[tikv] | table:im | tikv_task:{time:3.44ms, loops:0} | keep order:false | N/A | N/A |
+-------------------------------+----------+---------+-----------+---------------+------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+----------------------------------------------------------------------------------+----------+---------+
6 rows in set (10.11 sec)
```
on mysql (v8.0.28)
```
explain analyze SELECT count(*) FROM t1 im WHERE EXISTS ( SELECT 1 FROM t1 im_ps WHERE 1 = 1 AND locate(concat(im.c,'|'),im_ps.c)>0);
+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| EXPLAIN |
+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| -> Aggregate: count(0) (cost=20566263.14 rows=1) (actual time=1686.874..1686.875 rows=1 loops=1)
-> Hash semijoin (no condition), extra conditions: (locate(concat(im.c,'|'),im_ps.c) > 0) (cost=10284303.14 rows=102819600) (actual time=10.765..1686.194 rows=9216 loops=1)
-> Table scan on im (cost=1054.25 rows=10140) (actual time=0.069..3.507 rows=10240 loops=1)
-> Hash
-> Table scan on im_ps (cost=1678.57 rows=10140) (actual time=0.097..4.593 rows=10240 loops=1)
|
+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
1 row in set, 1 warning (1.69 sec)
```
it turns out TiDB is more than 5 times slower than MySQL (10.11s v.s. 1.69s), and with the profiling result below, it seems the bottleneck is on the contention on locks on `RowContainer`

Contributor guide
Assessment
This issue has not been assessed yet.