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

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

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

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

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

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

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

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

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

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

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

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

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

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

“進(jìn)行等價(jià)轉(zhuǎn)換的目的是找到性能更好的代數(shù)表達(dá)式吧？”小明問。

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

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

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

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

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

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

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

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

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

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

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

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

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

大明：“為什么？”

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

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

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

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

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

關(guān)于語法樹

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

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

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

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

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

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

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

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

“當(dāng)然，我最擅長(zhǎng)寫Hello World。”

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

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

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

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

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

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

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

“這是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對(duì)應(yīng)的簡(jiǎn)版查詢樹，看著復(fù)雜嗎？”大明邊畫邊問。小明心中翻騰出千萬只泥馬，他似乎感覺到自己選擇查詢優(yōu)化作為數(shù)據(jù)庫原理課的實(shí)踐作業(yè)是一個(gè)錯(cuò)誤的決定，現(xiàn)在自己已經(jīng)受到了沖動(dòng)的懲罰，這個(gè)圖里的大部分內(nèi)容他都不知道是什么東西。

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

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

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

關(guān)于子連接

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

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

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

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

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

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

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

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

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

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

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

“那么一定是相關(guān)子連接才會(huì)提升了，因?yàn)槲矣浀媚阍谡f邏輯優(yōu)化原理的時(shí)候說過，相關(guān)子連接會(huì)產(chǎn)生‘嵌套循環(huán)’，這種情況的復(fù)雜度是O(N^2)，提升上來的復(fù)雜度肯定不會(huì)比O(N^2)差，所以提升是有價(jià)值的。”小明說道。

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

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

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

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

“這是一個(gè)ANY類型的非相關(guān)子連接，但請(qǐng)注意，在>前面的sno實(shí)際上產(chǎn)生了一個(gè)天然的相關(guān)性，這個(gè)天然的相關(guān)性就會(huì)產(chǎn)生嵌套循環(huán)，因此是需要提升的。我們?cè)賮砜戳硪粋€(gè)語句。”大明把>前面的sno換成了一個(gè)常量： 

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

“這個(gè)SQL語句中的子連接就不會(huì)提升了，因?yàn)槲覀儼裺no換成了常量，父子之間的相關(guān)性被打破了，明白了嗎？”

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

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

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個(gè)語句提升之后會(huì)變成等價(jià)于第2個(gè)語句，而第2個(gè)語句本身是無法執(zhí)行的，在比較新版本的PostgreSQL上支持了LATERAL之后，只要在第2個(gè)語句上加上LATERAL，也就是變成第3個(gè)語句就能執(zhí)行了。”大明在屏幕上比劃著說。

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

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

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

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

關(guān)于選擇下推與等價(jià)類

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

小明仔細(xì)觀察著代數(shù)表達(dá)式和這兩個(gè)SQL語句，發(fā)現(xiàn)了一個(gè)問題，就是關(guān)系代數(shù)表達(dá)式中有TEACHER.tno = 5和TEACHER.tno = COURSE.tno這樣兩個(gè)約束條件，這是不是意味著COURSE.tno也應(yīng)該等于5呢？小明試著在電腦上寫了一個(gè)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這樣的兩個(gè)約束條件，我們是不是可以推理出一個(gè)新的COURSE.tno = 5的新約束條件來呢，這樣還可以把這個(gè)條件下推到COURSE表上，也能降低笛卡爾積的計(jì)算量。”

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

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

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

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

同時(shí)也敲出了這個(gè)語句對(duì)應(yīng)的關(guān)系代數(shù)表達(dá)式：

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

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

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

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

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

小明頓時(shí)陷入了苦苦的沉思。

關(guān)于表達(dá)式的嚴(yán)格

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

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

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

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

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

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

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

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

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

“那么嚴(yán)格有什么用呢？”

“如果對(duì)一個(gè)元組應(yīng)用約束條件，如果約束條件求值返回的是NULL值或者FALSE，實(shí)際上代表的是這一條元組不輸出，明白嗎？”

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

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

“哈哈，那你能給我一個(gè)不嚴(yán)格的例子不？讓我見識(shí)一下不嚴(yán)格的表達(dá)式。”

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

小明說：“看來表達(dá)式是否嚴(yán)格是很重要的一個(gè)概念，通過這個(gè)概念我們能做外連接消除，外連接消除又能夠?qū)е逻x擇能夠下推……這我就明白了為什么要做外連接消除了。”

“嗯，外連接消除不只是將外連接轉(zhuǎn)換成內(nèi)連接，其實(shí)還有一種情況，它也和我們要說的表達(dá)式的條件是否嚴(yán)格有關(guān)，那就是可以將外連接轉(zhuǎn)換成Anti Join，我們來看這樣一個(gè)例子。” 

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

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

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

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

“嚴(yán)格果然是太有用了，可是我怎么知道一個(gè)表達(dá)式是不是嚴(yán)格呢？” 

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