編者按：本文以邏輯優(yōu)化角度，對PostgreSQL數(shù)據(jù)庫的查詢優(yōu)化器的實現(xiàn)進行詳細分析。為了讓大家通過通俗易懂的方式更好地理解消化其中的晦澀概念，作者別出心裁地撰寫成趣味故事，雖然篇幅稍長，但細細品讀定將收獲匪淺。

查詢優(yōu)化器的基本原理

小明考上了北清大學的計算機研究生，今年學校開了數(shù)據(jù)庫原理的課程，小明對查詢優(yōu)化的內容不是很理解，雖然已經(jīng)使出了洪荒之力，仍覺得部分原理有些晦澀難懂，于是打算問一下自己的哥哥大明。

大明是一位資深的數(shù)據(jù)庫內核開發(fā)老碼農，對Greenplum/HAWQ數(shù)據(jù)庫有多年的內核開發(fā)經(jīng)驗，眼鏡片上的圈圈像年輪一樣見證著大明十多年的從業(yè)經(jīng)歷。知道小明要來問問題，大明有點緊張，雖然自己做數(shù)據(jù)庫內核好多年了，但是對優(yōu)化器研究不甚深入，如果被小明這樣的小菜鳥問倒就尷尬了，于是大明只好臨時抱佛腳，拿出了好多年不看的《數(shù)據(jù)庫系統(tǒng)實現(xiàn)》啃了起來。

小明提出的第一個問題是：“為什么數(shù)據(jù)庫要進行查詢優(yōu)化？”

大明推了推鼻梁上的眼鏡，慢條斯理地說：“不止是數(shù)據(jù)庫要進行優(yōu)化，基本上所有的編程語言在編譯的時候都會優(yōu)化，比如你在編譯C語言的時候，可以通過編譯選項-o來指定進行哪個級別的優(yōu)化，但是查詢數(shù)據(jù)庫的查詢優(yōu)化和C語言的優(yōu)化還有些區(qū)別。”

“有哪些區(qū)別呢？”大明停頓了一下，凝視著小明，仿佛期望小明能給出答案，或是給小明騰挪出足夠思考的空間。三五秒之后大明又自問自答道：“C語言是過程化語言，你已經(jīng)指定好了需要執(zhí)行的每一個步驟，但是SQL是描述性語言，它只指定了WHAT，而沒有指定HOW，這樣它的優(yōu)化空間就大了，你說是不是？”

小明點了點頭說：“對，也就是說條條大路通羅馬，它比過程語言的選擇更多，是不是這樣？”大明笑道：“孺子可教也。雖然我們知道它的優(yōu)化空間大，但具體如何優(yōu)化呢？”

說著大明將身子向沙發(fā)一靠，翹上二郎腿繼續(xù)說：“通常來說分成兩個層面，一個是基于規(guī)則的優(yōu)化，另一個是基于代價的優(yōu)化?；谝?guī)則的優(yōu)化也可以叫邏輯優(yōu)化或者規(guī)則優(yōu)化，基于代價的優(yōu)化也可以叫物理優(yōu)化或者代價優(yōu)化。”

“為什么要進行這樣的區(qū)分呢？優(yōu)化就優(yōu)化嘛，何必還分什么規(guī)則和代價呢？”，小明問道。

“分層不分層不是重點，有些優(yōu)化器層次分得清楚點，有些優(yōu)化器層次分得就不那么清楚，都只是優(yōu)化手段而已。”大明感到有點心虛，再這么問下去恐怕要被問住，于是試圖引開話題：“我們繼續(xù)說說SQL語言吧，我們說它是一種介于關系演算和關系代數(shù)之間的語言，關系演算和關系代數(shù)你看過吧？”

小明想了想，好像上課時老師說過關系代數(shù)，但沒有說關系演算，于是說：“接觸過一點，但不是特別明白。”大明得意地說：“關系演算是純描述性的語言，而關系代數(shù)呢，則包含了一些基本的關系操作，SQL主要借鑒的是關系演算，也包含了關系代數(shù)的一部分特點。”

大明看小明有點懵，頓了一下繼續(xù)說道：“上課的時候老師有沒有說過關系代數(shù)的基本操作？”小明想了一下說：“好像說了，有投影、選擇、連接、交集、差集這幾個。”大明點點頭說：“對的，還可以有一個叫重命名的，一共6個基本操作，另外結合實際應用在這些基本操作之上又擴展出了外連接、半連接、聚集操作、分組操作等等。”

大明繼續(xù)說道：“SQL語句雖然是描述性的，但是我們可以把它轉化成一個關系代數(shù)表達式，而關系代數(shù)中呢，又有一些等價的規(guī)則，這樣我們就能結合這些等價規(guī)則對關系代數(shù)表達式進行等價的轉換。”

“進行等價轉換的目的是找到性能更好的代數(shù)表達式吧？”小明問。

“對，就是這樣。”大明投去贊許的目光。

