Optimal ranges cannot be built in some case

[xuyifangreeneyes]

Bug Report

Please answer these questions before submitting your issue. Thanks!

1. Minimal reproduce step (Required)

create table t(id int, a varchar(100), b int, c int, index idx_ab(a, b));
explain select id, c from t use index (idx_ab) where ((a = 't' and b = 1) or (a = 't' and b = 2) or (a = 'w' and b = 0)) and c != 0;

2. What did you expect to see? (Required)

mysql> explain select id, c from t use index (idx_ab) where ((a = 't' and b = 1) or (a = 't' and b = 2) or (a = 'w' and b = 0)) and c != 0;
+---------------------------------+---------+-----------+-----------------------------+-----------------------------------------------------------------------------------+
| id                              | estRows | task      | access object               | operator info                                                                     |
+---------------------------------+---------+-----------+-----------------------------+-----------------------------------------------------------------------------------+
| Projection_4                    | 0.20    | root      |                             | test.t.id, test.t.c                                                               |
| └─IndexLookUp_8                 | 0.20    | root      |                             |                                                                                   |
|   ├─IndexRangeScan_5(Build)     | 0.30    | cop[tikv] | table:t, index:idx_ab(a, b) | range:["t" 1,"t" 2], ["w" 0,"w" 0], keep order:false, stats:pseudo |
|   └─Selection_7(Probe)          | 0.20    | cop[tikv] |                             | ne(test.t.c, 0)                                                                   |
|     └─TableRowIDScan_6          | 0.30    | cop[tikv] | table:t                     | keep order:false, stats:pseudo                                                    |
+---------------------------------+---------+-----------+-----------------------------+-----------------------------------------------------------------------------------+
5 rows in set (0.00 sec)

3. What did you see instead (Required)

mysql> explain select id, c from t use index (idx_ab) where ((a = 't' and b = 1) or (a = 't' and b = 2) or (a = 'w' and b = 0)) and c != 0;
+------------------------------+---------+-----------+-----------------------------+-----------------------------------------------------------------------------------------------------------------------------------+
| id                           | estRows | task      | access object               | operator info                                                                                                                     |
+------------------------------+---------+-----------+-----------------------------+-----------------------------------------------------------------------------------------------------------------------------------+
| Projection_4                 | 0.20    | root      |                             | test.t.id, test.t.c                                                                                                               |
| └─IndexLookUp_9              | 0.20    | root      |                             |                                                                                                                                   |
|   ├─Selection_7(Build)       | 0.20    | cop[tikv] |                             | or(and(eq(test.t.a, "t"), eq(test.t.b, 1)), or(and(eq(test.t.a, "t"), eq(test.t.b, 2)), and(eq(test.t.a, "w"), eq(test.t.b, 0)))) |
|   │ └─IndexRangeScan_5       | 20.00   | cop[tikv] | table:t, index:idx_ab(a, b) | range:["t","t"], ["w","w"], keep order:false, stats:pseudo                                                                        |
|   └─Selection_8(Probe)       | 0.20    | cop[tikv] |                             | ne(test.t.c, 0)                                                                                                                   |
|     └─TableRowIDScan_6       | 0.20    | cop[tikv] | table:t                     | keep order:false, stats:pseudo                                                                                                    |
+------------------------------+---------+-----------+-----------------------------+-----------------------------------------------------------------------------------------------------------------------------------+
6 rows in set (0.00 sec)

4. What is your TiDB version? (Required)

master

[xuyifangreeneyes]

It looks like a corner case since the following cases work:

mysql> explain select id, c from t use index (idx_ab) where ((a = 't' and b = 1) or (a = 't' and b = 3) or (a = 'w' and b = 0)) and c != 0;
+---------------------------------+---------+-----------+-----------------------------+-----------------------------------------------------------------------------------+
| id                              | estRows | task      | access object               | operator info                                                                     |
+---------------------------------+---------+-----------+-----------------------------+-----------------------------------------------------------------------------------+
| Projection_4                    | 0.20    | root      |                             | test.t.id, test.t.c                                                               |
| └─IndexLookUp_8                 | 0.20    | root      |                             |                                                                                   |
|   ├─IndexRangeScan_5(Build)     | 0.30    | cop[tikv] | table:t, index:idx_ab(a, b) | range:["t" 1,"t" 1], ["t" 3,"t" 3], ["w" 0,"w" 0], keep order:false, stats:pseudo |
|   └─Selection_7(Probe)          | 0.20    | cop[tikv] |                             | ne(test.t.c, 0)                                                                   |
|     └─TableRowIDScan_6          | 0.30    | cop[tikv] | table:t                     | keep order:false, stats:pseudo                                                    |
+---------------------------------+---------+-----------+-----------------------------+-----------------------------------------------------------------------------------+
5 rows in set (0.00 sec)

