pingcap / pingcap/tidb

Enhance range extraction for complicated OR filter

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

Description

## Enhancement
```
drop table if exists t1;
CREATE TABLE `t1` (
`c1` bigint NOT NULL AUTO_INCREMENT COMMENT 'x1',
`c2` bigint NOT NULL DEFAULT '0' COMMENT 'x2',
`c3` tinyint NOT NULL DEFAULT '1' COMMENT 'x3',
`c4` int NOT NULL DEFAULT '0' COMMENT 'x4',
`c5` varchar(32) NOT NULL DEFAULT '' COMMENT 'x5',
`c6` varchar(16) NOT NULL DEFAULT '' COMMENT 'x6',
`c7` decimal(40,18) NOT NULL DEFAULT '0.000000000000000000' COMMENT 'x7',
`c8` decimal(40,18) NOT NULL DEFAULT '0.000000000000000000' COMMENT 'x8',
`c9` decimal(40,18) NOT NULL DEFAULT '0.000000000000000000' COMMENT 'x9',
`c10` decimal(40,18) NOT NULL DEFAULT '0.0000' COMMENT 'x10',
`c11` varchar(4096) NOT NULL DEFAULT '' COMMENT 'x11',
`c12` varchar(4096) NOT NULL DEFAULT '' COMMENT 'x12',
`c13` int NOT NULL DEFAULT '0' COMMENT 'x13',
`c14` bigint NOT NULL DEFAULT '0' COMMENT 'x14',
`c15` bigint NOT NULL DEFAULT '0' COMMENT 'x15',
`c16` varchar(32) NOT NULL DEFAULT '' COMMENT 'x16',
`c17` tinyint NOT NULL DEFAULT '2' COMMENT 'x17',
`c18` varchar(24) NOT NULL DEFAULT 'RMB' COMMENT 'x18',
`c19` varchar(1024) NOT NULL DEFAULT '' COMMENT 'x19',
`c20` tinyint NOT NULL DEFAULT '0' COMMENT 'x20',
`c21` varchar(16) NOT NULL DEFAULT '' COMMENT 'x21',
`c22` varchar(24) NOT NULL DEFAULT '' COMMENT 'x22',
`c23` decimal(40,18) NOT NULL DEFAULT '1.0000' COMMENT 'x23',
`c24` decimal(40,18) NOT NULL DEFAULT '1.0000' COMMENT 'x24',
`c25` bigint NOT NULL DEFAULT '0' COMMENT 'x25',
`c26` tinyint(1) NOT NULL DEFAULT '0' COMMENT 'x26',
PRIMARY KEY (`c1`),
KEY `i1` (`c15`,`c17`,`c2`),
KEY `i2` (`c2`,`c6`,`c21`),
KEY `i3` (`c14`,`c18`,`c8`),
KEY `i4` (`c14`,`c3`,`c4`,`c6`,`c25`),
KEY `i5` (`c14`,`c2`,`c18`,`c6`,`c25`),
KEY `i6` (`c4`,`c8`),
KEY `i7` (`c4`,`c6`,`c14`,`c1`),
KEY `i8` (`c2`,`c4`,`c14`,`c18`,`c8`),
KEY `i9` (`c2`,`c14`,`c25`),
KEY `i10` (`c4`,`c6`,`c14`,`c25`),
KEY `i11` (`c18`,`c14`,`c25`,`c1`),
KEY `i12` (`c14`,`c25`,`c1`),
KEY `i13` (`c14`,`c25`,`c21`),
KEY `i14` (`c5`,`c18`),
KEY `i15` (`c2`,`c6`,`c18`,`c26`,`c8`,`c14`),
KEY `i16` (`c2`,`c6`,`c26`,`c18`,`c14`,`c4`),
KEY `i17` (`c2`,`c6`,`c26`,`c14`,`c4`,`c18`),
KEY `i18` (`c4`,`c14`,`c25`,`c1`,`c18`),
KEY `i19` (`c2`,`c6`,`c18`,`c14`,`c25`,`c1`,`c9`),
KEY `i20` (`c16`)
);

INSERT INTO t1
(
c2, c3, c4, c5, c6,
c7, c8, c9, c10,
c11, c12, c13, c14, c15,
c16, c17, c18, c19, c20,
c21, c22, c23, c24,
c25, c26
)
WITH RECURSIVE seq AS (
SELECT 1 AS n
UNION ALL
SELECT n + 1 FROM seq WHERE n < 300000
)
SELECT
(n % 50000) + 1 AS c2,
1 AS c3,
(n % 16) + 1 AS c4,
CONCAT('X1', LPAD(n, 10, '0')) AS c5,
IF(n % 3 = 0, 'X2', 'X3') AS c6,
1000.0, 1.0, 1001.0, 0.0,
'', '', 0,
1747600000 + (n % 150000) AS c14,
(n % 1000) + 1 AS c15,
CONCAT('X4', LPAD(n, 10, '0')) AS c16,
2,
IF(n % 5 = 0, 'X2', 'X5') AS c18,
'',
0,
IF(n % 2 = 0, 'X6', 'X7') AS c21,
'',
1.0, 1.0,
(1747600000 + (n % 150000)) * 10 + (n % 10) AS c25,
0
FROM seq;

SELECT
t1.*
FROM
`t1`
WHERE
(
t1.c14 >= 1747663372
AND t1.c14 <= 1748705453
)
AND (
((t1.c14 < 1748015999))
OR (
(t1.c14 = 1748604343)
AND (t1.c25 < 216627868)
)
OR (
(t1.c14 = 1748604343)
AND (t1.c25 = 473050276)
AND (t1.c1 > 154835914)
)
)
ORDER BY
t1.c14 DESC,
t1.c25 DESC,
t1.c1 ASC
LIMIT
5000;
```

