StarRocks 技術內幕 | 基於全域性字典的極速字串查詢

語言: CN / TW / HK

 作者:馮浩桉,StarRocks 核心研發工程師,StarRocks Committer

在資料庫和儲存系統中,String 型別資料廣泛存在。為了提升 String 的處理效率和節省儲存資源,出現了很多針對 String 型別進行優化的技術手段,例如提升處理效率的各類字典應用,提升儲存效率的字典編碼壓縮技術。

本文主要針對 StarRocks 基於全域性字典做的低基數 String 查詢優化,揭祕其技術內幕。

 

#01

為什麼要引入低基數字典優化

我們先看下兩個 SQL 的對比,表 Lineorder 是 SSB100G 資料集,lo_shippriority 為低基數 int 列,l_shipmode 為低基數 String 列



mysql> select count(cnt) from ( select count(*) cnt from lineorder group by lo_shippriority) tb;
+------------+
| count(cnt) |
+------------+
|          1 |
+------------+
1 row in set (3.51 sec)

mysql> select count(cnt) from ( select count(*) cnt from lineorder group by lo_shipmode) tb;
+------------+
| count(cnt) |
+------------+
|          7 |
+------------+
1 row in set (9.33 sec)

 

可以看到,處理相同資料量的情況下,String 型別的處理時間差不多是 int 型別的 3 倍。

如果能使用整數型別來替代 String 型別進行資料處理,能夠顯著提升系統的效能!

對於利用整型替代字串進行處理,通常是使用字典編碼進行優化。一個 SQL 從輸入到輸出結果,往往會經過這幾個步驟,幾乎每一個階段都可以使用字典優化:Scan,Filter,Agg,Join,Shuffle,Sort。

以 Filter 和 Agg 為例:

  • Filter (過濾操作)

 

對於 Filter 階段來說,如果某一個列是用字典編碼的,我們就可以直接使用編碼之後的整數進行比較,而不是直接用 String 進行比較操作。大多數情況下,整數之間的 Compare 效能會高於字串之間的效能。

  • Agg (聚合操作)

 

對於 Agg 操作,如果使用了字典編碼,我們在聚合中可以使用編碼之後的值作為聚合的 Key。如此一來,在聚合操作的 Hash 表構建和查詢過程中,可以減少 Hash 表中 Key 的比較代價,同時也能夠加快 Hash 值計算,節省記憶體空間,可以提升聚合操作的速度。

因此如果我們使用字典的編碼方式把字串轉變成整型,在 SQL 執行的很多階段,都可以起到正向加速的效果。

使用整型來替代 String 型別進行加速計算,業界通常使用的手段是使用字典優化。但是對於一個複雜系統來說,想要充分利用字典優化,並不是一件容易的事情。

 

#02

為什麼需要全域性字典

在一個分散式執行引擎中,一個 SQL 的執行過程是複雜的。一個查詢會存在多個執行階段,可能會涉及到多個機器多個任務之間的資料交換。如果想充分利用字典優化,那麼需要考慮很多的情況:

  • 在執行過程中,字典要保證全域性性。也就是說在不同的節點之間同樣需要維護一個字典。字典資料始終貫穿 SQL 執行的整個生命週期,如果不是全域性字典,那麼加速只能在區域性進行。例如如果兩個執行節點的字典編碼不一致,那麼在網路傳輸過程中需要同時把字典傳給對端機器,或者是需要提前把字典碼轉為字串再通過網路傳送。如果能保證一個字典的全域性性,在網路傳輸中就可以直接使用字典碼而不再需要傳輸字典。

  • 查詢規劃器規劃出使用全域性字典最高效的方式,如果一個 SQL 在執行過程中沒有網路 Shuffle,也不存在潛在應用字典優化的操作,那麼不再採用字典優化。例如`insert into t1 select * from t2;` 這樣的 SQL,中間既不存在資料網路 Shuffle,也不存在可能會應用到低基數優化的運算元。那麼這樣的 SQL 就不適合使用低基數優化。

對於一個複雜的、支援實時資料更新的分散式資料庫,做到以上兩點,並不容易。所以很多的分散式系統,只是用了字典來做區域性加速,並沒有做全域性加速。

 

#03

如何高效構建全域性字典

