一、 大數(shù)據(jù)體系和SQL

1、SQL的處理流程

1.1 Parser

String -> AST (Abstruct Syntax Tree)：

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

實現(xiàn)：遞歸下降 (ClickHouse)，F(xiàn)lex 和 Bison (PostgreSQL)，JavaCC (Flink)，Antlr (Presto，Spark)

1.2 Analyzer和Logical Plan

 Analyzer：

• 檢查并綁定Database, Table, Column等元信息
• SQL的合法性檢查，比如min/max/avg的輸入是數(shù)值
• AST -> Logical Plan

 Logical Plan：

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

1.3 Physical Plan 和 Executor

 Physical Plan: 執(zhí)行計劃子樹

• 目標:最小化網絡數(shù)據(jù)傳輸
• 利用上數(shù)據(jù)的物理分布(數(shù)據(jù)親和性)
• 增加Shuffle算子

 Executor

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

1.4 小結

• One SQL rules big data all
• SQL 需要依次經過Parser，Analyzer，Optimizer和Executor的處理
• 查詢優(yōu)化器是數(shù)據(jù)庫的大腦，在大數(shù)據(jù)場景下對查詢性能至關重要
• 查詢優(yōu)化器需要感知數(shù)據(jù)分布，充分利用數(shù)據(jù)的親和性
• 查詢優(yōu)化器按照最小化網絡數(shù)據(jù)傳輸?shù)哪繕税堰壿嬘媱澆鸱殖啥鄠€物理計劃片段

二、 常見的查詢優(yōu)化器

1、查詢優(yōu)化器分類

2、RBO（Rule-based optimizer）

2.1 關系代數(shù)

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

2.2 優(yōu)化原則

2.3 RBO-列裁剪

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

2.4 RBO-謂詞下推

• where的表達式是謂詞。謂詞盡快過濾數(shù)據(jù)，減少開銷2（條件：join是inter）

2.5 RBO-傳遞閉包

• 根據(jù)表達式等價關系，過濾條件，推導出一個新的過濾條件

2.6 RBO-Runtime Filter

對一個join如果能在查詢端提早過濾不必要數(shù)據(jù)，可減少開銷

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

2.7 小結

• 主流RBO實現(xiàn)一般都有幾百條基于經驗歸納得到的優(yōu)化規(guī)則
• 優(yōu)點:實現(xiàn)簡單，優(yōu)化速度快
• 缺點:不保證得到最優(yōu)的執(zhí)行計劃

3、CBO（Cost-based optimizer）

3.1 CBO-概念

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

• 執(zhí)行計劃的代價等于所有算子的執(zhí)行代價之和
• 通過RBO得到(所有)可能的等價執(zhí)行計劃

△算子代價:CPU，內存，磁盤IO，網絡I/O等代價

統(tǒng)計信息+推導規(guī)則→計算算子代價→計算執(zhí)行計劃代價→執(zhí)行計劃枚舉

3.2 CBO-統(tǒng)計信息

原始表統(tǒng)計信息

• 表或者分區(qū)級別:行數(shù)、行平均大小、表在磁盤中占用了多少字節(jié)等
• 列級別: min、max、num nulls、num not nulls、num distinct value(NDV)、histogram 等

推導統(tǒng)計信息

• 選擇率( selecthwty)：對于某一個過濾條件查詢會從表中返回多大比例的數(shù)據(jù)
• 基數(shù)( careinality )：在查詢計劃中常指算子需要處理的行數(shù)

3.2.1 CBO-統(tǒng)計信息的收集方式

• 在DDL里指定需要收集的統(tǒng)計信息，數(shù)據(jù)庫會在數(shù)據(jù)寫入時收集或者更新統(tǒng)計信息

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");

• 手動執(zhí)行explain analyze statement，出發(fā)數(shù)據(jù)庫收集或者更新統(tǒng)計信息

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

動態(tài)采樣：

SELECT count(*) FROM table_name

3.2.2 CBO-統(tǒng)計信息推導規(guī)則

• 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-執(zhí)行計劃枚舉

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

3.4 CBO-小結

• CBO使用代價模型和統(tǒng)計信息估算執(zhí)行計劃的代價
• CBO使用貪心或者動態(tài)規(guī)劃算法尋找最優(yōu)執(zhí)行計劃
• 在大數(shù)據(jù)場景下CBO對查詢性能非常重要

4、總結

• 主流RBO實現(xiàn)-般都有幾百條基于經驗歸納得到的優(yōu)化規(guī)則
• RBO實現(xiàn)簡單，優(yōu)化速度快
• RBO不保證得到最優(yōu)的執(zhí)行計劃
• CBO使用代價模型和統(tǒng)計信息估算執(zhí)行計劃的代價
• CBO使用貪心或者動態(tài)規(guī)劃算法尋找最優(yōu)執(zhí)行計劃
• 大數(shù)據(jù)場景下CBO對查詢性能非常重要

三、 社區(qū)開源實踐

1、Apache Calcite概覽

• One size fitsall：統(tǒng)一的SQL查詢引擎
• 模塊化,插件化，穩(wěn)定可靠
• 支持異構數(shù)據(jù)模型
  • 關系型
  • 半結構化
  • 流式
  • 地理空間數(shù)據(jù)
• 內置RBO和CBO

1.1 Calcite RBO

HepPlanner

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

1.2 Calcite CBO

VolcanoPlanner

• 基于Wolcano/Cascade 框架
• 成本最優(yōu)假設
• Memo :存儲候選執(zhí)行計劃
  • Group :等價計劃集合
• Top-down 動態(tài)規(guī)劃搜索
• 應用Rule搜索候選計劃
• Memo
  • 本質: AND/OR graph
  • 共享子樹減少內存開銷
• Group winner:目前的最優(yōu)計劃
• 剪枝：減少搜索空間
• Top-down遍歷：選擇winner構建最優(yōu)執(zhí)行計劃

1.3 小結

• 主流的查詢優(yōu)化器都包含RBO和CBO
• Apache Calcite是大數(shù)據(jù)領域很流行的查詢優(yōu)化器
• Apache Calcite RBO定義了許多優(yōu)化規(guī)則，使用pattern匹配子樹，執(zhí)行等價變換
• Apache Calcite CBO基于Volcano/Cascade框架
• Volcano/Cascade的精髓: Memo、動態(tài)規(guī)劃、剪枝

四、 前沿趨勢

1、AI4DB

• 自配置
  • 智能調參( OtterTune , QTune )
  • 負載預測/調度
• 自診斷和自愈合:錯誤恢復和遷移
• 自優(yōu)化:
  • 統(tǒng)計信息估計( Learned cardinalities )
  • 代價估計
  • 學習型優(yōu)化器( IBM DB2 LEQ )
  • 索引/視圖推薦

2、DB4AI

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

3、總結

• 大數(shù)據(jù)創(chuàng)業(yè)如火如荼, SQL查詢優(yōu)化器仍然是必不可少的一個重要組件
• 引擎架構的進化、云原生、湖倉一體等對SQL查詢優(yōu)化器有新的要求和挑戰(zhàn)
• AI加持,學習型查詢優(yōu)化器在不斷進化

五、 大總結

到此這篇關于SQL Optimizer 解析的文章就介紹到這了,更多相關SQL Optimizer內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

最新評論