“那么如何確定等價變換之后的表達式就能變得比之前性能更好呢？或者說為什么要進行這樣的等價變換，而不是使用原來的表達式呢？”

大明愣了一下，仿佛沒有想到小明會提出這樣的問題，但是基于自己多年的忽悠經(jīng)驗，他定了定神，回答道：“這既有經(jīng)驗的成分，也有量化的考慮。例如將選擇操作下推，就能優(yōu)先過濾數(shù)據(jù)，那么表達式的上層計算結點就能降低計算量，因此很容易可以知道是能降低代價的。再例如我們通常會對相關的子查詢進行提升，這是因為如果不提升這種子查詢，那么它執(zhí)行的時候就會產生一個嵌套循環(huán)，這種嵌套循環(huán)的執(zhí)行代價是O(N^2)，這種復雜度已經(jīng)是最壞的情況了，提升上來至少不會比它差，因此提升上來是有價值的。”大明心里對自己的臨危不亂暗暗點了個贊。

大明看小明沒有提問，繼續(xù)說道：“這些基于關系代數(shù)等價規(guī)則做等價變換的優(yōu)化，就是基于規(guī)則的優(yōu)化，當然數(shù)據(jù)庫本身也會結合實際的經(jīng)驗，產生一些優(yōu)化規(guī)則，比如外連接消除，因為外連接優(yōu)化起來不太方便，如果能把它消除掉，我們就有了更大的優(yōu)化空間，這些統(tǒng)統(tǒng)都是基于規(guī)則的優(yōu)化。同時這些都是建立在邏輯操作符上的優(yōu)化，這也是為什么基于規(guī)則的優(yōu)化也叫做邏輯優(yōu)化。”

小明想了想，自己好像對邏輯操作符不太理解，連忙問：“邏輯操作符是啥？既然有物理優(yōu)化，難道還有物理操作符嗎？”

大明伸了個懶腰繼續(xù)說：“比如說吧，你在SQL語句里寫上了兩個表要做一個左外連接，那么數(shù)據(jù)庫怎么來做這個左外連接呢？”

小明一頭霧水地搖搖頭，向大明投出了期待的眼神。

大明繼續(xù)說道：“數(shù)據(jù)庫說我也不知道啊，你說的左外連接意思我懂，但我也不知道怎么實現(xiàn)??？你需要告訴我實現(xiàn)方法啊，因此優(yōu)化器還承擔了一個任務，就是告訴執(zhí)行器，怎么來實現(xiàn)一個左外連接。”

“數(shù)據(jù)庫有哪些方法來實現(xiàn)一個左外連接呢？它可以用嵌套循環(huán)連接、哈希連接、歸并連接等等，注意了，重要的事情說三遍，你看內連接、外連接是連接操作，嵌套循環(huán)連接、歸并連接等也叫連接，但內連接、外連接這些就是邏輯操作符，而嵌套循環(huán)連接、歸并連接這些就是物理操作符。所以你說對了，物理優(yōu)化就是建立在物理操作符上的優(yōu)化。”

大明：“從北京去上海，你說你怎么去？”

小明：“坐高鐵啊，又快又方便。”

大明：“坐高鐵先去廣州再倒車到上海行不？”

小明：“有點扎心了，這不是吃飽了撐的嗎？”

大明：“為什么？”

小明：“很明顯，我有直達的高鐵，既省時間又省錢，先去廣州再倒車？我腦子瓦特了？！”

大明笑了笑說：“不知不覺之間，你的大腦就建立了一個代價模型，那就是性價比，優(yōu)化器作為數(shù)據(jù)庫的大腦，也需要建立代價模型，對物理操作符計算代價，然后篩選出最優(yōu)的物理操作符來，因此基于代價的優(yōu)化是建立在物理操作符上的優(yōu)化，所以也叫物理優(yōu)化。”

小明似乎懂了：“公司派我去上海出差就是一個邏輯操作符，它和我們寫一個SQL語句要求數(shù)據(jù)庫對兩個表做左外連接類似，而去上海的實際路徑有很多種，這些就像是物理操作符，我們對這些實際的物理路徑計算代價之后，就可以選出來最好的路徑了。”

大明掏出手機，分別打開了兩個不同的地圖APP，輸入了北京到上海的信息，然后拿給小明看。小明發(fā)現(xiàn)兩個APP給出的最優(yōu)路徑是不一樣的。小明若有所思地說：“看來代價模型很重要，代價模型是不是準確決定了最優(yōu)路徑選擇得是否準確？”

大明一拍大腿，笑著說：“太對了，所以我作為一個數(shù)據(jù)庫內核的資深開發(fā)人員，需要不斷地調整優(yōu)化器的代價模型，以期望獲得一個相對穩(wěn)定的代價模型，不過仍然是任重道遠啊。”

關于語法樹

