SQL Optimizer 詳細解析

一、 巨量資料體系和SQL

1、SQL的處理流程

1.1 Parser

String -> AST (Abstruct Syntax Tree)：

• 詞法分析:拆分字串，得到關鍵詞、數值常數、字串常數、運運算元號等token
• 語法分析:將token組成ASTnode，最終得到一個AST

實現：遞迴下降 (ClickHouse)，Flex 和 Bison (PostgreSQL)，JavaCC (Flink)，Antlr (Presto，Spark)

1.2 Analyzer和Logical Plan

 Analyzer：

• 檢查並繫結Database, Table, Column等元資訊
• SQL的合法性檢查，比如min/max/avg的輸入是數值
• AST -> Logical Plan

 Logical Plan：

• 邏輯地描述SQL對應的分步驟計算操作
• 計算操作:運算元( operator )

1.3 Physical Plan 和 Executor

 Physical Plan: 執行計劃子樹

• 目標:最小化網路資料傳輸
• 利用上資料的物理分佈(資料親和性)
• 增加Shuffle運算元

 Executor

• 單機並行: cache，pipeline, SIMD
• 多機並行: 一個fragment對應多個範例

1.4 小結

• One SQL rules big data all
• SQL 需要依次經過Parser，Analyzer，Optimizer和Executor的處理
• 查詢優化器是資料庫的大腦，在巨量資料場景下對查詢效能至關重要
• 查詢優化器需要感知資料分佈，充分利用資料的親和性
• 查詢優化器按照最小化網路資料傳輸的目標把邏輯計劃拆分成多個物理計劃片段

二、 常見的查詢優化器

1、查詢優化器分類

2、RBO（Rule-based optimizer）

2.1 關係代數

• 運運算元：Select Project Join Rename Union
• 等價變換：結合律、交換律、傳遞性

2.2 優化原則

2.3 RBO-列裁剪

• 掃描表格中所需要的列，而不是全部

2.4 RBO-謂詞下推

• where的表示式是謂詞。謂詞儘快過濾資料，減少開銷2（條件：join是inter）

2.5 RBO-傳遞閉包

• 根據表示式等價關係，過濾條件，推匯出一個新的過濾條件

2.6 RBO-Runtime Filter

對一個join如果能在查詢端提早過濾不必要資料，可減少開銷

• min-max的缺點：範圍必須很緊密
• in-list：只需要掃描in-list裡的資料。缺點：集合個數很多時，in-list也很大
• bloom filter：特性：大小不隨集合大小改變，固定大小，給一個數可以判斷在不在

2.7 小結

• 主流RBO實現一般都有幾百條基於經驗歸納得到的優化規則
• 優點:實現簡單，優化速度快
• 缺點:不保證得到最優的執行計劃

3、CBO（Cost-based optimizer）

3.1 CBO-概念

△使用一個模型估算執行計劃的代價，選擇代價最小的執行計劃

• 執行計劃的代價等於所有運算元的執行代價之和
• 通過RBO得到(所有)可能的等價執行計劃

△運算元代價:CPU，記憶體，磁碟IO，網路I/O等代價

統計資訊+推導規則→計算運算元代價→計算執行計劃代價→執行計劃列舉

3.2 CBO-統計資訊

原始表統計資訊

• 表或者分割區級別:行數、行平均大小、表在磁碟中佔用了多少位元組等
• 列級別: min、max、num nulls、num not nulls、num distinct value(NDV)、histogram 等

推導統計資訊

• 選擇率( selecthwty)：對於某一個過濾條件查詢會從表中返回多大比例的資料
• 基數( careinality )：在查詢計劃中常指運算元需要處理的行數

3.2.1 CBO-統計資訊的收集方式

• 在DDL裡指定需要收集的統計資訊，資料庫會在資料寫入時收集或者更新統計資訊

CREATE TABLE REGION( R_ REGIONKEY INT NOT NULL, R NAME CHAR(25) NOT NULL, R_ COMMENT VARCHAR(152) ) DUPLICATE KEY(R_ REGIONKEY) DISTRIBUTED BY HASH(R_ REGIONKEY) BUCKETS 1 PROPERTIES (" sotumnselelR w");

• 手動執行explain analyze statement，出發資料庫收集或者更新統計資訊

ANALYZE TABLE table_name COMPUTE STATISICS FOR COLUMNS column-name1,column-name2....

動態取樣：

SELECT count(*) FROM table_name

