pingcap / pingcap/tidb

planner: expand the DNF expression to construct precise scan ranges

Open
#63,417 0 comments 0 reactions 1 assignee Claimed by @hawkingrei View on GitHub
plan-rewrite 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 case below:
```
create table t (a int, b int, c int, d int, e int, key(a, b, c, d));

explain select 1
from t
where
a = 1
and ( b > 0 or (b = 0 and d > 0))
and c = 1;
+----------------------------+---------+-----------+------------------------------+-----------------------------------------------------------------------------+
| id | estRows | task | access object | operator info |
+----------------------------+---------+-----------+------------------------------+-----------------------------------------------------------------------------+
| Projection_4 | 1.00 | root | | 1->Column#7 |
| └─IndexReader_8 | 1.00 | root | | index:Selection_7 |
| └─Selection_7 | 1.00 | cop[tikv] | | eq(test.t.c, 1), or(gt(test.t.b, 0), and(eq(test.t.b, 0), gt(test.t.d, 0))) |
| └─IndexRangeScan_6 | 33.43 | cop[tikv] | table:t, index:a(a, b, c, d) | range:[1 0,1 0], (1 0,1 +inf], keep order:false, stats:pseudo |
+----------------------------+---------+-----------+------------------------------+-----------------------------------------------------------------------------+
```
In the case above, we can only use the first 2 columns in the index to construct the scan ranges: `[1 0,1 0], (1 0,1 +inf]`.
Actually we can expand and rewrite the DNF with this formula: `A and (B or C) and D --> (A and B and D) or (A and C and D)`.
Then we'll get a precise and better key scan range:
```
explain select 1
from t
where
(a = 1 and b > 0 and c = 1)
or
(a = 1 and b = 0 and c = 1 and d > 0);
+----------------------------+---------+-----------+------------------------------+----------------------------------------------------------------------------------------------------------------------------------------------------+
| id | estRows | task | access object | operator info |
+----------------------------+---------+-----------+------------------------------+----------------------------------------------------------------------------------------------------------------------------------------------------+
| Projection_4 | 26.67 | root | | 1->Column#7 |
| └─IndexReader_8 | 26.67 | root | | index:Selection_7 |
| └─Selection_7 | 26.67 | cop[tikv] | | or(and(eq(test.t.a, 1), and(gt(test.t.b, 0), eq(test.t.c, 1))), and(and(eq(test.t.a, 1), eq(test.t.b, 0)), and(eq(test.t.c, 1), gt(test.t.d, 0)))) |
| └─IndexRangeScan_6 | 33.34 | cop[tikv] | table:t, index:a(a, b, c, d) | range:(1 0 1 0,1 0 1 +inf], (1 0,1 +inf], keep order:false, stats:pseudo |
+----------------------------+---------+-----------+------------------------------+----------------------------------------------------------------------------------------------------------------------------------------------------+
```
After the rewriting, the new scan range is `(1 0 1 0,1 0 1 +inf], (1 0,1 +inf]`, which can take advantage of more columns in this index.

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.