offset新探索：雙管齊下，加速大數(shù)據(jù)量查詢

眾所周知，在各類業(yè)務(wù)中時(shí)常會(huì)用到LIMIT y offset x來(lái)做跳過(guò)x條數(shù)據(jù)讀取Y條數(shù)據(jù)的操作。例如：SELECT * FROM ... LIMIT 1000 OFFSET 1000000;表示從第1000001條數(shù)據(jù)開(kāi)始查，讀取1000條數(shù)據(jù)。隨著offset的增加，查詢的時(shí)長(zhǎng)也會(huì)越來(lái)越長(zhǎng)。當(dāng)offset達(dá)到百萬(wàn)級(jí)別的時(shí)候查詢時(shí)長(zhǎng)有可能秒級(jí)，這是業(yè)務(wù)所不能容忍的。

那么如何來(lái)提升offset在大數(shù)據(jù)量查詢時(shí)的性能、縮短執(zhí)行時(shí)間呢？我們的答案是：

offset Pushdown( offset下推，下文簡(jiǎn)稱OP)

Redundant Condition Removal (冗余條件刪除，下文簡(jiǎn)稱 RCR)

這是華為云GaussDB for MySQL推出的兩個(gè)新特性，通過(guò)OP和RCR的結(jié)合，將大數(shù)據(jù)量查詢的性能提升一到兩個(gè)數(shù)量級(jí)。下面我們分別介紹這兩個(gè)特性的基本原理、如何啟用、執(zhí)行驗(yàn)證、以及通過(guò)嚴(yán)密測(cè)試來(lái)驗(yàn)證其帶來(lái)的性能提升。

Offset Pushdown -- OP

OP賦予MySQL存儲(chǔ)引擎InnoDB處理offset的能力。當(dāng)OP啟用時(shí)，在SQL層評(píng)估offset是否可以下推并將下推信息傳遞給存儲(chǔ)引擎。SQL層不再對(duì)存儲(chǔ)引擎返回的行進(jìn)行offset處理，取而代之的是存儲(chǔ)引擎層直接跳過(guò)offset范圍內(nèi)的行，僅返回后續(xù)行，即查詢所需要的行。

通過(guò)啟用OP，offset范圍內(nèi)的行不會(huì)再傳輸?shù)絊QL層，從而節(jié)省了存儲(chǔ)引擎和SQL層之間多次來(lái)回交互時(shí)間；其次，對(duì)非覆蓋索引掃描（non-covering index，即查詢?cè)L問(wèn)二級(jí)索引之后，還必須訪問(wèn)基表），直接跳過(guò)offset范圍內(nèi)的行可以節(jié)省對(duì)這些行回表訪問(wèn)的開(kāi)銷。這種對(duì)offset的提前處理可以節(jié)省數(shù)據(jù)處理時(shí)間，特別是當(dāng)offset非常大時(shí)。OP的適用性取決于WHERE子句是否可以由存儲(chǔ)引擎整體處理。

下方圖1和2分別說(shuō)明了在沒(méi)有OP和啟用OP時(shí)LIMIT offset的處理邏輯。

圖1無(wú)OP的極限偏移邏輯

圖2啟用OP的LIMIT offset邏輯

Redundant Condition Removal – RCR

RCR的思路也比較簡(jiǎn)單：當(dāng)進(jìn)行索引范圍掃描時(shí)，SQL層對(duì)存儲(chǔ)引擎返回的行執(zhí)行冗余檢查，因?yàn)樗恢来鎯?chǔ)引擎已經(jīng)執(zhí)行了這些檢查，而RCR就是讓 SQL層了解這點(diǎn)。為了使 OP成為可能，除了要求WHERE條件能夠被存儲(chǔ)引擎獨(dú)立且完整的評(píng)估，SQL層還必須了解這點(diǎn)從而避免冗余檢查。

OP功能的實(shí)現(xiàn)方式與索引條件下推 (Index Condition Pushdown，ICP) 類似。對(duì)于某些查詢，ICP通過(guò)將整個(gè) WHERE子句下推到存儲(chǔ)引擎來(lái)啟用 OP。而RCR在 ICP執(zhí)行之前會(huì)評(píng)估條件是否冗余，并且移除冗余條件，確保了ICP不會(huì)處理冗余的條件檢查。RCR很好地補(bǔ)充了OP特性的適用范圍，允許更多查詢使用 OP。

