planner: utilize prefix of columns in order-limit clause to avoid full table scan in join queries

[qw4990]

Enhancement

See the query and plan below, we have to full scan these 2 tables since columns in the order-limit clause are from different sides, then we can't push the Limit down through the Join.

create table t1 (a int, b int, c int, d int, key b(b));
create table t2 (a int, b int, c int, d int, key a(a));

explain select *  from t1 join t2 on t1.a=t2.a
order by t1.b, t2.b limit 100;
+--------------------------------+----------+-----------+---------------+----------------------------------------------+
| id                             | estRows  | task      | access object | operator info                                |
+--------------------------------+----------+-----------+---------------+----------------------------------------------+
| TopN_14                        | 100.00   | root      |               | test.t1.b, test.t2.b, offset:0, count:100    |
| └─HashJoin_32                  | 12487.50 | root      |               | inner join, equal:[eq(test.t1.a, test.t2.a)] |
|   ├─TableReader_43(Build)      | 9990.00  | root      |               | data:Selection_42                            |
|   │ └─Selection_42             | 9990.00  | cop[tikv] |               | not(isnull(test.t2.a))                       |
|   │   └─TableFullScan_41       | 10000.00 | cop[tikv] | table:t2      | keep order:false, stats:pseudo               |
|   └─TableReader_36(Probe)      | 9990.00  | root      |               | data:Selection_35                            |
|     └─Selection_35             | 9990.00  | cop[tikv] |               | not(isnull(test.t1.a))                       |
|       └─TableFullScan_34       | 10000.00 | cop[tikv] | table:t1      | keep order:false, stats:pseudo               |
+--------------------------------+----------+-----------+---------------+----------------------------------------------+

But actually, we could first use some prefix columns of order-limit clause to avoid full table scan, and then order the final results by 2 columns at the end, which is like:

-- it seems like we rewrite the query above to the below query:
explain select * from (
  select /*+ order_index(t1, b) */ 
  t1.b as t1b, t2.b as t2b from t1 join t2 on t1.a=t2.a
  order by t1.b limit 100
) tt order by tt.t1b, tt.t2b limit 100;

+-----------------------------------------+---------+-----------+----------------------+-----------------------------------------------------------------------------------------------------------------+
| id                                      | estRows | task      | access object        | operator info                                                                                                   |
+-----------------------------------------+---------+-----------+----------------------+-----------------------------------------------------------------------------------------------------------------+
| TopN_18                                 | 100.00  | root      |                      | test.t1.b, test.t2.b, offset:0, count:100                                                                       |
| └─Limit_29                              | 100.00  | root      |                      | offset:0, count:100                                                                                             |
|   └─IndexHashJoin_51                    | 100.00  | root      |                      | inner join, inner:IndexLookUp_60, outer key:test.t1.a, inner key:test.t2.a, equal cond:eq(test.t1.a, test.t2.a) |
|     ├─Projection_56(Build)              | 80.00   | root      |                      | test.t1.a, test.t1.b                                                                                            |
|     │ └─IndexLookUp_55                  | 80.00   | root      |                      |                                                                                                                 |
|     │   ├─IndexFullScan_52(Build)       | 179.28  | cop[tikv] | table:t1, index:b(b) | keep order:true, stats:pseudo                                                                                   |
|     │   └─Selection_54(Probe)           | 80.00   | cop[tikv] |                      | not(isnull(test.t1.a))                                                                                          |
|     │     └─TableRowIDScan_53           | 179.28  | cop[tikv] | table:t1             | keep order:false, stats:pseudo                                                                                  |
|     └─IndexLookUp_60(Probe)             | 100.00  | root      |                      |                                                                                                                 |
|       ├─Selection_59(Build)             | 100.00  | cop[tikv] |                      | not(isnull(test.t2.a))                                                                                          |
|       │ └─IndexRangeScan_57             | 100.10  | cop[tikv] | table:t2, index:a(a) | range: decided by [eq(test.t2.a, test.t1.a)], keep order:false, stats:pseudo                                    |
|       └─TableRowIDScan_58(Probe)        | 100.00  | cop[tikv] | table:t2             | keep order:false, stats:pseudo                                                                                  |
+-----------------------------------------+---------+-----------+----------------------+-----------------------------------------------------------------------------------------------------------------+

One thing we have to be careful with is that we need to read all rows in t1 that have the same value on column t1.b with the 100th row.
In the below example, we have to read 1~102 rows, since row-101 and row-102 have the same t1.b value with row-100.
So the limit 100 in the sub-query is not exactly accurate.

row_id    t1.b
1         1
2         1
3         2
...
99        13
100       13
101       13
102       13
103       14

[qw4990]

This cool idea is from @windtalker

[qw4990]

Have the similar idea with #48241.

[elsa0520]

