Planner: Ordering vs filtering issue applies to index join #62034
Description
Bug Report
If a customer/user discourages merge join, or encourages index join. For join queries with ORDER BY & LIMIT - where the filtering is from a table other than the ordering table - the optimizer may choose an inefficient index join plan because it underestimates how "early" it will find the filtering rows on the 2nd (or subsequent) table.
The fact that merge join is favored initially is a separate issue. This issue was exposed by a customer wanting to discourage hash and merge joins and encourage index joins generally in their workload.
1. Minimal reproduce step (Required)
CREATE TABLE `t1` (
`a` int,
`b` int,
`c` int,
KEY `ib` (`b`),
KEY `iab` (`a`, `b`)
);
set @@cte_max_recursion_depth=10000000;
INSERT INTO t1 (a, b, c)
SELECT a, mod(a, 10000) AS b, mod(a, 100) AS c
FROM (
WITH RECURSIVE x AS (
SELECT 1 AS a
UNION ALL
SELECT a + 1 AS a
FROM x
WHERE a < 1000000
)
SELECT a
FROM x
) AS subquery;
Create table t2 like t1;
Insert into t2 select * from t1;
Analyze table t1;
Analyze table t2;
set @@session.tidb_opt_merge_join_cost_factor=100;
explain analyze select t1.a from t1 join t2 on t1.a=t2.a where t2.b between 9990 and 9999 order by t1.a limit 2;
2. What did you expect to see? (Required)
explain analyze select t1.a from t1 join t2 on t1.a=t2.a where t2.b between 9990 and 9999 order by t1.a limit 2;
+--------------------------------------+---------+---------+-----------+---------------------------+-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+-----------------------------------------------------------------------------------------------------------------+-----------+---------+
| id | estRows | actRows | task | access object | execution info | operator info | memory | disk |
+--------------------------------------+---------+---------+-----------+---------------------------+-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+-----------------------------------------------------------------------------------------------------------------+-----------+---------+
| TopN_15 | 2.00 | 2 | root | | time:27.3ms, open:116.9µs, close:5.42µs, loops:2, RU:16.83 | test.t1.a, offset:0, count:2 | 396 Bytes | 0 Bytes |
| └─IndexJoin_23 | 1219.50 | 1000 | root | | time:27.1ms, open:34.7µs, close:4.42µs, loops:3, inner:{total:9.47ms, concurrency:5, task:8, construct:969.5µs, fetch:7.9ms, build:588µs}, probe:386.2µs | inner join, inner:IndexReader_50, outer key:test.t2.a, inner key:test.t1.a, equal cond:eq(test.t2.a, test.t1.a) | 211.8 KB | N/A |
| ├─IndexLookUp_44(Build) | 1219.50 | 1000 | root | | time:22.5ms, open:13.2µs, close:2.54µs, loops:10, index_task: {total_time: 2.17ms, fetch_handle: 2.16ms, build: 792ns, wait: 6.63µs}, table_task: {total_time: 20.2ms, num: 1, concurrency: 5}, next: {wait_index: 2.27ms, wait_table_lookup_build: 329.4µs, wait_table_lookup_resp: 19.8ms} | | 67.4 KB | N/A |
| │ ├─IndexRangeScan_41(Build) | 1219.50 | 1000 | cop[tikv] | table:t2, index:ib(b) | time:2.11ms, open:0s, close:0s, loops:3, cop_task: {num: 1, max: 2.02ms, proc_keys: 0, tot_proc: 1ms, copr_cache_hit_ratio: 0.00, build_task_duration: 21.5µs, max_distsql_concurrency: 1}, fetch_resp_duration: 2.06ms, rpc_info:{Cop:{num_rpc:1, total_time:1.99ms}}, tikv_task:{time:1.89ms, loops:0}, time_detail: {total_process_time: 1ms} | range:[9990,9999], keep order:false | N/A | N/A |
| │ └─Selection_43(Probe) | 1219.50 | 1000 | cop[tikv] | | time:19.7ms, open:0s, close:2.04µs, loops:2, cop_task: {num: 2, max: 19.6ms, min: 8.96ms, avg: 14.3ms, p95: 19.6ms, tot_proc: 27ms, copr_cache_hit_ratio: 0.00, build_task_duration: 86.9µs, max_distsql_concurrency: 2}, fetch_resp_duration: 19.6ms, rpc_info:{Cop:{num_rpc:2, total_time:28.5ms}}, tikv_task:{proc max:19.6ms, min:8.89ms, avg: 14.2ms, p80:19.6ms, p95:19.6ms, iters:0, tasks:2}, time_detail: {total_process_time: 27ms} | not(isnull(test.t2.a)) | N/A | N/A |
| │ └─TableRowIDScan_42 | 1219.50 | 1000 | cop[tikv] | table:t2 | tikv_task:{proc max:19.6ms, min:8.89ms, avg: 14.2ms, p80:19.6ms, p95:19.6ms, iters:0, tasks:2} | keep order:false | N/A | N/A |
| └─IndexReader_50(Probe) | 1219.50 | 1000 | root | | total_time:4.86ms, total_open:0s, total_close:33.3µs, loops:16, cop_task: {num: 11, max: 1.12ms, min: 184.9µs, avg: 428.8µs, p95: 1.12ms, tot_proc: 1ms, copr_cache_hit_ratio: 0.00, build_task_duration: 132µs, max_distsql_concurrency: 2}, fetch_resp_duration: 4.69ms, rpc_info:{Cop:{num_rpc:11, total_time:4.62ms}} | index:Selection_49 | 244 Bytes | N/A |
| └─Selection_49 | 1219.50 | 1000 | cop[tikv] | | tikv_task:{proc max:1.1ms, min:157.8µs, avg: 401.1µs, p80:563.9µs, p95:1.1ms, iters:0, tasks:11}, time_detail: {total_process_time: 1ms} | not(isnull(test.t1.a)) | N/A | N/A |
| └─IndexRangeScan_48 | 1219.50 | 1000 | cop[tikv] | table:t1, index:iab(a, b) | tikv_task:{proc max:1.1ms, min:157.8µs, avg: 401.1µs, p80:563.9µs, p95:1.1ms, iters:0, tasks:11} | range: decided by [eq(test.t1.a, test.t2.a)], keep order:false | N/A | N/A |
+--------------------------------------+---------+---------+-----------+---------------------------+-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+-----------------------------------------------------------------------------------------------------------------+-----------+---------+
3. What did you see instead (Required)
Without setting merge_join_cost_factor - optimizer will choose merge join.
explain analyze select t1.a from t1 join t2 on t1.a=t2.a where t2.b between 9990 and 9999 order by t1.a limit 2;
+-------------------------------+---------+---------+-----------+---------------------------+----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+-----------------------------------------------------+---------+---------+
| id | estRows | actRows | task | access object | execution info | operator info | memory | disk |
+-------------------------------+---------+---------+-----------+---------------------------+----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+-----------------------------------------------------+---------+---------+
| Limit_19 | 2.00 | 2 | root | | time:3.19s, open:176.3µs, close:364.4ms, loops:2, RU:2591.31 | offset:0, count:2 | N/A | N/A |
| └─MergeJoin_58 | 2.00 | 2 | root | | time:3.19s, open:161.9µs, close:364.3ms, loops:1 | inner join, left key:test.t2.a, right key:test.t1.a | 38.3 KB | 0 Bytes |
| ├─IndexReader_69(Build) | 1640.02 | 10528 | root | | time:3.19s, open:35.8µs, close:364.3ms, loops:19, cop_task: {num: 7, max: 581.1ms, min: 365.2ms, avg: 403.3ms, p95: 581.1ms, tot_proc: 2.82s, copr_cache_hit_ratio: 0.00, build_task_duration: 27µs, max_distsql_concurrency: 2}, fetch_resp_duration: 2.82s, rpc_info:{Cop:{num_rpc:7, total_time:2.82s}} | index:IndexFullScan_68 | 2.68 MB | N/A |
| │ └─IndexFullScan_68 | 1640.02 | 16480 | cop[tikv] | table:t1, index:iab(a, b) | tikv_task:{proc max:581ms, min:365ms, avg: 403.3ms, p80:390.5ms, p95:581ms, iters:0, tasks:7}, time_detail: {total_process_time: 2.82s} | keep order:true | N/A | N/A |
| └─IndexReader_67(Probe) | 0.12 | 1000 | root | | time:135µs, open:67.6µs, close:5.38µs, loops:1, cop_task: {num: 5, max: 587.7ms, min: 124.2ms, avg: 316ms, p95: 587.7ms, tot_proc: 1.58s, copr_cache_hit_ratio: 0.00, build_task_duration: 35.9µs, max_distsql_concurrency: 2}, fetch_resp_duration: 4.63µs, rpc_info:{Cop:{num_rpc:5, total_time:1.58s}} | index:Selection_66 | 17.3 KB | N/A |
| └─Selection_66 | 0.12 | 1000 | cop[tikv] | | tikv_task:{proc max:587.7ms, min:124.2ms, avg: 316ms, p80:587.7ms, p95:587.7ms, iters:0, tasks:5}, time_detail: {total_process_time: 1.58s} | ge(test.t2.b, 9990), le(test.t2.b, 9999) | N/A | N/A |
| └─IndexFullScan_65 | 101.88 | 1000000 | cop[tikv] | table:t2, index:iab(a, b) | tikv_task:{proc max:587.7ms, min:124.2ms, avg: 316ms, p80:587.7ms, p95:587.7ms, iters:0, tasks:5} | keep order:true | N/A | N/A |
+-------------------------------+---------+---------+-----------+---------------------------+----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+-----------------------------------------------------+---------+---------+
If you discourage merge join, a poor index join plan is chosen:
explain analyze select t1.a from t1 join t2 on t1.a=t2.a where t2.b between 9990 and 9999 order by t1.a limit 2;
+-------------------------------+---------+---------+-----------+---------------------------+----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+-----------------------------------------------------------------------------------------------------------------+-----------+------+
| id | estRows | actRows | task | access object | execution info | operator info | memory | disk |
+-------------------------------+---------+---------+-----------+---------------------------+----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+-----------------------------------------------------------------------------------------------------------------+-----------+------+
| Limit_19 | 2.00 | 2 | root | | time:3.23s, open:193µs, close:351.5ms, loops:2, RU:2121.05 | offset:0, count:2 | N/A | N/A |
| └─IndexJoin_60 | 2.00 | 2 | root | | time:3.23s, open:187.8µs, close:351.5ms, loops:1, inner:{total:64.6ms, concurrency:5, task:12, construct:9.33ms, fetch:55.3ms, build:8.42µs}, probe:1.15ms | inner join, inner:IndexReader_53, outer key:test.t1.a, inner key:test.t2.a, equal cond:eq(test.t1.a, test.t2.a) | 2.59 MB | N/A |
| ├─IndexReader_69(Build) | 1640.02 | 16480 | root | | time:3.23s, open:181.9µs, close:351.4ms, loops:24, cop_task: {num: 7, max: 421ms, min: 390.8ms, avg: 407.6ms, p95: 421ms, tot_proc: 2.85s, copr_cache_hit_ratio: 0.00, build_task_duration: 64.5µs, max_distsql_concurrency: 2}, fetch_resp_duration: 2.88s, rpc_info:{Cop:{num_rpc:7, total_time:2.85s}} | index:IndexFullScan_68 | 2.68 MB | N/A |
| │ └─IndexFullScan_68 | 1640.02 | 16480 | cop[tikv] | table:t1, index:iab(a, b) | tikv_task:{proc max:420.8ms, min:390.7ms, avg: 407.5ms, p80:417.8ms, p95:420.8ms, iters:0, tasks:7}, time_detail: {total_process_time: 2.85s} | keep order:true | N/A | N/A |
| └─IndexReader_53(Probe) | 2.00 | 10 | root | | total_time:20ms, total_open:0s, total_close:62.5µs, loops:13, cop_task: {num: 12, max: 8.44ms, min: 121.8µs, avg: 1.61ms, p95: 8.44ms, tot_proc: 16ms, copr_cache_hit_ratio: 0.00, build_task_duration: 1.03ms, max_distsql_concurrency: 1}, fetch_resp_duration: 19.8ms, rpc_info:{Cop:{num_rpc:12, total_time:19.2ms}} | index:Selection_52 | 209 Bytes | N/A |
| └─Selection_52 | 2.00 | 10 | cop[tikv] | | tikv_task:{proc max:8.42ms, min:86.4µs, avg: 1.58ms, p80:2.02ms, p95:8.42ms, iters:0, tasks:12}, time_detail: {total_process_time: 16ms} | not(isnull(test.t2.a)) | N/A | N/A |
| └─IndexRangeScan_51 | 2.00 | 10 | cop[tikv] | table:t2, index:iab(a, b) | tikv_task:{proc max:8.42ms, min:86.4µs, avg: 1.58ms, p80:2.02ms, p95:8.42ms, iters:0, tasks:12} | range: decided by [eq(test.t2.a, test.t1.a) ge(test.t2.b, 9990) le(test.t2.b, 9999)], keep order:false | N/A | N/A |
+-------------------------------+---------+---------+-----------+---------------------------+----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+-----------------------------------------------------------------------------------------------------------------+-----------+------+
4. What is your TiDB version? (Required)
master branch (9.0)