歡迎閱讀新一期的數據庫內核雜談！上一期內容(表的JOIN)中，我們挖了一個坑：在大部分情況下，HashJoin都是表現最優(yōu)的，那為什么還需要去支持其他Join比如SortMergeJoin或者NestLoopJoin的算子實現呢？因為不同表的大小，是否有索引支持，以及查詢語句是否對某些column需要排序都會對執(zhí)行算子產生影響，從而進一步影響執(zhí)行時間。就是只看HashJoin，hash表到底是對表A來建，還是對表B來建，也會造成非常大的差別(通常，我們選取數據量小的表來做Hash表，這能使得需要用到的內存更少，更小概率需要借助外部Hash表來進行分批次的join)。而擁有最終決定權的，就是我們今天要聊的主角：數據庫優(yōu)化器(Query Optimizer)。

首先來談談為什么叫優(yōu)化器。它優(yōu)化的又是什么呢？最常見的優(yōu)化指標就是查詢語句的運行時間，譬如上述例子中的HashJoin，優(yōu)化器選擇用數據量小的表來建Hash表，運行時間就比選擇用大的表要快。那我們再問深一層，為什么對應一個查詢語句，可以優(yōu)化執(zhí)行時間？歸根到底是因為SQL是一種declarative language(聲明式語言)，它只是告知了數據庫系統(tǒng)，它希望數據以什么形式返回，但并沒有告訴系統(tǒng)，要怎么去一步一步執(zhí)行算子來得到最終結果。這和我們通常使用的編程語言是有所不同的。比如用C語言寫一個冒泡排序和快速排序，雖然最終排序結果一樣，但是快速排序確實只用到了更少的比較和交換，所以性能比冒泡排序要快。因為算法交代了應該如何去排序(當然，編譯器還是可以進一步地來優(yōu)化代碼，比如function-inline，dead code elimination等等)。這就給了優(yōu)化器變魔術的空間。

除了時間，還有什么可以優(yōu)化的維度呢？比如計算資源，一個查詢語句，需要發(fā)生多少次IO，使用多少內存，總共運行多少個CPU cycle，耗費了多少電量，等等。雖然，絕大部分情況下，這些資源都是正比于運行時間。再如，對于一個高并發(fā)的數據庫系統(tǒng)，單個語句的運行時間可能并不是最好的優(yōu)化指標，優(yōu)化整體的吞吐量才是王道：相較于讓每個語句都能在5秒內完成，可能更希望每10秒能運行完100個語句。

今天的內容我們主要圍繞如何優(yōu)化運行時間，因為對于單個語句優(yōu)化執(zhí)行時間，就已經是NP-HARD復雜度的問題了。不知大家是否還有印象，在討論數據庫執(zhí)行模式的那章，我們簡單介紹了整個數據庫內核的架構，其中就談到了優(yōu)化器：優(yōu)化器的輸入是數據庫的元數據以及語義綁定的語法樹，輸出是最終的物理算子的執(zhí)行計劃。那它內部又是怎么得到最終的物理算子的執(zhí)行計劃的呢？我們一步一步來看。

