offset新探索：雙管齊下，加速大數(shù)據(jù)量查詢
offset新探索：雙管齊下，加速大數(shù)據(jù)量查詢
?
眾所周知，在各類業(yè)務中時常會用到LIMIT y offset x來做跳過x條數(shù)據(jù)讀取Y條數(shù)據(jù)的操作。例如：SELECT * FROM ... LIMIT 1000 OFFSET 1000000; 表示從第1000001條數(shù)據(jù)開始查，讀取1000條數(shù)據(jù)。隨著offset的增加，查詢的時長也會越來越長。當offset達到百萬級別的時候查詢時長有可能秒級，這是業(yè)務所不能容忍的。
?
那么如何來提升offset在大數(shù)據(jù)量查詢時的性能、縮短執(zhí)行時間呢？我們的答案是：
l? offset Pushdown( offset下推，下文簡稱OP)
l? Redundant Condition Removal (冗余條件刪除，下文簡稱 RCR)
這是華為云GaussDB for MySQL推出的兩個新特性，通過OP和RCR的結合，將大數(shù)據(jù)量查詢的性能提升一到兩個數(shù)量級。下面我們分別介紹這兩個特性的基本原理、如何啟用、執(zhí)行驗證、以及通過嚴密測試來驗證其帶來的性能提升。
?
Offset Pushdown -- OP
OP賦予MySQL存儲引擎InnoDB處理offset 的能力。當OP啟用時，在SQL層評估offset 是否可以下推并將下推信息傳遞給存儲引擎。SQL層不再對存儲引擎返回的行進行offset 處理，取而代之的是存儲引擎層直接跳過offset 范圍內(nèi)的行，僅返回后續(xù)行，即查詢所需要的行。
?
通過啟用OP，offset 范圍內(nèi)的行不會再傳輸?shù)絊QL層，從而節(jié)省了存儲引擎和SQL層之間多次來回交互時間；其次，對非覆蓋索引掃描（non-covering index，即查詢訪問二級索引之后，還必須訪問基表），直接跳過offset 范圍內(nèi)的行可以節(jié)省對這些行回表訪問的開銷。這種對offset 的提前處理可以節(jié)省數(shù)據(jù)處理時間，特別是當offset 非常大時。OP的適用性取決于WHERE子句是否可以由存儲引擎整體處理。
下方圖1和2分別說明了在沒有OP和啟用OP時LIMIT offset的處理邏輯。
?
圖1無OP的極限偏移邏輯
?
圖2啟用OP的LIMIT offset 邏輯
?
?
Redundant Condition Removal – RCR
RCR的思路也比較簡單：當進行索引范圍掃描時，SQL 層對存儲引擎返回的行執(zhí)行冗余檢查，因為它不知道存儲引擎已經(jīng)執(zhí)行了這些檢查，而RCR 就是讓 SQL 層了解這點。為了使 OP 成為可能，除了要求WHERE條件能夠被存儲引擎獨立且完整的評估，SQL 層還必須了解這點從而避免冗余檢查。
OP功能的實現(xiàn)方式與索引條件下推 (Index Condition Pushdown，ICP) 類似。對于某些查詢，ICP 通過將整個 WHERE 子句下推到存儲引擎來啟用 OP。而RCR在 ICP 執(zhí)行之前會評估條件是否冗余，并且移除冗余條件，確保了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? 不支持涉及多個分區(qū)的分區(qū)表查詢，只涉及單個分區(qū)的可以
?
RCR適用于索引范圍掃描，如果WHERE子句中出現(xiàn)了一個或者多個條件，而這些條件涉及到的字段在對應使用的索引上是被連續(xù)定義的，這些條件的冗余檢查就都會被移除。
?
如何啟用OP？
方法一：使用特定的optimizer switch: offset _PUSHDOWN
set optimizer_switch='OFFSET_PUSHDOWN=[on]/[off]';
默認為打開。
?
方法二：使用特定的優(yōu)化器hint：[NO]_OFFSET_PUSHDOWN()
SELECT /*+ [NO]_OFFSET_PUSHDOWN() */ FROM TABLE LIMIT n? OFFSET p;
?
請注意，hint優(yōu)先級高于optimizer switch的設置。
我們基于下方創(chuàng)建的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??
通過系統(tǒng)變量rds_empty_redundant_check_in_range_scan設置，如下：
set rds_empty_redundant_check_in_range_scan=[true]/[false];
默認為true。
?
我們通過一個示例來說明：
創(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上的范圍條件會被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：
創(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)
?
以上示例說明：ICP不是必要的。通過評估是否應使用ICP之前移除冗余條件，就可以避免使用ICP。
?
?
性能驗證：
下面我們通過實際測試來驗證OP所帶來的性能提升。在測試中，我們重點關注：
l? 覆蓋/非覆蓋索引
考慮一個非覆蓋索引，不使用OP，InnoDB必須從基表讀取行，然后才能將它們返回到SQL層。使用OP后，就可以跳過行，而不必從基表讀取。因此，OP在非覆蓋索引上可以提供更好的性能。
l? 熱/冷緩沖池
我們希望通過熱緩沖池全面提高性能，但我們也希望OP在熱緩沖池上相對更高效，原因如下：
基于一個冷緩沖池并且查詢使用覆蓋索引掃描的場景，設定為不使用OP的計算時間（）和使用OP的計算時間()的比值：
?
?
比值預計將大于1，因為使用OP將獲得性能提升。基于一個熱緩沖池并且查詢使用覆蓋索引掃描的場景，設定是不使用OP的計算時間(和使用OP的計算時間（的比值：
其中表示從磁盤讀取索引所需的時間，可以合理地假設，在使用OP和不使用OP的情況下，都是相同的。因為不論是否使用OP，都必須從左到右遍歷索引，無法在使用OP的情況下，利用B-tree結構索引的優(yōu)勢直接跳轉(zhuǎn)到offset 范圍的結束點。
那么，這兩個比值的差值可以表述為：
因此，我們預計OP在熱緩沖池將更有效。
l? 緩沖池大小
對于覆蓋索引查詢，可以假定索引數(shù)據(jù)都在緩沖池中，因此，緩沖池的大小對性能不會產(chǎn)生太大影響。然而，對于非覆蓋索引的查詢，情況會大不相同。在不使用OP時，緩沖池能緩存表數(shù)據(jù)的比例確實會對查詢的性能產(chǎn)生有利的影響。
?
基于以上三個關注點以及預判，我們在一個包含200萬行數(shù)據(jù)的測試表中，分別測試覆蓋/非覆蓋索引、冷/熱緩沖池、不同緩沖池大小下條件下，通過OP帶來的性能表現(xiàn)。
測試語句：
覆蓋索引查詢：
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次運行結果的中位數(shù)。
?
??????????????????????????????????????
通過以上測試結果可以看出：
熱緩沖池，并將其大小設為128MB
l? 使用覆蓋索引，OP可以將查詢性能提升3 – 12倍；
l? 使用非覆蓋索引，OP可以將查詢性能提升 48 – 128倍
?
冷緩沖池，并將其大小設定為128MB：
l? 使用覆蓋索引，OP可以將性能提升 40% - 8倍；
l? 使用非覆蓋索引，OP可以將性能提升2 - 148 倍
?
綜上，在所有測試中，使用OP能提升查詢性能。不論是冷緩沖池還是熱緩沖池，啟用OP后，非覆蓋索引掃描可以比覆蓋索引掃描獲得10倍以上的性能提升。此外，正如我們所預計，在熱緩沖池上啟用OP獲得了更大的性能提升。
對于大的OFFSET，使用OP可將性能提高一兩個數(shù)量級，而RCR可擴大了OP的適用范圍。正如上述測試所證明，使用OP所帶來的性能提升主要受下面兩個因素的影響：
l? OP可以在存儲引擎層跳過offset 行，而不必將它們返回到SQL層，這將導致計算時間的顯著降低。
l? OP可以跳過offset 行，而不必從基表讀取它們，從而獲得性能提升。
?
而OP和RCR的聯(lián)合使用，進一步擴大了OP的使用范圍，可以為更多的Limit/offset查詢帶來性能提升，尤其是對大的offset操作。
?
在后續(xù)的研究中，我們將會評估OP與NDP（Near Data Processing, 近數(shù)據(jù)處理）的兼容性以及潛在的性能改進。
?
?
本文作者
?
呂漫漪
現(xiàn)任華為瑞典研究所數(shù)據(jù)庫Lab首席科學家，云數(shù)據(jù)庫歐洲研發(fā)團隊的負責人。在數(shù)據(jù)庫領域有20多年經(jīng)驗，曾經(jīng)參與開發(fā)電信行業(yè)分布式高可用數(shù)據(jù)庫，在國際知名軟件公司深耕了十年MySQL技術。2020年加入華為，立志于打造世界頂端的企業(yè)級云數(shù)據(jù)庫。
?
Maxime Conjard
華為云數(shù)據(jù)庫工程師，就職于華為云數(shù)據(jù)庫歐洲研發(fā)團隊。Max畢業(yè)于挪威科技大學（NTNU），獲得統(tǒng)計學碩士和博士學位；在此之前，他在法國馬賽中央學院獲得工程碩士學位。
?
?