請(qǐng)注意：OP的啟用需要滿足三個(gè)主要條件：

SQL語(yǔ)句包含offset

WHERE子句完全由InnoDB處理

SQL語(yǔ)句只涉及一張表

另外，

查詢中使用的表必須是InnoDB表

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

不支持涉及多個(gè)分區(qū)的分區(qū)表查詢，只涉及單個(gè)分區(qū)的可以

RCR適用于索引范圍掃描，如果WHERE子句中出現(xiàn)了一個(gè)或者多個(gè)條件，而這些條件涉及到的字段在對(duì)應(yīng)使用的索引上是被連續(xù)定義的，這些條件的冗余檢查就都會(huì)被移除。

如何啟用OP？

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

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

默認(rèn)為打開(kāi)。

方法二：使用特定的優(yōu)化器hint：[NO]_OFFSET_PUSHDOWN()

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

請(qǐng)注意，hint優(yōu)先級(jí)高于optimizer switch的設(shè)置。

我們基于下方創(chuàng)建的t1表，來(lái)舉例說(shuō)明如何使用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)

示例二：二級(jí)索引上的索引范圍掃描

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?

通過(guò)系統(tǒng)變量rds_empty_redundant_check_in_range_scan設(shè)置，如下：

set rds_empty_redundant_check_in_range_scan=[true]/[false];

默認(rèn)為true。

我們通過(guò)一個(gè)示例來(lái)說(shuō)明：

創(chuàng)建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上的范圍條件會(huì)被InnoDB默認(rèn)檢查，但SQL層將再次檢查InnoDB返回的行是否匹配列a的范圍條件。在這種情況下，無(wú)法使用OP，因?yàn)镾QL層不知道存儲(chǔ)引擎實(shí)際上處理了整個(gè)WHERE子句。

啟用RCR：設(shè)定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)

可以看出：?jiǎn)⒂肦CR，刪除SQL層對(duì)列A的范圍條件的冗余檢查后，啟用OP。

簡(jiǎn)化ICP：

創(chuàng)建表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)

以上示例說(shuō)明：ICP不是必要的。通過(guò)評(píng)估是否應(yīng)使用ICP之前移除冗余條件，就可以避免使用ICP。

性能驗(yàn)證：

下面我們通過(guò)實(shí)際測(cè)試來(lái)驗(yàn)證OP所帶來(lái)的性能提升。在測(cè)試中，我們重點(diǎn)關(guān)注：

覆蓋/非覆蓋索引

考慮一個(gè)非覆蓋索引，不使用OP，InnoDB必須從基表讀取行，然后才能將它們返回到SQL層。使用OP后，就可以跳過(guò)行，而不必從基表讀取。因此，OP在非覆蓋索引上可以提供更好的性能。

熱/冷緩沖池

我們希望通過(guò)熱緩沖池全面提高性能，但我們也希望OP在熱緩沖池上相對(duì)更高效，原因如下：

基于一個(gè)冷緩沖池并且查詢使用覆蓋索引掃描的場(chǎng)景，設(shè)定

）和使用OP的計(jì)算時(shí)間(

)的比值：

比值

預(yù)計(jì)將大于1，因?yàn)槭褂肙P將獲得性能提升?；谝粋€(gè)熱緩沖池并且查詢使用覆蓋索引掃描的場(chǎng)景，設(shè)定

是不使用OP的計(jì)算時(shí)間(

和使用OP的計(jì)算時(shí)間（

的比值：

其中

表示從磁盤讀取索引所需的時(shí)間，可以合理地假設(shè)，在使用OP和不使用OP的情況下，

都是相同的。因?yàn)椴徽撌欠袷褂肙P，都必須從左到右遍歷索引，無(wú)法在使用OP的情況下，利用B-tree結(jié)構(gòu)索引的優(yōu)勢(shì)直接跳轉(zhuǎn)到offset范圍的結(jié)束點(diǎn)。

那么，這兩個(gè)比值的差值可以表述為：

