pingcap / pingcap/tidb

planner: IndexJoin + large not-in list cause TiKV CPU spike

Open
#67,573 0 comments 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
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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.