PostgreSQL查詢優(yōu)化器詳解（物理優(yōu)化篇）
繼《PostgreSQL查詢優(yōu)化器詳解（邏輯優(yōu)化篇）》，本文將另以物理優(yōu)化角度，繼續(xù)深入PostgreSQL數(shù)據(jù)庫(kù)查詢優(yōu)化器的細(xì)枝末節(jié)。為了讓大家通過(guò)通俗易懂的方式更好地理解消化其中的晦澀概念，作者別出心裁地撰寫(xiě)成趣味故事，雖然篇幅稍長(zhǎng)，但細(xì)細(xì)品讀定將收獲匪淺。
關(guān)于統(tǒng)計(jì)信息與選擇率
“咚咚咚……”門(mén)外傳來(lái)了敲門(mén)聲，大明打開(kāi)門(mén)一看，原來(lái)是同事牛二哥。牛二哥是專門(mén)從事數(shù)據(jù)庫(kù)查詢優(yōu)化開(kāi)發(fā)的碼農(nóng)，也有十幾年從業(yè)經(jīng)驗(yàn)了，大明感到非常happy，因?yàn)檫@兩天給小明講查詢優(yōu)化器講得有些吃力，今天牛二哥來(lái)了正好可以幫上忙：“牛二同志，我弟弟小明最近學(xué)校要做數(shù)據(jù)庫(kù)原理實(shí)踐，總來(lái)問(wèn)我優(yōu)化器的問(wèn)題，可我對(duì)優(yōu)化器也是一知半解，這下你來(lái)了可以幫幫忙不？”
牛二哥痛快地說(shuō)：“這難不倒我，隨時(shí)都可以講。”
小明對(duì)牛二哥早有耳聞，接到大明電話后速速趕到，見(jiàn)面不久便吐起了苦水：“我最近正在查看基于代價(jià)的優(yōu)化，感覺(jué)付出了很多代價(jià)，但收獲甚微，期望今天能得到牛二哥的指導(dǎo)。”
牛二哥說(shuō)：“說(shuō)到代價(jià)，我覺(jué)得有個(gè)東西是繞不過(guò)去的，就是統(tǒng)計(jì)信息和選擇率，PostgreSQL的物理優(yōu)化需要計(jì)算各種物理路徑的代價(jià)，而代價(jià)估算的過(guò)程嚴(yán)重依賴于數(shù)據(jù)庫(kù)的統(tǒng)計(jì)信息，統(tǒng)計(jì)信息是否能準(zhǔn)確地描述表中的數(shù)據(jù)分布情況是決定代價(jià)準(zhǔn)確性的重要條件之一。”
小明說(shuō)：“大明和我說(shuō)過(guò)，數(shù)據(jù)庫(kù)有很多物理路徑，這些物理路徑也叫物理算子。和邏輯算子不同，物理算子是查詢執(zhí)行器的執(zhí)行方法，我們只需要計(jì)算物理算子每個(gè)步驟的代價(jià)，匯總起來(lái)就是路徑的代價(jià)了，那要統(tǒng)計(jì)信息有什么用呢？”
牛二哥說(shuō)：“是的，我們就是要計(jì)算一個(gè)物理算子的代價(jià)，但是物理算子的計(jì)算量并不是一成不變的。”說(shuō)著他從旁邊的書(shū)桌上拿來(lái)紙和筆，寫(xiě)了兩個(gè)SQL語(yǔ)句。
- SELECT A+B FROM TEST_A WHERE A > 1;
- SELECT A+B FROM TEST_A WHERE A > 100000000;
然后說(shuō)：“你看，這兩個(gè)語(yǔ)句可以用同樣的物理算子來(lái)完成，但是他們的計(jì)算量一樣的嗎？”
小明心想：A > 1和A > 1000000000都是過(guò)濾條件，經(jīng)過(guò)過(guò)濾之后，他們產(chǎn)生的數(shù)據(jù)量就不同了，這樣投影中的A+B的計(jì)算次數(shù)就不同了，所以它們的代價(jià)應(yīng)該是不同的，那它和統(tǒng)計(jì)信息有什么關(guān)系呢？小明靈光一閃，馬上說(shuō)：“我知道了，我在計(jì)算物理算子的代價(jià)的時(shí)候，要知道A > 1之后還剩下多少數(shù)據(jù)或者A > 1000000000之后還剩下多少數(shù)據(jù)，如果我們提前對(duì)表上的數(shù)據(jù)內(nèi)容做了統(tǒng)計(jì)，剩下多少數(shù)據(jù)就不難計(jì)算了，所以必須要有統(tǒng)計(jì)信息。”
牛二哥點(diǎn)了點(diǎn)頭說(shuō)：“嗯，通過(guò)統(tǒng)計(jì)信息，代價(jià)估算系統(tǒng)就可以了解一個(gè)表有多少行數(shù)據(jù)、用了多少個(gè)數(shù)據(jù)頁(yè)面、某個(gè)值出現(xiàn)的頻率等等，然后就能根據(jù)這些信息計(jì)算出一個(gè)約束條件能過(guò)濾掉多少數(shù)據(jù)，這種約束條件過(guò)濾出的數(shù)據(jù)占總數(shù)據(jù)量的比例稱之為‘選擇率’，所謂選擇率就是一個(gè)比例，它的公式是這樣的。”說(shuō)著牛二哥繼續(xù)在紙上寫(xiě)下了選擇率的公式：
“不過(guò)上面的示例有點(diǎn)簡(jiǎn)單了，實(shí)際應(yīng)用中通常約束條件會(huì)比較多，而且比較復(fù)雜，通常我們會(huì)計(jì)算每個(gè)子約束條件的選擇率，然后就可以根據(jù)AND運(yùn)算符和OR運(yùn)算符計(jì)算它們的綜合的選擇率，AND運(yùn)算符和OR運(yùn)算符的選擇率計(jì)算是基于概率的，你看這里的概率公式。”說(shuō)著，牛二哥又繼續(xù)在紙上寫(xiě)了起來(lái)。
- P(A+B)=P(A)+P(B)-P(AB)
- P(AB)=P(A)×P(B)
“有了這些，我們就可以求解多種類型的約束條件的選擇率了，比如……”牛二哥繼續(xù)寫(xiě)出：
- P(ssex IS NOT NULL OR sno > 5)
- = P(ssex IS NOT NULL) + P(sno > 5) – P(ssex IS NOT NULL AND sno > 5)
- = P(ssex IS NOT NULL) + P(sno > 5) – P(ssex IS NOT NULL) × P(no > 5)
小明覺(jué)得牛二哥講解的進(jìn)展有點(diǎn)快，趕緊問(wèn)：“那么統(tǒng)計(jì)信息是什么形式的呢？”
牛二哥撓撓頭說(shuō)：“這個(gè)還真是有點(diǎn)麻煩，我們說(shuō)常用的統(tǒng)計(jì)信息的形式就是distinct率、NULL值率、高頻值、直方圖、相關(guān)系數(shù)這些，它們分別有不同的作用。比如說(shuō)distinct率，你可以獲知某一列有多少個(gè)獨(dú)立值，這種信息對(duì)于像性別這種列就顯得特別有用。NULL值率呢，在統(tǒng)計(jì)的過(guò)程中，NULL值是不好處理的，因此把它獨(dú)立出來(lái)，形成NULL值率，這樣在高頻值、直方圖這些里面就不用考慮NULL值的情況了。高頻值屬于奇異值，顧名思義，就是出現(xiàn)得比較多的一些列值。去掉了NULL值，再去掉高頻值，剩下的值可以用來(lái)做一個(gè)等頻的直方圖。”
大明看小明有點(diǎn)跟不上，過(guò)來(lái)說(shuō)：“統(tǒng)計(jì)信息嘛，主要的還是高頻值、直方圖和相關(guān)系數(shù)，實(shí)際上我建議還是不要糾結(jié)于統(tǒng)計(jì)信息有哪些形式，只要知道它是用來(lái)算代價(jià)的就可以了。”
牛二哥對(duì)大明說(shuō)：“這怎么可以，我還沒(méi)有說(shuō)統(tǒng)計(jì)信息是如何生成的呢，比如它通過(guò)了兩階段采樣，然后對(duì)樣本進(jìn)行統(tǒng)計(jì)時(shí)使用的統(tǒng)計(jì)方法，哪些值可以作為高頻值，直方圖有幾個(gè)桶，相關(guān)系數(shù)是怎么計(jì)算的，相關(guān)系數(shù)在計(jì)算索引掃描路徑代價(jià)的時(shí)候怎么用的……而且我和你說(shuō)，PostgreSQL還出了基于多列的擴(kuò)展統(tǒng)計(jì)信息，多列統(tǒng)計(jì)信息分成了哪些類型，分別是什么含義，各自是怎么計(jì)算的，還有選擇率是怎么結(jié)合統(tǒng)計(jì)信息計(jì)算的，這些我還沒(méi)說(shuō)呢……”
大明忍不住說(shuō)：“像你這樣講優(yōu)化器，豈不是要出一本書(shū)了？”
牛二哥做痛苦狀：“那好吧，統(tǒng)計(jì)信息我們就說(shuō)到這里，但是它確實(shí)是代價(jià)計(jì)算的基石，小明同學(xué)，你理解了它的作用就可以了。”
大明繼續(xù)神秘地說(shuō)：“實(shí)際上統(tǒng)計(jì)信息往往也不準(zhǔn)，你想想本來(lái)就是采樣的結(jié)果嘛，樣本是否顯著壓根就不好說(shuō)，而且隨著應(yīng)用程序?qū)Ρ淼母?，統(tǒng)計(jì)信息可能更新不及時(shí)，那就更會(huì)出現(xiàn)偏差。更嚴(yán)重的是，如果我們遇到a > b這樣的約束條件，使用統(tǒng)計(jì)信息計(jì)算選擇率也很不好計(jì)算，即使算出來(lái)，也不準(zhǔn)嘛。”
牛二哥說(shuō)：“是的，統(tǒng)計(jì)信息確實(shí)也有不準(zhǔn)確的問(wèn)題。我聽(tīng)說(shuō)有個(gè)DBA，他家后院出了一口泉水，他爸爸覺(jué)得是吉兆，去找風(fēng)水大師看。風(fēng)水大師掐指一算說(shuō)：你兒子是個(gè)DBA，每次數(shù)據(jù)庫(kù)性能慢就知道更新統(tǒng)計(jì)信息，可是統(tǒng)計(jì)信息太水了，都從你家后院冒出來(lái)了。”
三個(gè)人頓時(shí)笑做一團(tuán)。
關(guān)于物理路徑
玩笑過(guò)后，小明說(shuō)：“不如給我說(shuō)說(shuō)物理路徑吧，我們代價(jià)算來(lái)算去，最終還是為了物理路徑計(jì)算代價(jià)嘛。大明和我說(shuō)過(guò)它大體分成掃描路徑和連接路徑，我查過(guò)一些說(shuō)明，知道掃描路徑有順序掃描路徑、索引掃描路徑、位圖掃描路徑等等；而連接路徑通常有嵌套循環(huán)連接路徑、哈希連接路徑、歸并連接路徑，另外還有一些其他的路徑，比如排序路徑、物化路徑等等。”
牛二哥說(shuō)：“是的，我們就來(lái)說(shuō)說(shuō)這些路徑的含義吧。如果要獲得一個(gè)表中的數(shù)據(jù)，最基礎(chǔ)的方法就是將表中的所有的數(shù)據(jù)都遍歷一遍，從中挑選出符合條件的數(shù)據(jù)，這種方式就是順序掃描路徑。順序掃描路徑的優(yōu)點(diǎn)是具有廣泛的適用性，各種表都可以用這種方法，缺點(diǎn)自然是代價(jià)通常比較高，因?yàn)橐阉械臄?shù)據(jù)都遍歷一遍。”大明同時(shí)在紙上畫(huà)了個(gè)圖，說(shuō)：“這個(gè)圖大概就是順序掃描路徑。”
牛二哥則繼續(xù)說(shuō)：“如果將數(shù)據(jù)做一些預(yù)處理，比如建立一個(gè)索引，如果要想獲得一個(gè)表的數(shù)據(jù)，可以通過(guò)掃描索引獲得所需數(shù)據(jù)的‘地址’，然后通過(guò)地址將需要的數(shù)據(jù)獲取出來(lái)。尤其是在選擇操作帶有約束條件的情況下，在索引和約束條件共同的作用下，表中有些數(shù)據(jù)就不用再遍歷了，因?yàn)橥ㄟ^(guò)索引就很容易知道這些數(shù)據(jù)是不符合約束條件的，更有甚者，因?yàn)樗饕弦脖４媪藬?shù)據(jù)，它的數(shù)據(jù)和關(guān)系中的數(shù)據(jù)是一致的，因此如果索引上的數(shù)據(jù)就能滿足要求，只需要掃描索引就可以獲得所需數(shù)據(jù)了，也就是說(shuō)在掃描路徑中還可以有索引掃描路徑和快速索引掃描路徑兩種方式。”
大明則繼續(xù)為牛二哥“捧哏”，在紙上畫(huà)出了索引掃描和快速索引掃描的圖。
小明看到圖上寫(xiě)了“隨機(jī)讀”三個(gè)字，問(wèn)道：“我看這個(gè)索引掃描有隨機(jī)讀的問(wèn)題，這個(gè)問(wèn)題能否解決掉呢？也就是說(shuō)即利用了索引，還避免了隨機(jī)讀的問(wèn)題，有這樣的辦法嗎？”
牛二哥說(shuō)：“索引掃描路徑確實(shí)帶來(lái)隨機(jī)讀的問(wèn)題，因?yàn)樗饕杏涗浀氖菙?shù)據(jù)元組的地址，索引掃描是通過(guò)掃描索引獲得元組地址，然后通過(guò)元組地址訪問(wèn)數(shù)據(jù)，索引中保存的“有序”的地址，到數(shù)據(jù)中就可能是隨機(jī)的了。位圖掃描就能解決這個(gè)問(wèn)題，它通過(guò)位圖將地址保存起來(lái)，把地址收集起來(lái)之后，然后讓地址變得有序，這樣就通過(guò)中間的位圖把隨機(jī)讀消解掉了。”大明則繼續(xù)在紙上畫(huà)出了位圖掃描的示意圖。
大明補(bǔ)充說(shuō)道：“掃描過(guò)程中還會(huì)結(jié)合一些特殊的情況有一些非常高效的掃描路徑，比如TID掃描路徑，TID實(shí)際上是元組在磁盤(pán)上的存儲(chǔ)地址，我們能夠根據(jù)TID直接就獲得元組，這樣查詢效率就非常高了。”
牛二哥點(diǎn)了點(diǎn)頭繼續(xù)說(shuō)：“掃描路徑通常是執(zhí)行計(jì)劃中的葉子結(jié)點(diǎn)，也就是在最底層對(duì)表進(jìn)行掃描的結(jié)點(diǎn)，掃描路徑就是為連接路徑做準(zhǔn)備的，掃描出來(lái)的數(shù)據(jù)就可以給連接路徑來(lái)實(shí)現(xiàn)連接操作了。”
大明一邊在紙上畫(huà)一邊說(shuō)：“要對(duì)兩個(gè)關(guān)系做連接，受笛卡爾積的啟發(fā)，可以用一個(gè)算法復(fù)雜度是O(mn)的方法來(lái)實(shí)現(xiàn)，我們叫它Nestlooped Join方法。這種方法雖然復(fù)雜度比較高，但是和順序掃描一樣，勝在具有普適性。”
牛二哥說(shuō)：“嵌套循環(huán)連接這種方法的復(fù)雜度比較高，看上去沒(méi)什么意義，但是如果Nestlooped Join的內(nèi)表的路徑是一個(gè)索引掃描路徑，那么算法的復(fù)雜度就會(huì)降下來(lái)。索引掃描的算法復(fù)雜度是O(logn)，因此如果Nestlooped Join的內(nèi)表是一個(gè)索引掃描，它的整體的算法復(fù)雜度就變成了O(mlogn)，看上去這樣也是可以接受的。”
小明點(diǎn)了點(diǎn)頭說(shuō)：“嗯，索引實(shí)際上是對(duì)數(shù)據(jù)做了一些預(yù)處理，我想如果哈希連接方法就是將內(nèi)表做一個(gè)哈希表，這樣也等于將內(nèi)表的數(shù)據(jù)做了預(yù)處理，也能方便外表的元組在里面探測(cè)吧？”
牛二哥點(diǎn)了點(diǎn)頭說(shuō)：“假設(shè)Hash表有N個(gè)桶，內(nèi)表數(shù)據(jù)均勻的分布在各個(gè)桶中，那么Hash Join的時(shí)間復(fù)雜度就是O(m * n /N)，當(dāng)然，這里我們沒(méi)有考慮上建立Hash表的代價(jià)。”
大明則在紙上畫(huà)出了Hash連接的示意圖，并補(bǔ)充道：“Hash連接通常只能用來(lái)做等值判斷。”
牛二哥繼續(xù)說(shuō)：“如果將兩個(gè)表先排序，那么就可以引入第三種連接方式，Merge Join。這種連接方式的代價(jià)主要浪費(fèi)在排序上，如果兩個(gè)關(guān)系的數(shù)據(jù)量都比較小，那么排序的代價(jià)是可控的，MergeJoin就是適用的。另外如果關(guān)系上有有序的索引，那就可以不用單獨(dú)排序了，這樣也比較適用于MergeJoin。你看我畫(huà)的這個(gè)歸并連接的示意圖，外表是需要排序的，而內(nèi)表則借用了原有的索引的順序，消除了排序的時(shí)間，降低了物理路徑的代價(jià)。”
“這些路徑屬于SPJ路徑，在PostgreSQL的優(yōu)化器中，通常會(huì)先生成SPJ的路徑，然后在這基礎(chǔ)上再疊加Non-SPJ的路徑，比如說(shuō)聚集操作、排序操作、limit操作、分組操作……”牛二哥繼續(xù)補(bǔ)充道。
關(guān)于代價(jià)的計(jì)算
小明說(shuō)：“可是算來(lái)算去，物理路徑的代價(jià)還是有選不準(zhǔn)的時(shí)候啊。”
牛二哥說(shuō)：“最優(yōu)路徑選得不準(zhǔn)是誰(shuí)的原因？那就是代價(jià)模型不行啊。代價(jià)模型不行賴誰(shuí)？那就是程序員沒(méi)建好啊，所以要怪就怪到程序員自己頭上。”
小明問(wèn)道：“可是我看PostgreSQL的代價(jià)計(jì)算已經(jīng)很復(fù)雜了啊。”
“但數(shù)據(jù)庫(kù)的周邊環(huán)境更復(fù)雜啊。你想想，在實(shí)際應(yīng)用中，數(shù)據(jù)庫(kù)用戶的配置硬件環(huán)境千差萬(wàn)別，CPU的頻率、主存的大小和磁盤(pán)介質(zhì)的性質(zhì)都會(huì)影響執(zhí)行計(jì)劃在實(shí)際執(zhí)行時(shí)的效率。”牛二哥說(shuō)。
大明接過(guò)來(lái)繼續(xù)說(shuō)道；“雖然在代價(jià)估算的過(guò)程中，我們無(wú)法獲得‘絕對(duì)真實(shí)’的代價(jià)，但是‘絕對(duì)真實(shí)’的代價(jià)也是不必要的。因?yàn)槲覀冎皇窍霃亩鄠€(gè)路徑（Path）中找到一個(gè)代價(jià)最小的路徑，只要這些路徑的代價(jià)是可以‘相互比較’的就可以了。因此可以設(shè)定一個(gè)‘相對(duì)’的代價(jià)的單位1，同一個(gè)查詢中所有的物理路徑都基于這個(gè)“相對(duì)”的單位1來(lái)計(jì)算的代價(jià)，這樣計(jì)算出來(lái)的代價(jià)就是可以比較的，也就能用來(lái)對(duì)路徑進(jìn)行挑選了。”
牛二哥接著說(shuō)：“PostgreSQL采用順序讀寫(xiě)一個(gè)頁(yè)面的IO代價(jià)作為單位1，而把隨機(jī)IO定為了順序IO的4倍。”
小明說(shuō)：“我知道，這個(gè)我查過(guò)相關(guān)的書(shū)。首先，目前的存儲(chǔ)介質(zhì)很大部分仍然是機(jī)械硬盤(pán)，機(jī)械硬盤(pán)的磁頭在獲得數(shù)據(jù)庫(kù)的時(shí)候需要付出尋道時(shí)間。如果要讀寫(xiě)的是一串在磁盤(pán)上連續(xù)的數(shù)據(jù)，就可以節(jié)省尋道時(shí)間，提高IO性能。而如果隨機(jī)讀寫(xiě)磁盤(pán)上任意扇區(qū)的數(shù)據(jù)，那么會(huì)有大量的時(shí)間浪費(fèi)在尋道上。其次，大部分磁盤(pán)本身帶有緩存，這就形成了主存→磁盤(pán)緩存→磁盤(pán)的三級(jí)結(jié)構(gòu)。在將磁盤(pán)的內(nèi)容加載到內(nèi)存的時(shí)候，考慮到磁盤(pán)的IO性能，磁盤(pán)會(huì)進(jìn)行數(shù)據(jù)的預(yù)讀，把預(yù)讀到的數(shù)據(jù)保存在磁盤(pán)的緩存中。也就是說(shuō)如果用戶只打算從磁盤(pán)讀取100個(gè)字節(jié)的數(shù)據(jù)，那么磁盤(pán)可能會(huì)連續(xù)地讀取磁盤(pán)中的512字節(jié)（不同的磁盤(pán)預(yù)讀的數(shù)量可能不同）并將其保存到磁盤(pán)緩存。如果下一次是順序讀取100個(gè)字節(jié)之后的內(nèi)容，那么預(yù)讀的512字節(jié)的數(shù)據(jù)就會(huì)發(fā)揮作用，性能會(huì)大大的增加。而如果讀取的內(nèi)容超出了512字節(jié)的范圍，那么預(yù)讀的數(shù)據(jù)就沒(méi)有發(fā)揮作用，磁盤(pán)的IO性能就會(huì)下降。”說(shuō)完小明得意地說(shuō)：“怎么樣，我說(shuō)得對(duì)吧？”
牛二哥說(shuō)：“你說(shuō)得對(duì)，目前PostgreSQL的查詢優(yōu)化大量的考慮了隨機(jī)IO和順序IO所帶來(lái)的性能差別，在這方面做了不少優(yōu)化。但是現(xiàn)在的磁盤(pán)技術(shù)越來(lái)越發(fā)達(dá)了，以后隨機(jī)IO和順序IO是不是還差這么多，就值得商榷了。”
“那到底還有哪些代價(jià)基準(zhǔn)單位呢？”小明繼續(xù)問(wèn)道。
大明回答：“基于磁盤(pán)IO的代價(jià)單位當(dāng)然就是和Page有關(guān)的了，也就是說(shuō)我們剛才說(shuō)的順序IO和隨機(jī)IO都屬于IO方面的基準(zhǔn)代價(jià)。讓牛二哥給你介紹一下CPU方面的代價(jià)基準(zhǔn)單位吧。”
牛二哥說(shuō)：“CPU方面的基準(zhǔn)單位有哪些呢？比如說(shuō)我們通過(guò)IO把磁盤(pán)頁(yè)面讀到了緩存，但我們要處理的是元組啊，所以還需要把元組從頁(yè)面里解出來(lái)，還要處理元組，這部分主要消耗的是CPU，所以會(huì)有一個(gè)元組處理的代價(jià)基準(zhǔn)單位。另外，我們?cè)谕队?、約束條件里有大量的表達(dá)式，這些表達(dá)式求解也主要消耗CPU資源，所以還有一個(gè)表達(dá)式代價(jià)的基準(zhǔn)單位。”
牛二哥繼續(xù)說(shuō)道：“現(xiàn)在PostgreSQL增加了很多并行路徑，因此它也產(chǎn)生了通信代價(jià)，這個(gè)也需要計(jì)算的。”
小明聽(tīng)后說(shuō)：“那我們就能得到一個(gè)這樣的公式。”說(shuō)著在紙上寫(xiě)了一個(gè)公式：
總代價(jià) = CPU代價(jià) + IO代價(jià) + 通信代價(jià)
然后繼續(xù)說(shuō)：“可是我通過(guò)EXPLAIN還查看過(guò)PostgreSQL的執(zhí)行計(jì)劃，從執(zhí)行計(jì)劃中還看到有啟動(dòng)代價(jià)和總代價(jià)，這是怎么回事呢？”
牛二哥想了想，在紙上寫(xiě)了一個(gè)公式：
總代價(jià) = 啟動(dòng)代價(jià) + 執(zhí)行代價(jià)
然后說(shuō)：“這是從另一個(gè)角度來(lái)計(jì)算代價(jià)，啟動(dòng)代價(jià)是指從語(yǔ)句開(kāi)始執(zhí)行到查詢引擎返回第一條元組的代價(jià)（另一種說(shuō)法是準(zhǔn)備好去獲得第一條元組的代價(jià)），總代價(jià)是SQL語(yǔ)句從開(kāi)始執(zhí)行到結(jié)束的所有代價(jià)。”
“可是……為什么要區(qū)分啟動(dòng)代價(jià)和執(zhí)行代價(jià)呢？”
“這個(gè)嘛……”牛二哥思考了一下，覺(jué)得一兩句話不容易說(shuō)清楚，于是寫(xiě)了個(gè)例子：
- SELECT * FROM TEST_A WHERE a > 1 ORDER BY a LIMIT 1;
“我們假設(shè)這個(gè)在TEST_A(a)上有一個(gè)B樹(shù)索引，曉得不，那這個(gè)語(yǔ)句可能會(huì)形成什么樣的執(zhí)行計(jì)劃呢？”
小明想了想，覺(jué)得空想可能有點(diǎn)困難，于是在紙上畫(huà)了一下，最終畫(huà)出了兩個(gè)執(zhí)行路徑：
執(zhí)行路徑1：LIMIT 1
-> SORT(a)
-> SeqScan WHERE A > 1;
執(zhí)行路徑2：LIMIT 1
-> IndexScan WHERE A > 1;
（小明注：B樹(shù)索引有序，不用再排序了）
小明說(shuō)：“我覺(jué)得這兩個(gè)都可以，不過(guò)第二個(gè)更好，因?yàn)楣?jié)省了排序的時(shí)間。”
牛二哥問(wèn)：“你知道的，PostgreSQL采用動(dòng)態(tài)規(guī)劃的方法來(lái)實(shí)現(xiàn)路徑的搜索，它是一種自底向上的方法，也就是說(shuō)會(huì)先建立篩選掃描路徑，然后用篩選后的掃描路徑再去形成連接路徑。那么在我們篩選掃描路徑的時(shí)候，是不知道它的上層有沒(méi)有LIMIT的，這時(shí)候如果單獨(dú)看SeqScan + SORT和IndexScan你覺(jué)得哪個(gè)好呢？”
“嗯，我知道陷阱在哪里，大明和我說(shuō)過(guò)，A > 1的選擇率高的話會(huì)選擇順序掃描，而A > 1的選擇率低的情況下，會(huì)選擇索引掃描。這是因?yàn)樗饕龗呙钑?huì)產(chǎn)生隨機(jī)IO，也就是說(shuō)在選擇率高的情況下，有可能SeqScan + SORT會(huì)優(yōu)于IndexScan。雖然SeqScan + SORT會(huì)有排序，但是IndexScan的隨機(jī)IO實(shí)在是太可觀了。”
牛二哥點(diǎn)了點(diǎn)頭說(shuō)：“對(duì)的，假設(shè)選擇率比較高，這時(shí)選擇了SeqScan + SORT，是因?yàn)樗恢涝偕蠈邮荓IMIT 1。如果上面是LIMIT 1，就會(huì)導(dǎo)致索引掃描不用全部掃完，只要掃一丟丟就可以了。這時(shí)隨機(jī)IO就很小了，但是SeqScan + SORT就還必須全部執(zhí)行完才能獲取到LIMIT 1，也就是說(shuō)SeqScan + SORT、或者說(shuō)SORT要獲取第一條元組的啟動(dòng)代價(jià)是比較高的。如果上面有LIMIT 1這樣的子句，那么啟動(dòng)代價(jià)高的路徑可能就沒(méi)有優(yōu)勢(shì)了，這就是啟動(dòng)代價(jià)的作用。”
小明恍然大悟地說(shuō)：“SORT要全部做完才能獲取第一條元組，它的啟動(dòng)代價(jià)大，但是總代價(jià)小。而索引掃描呢，因?yàn)楸旧碛行颍膯?dòng)代價(jià)是小的，但是由于有隨機(jī)IO，所以它的總代價(jià)是大的。如果我們只按照總代價(jià)進(jìn)行篩選，就沒(méi)辦法獲得最優(yōu)的代價(jià)了。”
“什么什么？啟動(dòng)代價(jià)……你們進(jìn)展很快嘛。”這時(shí)大明跑過(guò)來(lái)說(shuō)：“讓我們想一下晚上吃點(diǎn)什么吧？”
小明：“吃點(diǎn)好的，很有必要。我這腦細(xì)胞已經(jīng)快用沒(méi)了。”
關(guān)于最優(yōu)路徑
小明、大明和牛二哥在外賣(mài)APP里搜索附近的飯店，大明突然感嘆道：“看，這就是藍(lán)海，我們可以創(chuàng)業(yè)搞一個(gè)AI點(diǎn)評(píng)，只能推薦最優(yōu)的飯店啊，我準(zhǔn)確地找到了吃貨們的痛點(diǎn)，這里面隱含著很大的商機(jī)??！”
牛二哥瞥了他一眼說(shuō)：“AI推薦當(dāng)然好，可是要推薦得準(zhǔn)才行啊。一個(gè)人一個(gè)口味，你這個(gè)需求太‘智能’了，我估計(jì)不好弄。”
小明突然說(shuō)：“我最近在算法課上學(xué)過(guò)一些最優(yōu)解問(wèn)題的解決方法，應(yīng)該能用得上。”
牛二哥嘆口氣說(shuō)：“可是這些方法用到優(yōu)化器里都不一定夠用，何況用到一個(gè)更加智能的項(xiàng)目上呢？”
“嗯？?jī)?yōu)化器里也用到最優(yōu)解問(wèn)題的方法了嗎？我們學(xué)過(guò)動(dòng)態(tài)規(guī)劃、貪心算法……”小明如數(shù)家珍地說(shuō)起來(lái)。
大明說(shuō)：“用到了啊， 雖然物理路徑看上去也不多，但實(shí)際上枚舉起來(lái)，它的搜索空間也不小。例如在掃描路徑中，我們就可以有順序掃描、索引掃描和位圖掃描。假如一個(gè)表上有多個(gè)索引，就可能產(chǎn)生多個(gè)不同的索引掃描，那么哪個(gè)索引掃描路徑好呢？還有索引掃描和順序掃描、位圖掃描相比，哪個(gè)好呢？”
大明看著小明迷離的眼神后繼續(xù)說(shuō)：“數(shù)據(jù)庫(kù)路徑的搜索方法通常有3種類型：自底向上方法、自頂向下方法、隨機(jī)方法，而PostgreSQL采用了其中的兩種方法。”
“采用了哪兩種方法？”牛二哥明知故問(wèn)。
“采用了自底向上和隨機(jī)方法，其中自底向上的方法是采用動(dòng)態(tài)規(guī)劃方法，而隨機(jī)方法采用的是遺傳算法。”
“那有誰(shuí)使用了自頂向下的方法呢？”牛二哥繼續(xù)“捧哏”道。
“嗯……這個(gè)嘛，Pivotal公司的開(kāi)源優(yōu)化器ORCA用的就是自頂向下的方法?？梢宰屌６缦冉o你說(shuō)說(shuō)怎樣用動(dòng)態(tài)規(guī)劃方法搜索最優(yōu)物理路徑。”
牛二哥拿出紙來(lái)畫(huà)了幾個(gè)圈，然后說(shuō)：“這代表四個(gè)表，自底向上嘛，所以是從底下向上堆積，這是最底層，我們叫它第一層”。
“動(dòng)態(tài)規(guī)劃方法首先考慮兩個(gè)表的連接，其中優(yōu)先考慮有連接關(guān)系的表進(jìn)行連接，兩個(gè)表的連接可以建立一個(gè)新的表，我們把這些新表叫做第二層。”牛二哥通過(guò)連線，產(chǎn)生了一些新的“表”。
“第二層的表和第一層的表再連接，可以生成基于三個(gè)表連接的新的‘表’，這樣就又向前推進(jìn)了一層，我們產(chǎn)生了第三層”
“然后再用第三層的表和第一層的表進(jìn)行連接，最終生成整個(gè)問(wèn)題的最優(yōu)路徑。”
“可是，這不就是窮舉嗎？”小明問(wèn)道。
牛二哥解釋說(shuō)：“動(dòng)態(tài)規(guī)劃有兩個(gè)特點(diǎn)，一個(gè)是要重復(fù)地利用子問(wèn)題的解，這樣能減少計(jì)算量，降低復(fù)雜度；另外一點(diǎn)就是通過(guò)子問(wèn)題的最優(yōu)解能夠構(gòu)造出最終的最優(yōu)解，也就是說(shuō)需要具有最優(yōu)子結(jié)構(gòu)的性質(zhì)，所以動(dòng)態(tài)規(guī)劃的復(fù)雜度和窮舉是不一樣的。”
大明繼續(xù)解釋說(shuō)：“還有，雖然你看圖里的連線比較多，但在實(shí)際情況里，并不是所有的圈圈之間都能產(chǎn)生連線，連接關(guān)系也有個(gè)合法性的問(wèn)題嘛，所以復(fù)雜度是可以控制住的。”
小明感覺(jué)好像明白了一點(diǎn)，然后趕緊追問(wèn)：“那遺傳算法呢？”
大明說(shuō)：“雖然動(dòng)態(tài)規(guī)劃的復(fù)雜度是可以控制的，但是如果表比較多，它的搜索空間還是很大，所以如果在表比較多的時(shí)候，可以嘗試使用遺傳算法，這個(gè)算法獲得的不一定是全局最優(yōu)解，可能是局部最優(yōu)解。”
“那遺傳算法是怎么實(shí)現(xiàn)物理路徑搜索的呢？”小明問(wèn)。
牛二哥從書(shū)柜里找到了一本算法的書(shū)，恰好里面有遺傳算法的介紹，于是朗讀了起來(lái)：“遺傳算法的實(shí)現(xiàn)步驟如下：
- 種群初始化：對(duì)基因進(jìn)行編碼，并通過(guò)對(duì)基因進(jìn)行隨機(jī)的排列組合，生成多個(gè)染色體，這些染色體構(gòu)成一個(gè)新的種群。另外，在生成染色體的過(guò)程中同時(shí)計(jì)算染色體的適應(yīng)度；
- 選擇染色體：通過(guò)隨機(jī)選擇（實(shí)際上通過(guò)基于概率的隨機(jī)數(shù)生成算法，這樣能傾向于選擇出優(yōu)秀的染色體），選擇出用于交叉和變異的染色體；
- 交叉操作：染色體進(jìn)行交叉，產(chǎn)生新的染色體并加入到種群；
- 變異操作：對(duì)染色體進(jìn)行變異操作，產(chǎn)生新的染色體并加入到種群；
- 適應(yīng)度計(jì)算：對(duì)不良的染色體進(jìn)行淘汰。”
大明笑著說(shuō)：“盡信書(shū)不如無(wú)書(shū)，我來(lái)說(shuō)一下遺傳算法是如何解決貨郎問(wèn)題的。我們可以將城市作為基因，走遍各個(gè)城市的路徑作為染色體，路徑的總長(zhǎng)度作為適應(yīng)度，適應(yīng)度函數(shù)負(fù)責(zé)篩選掉比較長(zhǎng)的路徑，保留較短的路徑，算法的步驟如下：
- 對(duì)各個(gè)城市進(jìn)行編號(hào)，將各個(gè)城市根據(jù)編號(hào)進(jìn)行排列組合，生成多條新的路徑（染色體）。然后根據(jù)各城市間的距離計(jì)算整體路徑長(zhǎng)度（適應(yīng)度），多條新路徑構(gòu)成一個(gè)種群；
- 選擇兩個(gè)路徑進(jìn)行交叉（需要注意交叉生成新染色體中不能重復(fù)出現(xiàn)同一個(gè)城市），對(duì)交叉操作產(chǎn)生的新路徑計(jì)算路徑長(zhǎng)度；
- 隨機(jī)選擇染色體進(jìn)行變異（通常方法是交換城市在路徑中的位置），對(duì)變異操作后的新路徑計(jì)算路徑長(zhǎng)度；
- 對(duì)種群中所有路徑進(jìn)行基于路徑長(zhǎng)度有小到大排序，淘汰掉排名靠后的路徑。”
大明一口氣說(shuō)完了整個(gè)流程，長(zhǎng)舒了一口氣，繼續(xù)說(shuō)道：“怎么樣，是不是so easy?”
小明想了想牛二哥和大明說(shuō)的流程，然后說(shuō)，“我來(lái)猜想一下PostgreSQL是如何實(shí)現(xiàn)遺傳算法的。PostgreSQL應(yīng)該是模擬了解決貨郎問(wèn)題的方法，它將表作為基因，最終生成的執(zhí)行計(jì)劃作為染色體，執(zhí)行計(jì)劃的總代價(jià)作為適應(yīng)度，適應(yīng)度函數(shù)則是基于路徑的代價(jià)進(jìn)行篩選，對(duì)不對(duì)？”
牛二哥贊嘆道：“說(shuō)得非常好，不過(guò)需要注意的是，PostgreSQL的基因算法實(shí)現(xiàn)方式和通常的遺傳算法略有不同，在于其沒(méi)有變異的過(guò)程，只通過(guò)交叉產(chǎn)生新的染色體，不過(guò)這都不是重點(diǎn)了。”
大明說(shuō)：“哎哎哎，我們不是在搜索飯店嗎，怎么就說(shuō)起最優(yōu)路徑了？先點(diǎn)餐吧，再晚飯都沒(méi)得吃了。”
于是三個(gè)人又熱火朝天地搜起飯店來(lái)……
總結(jié)
本故事到此暫時(shí)劇終了。通過(guò)上下兩篇文章，我們基本已了解到大部分查詢優(yōu)化的概念，但篇幅有限，沒(méi)能把細(xì)節(jié)說(shuō)得特別到位，請(qǐng)大家多多包涵。
兩篇文章中大部分內(nèi)容均摘錄自我的新書(shū)《PostgreSQL技術(shù)內(nèi)幕：查詢優(yōu)化深度探索》，然后以小明、大明和牛二哥的對(duì)話方式展現(xiàn)出來(lái)。而書(shū)中介紹的代碼分析部分以及比較深入的實(shí)現(xiàn)細(xì)節(jié)，由于不太便于展示，所以在故事中沒(méi)有涉及到，有興趣的同學(xué)歡迎從書(shū)中獲取相關(guān)知識(shí)。