tidb Plan:
```
TiDB root@127.0.0.1:test> explain SELECT
-> t1.*
-> FROM
-> `t1`
-> WHERE
-> (
-> t1.c14 >= 1747663372
-> AND t1.c14 <= 1748705453
-> )
-> AND (
-> ((t1.c14 < 1748015999))
-> OR (
-> (t1.c14 = 1748604343)
-> AND (t1.c25 < 216627868)
-> )
-> OR (
-> (t1.c14 = 1748604343)
-> AND (t1.c25 = 473050276)
-> AND (t1.c1 > 154835914)
-> )
-> )
-> ORDER BY
-> t1.c14 DESC,
-> t1.c25 DESC,
-> t1.c1 ASC
-> LIMIT
-> 5000;
+------------------------------+---------+-----------+-----------------------------------+-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| id | estRows | task | access object | operator info |
+------------------------------+---------+-----------+-----------------------------------+-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| TopN_10 | 87.00 | root | | test.t1.c14:desc, test.t1.c25:desc, test.t1.c1, offset:0, count:5000 |
| └─IndexLookUp_29 | 87.28 | root | | |
| ├─TopN_28(Build) | 87.28 | cop[tikv] | | test.t1.c14:desc, test.t1.c25:desc, test.t1.c1, offset:0, count:5000 |
| │ └─Selection_18 | 87.28 | cop[tikv] | | or(lt(test.t1.c14, 1748015999), or(and(eq(test.t1.c14, 1748604343), lt(test.t1.c25, 216627868)), and(eq(test.t1.c14, 1748604343), and(eq(test.t1.c25, 473050276), gt(test.t1.c1, 154835914))))) |
| │ └─IndexRangeScan_16 | 260.00 | cop[tikv] | table:t1, index:i12(c14, c25, c1) | range:[1747663372,1748015999), [1748604343,1748604343], keep order:false, stats:pseudo |
| └─TableRowIDScan_17(Probe) | 87.28 | cop[tikv] | table:t1 | keep order:false, stats:pseudo |
+------------------------------+---------+-----------+-----------------------------------+-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
6 rows in set
Time: 0.023s
```

