SQL Optimizer 詳細解析

Posted on by

一、 大數據體系和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內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：