StarRocks 原始碼導讀一

語言: CN / TW / HK

作者: 康凱森

日期: 2021-09-12

分類:OLAP

    • StarRocks Relation To Logical Plan
    • StarRocks Logical Plan Rewrite
    • StarRocks Cost Based Optimize
    • StarRocks 統計資訊收集
    • StarRocks 如何優化搜尋耗時
    • StarRocks CBO 優化器理論和實踐的差別
  • StarRocks 向量化執行器
    • StarRocks 表示式向量化
    • StarRocks 儲存層向量化
    • StarRocks 如何進行效能優化

2021年9月8日,我司鼎石科技開放了核心資料庫產品 StarRocks 原始碼: https://github.com/StarRocks/starrocks ,StarRocks 基於 Apache Doris 開發,我們十分感謝 Apache Doris 社群貢獻了這樣一個優秀的OLAP資料庫,也感謝所有向 Apache Doris 貢獻過的同學,讓我們可以站在巨人的肩膀上快速前進和迭代,不過 StarRocks 和 Apache Doris 已經有了很大的不同,我們新增和修改的程式碼行數達到了幾十萬行,我將分兩篇文章對 StarRocks 的原始碼進行導讀,這篇文章主要介紹 StarRocks 全新的 CBO 優化器和向量化執行器。

StarRocks CBO 優化器

如果一條SQL的執行是一場旅程,查詢執行器就是你的交通工具,你的交通工具效能越好,在相同的路徑下,旅程的耗時自然越短。但是從旅程的出發點到終點可能有成千上萬條路徑,有康莊大道,也有林蔭小路,而查詢優化器的作用就是選擇出最短,最合適的道路。 一般 SQL 越複雜,資料量越大,查詢優化器的意義就越大,因為不同執行方式的效能差別可能有成百上千倍

一條 SQL 查詢時會依次需要經過查詢解析器,分析器, 優化器,查詢執行層和儲存層。 查詢優化器的輸入是一顆邏輯的抽象語法樹,輸出是一顆“最優的” 物理執行計劃。 查詢越複雜,資料量越大,物理執行計劃的好壞對查詢效能影響越大,所以一款成熟的商業資料庫都需要一個強大的,成熟的查詢優化器。

StarRocks 全新的 CBO 優化器主要基於 Cascades,Columbia,ORCA 論文實現,也參考了 ORCA,Presto,Calcite,CMU Noisepage,CockroachDB 等專案,核心優化流程基本和 Columbia 一致,在具體工程實踐中,我們進行了很多優化與創新。

整個 CBO 優化器的流程如下所示,SQL Parser 部分和 Apache Doris 相同,我們暫時還沒有進行重寫,我們的重寫是從 Analyzer 部分開始,整個CBO 優化器的程式碼都位於 SQL 目錄下

如果你對 CBO 優化器感興趣,推薦先閱讀 Columbia 論文 ,這篇論文比較通俗易懂,論文中涉及的基本概念我在本文中就不再贅述。

StarRocks Analyzer

StarRocks Analyzer 程式碼在 Analyzer 目錄下 ,主要完成了 表名,列名的識別和解析(Binder),SQL合法性檢查,SQL重寫,函式檢查,別名處理。 核心類是 QueryAnalyzerExpressionAnalyzer , Analyzer的結果是一個有層級結構的 Relation

StarRocks Relation To Logical Plan

程式碼在 transformer 目錄下 核心類是 RelationTransformer,QueryTransformer,SubqueryTransformer。

StarRocks Logical Plan Rewrite

主要完成了:

  • 各種表示式的重寫和化簡
  • 列裁剪
  • 謂詞下推
  • Limit 下推
  • 等價謂詞推導(常量傳播)
  • Outer Join 轉 Inner Join
  • 常量摺疊
  • 公共表示式複用
  • 子查詢重寫
  • Lateral Join 化簡
  • 分割槽分桶裁剪
  • Empty Node 優化

Rewrite Task 的驅動在 Optimizer類 ,各種 Rewrite的Rule在 rewrite 目錄