Better Plan: table scan range is better
```
MySQL [test]> explain SELECT
-> t1.*
-> FROM
-> `t1`
-> WHERE
-> (
-> t1.c14 >= 1747663372
-> AND t1.c14 <= 1748705453
-> )
-> AND (
-> ((t1.c14 < 1748015999))
-> OR (
-> (t1.c14 = 1748604343)
-> AND (t1.c25 < 216627868)
-> )
-> OR (
-> (t1.c14 = 1748604343)
-> AND (t1.c25 = 473050276)
-> AND (t1.c1 > 154835914)
-> )
-> )
-> ORDER BY
-> t1.c14 DESC,
-> t1.c25 DESC,
-> t1.c1 ASC
-> LIMIT
-> 5000;
+------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| Query Plan |
+------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| ================================================================= |
| |ID|OPERATOR |NAME |EST.ROWS|EST.TIME(us)| |
| ----------------------------------------------------------------- |
| |0 |NESTED-LOOP JOIN | |24142 |81828 | |
| |1 |├─SUBPLAN SCAN |VIEW1 |5000 |1275 | |
| |2 |│ └─TOP-N SORT | |5000 |1262 | |
| |3 |│ └─TABLE RANGE SCAN|t1(i12,Reverse)|5001 |757 | |
| |4 |└─TABLE GET |t1 |1 |16 | |
| ================================================================= |
| Outputs & filters: |
| ------------------------------------- |
| 0 - output([VIEW1.t1.c1], [t1.c2], [t1.c3], [t1.c4], [t1.c5], [t1.c6], [t1.c7], [t1.c8], [t1.c9], [t1.c10], [t1.c11], [t1.c12], [t1.c13], [VIEW1.t1.c14], |
| [t1.c15], [t1.c16], [t1.c17], [t1.c18], [t1.c19], [t1.c20], [t1.c21], [t1.c22], [t1.c23], [t1.c24], [VIEW1.t1.c25], [t1.c26]), filter(nil), rowset=256 |
| conds(nil), nl_params_([VIEW1.t1.c1(:0)]), use_batch=true |
| 1 - output([VIEW1.t1.c1], [VIEW1.t1.c14], [VIEW1.t1.c25]), filter(nil), rowset=256 |
| access([VIEW1.t1.c1], [VIEW1.t1.c14], [VIEW1.t1.c25]) |
| 2 - output([t1.c1], [t1.c14], [t1.c25]), filter(nil), rowset=256 |
| sort_keys([t1.c14, DESC], [t1.c25, DESC], [t1.c1, ASC]), topn(5000), prefix_pos(2) |
| 3 - output([t1.c1], [t1.c14], [t1.c25]), filter([(T_OP_OR, t1.c14 < 1748015999, t1.c14 = 1748604343 AND t1.c25 < 216627868, (T_OP_AND, t1.c14 = 1748604343, |
| t1.c25 = 473050276, t1.c1 > 154835914))]), rowset=256 |
| access([t1.c1], [t1.c14], [t1.c25]), partitions(p0) |
| is_index_back=false, is_global_index=false, filter_before_indexback[false], |
| range_key([t1.c14], [t1.c25], [t1.c1]), range(1747663372,MIN,MIN ; 1748015999,MIN,MIN), (1748604343,NULL,MAX ; 1748604343,216627868,MIN), (1748604343, |
| 473050276,154835914 ; 1748604343,473050276,MAX), |
| range_cond([(T_OP_OR, (T_OP_AND, t1.c14 >= 1747663372, t1.c14 <= 1748705453, t1.c14 < 1748015999), (T_OP_AND, t1.c14 >= 1747663372, t1.c14 <= 1748705453, |
| t1.c14 = 1748604343, t1.c25 < 216627868), (T_OP_AND, t1.c14 >= 1747663372, t1.c14 <= 1748705453, t1.c14 = 1748604343, t1.c25 = 473050276, t1.c1 > 154835914))]) |
| 4 - output([t1.c2], [t1.c3], [t1.c4], [t1.c5], [t1.c6], [t1.c7], [t1.c8], [t1.c9], [t1.c10], [t1.c11], [t1.c12], [t1.c13], [t1.c15], [t1.c16], [t1.c17], |
| [t1.c18], [t1.c19], [t1.c20], [t1.c21], [t1.c22], [t1.c23], [t1.c24], [t1.c26]), filter(nil), rowset=256 |
| access([GROUP_ID], [t1.c2], [t1.c3], [t1.c4], [t1.c5], [t1.c6], [t1.c7], [t1.c8], [t1.c9], [t1.c10], [t1.c11], [t1.c12], [t1.c13], [t1.c15], [t1.c16], |
| [t1.c17], [t1.c18], [t1.c19], [t1.c20], [t1.c21], [t1.c22], [t1.c23], [t1.c24], [t1.c26]), partitions(p0) |
| is_index_back=false, is_global_index=false, |
| range_key([t1.c1]), range(MIN ; MAX), |
| range_cond([t1.c1 = :0]) |
+------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
33 rows in set (0.057 sec)
```

```
TiDB root@127.0.0.1:test> select tidb_version();
+-----------------------------------------------------------+
| tidb_version() |
+-----------------------------------------------------------+
| Release Version: v9.0.0-beta.2.pre-1126-g550a05a2ff |
| Edition: Community |
| Git Commit Hash: 550a05a2ff087bab7260f5dc6f8542b1f82e22e8 |
| Git Branch: master |
| UTC Build Time: 2026-01-28 10:21:18 |
| GoVersion: go1.25.6 |
| Race Enabled: false |
| Check Table Before Drop: false |
| Store: unistore |
| Kernel Type: Classic |
+-----------------------------------------------------------+
1 row in set
Time: 0.003s
```

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.