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

查詢優化器的基本原理

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

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

小明提出的第一個問題是：“為什么數據庫要進行查詢優化？”

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

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

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

說著大明將身子向沙發一靠，翹上二郎腿繼續說：“通常來說分成兩個層面，一個是基于規則的優化，另一個是基于代價的優化。基于規則的優化也可以叫邏輯優化或者規則優化，基于代價的優化也可以叫物理優化或者代價優化。”

“為什么要進行這樣的區分呢？優化就優化嘛，何必還分什么規則和代價呢？”，小明問道。

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

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

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

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

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

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

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

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

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

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

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

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

大明繼續說道：“數據庫說我也不知道啊，你說的左外連接意思我懂，但我也不知道怎么實現啊？你需要告訴我實現方法啊，因此優化器還承擔了一個任務，就是告訴執行器，怎么來實現一個左外連接。”

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

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

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

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

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

大明：“為什么？”

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

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

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

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

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

關于語法樹

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

“是的。”大明肯定地說。“不過語義分析還做了一個工作，那就是檢查工作，在語法樹是通過分析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對應的簡版查詢樹，看著復雜嗎？”大明邊畫邊問。小明心中翻騰出千萬只泥馬，他似乎感覺到自己選擇查詢優化作為數據庫原理課的實踐作業是一個錯誤的決定，現在自己已經受到了沖動的懲罰，這個圖里的大部分內容他都不知道是什么東西。

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

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

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

關于子連接

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

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

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

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

“可是我們的數據庫原理課上并沒有說有邏輯重寫優化和邏輯分解優化啊。”

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

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

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

“那在PostgreSQL是如何區分子查詢和子連接的呢？”大明自問自答道：“在實際應用中可以通過子句所處的位置來區分子連接和子查詢，出現在FROM關鍵字后的子句是子查詢語句，出現在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里的子句出現在FROM后面，它是以‘表’的形式存在的，是子查詢，2和3的子句出現在投影和約束條件中，是以表達式的形式存在的，是子連接。”小明不但答對了問題，而且還對問題的答案做了擴展，大明調侃道：“腰間盤同學，坐下，你太突出了。”

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

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

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

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

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

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

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

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

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

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

大明說：“這可能有點歷史原因了，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個語句本身是無法執行的，在比較新版本的PostgreSQL上支持了LATERAL之后，只要在第2個語句上加上LATERAL，也就是變成第3個語句就能執行了。”大明在屏幕上比劃著說。

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

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

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

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

關于選擇下推與等價類

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

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

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

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

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

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

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

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

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

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

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

Π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)))

“這還差不多。”大明笑著說：“這是使用的投影的串接率，也是一個非常重要的關系代數等價規則，目前我們對這個表達式的優化主要是使用了選擇下推和投影下推，如果用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; 

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

小明仔細觀察著代數表達式和這兩個SQL語句，發現了一個問題，就是關系代數表達式中有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在查詢優化的過程中，會將約束條件中等價的部分都記錄到等價類中，這樣就能根據等價類生成新的約束條件出來，比如示例的語句中就會產生一個等價類{TEACHER.tno, COURSE.tno, 5}，這是一個含有常量的等價類，是查詢優化器比較喜歡的等價類，這種等價類可以得到列屬性和常量組合成的約束條件，通常都是能下推的。”

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

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

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

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

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

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

 

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

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

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

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

關于表達式的嚴格

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

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

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

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

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

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

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

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

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

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

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

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

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

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

“比如說IS NOT NULL，輸入是NULL值，輸出竟然是TRUE，還有COALESCE函數，輸入是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值的數據全部保留下來，這個語句的執行結果實際上就相當于做了一個Anti Join，因此這個語句可以轉換成為Anti Join，它轉換的結果相當于下面這個語句。”大明在電腦上敲出了等價語句。 

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

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

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

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