聽了大明對查詢優(yōu)化器基本原理的講解，小明在學校的數(shù)據(jù)庫原理課堂上順風順水，每天吃飯睡覺打豆豆，日子過得非常悠哉。不過眼看就到了數(shù)據(jù)庫原理實踐課，老師給出的題目是分析一個數(shù)據(jù)庫的某一模塊的實現(xiàn)，小明千挑萬選，終于選定了要分析PostgreSQL數(shù)據(jù)庫的查詢優(yōu)化器的實現(xiàn)，因為據(jù)說PostgreSQL數(shù)據(jù)庫的查詢優(yōu)化器層（相）次（當）清（復）楚（雜），具有教科書級的示范作用。

可是當小明下載了PostgreSQL數(shù)據(jù)庫的源代碼，頓時就懵圈了，雖然平時理論說得天花亂墜，但到了實踐的時候卻發(fā)現(xiàn)，理論和實際對應不上。小明深深陷入到代碼的細節(jié)里不可自拔，查閱了好多資料，結果是讀破書萬卷，下筆如有錘，一點進展都沒有。于是小明又想到了與PostgreSQL有著不解之緣的大明，想必他一定能站得更高，看得更遠，于是小明蹬著自己的寶馬向大明駛去。

大明看著大汗淋漓找上門的小明，意味深長地說：“PostgreSQL的查詢優(yōu)化器功能比較多，恐怕一次說不完，我們分成幾次來說清楚吧。”

小明說：“的確是的，我在看查詢優(yōu)化器代碼的時候覺得無從下手，雖然一些理論學過了，但不知道代碼和理論如何對應，而且還有一些優(yōu)化規(guī)則好像我們講數(shù)據(jù)庫原理的時候沒有涉及到，畢竟理論和實踐之間還是有一些差距。”

大明打開電腦，調出了PostgreSQL的代碼說：“我們先來看一下PostgreSQL一個查詢執(zhí)行的基本流程。”，然后調出了一張圖。 

“這張圖是我自己畫的，這種圖已經(jīng)成了優(yōu)化器培訓開篇的必備圖了，我們有必要借助這張圖來看一下PostgreSQL源碼的大體結構，了解查詢優(yōu)化器所處的位置。”

大明一邊指點著電腦屏幕，一邊繼續(xù)說：“我們要執(zhí)行一條SQL語句，首先會進行詞法分析，也就是說把SQL語句做一個分割，分成很多小段段……”小明連忙說：“我們在學編譯原理的時候老師說了，分成的小段段可以是關鍵字、標識符、常量、運算符和邊界符，是不是分詞之后就會給這些小段段賦予上這些語義？”

“對的！看來你對編譯原理的第一章很熟悉嘛。”大明笑著說。

“當然，我最擅長寫Hello World。”

“好吧，Let’s繼續(xù)，PostgreSQL的分詞是在scan.l文件中完成的，它可能分得更細致一些，比如常量它就分成了SCONST、FCONST、ICONST等等，不過基本的原理是一樣的。進行分詞并且給每個單詞以語義之后，就可以去匹配gram.y里的語法規(guī)則了，在gram.y文件里定義了所有的SQL語言的語法規(guī)則，我們的查詢經(jīng)過匹配之后，最終形成了一顆語法樹。”

“語法樹？我還聽過什么查詢樹、計劃樹，這些樹要怎么區(qū)分呢？”

“一個查詢語句在不同的階段，生成的樹是不同的，這些樹的順序應該是先生成語法樹，然后得到查詢樹，最終得到計劃樹，計劃樹就是我們說的執(zhí)行計劃。”

“那為什么要做這些轉換呢？”小明不解地問。

“我們通過詞法分析、語法分析獲得了語法樹，但這時的語法樹還和SQL語句有很緊密的關系，比如我們在語法樹中保存的還是一個表的名字，一個列的名字，但實際上在PostgreSQL數(shù)據(jù)庫數(shù)據(jù)庫中，有很多系統(tǒng)表，比如PG_CLASS用來將表保存成數(shù)據(jù)庫的內部結構，當我們創(chuàng)建一個表的時候，會在PG_CLASS、PG_ATTRIBUTE等等系統(tǒng)表里增加新的元數(shù)據(jù)，我們要用這些元數(shù)據(jù)的信息取代語法樹中表的名字、列的名字等等。”

小明想了想，說：“這個取代的過程就是語義分析？這樣就把語法樹轉換成了查詢樹，而查詢樹是使用元數(shù)據(jù)來描述的，所以我們在數(shù)據(jù)庫內核中使用它就更方便了？”

“是的。”大明肯定地說。“不過語義分析還做了一個工作，那就是檢查工作，在語法樹是通過分析SQL語句獲得的，它還不知道一個表是不是存在，一個列是不是存在，這個轉換的過程，也是一個檢查的過程。”大明停頓了一下，似乎是做了一下思考，然后拿出一張紙，在上邊畫了起來。

 