為了充分利用字典加速,首先需要解決的問題就是全域性字典構建和維護問題。

 

1、通常的分散式字典構建方式

對於很多系統來說,通常構建全域性字典的方式有兩種:

1. 使用者指定 Schema,使用者在建表的時候,指定對應的列為低基數列

因為使用者指定了低基數,那麼可以在資料匯入的時候,構建全域性字典,因為知道了基數範圍,全域性字典很好維護,按著特定的規則去生成就好了,儲存的代價也不高。 

但是這麼做,主要存在的問題在於: 

  • 對使用者不友好,需要使用者指定 Schema,當基數存在變化,比如基數變高後,不方便維護

  • 無法提升已經執行的系統的效能,必須得重建表並且重新匯入資料後才能使用。 

2. 匯入時候構建全域性字典 

匯入資料時,通過中心節點維護全域性字典。每次遇到新的的字元都要通過中心節點建立一個新的字典碼。但是這麼做的主要問題是中心節點很容易會成為瓶頸。另外中心節點因為需要同時處理維護併發控制。

因為維護和構建字典對於很多系統來說都是一個比較困難的事情,因此很多系統,只是在區域性使用了局部字典來進行加速,並不支援字典的全域性加速。

 

2、StarRocks 全域性字典的構建

 

對於 StarRocks 的全域性字典的構建,主要有以下考慮:

  • 自適應,不需要使用者通過 Schema 指定特定低基數列,而是根據資料特性,自動選擇優化策略。

  • 儘可能避免單點問題,比如資料匯入的時候遇到新的字串,先通過中心節點更新全域性字典。

資料儲存上的字典優化 

首先先來看下 StarRocks 的資料儲存的結構。

StarRocks 的基本儲存單元為 Segment,每個 Segment 的儲存結構如下圖所示:

StarRocks 的儲存結構天然為低基數字符串做了字典編碼。對於 Segment 上的低基數字符串列會有以下特點:

  • Footer 上會儲存有這個 Column 特有的字典資訊,包括字典碼跟原始字串之間的對映關係;

  • Data page 上儲存的不是原始字串,而是整數型別的字典碼(整型)。

簡單的示意圖如下:

當處理低基數 String column 的時候,直接使用編碼後的字典碼,而不是直接處理原始的 String 值。當需要原始的 String 值時,使用字典碼就可以很方便地在這個列的字典資訊裡面拿到原始 String 值。這麼做帶來的明顯好處是:

  • 減少了磁碟IO。

  • 可以提前做一些過濾操作,提升處理速度。

全域性字典的構建

StarRocks 支援 CBO 優化器,並且存在一套統計資訊機制,那麼就可以通過統計資訊來收集全域性字典。我們通過統計資訊,篩選出潛在的低基數列,再從潛在的低基數列的元資料中讀取字典資訊,然後做去重/編碼操作,就可以收集到全量的字典了。

全域性字典的正確性保證

對於低基數列來說,那麼肯定會出現一種情況,在某次匯入中匯入了新的 String (這個 String 不在全域性字典的集合內),那麼這個時候,原先已經構建的全域性字典就沒有辦法包含所有的字串的值。因此 StarRocks 需要維護全域性字典的有效性。

全域性字典可能失效只會出現在匯入, StarRocks 支援了很多型別的資料匯入方式,而所有的匯入都有兩個共同點

  • 匯入產生新的 Segment。

  • 通過 Master FE 提交事務。

對於低基數列,所有 Segment 中都必定存在區域性字典資訊,那麼對於一個新的匯入,在產生新的 Segment 時,會有幾種情況。

  • 如果新生成的 Segment 沒有了區域性字典,那麼說明這個列很可能是一個高基數列,此時不再適合全域性字典優化;

  • 新生成的 Segment 有區域性字典,而且區域性字典中的所有 String 是全域性字典的子集,這種情況下可以直接使用舊的字典;

  • 新生成的 Segment 有區域性字典,而且區域性字典所有的 String 值,部分不在全域性字典裡,此時全域性字典失效已經生效,需要重新生成全域性字典。

無論出現了上面的哪種情況,在向 FE 中心節點提交的時候,帶上這個對應的資訊,我們就都能保證全域性字典的正確性。