因此，我們預(yù)計(jì)OP在熱緩沖池將更有效。

緩沖池大小

對(duì)于覆蓋索引查詢，可以假定索引數(shù)據(jù)都在緩沖池中，因此，緩沖池的大小對(duì)性能不會(huì)產(chǎn)生太大影響。然而，對(duì)于非覆蓋索引的查詢，情況會(huì)大不相同。在不使用OP時(shí)，緩沖池能緩存表數(shù)據(jù)的比例確實(shí)會(huì)對(duì)查詢的性能產(chǎn)生有利的影響。

基于以上三個(gè)關(guān)注點(diǎn)以及預(yù)判，我們?cè)谝粋€(gè)包含200萬(wàn)行數(shù)據(jù)的測(cè)試表中，分別測(cè)試覆蓋/非覆蓋索引、冷/熱緩沖池、不同緩沖池大小下條件下，通過(guò)OP帶來(lái)的性能表現(xiàn)。

測(cè)試語(yǔ)句：

覆蓋索引查詢：

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;

為了過(guò)濾干擾，計(jì)算時(shí)間是取9次運(yùn)行結(jié)果的中位數(shù)。

通過(guò)以上測(cè)試結(jié)果可以看出：

熱緩沖池，并將其大小設(shè)為128MB

使用覆蓋索引，OP可以將查詢性能提升3 – 12倍；

使用非覆蓋索引，OP可以將查詢性能提升 48 – 128倍

冷緩沖池，并將其大小設(shè)定為128MB：

使用覆蓋索引，OP可以將性能提升 40% - 8倍；

使用非覆蓋索引，OP可以將性能提升2 - 148倍

綜上，在所有測(cè)試中，使用OP能提升查詢性能。不論是冷緩沖池還是熱緩沖池，啟用OP后，非覆蓋索引掃描可以比覆蓋索引掃描獲得10倍以上的性能提升。此外，正如我們所預(yù)計(jì)，在熱緩沖池上啟用OP獲得了更大的性能提升。

對(duì)于大的OFFSET，使用OP可將性能提高一兩個(gè)數(shù)量級(jí)，而RCR可擴(kuò)大了OP的適用范圍。正如上述測(cè)試所證明，使用OP所帶來(lái)的性能提升主要受下面兩個(gè)因素的影響：

OP可以在存儲(chǔ)引擎層跳過(guò)offset行，而不必將它們返回到SQL層，這將導(dǎo)致計(jì)算時(shí)間的顯著降低。

OP可以跳過(guò)offset行，而不必從基表讀取它們，從而獲得性能提升。

而OP和RCR的聯(lián)合使用，進(jìn)一步擴(kuò)大了OP的使用范圍，可以為更多的Limit/offset查詢帶來(lái)性能提升，尤其是對(duì)大的offset操作。

在后續(xù)的研究中，我們將會(huì)評(píng)估OP與NDP（Near Data Processing, 近數(shù)據(jù)處理）的兼容性以及潛在的性能改進(jìn)。

本文作者

呂漫漪

現(xiàn)任華為瑞典研究所數(shù)據(jù)庫(kù)Lab首席科學(xué)家，云數(shù)據(jù)庫(kù)歐洲研發(fā)團(tuán)隊(duì)的負(fù)責(zé)人。在數(shù)據(jù)庫(kù)領(lǐng)域有20多年經(jīng)驗(yàn)，曾經(jīng)參與開(kāi)發(fā)電信行業(yè)分布式高可用數(shù)據(jù)庫(kù)，在國(guó)際知名軟件公司深耕了十年MySQL技術(shù)。2020年加入華為，立志于打造世界頂端的企業(yè)級(jí)云數(shù)據(jù)庫(kù)。

Maxime Conjard

華為云數(shù)據(jù)庫(kù)工程師，就職于華為云數(shù)據(jù)庫(kù)歐洲研發(fā)團(tuán)隊(duì)。Max畢業(yè)于挪威科技大學(xué)（NTNU），獲得統(tǒng)計(jì)學(xué)碩士和博士學(xué)位；在此之前，他在法國(guó)馬賽中央學(xué)院獲得工程碩士學(xué)位。

審核編輯：湯梓紅