“這是SQL語句SELECT st.sname, c.cname, sc.degree FROM STUDENT st , COURSE c INNER JOIN SCORE sc ON c.cno = sc.cno WHERE st.sno = sc.sno對應的簡版查詢樹，看著復雜嗎？”大明邊畫邊問。小明心中翻騰出千萬只泥馬，他似乎感覺到自己選擇查詢優(yōu)化作為數(shù)據(jù)庫原理課的實踐作業(yè)是一個錯誤的決定，現(xiàn)在自己已經(jīng)受到了沖動的懲罰，這個圖里的大部分內容他都不知道是什么東西。

看著小明迷離的眼神，大明有點發(fā)慌，說：“我們現(xiàn)在還不用深入到代碼層面，你可以忽略這張圖，現(xiàn)在可以把查詢樹認為是一個關系代數(shù)表達式。”

小明定了定神，問道：“關系代數(shù)表達式？上次我問你查詢優(yōu)化原理的時候你是不是說基于規(guī)則的優(yōu)化就是使用關系代數(shù)的等價規(guī)則對關系代數(shù)表達式進行等價的變換，所以查詢優(yōu)化器的工作就是用這個查詢樹做等價變換？”

“恭喜你，答對了。”大明暗暗贊許小明的理解能力和記憶力，繼續(xù)說：“查詢樹就是查詢優(yōu)化器的輸入，經(jīng)過邏輯優(yōu)化和物理優(yōu)化，最終產生一顆最優(yōu)的計劃樹，而我們要做的就是看看查詢優(yōu)化器是如何產生這棵最優(yōu)的計劃樹的。”

關于子連接

午飯過后，大明愜意地抽起了中華煙，小明看著他好奇地問：“咱爺爺抽的是在農村種的煙葉，自給自足還省錢，你也干脆回農村種煙葉吧，你這中華煙和農村的自己卷的煙葉，能有什么區(qū)別？”

大明看電視劇正看得起勁，心不在焉地說：“自己種的煙葉直接用報紙卷了抽，沒有過濾嘴，會吸入有害顆粒物，而且煙葉的味道也不如現(xiàn)在改進的香煙。”說到這里大明好像想到了什么，繼續(xù)說：“這就像是查詢優(yōu)化器的邏輯優(yōu)化，查詢樹輸入之后，需要進行持續(xù)的改進。無論是自己用報紙卷的煙，還是在超市買的成品煙，都是香煙，但是通過改進之后，香煙的毒害作用更低、香型更豐富了，邏輯優(yōu)化也是這個道理，通過改進查詢樹，能夠得到一個更‘好’的查詢樹。”

“哦，那邏輯優(yōu)化是如何在已有的查詢樹上增加香型的呢？”

大明繼續(xù)說：“我總結，PostgreSQL在邏輯優(yōu)化階段有這么幾個重要的優(yōu)化：子查詢&子連接提升、表達式預處理、外連接消除、謂詞下推、連接順序交換、等價類推理。”大明又抽了一口煙，接著說：“從代碼邏輯上來看，我們還可以把子查詢&子連接提升、表達式預處理、外連接消除叫做邏輯重寫優(yōu)化，因為他們主要是對查詢樹進行改造，而后面的謂詞下推、連接順序交換、等價類推理則可以稱之為邏輯分解優(yōu)化，他們已經(jīng)把查詢樹蹂躪得不成樣子了，已經(jīng)到了看香煙不是香煙的地步了。”

“可是我們的數(shù)據(jù)庫原理課上并沒有說有邏輯重寫優(yōu)化和邏輯分解優(yōu)化啊。”

“嗯，是的，這是我根據(jù)PostgreSQL源代碼的特征自己總結的，不過它能比較形象地將現(xiàn)有的邏輯優(yōu)化區(qū)分開來，這樣就能更好地對邏輯優(yōu)化進行提煉、總結、分析。”大明想了一下覺得如果把所有的邏輯優(yōu)化規(guī)則都說完有點多，于是對小明說：“我們就從中挑選一兩個詳細說明吧，先從子查詢&子連接的提升開始說起。”

“那……子查詢和子連接有什么區(qū)別呢？我們在數(shù)據(jù)庫原理課里只講了子查詢，沒有子連接的概念，這該怎么解釋呢？”小明不解地問。

大明拿出了《數(shù)據(jù)庫系統(tǒng)實現(xiàn)》這本書并翻開了對應章節(jié)，說道：“通常數(shù)據(jù)庫原理書籍中說的子查詢，指的是PostgreSQL中的子連接。你看，書里說的是從條件中去除子查詢，但是PostgreSQL把這種情況歸類為子連接。”

“那在PostgreSQL是如何區(qū)分子查詢和子連接的呢？”大明自問自答道：“在實際應用中可以通過子句所處的位置來區(qū)分子連接和子查詢，出現(xiàn)在FROM關鍵字后的子句是子查詢語句，出現(xiàn)在WHERE/ON等約束條件中或投影中的子句是子連接語句。”說著大明快速地在電腦上打開了記事本，敲入了幾個SQL語句： 

