对于 ORDER BY xx LIMIT xx 语句的优化策略

在数据库中，ORDER BY xx LIMIT xx 是一种常见的查询语句。用于获取排序后的前 N 条记录（如排行榜、最新数据等）。这种 SQL 有着执行频率高，要求 RT 低的特点，也是 SQL 调优中经常出现的一类 SQL。这类查询的性能优化核心在于减少排序的数据量和利用索引避免全表扫描。在 Oceanbase，针对这种类型的 SQL，我们也进行了一定的优化，但当前这种 SQL 的优化存在一定问题。本文介绍针对这种 SQL，当前可能生成的计划形态，如何识别各类计划以及如何尝试手动优化。

详细说明

表结构如下。

CREATE TABLE test123 (
  c1 int(10),
  c2 varchar(48) NOT NULL,
  c3 bigint(20) NOT NULL,
  c4 varchar(48) DEFAULT NULL,
  c5 varchar(48) DEFAULT NULL,
  PRIMARY KEY (c1),
  KEY idx_filter (c2,c3),
  KEY idx_order(c4)
);

涉及的 SQL 语句如下。

SELECT * FROM test123 WHERE c2 > '0' AND c3 = 1 ORDER BY c4 DESC LIMIT 100;

计划形态

TOP-N SORT

TOP-N 排序表示上层只要求取最大/最小的前 N 个结果。当 SORT 的上层为 LIMIT 时，优化器认为该 SORT 不需要所有结果，标记该 SORT 为 TOP-N SORT。 该种计划要求在 WHERE 的过滤条件列创建索引，查询使用索引缩小查询结果集。并在查询后的结果集中，按照 ORDER BY 列进行排序，之后取出 TOP-N 条数据。 该种方法在过滤之后仍然存在大量数据的场景下，执行效率不优。但是计划相对稳定。 下面的计划中使用了在基表扫描中使用 idx_filter(c2,c3) 索引，对满足条件的数据进行过滤。过滤后 2 号算子按照 ORDER BY 列(c4), 主键列(c1) 进行排序， 然后取出 TOP-N(100) 行数据。

流式计划（消序计划，pipeline 计划）

流式计划是指计划中不存在阻塞算子，使得下层的数据输出能传到上层算子持续处理，使得数据流动起来。常见的阻塞算子有 SORT、HASH GROUP BY、HASH JOIN、HASH DISTINCT 等。 在一些场景下，通过选择包含 ORDER BY 列的索引使得排序有序（正序逆序都可以），可以将 LIMIT 的数量下压到基表扫描中，从而减少扫描的数据量，提升查询效率。 在下面的计划中，使用索引 idx_order(c4) 即排序列，将 limit(100) 下压到 test123 表的基表扫描中，整体只需要扫描满足条件的 100 条数据即可。

此外，计划中存在 prefix_pos(n) ，也是当作流式计划在处理的。

前缀排序 prefix_pos(n)

索引表虽然不能完全消除排序，但可以做到一个 prefix top-n sort， 从而走上流式计划。 例如 sort keys(c1,c2,c3)，prefix_pos(2)，表示 c1，c2 已经有序。 在下面的计划中，表的索引 idx_234(c2,c3,c4)， sort 算子的排序键为 c2，c5，那么公共前缀是 c2。优化器会认为可以利用 c2 的序，所以选择前缀排序。其中 prefix_pos(1) 表示前 1 个列已经有序，不再需要比较，从而 2 号算子可以直接消费 3 号算子输出的数据。

当前流式计划存在一些问题：

1. 流式计划不稳定，在一些场景下（尤其是需要访问的数据靠后的情况下），需要访问的数据量增多，反而导致执行变慢。

2. 流式计划代价估算不准，实际执行代价高于非流式计划（目前 LIMIT 重计算使用的选择率和重计算行数获取的行数等方面存在一些问题，可能导致错误选择 pipeline 计划）。

目前大部分此类型 SQL 的工单，都是优化器默认选择流式计划，实际执行效果可能不优的问题。针对这种场景，优化器团队做一些优化。例如： 如果走了一个消序的索引（通常是主表），并且没有抽 query range，这种流式计划就不会选择，会直接选择一个可以抽取更好 query range 的走索引的计划。 同时也在 OceanBase 数据库 V4.3.5 BP1/V4.2.5 BP3 提供 SQL 级别的参数控制关闭流式计划。新增系统变量 ENABLE_OPTIMIZER_ROWGOAL 对应 Hint /*+ OPT_PARAM('ENABLE_OPTIMIZER_ROWGOAL','OFF') */。 系统变量 ENABLE_OPTIMIZER_ROWGOAL 控制优化器这一行为，如下。

1. ON：总是启用行数目标进行估计。

2. OFF：总是禁用行数目标进行估计。

3. AUTO：优化器自行决策是否使用行数目标（默认行为）。

晚期物化

晚期物化是针对 TOP-N SORT 回表数据量大的情况，减少回表数据量的优化。 该种先做索引扫描，然后取 TOP N 的数据，最后再回表 N 行数据。晚期物化策略是单表查询满足有索引能完成过滤条件、排序和 LIMIT，再回查主表时，就不再索引回表后排序、LIMIT，从而极大降低回表随机 IO 损耗。 要求：过滤条件+ 排序条件涉及的所有列建立索引，否则还是无法避免回表操作。 在 OceanBase 数据库 V4.2.5 之前版本，已支持了查询非分区表触发晚期物化策略；从 V4.2.5 及之后版本，提供查询分区表触发晚期物化策略的能力。 在下面的例子中，存在索引 idx_234(c2,c3,c4), 覆盖了过滤条件 + 排序列，通过 WHERE 条件过滤之后，取 TOP-N 行，然后只需要回表这 TOP-N 行数据即可。

如何手动优化

当前优化器会基于规则和代价去决定选择某种计划形态。但是因为存在各种各样的问题，导致有可能选上不优计划，遇到此种类型的问题，可以尝试根据条件，手动绑定 Hint 来走上不同的计划形态，查看哪种更优。

TOP-N SORT      /*+INDEX(test123 idx_filter */                         包含 WHERE 过滤条件的索引
流式计划        /*+INDEX(test123 idx_order) */                          包含排序列的索引
晚期物化       /*+INDEX(test123 idx_234) USE_LATE_MATERIALIZATION */    覆盖过滤条件 + 排序列的索引

此外，在极致优化的场景，如果 SELECT 中的投影列不多，可以创建全覆盖索引（投影列 + 过滤条件列 + 排序列），降低瓶颈点为回表（OceanBase 回表代价高）性能不优的场景。

对于两表或者多表关联的场景，如果流式计划不优，可以尝试查看去掉 LIMIT xx 之后的计划，从而确定关联表使用的索引。绑定表使用的对应索引，就可以找到对应的非流式计划。

适用版本

OceanBase 数据库 V4.x 版本。