offset 新探索：双管齐下，加速大数据量查询

offset 新探索：双管齐下，加速大数据量查询

众所周知，在各类业务中时常会用到 LIMIT y offset x 来做跳过 x 条数据读取 Y 条数据的操作。例如：SELECT * FROM ... LIMIT 1000 OFFSET 1000000; 表示从第 1000001 条数据开始查，读取 1000 条数据。随着 offset 的增加，查询的时长也会越来越长。当 offset 达到百万级别的时候查询时长有可能秒级，这是业务所不能容忍的。

那么如何来提升 offset 在大数据量查询时的性能、缩短执行时间呢？我们的答案是：

l  offset Pushdown( offset 下推，下文简称 OP)

l  Redundant Condition Removal (冗余条件删除，下文简称 RCR)

这是华为云 GaussDB for MySQL 推出的两个新特性，通过 OP 和 RCR 的结合，将大数据量查询的性能提升一到两个数量级。下面我们分别介绍这两个特性的基本原理、如何启用、执行验证、以及通过严密测试来验证其带来的性能提升。

Offset Pushdown -- OP

OP 赋予 MySQL 存储引擎 InnoDB 处理 offset 的能力。当 OP 启用时，在 SQL 层评估 offset 是否可以下推并将下推信息传递给存储引擎。SQL 层不再对存储引擎返回的行进行 offset 处理，取而代之的是存储引擎层直接跳过 offset 范围内的行，仅返回后续行，即查询所需要的行。

通过启用 OP，offset 范围内的行不会再传输到 SQL 层，从而节省了存储引擎和 SQL 层之间多次来回交互时间；其次，对非覆盖索引扫描（non-covering index，即查询访问二级索引之后，还必须访问基表），直接跳过 offset 范围内的行可以节省对这些行回表访问的开销。这种对 offset 的提前处理可以节省数据处理时间，特别是当 offset 非常大时。OP 的适用性取决于 WHERE 子句是否可以由存储引擎整体处理。

下方图 1 和 2 分别说明了在没有 OP 和启用 OP 时 LIMIT offset 的处理逻辑。

图 1 无 OP 的极限偏移逻辑

图 2 启用 OP 的 LIMIT offset 逻辑

Redundant Condition Removal – RCR

RCR 的思路也比较简单：当进行索引范围扫描时，SQL 层对存储引擎返回的行执行冗余检查，因为它不知道存储引擎已经执行了这些检查，而 RCR 就是让 SQL 层了解这点。为了使 OP 成为可能，除了要求 WHERE 条件能够被存储引擎独立且完整的评估，SQL 层还必须了解这点从而避免冗余检查。

OP 功能的实现方式与索引条件下推 (Index Condition Pushdown，ICP) 类似。对于某些查询，ICP 通过将整个 WHERE 子句下推到存储引擎来启用 OP。而 RCR 在 ICP 执行之前会评估条件是否冗余，并且移除冗余条件，确保了 ICP 不会处理冗余的条件检查。RCR 很好地补充了 OP 特性的适用范围，允许更多查询使用 OP。

请注意：OP 的启用需要满足三个主要条件：

1.         SQL 语句包含 offset

2.         WHERE 子句完全由 InnoDB 处理

3.         SQL 语句只涉及一张表

另外，

l  查询中使用的表必须是 InnoDB 表

l  不使用 HAVING, aggregations, GROUP BY, SELECT DISTINCT, ROLLUP, Window functions 以及文件排序

l  不支持涉及多个分区的分区表查询，只涉及单个分区的可以

RCR 适用于索引范围扫描，如果 WHERE 子句中出现了一个或者多个条件，而这些条件涉及到的字段在对应使用的索引上是被连续定义的，这些条件的冗余检查就都会被移除。

如何启用 OP？

方法一：使用特定的 optimizer switch: offset _PUSHDOWN

set optimizer_switch='OFFSET_PUSHDOWN=[on]/[off]';

默认为打开。

方法二：使用特定的优化器 hint：[NO]_OFFSET_PUSHDOWN()

SELECT /*+ [NO]_OFFSET_PUSHDOWN() */ FROM TABLE LIMIT n  OFFSET p;

请注意，hint 优先级高于 optimizer switch 的设置。

我们基于下方创建的 t1 表，来举例说明如何使用 OP：

CREATE TABLE t1 (a int, b int, INDEX  (b));

示例一：表扫描

explain format=tree select * from t1 limit 100 offset 1;

