啃論文俱樂部——分布式查詢優(yōu)化的歷史與現(xiàn)狀
1984—關于分布式查詢優(yōu)化
該部分為1984的分布式查詢優(yōu)化綜述概括，介紹了分布式數(shù)據(jù)庫中優(yōu)化查詢的各種技術。雖然沒有涵蓋這個主題上所有提出的算法，但概述了從現(xiàn)有算法中提取的相當多的想法。
運營和成本措施
假設關系數(shù)據(jù)庫中的關系分布在不同的站點。本文中使用的關系數(shù)據(jù)操作包括投影、選擇、連接和半連接。
- 投影：選擇符合關系的列。
- 選擇：選擇符合關系的元組（行）。
- 連接：就是將兩個表合并，然后選擇出滿足關系的元組。
半連接：屬性A上從關系R2到關系R1的半連接用
表示。其中R2是發(fā)送關系，R1是簡化關系，A是連接屬性。有時使用
來表示
它可以通過將屬性A上的R2和R1連接起來，然后將得到的關系投影到R1的模式上而得到，半連接在數(shù)據(jù)庫機器中很有用。如果關系不被分割，那么在投影和選擇中，只涉及本地處理成本。但是，執(zhí)行連接和半連接時，除了本地處理成本之外，還會產生不同站點之間的通信成本。例如，如果R1和R2在不同的站點，R1必須發(fā)送到包含R2的站點。或者R2必須被發(fā)送到R1的站點才能進行操作。本地處理成本通常根據(jù)磁盤訪問次數(shù)和cpu的處理時間來評估，而通信成本是以傳輸?shù)臄?shù)據(jù)總量來表示的。但本地處理成本對本地網絡更為重要。在此主要認為網絡是地理上分散的計算機網絡。
我們假設從一個站點向另一個站點傳輸一定數(shù)量的數(shù)據(jù)(比如X)的成本是c0 + c1* X，其中c0是啟動傳輸?shù)膯映杀?，c1是比例常數(shù)。回答一個查詢的成本可以用總成本或響應時間來表示。
在上圖圖（a）中，回答查詢所需的X個數(shù)據(jù)單元從站點1傳輸?shù)秸军c2，Y個數(shù)據(jù)單元從站點2傳輸?shù)秸军c3，總成本為(c0+c1* X)+(c0+c1* Y)= 2c0 + c1*(X + Y)。響應時間是從開始查詢到產生答案的時間。在上圖圖（b）中，來自站點1的X個數(shù)據(jù)單元和來自站點2的Z個數(shù)據(jù)單元被并行傳輸?shù)秸军c3以應答查詢，響應時間成本是c0+c1* X和c0 + c1*Z的最大值，在本文中，我們主要關注總成本測量。由于傳輸?shù)臄?shù)據(jù)量會影響策略的成本，因此有人嘗試降低成本。一個可能的方法是利用半連接。
比如在上圖圖（a）中從屬性B上的關系R2到關系R1的半連接可以將R2投影到屬性B上，然后將投影的結果與R1 連接得到，可以看出得到的結果比原來的R1小得多。
在c0比較小的情況下，這種半連接是合理的。但在另一方面，在上圖圖（b）中，如果R1，R2之間的共同值很多，使用半連接可能不劃算，所以在執(zhí)行半連接之前，最好能估計兩個關系之間共同值的數(shù)量。
估計
從上文可以看出，分布式的性能查詢處理算法的性能在很大程度上取決于某些中間關系的大小。因此，選擇合理的估計算法是極其重要的。
半連接后，R1投影在b屬性上的問題可以用下面的球顏色問題來證明:“有n個球，有m種不同顏色。如果從n個球中隨機選擇t個球，求出顏色的期望值?！笨梢缘玫较铝泄剑?/p>
如果該公式以現(xiàn)在的形式計算，它的計算成本將會變得很大，并且t值較大時可能導致溢出。
一個半連接策略也可以看作有向圖，通過有向圖也可以估算出預期數(shù)量。
將半連接策略看作一個有向圖，其中頂點是Ri到Rj之間的關系。有向邊表示從Ri到Rj的半連接,即Ri->Rj。首先執(zhí)行的半連接是那些入度為0的節(jié)點的半連接。然后，產生簡化Rj，用表示。然后就是-> ，入度變?yōu)榱?，那么將會被?zhí)行。顯然，半連接策略中不會出現(xiàn)有向環(huán)。
假設有三個關系R1、R2和R3，每個都有屬性值A和B。在以上策略中，R1-B->R2-A->R3和R2-B->R1-A->R3在執(zhí)行半連接后得到的關系是不相等的，因此，在一個半連接策略中計算關系的大小，必須要了解操作的過程。
三個階段
分布式查詢的處理可以分為三個階段:副本識別階段、簡化階段和組裝階段。
在副本識別階段，出現(xiàn)在查詢限定中的每個關系的一個或多個副本被識別，并將用于處理查詢。由于分布式數(shù)據(jù)庫系統(tǒng)可能包含一些關系的復制副本，所以為了最小化傳輸成本而識別關系的適當副本可能不是一個容易的過程。
在簡化階段，半連接通常用于消除不滿足查詢條件的關系元組并且要求最大化地減少成本。例如，對于前面引用的具有關系副本的最佳選擇的查詢，可以執(zhí)行半連接來消除一些元組，而不會產生通信成本。如果半連接的結果不是最優(yōu)結果，則可以執(zhí)行其他半連接以減少成本。
在組裝階段，查詢得到的結果關系被發(fā)送到一個站點，以產生用戶所要求的輸出。
我們要指出的是﹐將查詢處理策略分離成三個階段只是傾向于簡化所涉及的概念。一個合理的選擇關系副本的策略是找到包含所選關系副本的最小平均數(shù)的站點。不幸的是，這也是一個NP-complete問題，即最難的決定性問題。然而，由于查詢引用的關系數(shù)量和包含這些關系的站點數(shù)量通常較少﹐通過列舉找到站點的數(shù)量不需要很多時間。減少階段和組合階段將在后文中詳細描述。
樹查詢與循環(huán)查詢
特征:只有某些類型的查詢可以使用半連接解決。更準確地說，如果不滿足查詢限定條件的所有元組都被消除，那么投影的關系將被完全減少。如果使用半連接來減少關系，可能會產生較少的通信成本。但是查詢中出現(xiàn)的關系可能沒有完全減少。因此，組裝關系的溝通成本仍然很高。因此，需要對可以通過半連接完全減少的查詢類型進行精確的描述。
樹狀查詢圖：關系的查詢圖可以轉換成樹狀的。如果查詢圖不是樹形的﹐那么這就是一個循環(huán)查詢。如前所述,如果查詢是樹狀查詢﹐樹狀查詢的關系可以通過半連接完全減少﹐但循環(huán)查詢無法通過半連接完全減少。這說明了識別出該查詢是否樹狀查詢的重要性。
有一種簡單的算法可以識別，如下所示。該算法將一個查詢作為輸入，他有兩個關鍵步驟，最初，對于每個關系Rt，構造條件中出現(xiàn)的關系的屬性集J(Rt)。如前所述，假設存在三種關系R1 R2 R3.
第一步，假設存在某種關系，這個關系保證了可以通過替換表格中的每個子元組來構造等價替換。替換后Ri只出現(xiàn)在關系Ri.X=Rj.X中。很明顯，在查詢圖中，Ri與Rj變成了相鄰，而不屬于任何循環(huán)。因此，消除R不會改變查詢圖的類型。在圖7中，R3的A2屬于R1，將R3到R4的邊替換為R1到R4的邊(以及R1到R3的邊)。因此，R3不屬于任何周期，可以在不影響查詢類型的情況下消除它。
第二步，如果在第1步中消除了任何關系，則檢查它是否導致了某個屬性的消除。如果一個屬性只剩下一個包含該屬性的關系，則該屬性將被刪除。（如果一組關系包含相同的屬性，它們之間的關系是由該屬性的相等性決定的;因此，如果沒有一個以上的關系具有該屬性，那么這種關系就不存在。) 很明顯，刪除一個屬性會導致關系R的更新。如果在算法結束時消除了所有關系，那么原始查詢就是樹查詢，因為算法不影響查詢的類型(樹查詢或循環(huán)查詢)，而null查詢顯然是樹查詢。如果在算法的最后確實存在一些關系，那么可以表明原始查詢是一個循環(huán)查詢。
將循環(huán)查詢轉換為樹查詢
因為樹查詢是完全可約的，所以能夠將循環(huán)查詢轉換成樹查詢的算法是合乎需要的. 基本上，有三種不同的變換算法:
（1）關系合并算法。
（2）tuplewise分解算法。
（3）屬性添加算法。
關系合并算法簡單地連接存在于循環(huán)中的某些關系以消除循環(huán)。例如，給定下圖圖（a）所示的循環(huán)查詢，該算法可以連接循環(huán)中的任意兩個關系。這導致循環(huán)消失。下圖圖（b）顯示了將R1和R2連接在一起的查詢圖。
元組式分解算法：
R1thm算法基于Wong和Youssefi的元組替換思想。該算法通過將一個循環(huán)查詢分解成多個樹子查詢來消除循環(huán)。
（3）屬性添加算法：
循環(huán)中涉及的一些關系的某些屬性被添加到其他關系中，從而產生樹查詢。然后通過半連接來完全簡化任何給定的關系。
簡單查詢的最佳策略
在還原階段描述的查詢處理算法都是啟發(fā)式的﹐不一定能產生最優(yōu)策略。在這一節(jié)中﹐提出了一個簡單查詢的最優(yōu)算法（在這種查詢的限定中出現(xiàn)的所有關系都有相同的屬性﹐并且每個關系都有一個屬性)。
一個策略的成本是執(zhí)行邊所代表的半連接的數(shù)據(jù)傳輸成本之和。由于在策略執(zhí)行前不可能找到策略的精確成本，通常的程序是使預期成本最小化。
對于簡單查詢，優(yōu)化策略可以滿足某些屬性。它們的列表如下:所有關系都應該出現(xiàn)在一個方向上。有兩種情況。在第一種情況下，結果站點是包含R1、R2 . . . . . Rn。在另一種情況下，站點不包含這n種關系中的任何一種。
如果結果位點不包含這n種關系中的任何一種，那么最優(yōu)策略中的所有關系都是不同的;也就是說，關系不會出現(xiàn)超過一次。這個結論是相當明顯的，因為如果一個關系出現(xiàn)兩次或兩次以上，那么該關系的第二次和后續(xù)的出現(xiàn)就可以從該策略中移除，產生一個等價但成本更低的策略。因此，最優(yōu)策略實際上是R1、R2 . . . . . Rn。對于簡單的查詢，可以容易地獲得最佳策略。
TREG查詢的最優(yōu)策略
在此只說明一種情況，以獲得最佳策略來完全減少樹狀查詢的尖系。其限制條件是任何兩個關系最多只有一個共同的連接屬性。
基于半連接的啟發(fā)式算法
討論兩種使用半連接的查詢處理算法。它們假設查詢引用的每個關系的一個副本已經被選擇，然后執(zhí)行簡化和組裝階段。
第一種半連接X-A-Y的成本定義為將X.A從包含A的站點轉移到包含Y的站點的成本(如果兩個站點相同，成本為零)。半連接的好處是操作前Y的大小減去操作后Y的大小。如果成本小于收益，那么這個半連接是有利可圖的。
減少階段是非常簡單的﹔它確定了任何兩個關系之間所有可能的半連接。每個半連接的成本和收益都被估算出來。然后選擇一個具有最小成本的有利的半連接。
那些可能被半連接策略影響的成本和收益不斷更新，并涉及了接下來的半連接。這個過程重復進行，直到找不到有利的半連接為止。
基于連接的算法
雖然半連接的使用減少了數(shù)據(jù)傳輸?shù)臄?shù)量，但它并不總是最優(yōu)解。一個原因是，對于某些網絡，交換的消息數(shù)量可能更重要，而不是傳輸?shù)臄?shù)據(jù)量。
畢竟當使用半連接時，可能會生成額外的消息。另一個原因是，本地處理成本可能會非常高。最后，盡管半連接可以并行執(zhí)行，但使用半連接的效應時間最小化是很復雜的。
第二種：有教授提出了一種算法，它是上文中給出的處理簡單查詢的最佳算法的推廣。該算法構造的策略是n個子策略的并集，每個子策略對應一個關系，其中n是查詢引用的關系數(shù)。考慮查詢的關系R。設A是R的一個連接屬性，尋找一個最佳的方法來簡化R，并只在屬性A上使用半連接將R發(fā)送到結果站點產生答案。
枚舉算法
該算法首先將查詢中的關系集劃分成兩個互補的組G1和G2，其中G1具有至少兩個關系，而G2具有零個或多個關系。接下來，通過將包含最大關系的站點指定為結果站點，并將G1中的所有其他關系發(fā)送給它，來獲得G1中的關系的子策略。它通過遞歸調用G2中的關系來尋找最小代價子策略。
假設關系R1、R2和R3位于不同的位置，并且查詢請求這三個關系的連接，算法會首先將R1、R2和R3劃分為{{R1, R2}， {R3}}。然后構造{R1， R2}的最小代價子策略，將兩個關系R1和R2中的較小的一個發(fā)送給另一個。將R1與R2的關系(例如T1)加入到第二組中，尋找{T1， R3}的最小代價子策略。然后得到R1、R2和R3的連接策略。重復相同的過程為{{R1, R3},{R2}},{{R2,R3}, {R1}},和 {{R1,R2,R3},{ }}。最后，得到查詢的最優(yōu)策略。
非數(shù)值算法
它將一個查詢分解為鏈式查詢﹐并解決它們以獲得答案。
鏈式查詢指的是其查詢圖是一條鏈的查詢。
一個給定的鏈式查詢被分解成多個子查詢，在兩個連續(xù)的子查詢之間最多只有一個共同變量。每個子查詢都是不可化簡的。我們假設關系不被分割﹐只考慮數(shù)據(jù)通信成本。如果一個子查詢是一個有兩個節(jié)點的鏈﹐比如Rx和Ry，那么要么Rx被發(fā)送到包含Ry的站點，要么Ry被發(fā)送到包含Rx的站點,這取決于哪個策略產生的成本更低。如果子查詢是一個循環(huán)查詢﹐那么就必須決定是一次性處理整個子查詢還是將其細分為若干部分。如果子查詢有以下情況﹐則對其進行細分來降低成本。
假設給定一個指定為根節(jié)點的鏈式查詢。該算法找到集合點﹐也就是查詢所引用的數(shù)據(jù)數(shù)量最多的站點。然后，該算法重復以下過程﹐直到得到鏈式查詢的答察。從一個葉子開始﹐算法先把葉子和它的父本連接起來，然后把結果發(fā)送到集合點﹐檢查是否比直接把兩個關系發(fā)送到集合點并在那里進行連接的成本要低。如果前一種策略的成本較低﹐那么葉子節(jié)點和它的父節(jié)點就會被合并﹐形成一個臨時關系﹐并且查詢圖被修改﹐用新創(chuàng)建的關系替換連接兩個關系的圖的部分。否則﹐葉子節(jié)點就會被送到裝配點，并從查詢圖中刪除。這個過程在修改后的查詢圖上重復進行。當兩個關系被連接時﹐算法將較小的關系發(fā)送到包含較大關系的站點并合并它們。
片段處理
一個關系可以被視為一個矩陣，其中行代表元組，列代表屬性。關系的水平片段是矩陣行的子集。它是通過對關系應用選擇操作獲得的。有時一個水平片段在一個站點被頻繁訪問，而另一個水平片段在另一個站點被頻繁引用。因此，根據(jù)它們的參考位置將片段分配給站點可能是有益的。
關系的垂直片段是關系的列的子集，并且通過使用關系上的投影運算來構造。這一節(jié)只討論水平碎片。這個方法中，引用分段關系的查詢首先被分解成子查詢。然后，使用第7節(jié)中描述的算法來獲得每個子查詢的答案。所有子查詢答案的并集就是該查詢的答案。
轉換方法
也許處理查詢的更系統(tǒng)的方法是轉換方法。在這種方法中，存在一組規(guī)則，其中每個規(guī)則將查詢表達式轉換成等價的表達式。這個想法是重復應用這些規(guī)則來獲得一個可以用很小的代價評估的表達式。通常，應用一元操作符(如project或select)后的結果關系往往比原始關系小，而應用二元操作符(如join或union)后的結果關系可能比原始操作數(shù)大得多。如果操作數(shù)在不同的位置，則可以通過應用一元操作符來減小它們的大小，同時保持表達式的等價性。
例如，在屬性B上加入RI(A, B, C)和R2(B, E, F)關系，然后將結果投影到屬性(A, B, E)上，相當于在屬性A和B上投影R1來消去C，在屬性B和E上投影R2來消去F，然后再將兩者的簡化關系進行連接。如果R1和R2在不同的位置，則后一種表達式可以用較少的數(shù)據(jù)傳輸來計算，因此更可取。
2021—:地理分布查詢處理方法
今天的全球化世界拓寬了數(shù)據(jù)分析應用的前景。大型組織在不同的站點上容納多個數(shù)據(jù)庫和IT基礎設施組織需要在不同的地點進行數(shù)據(jù)分析。以統(tǒng)一的方式支持地理分布式數(shù)據(jù)分析對組織的日常運營至關重要。本部分介紹了一個基于遵從性的查詢優(yōu)化器，該優(yōu)化器考慮了數(shù)據(jù)流策略，這些策略使用我們的策略表達式聲明性地指定，以生成遵從性的地理分布式執(zhí)行計劃。
前提例子
有一個公司名叫CarCO，它在三個地區(qū)擁有分公司。
它的總部在歐洲，同時在歐洲擁有多個辦事處。數(shù)據(jù)庫記為DN。
它有子公司在北美。數(shù)據(jù)庫記為DE。
供應商制造部門在亞洲。數(shù)據(jù)庫記為DA。
數(shù)據(jù)表為：
因為在實際的地理情況當中，數(shù)據(jù)的運輸被規(guī)則所約束，稱之為數(shù)據(jù)流約束。
假設CarCo公司不同地理位置的數(shù)據(jù)流為：
1.北美的客戶只有在壓制賬戶余額信息后才能發(fā)往國外。
2.只有聚合的訂單數(shù)據(jù)才能從歐洲發(fā)送到亞洲，訂單價格不能發(fā)送到北美。
3.只有從亞洲匯總的訂單數(shù)量和延伸價格才能發(fā)往歐洲。
這里的工作目標有兩個：
1.確定簡單有效的數(shù)據(jù)流策略。
2.設置優(yōu)化器。
關于數(shù)據(jù)流策略
定義
數(shù)據(jù)流策略指定了哪些信息以及這些信息可以合法傳輸?shù)姆绞胶臀恢谩?/p>
我們把數(shù)據(jù)流策略用
來表示
表示在D位置上的信息可以運輸?shù)轿恢肔D上。
政策規(guī)范
一種簡單而直接的指定方式——策略表達式。
兩個規(guī)定：
1.用屏蔽函數(shù)轉換數(shù)據(jù)（簡單表達式和聚合表達式）。
2.信息披露模式（指明什么數(shù)據(jù)不允許被發(fā)送）。
舉例一個查詢如下：
select C.name,sum(O.totprice),sum(S.quantity)
from Custom AS C,Orders AS O,Supply AS S
where C.custkey=O.custkey and O.ordkey=S.ordkey
group by C.name
該查詢表示查詢Custom表中的name屬性，Orders表中totprice的總和當C.custkey=O.custkey時以及Supply表中的quantity的總和當O.ordkey=S.ordkey時，并且以name屬性。
簡單表達式
假設該策略還允許將客戶的mktsegment和區(qū)域信息發(fā)送到CarCo的商業(yè)客戶的歐洲。我們可以使用以下策略表達式:
ship custkey,name from Customer C to Asia, Europe
ship mktseg, region from Customer C to Europe
where mktseg=‘commercial’
聚合表達式
雖然簡單的表達式足以表示各種各樣的數(shù)據(jù)流策略，但有些策略只允許傳遞聚合信息。
ship acctbal as aggregates sum, avg from Customer C
to * group by mktseg, region
兼容的優(yōu)化查詢處理
系統(tǒng)將策略存儲在策略目錄中，以進行查詢優(yōu)化。在查詢時，基于遵從性的查詢優(yōu)化器在枚舉計劃時使用這個策略編目(通過策略評估器)來驗證它們是否符合輸入數(shù)據(jù)流策略。優(yōu)化器使用這種驗證機制來知道最終查詢執(zhí)行計劃(QEP)何時違反了現(xiàn)有的數(shù)據(jù)流策略。如果是，則拒絕執(zhí)行查詢。只有當生成的QEP符合要求時，它才會繼續(xù)執(zhí)行查詢。
兼容的查詢處理框架依賴于兩個核心部分:(i)指定與每個數(shù)據(jù)位置相關的數(shù)據(jù)流策略，以及(ii)在這些策略下的查詢優(yōu)化過程。在下文中，我們將首先形式化數(shù)據(jù)流策略和遵從查詢計劃的概念，然后定義遵從查詢處理問題。
跨境數(shù)據(jù)流策略描述了跨組織和/或地理邊界傳輸數(shù)據(jù)的限制。一般來說，數(shù)據(jù)流策略指定了哪些信息以及這些信息可以合法傳輸?shù)姆绞胶臀恢谩?/p>
基于火山的優(yōu)化器生成器
1.引入了新的抽象邏輯屬性來注釋操作符。
執(zhí)行特征是一個邏輯屬性，描述操作符在哪里可以合法執(zhí)行，而運輸特征描述操作符的輸出在哪里可以合法運輸。
如該圖所示，節(jié)點3表示一個執(zhí)行特征，表示該執(zhí)行在北美被允許。
節(jié)點4表示運輸特征，節(jié)點3的結果可以運輸?shù)綒W洲和北美。
根據(jù)數(shù)據(jù)流策略，操作符節(jié)點可以有0個、1個或多個執(zhí)行和傳遞特征。
2.調整每個物理操作符的成本函數(shù)。
擴展了代價函數(shù)來考慮操作符的執(zhí)行特征，以防止優(yōu)化器丟棄操作符尚未注釋的計劃/子計劃。
3.引入了一組規(guī)則，允許我們以在計劃枚舉期間確定注釋。
它們使優(yōu)化器能夠在優(yōu)化過程中獲得計劃操作符的執(zhí)行和交付特征。優(yōu)化器通過其規(guī)則引擎將操作符節(jié)點與注釋規(guī)則進行匹配，以獲得其運輸和執(zhí)行特征。
四個注釋規(guī)則：
（1）假設一個操作符節(jié)點n有一個執(zhí)行特征
，那么l是合法操作執(zhí)行的位置。
（2）假設一個操作符節(jié)點n有一個執(zhí)行特征
，表示在操作的所有輸入都可以運到l處時，操作可以在強制在l處進行。例如，在美國加入來自歐洲和亞洲的數(shù)據(jù)，只有當這兩種數(shù)據(jù)都能合法運到美國時才執(zhí)行合法操作。
（3）假設一個操作符節(jié)點n有一個運輸特征
即運輸特征為運輸特征和執(zhí)行特征的并集，那么操作員的輸出總是可以合法地運送到合法執(zhí)行它的地點。
（4）假設一個操作符節(jié)點n有一個運輸特征
，該規(guī)則對屬于單個數(shù)據(jù)源的查詢子表達式調用策略評估。
計劃注釋器Plan Annotator——優(yōu)化第一階段
計劃注釋器的作用：接收邏輯計劃和基于遵從性的優(yōu)化目標作為輸入，以輸出帶注釋的QEP。
遵從以優(yōu)化目標為基礎：
將優(yōu)化目標設置為計劃向量，該向量指定非空運輸特性的需求，以及所需的物理屬性。
優(yōu)化過程
假設給定一個邏輯表達式和基于遵從性的優(yōu)化目標，計劃注釋器從初始表達式樹開始。計劃注釋器從一個初始表達式樹開始，通過Volcano的規(guī)則引擎反復應用規(guī)則來枚舉qep的搜索空間。
規(guī)則有：
1.代數(shù)等價規(guī)則。
2.邏輯運算符節(jié)點轉換為物理運算符節(jié)點的實現(xiàn)規(guī)則。
3.強制規(guī)則可以“強制”輸入具有特定的物理屬性。
該計劃注釋器依賴于Volcano的搜索引擎和基于成本的修剪，以確定成本最低的注釋計劃。
上圖即為一個優(yōu)化后的帶有注釋的QEP查詢圖
站點選擇器Site Selector——優(yōu)化第二階段
此時已經擁有一個帶注釋的QEP圖。
站點選擇器的作用是繼續(xù)放置操作符節(jié)點。
可能造成的后果：計劃成指數(shù)級增長。
又上述可知站點選擇器不宜使用貪婪方法和窮盡枚舉，而是使用動態(tài)規(guī)劃：一種記憶的遞歸自頂向下。
站點選擇器算法：