SELECT * FROM STUDENT, (SELECT * FROM SCORE) as sc;  
SELECT (SELECT AVG(degree) FROM SCORE), sname FROM STUDENT;  
SELECT * FROM STUDENT WHERE EXISTS (SELECT A FROM SCORE WHERE SCORE.sno = STUDENT.sno); 

“這些SQL語句中哪個是子查詢？哪個是子連接？”

小明看了一下說：“1是子查詢，2和3是子連接，語句1里的子句出現(xiàn)在FROM后面，它是以‘表’的形式存在的，是子查詢，2和3的子句出現(xiàn)在投影和約束條件中，是以表達式的形式存在的，是子連接。”小明不但答對了問題，而且還對問題的答案做了擴展，大明調侃道：“腰間盤同學，坐下，你太突出了。”

大明繼續(xù)說道“從大的方向上分類，子查詢還可以分為相關子連接和非相關子連接，相關子連接是指在子查詢語句中引用了外層表的列屬性，這就導致外層表每獲得一個元組，子查詢就需要重新執(zhí)行一次；而非相關子查詢是指在子查詢語句是獨立的，和外層的表沒有直接的關聯(lián)，子查詢可以單獨執(zhí)行一次，外層表可以重復利用子查詢的執(zhí)行結果。”

“那么一定是相關子連接才會提升了，因為我記得你在說邏輯優(yōu)化原理的時候說過，相關子連接會產生‘嵌套循環(huán)’，這種情況的復雜度是O(N^2)，提升上來的復雜度肯定不會比O(N^2)差，所以提升是有價值的。”小明說道。

聽到這些，大明頓時碉堡了，道理雖然是這個道理，但是PostgreSQL偏偏不走尋常路，和自己之前說過的有些許差異，大明羞澀地說：“雖然話是這樣說，但PostgreSQL有點不同，PostgreSQL提升了兩種類型的子連接，一種是ANY類型的子連接，一種是EXISTS類型的子連接，對于ANY類型的子連接，只提升非相關子連接，而對于EXISTS類型的子連接，則只提升相關子連接。”

小明頓時想起了自己曾和同學說過相關子連接理論，當時把宿舍同學忽悠得五迷三道的，今天大明又說這可能是錯的，心里不太爽利，于是怒道：“那我和同學吹過的牛豈不是要成為笑柄？感覺受到了一萬點傷害……”

“小明同學別急”，大明安撫道：“雖然PostgreSQL對于ANY類型只提升非相關的子連接，但它仍然是只提升產生嵌套循環(huán)的那種子連接，你看看這個例子。”說著在電腦上又敲了一個SQL語句： 

SELECT * FROM STUDENT WHERE sno > ANY (SELECT sno from STUDENT); 

“這是一個ANY類型的非相關子連接，但請注意，在>前面的sno實際上產生了一個天然的相關性，這個天然的相關性就會產生嵌套循環(huán)，因此是需要提升的。我們再來看另一個語句。”大明把>前面的sno換成了一個常量： 

SELECT * FROM STUDENT WHERE 10 > ANY (SELECT sno from STUDENT); 

“這個SQL語句中的子連接就不會提升了，因為我們把sno換成了常量，父子之間的相關性被打破了，明白了嗎？”

小明點點頭，心里想：子連接是否提升取決于相關性，而這個相關性不只是體現(xiàn)在子句里，也體現(xiàn)在表達式里，也就是說只要能產生嵌套循環(huán)，那就有提升的必要啊，但是……小明靈機一動，問道：“那ANY類型的相關子連接也會產生嵌套循環(huán)啊，為什么不提升呢？”

大明說：“這可能有點歷史原因了，PostgreSQL提升ANY類型的子連接的方式和EXISTS類型的子連接的方式不同，他提升EXISTS類型的子連接的時候，是直接把子句中的表提上來做，形成一個SemiJoin，可是提升ANY類型的子連接時，是把整個子句提上來，和父語句中的表做SemiJoin，這時候這個子句就變成了一個子查詢，你看這個例子。”說著在電腦上敲了三個語句： 

SELECT * FROM TEST_A WHERE a > ANY (SELECT a FROM TEST_B WHERE TEST_A.b = TEST_B.b)；  
SELECT * FROM TEST_A, (SELECT a FROM TEST_B WHERE TEST_A.b = TEST_B.b) b WHERE TEST_A.a > b.a;  
SELECT * FROM TEST_A, LATERAL (SELECT a FROM TEST_B WHERE TEST_A.b = TEST_B.b) b WHERE TEST_A.a > b.a; 

“如果按照目前ANY類型子連接先提升成子查詢的方式，第1個語句提升之后會變成等價于第2個語句，而第2個語句本身是無法執(zhí)行的，在比較新版本的PostgreSQL上支持了LATERAL之后，只要在第2個語句上加上LATERAL，也就是變成第3個語句就能執(zhí)行了。”大明在屏幕上比劃著說。

