planner: IndexJoin + large not-in list cause TiKV CPU spike
- Dominant language
- Go
- Stars
- 40.5k
- Forks
- 6.2k
- PR merge metrics
- PR metrics pending
Description
## Enhancement
See the example below, the not-in list is very large, so decoding this not-in list can cost loads of CPU resources. And the optimizer chose `IndexJoin` in this case, this amplify this problem, the TiKV needs to decode this not-in list multiple times.
```
explain select * from t1, t2 where t1.a=t2.a and t2.b not in (...);
+-------------------------------+-----------+----------------------+-----------------------------------------------------------------------------------------------------------------+
| id | task | access object | operator info |
+-------------------------------+-----------+----------------------+-----------------------------------------------------------------------------------------------------------------+
| IndexHashJoin_13 | root | | inner join, inner:IndexLookUp_29, outer key:test.t1.a, inner key:test.t2.a, equal cond:eq(test.t1.a, test.t2.a) |
| ├─TableReader_24(Build) | root | | data:Selection_23 |
| │ └─Selection_23 | cop[tikv] | | not(isnull(test.t1.a)) |
| │ └─TableFullScan_22 | cop[tikv] | table:t1 | keep order:false |
| └─IndexLookUp_29(Probe) | root | | |
| ├─Selection_27(Build) | cop[tikv] | | not(isnull(test.t2.a)) |
| │ └─IndexRangeScan_25 | cop[tikv] | table:t2, index:a(a) | range: decided by [eq(test.t2.a, test.t1.a)], keep order:false, stats:pseudo |
| └─Selection_28(Probe) | cop[tikv] | | not(in(test.t2.b, ...)) |
| └─TableRowIDScan_26 | cop[tikv] | table:t2 | keep order:false, stats:pseudo |
+-------------------------------+-----------+----------------------+-----------------------------------------------------------------------------------------------------------------+
```
Below is the TiKV CPU Profile, a large amount of CPU is spent on decoding requests and building executors, because the not-in list is too large.
```
TiKV CPU Profile:
- grpc-server CPU: decoding cop request (because the not-in list is too large)
- protobuf::rt::read_singular_message_into 47.86%
- protobuf::rt::read_repeated_message_into 48.14%
- tipb::protos::expression::Expr::merge_from 47.76%
- tipb::protos::select::DagRequest::merge_from
- unified-read-po CPU: build and construct the executor (because the not-in list is too large)
- tidb_query_expr::types::expr_builder::handle_node_fn_call 26.88% cum
- BatchExecutorsRunner::from_request / build_executors / BatchSelectionExecutor::new
- tidb_query_expr::impl_compare_in::compare_in_int_type_by_hash_fn_meta::init_metadata 9.44%
```
After discussing with AI, below are some possible solutions to mitigate this:
1. rewrite the large not-in into a "tmp table + join", for example, insert all values in this list to a tmp table and then rewrite "where b not in (1, 2, ...)" to "where b not in (select _b from tmp_table)";
2. compress the large list, for example, "WHERE b NOT IN (1,2,3,...,1000,2000,2001,...,10000)" to "WHERE b <= 0 OR b BETWEEN 1001 AND 1999 OR b >= 10001" if b is integer;
3. consider the large not-in list encoding/decoding cost as penalty in IndexJoin's cost formula, then the optimizer would prefer HashJoin for this case;
4. just avoid pushing down the large not-in list to the probe side of IndexJoin to avoid this amplification;
Now the solution 4 and 2 should have the highest ROI, and 1 is the most thorough solution, 3 might not work well for large tables (HashJoin would cause large Scan).
Contributor guide
Research direction
Start with the EXPLAIN example and TiKV CPU profile, then trace how a large NOT IN list reaches the IndexJoin probe side and is decoded and used to build executors repeatedly. Done means selecting and implementing one mitigation, with a reproducible regression or benchmark showing that the CPU amplification is reduced.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- go, sql
- Domain
- databases, performance
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Quiet
- Clarity
- Mostly clear
- Newbie friendliness
- 35/100