Query Rewrite (語句重寫）

優(yōu)化器的第一個階段叫做Query Rewrite(語句重寫)。這個階段，主要是對原來的語法樹進行等價語義的重寫，通常是根據預先定義好的規(guī)則來進行重寫，優(yōu)化掉一些無效或者無意義的操作。換句話說，有時候程序員寫的SQL通常是結果導向的，并不專門針對執(zhí)行去優(yōu)化，而且，很多時候還會有意無意引入無意義的操作。你可能會納悶，怎么會呢？一起來看一些簡單的示例。

SELECT

????class.name AS class_name,

????student.name AS student_name,?

????student.id AS student_id

FROM

????class, student

WHERE? ?

????class.id = student.class_id AND? ?

????student.name = 'ZhangSan';

上述語句返回這個學校所有叫ZhangSan的學生的姓名，學號，以及班級。那這樣一個語句轉換成語法樹應該是下面這個形式：

Logical Operator Tree

這里我用了簡單的關系型代數模型符號來表達語法樹的邏輯算子，只用到了最基本的projection，equality join，和filtering operator。看了這個語法樹，你可能覺得，沒毛病啊，語義正確。但是，如果直接把這個語法樹轉換成物理算子的執(zhí)行計劃，就會發(fā)現可以優(yōu)化的地方了。我們自下而上地來看。首先執(zhí)行計劃要求掃描全表class和表student，然后對其進行Join，join條件是class.id = student.class_id。join完之后，對于tuple進行filter，filter條件是student.name = 'ZhangSan'。最后，對于filter后的tuple，進行projection，只有3個column作為輸出class.name, student.name 和 student.id。

可能看完了這個執(zhí)行計劃的流程，讀者依然會說，沒毛病啊。其實不然。比如，對于class表，總共只用到了兩個column:id 和 name，因此我們可以在讀取表的時候直接進行projection。一是，相對于把整個表全部讀取放進內存中，只讀取2個column所需的內存要少很多。另外，如果考慮到使用列存形式存儲數據，只讀兩個column和讀取全部的column速度上也快很多。這里，我們引出了第一個語句重寫的規(guī)則：Projections push down。通過把用到的哪些column往下推送直到葉節(jié)點的table scan，可以減少掃描后數據的大小，同時也可以提升掃描速度。同樣的，我們也可以對學生表的讀取進行優(yōu)化，學生表只用到了id, class_id, 和name column。更進一步的是，對于學生表，除了projections push down，我們還能把filter predicates也往下推送。因為最終的結果里面只需要姓名為'ZhangSan'的學生，與其把所有的學生信息都讀取進來和class表進行join，我們可以先filter掉其他的學生，使得join的數據大大減少(假設叫'ZhangSan'的同學應該不會很多)。這便是我們提到的第二個重寫規(guī)則：Predicates push down。通過把filter predicates往下推送，以減少后續(xù)操作的數據量。經過這兩步的改寫，新的語法樹變成了如下這個形式：

new logical operator tree with projections/predicates push down

通過上述兩個重寫規(guī)則，我們使得自下而上讀取的數據量減小到最少，繼而減少后續(xù)處理的數據量，以此來優(yōu)化執(zhí)行時間。并且，這些重寫規(guī)則，屬于有百利而無一弊，只要規(guī)則允許，就應該進行重寫。有讀者可能有疑問了，這些語句重寫能帶來多少運行速度的提高呢？這完全取決于表的大小，數據分布和查詢語句。試想，如果把student表換做是一個有萬億數據的超級大表，通過Predicates push down，可能最后只保留了幾行數據。并且，由于Predicates push down，優(yōu)化器可能會選擇使用IndexScan而非全表掃描(如果對應的Predicate column有建立相應的index)，這進一步極大提高了表讀取速度，此為后話，暫且不表。

這些重寫規(guī)則都是提前實現好了，在對語法樹進行分析的時候，如果滿足了某類觸發(fā)條件，就會加載相應的重寫規(guī)則。下面，我們再來看一些常見的重寫規(guī)則。查詢語句如下圖所示：

SELECT * FROM super_large_table WHERE 1 = 0;

對SQL比較熟悉的讀者可能一眼就看出來了，由于where condition的predicate始終為false，所以無論這個表有多大，最終結果都為空集。通過引入重寫規(guī)則 Impossible/Unnecessary Predicates: 計算出Predicates的值，如果值衡為false，直接返回空集；如果值衡為true，直接去掉predicates。相對應的語法樹發(fā)生如下變化：

original logical operator tree

重寫后變?yōu)?/p>

new logical operator tree