We can directly rewrite the query like instead of add the limit inside of subquery. It can protect the all same t1.b rows can be returned.

explain select * from (
  select /*+ order_index(t1, b) */ 
  t1.b as t1b, t2.b as t2b from t1 join t2 on t1.a=t2.a
  order by t1.b 
) tt order by tt.t1b, tt.t2b limit 100;

Although this case may be slower than the case with a limit, it depends on the ndv of t1.b.

[elsa0520]

There is also a more prefect solution in DB2 - Partial order with FETCH FIRST http://www.alabamadb2usersgroup.org/presentations/2016-DB2-12-Optimizer-Alabama-DB2-User-Group.pdf

[windtalker]

an directly rewrite the query like inst

but for this sql, the execution can not stop earlier which means we still need get whole result of the subquery?

select /*+ order_index(t1, b) */ 
  t1.b as t1b, t2.b as t2b from t1 join t2 on t1.a=t2.a
  order by t1.b 

[elsa0520]

Yes, but it can reduce the inner order by because the keeporder:true. Also it can choose the IndexScan and IndexJoin which is faster than HashJoin and TableFullScan.

The outside order cannot be reduced rows. If the inner ndv(t1.b) is smaller than limit number which means both of two ways need get whole result of the subquery. But if the inner ndv(t1.b) is more than limit number. The way in the first comment is better.

[qw4990]

Another similar case from another user:

CREATE TABLE `t8` (
  `a` int,
  `b` varchar(120) default null,
  `c` datetime,
  `d` varchar(100),
  KEY ixbd(a, d(2))
);
set @@cte_max_recursion_depth=10000000;
INSERT INTO t8 (a, b, c, d)
SELECT mod(a,10) as a, 1 AS b, timestampadd(second, a, now()), a as d
FROM (
    WITH RECURSIVE x AS (
        SELECT 1 AS a
        UNION ALL
        SELECT a + 1 AS a
        FROM x
        WHERE a < 1000000
    )
    SELECT a
    FROM x
) AS subquery;
Analyze table t8;
explain select * from t8 where a = 1 order by d limit 5;
+------------------------------+------------+-----------+---------------+------------------------------+
| id                           | estRows    | task      | access object | operator info                |
+------------------------------+------------+-----------+---------------+------------------------------+
| TopN_9                       | 5.00       | root      |               | test.t8.d, offset:0, count:5 |
| └─TableReader_19             | 5.00       | root      |               | data:TopN_18                 |
|   └─TopN_18                  | 5.00       | cop[tikv] |               | test.t8.d, offset:0, count:5 |
|     └─Selection_17           | 99869.50   | cop[tikv] |               | eq(test.t8.a, 1)             |
|       └─TableFullScan_16     | 1000000.00 | cop[tikv] | table:t8      | keep order:false             |
+------------------------------+------------+-----------+---------------+------------------------------+

We are using TableFullScan now, and if we specify the index, the plan could be:

+----------------------------------+----------+-----------+----------------------------+-------------------------------+
| id                               | estRows  | task      | access object              | operator info                 |
+----------------------------------+----------+-----------+----------------------------+-------------------------------+
| TopN_10                          | 5.00     | root      |                            | test.t8.d, offset:0, count:5  |
| └─IndexLookUp_19                 | 5.00     | root      |                            |                               |
|   ├─IndexRangeScan_16(Build)     | 99869.50 | cop[tikv] | table:t8, index:ixbd(a, d) | range:[1,1], keep order:false |
|   └─TopN_18(Probe)               | 5.00     | cop[tikv] |                            | test.t8.d, offset:0, count:5  |
|     └─TableRowIDScan_17          | 99869.50 | cop[tikv] | table:t8                   | keep order:false              |
+----------------------------------+----------+-----------+----------------------------+-------------------------------+

Actually, the IndexLookup plan could also be improved by utilizing the prefix of d(2) to filter out more data on the index side and avoid a large sort. The plan could be:

IndexLookUp
  TopN
    IndexRangeScan(idx(a, d))
  TopN
    TableRowIDScan

For example, if rows are (1, "0001"), (1, "0002"), (1, "0101"), (1, "0102"), (1, "0201"), (1, "0202"), (1, "0301"), ....
We could read "0001" ~ "0202" only on the index side, since there are already 6 rows, and we know any prefix larger than "02" is not going to be the output. This can hugely reduce the number of rows we have to lookup at the table side.

[mzhang77]

I have a paid customer with a simpler testcase:

CREATE TABLE t (
  id INT PRIMARY KEY,
  test VARCHAR(501)
);

CREATE INDEX idx_test_prefix ON t(test(500));

Query:

SELECT * FROM t ORDER BY test LIMIT 1;

In this case, the optimizer does not use the prefix index to stop the index range scan early, even when the distinguishing characters appear within the stored prefix.