1. 目標(biāo)
從70年代就有很多關(guān)于查詢(xún)優(yōu)化器的技術(shù)，很難用一篇短文就把這個(gè)領(lǐng)域的深度和廣度表達(dá)出來(lái)，因此這里會(huì)列出基礎(chǔ)技術(shù)和這個(gè)領(lǐng)域重要工作的采樣
2. 概述
關(guān)系查詢(xún)語(yǔ)言提供的高抽象聲明的接口來(lái)訪問(wèn)存儲(chǔ)的數(shù)據(jù)，慢慢的SQL成了關(guān)系查詢(xún)語(yǔ)言的標(biāo)準(zhǔn)，對(duì)于SQL數(shù)據(jù)庫(kù)系統(tǒng)，最重要的兩個(gè)組件是查詢(xún)優(yōu)化器和查詢(xún)執(zhí)行引擎。
查詢(xún)執(zhí)行引擎是執(zhí)行一組物理算子，算子有一個(gè)或者多個(gè)輸入，一個(gè)輸出。典型的物理算子有
（外部）排序-(external) sort
順序掃描-sequential scan
索引掃描-index scan
嵌套連接- nested-loop join
排序連接-sort-merge join
對(duì)于一種執(zhí)行，一個(gè)抽象表達(dá)是如圖1物理算子樹(shù)，圖1中的邊代表數(shù)據(jù)在物理算子間的數(shù)據(jù)流轉(zhuǎn)。物理算子樹(shù)和執(zhí)行計(jì)劃（簡(jiǎn)稱(chēng)計(jì)劃）用兩個(gè)術(shù)語(yǔ)分別表示。
執(zhí)行引擎負(fù)責(zé)計(jì)劃的執(zhí)行和產(chǎn)出結(jié)果。所以查詢(xún)執(zhí)行器的能力取決于它支持的算子。查詢(xún)執(zhí)行技術(shù)可以看另外一篇論文《Query Evaluation Techniques for Large Databases》
查詢(xún)優(yōu)化器負(fù)責(zé)產(chǎn)出供執(zhí)行引擎使用的計(jì)劃，優(yōu)化器很重要，因?yàn)閷?duì)于一個(gè)查詢(xún)，有可能會(huì)有很多算子計(jì)劃樹(shù)：
對(duì)于給定的查詢(xún)有可能有很多等價(jià)的計(jì)劃，比如
Join(Join(A,B),C)= Join(Join(B,C),A)
對(duì)于給定的關(guān)系代數(shù)，會(huì)有很多物理實(shí)現(xiàn)，比如join操作就有幾種實(shí)現(xiàn)算法。
另外，對(duì)于這些計(jì)劃的吞吐量和執(zhí)行耗時(shí)會(huì)有很大不同，因此對(duì)于優(yōu)化器選擇一個(gè)優(yōu)等的計(jì)劃很重要。因此，查詢(xún)優(yōu)化可以看作是一個(gè)艱難的搜索問(wèn)題，為了解決這個(gè)這些問(wèn)題，我們需要提供
計(jì)劃的搜索空間。
價(jià)估計(jì)技術(shù)，這些代價(jià)用于各個(gè)搜索空間的代價(jià)計(jì)算。
對(duì)于執(zhí)行空間進(jìn)行搜索的枚舉算法。
一個(gè)好的優(yōu)化器應(yīng)該是
a. 搜索空間包含了代價(jià)低的計(jì)劃，b. 代價(jià)評(píng)估是準(zhǔn)確的，c. 搜索枚舉算法是有效的，對(duì)于每一個(gè)任務(wù)都是重要的，這樣就是為什么一個(gè)好的優(yōu)化器是一個(gè)重大的挑戰(zhàn)。
3. 舉例：System-R 優(yōu)化器
System-R的項(xiàng)目，顯著提高了關(guān)系查詢(xún)優(yōu)化器的狀態(tài)?！禔ccess Path Selection in a Relational Database System》這篇論文里的設(shè)計(jì)已經(jīng)被很多商業(yè)數(shù)據(jù)庫(kù)使用。這里會(huì)展示Select-Project-Join(SPJ)查詢(xún)的一些技術(shù)設(shè)計(jì)。
在System-R中對(duì)于SPJ查詢(xún)，只支持線性Join算子，比如圖2里面的a
因?yàn)榻Y(jié)合律和交換律，以上這些join都是邏輯相等的。對(duì)于join可以使用nested loop 或者 sort-merge的實(shí)現(xiàn)。對(duì)于scan既可以使用索引掃描（聚簇或者非聚簇），也可以使用順序掃描，最后斷言是要盡可能早執(zhí)行。
代價(jià)模型會(huì)對(duì)搜索空間的部分或者全部計(jì)劃進(jìn)行代價(jià)估計(jì)，也會(huì)估計(jì)算子產(chǎn)出的記錄數(shù)，代價(jià)模型依賴(lài)于以下3點(diǎn)：
關(guān)系和索引的統(tǒng)計(jì)信息，比如關(guān)系的數(shù)據(jù)頁(yè)數(shù)，索引的數(shù)據(jù)頁(yè)數(shù)，基數(shù)等。
評(píng)估 predicates 選擇率和 project 輸出數(shù)據(jù)大小的計(jì)算公式。
評(píng)估執(zhí)行計(jì)劃算子的 CPU 和 I/O代價(jià)的計(jì)算公式，這些公式需要考慮輸入數(shù)據(jù)的統(tǒng)計(jì)信息，輸入數(shù)據(jù)的物理實(shí)現(xiàn)方法，輸入數(shù)據(jù)流的可用排序順序
代價(jià)模型使用以上的能力來(lái)自底向上的風(fēng)格來(lái)計(jì)算計(jì)劃，來(lái)獲取以下信息：
算子數(shù)據(jù)輸出流的記錄數(shù)
數(shù)據(jù)輸出流的新創(chuàng)建的排序或者傳遞的已有排序
評(píng)估執(zhí)行算子的代價(jià)（包含累計(jì)代價(jià)）
System-R的迭代算法有兩個(gè)重要的設(shè)計(jì)，動(dòng)態(tài)規(guī)劃和interesting orders
動(dòng)態(tài)規(guī)劃的本質(zhì)上是，最優(yōu)子結(jié)構(gòu)。就是為了得到包含k個(gè)join的SPJ查詢(xún)，只需要考慮k-1個(gè)join的的最優(yōu)計(jì)劃是哪些，之后拓展一個(gè)join，就能獲得k個(gè)join的SPJ查詢(xún)的最優(yōu)，而不用考慮k-1個(gè)join的的最優(yōu)計(jì)劃的細(xì)節(jié)。動(dòng)態(tài)規(guī)劃是很有效的算法，從O(n!)時(shí)間復(fù)雜度減少到（ 2 的n-1次方 ）
第二個(gè)System-R優(yōu)化器重要設(shè)計(jì)是interesting orders，考慮{R1, R2, R3}三個(gè)關(guān)系的join，join的條件是R1.a, R2.a, R3.a。對(duì)于{R1, R2}的join，采用nested loop的代價(jià)是x，采用sort-merge的代價(jià)是y。x<y。對(duì)于{R1, R2, R3}就不會(huì)考慮{R1, R2}使用sort-merge的計(jì)劃。
假設(shè){R1, R2}使用sort-merge join，那么join結(jié)果是根據(jù)字段a有序。這樣的有序會(huì)大大減少和R3 join的代價(jià)。因此提前把{R1, R2}的sort-merge join裁剪掉會(huì)導(dǎo)致次優(yōu)計(jì)劃的產(chǎn)生。這個(gè)問(wèn)題產(chǎn)生的本質(zhì)是{R1, R2} sort-merge join會(huì)產(chǎn)生出排序，這個(gè)對(duì)于后續(xù)是有利的，但是nested loop沒(méi)有這樣的順序。因此System-R會(huì)記錄對(duì)于計(jì)劃有意義的排序，也叫interesting orders。這個(gè)interesting orders在《The Volcano Optimizer Generator: Extensibility and Efficient Search》被稱(chēng)作是物理屬性。物理屬性不被所有的邏輯計(jì)劃共有，但是可以影響子樹(shù)的代價(jià)。
盡管System-R設(shè)計(jì)優(yōu)雅，這個(gè)框架不太容易拓展轉(zhuǎn)換規(guī)則來(lái)增大搜索空間。所以就有了更利于拓展的架構(gòu)設(shè)計(jì)，代價(jià)優(yōu)化，動(dòng)態(tài)規(guī)劃，interesting orders深深地影響了數(shù)據(jù)庫(kù)優(yōu)化器的發(fā)展。
4. 搜索空間
就像第二部提到的，搜索空間的大小取決于
保留相同語(yǔ)義的關(guān)系代數(shù)轉(zhuǎn)換數(shù)量
優(yōu)化器支持的物理實(shí)現(xiàn)算子
關(guān)系代數(shù)轉(zhuǎn)換并不一定會(huì)減少代價(jià)，因此也要經(jīng)過(guò)基于代價(jià)的處理器獲得最優(yōu)計(jì)劃。
優(yōu)化器在優(yōu)化查詢(xún)的不同階段會(huì)使用不同的方式去表達(dá)查詢(xún)。最開(kāi)始會(huì)是一個(gè)查詢(xún)的抽象語(yǔ)法樹(shù)，最后是一個(gè)算子計(jì)劃樹(shù)，中間使用邏輯的算子樹(shù)（也叫做查詢(xún)樹(shù)）來(lái)表達(dá)關(guān)系代數(shù)。
有些系統(tǒng)使用面向代數(shù)的方式來(lái)表現(xiàn)查詢(xún)的結(jié)構(gòu)，對(duì)于SPJ查詢(xún)，這樣的結(jié)構(gòu)就是一個(gè)查詢(xún)圖，節(jié)點(diǎn)代表關(guān)系，邊代表join predicates，如圖3。
4.1 算子間交換（Commuting Between Operators）
有很多重要的轉(zhuǎn)換類(lèi)探索操作符間的可交換性
4.4.1 歸納join順序
在很多系統(tǒng)中，join算子順序的會(huì)被限制來(lái)減少搜索空間。比如在System R中，只支持線性join連接順序，笛卡爾的操作要延遲到j(luò)oin之后進(jìn)行。
因?yàn)閖oin滿(mǎn)足交換律和結(jié)合律，所以join不一定是線性 join順序，也可以如圖2b的濃密樹(shù)的方式，濃密樹(shù)的方式需要產(chǎn)生中間物化關(guān)系。濃密樹(shù)有可能會(huì)降低代價(jià)，但是會(huì)增加搜索空間。
延遲操作笛卡爾積到j(luò)oin之后，同樣會(huì)產(chǎn)生性能問(wèn)題，比如在星型查詢(xún)中，在維表之間的笛卡爾積可以大幅減少代價(jià)。
在一個(gè)可拓展的系統(tǒng)中，join優(yōu)化迭代可以是自適應(yīng)的。根據(jù)查詢(xún)來(lái)限制是否使用濃密樹(shù)優(yōu)化，或者是否禁用笛卡爾積。
4.1.2 外部連接和連接
單側(cè)的outer join是不對(duì)稱(chēng)的操作符，會(huì)保留單邊關(guān)系的所有元組。對(duì)稱(chēng)的outer join會(huì)保留關(guān)系中的左右元組。
(R LOJ S）會(huì)保留R關(guān)系中所有元組，LOJ就是left outer join。不像自然連接，對(duì)于一系列的 outer joins 和自然連接是不能自由交換的。但是當(dāng) （R, S）根據(jù)斷言自然連接。（S, T）根據(jù)斷言外部連接，可以進(jìn)行下面的結(jié)合：
Join(R, S LOJ T) = Join (R,S) LOJ T
如果如上的結(jié)合律可以重復(fù)執(zhí)行，我們就可以在LOJ之前獲自然連接的Join (R,S)，對(duì)于Join (R,S)就可以自由進(jìn)行交換律。
4.1.3 Group-By 和 Join
SPJ查詢(xún)?cè)趥鹘y(tǒng)的執(zhí)行中，一般會(huì)在Group-By之前，有一種優(yōu)化技術(shù)是將Group-By下推到Join之前，這樣可以大幅減少join的元組數(shù)量，因?yàn)镚roup-By的每個(gè)分區(qū)只會(huì)產(chǎn)出一行元組。對(duì)于SELECT DISTINCT語(yǔ)句也是有效的，因?yàn)镾ELECT DISTINCT是一種特殊的Group-By。下推后的Group-By如果有索引，就可以通過(guò)索引低代價(jià)執(zhí)行。
4.2 合并多 Block 查詢(xún)到單 Block
4.2.1 合并視圖
設(shè)想鏈接查詢(xún)，查詢(xún)中使用了一個(gè)或者多個(gè)view，對(duì)于view可以進(jìn)行展開(kāi)來(lái)得到單Block。比如查詢(xún)
query Q = Join(R,V) view V = Join(S,T)，可以展開(kāi)為
Join(R, Join(S,T)
展開(kāi)后可以自由進(jìn)行交換律。
對(duì)于views更復(fù)雜時(shí)，就不能進(jìn)行簡(jiǎn)單的展開(kāi)了，比如views包含SELECT DISTINCT，需要將DISTINCT消除或者上拉，這個(gè)步驟需要注意保持?jǐn)?shù)據(jù)的重復(fù)度（duplicates）。當(dāng)展開(kāi)后可以自由交換join 或者 Group-By進(jìn)行優(yōu)化。就是圖4b 到 圖4a。
4.2.2 合并嵌套子查詢(xún)
考慮如下的子查詢(xún)
如果按照元組迭代語(yǔ)義來(lái)響應(yīng)這個(gè)查詢(xún)，對(duì)于Dept關(guān)系中的每個(gè)元組，子查詢(xún)都需要執(zhí)行一遍。如果子查詢(xún)沒(méi)有引用外部的變量，即非相關(guān)子查詢(xún)，那么子查詢(xún)只需要執(zhí)行一次就好了。如果子查詢(xún)使用了外部的變量，就是相關(guān)子查詢(xún)，對(duì)于上面的查詢(xún)，Emp.Emp#就是這個(gè)相關(guān)變量。對(duì)于這種子查詢(xún)可以解嵌套和打平（flatten）成一個(gè)查詢(xún)，如下
如果子查詢(xún)有quantifiers（比如 ALL, EXISTS），聚合，或者其他，解嵌套會(huì)更復(fù)雜一些。最簡(jiǎn)單的情況就是上面的情況，相同語(yǔ)義的轉(zhuǎn)換是
Somijoin(Emp,Dept,Emp.Dept# = Dept. Dept#) =
Project(Join(Emp,Dept), Emp.*)
其中 Join (Emp, Dept) 的鏈接條件是 Emp.Dept# =Dopt . Dept# ，Emp.*表明要保留所有的列。
當(dāng)子查詢(xún)中有聚合的時(shí)候會(huì)解嵌套更復(fù)雜一些，提升聚合時(shí)要保留相同的語(yǔ)義，如下查詢(xún)
可以轉(zhuǎn)換成如下
4.3 使用類(lèi)似Semijoin技術(shù)來(lái)優(yōu)化Multi-Block查詢(xún)
示例如下查詢(xún)
對(duì)于上面的查詢(xún)，對(duì)于E和D之間的連接，因?yàn)橛袟l件
E.age <30
AND D.budget > lOOk
所以可以先進(jìn)行連接，減少E.did的數(shù)量，這樣group by的時(shí)候就會(huì)減少計(jì)算量，可以進(jìn)行如下改造，比如首先創(chuàng)建部分結(jié)果partialresult
之后使用上面的 **partialresult **創(chuàng)建 Filter
之后根據(jù) did Filter 和Emp連接，計(jì)算平均sal 進(jìn)行限制
最后再進(jìn)行查詢(xún)
上面用到的技術(shù)，可以用在multi-block的包含view的查詢(xún)中，主要是想避免仕途或者嵌套子查詢(xún)中重復(fù)多余的計(jì)算。當(dāng)然也是進(jìn)行權(quán)衡，就是計(jì)算view的代價(jià)和這個(gè)view能減少的代價(jià)，哪個(gè)收益更高。
上面的轉(zhuǎn)換優(yōu)化可以使用Semi-Join，見(jiàn)論文《Cost Based Optimization for Magic: Algebra and Implementatio》，當(dāng)然也有更簡(jiǎn)單的做法，就是將斷言盡量下推，見(jiàn)論文《Query Optimization by Prcdicatc Move-Aroun》
5. 統(tǒng)計(jì)信息和代價(jià)估計(jì)
對(duì)于一個(gè)查詢(xún)，有很多邏輯等價(jià)的關(guān)系代數(shù)表達(dá)式，遍歷可能使用的關(guān)系代數(shù)空間和確定消耗最少資源的計(jì)劃是復(fù)雜的問(wèn)題。資源包括 CPU 時(shí)間，I/O代價(jià)，內(nèi)存，通信帶寬，也有可能是這些的組合。因此給定查詢(xún)的算子樹(shù)，能夠準(zhǔn)確和高效的評(píng)估它的代價(jià)是很重要的基礎(chǔ)。代價(jià)估計(jì)應(yīng)該是準(zhǔn)確的，因?yàn)檫@決定了優(yōu)化器是否準(zhǔn)確。代價(jià)估計(jì)應(yīng)該是高效的，因?yàn)樵賰?yōu)化過(guò)程中會(huì)循環(huán)多次調(diào)用。
System-R 基礎(chǔ)代價(jià)估計(jì)框架如下：
- 收集已存數(shù)據(jù)的統(tǒng)計(jì)信息摘要
- 給定算子和算子輸入流的統(tǒng)計(jì)信息摘要，可以計(jì)算如下信息
a. 算子輸出流的統(tǒng)計(jì)信息摘要
b. 算子執(zhí)行的代價(jià)估計(jì)
第2步會(huì)迭代的探索算子樹(shù)的任意深度來(lái)推導(dǎo)每個(gè)算子的代價(jià)，當(dāng)每個(gè)算子的代價(jià)都估計(jì)出來(lái)后，就能得到整個(gè)算子樹(shù)的代價(jià)。
統(tǒng)計(jì)信息屬性和計(jì)劃的代價(jià)是不一樣的。統(tǒng)計(jì)信息屬性是邏輯屬性，就是對(duì)于同一個(gè)查詢(xún)的不同計(jì)劃是一樣的。而代價(jià)是物理屬性，對(duì)于同一個(gè)查詢(xún)的不同計(jì)劃，代價(jià)有可能是不同的。
5.1 數(shù)據(jù)的統(tǒng)計(jì)信息摘要
5.1.1 基礎(chǔ)數(shù)據(jù)的統(tǒng)計(jì)信息**
對(duì)于每個(gè)表，必要的統(tǒng)計(jì)信息包含如下幾部分：
- 數(shù)據(jù)流中的元組數(shù)量（據(jù)此可以估計(jì)scan，join等代價(jià)和它們的內(nèi)存消耗）
- 表使用的物理頁(yè)數(shù)
- 列的統(tǒng)計(jì)信息（估計(jì)此列斷言的選擇率）
基于列的數(shù)據(jù)分布信息是通過(guò)直方圖提供的。直方圖有等寬和等高不同的類(lèi)別，對(duì)于等高直方圖，會(huì)把所有的元組（n個(gè)元組）分成k個(gè)桶，每個(gè)桶的元組數(shù)相同，那么每個(gè)桶就有n/k個(gè)元組。
在論文《Improved Histograms for Selectivity Estimation of Range Predicate》中論述了這種直方圖對(duì)于數(shù)據(jù)高度或者低度傾斜是有效的。
除了直方圖，min-max值統(tǒng)計(jì)信息也很有用，實(shí)踐中，次最大和次最小的值經(jīng)常會(huì)用到，因?yàn)樽畲笾底钚≈灯钐唷?/p>
每列的基數(shù)也是很有用的統(tǒng)計(jì)信息。
雖然直方圖提供了單列的統(tǒng)計(jì)信息，但是并沒(méi)有統(tǒng)計(jì)列之間的相關(guān)性。為了計(jì)算相關(guān)性，需要列的聯(lián)合分布信息。這個(gè)分布空間會(huì)很大。因此一些系統(tǒng)只是提供了disctinct的值對(duì)的信息.
5.1.2 基礎(chǔ)數(shù)據(jù)的統(tǒng)計(jì)估計(jì)
企業(yè)級(jí)數(shù)據(jù)庫(kù)有很多庫(kù)和大量的數(shù)據(jù)，準(zhǔn)確和高效的統(tǒng)計(jì)信息很重要，所以就需要進(jìn)行采樣，挑戰(zhàn)就是如何減少采樣帶來(lái)的估計(jì)錯(cuò)誤問(wèn)題。
5.1.3 統(tǒng)計(jì)信息的傳播計(jì)算
在基礎(chǔ)數(shù)據(jù)上進(jìn)行統(tǒng)計(jì)信息是不夠的，因?yàn)椴樵?xún)會(huì)包含很多算子，因此，基于統(tǒng)計(jì)信息在算子間進(jìn)行估計(jì)很重要。
最簡(jiǎn)單的統(tǒng)計(jì)估計(jì)是selection算子。如果查詢(xún)一張表上的A列，同時(shí)A列上有直方圖統(tǒng)計(jì)信息，可以用直方圖進(jìn)行統(tǒng)計(jì)信息估計(jì)。在這個(gè)過(guò)程中有2點(diǎn)會(huì)導(dǎo)致誤差。
- 查詢(xún)A列的值是單個(gè)桶的子集，這樣會(huì)有一定誤差
- 列之間是有相關(guān)性的，如果對(duì)多個(gè)列進(jìn)行斷言過(guò)濾，就假定列之間是獨(dú)立的，有的系統(tǒng)會(huì)選擇多個(gè)列中的最大選擇率的列統(tǒng)計(jì)信息
如果沒(méi)有統(tǒng)計(jì)信息的話，一般按照《Access Path Selection in a Relational Database System. In Readings in Database System》論文進(jìn)行估算
5.2 代價(jià)計(jì)算
代價(jià)估計(jì)階段會(huì)計(jì)算算子代價(jià)。代價(jià)模型估計(jì)CPU，I/O，在分布式系統(tǒng)中還會(huì)估計(jì)通信代價(jià)。在大多的系統(tǒng)中會(huì)組合使用來(lái)比較等價(jià)計(jì)劃。選擇一組合適的指標(biāo)來(lái)計(jì)算代價(jià)需要仔細(xì)斟酌。
早期的研究中除了上面這些屬性來(lái)計(jì)算代價(jià)，還包含使用緩存的命中率，比如對(duì)于nested loop join的算子，如果是index scan的內(nèi)存緩存可以大幅減少代價(jià)。代價(jià)估算再查詢(xún)優(yōu)化器中一直是很難的部分。
6. 枚舉架構(gòu)
對(duì)于給定的查詢(xún)，枚舉算法需要遍歷搜索空間來(lái)選擇一個(gè)廉價(jià)的執(zhí)行計(jì)劃。System-R的設(shè)計(jì)是只考慮線性join順序的優(yōu)化。
對(duì)于工程師來(lái)說(shuō)，需要設(shè)計(jì)一種枚舉計(jì)劃的架構(gòu)，可以?xún)?yōu)雅的添加一種轉(zhuǎn)換規(guī)則或者物理實(shí)現(xiàn)來(lái)拓寬搜索空間。也可以?xún)?yōu)雅地調(diào)整代價(jià)模型。最近的優(yōu)化器架構(gòu)是可拓展的設(shè)計(jì)，拓展性的同時(shí)需要權(quán)衡高效。
介紹兩種不同的設(shè)計(jì)類(lèi)型的優(yōu)化器，Starburst和Volcano/Cascades，盡管他們有不同的設(shè)計(jì)，他們的相同點(diǎn)是
- 算子會(huì)使用計(jì)算代價(jià)函數(shù)和物理屬性
- 使用規(guī)則引擎來(lái)改變查詢(xún)表達(dá)式或者算子
- 預(yù)留拓展點(diǎn)，可以改變枚舉框架的行為
6.1 Starburst
使用QGM（Query Graph Model）來(lái)表示關(guān)系代數(shù)
- 查詢(xún)改寫(xiě)階段，使用規(guī)則把QGM轉(zhuǎn)換成另外等價(jià)的QGM，在這個(gè)階段沒(méi)有代價(jià)信息
- 計(jì)劃優(yōu)化階段，使用grammar-like的語(yǔ)言，join枚舉器類(lèi)似于*System-R *的自下向上的枚舉框架
6.2 Volcano/Cascades
Volcano 和 Cascades拓展的架構(gòu)是Exodus的衍生體。在這些系統(tǒng)里，規(guī)則被用來(lái)拓展搜索空間。
有兩種類(lèi)型的規(guī)則，轉(zhuǎn)換規(guī)則和實(shí)現(xiàn)規(guī)則。
為了高效，Volcano 和 Cascades使用自上而下的動(dòng)態(tài)規(guī)劃（這個(gè)過(guò)程也叫memoization）。當(dāng)執(zhí)行優(yōu)化任務(wù)的時(shí)候會(huì)通過(guò)邏輯和物理屬性進(jìn)行校驗(yàn)任務(wù)是否執(zhí)行過(guò)。如果沒(méi)執(zhí)行過(guò)，有可能執(zhí)行轉(zhuǎn)換規(guī)則，物理實(shí)現(xiàn)規(guī)則，或者使用enforcer來(lái)改變數(shù)據(jù)流的屬性。在優(yōu)化的每一步使用promise來(lái)決定下一步要進(jìn)行什么操作。
Volcano 和 Cascades框架和Starburst不同的是：
a. 這些系統(tǒng)沒(méi)有使用兩種不同的優(yōu)化階段，因?yàn)樗械霓D(zhuǎn)換都是關(guān)系代數(shù)和基于代價(jià)的
b. 從關(guān)系代數(shù)到物理的映射發(fā)生在單獨(dú)的步驟
c. 和Starburst的通過(guò)鏈?zhǔn)綀?zhí)行規(guī)則不同，Volcano 和 Cascades是代價(jià)減少為目標(biāo)的規(guī)則使用
7. 基礎(chǔ)拓展
以上是優(yōu)化器基礎(chǔ)的組件。這部分描述一些高級(jí)議題。
7.1 分布式和并行數(shù)據(jù)庫(kù)
分布式數(shù)據(jù)庫(kù)需要引進(jìn)了節(jié)點(diǎn)通信代價(jià)，可以通過(guò)移動(dòng)數(shù)據(jù)和為中間算子選擇節(jié)點(diǎn)來(lái)拓展搜索空間。早期的工作專(zhuān)注于減少通信代價(jià)。隨著時(shí)間推移，分布式數(shù)據(jù)庫(kù)架構(gòu)衍生為副本數(shù)據(jù)庫(kù)或者并行數(shù)據(jù)庫(kù)來(lái)擴(kuò)容。在副本數(shù)據(jù)庫(kù)中保持副本間的數(shù)據(jù)一致性是一個(gè)很重要的議題。
不像分布式數(shù)據(jù)庫(kù)，并行數(shù)據(jù)庫(kù)的行為就像一個(gè)單獨(dú)的系統(tǒng)，通過(guò)并行執(zhí)行來(lái)降低查詢(xún)響應(yīng)時(shí)間。
并行處理有幾個(gè)好處，比如數(shù)據(jù)的物理分布有可能根據(jù)分區(qū)或者備份至幾個(gè)節(jié)點(diǎn)，允許獨(dú)立的處理數(shù)據(jù)。并行處理可以并行處理獨(dú)立的算子或者流水線（通過(guò)把生產(chǎn)者和消費(fèi)者分布在不同節(jié)點(diǎn)上）。壞處就是并行需要在節(jié)點(diǎn)之間通信來(lái)交換數(shù)據(jù)
高效地對(duì)物理算子進(jìn)行調(diào)度給優(yōu)化器帶來(lái)新的挑戰(zhàn)。
7.2 用戶(hù)自定義函數(shù)
存儲(chǔ)過(guò)程（也叫用戶(hù)定義函數(shù)）在關(guān)系型數(shù)據(jù)庫(kù)廣泛使用。提供了一種機(jī)制，可以減少客戶(hù)端和服務(wù)器的通信。
隨之也帶來(lái)了問(wèn)題，比如用戶(hù)定義函數(shù)的代價(jià)評(píng)估。見(jiàn)《Optimization of Queries with Userdefined Predicate》
解決了用戶(hù)定義函數(shù)的優(yōu)化問(wèn)題只是第一步，還有ADTs對(duì)于查詢(xún)?cè)趺催M(jìn)行優(yōu)化。
7.3 物化視圖
物化視圖是視圖的結(jié)果進(jìn)行物化存儲(chǔ)。之后被優(yōu)化器使用。對(duì)于優(yōu)化器的挑戰(zhàn)是給定一部分物化視圖，怎么用物化視圖來(lái)改寫(xiě)查詢(xún)和查詢(xún)使用無(wú)話改寫(xiě)的高效性。
7.4 其他優(yōu)化項(xiàng)
排序優(yōu)化《Fundamental Techniques for Order Optimization》等
8. 結(jié)論
優(yōu)化不僅僅是轉(zhuǎn)換和查詢(xún)等價(jià)，構(gòu)建優(yōu)秀的SQL轉(zhuǎn)換，代價(jià)估計(jì)，枚舉框架都很有挑戰(zhàn)。核心挑戰(zhàn)問(wèn)題依然在，了解目前現(xiàn)有的優(yōu)化技術(shù)對(duì)于未來(lái)對(duì)優(yōu)化做貢獻(xiàn)也是必要的。
