[[436755]]

本文轉(zhuǎn)載自微信公眾號「數(shù)據(jù)和云」，作者數(shù)據(jù)和云。轉(zhuǎn)載本文請聯(lián)系數(shù)據(jù)和云公眾號。

數(shù)據(jù)庫的SQL引擎是數(shù)據(jù)庫重要的子系統(tǒng)之一，它對上負責(zé)承接應(yīng)用程序發(fā)送過來的SQL語句，對下則負責(zé)指揮執(zhí)行器運行執(zhí)行計劃。其中優(yōu)化器作為SQL引擎中最重要、最復(fù)雜的模塊，被稱為數(shù)據(jù)庫的“大腦”，優(yōu)化器產(chǎn)生的執(zhí)行計劃的優(yōu)劣直接決定數(shù)據(jù)庫的性能。

SQL引擎概覽

SQL引擎是數(shù)據(jù)庫系統(tǒng)重要組成部分，它的主要職責(zé)是負責(zé)將應(yīng)用程序輸入的SQL在當前負載場景下生成高效的執(zhí)行計劃，在SQL的高效執(zhí)行上扮演重要角色。SQL在SQL引擎里執(zhí)行過程，如圖7-1所示。

圖1 SQL執(zhí)行流程

從圖7-1中可以看出，應(yīng)用程序的SQL需要經(jīng)過SQL解析生成邏輯執(zhí)行計劃、經(jīng)過查詢優(yōu)化生成物理執(zhí)行計劃，然后將物理執(zhí)行計劃轉(zhuǎn)交給查詢執(zhí)行引擎做物理算子的執(zhí)行操作。

SQL解析通常包含詞法分析、語法分析、語義分析幾個子模塊。SQL語言是介于關(guān)系演算和關(guān)系代數(shù)之間一種描述性語言，它吸取了關(guān)系代數(shù)中一部分邏輯算子的描述，而放棄了關(guān)系代數(shù)中“過程化”的部分，SQL解析主要的作用就是將一個SQL語句編譯成為一個由關(guān)系算子組成的邏輯執(zhí)行計劃。

描述語言的特點是規(guī)定了需要獲取的“WHAT”，而不關(guān)心“HOW”，也就是只關(guān)注結(jié)果而不關(guān)注過程，因此SQL語言描述性的特點導(dǎo)致查詢優(yōu)化在數(shù)據(jù)庫管理系統(tǒng)中具有非常重要的作用。

查詢重寫則是在邏輯執(zhí)行計劃的基礎(chǔ)上進行等價的關(guān)系代數(shù)變換，這種優(yōu)化也可以稱為代數(shù)優(yōu)化，雖然兩個關(guān)系代數(shù)式獲得的結(jié)果完全相同，但是它們的執(zhí)行代價卻可能有很大的差異，這就構(gòu)成了查詢重寫優(yōu)化的基礎(chǔ)。

在早期的數(shù)據(jù)庫管理系統(tǒng)中，通常采用基于啟發(fā)式規(guī)則的方法來生成最優(yōu)的物理執(zhí)行計劃，但是這種基于規(guī)則的優(yōu)化的靈活度不夠，常常導(dǎo)致產(chǎn)生一些次優(yōu)的執(zhí)行計劃，而代價估算的引入，則從根本上解決了基于規(guī)則優(yōu)化的不足。

基于代價的優(yōu)化器一方面生成“候選”的物理執(zhí)行路徑，另一方面對這些執(zhí)行路徑計算它們的執(zhí)行代價，這樣就建立了執(zhí)行路徑的篩選標準，從而能夠通過比較代價而獲得最優(yōu)的物理執(zhí)行計劃。

SQL解析

SQL語句在數(shù)據(jù)庫管理系統(tǒng)中的編譯過程符合編譯器實現(xiàn)的常規(guī)過程，需要進行詞法分析、語法分析和語義分析。

§ 詞法分析：從查詢語句中識別出系統(tǒng)支持的關(guān)鍵字、標識符、操作符、終結(jié)符等，每個詞確定自己固有的詞性。

§ 語法分析：根據(jù)SQL語言的標準定義語法規(guī)則，使用詞法分析中產(chǎn)生的詞去匹配語法規(guī)則，如果一個SQL語句能夠匹配一個語法規(guī)則，則生成對應(yīng)的抽象語法樹(Abstract Syntax Tree，AST)。

§ 語義分析：對語法樹(AST)進行有效性檢查，檢查語法樹中對應(yīng)的表、列、函數(shù)、表達式是否有對應(yīng)的元數(shù)據(jù)，將抽象語法樹轉(zhuǎn)換為邏輯執(zhí)行計劃(關(guān)系代數(shù)表達式)。

在SQL語言標準中，確定了SQL語言的關(guān)鍵字以及語法規(guī)則信息，SQL解析器在做詞法分析的過程中會將一個SQL語句根據(jù)關(guān)鍵字信息以及間隔信息劃分為獨立的原子單位，每個單位以一個詞的方式展現(xiàn)，例如有SQL語句：

SELECT w_name FROM warehouse WHERE w_no = 1; 

可以劃分的關(guān)鍵字、標識符、操作符、常量等原子單位，如表7-1所示。

語法分析會根據(jù)詞法分析獲得的詞來匹配語法規(guī)則，最終生成一個抽象語法樹(AST)，每個詞作為語法樹的葉子結(jié)點出現(xiàn)，如圖7-2所示。

圖2 抽象語法樹

抽象語法樹表達的語義還僅僅限制在能夠保證應(yīng)用的SQL語句符合SQL標準的規(guī)范，但是對于SQL語句的內(nèi)在含義還需要做有效性的檢查。

§ 檢查關(guān)系的使用：FROM子句中出現(xiàn)的關(guān)系必須是該查詢對應(yīng)模式中的關(guān)系或視圖。

§ 檢查與解析屬性的使用：在SELECT句中或者WHERE子句中出現(xiàn)的各個屬性必須是FROM子句中某個關(guān)系或視圖的屬性。

§ 檢查數(shù)據(jù)類型：所有屬性的數(shù)據(jù)類型必須是匹配的。

在有效性檢查的同時，語義分析的過程還是有效性語義綁定(Bind)的過程，通過語義分析的檢查，抽象語法樹就轉(zhuǎn)換成一個邏輯執(zhí)行計劃，邏輯執(zhí)行計劃可以通過關(guān)系代數(shù)表達式的形式來表現(xiàn)，如圖7-3所示。

圖3 關(guān)系代數(shù)表達式