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 ），获得统计学硕士和博士学位；在此之前，他在法国马赛中央学院获得工程硕士学位。