+----------------------------------------------------------------------------------------------------------------------+

| EXPLAIN                                                                                                              |

+----------------------------------------------------------------------------------------------------------------------+

| -> Limit/Offset: 100/1 row(s), with offset pushdown  (cost=0.65 rows=4)

    -> Table scan on t1  (cost=0.65 rows=4)

 |

+----------------------------------------------------------------------------------------------------------------------+

1 row in set (0.00 sec)

示例二：二级索引上的索引范围扫描

explain  format=tree select a,b from t1 where b>2 limit 100 offset 1;

+------------------------------------------------------------------------------------------------------------------------------------+

| EXPLAIN                                                                                                                            |

+------------------------------------------------------------------------------------------------------------------------------------+

| -> Limit/Offset: 100/1 row(s), with offset pushdown  (cost=1.61 rows=3)

    -> Index range scan on t1 using b  (cost=1.61 rows=3)

 |

+------------------------------------------------------------------------------------------------------------------------------------+

1 row in set (0.00 sec)

如何启用 RCR ?

通过系统变量 rds_empty_redundant_check_in_range_scan 设置，如下：

set rds_empty_redundant_check_in_range_scan=[true]/[false];

默认为 true。

我们通过一个示例来说明：

创建 t0 表：

CREATE TABLE t0 (a int, b int, INDEX  (a,b));

不启用 RCR：

explain format=tree select * from t0 where a<100 and a>20  LIMIT 1 OFFSET 100;

+------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+

| EXPLAIN                                                                                                                                                                            |

+------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+

| -> Limit/Offset: 1/100 row(s)  (cost=0.46 rows=1)

    -> Filter: ((t0.a < 100) and (t0.a > 20))  (cost=0.46 rows=1)

        -> Index range scan on t0 using a  (cost=0.46 rows=1)

 |

+---------------------------

可以看出：列 a 上的范围条件会被 InnoDB 默认检查，但 SQL 层将再次检查 InnoDB 返回的行是否匹配列 a 的范围条件。在这种情况下，无法使用 OP，因为 SQL 层不知道存储引擎实际上处理了整个 WHERE 子句。

启用 RCR：设定 rds_empty_redundant_check_in_range_scan = true;

explain format=tree select * from t0 where a<100 and a>20  LIMIT 1 OFFSET 100;

+------------------------------------------------------------------------------------------------------------------------------------+

| EXPLAIN                                                                                                                            |

+------------------------------------------------------------------------------------------------------------------------------------+

| -> Limit/Offset: 1/100 row(s), with offset pushdown  (cost=0.46 rows=1)

    -> Index range scan on t0 using a  (cost=0.46 rows=1)

 |

+------------------------------------------------------------------------------------------------------------------------------------+

1 row in set (0.00 sec)

可以看出：启用 RCR，删除 SQL 层对列 A 的范围条件的冗余检查后，启用 OP。

简化 ICP：

创建表 t1：

create table t1(a int, b int, INDEX(b));

不启用 RCR：

explain format=tree select a,b from t1 where b>2 limit 100 offset 1;

+----------------------------------------------------------------------------------------------------------------------------------------------------------------------+

| EXPLAIN                                                                                                                                                              |

+----------------------------------------------------------------------------------------------------------------------------------------------------------------------+

| -> Limit/Offset: 100/1 row(s), with offset pushdown  (cost=1.61 rows=3)

    -> Index range scan on t1 using b, with index condition: (t1.b > 2)  (cost=1.61 rows=3)

 |

+----------------------------------------------------------------------------------------------------------------------------------------------------------------------+

1 row in set (0.00 sec)

可以看出：使用了 ICP 后，OP 也被启用了

启用 RCR：

explain format=tree select a,b from t1 where b>2 limit 100 offset 1;

+------------------------------------------------------------------------------------------------------------------------------------+

| EXPLAIN                                                                                                                            |

+------------------------------------------------------------------------------------------------------------------------------------+

| -> Limit/Offset: 100/1 row(s), with offset pushdown  (cost=1.61 rows=3)

    -> Index range scan on t1 using b  (cost=1.61 rows=3)

 |

+------------------------------------------------------------------------------------------------------------------------------------+

1 row in set (0.00 sec)

以上示例说明：ICP 不是必要的。通过评估是否应使用 ICP 之前移除冗余条件，就可以避免使用 ICP。

性能验证：

下面我们通过实际测试来验证 OP 所带来的性能提升。在测试中，我们重点关注：

l  覆盖/非覆盖索引

