TopN 和 Limit 下推

SQL 中的 LIMIT 子句在 TiDB 查询计划树中对应 Limit 算子节点,ORDER BY 子句在查询计划树中对应 Sort 算子节点,此外,我们会将相邻的 Limit 和 Sort 算子组合成 TopN 算子节点,表示按某个排序规则提取记录的前 N 项。从另一方面来说,Limit 节点等价于一个排序规则为空的 TopN 节点。

和谓词下推类似,TopN(及 Limit,下同)下推将查询计划树中的 TopN 计算尽可能下推到距离数据源最近的地方,以尽早完成数据的过滤,进而显著地减少数据传输或计算的开销。

如果要关闭这个规则,可参照优化规则及表达式下推的黑名单中的关闭方法。

示例

以下通过一些例子对 TopN 下推进行说明。

示例 1:下推到存储层 Coprocessor

  1. create table t(id int primary key, a int not null);
  2. explain select * from t order by a limit 10;
  1. +----------------------------+----------+-----------+---------------+--------------------------------+
  2. | id | estRows | task | access object | operator info |
  3. +----------------------------+----------+-----------+---------------+--------------------------------+
  4. | TopN_7 | 10.00 | root | | test.t.a, offset:0, count:10 |
  5. | └─TableReader_15 | 10.00 | root | | data:TopN_14 |
  6. | └─TopN_14 | 10.00 | cop[tikv] | | test.t.a, offset:0, count:10 |
  7. | └─TableFullScan_13 | 10000.00 | cop[tikv] | table:t | keep order:false, stats:pseudo |
  8. +----------------------------+----------+-----------+---------------+--------------------------------+
  9. 4 rows in set (0.00 sec)

在该查询中,将 TopN 算子节点下推到 TiKV 上对数据进行过滤,每个 Coprocessor 只向 TiDB 传输 10 条记录。在 TiDB 将数据整合后,再进行最终的过滤。

示例 2:TopN 下推过 Join 的情况(排序规则仅依赖于外表中的列)

  1. create table t(id int primary key, a int not null);
  2. create table s(id int primary key, a int not null);
  3. explain select * from t left join s on t.a = s.a order by t.a limit 10;
  1. +----------------------------------+----------+-----------+---------------+-------------------------------------------------+
  2. | id | estRows | task | access object | operator info |
  3. +----------------------------------+----------+-----------+---------------+-------------------------------------------------+
  4. | TopN_12 | 10.00 | root | | test.t.a, offset:0, count:10 |
  5. | └─HashJoin_17 | 12.50 | root | | left outer join, equal:[eq(test.t.a, test.s.a)] |
  6. | ├─TopN_18(Build) | 10.00 | root | | test.t.a, offset:0, count:10 |
  7. | └─TableReader_26 | 10.00 | root | | data:TopN_25 |
  8. | └─TopN_25 | 10.00 | cop[tikv] | | test.t.a, offset:0, count:10 |
  9. | └─TableFullScan_24 | 10000.00 | cop[tikv] | table:t | keep order:false, stats:pseudo |
  10. | └─TableReader_30(Probe) | 10000.00 | root | | data:TableFullScan_29 |
  11. | └─TableFullScan_29 | 10000.00 | cop[tikv] | table:s | keep order:false, stats:pseudo |
  12. +----------------------------------+----------+-----------+---------------+-------------------------------------------------+
  13. 8 rows in set (0.01 sec)

在该查询中,TopN 算子的排序规则仅依赖于外表 t 中的列,可以将 TopN 下推到 Join 之前进行一次计算,以减少 Join 时的计算开销。除此之外,TiDB 同样将 TopN 下推到了存储层中。

示例 3:TopN 不能下推过 Join 的情况

  1. create table t(id int primary key, a int not null);
  2. create table s(id int primary key, a int not null);
  3. explain select * from t join s on t.a = s.a order by t.id limit 10;
  1. +-------------------------------+----------+-----------+---------------+--------------------------------------------+
  2. | id | estRows | task | access object | operator info |
  3. +-------------------------------+----------+-----------+---------------+--------------------------------------------+
  4. | TopN_12 | 10.00 | root | | test.t.id, offset:0, count:10 |
  5. | └─HashJoin_16 | 12500.00 | root | | inner join, equal:[eq(test.t.a, test.s.a)] |
  6. | ├─TableReader_21(Build) | 10000.00 | root | | data:TableFullScan_20 |
  7. | └─TableFullScan_20 | 10000.00 | cop[tikv] | table:s | keep order:false, stats:pseudo |
  8. | └─TableReader_19(Probe) | 10000.00 | root | | data:TableFullScan_18 |
  9. | └─TableFullScan_18 | 10000.00 | cop[tikv] | table:t | keep order:false, stats:pseudo |
  10. +-------------------------------+----------+-----------+---------------+--------------------------------------------+
  11. 6 rows in set (0.00 sec)

TopN 无法下推过 Inner Join。以上面的查询为例,如果先 Join 得到 100 条记录,再做 TopN 可以剩余 10 条记录。而如果在 TopN 之前就过滤到剩余 10 条记录,做完 Join 之后可能就剩下 5 条了,导致了结果的差异。

同理,TopN 无法下推到 Outer Join 的内表上。在 TopN 的排序规则涉及多张表上的列时,也无法下推,如 t.a+s.a。只有当 TopN 的排序规则仅依赖于外表上的列时,才可以下推。

示例 4:TopN 转换成 Limit 的情况

  1. create table t(id int primary key, a int not null);
  2. create table s(id int primary key, a int not null);
  3. explain select * from t left join s on t.a = s.a order by t.id limit 10;
  1. +----------------------------------+----------+-----------+---------------+-------------------------------------------------+
  2. | id | estRows | task | access object | operator info |
  3. +----------------------------------+----------+-----------+---------------+-------------------------------------------------+
  4. | TopN_12 | 10.00 | root | | test.t.id, offset:0, count:10 |
  5. | └─HashJoin_17 | 12.50 | root | | left outer join, equal:[eq(test.t.a, test.s.a)] |
  6. | ├─Limit_21(Build) | 10.00 | root | | offset:0, count:10 |
  7. | └─TableReader_31 | 10.00 | root | | data:Limit_30 |
  8. | └─Limit_30 | 10.00 | cop[tikv] | | offset:0, count:10 |
  9. | └─TableFullScan_29 | 10.00 | cop[tikv] | table:t | keep order:true, stats:pseudo |
  10. | └─TableReader_35(Probe) | 10000.00 | root | | data:TableFullScan_34 |
  11. | └─TableFullScan_34 | 10000.00 | cop[tikv] | table:s | keep order:false, stats:pseudo |
  12. +----------------------------------+----------+-----------+---------------+-------------------------------------------------+
  13. 8 rows in set (0.00 sec)

在上面的查询中,TopN 首先推到了外表 t 上。然后因为它要对 t.id 进行排序,而 t.id 是表 t 的主键,可以直接按顺序读出 (keep order:true),从而省略了 TopN 中的排序,将其简化为 Limit。