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

1、SQL的處理流程

1.1 Parser

String -> AST (Abstruct Syntax Tree)：

• 詞法分析:拆分字符串，得到關(guān)鍵詞、數(shù)值常量、字符串常量、運(yùn)算符號(hào)等token
• 語(yǔ)法分析:將token組成ASTnode，最終得到一個(gè)AST

實(shí)現(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對(duì)應(yīng)的分步驟計(jì)算操作
• 計(jì)算操作:算子( operator )

1.3 Physical Plan 和 Executor

 Physical Plan: 執(zhí)行計(jì)劃子樹(shù)

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

 Executor

• 單機(jī)并行: cache，pipeline, SIMD
• 多機(jī)并行: 一個(gè)fragment對(duì)應(yīng)多個(gè)實(shí)例

1.4 小結(jié)

• One SQL rules big data all
• SQL 需要依次經(jīng)過(guò)Parser，Analyzer，Optimizer和Executor的處理
• 查詢(xún)優(yōu)化器是數(shù)據(jù)庫(kù)的大腦，在大數(shù)據(jù)場(chǎng)景下對(duì)查詢(xún)性能至關(guān)重要
• 查詢(xún)優(yōu)化器需要感知數(shù)據(jù)分布，充分利用數(shù)據(jù)的親和性
• 查詢(xún)優(yōu)化器按照最小化網(wǎng)絡(luò)數(shù)據(jù)傳輸?shù)哪繕?biāo)把邏輯計(jì)劃拆分成多個(gè)物理計(jì)劃片段

二、 常見(jiàn)的查詢(xún)優(yōu)化器

1、查詢(xún)優(yōu)化器分類(lèi)

2、RBO（Rule-based optimizer）

2.1 關(guān)系代數(shù)

• 運(yùn)算符：Select Project Join Rename Union
• 等價(jià)變換：結(jié)合律、交換律、傳遞性

2.2 優(yōu)化原則

2.3 RBO-列裁剪

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

2.4 RBO-謂詞下推

• where的表達(dá)式是謂詞。謂詞盡快過(guò)濾數(shù)據(jù)，減少開(kāi)銷(xiāo)2（條件：join是inter）

2.5 RBO-傳遞閉包

• 根據(jù)表達(dá)式等價(jià)關(guān)系，過(guò)濾條件，推導(dǎo)出一個(gè)新的過(guò)濾條件

2.6 RBO-Runtime Filter

對(duì)一個(gè)join如果能在查詢(xún)端提早過(guò)濾不必要數(shù)據(jù)，可減少開(kāi)銷(xiāo)

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

2.7 小結(jié)

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

3、CBO（Cost-based optimizer）

3.1 CBO-概念

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

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

△算子代價(jià):CPU，內(nèi)存，磁盤(pán)IO，網(wǎng)絡(luò)I/O等代價(jià)

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

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

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

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

推導(dǎo)統(tǒng)計(jì)信息

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

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

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

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

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

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

動(dòng)態(tài)采樣：

SELECT count(*) FROM table_name

3.2.2 CBO-統(tǒng)計(jì)信息推導(dǎo)規(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í)行計(jì)劃枚舉

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

3.4 CBO-小結(jié)

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

4、總結(jié)

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

三、 社區(qū)開(kāi)源實(shí)踐

1、Apache Calcite概覽

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

1.1 Calcite RBO

HepPlanner

• 優(yōu)化規(guī)則(Rule)
  • Pattern :匹配表達(dá)式子樹(shù)
  • 等價(jià)變換:得到新的表達(dá)式
• 內(nèi)置有100+優(yōu)化規(guī)則
• 四種匹配規(guī)則
  • ARBITRARY/DEPTH FIRST :深度優(yōu)先
  • TOP DOWN :拓?fù)漤樞?/li>
  • BOTTOM_ UP :與TOP_ DOWN相反
• 遍歷所有的rule ,直到?jīng)]有rule可以被觸發(fā)
• 優(yōu)化速度快,實(shí)現(xiàn)簡(jiǎn)單,但是不保證最優(yōu)

1.2 Calcite CBO

VolcanoPlanner

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

1.3 小結(jié)

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

四、 前沿趨勢(shì)

1、AI4DB

• 自配置
  • 智能調(diào)參( OtterTune , QTune )
  • 負(fù)載預(yù)測(cè)/調(diào)度
• 自診斷和自愈合:錯(cuò)誤恢復(fù)和遷移
• 自?xún)?yōu)化:
  • 統(tǒng)計(jì)信息估計(jì)( Learned cardinalities )
  • 代價(jià)估計(jì)
  • 學(xué)習(xí)型優(yōu)化器( IBM DB2 LEQ )
  • 索引/視圖推薦

2、DB4AI

• 內(nèi)嵌人工智能算法( MLSQL,SOLFlow )
• 內(nèi)嵌機(jī)器學(xué)習(xí)框架( SparkML，Alink,dl-on-fink )

3、總結(jié)

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

五、 大總結(jié)

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

最新評(píng)論