3.2.2 CBO-統計資訊推導規則

• Filter Selectivity
  • AND條件:fs(a AND b)=fs(a)* fs(b)
  • OR條件: fs(a OR b) = fs(a) + fs(b) - (fs(a) * fs(b))
  • NOT條件: fs(NOT a)= 1.0 - fs(a)
  • 等於條件(x = literal )
    • literal < min && literal > max : 0
    • 1/NDV
• 小於條件(x < literal )
  • literal<min:0
  • literal>max:1
  • (literal-min)/(max-min)

3.3 CBO-執行計劃列舉

• 單表掃描:索引掃描(隨機I/O) vs 全表掃描(順序IO)
  • 如果查詢的資料分佈非常不均衡，索引掃描可能不如全表掃描
• Join的實現: Hash Join Vs. SortMerge Join
• 兩表Hash Join :用小表構建雜湊表如何識別小表?
• 多表Join :
  • 哪種連線順序是最優的?
  • 是否要對每種組合都探索?
• N個表連線,僅僅是left-deep tree就有差不多N!種連線順序
  • e.g. N= 10->總共3, 628, 800個連線順序

3.4 CBO-小結

• CBO使用代價模型和統計資訊估算執行計劃的代價
• CBO使用貪心或者動態規劃演演算法尋找最優執行計劃
• 在巨量資料場景下CBO對查詢效能非常重要

4、總結

• 主流RBO實現-般都有幾百條基於經驗歸納得到的優化規則
• RBO實現簡單，優化速度快
• RBO不保證得到最優的執行計劃
• CBO使用代價模型和統計資訊估算執行計劃的代價
• CBO使用貪心或者動態規劃演演算法尋找最優執行計劃
• 巨量資料場景下CBO對查詢效能非常重要

三、 社群開源實踐

1、Apache Calcite概覽

• One size fitsall：統一的SQL查詢引擎
• 模組化,外掛化，穩定可靠
• 支援異構資料模型
  • 關係型
  • 半結構化
  • 流式
  • 地理空間資料
• 內建RBO和CBO

1.1 Calcite RBO

HepPlanner

• 優化規則(Rule)
  • Pattern :匹配表示式子樹
  • 等價變換:得到新的表示式
• 內建有100+優化規則
• 四種匹配規則
  • ARBITRARY/DEPTH FIRST :深度優先
  • TOP DOWN :拓撲順序
  • BOTTOM_ UP :與TOP_ DOWN相反
• 遍歷所有的rule ,直到沒有rule可以被觸發
• 優化速度快,實現簡單,但是不保證最優

1.2 Calcite CBO

VolcanoPlanner

• 基於Wolcano/Cascade 框架
• 成本最優假設
• Memo :儲存候選執行計劃
  • Group :等價計劃集合
• Top-down 動態規劃搜尋
• 應用Rule搜尋候選計劃
• Memo
  • 本質: AND/OR graph
  • 共用子樹減少記憶體開銷
• Group winner:目前的最優計劃
• 剪枝：減少搜尋空間
• Top-down遍歷：選擇winner構建最優執行計劃

1.3 小結

• 主流的查詢優化器都包含RBO和CBO
• Apache Calcite是巨量資料領域很流行的查詢優化器
• Apache Calcite RBO定義了許多優化規則，使用pattern匹配子樹，執行等價變換
• Apache Calcite CBO基於Volcano/Cascade框架
• Volcano/Cascade的精髓: Memo、動態規劃、剪枝

四、 前沿趨勢

1、AI4DB

• 自設定
  • 智慧調參( OtterTune , QTune )
  • 負載預測/排程
• 自診斷和自癒合:錯誤恢復和遷移
• 自優化:
  • 統計資訊估計( Learned cardinalities )
  • 代價估計
  • 學習型優化器( IBM DB2 LEQ )
  • 索引/檢視推薦

2、DB4AI

• 內嵌人工智慧演演算法( MLSQL,SOLFlow )
• 內嵌機器學習框架( SparkML，Alink,dl-on-fink )

3、總結

• 巨量資料創業如火如荼, SQL查詢優化器仍然是必不可少的一個重要元件
• 引擎架構的進化、雲原生、湖倉一體等對SQL查詢優化器有新的要求和挑戰
• AI加持,學習型查詢優化器在不斷進化

五、 大總結

到此這篇關於SQL Optimizer 解析的文章就介紹到這了,更多相關SQL Optimizer內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com！