小明問道：“那豈不是說，有了LATERAL之后，ANY類型的相關子連接也能提升了？”

大明說：“只能說有一部分ANY類型的相關子連接能夠提升了，比如我們上面的例1本質上就是能提升的，而且一些商業(yè)數(shù)據(jù)庫確實也對這種語句做了提升，但是PostgreSQL目前還沒有處理這種情況。”

小明打了個哈欠說：“實在是太累了，讓我們休息一下吧，查詢優(yōu)化器太復雜了。”

大明笑著說：“堅持不懈就能成功，子連接提升之后，還有子查詢提升、表達式預處理、外連接消除，不過，在這之前還是讓我們先吃個雞再說吧。”

關于選擇下推與等價類

小明感嘆道：“我覺得要深度了解查詢優(yōu)化沒希望了……”大明看出小明對查詢優(yōu)化產生了畏難情緒，因為小明本以為通過大明的講解能夠快速理解查詢優(yōu)化的本質，但他聽過之后發(fā)現(xiàn)，查詢優(yōu)化器遠不是幾次講解就能解決的，大明目前給他講解的還只是在應用層面的講解，還沒有深入到分析源碼階段，僅僅如此，對小明來說理解上就已經(jīng)有些困難了，看來要想深度了解查詢優(yōu)化器，還需要下更大功夫才行。

大明說：“啥叫成功？成功就是在你堅持不下去的時候再堅持一下。來吧，Let’s繼續(xù)。”說著打開了電腦，“我們繼續(xù)說點啥呢？剛剛說到了子連接，接下來我們簡單說說選擇下推和等價類吧。”

小明想了想說：“選擇下推和等價類是邏輯分解優(yōu)化中的內容了，可是邏輯重寫優(yōu)化里還有子查詢提升、表達式預處理、外連接消除這些大塊頭你還沒有給我講解過呀。”

大明說：“這些先留給你自己去理解，如果理解不了再來找我吧。邏輯優(yōu)化的規(guī)則實際上還是比較多的，但是可以逐個擊破的，也就是他們之間通常而言并沒有多大的關聯(lián)，我們不打算在這上面糾纏太多時間，我相信以你自己的能力把他們搞定是沒有問題的。”

“我記得你說過，選擇下推是為了盡早地過濾數(shù)據(jù)，這樣就能在上層結點降低計算量，是吧？”

“是的。”大明點了點頭，“還是通過一個關系代數(shù)的示例來說明一下它吧，順便我們把等價類推理也說一說。比如說我們想要獲得編號為5的老師承擔的所有課程名字，我們可以給出它的關系代數(shù)表達式。”說著在電腦上敲了一個關系代數(shù)表達式：

Πcname (σTEACHER.tno=5∧TEACHER.tno=COURSE.tno (TEACHER×COURSE))

“小明，你看這個關系代數(shù)表達式怎么下推選擇操作？”

小明看著關系代數(shù)表達式思考了一會，說：“我看這個TEACHER.tno = 5比較可疑，你看這個關系代數(shù)表達式，先做了TEACHER×COURSE，也就是先做了卡氏積，我要是把TEACHER.tno = 5放到TEACHER上先把一些數(shù)據(jù)過濾掉，豈不是……完美！”說著小明也在電腦上敲出了把TEACHER.tno = 5下推之后的關系代數(shù)表達式。

Πcname (σTEACHER.tno=5∧TEACHER.tno=COURSE.tno (TEACHER×COURSE))

大明說：“對的，你這樣下推下來的確能降低計算量，這應用的是關系代數(shù)表達式中的分配率σF(A × B) == σF1(A) × σF2(B)，那你看看，既然下推這么好，是不是投影也能下推？”小明看了一下，關系代數(shù)表達式中值需要對cname進行投影，頓時想到了，COURSE表雖然有很多個列，但是我們只需要使用cname就夠了嘛，于是小明在電腦上敲了投影下推的關系代數(shù)表達式。

Πcname (σTEACHER.tno=COURSE.tno (σTEACHER.tno=5(TEACHER)×COURSE))

大明拍了小明的頭一下說：“笨蛋，你這樣下推投影，TEACHER.tno=COURSE.tno還有辦法做嗎？”小明頓時領悟了，如果只在COURSE上對cname做投影時不行的，上層結點所有的表達式都需要考慮到，于是修改了表達式：

Πcname (σTEACHER.tno=COURSE.tno (σTEACHER.tno=5(TEACHER)× Πcname, tno(COURSE)))

“這還差不多。”大明笑著說：“這是使用的投影的串接率，也是一個非常重要的關系代數(shù)等價規(guī)則，目前我們對這個表達式的優(yōu)化主要是使用了選擇下推和投影下推，如果用SQL語句來表示，就像這樣。”大明在電腦的記事本上快速打出了兩個SQL語句： 

