optimize the list partition pruner for range query,

[crazycs520]

Bug Report

Please answer these questions before submitting your issue. Thanks!

1. Minimal reproduction step (Required)

For the list partition table:

set @@session.tidb_enable_table_partition = nightly;
create table t (id int) partition by list  (id) (
	    partition p0 values in (1,2),
	    partition p1 values in (3,4),
	    partition p3 values in (5,null)
	);

Currently, range query can't prune partition:

test> desc select * from t where id < 3;
+------------------------+----------+-----------+-----------------------+--------------------------------+
| id                     | estRows  | task      | access object         | operator info                  |
+------------------------+----------+-----------+-----------------------+--------------------------------+
| PartitionUnion_9       | 9970.00  | root      |                       |                                |
| ├─TableReader_12       | 3323.33  | root      |                       | data:Selection_11              |
| │ └─Selection_11       | 3323.33  | cop[tikv] |                       | lt(test.t.id, 3)               |
| │   └─TableFullScan_10 | 10000.00 | cop[tikv] | table:t, partition:p0 | keep order:false, stats:pseudo |
| ├─TableReader_15       | 3323.33  | root      |                       | data:Selection_14              |
| │ └─Selection_14       | 3323.33  | cop[tikv] |                       | lt(test.t.id, 3)               |
| │   └─TableFullScan_13 | 10000.00 | cop[tikv] | table:t, partition:p1 | keep order:false, stats:pseudo |
| └─TableReader_18       | 3323.33  | root      |                       | data:Selection_17              |
|   └─Selection_17       | 3323.33  | cop[tikv] |                       | lt(test.t.id, 3)               |
|     └─TableFullScan_16 | 10000.00 | cop[tikv] | table:t, partition:p3 | keep order:false, stats:pseudo |
+------------------------+----------+-----------+-----------------------+--------------------------------+

But actually, we can use id < 3 to do partition prune, since only partition p0 contain the value that id<3. The expected result is:

test> desc select * from t where id < 3;
+------------------------+----------+-----------+-----------------------+--------------------------------+
| id                     | estRows  | task      | access object         | operator info                  |
+------------------------+----------+-----------+-----------------------+--------------------------------+
| PartitionUnion_9       | 9970.00  | root      |                       |                                |
| ├─TableReader_12       | 3323.33  | root      |                       | data:Selection_11              |
|   └─Selection_11       | 3323.33  | cop[tikv] |                       | lt(test.t.id, 3)               |
|     └─TableFullScan_10 | 10000.00 | cop[tikv] | table:t, partition:p0 | keep order:false, stats:pseudo |
+------------------------+----------+-----------+-----------------------+--------------------------------+

Idea

Use a BTree to store the all list partition values, for range query, traversal the range to find the partition in this range.

Samely, the list column partition can also use this optimization.

4. What is your TiDB version? (Required)

test> select tidb_version();
+-------------------------------------------------------------------+
| tidb_version()                                                    |
+-------------------------------------------------------------------+
| Release Version: v4.0.0-beta.2-1948-g9cb4fb38d                    |
| Edition: Community                                                |
| Git Commit Hash: 9cb4fb38d844204b7acba35f1784405c86476dbc         |
| Git Branch: master                                                |
| UTC Build Time: 2021-01-04 03:34:31                               |
| GoVersion: go1.15.6                                               |
| Race Enabled: false                                               |
| TiKV Min Version: v3.0.0-60965b006877ca7234adaced7890d7b029ed1306 |
| Check Table Before Drop: false                                    |
+-------------------------------------------------------------------+

[TszKitLo40]

I want to try this issue.

[TszKitLo40]

/assign