mysql> explain select id, c from t use index (idx_ab) where (a = 't' and b = 1) or (a = 't' and b = 2) or (a = 'w' and b = 0);
+---------------------------------+---------+-----------+-----------------------------+--------------------------------------------------------------------+
| id                              | estRows | task      | access object               | operator info                                                      |
+---------------------------------+---------+-----------+-----------------------------+--------------------------------------------------------------------+
| Projection_4                    | 2.60    | root      |                             | test.t.id, test.t.c                                                |
| └─IndexLookUp_7                 | 3.25    | root      |                             |                                                                    |
|   ├─IndexRangeScan_5(Build)     | 3.25    | cop[tikv] | table:t, index:idx_ab(a, b) | range:["t" 1,"t" 2], ["w" 0,"w" 0], keep order:false, stats:pseudo |
|   └─TableRowIDScan_6(Probe)     | 3.25    | cop[tikv] | table:t                     | keep order:false, stats:pseudo                                     |
+---------------------------------+---------+-----------+-----------------------------+--------------------------------------------------------------------+
4 rows in set (0.01 sec)

mysql> explain select id, c from t use index (idx_ab) where ((a = 't' and b = 1) or (a = 's' and b = 2) or (a = 'w' and b = 0)) and c != 0;
+---------------------------------+---------+-----------+-----------------------------+-----------------------------------------------------------------------------------+
| id                              | estRows | task      | access object               | operator info                                                                     |
+---------------------------------+---------+-----------+-----------------------------+-----------------------------------------------------------------------------------+
| Projection_4                    | 0.20    | root      |                             | test.t.id, test.t.c                                                               |
| └─IndexLookUp_8                 | 0.20    | root      |                             |                                                                                   |
|   ├─IndexRangeScan_5(Build)     | 0.30    | cop[tikv] | table:t, index:idx_ab(a, b) | range:["s" 2,"s" 2], ["t" 1,"t" 1], ["w" 0,"w" 0], keep order:false, stats:pseudo |
|   └─Selection_7(Probe)          | 0.20    | cop[tikv] |                             | ne(test.t.c, 0)                                                                   |
|     └─TableRowIDScan_6          | 0.30    | cop[tikv] | table:t                     | keep order:false, stats:pseudo                                                    |
+---------------------------------+---------+-----------+-----------------------------+-----------------------------------------------------------------------------------+
5 rows in set (0.00 sec)

[xuyifangreeneyes]

When building ranges, here is the code path: DetachCondAndBuildRangeForIndex -> detachCondAndBuildRangeForCols -> detachCNFCondAndBuildRangeForIndex -> extractIndexPointRangesForCNF. In extractIndexPointRangesForCNF, we call DetachCondAndBuildRangeForIndex for (a = 't' and b = 1) or (a = 't' and b = 2) or (a = 'w' and b = 0) and get ["t" 1,"t" 2], ["w" 0,"w" 0]. Since the ranges are not all points, pointRes returned by extractIndexPointRangesForCNF is nil, which is the root cause for the issue.

[xuyifangreeneyes]

When we call DetachCondAndBuildRangeForIndex for (a = 't' and b = 1) or (a = 't' and b = 2) or (a = 'w' and b = 0), it would merge consecutive ranges, i.e., convert ["t" 1,"t" 1], ["t" 2,"t" 2], ["w" 0,"w" 0] to ["t" 1,"t" 2], ["w" 0,"w" 0]. We should not merge consecutive ranges here because we hope to generate point ranges here. Not merging consecutive ranges can fix the issue.