因為每次匯入都是產生新的版本,而查詢是支援 MVCC 的,每次查詢都會帶有一個固定的查詢版本號。在某一時刻中,如果出現一個新的版本資料,那麼對這個版本出現之前的所有查詢都是不可見的。因此我們查詢中如果有新的匯入,那麼已發起的查詢也是不受影響的。

 

#04

如何高效使用全域性字典

1、CBO 優化器的緊密配合

對於一個簡單的聚合 SQL 來說,其執行過程如下:

 

因為 StarRocks 是個分散式系統,其資料分散在多個後端 BE 例項上,且存在多個副本。Segment 內的字典是一個區域性的字典,不能作為全域性字典碼使用。

對於一個沒有使用全域性字典優化的 SQL,在 SCAN NODE 掃描 Segment 資料的過程中就需要將對應把區域性的字典碼(int)解碼成原始的 String 返回給上層節點。

如果使用了全域性字典優化,我們就不需要 SCAN NODE 節點就進行 Decoded,而是可以將原先的區域性字典碼(int),直接對映到全域性字典中的字典碼(int),並在之後的計算處理過程中,均使用全域性字典碼進行處理。當遇到某些特殊的運算元,或者是需要具體的依賴字串內部資訊的時候,再按著全域性字典的資訊,Decoded 出原始的 String 值,這樣可以充分利用到全域性字典的加速。

下圖展示了 SCAN NODE 使用全域性字典後,向上傳遞的資料使用了 int 編碼:

 

既然我們已經有了全域性字典,那麼接下來的問題就是更高效地使用好全域性字典。 

當存在全域性字典的時候,所需要做的比較關鍵的就是:

  • 將對 String 的操作轉化為對 int 的操作時 ,從而提升處理的速度,節省對應的資源。

  • 當遇到無法使用 int 替代 String 的操作時,需要提前將字典碼 Decoded 成 String。

舉個例子:

lineitem 表中的 l_shipmode 是低基數 String 列

select count(*) from lineitem group by l_shipmode;

 

對於這個 SQL 來說,我們需要的只是聚合之後的行數,因此在整個 SQL 的執行過程中,都可以使用 int 來替代 String 進行處理,並不需要進行 Decoded。

select count(*), l_shipmode from lineitem group by l_shipmode;

 

而對於這個 SQL,需要的不僅僅是聚合後的結果數,還有對應的字串值。在這裡我們需要在結果輸出之前,進行 Decoded,將 int 值翻譯成 String。

對於第二條 SQL 來說,其執行過程如下所示:

 

可以看到第二條 SQL 多了個 Decode 節點。

對於低基數 String 列來說,聚合後的行數並不多,這個 Decode 的成本基本可以忽略不計,反而在之前的處理,使用 int 替代 String 所帶來的提升是巨大的。

那麼,對於查詢規劃器來說,要做的就是選擇最合適的 Decode 時期,最大限度地提升效能。

 select * from lineitem;

對於上面的 SQL 來說,使用全域性字典,反而會帶來額外的解碼的開銷。對於這樣的 SQL,我們的 CBO 優化器需要正確規劃,並且不會使用字典。

 

2、全域性字典的字串函式優化

上面的 SQL 都是簡單的例子。如果稍微對 SQL 進行一些改動,比如:

select count(*), l_shipmode from lineitem group by substr(l_shipmode, 1, 3);

在這個 SQL 中,需要對 String 列進行 substr 運算,並且按著運算後的值進行聚合,這麼一看,那肯定是需要在聚合前,插入一個 Decode 節點來把字典碼轉為具體的字串值了,甚至在掃描資料的時候,就需要原始的 String 列了。

對於這條 SQL 來說,使用 int 值替代 String 來進行聚合,所帶來的提升是巨大的,我們應該發揮全域性字典的最大價值。

對於大多數的字串函式來說,他們的計算往往有下面的一些特點:

  • 對於固定的輸入,輸出也是固定,最簡單的比如 substring 函式, substring("abc", 1, 2) 的結果一定是 "AB";

  • 大部分 String 操作,都符合上面的定義。

既然對於單個 String 的運算,輸出是固定的,那麼對於固定集合的 String 的運算,其結果集合也一定是固定的,比如對 {"s1", "s2", "s11" } 進行 substring(str, 1, 2) 運算,其結果也一定是 {"s1", "s2", "s11" }。