StarRocks Cost Based Optimize

StarRocks 整個搜尋框架如下圖所示:

我們在 Logical Plan Rewrite 完成後,正式基於 Columbia 論文進行 CBO 優化,主要包括下面的優化:

  • 兩階段聚合優化
  • Join 左右表調整 : StarRocks 是用永遠用右表構建 Hash 表,所以右表應該是小表,StarRocks 可以基於 cost 自動調整左右表順序,也會自動把 left join 轉 right join。
  • Join 多表 Reorder :多表Join 如何選擇出正確的Join 順序,是優化器的核心,當Join表的數量小於等於5時,StarRocks 會基於Join 交換律和結合律進行 Join Reorder,大於5時,StarRocks 會基於貪心演算法 和動態規劃進行 Join Reorder。
  • Join 分散式執行選擇 :StarRocks 支援地分散式Join 方式有Broadcast,Shuffle, 單邊 Shuffle,Colocate,Replicated。StarRocks 會基於 Cost 估算 和 Property Enforce 機制選擇出 “最佳” 的 Join 分散式執行方式
  • Push Down Aggregate to Join
  • 物化檢視選擇與重寫

CBO 優化的 幾個核心資料結構是 Memo, Group, GroupExpression, OptExpression, 位於 optimizer 目錄下 , 搜尋框架位於 task 目錄下 包括 OptimizeGroupTask,OptimizeExpressionTask, ApplyRuleTask,DeriveStatsTask,EnforcerAndCostTask,其中最核心和最複雜的是 EnforcerAndCostTask,Transformation 和 Implementation 的各種 Rule 位於 rule 目錄下 ,你可以在 RuleSet 類 中找到所有的Rule。

在 CBO 優化中,Logic Plan 會先轉成 Memo的資料結構,(Logic Plan 到 Memo 的對映如下圖所示),然後會基於 Transform Rule 擴充套件搜尋空間,基於 Implement Rule 將 Logical Group Expression 轉換成 Physical Group Expression,基於統計資訊和 Cost 估計從 Memo 中選擇一組 Cost 最低的 Physical Group Expressions,最後將選擇的 Physical Group Expressions 轉成 Physical Plan tree.

StarRocks 統計資訊收集

Cost 估算的基礎是統計資訊估算,統計資訊估算的基礎是統計資訊收集。 StarRocks 目前支援表級別和列級別的統計資訊,支援自動收集和手動收集兩種方式,無論自動還是手動,都支援全量收集和抽樣收集兩種方式。

StarRocks 統計資訊收集內容和收集框架如下圖所示。

StarRocks 統計資訊收集的程式碼位於 statistic

抽樣統計資訊收集的難點在於如何根據抽樣得到的統計值估算出整體資料的統計值,一旦選擇抽樣收集的方式,誤差就很難避免。

StarRocks Cost 估算

統計資訊估算和 Cost 估算是整個 CBO 優化器最關鍵的部分之一,其中每一個公式和係數的改動,都會對最終的 Plan 產生很大的影響,這一塊也是業界一直在研究的熱點,統計資訊估算和 Cost 估算的難點體現在下面幾個方面:

  1. 資料分佈不是完全均勻的
  2. 多列之間的資料特徵不是完全獨立的
  3. 一些函式和複雜表示式的選擇率無法較好地估計
  4. 基於多個維表的謂詞去估算事實表的基數時,很難估算準
  5. 基數估計的誤差會被層層放大

統計資訊估算和 Cost 估算 的程式碼 位於 statistic 目錄cost 目錄