考虑一个非覆盖索引，不使用 OP，InnoDB 必须从基表读取行，然后才能将它们返回到 SQL 层。使用 OP 后，就可以跳过行，而不必从基表读取。因此，OP 在非覆盖索引上可以提供更好的性能。

l  热/冷缓冲池

我们希望通过热缓冲池全面提高性能，但我们也希望 OP 在热缓冲池上相对更高效，原因如下：

基于一个冷缓冲池并且查询使用覆盖索引扫描的场景，设定

为不使用 OP 的计算时间（

）和使用 OP 的计算时间(

)的比值：

比值

预计将大于 1，因为使用 OP 将获得性能提升。基于一个热缓冲池并且查询使用覆盖索引扫描的场景，设定

是不使用 OP 的计算时间(

和使用 OP 的计算时间（

的比值：

其中

表示从磁盘读取索引所需的时间，可以合理地假设，在使用 OP 和不使用 OP 的情况下，

都是相同的。因为不论是否使用 OP，都必须从左到右遍历索引，无法在使用 OP 的情况下，利用 B-tree 结构索引的优势直接跳转到 offset 范围的结束点。

那么，这两个比值的差值可以表述为：

因此，我们预计 OP 在热缓冲池将更有效。

l  缓冲池大小

对于覆盖索引查询，可以假定索引数据都在缓冲池中，因此，缓冲池的大小对性能不会产生太大影响。然而，对于非覆盖索引的查询，情况会大不相同。在不使用 OP 时，缓冲池能缓存表数据的比例确实会对查询的性能产生有利的影响。

基于以上三个关注点以及预判，我们在一个包含 200 万行数据的测试表中，分别测试覆盖/非覆盖索引、冷/热缓冲池、不同缓冲池大小下条件下，通过 OP 带来的性能表现。

测试语句：

覆盖索引查询：

CREATE TABLE data (id int, value int, INDEX  (id,value));

SELECT * FROM data   LIMIT 1 OFFSET p;

非覆盖索引查询：

CREATE TABLE data_non_covering(id INT, value INT, INDEX  (value));

INSERT INTO data_non_covering SELECT * FROM data;

SELECT * FROM data_non_covering WHERE value>2 LIMIT 1 OFFSET p;

为了过滤干扰，计算时间是取 9 次运行结果的中位数。

通过以上测试结果可以看出：

热缓冲池，并将其大小设为 128MB

l  使用覆盖索引，OP 可以将查询性能提升 3 – 12 倍；

l  使用非覆盖索引，OP 可以将查询性能提升 48 – 128 倍

冷缓冲池，并将其大小设定为 128MB：

l  使用覆盖索引，OP 可以将性能提升 40% - 8 倍；

l  使用非覆盖索引，OP 可以将性能提升 2 - 148 倍

综上，在所有测试中，使用 OP 能提升查询性能。不论是冷缓冲池还是热缓冲池，启用 OP 后，非覆盖索引扫描可以比覆盖索引扫描获得 10 倍以上的性能提升。此外，正如我们所预计，在热缓冲池上启用 OP 获得了更大的性能提升。

对于大的 OFFSET，使用 OP 可将性能提高一两个数量级，而 RCR 可扩大了 OP 的适用范围。正如上述测试所证明，使用 OP 所带来的性能提升主要受下面两个因素的影响：

l  OP 可以在存储引擎层跳过 offset 行，而不必将它们返回到 SQL 层，这将导致计算时间的显著降低。

l  OP 可以跳过 offset 行，而不必从基表读取它们，从而获得性能提升。

而 OP 和 RCR 的联合使用，进一步扩大了 OP 的使用范围，可以为更多的 Limit/offset 查询带来性能提升，尤其是对大的 offset 操作。

在后续的研究中，我们将会评估 OP 与 NDP（Near Data Processing, 近数据处理）的兼容性以及潜在的性能改进。

本文作者

吕漫漪

现任华为瑞典研究所数据库 Lab 首席科学家，云数据库欧洲研发团队的负责人。在数据库领域有 20 多年经验，曾经参与开发电信行业分布式高可用数据库，在国际知名软件公司深耕了十年 MySQL 技术。2020 年加入华为，立志于打造世界顶端的企业级云数据库。

Maxime Conjard

华为云数据库工程师，就职于华为云数据库欧洲研发团队。Max 毕业于挪威科技大学（NTNU），获得统计学硕士和博士学位；在此之前，他在法国马赛中央学院获得工程硕士学位。