很明顯,當有了低基數全域性字典,全域性字典裡面的 String 取值,就是固定的集合。因此,我們將對單個 String 的操作,轉化為對 String 集合的操作,而這個操作,在 SQL 執行的過程中,只需要執行一次。

以上面的 substr  SQL 為例子,當低基數列 l_shipmode 存在全域性字典時,我們運用 substr 對全域性字典進行計算,計算的示意圖如下:

 

對於上圖所示的全域性字典來說,substring("hello", 1, 2) 和 substring("world", 1, 3)產生的結果集是 {"he", "wo"}。我們會把所有的輸出都加入到一個新的字典中,與此同時,我們還得到了兩個字典之間的轉換關係。

例如字典碼1的輸入在經過這個函式之後會變成新字典的字典碼1。

有了這個對映關係,對輸入的資料,進行 substring 操作,那就很簡單了,因為我們輸入的資料是全域性字典碼,並不是原始的 String,我們只需要按著 substring 中兩個字典之間的轉換關係,將對應的字典碼通過對映輸出成對應的新字典碼,就完成了相關函式的計算。

 

對於這類的字串函式,並不需要進行 Decode 獲取原始 String 來呼叫函式處理,而且這種對映的方法,對於直接使用字串進行計算也有一定的效能提升,尤其是對複雜的表示式。

 

#05

優化效果

我們選取了幾組典型的 SQL,對比了開啟低基數下的效能。

StarRocks 2.0+後的版本預設會開啟低基數字典優化:

 

set cbo_enable_low_cardinality_optimize = true;

對比 SQL:


select count(*),lo_shipmode from lineorder group by lo_shipmode;
select count(distinct lo_shipmode) from lineorder;
select count(*),lo_shipmode,lo_orderpriority from lineorder group by lo_shipmode,lo_orderpriority;
select count(*),lo_shipmode,lo_orderpriority from lineorder group by lo_shipmode,lo_orderpriority,lo_shippriority;
select count(*) from (select count(*) from lineorder_flat group by lo_shipmode,lo_orderpriority,p_category,s_nation,c_nation) t;
select count(*) from (select count(*) from lineorder_flat group by lo_shipmode,lo_orderpriority,p_category,s_nation,c_nation,p_mfgr) t;
select count(*) from (select count(*) from lineorder_flat group by substr(lo_shipmode,2),lower(lo_orderpriority),p_category,s_nation,c_nation,s_region,p_mfgr) t;
select count(*),lo_shipmode,s_city from lineorder_flat group by lo_shipmode,s_city;
select count(*) from lineorder_flat group by c_city,s_city;
select count(*) from lineorder_flat group by c_city,s_city,c_nation,s_nation;
select count(*) from lineorder_flat group by lo_shipmode,lo_orderdate;
select count(*) from lineorder_flat group by lo_orderdate,s_nation,s_region;

對比結果:

從效果上來看,開啟低基數優化的 SQL 比沒開啟低基數優化的 SQL 平均快了 3 倍。

 

 

#06

總結

StarRocks 的低基數 String 優化,主要的特點有:

  • 全域性的字典加速,作用於 SQL 執行的各個階段。

  • 基於 CBO 優化器的,自適應選擇全域性字典的加速策略。

  • 無 Schema,自適應,使用者不需要指定特定的低基數列。

  • 對使用者透明,不需要重新導資料。

  • 高效能,業界領先水平。

  • 支援場景豐富,相容大部分 String 處理邏輯。

 

 

關於 StarRocks 

StarRocks 創立兩年多來,一直專注打造世界頂級的新一代極速全場景 MPP 資料庫,幫助企業建立“極速統一”的資料分析新正規化,助力企業全面數字化經營。

當前已經幫助騰訊、攜程、順豐、Airbnb 、滴滴、京東、眾安保險等超過 110 家大型使用者構建了全新的資料分析能力,生產環境中穩定執行的 StarRocks 伺服器數目達數千臺。 

2021 年 9 月,StarRocks 原始碼開放,在 Github 上的星數已超過 3100 個。StarRocks 的全球社群飛速成長,至今已有超百位貢獻者,社群使用者突破 5000 人,吸引幾十家國內外行業頭部企業參與共建。