StarRocks 如何優化搜尋耗時

  1. 提前 Rewrite (預處理) :在進入優化階段之前,對錶達式 進行 Rewrite, 對整個Plan 進行 肯定會變優的Rewrite,降低優化時的搜尋空間大小
  2. Multi-Stage Optimization :分多個Stage 進行優化,每個Stage 只應用部分Rule,越複雜的Rule 應用地越靠後
  3. 按需 Explore group :Logical transformation 和 Physical implementation 不會分兩階段執行,對於一個 Group,不必生成完所有的邏輯表示式。通過transformation rule 生成的邏輯表示式 會立即被 implemented 成物理表示式並計算 cost。這種實現方式可以基於 Cost 進行快速裁剪,避免列舉低效的 Plan。 例如,我們計算 ((A join B join C) join D) 的 cost, 如果 先 ((A join B join C) , 再 join D 的 cost 已經大於了 ((A join B) join (C join D)) 的cost, 我們就可以進行快速裁剪,避免對 (A join B join C) 進行 join order 的列舉。
  4. Upper bounds Pruning : 如果當前 Group 的 lower bound 大於當前 context的 UpperBound,我們就沒有必要繼續enumerated 當前 Group 的 input groups
  5. 記憶化 : 利用 Bitmap 去重,保證一個Group 不會用同一個Rule重複優化
  6. Group 支援刪除(替換 ): 如果經過 Transform Rule 後生成的新Group Expression 一定比舊的好,我們可以把舊的Group Expression 從Group 刪除,或者使用新的Group Expression 直接替換掉舊的 Group Expression,這樣可以降低搜尋空間的大小
  7. Multi Join Reorder : 多張表Join reorder 時,按照Multi-Join 或者N-Array join 一起處理,而不是一個一個處理
  8. 搜尋終止條件 :找到了低於 Cost threshold 的Plan;超時;轉換規則已用盡

StarRocks CBO 優化器理論和實踐的差別

雖然幾篇論文理論描述的都比較詳細,但是我們在實踐過濾中,好多關鍵點和論文並不相同,或者論文沒有描述,下面簡單羅列幾點

  1. ExploreGroupTask 在論文的搜尋流程中是存在的,但是我們沒有用到
  2. 如何正確和快速地 Merge 兩個 Group
  3. Project 節點的處理:有了 Project 之後,Join的 Reorder 就會比較麻煩
  4. 如何禁掉特定的Plan:由於查詢排程和查詢執行可能無法支援某些Plan,為了保證得到正確的結果,我們必須禁掉特定的Plan
  5. 查詢優化器需要和查詢排程器緊密配合:在分散式環境下,StarRocks支援了 Broadcast,Shuffle, 單邊 Shuffle,Colocate,Replicated 多種Join 分散式執行方式,對於上面多種分散式執行策略,查詢排程也必須能夠支援
  6. 在分散式環境下,Enforce 出來的 Sort 節點可能既需要按照1階段執行,也需要按照2階段執行
  7. 多個 Enforce 屬性的處理
  8. Logical Plan 的 Rewrite 是基於 Memo 還是 Tree 實現
  9. Group 的統計資訊推導進行一次是否足夠
  10. 。。。

StarRocks 向量化執行器

StarRocks 從零實現了向量化執行器,向量化執行主要分為運算元的向量化和表示式的向量化執行,儲存層的向量化。 向量化執行的核心是批量按列執行 , 批量執行,相比傳統的按行執行,可以有更少的虛擬函式呼叫,更少的分支判斷,按列執行,相比於按行執行,對CPU Cache 更友好,更易於SIMD優化。

向量化的基數資料結構是 Column 和 Chunk,其程式碼位於 column 目錄下

StarRocks 運算元向量化

運算元向量化的核心思路主要是將之前 get_next 拉取一個 RowBatch 變成 拉取一個 Chunk, 演算法中的按行處理 變成 按列處理。

運算元向量化的大部分程式碼位於: exec / vectorized 目錄下

運算元向量化的難點在於 多列聚合的向量化,多列 Join的向量化,多列 Sort的向量化,Shuffle的向量化,記憶體申請釋放上的優化。

StarRocks 表示式向量化

表示式向量化的核心思路主要是將之前的表示式按行處理變成按列處理,上圖是一個加法向量化的示意圖。

標量函式和表示式的向量化程式碼位於 exprs / vectorized 目錄下

聚合函式表示式向量化的程式碼位於 exprs / agg 目錄下

視窗函式向量化的程式碼位於 window.h

Table Function 向量化的程式碼位於 exprs / table_function 目錄下

表示式向量化的難點在於如何處理編譯器自動進行SIMD 指令優化,以及如何顯式進行 SIMD 指令優化。

StarRocks 儲存層向量化

儲存層向量化主要包括:

  • 儲存層按照每一列的Page 讀取資料後,直接瓶裝成 Chunk 資料結構
  • 向量化過濾
  • 聚合模型的向量化聚合

儲存層向量化的程式碼主要位於 storage/vectorized 目錄storage/rowset/vectorized 目錄 下,查詢時涉及的核心類是 segment_iterator

儲存層進行了自適應延遲物化,自適應聚合,Operations On Encoded Data的優化。

延遲物化的示意圖如下:

Operations On Encoded Data的示意圖如下:

StarRocks SIMD 優化

我們在實現向量化執行器過程中,會盡量想辦法觸發編譯器的自動 SIMD 優化,不能自動觸發的,會嘗試進行手動 SIMD 優化。 手動 SIMD 優化的程式碼直接全域性搜尋 SSE 和 AV2 就可以看到。

下圖中列出了我們部分進行手動 SIMD 優化的操作:

StarRocks 自適應優化

我們知道,不同的資料分佈或者資料特點往往需要不同的演算法或者資料結構進行處理,所以在 StarRocks 向量化引擎中,我們進行比較多的自適應優化。

除了上面提到的儲存層的自適應預聚合,自適應延遲物化。我們在下面幾處也實現了自適應優化:

  • Runtime Filter 過濾: 有過濾度時再進行過濾,沒有過濾度時就不再進行過濾
  • 聚合 Hash Map的使用: 低基數時直接使用phmap::flat_hash_map, 高基數時使用 phmap::parallel_flat_hash_map
  • 兩階段 Streaming 聚合時:有聚合效果是進 Hash 表,沒有聚合效果時直接傳送資料
  • 多個 Filter 過濾時何時進行 Chunk 重整

StarRocks 如何進行效能優化

和 CBO 優化器不同,大家可以看到向量化執行本身框架上的風險不大,所以不同系統向量化執行器的最終效果如何,其實就是看細節上的效能優化。

StarRocks 的效能優化主要從 5 個方面進行:

  1. 演算法和資料結構的選擇 :演算法和資料結構是最基礎的,但有些情況下的選擇和優化卻並沒有那麼簡單。 比如:進行 Int 型別去重時,我們應該選擇Bitmap 還是 HashSet, 其實是不一定的,因為兩者都有明顯優勢的場景
  2. 自適應 : 在進行效能優化時,如果我們知道的上下文足夠多,我們就可以進行更多針對性的優化,但是有些上下文可能只有在執行時我們才能知道,所以此時我們就需要進行自適應策略
  3. SIMD 指令優化 : 在按列處理的前提下,儘可能自動或者手動進行SIMD 指令優化
  4. C++ Low Level 優化 : 比如 Copy To Move,不同API的選擇,編譯期運算,memcpy, memcmp, 非同步,鎖等。 有些規則可能大家都知道,但是實際實現時就可能忽略或者沒有意識到,比如 大物件的 Move,很多時候一個細節的不注意,就變成了 Copy
  5. CPU Cache 優化 :當我們 CPU 指令的個數和效率已經優化到最佳的時候,我們就需要優化 CPU Cache 了。 包括 記憶體對齊,Padding,時間和空間區域性性優化,Prefetching,Cache Blocking,更緊湊的記憶體佈局,Cache Line Conflict, Code Cache 優化。

關於後面4點,我之後會寫文章詳細說明和解釋。

結語

本文主要進行了 StarRocks CBO 優化器和向量化執行器兩個模組的原始碼導讀,下一篇文章會進行 Pipeline 並行執行引擎,Update 儲存引擎,匯入和 Compaction 向量化,Hive 外表,Global Runtime filter, Lateral Join, Fast Decimal, Array 型別 等模組或者功能的原始碼導讀。

如果你對資料庫研發,測試,解決方案,DBA,銷售感興趣,歡迎將你的簡歷傳送到 [email protected]

評論