列存索引中TopK運算元的實現一文中介紹了PolarDB IMCI如何利用統計資訊在運行時進行剪枝，以提高TopK演算法的查詢效能。本文將進一步全面介紹PolarDB IMCI的查詢剪枝（pruning or data skipping）技術。
背景與作用
在HTAP情境中，PolarDB IMCI（In Memory Column Index）選擇列式Heap Table作為底層主要儲存架構來支援即時更新，SQL Server以及Oracle的Column Index也採用了相同的儲存架構。然而，Heap Table架構雖然更新速度快，但在小範圍的掃描上表現並不理想，很多時候需要進行全表掃描。為了盡量減少全表掃描的問題，SQL Server主要通過Min-Max、分區以及聚簇索引來降低掃描資料量；Oracle是全記憶體的列索引，其主要通過Min-Max以及metadata dictionary來減少全表掃描。PolarDB IMCI屬於列存表的模式，資料支援落盤，實現了更加多樣化的方法來最佳化全表資料掃描。
技術選型 | 特點 | 樣本 |
列式HeapTable |
|
|
列式LSM |
|
|
PolarDB IMCI按RowGroup組織資料，每個RowGroup包含64K行。對於每一列的列索引，其儲存都採用的是無序且追加寫的格式。因此，IMCI無法像InnoDB的普通有序索引那樣，可以精確地過濾掉不符合要求的資料。在讀取DataPack時，需要從磁碟中載入進記憶體並解壓縮，然後遍曆DataPack中的所有記錄，利用過濾條件式篩選出合格記錄。對於大表而言，這些掃描任務的代價很大，並會對LRU cache造成一定程度的汙染，導致整體查詢延遲升高，QPS大幅降低。
為瞭解決大表掃描代價過高的問題，PolarDB IMCI引入了查詢剪枝技術。該技術可以在過濾資料時，提前過濾掉不需要訪問的DataPack，從而減少資料訪問量，提高查詢效率。具體實現方式是通過訪問分區資訊和統計資訊，結合特定的過濾條件，在查詢之前就把不合格資料剪去。這樣就可以減少對儲存的掃描次數，進而減少資料轉送和計算消耗。該技術不僅適用於單表資料的查詢，也適用於多表串連查詢，並能大幅度提升PolarDB IMCI的查詢效能。
基本原理與方法
分區資訊剪枝
IMCI的分區剪枝技術是指在查詢時根據分區鍵的條件來過濾不需要查詢的分區，從而減少查詢的資料量和提高查詢效率的技術。IMCI支援的分區類型包括RANGE、LIST、HASH三種。其中，RANGE和LIST分區會把資料表分成若干個區間或列表，HASH分區會將資料散列到不同的分區。在使用分區剪枝技術時，需要使用符合分區條件的查詢語句，並將分區鍵作為查詢條件進行查詢。
例如，假設有一個訂單表orders，根據訂單日期分為12個分區，通過以下查詢語句可查詢某一天的訂單：
SELECT * FROM orders WHERE order_date = '2022-01-01';IMCI在執行該查詢時，會根據訂單表的分區order_date，找到合格分區，並只查詢該分區的資料，從而減少了查詢的資料量和提高了查詢效率。同時，也支援JOIN列的等價關係進行推導，從而更加充分的進行分區剪枝。例如關係R，S的分區鍵均為a，查詢select count(1) from R,S where R.a = S.a and R.a > 10，利用R.a = S.a以及R.a > 10可推匯出S.a > 10，從而用來做關係S的分區剪枝。
不同分區類型的剪枝演算法描述如下：
對於RANGE分區，其不同分區的分界點有序儲存在一個數組裡，因此直接使用二分搜尋法；
對於LIST分區，會將所有分區的list值及其對應的分區ID組成tuple <value, part_id>，按value有序儲存，也是按照二分搜尋法尋找命中分區；
對於HASH分區，則枚舉可能的取值進行hash，計算可能落在哪些分區，只能用於整型欄位並且需要枚舉的數量較少。
此處以分區Pruning演算法（以一級分區）為例：
實際使用中，需要根據具體的資料量和查詢需求來選擇適合的分區類型和分區鍵，以達到最優的查詢效能。
統計資訊剪枝
IMCI利用DataPack上的統計資訊來跳過不需要訪問的pack，類似於Clickhouse中的skipping index以及infobright裡的knowledge grid，在IMCI中稱為Pruner（粗糙索引），Pruner可以協助IMCI最佳化查詢效能。其基本原理是在查詢時利用統計資訊與過濾條件進行剪枝，判斷是否需要掃描某個pack。由於統計資訊記憶體佔用較少，可以常駐記憶體。如果剪枝成功，則可以減少IO次數和條件判斷次數，從而提升查詢效能。
對於一個DataPack來說，被Pruner過濾後有三種可能的結果：Accept（AC）、Reject（RE）以及Partial Accept（PA）。被Accept的DataPack，無需對每條記錄進行過濾，減少了計算開銷；被Reject的DataPack，與本次查詢無關，無需載入進記憶體，同時減少IO與計算開銷，避免LRU Cache汙染；被Partial Accept的DataPack，則需要進一步掃描每條記錄來篩選出合格記錄。
IMCI的Pruner有minmax和Bloom filter兩種類型，分別適用於不同的情境。此外，IMCI還針對Nullable列進行了最佳化，在查詢時Pruner可以跳過包含Null值的DataPack，進一步提升查詢速度。
Minmax
minmax索引是針對大型資料集的一種增強型索引技術。它通過儲存每個資料區塊的最小值和最大值來為資料集構建索引，從而提供快速和高效的資料檢索。minmax索引適用於資料集中、數值連續的資料，例如時間戳記或實數值。它將資料集拆分成塊，然後計算每個塊的最小值和最大值，儲存在索引中。當進行資料查詢時，minmax索引可以根據查詢範圍的最小值和最大值快速定位元據塊，從而減少對不相關資料的訪問。以下圖為例，A、B列包含3個DataPack，條件A>15 and B<10結合minmax索引，最終RowGroup2與RowGroup3可跳過，只需訪問RowGroup1，從而減少了2/3的掃描代價。
minmax索引的優點是它可以在非常快的時間內處理非常大的資料集。它能夠減少為了處理查詢而必須掃描的資料量，因為它只需要處理與查詢範圍相關的資料區塊。另外，minmax索引有助於減少儲存索引所需的空間，因為它只需要儲存每個塊的最小值和最大值，而不是所有資料的索引。
Bloom filter
Bloom filter是一種常用的機率型資料結構，用於判斷一個元素是否屬於某個集合中。它使用一個位元數組和一組雜湊函數來儲存和搜尋元素。當一個元素被添加到過濾器中時，雜湊函數將元素映射到位元數組中的幾個位置，並將相應的位元設定為1。當檢查一個元素是否在過濾器中時，雜湊函數再次應用於該元素，如果所有相應的位元位都是1，則該元素可能在集合中。然而，如果任何一個相應的位元位為0，則該元素肯定不在集合中。Bloom filter是具有空間效率的表示方法，可以快速確定一個元素在不在集合中，但它們可能會產生誤判（false positives）- 查詢一個不在集合中的元素可能會錯誤地指示它在集合中。
Bloom filter的優點是高效、空間效率高、可擴充性強和誤判率可控。這些優點使Bloom filter成為處理大規模資料集中的元素存在性問題的一種非常有用的資料結構。
Bloom filter與minmax也可以結合使用，IMCI會根據兩者的綜合結果來判斷是否要跳過某個資料區塊。
Nullable列最佳化
由於Null值處理邏輯比較特殊，資料庫索引一般針對Null值的列支援不太好。不同資料庫對Nullable列的處理不盡相同。
PolarDB IMCI針對Nullable列進行了最佳化，使得Null值對查詢的效能影響大大減少。在PolarDB的使用者使用情境中，經常出現包含Null值列的情況，如果讓現有使用者使用預設值填充Null值，不僅需要通過DDL花費大量時間更改表的結構，可能還需要更改現有業務的查詢SQL。PolarDB IMCI支援對Null值的列構建minmax以及Bloom filter索引，不僅支援IS Null/IS NOT Null謂詞，還支援>、<、=等其他謂詞的查詢。
對於pack中包含Null值的情況，構建pruner時，跳過該值。例如pack中有[1, 2, 3, null ]四條資料，那麼min=1，max=3。在查詢時，先按照沒有Null值的邏輯進行處理，然後根據處理的結果，結合是否包含Null值，對結果進行轉化。如上圖所示，Pack A1中只有Null，而Pack A2與A3均包含部分Null，此時條件A>15在不考慮Null的情況下先得出[PA, AC, RE] 這樣的結果（由於A1中沒有minmax，因此無法過濾），然後再根據每個pack包含Null值的情況，將結果轉成[RE, PA, RE]，最終可以剪枝掉其中的兩個DataPack，從而提升查詢效能。
Runtime filter
Runtime filter是一種查詢最佳化技術，它是在查詢執行期間動態產生的過濾器。在查詢執行過程中，Runtime filter可以根據已經掃描到的資料值或者其他資訊，過濾掉不需要的資料，從而減少查詢的資料量，提高查詢效能。常見的Runtime filter有Bloom Filter和Min-Max Filter等。它們可以用於多種查詢情境，如join、group by、order by等。
例如，PolarDB IMCI對TopK（order by+limit）進行了最佳化，可以利用Topk運算元構建的Self-sharpening Input Filter，結合儲存層資料區塊上的minmax索引進行pruning，從而加快topk效能，具體實現原理請參見計算下推 。
此外，Runtime filter可用於Hash Join的加速。以SQLSELECT * FROM sales JOIN items ON sales.item_id = items.id WHERE items.price > 1000為例，sales表是事實表，items是維度資料表，維度資料表較小，通過條件price>1000可以進一步減少返回的記錄數。在執行join時，可以依據滿足條件的item_id結果集建立filter，例如滿足條件的min，max分別是1，100，可以產生id > 1 and id < 100的過濾運算式，也可以產生ID的in(id1,id2,id3 ...)運算式。Runtime filter傳遞給左表，左表在掃描記錄進行probe時，可以通過filter提前過濾不滿足條件的記錄，減少probe的次數。對於字串類型，還可以為右表結果集建立Bloom filter來做提前過濾，當然本身Bloom filter也有代價，不太適合結果集比較大的情境。更進一步，如果左表列上有粗糙索引，可以依據filter來做過濾，減少資料區塊掃描。在MPP情境，Runtime filter也能發揮作用，可以有效減少shuffle的資料量。
位元影像索引
位元影像索引在行存中也有使用，例如Oracle就提供位元影像索引的功能，比較適合於列的基數較少的情境。具體來說，就是為每個列值儲存所在行的位置資訊，每個位置資訊只需要一個bit位標識值存在與否。執行查詢過濾時，只需要根據列值拿到位元影像資訊即可定位行的位置，對於多個列組合的AND/OR等謂詞尤其適合。一般來說，B+tree索引比較適合於高基數列，方便快速過濾定位；位元影像索引則正好與B+tree互補。B+tree索引適合搜尋模式固定的情境，對於謂詞OR不是很友好，位元影像索引在這個情境也能有不錯的效果。
位元影像索引的相對於B+tree索引的另外一個優勢是，對於低基數列，儲存空間非常小。如下圖，為表的性別列和職級建立了位元影像索引，表中只有5行資料，那麼一個列值對應的位元影像只需要5個bit即可。相對於傳統的B+tree索引，位元影像索引所需要的儲存空間非常少，具體大小與基數和總的行數相關。對於全域位元影像索引來說，由於位元影像索引的特徵，使得修改任何一行，都需要維護位元影像索引，需要將整個表鎖住，因此代價非常大，適合於讀多寫少的情境。
PolarDB IMCI當前支援datapack粒度的位元影像索引，可以通過位元影像索引可以直接返回所需資料的行號，從而可以有效減少DataPack的訪問。
優勢與適用情境
PolarDB IMCI的多種查詢剪枝技術是相輔相成的，可以結合使用，使用者需要根據自己的資料特徵以及查詢情境，選擇使用相應的方法。IMCI的查詢剪枝技術都需要資料具有一定的分布特徵，局部性越強，pruning效果越好，但現實情境可能並不是很直觀，這時候需要仔細設計。
分區剪枝：該功能需要使用者選擇合適的分區鍵構建分區表。優點是資料預先按分區鍵分布，通常均具有較好的過濾效果，如果使用者大部分查詢條件均包含分區鍵，並且還有按分區管理資料生命週期的需求，分區表pruning是個不錯的選擇，可根據需要建立一級或二級分區。
minmax：一般需要該列資料分布有較好的局部性，且支援範圍查詢。例如時間戳記資料類型，一般天然是有序插入的，這種欄位類型構建minmax一般具有較好的應用價值。
Bloom filter：用於等值條件以及IN條件過濾，對於過濾性較強的等值條件，一般具有比較好的過濾效果。例如各種隨機產生的ID，通常單個ID僅對應少數記錄，包含這種ID的等值過濾條件具有較好的pruning效果。
位元影像索引：適用於單一條件過濾性差、組合條件過濾性強，或者查詢無需物化資料的情境（例如
select count(*) from t where xxx）。
局限性與解決方案
IMCI的查詢各項剪枝技術均具有一定局限性，實際情境需要結合多種技術來提升其查詢剪枝能力。
分區剪枝：缺點是對於存量資料來說，是一個比較昂貴的DDL操作，另外查詢條件必須包含分區鍵才會生效。對於存量資料來說，可以找個空閑時間進行變更操作，而如果查詢條件很多不包含分區鍵，則建議採用其他最佳化手段。
統計資訊剪枝：由於寫入時不排序，統計資訊對於資料分布離散均勻的情境效果比較差，有以下最佳化方案：
減小pack大小。對於minmax與Bloom filter來說，更小的pack意味著更細粒度的索引，通常也具有更好的剪枝效果。IMCI支援調整表的列索引pack大小，然而減小pack大小可能也會導致記憶體佔用的增加。
資料排序。對於資料分布比較隨機的情況，可以考慮使用PolarDB IMCI的排序鍵功能，這樣的資料具有良好的局部性，非常有利於統計資訊剪枝。
關閉pruner。和其他任何索引一樣，統計資訊剪枝不一定有效果，但存在一定的計算與記憶體開銷，對於Bloom filter還存在一定的IO開銷，此時可以查詢時關閉pruner。
效能測試
本小節測試了PolarDB HTAP的粗糙索引和位元影像索引的效能，粗糙索引主要覆蓋了min/max和Bloom filter兩種。測試資料集採用了TPCH的100 GB資料，主要測試了幾種典型的查詢情境，包括點查，範圍查詢等，資料類型主要涉及到數實值型別和字串類型。
測試SQL
輕量級索引是否有效果主要取決於資料分布和查詢類型。為了體現輕量級索引帶來的作用，人為構造了幾條以Scan運算元為主的SQL，對比使用粗糙索引（pruner）和位元影像索引（bitmap-index）加速前後的效果。測試環境採用了全記憶體情境，並發度設定為1，在有IO的情境下，索引的加速效果會更明顯。
Q1:select count(*) from partsupp where ps_suppkey = 41164;
Q2:select count(*) from partsupp where ps_suppkey in (41164,58321);
Q3:select count(*) from partsupp where ps_suppkey between 40000 and 50000;
Q4:select count(*) from orders where o_clerk = 'Clerk#000068170';
Q5:select count(*) from orders where o_clerk in ('Clerk#000068170', 'Clerk#000087784');
Q6:select count(*) from customer where c_mktsegment = 'AUTOMOBILE';
Q7:select count(*) from customer where c_mktsegment in ('AUTOMOBILE','FURNITURE','BUILDING');
Q8:select count(*) from customer where c_mktsegment = 'AUTOMOBILE' or c_phone = '18-338-906-3675';
Q9:select count(*) from customer where c_mktsegment = 'AUTOMOBILE' and c_phone = '18-338-906-3675';測試結果
Q1到Q5主要驗證了粗糙索引（Pruner）的加速效果，partsupp表和orders表的ps_suppkey列，以及o_clerk列分別可以利用min/max索引和Bloom filter索引進行加速，從加速比來看，也基本與過濾的塊成比例。
查詢時間如下：
SQL
查詢耗時（單位：秒）
SQL查詢耗時（單位：秒）
SQL（Pruner）查詢耗時（單位：秒）
Q1
0.11
0.05
Q2
0.14
0.07
Q3
0.13
0.06
Q4
0.89
0.43
Q5
1.85
1.35
查詢時間對比圖如下：
Q6到Q9主要驗證了位元影像索引的加速效果，customer的c_mktsegment列值在各個資料區塊分布均勻，因此僅通過pruner並不能起到加速效果，通過與位元影像索引疊加使用，才能提升這種SQL的執行效率。
查詢時間如下：
SQL
查詢耗時（單位：秒）
SQL查詢耗時（單位：秒）
SQL(Pruner）查詢耗時（單位：秒）
SQL（pruner+bitmap-index）查詢耗時（單位：秒）
Q6
1.43
1.43
0.03
Q7
3.49
3.49
0.07
Q8
2.48
2.48
1.09
Q9
1.25
0.05
0.05
查詢時間對比圖如下：
