pingcap / pingcap/tidb

planner: compress large IN-List into a Range-Scan + Selection

Open
#68,623 1 comment 0 reactions 0 assignees View on GitHub
report/customer sig/planner type/enhancement
Dominant language
Go
Stars
40.5k
Forks
6.2k
PR merge metrics
PR metrics pending

Description

## Enhancement
The problematic query and plan are like:
```
SELECT
`a`.`a_id`,
`a`.`a_flag`,
`a`.`a_ref_id`,
`a`.`a_owner_id`,
`a`.`a_join_id`,
`a`.`a_expire_at`,
`a`.`a_created_at`,
`b`.`b_num_1`,
`b`.`b_num_2`,
`b`.`b_num_3`,
`b`.`b_type_1`,
`b`.`b_ref_id_1`,
`b`.`b_ref_id_2`,
`b`.`b_ref_ids_3`,
`b`.`b_flag_1`,
`b`.`b_ref_ids_4`,
`b`.`b_num_min`,
`b`.`b_num_max`,
`b`.`b_text_1`,
`b`.`b_text_2`,
`b`.`b_json_1`,
`b`.`b_flag_2`,
`b`.`b_type_2`
FROM
`table_a` `a`
JOIN `table_b` `b` ON `a`.`a_join_id` = `b`.`b_id`
WHERE
`a`.`a_owner_id` IS ?
AND `b`.`b_active` = ?
AND `a`.`a_flag` = ?
AND `a`.`a_expire_at` > ?
AND (
`b`.`b_start_at` <= ?
OR `b`.`b_start_at` IS ?
)
AND `a`.`a_ref_id` IN (...)
ORDER BY
`a_created_at` DESC;

| id | estRows | estCost | actRows | task | access object | execution info | operator info | memory | disk |
| Sort_9 | 128.75 | 197489.70 | 0 | root | | time:294.2ms, loops:1 | appdb.table_a.a_created_at:desc | 0 Bytes | 0 Bytes |
| └─Projection_11 | 128.75 | 94599.06 | 0 | root | | time:291.1ms, loops:1, Concurrency:OFF | appdb.table_a.a_id, appdb.table_a.a_flag, appdb.table_a.a_ref_id, appdb.table_a.a_owner_id, appdb.table_a.a_join_id, appdb.table_a.a_expire_at, appdb.table_a.a_created_at, appdb.table_b.b_num_1, appdb.table_b.b_num_2, appdb.table_b.b_num_3, appdb.table_b.b_type_1, appdb.table_b.b_ref_id_1, appdb.table_b.b_ref_id_2, appdb.table_b.b_ref_ids_3, appdb.table_b.b_flag_1, appdb.table_b.b_ref_ids_4, appdb.table_b.b_num_min, appdb.table_b.b_num_max, appdb.table_b.b_text_1, appdb.table_b.b_text_2, appdb.table_b.b_json_1, appdb.table_b.b_flag_2, appdb.table_b.b_type_2 | 11.5 KB | N/A |
| └─IndexHashJoin_21 | 128.75 | 94303.52 | 0 | root | | time:291.1ms, loops:1 | inner join, inner:TableReader_15, outer key:appdb.table_a.a_join_id, inner key:appdb.table_b.b_id, equal cond:eq(appdb.table_a.a_join_id, appdb.table_b.b_id) | 0 Bytes | N/A |
| ├─IndexReader_41(Build) | 157.95 | 8629.11 | 0 | root | | time:266.9ms, loops:1, cop_task: {num: 97, max: 107.8ms, min: 1.83ms, avg: 27.6ms, p95: 65.4ms, tot_proc: 8.71ms, tot_wait: 5.28ms, copr_cache: disabled, build_task_duration: 3.38ms, max_distsql_concurrency: 15}, rpc_info:{Cop:{num_rpc:97, total_time:2.67s}} | index:Selection_40 | 581 Bytes | N/A |
| │ └─Selection_40 | 157.95 | 60500.63 | 0 | cop[tikv] | | tikv_task:{proc max:1ms, min:0s, avg: 51.5µs, p80:0s, p95:1ms, iters:97, tasks:97}, scan_detail: {total_keys: 114, get_snapshot_time: 976.2µs, rocksdb: {block: {cache_hit_count: 1414}}}, time_detail: {total_process_time: 8.71ms, total_wait_time: 5.28ms, total_kv_read_wall_time: 5ms, tikv_wall_time: 33.6ms} | eq(appdb.table_a.a_flag, ?), isnull(appdb.table_a.a_owner_id) | N/A | N/A |
| │ └─IndexRangeScan_39 | 160.94 | 44438.52 | 0 | cop[tikv] | table:a, index:idx_a_ref_id_a_expire_at_a_flag_a_owner_id_a_created_at_a_join_id(a_ref_id, a_expire_at, a_flag, a_owner_id, a_created_at, a_join_id) | tikv_task:{proc max:1ms, min:0s, avg: 51.5µs, p80:0s, p95:1ms, iters:97, tasks:97} | range:(? ?,? +inf], (? ?,? +inf], ... repeated for IN list ..., keep order:false | N/A | N/A |
| └─TableReader_15(Probe) | 157.59 | 586.08 | 0 | root | | | data:Selection_14 | N/A | N/A |
| └─Selection_14 | 157.59 | 584.99 | 0 | cop[tikv] | | | eq(appdb.table_b.b_active, ?), or(le(appdb.table_b.b_start_at, ?), isnull(appdb.table_b.b_start_at)) | N/A | N/A |
| └─TableRangeScan_13 | 157.95 | 485.19 | 0 | cop[tikv] | table:b | | range: decided by [appdb.table_a.a_join_id], keep order:false | N/A | N/A |
```

We can see there is a big fan-out caused by the IN-list (around 200+ values), and these ranges would trigger more seek operations on the storage layer, and cause high CPU usage.

Image

Image

A possible optimization could be compressing these separate IN-List values into a Range-Scan + Selection if the range is not wide.
For example, `Scan([1, 1], [2, 2], [3, 3], ... [100, 100])` to `Scan([1, 100]) --> Selection(a in (1, 2, 3, ... 100))`.
A similar issue: https://github.com/pingcap/tidb/issues/67573

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.