SELECT sname FROM TEACHER t, COURSE c WHERE t.tno = 5 AND t.tno = c.tno;  
SELECT sname FROM (SELECT * FROM TEACHER WHERE tno = 5) tt, (SELECT cname, tno FROM COURSE) cc WHERE tt.tno = cc.tno; 

“你看這兩個語句，就是謂詞下推和投影下推前后的對照語句。在做卡氏積之前，先做了過濾，這樣笛卡爾積的計算量會變小。”

小明仔細觀察著代數(shù)表達式和這兩個SQL語句，發(fā)現(xiàn)了一個問題，就是關系代數(shù)表達式中有TEACHER.tno = 5和TEACHER.tno = COURSE.tno這樣兩個約束條件，這是不是意味著COURSE.tno也應該等于5呢？小明試著在電腦上寫了一個SQL語句： 

SELECT sname FROM (SELECT * FROM TEACHER WHERE tno = 5) tt, (SELECT cname, tno FROM COURSE WHERE tno=5) cc WHERE tt.tno = cc.tno; 

然后小明說：“你看，由于有TEACHER.tno = 5和TEACHER.tno = COURSE.tno這樣的兩個約束條件，我們是不是可以推理出一個新的COURSE.tno = 5的新約束條件來呢，這樣還可以把這個條件下推到COURSE表上，也能降低笛卡爾積的計算量。”

大明說：“是的，這就是等價推理，PostgreSQL在查詢優(yōu)化的過程中，會將約束條件中等價的部分都記錄到等價類中，這樣就能根據(jù)等價類生成新的約束條件出來，比如示例的語句中就會產生一個等價類{TEACHER.tno, COURSE.tno, 5}，這是一個含有常量的等價類，是查詢優(yōu)化器比較喜歡的等價類，這種等價類可以得到列屬性和常量組合成的約束條件，通常都是能下推的。”

小明心里很高興，自己通過仔細觀察，得到了等價類的優(yōu)化，感覺有了學習的動力，心里美滋滋的，然后問大明：“那上面的SQL語句還有什么可優(yōu)化的嗎？”

大明觀察了一下這個語句說：“我們已經(jīng)在TEACHER表上進行了TEACHER.tno = 5的過濾，在COURSE表上也做了COURSE.tno = 5的過濾，這就說明在做笛卡爾積時，實際上已確定了TEACHER.tno = COURSE.tno = 5，也就是說TEACHER.tno = COURSE.tno這個約束條件已經(jīng)隱含成立了，也就沒什么用了，我們可以把它去掉，最終形成一個這樣的SQL語句。”大明敲下了最終的語句： 

SELECT sname FROM (SELECT * FROM TEACHER WHERE tno = 5) tt, (SELECT cname, tno FROM COURSE WHERE tno=5) cc； 

同時也敲出了這個語句對應的關系代數(shù)表達式：