這類規(guī)則有點類似傳統(tǒng)編譯器里的constant folding/propagation和dead code elimination的優(yōu)化策略：試圖在編譯階段就確定predicates的值，以此來簡化expression。雖然上述的例子很簡單，但有些查詢語句的predicates會很復雜，優(yōu)化器是否足夠"聰明"作出優(yōu)化，是考驗優(yōu)化器的一個標準。 筆者曾經對不同的數據庫進行過比較，每一款優(yōu)化器支持的語句重寫規(guī)則都不同，正所謂沒有比較就沒有傷害！有時候會覺得，某某優(yōu)化器怎么那么“笨”，連這個都看不出來。曾有個前輩這樣說過，那些商用數據庫之所以貴，就貴在優(yōu)化器的聰明上。最后，我們一起來看幾個并不是非常顯而易見的重寫規(guī)則。

示例查詢語句1:

SELECT * FROM table1

WHERE

????val BETWEEN 1 AND 50? ?

????OR val BETWEEN 45 AND 100;

通過Merge predicates重寫規(guī)則，可以改寫成如下(介于查詢語句也能很好地體現重寫后的效果，直接上SQL)：

SELECT * FROM table1

WHERE val BETWEEN 1 AND 100;

優(yōu)化器把多個predicates合并到了一起。

示例查詢語句2:

SELECT * FROM table1 AS t1

WHERE EXISTS (

? ? SELECT * FROM table1 AS t2

? ? WHERE t1.id = t2.id

);

這個就有點復雜啦，如果優(yōu)化器能察覺到EXISTS中的查詢條件其實是table1的self join，這樣condition就總是為true，所以可以被重寫為：

SELECT * FROM table1;

再來看一個類似的示例語句3:

SELECT t1.*

FROM

? ? table1 AS t1

JOIN

? ? table1 AS t2

ON t1.id = t2.id;

因為依然是table1的self join，所以通過join elimination重寫規(guī)則，可以直接改寫為如下：

SELECT * FROM table1;

最后，來看一個不一樣地去掉無意義語句的重寫。示例語句如下：

SELECT

????id, name, class_id

FROM (

? ? SELECT * FROM students

? ? ORDER BY id

) t

ORDER BY class_id;

不知道讀者是否看出了這句語句中的無效操作，即inner語句中的ORDER BY id。因為在outter語句中已經申明了以class_id排序的要求，內部的排序即可視為無效語句。聰明的優(yōu)化器可以直接將其改寫成：

SELECT

? ? id, name, class_id

FROM

? ? students

ORDER BY

? ? class_id;

類似的語句重寫規(guī)則還有很多很多，優(yōu)化器也會根據查詢語句的側重點，來實現特定的語句重寫。留個問題給大家，還能想到哪些顯而易見的語句重寫規(guī)則嗎？

總結

總結一下，優(yōu)化器引入了事先編寫好的語句重寫規(guī)則，在編譯語法樹的過程中，通過觸發(fā)規(guī)則來加載語句重寫規(guī)則，從而簡化語句，去掉無意義的語句，以及通過Predicates push down, Projectsions push down來優(yōu)化數據讀取。這些規(guī)則雖然有時候能大大簡化語句，提升執(zhí)行速度，但對于復雜的多表查詢語句，顯然是不夠的。 比如下面這個示例語句：

SELECT

? ? t1.a,

? ? t2.b,

? ? t3.c,

? ? ...

? ? tn.x

FROM

? ? table1 AS t1,

? ? table2 AS t2,

? ? table3 AS t3,

? ? ...

? ? tablen AS tn

WHERE

? ? t1.a = t2.aa AND

? ? t2.b = t3.cc OR

? ? ...;

上述這句語句的復雜度在于，有n個表同時join在一起。對于表和表的Join relation，是可傳遞且可交換的。即：

table1 JOIN table2 = table2 JOIN table1

(table1 JOIN table2) JOIN table3 = table1 JOIN (table2 JOIN table3)

那上述n個表的join，表達成兩兩join的關系后，一共有多少種可能性呢？ 我這里直接給出結果，大致會有4^n(4的n次方)種可能。要在那么多種可能中找到最優(yōu)的join ordering，已經是NP-HARD的問題。那優(yōu)化器又是如何在巨大的搜索空間中，找出最優(yōu)解呢？下一期，接著聊優(yōu)化器。