index merge union case order property may be interrupted by implicit handle's reorder for cop location convenience

[AilinKid]

Bug Report

Please answer these questions before submitting your issue. Thanks!

source: #52901

1. Minimal reproduce step (Required)

mysql> show create table tbl_43;
+--------+----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| Table  | Create Table                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                   |
+--------+----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| tbl_43 | CREATE TABLE `tbl_43` (
  `col_304` binary(207) NOT NULL DEFAULT 'eIenHx\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0',
  PRIMARY KEY (`col_304`) /*T![clustered_index] CLUSTERED */,
  UNIQUE KEY `idx_259` (`col_304`(5)),
  UNIQUE KEY `idx_260` (`col_304`(2)),
  KEY `idx_261` (`col_304`),
  UNIQUE KEY `idx_262` (`col_304`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8 COLLATE=utf8_bin |
+--------+----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+

mysql> select * from tbl_43;
+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| col_304                                                                                                                                                                                                         |
+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| BCmuENPHzSOIMJLPB                                                                                                                                                                                               |
| LDOdXZYpOR                                                                                                                                                                                                      |
| R                                                                                                                                                                                                               |
| TloTqcHhdgpwvMsSoJ                                                                                                                                                                                              |
| UajN                                                                                                                                                                                                            |
| mAwLZbiyq                                                                                                                                                                                                       |
| swLIoWa                                                                                                                                                                                                         |
+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+

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

they should be BCmuENPHzSOIMJLPB and swLIoWa

3. What did you see instead (Required)

mysql> select * from (select /*+ use_index_merge( tbl_43 ) */ * from tbl_43 where not( tbl_43.col_304 between 'YEpfYfPVvhMlHGHSMKm' and 'PE' ) or tbl_43.col_304 in ( 'LUBGzGMA' ) and tbl_43.col_304 between 'HpsjfuSReCwBoh' and 'fta' or not( tbl_43.col_304 between 'MFWmuOsoyDv' and 'TSeMYpDXnFIyp' ) order by col_304 desc) x limit 1;
+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| col_304                                                                                                                                                                                                         |
+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| BCmuENPHzSOIMJLPB                                                                                                                                                                                               |
+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
1 row in set (0.07 sec)

mysql> explain  select * from (select /*+ use_index_merge( tbl_43 ) */ * from tbl_43 where not( tbl_43.col_304 between 'YEpfYfPVvhMlHGHSMKm' and 'PE' ) or tbl_43.col_304 in ( 'LUBGzGMA' ) and tbl_43.col_304 between 'HpsjfuSReCwBoh' and 'fta' or not( tbl_43.col_304 between 'MFWmuOsoyDv' and 'TSeMYpDXnFIyp' ) order by col_304 desc) x limit 1;
+----------------------------------+---------+-----------+--------------------------------------+------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| id                               | estRows | task      | access object                        | operator info                                                                                                                                                                                                                |
+----------------------------------+---------+-----------+--------------------------------------+------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| Limit_13                         | 1.00    | root      |                                      | offset:0, count:1                                                                                                                                                                                                            |
| └─IndexMerge_35                  | 1.00    | root      |                                      | type: union                                                                                                                                                                                                                  |
|   ├─Selection_27(Build)          | 0.00    | cop[tikv] |                                      | 1                                                                                                                                                                                                                            |
|   │ └─TableRangeScan_26          | 0.00    | cop[tikv] | table:tbl_43                         | range:["LUBGzGMA","LUBGzGMA"], keep order:true, desc, stats:pseudo                                                                                                                                                           |
|   ├─IndexRangeScan_28(Build)     | 0.33    | cop[tikv] | table:tbl_43, index:idx_261(col_304) | range:[-inf,"YEpfYfPVvhMlHGHSMKm"), keep order:true, desc, stats:pseudo                                                                                                                                                      |
|   ├─IndexRangeScan_29(Build)     | 0.33    | cop[tikv] | table:tbl_43, index:idx_262(col_304) | range:("PE",+inf], keep order:true, desc, stats:pseudo                                                                                                                                                                       |
|   ├─TableRangeScan_30(Build)     | 0.33    | cop[tikv] | table:tbl_43                         | range:[-inf,"MFWmuOsoyDv"), keep order:true, desc, stats:pseudo                                                                                                                                                              |
|   ├─TableRangeScan_31(Build)     | 0.33    | cop[tikv] | table:tbl_43                         | range:("TSeMYpDXnFIyp",+inf], keep order:true, desc, stats:pseudo                                                                                                                                                            |
|   └─Limit_34(Probe)              | 1.00    | cop[tikv] |                                      | offset:0, count:1                                                                                                                                                                                                            |
|     └─Selection_33               | 1.00    | cop[tikv] |                                      | or(or(lt(test.tbl_43.col_304, "YEpfYfPVvhMlHGHSMKm"), gt(test.tbl_43.col_304, "PE")), or(and(eq(test.tbl_43.col_304, "LUBGzGMA"), 1), or(lt(test.tbl_43.col_304, "MFWmuOsoyDv"), gt(test.tbl_43.col_304, "TSeMYpDXnFIyp")))) |
|       └─TableRowIDScan_32        | 1.00    | cop[tikv] | table:tbl_43                         | keep order:false, stats:pseudo                                                                                                                                                                                               |
+----------------------------------+---------+-----------+--------------------------------------+------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
11 rows in set (0.03 sec)

mysql> select * from (select /*+ use_index_merge( tbl_43 ) */ * from tbl_43 where not( tbl_43.col_304 between 'YEpfYfPVvhMlHGHSMKm' and 'PE' ) or tbl_43.col_304 in ( 'LUBGzGMA' ) and tbl_43.col_304 between 'HpsjfuSReCwBoh' and 'fta' or not( tbl_43.col_304 between 'MFWmuOsoyDv' and 'TSeMYpDXnFIyp' ) order by col_304) x limit 1;
+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| col_304                                                                                                                                                                                                         |
+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| BCmuENPHzSOIMJLPB                                                                                                                                                                                               |
+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
1 row in set (0.04 sec)

mysql> explain select * from (select /*+ use_index_merge( tbl_43 ) */ * from tbl_43 where not( tbl_43.col_304 between 'YEpfYfPVvhMlHGHSMKm' and 'PE' ) or tbl_43.col_304 in ( 'LUBGzGMA' ) and tbl_43.col_304 between 'HpsjfuSReCwBoh' and 'fta' or not( tbl_43.col_304 between 'MFWmuOsoyDv' and 'TSeMYpDXnFIyp' ) order by col_304) x limit 1;
+----------------------------------+---------+-----------+--------------------------------------+------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| id                               | estRows | task      | access object                        | operator info                                                                                                                                                                                                                |
+----------------------------------+---------+-----------+--------------------------------------+------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| Limit_13                         | 1.00    | root      |                                      | offset:0, count:1                                                                                                                                                                                                            |
| └─IndexMerge_35                  | 1.00    | root      |                                      | type: union                                                                                                                                                                                                                  |
|   ├─Selection_27(Build)          | 0.00    | cop[tikv] |                                      | 1                                                                                                                                                                                                                            |
|   │ └─TableRangeScan_26          | 0.00    | cop[tikv] | table:tbl_43                         | range:["LUBGzGMA","LUBGzGMA"], keep order:true, stats:pseudo                                                                                                                                                                 |
|   ├─IndexRangeScan_28(Build)     | 0.33    | cop[tikv] | table:tbl_43, index:idx_261(col_304) | range:[-inf,"YEpfYfPVvhMlHGHSMKm"), keep order:true, stats:pseudo                                                                                                                                                            |
|   ├─IndexRangeScan_29(Build)     | 0.33    | cop[tikv] | table:tbl_43, index:idx_262(col_304) | range:("PE",+inf], keep order:true, stats:pseudo                                                                                                                                                                             |
|   ├─TableRangeScan_30(Build)     | 0.33    | cop[tikv] | table:tbl_43                         | range:[-inf,"MFWmuOsoyDv"), keep order:true, stats:pseudo                                                                                                                                                                    |
|   ├─TableRangeScan_31(Build)     | 0.33    | cop[tikv] | table:tbl_43                         | range:("TSeMYpDXnFIyp",+inf], keep order:true, stats:pseudo                                                                                                                                                                  |
|   └─Limit_34(Probe)              | 1.00    | cop[tikv] |                                      | offset:0, count:1                                                                                                                                                                                                            |
|     └─Selection_33               | 1.00    | cop[tikv] |                                      | or(or(lt(test.tbl_43.col_304, "YEpfYfPVvhMlHGHSMKm"), gt(test.tbl_43.col_304, "PE")), or(and(eq(test.tbl_43.col_304, "LUBGzGMA"), 1), or(lt(test.tbl_43.col_304, "MFWmuOsoyDv"), gt(test.tbl_43.col_304, "TSeMYpDXnFIyp")))) |
|       └─TableRowIDScan_32        | 1.00    | cop[tikv] | table:tbl_43                         | keep order:false, stats:pseudo                                                                                                                                                                                               |
+----------------------------------+---------+-----------+--------------------------------------+------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
11 rows in set (0.07 sec)

4. What is your TiDB version? (Required)

mysql> select version();
+--------------------------------+
| version() |
+--------------------------------+
| 8.0.11-TiDB-v8.2.0-alpha-dirty |
+--------------------------------+
1 row in set (0.03 sec)

[AilinKid]

heap popping logic is according to row_idx, which may interrupt the UNION case pushes down order property

in the second case, we use an ascending order order by col_304 , the heap sort is the same as the order of col_304, because it's pk, so the result is as expected.
in the first case, we use a descending order order by col_304 desc, while the output is the same. we should adjust the heap sort logic maybe.

[Defined2014]

This has nothing to do with the heap. When create tableReader in indexMerge, the rangeKey will be reordered. The Limit is pushed down to the tableReader, it will return after reading one row which is incorrect.

[AilinKid]

[AilinKid]

that's why the table's limit violated the index order semantic, or we should say the index-order-restore work is too late for an injection.