Πcname (σTEACHER.tno=5(TEACHER)× Πcname, tno(σCOURSE.tno=5(COURSE))

大明說：“經(jīng)過選擇下推、投影下推和等價類推理，我們對這個SQL語句或者說關系代數(shù)表達式進行了優(yōu)化，最終降低了計算量。”

 

小明感覺對謂詞下推已經(jīng)理解了：“看上去也不復雜嘛，我發(fā)現(xiàn)了可以下推的選擇我就下推，完全沒有問題啊。”大明笑著說：“甚矣，我從未見過如此厚顏無恥之人，我們現(xiàn)在看的這個例子，只不過是最簡單的一種情況啊，你就這樣大言不慚，你的人生字典里還有羞恥二字嗎？”

小明憤憤地說：“我的人生沒有字典……”

大明問道：“我們這個例子有一個問題，它是內連接，因此我們可以肆意妄為地將選擇下推下來，可以沒羞沒臊地做等價類推理，但如果是外連接，還能這么做嗎？”

小明頓時陷入了苦苦的沉思。

關于表達式的嚴格

小明被大明將了一軍，心里開始合計起來，假如是外連接，可能會對某一方補NULL值，這樣的話TEACHER.tno = COURSE.tno的約束條件就無法構成等價類了，然后小明在電腦上默默敲了一個SQL語句： 

SELECT sname FROM TEACHER t LEFT JOIN COURSE c ON t.tno = 5 AND t.tno = c.tno; 

然后小明發(fā)現(xiàn)不但等價類可能產生不了，選擇下推也無法進行了，于是說：“這個語句中的TEACHER.tno = 5不能下推了，因為左連接的語義是外表的所有數(shù)據(jù)都要輸出出來，如果把TEACHER.tno = 5下推到TEACHER表上，就會在做左連接之前先對TEACHER表做過濾，導致查詢結果的不等價，而且由于補NULL值，等價類也生成不了了。”

大明說：“對的，你理解得很快，由于外連接補NULL值的關系，確實導致無法做謂詞下推，不過你可以看一下下面這個語句，看看有什么區(qū)別。”然后大明在電腦里輸入了另一個類似的SQL語句： 

SELECT sname FROM TEACHER t LEFT JOIN COURSE c ON TRUE WHERE t.tno = 5 AND t.tno = c.tno; 

小明仔細觀察上面的例句和當前這個例句，發(fā)現(xiàn)約束條件一個處在ON后面，另一個處在WHERE后面，小明好像還不是很理解它們的含義，于是向大明投去了詢問的目光。大明說：“我們粗略地分一下，ON后面的約束條件是連接條件，WHERE后面的約束條件是過濾條件，連接條件和過濾條件是不同的。”

小明好像悟到了什么，搶著說：“我知道了，一個是連接中的，一個是連接后的，可以這么理解吧？你看，連接條件會參與到連接操作的過程中，滿足連接條件的會顯示出來，不滿足連接條件的，根據(jù)連接的類型還會決定是否補NULL值，而過濾條件是在連接操作之后對連接的結果進行過濾……”小明又對大明投去了期待的眼神，大明笑著說：“對，可以這么理解。”

小明趕緊說：“你先別講，讓我看看這個帶有過濾條件的SQL語句是不是能下推。”，然后對著這個SQL語句仔細觀察起來，口中念念有詞，但觀察了半天毫無收獲。

大明見狀繼續(xù)說：“實際上這里還有一個嚴格的概念，什么叫嚴格呢？一個表達式，如果它的輸入是NULL并且輸出也是NULL，那我們就說這個表達式是嚴格的，另外我們可以擴展一下嚴格的定義，從而定義出一個叫做‘寬泛的嚴格’的概念，就是說如果一個表達式它的輸入是NULL，它的輸出是NULL或者false，那么我們就說它符合寬泛的嚴格。”

“那么嚴格有什么用呢？”

“如果對一個元組應用約束條件，如果約束條件求值返回的是NULL值或者FALSE，實際上代表的是這一條元組不輸出，明白嗎？”

“那就是說我們補的NULL值如果遇到這種過濾條件，就不會輸出出來嘍。”小明停了一下，突然想到了些什么，繼續(xù)問道，“那這種外連接還補NULL值干嘛，豈不是沒有什么用了？”

“對頭，這就是外連接消除的基本原理，遇上這種嚴格的約束條件，外連接補的NULL值沒有什么用，那也就轉變成內連接就好了。問題來了，如果變成了內連接，我們又能肆意妄為地選擇下推、沒羞沒臊地做等價推理了，驚不驚喜，意不意外？”

“哈哈，那你能給我一個不嚴格的例子不？讓我見識一下不嚴格的表達式。”

“比如說IS NOT NULL，輸入是NULL值，輸出竟然是TRUE，還有COALESCE函數(shù)，輸入是NULL值，輸出是啥隨你定。”

小明說：“看來表達式是否嚴格是很重要的一個概念，通過這個概念我們能做外連接消除，外連接消除又能夠導致選擇能夠下推……這我就明白了為什么要做外連接消除了。”

“嗯，外連接消除不只是將外連接轉換成內連接，其實還有一種情況，它也和我們要說的表達式的條件是否嚴格有關，那就是可以將外連接轉換成Anti Join，我們來看這樣一個例子。” 

SELECT * FROM STUDENT LEFT JOIN SCORE ON STUDENT.sno = SCORE.sno WHERE SCORE.sno IS NULL; 

“由于STUDENT.sno = SCORE.sno是嚴格的，而且是連接條件，這樣在連接的過程中他會將在STUDENT表和SCORE表中原有的NULL值去除掉，反而由于SOCRE.sno IS NULL是過濾條件，它起到了過濾作用，會將外連接補充NULL值的數(shù)據(jù)全部保留下來，這個語句的執(zhí)行結果實際上就相當于做了一個Anti Join，因此這個語句可以轉換成為Anti Join，它轉換的結果相當于下面這個語句。”大明在電腦上敲出了等價語句。 

SELECT * FROM STUDENT ANTI JOIN SCORE ON STUDENT.sno = SCORE.sno 

“不過需要注意，SQL語法中是沒有ANTI JOIN的，這只是一個等價的語句，但是它無法直接執(zhí)行。另外在外連接消除的階段還有一個‘很重大’的舉措，就是把左外連接全部轉換成了右外連接，這樣就可以在后續(xù)的代碼中少處理一種情況，簡化了后面的代碼邏輯。”

“嚴格果然是太有用了，可是我怎么知道一個表達式是不是嚴格呢？” 

“對于函數(shù)而言，在PG_PROC系統(tǒng)表中的proisstrict列屬性代表了當前函數(shù)是否嚴格，如果是操作符表達式，在PostgreSQL中操作符實際都轉成了對應的函數(shù)，因此也可以用proisstrict來表示是否嚴格，而對基于IS [NOT] NULL產生的NullTest表達式需要單獨處理，其中IS NOT NULL是嚴格的，IS NULL是不嚴格的，大體上我們可以分成這么幾類。”