1、Oracle中的增強子查詢優化這篇文章是我偶然在asktom上看到的，當時有人問子查詢合并（subquery coalescing），TOM給出了這篇文章的鏈接：我花了大約一周時間翻譯，有很多術語找不到相關翻譯就只好自己杜撰一個，根據自己的理解對一些難懂的地方做了注釋。如果你發現了錯誤請不吝指正。文中的例子非常值得一讀，目前我沒有時間去一一驗證哪些已由CBO實現，如果你都看懂了對提高自己的SQL技巧是非常有幫助的。插圖只上傳了前四個，后面的都是一些關于性能的圖表，自己看原文即可。Oracle中的增強型子查詢優化作者：Srikanth Bellamkonda ()   

2、60;  Angela Amor ()      Rafi Ahmed ()       Mohamed Zait ()      Andrew Witkowski ()      Chun-Chieh Lin ()            Oracle USA       500 Oracle Parkway

3、       Redwood Shores, CA, USA （版權歸原作者所有，未經許可不得轉載）摘要本文描述了ORACLE關系數據庫系統中的增強型子查詢優化。它討論了幾種技術子查詢合并，利用窗口函數（譯者注：即分析函數）的子查詢消除，對分組查詢的視圖消除(view elimination)。這些技術辨認出查詢結構中的冗余成分，并把它們去除，將查詢轉換為可能更加優化的形式。本文也討論了新型的并行執行技術，該技術應用廣泛，并可用來改善這些經過變換的查詢的可擴展性。它還描述了一種反連接（antijoin）的變種，用來優化在有空值的列上帶全稱量詞（譯者注：在

4、SQL中指ALL這類量詞）的查詢。它隨后演示了這些優化的結果，表明在執行速度上有著顯著的改善。1. 介紹當今的關系數據庫系統處理各種復雜的SQL查詢, 包括帶有聚合函數，UNION/UNION ALL, DISTINCT, 分組(GROUP BY)視圖等等的嵌套子查詢。這類查詢在決策支持系統(DSS)和在線分析處理系統(OLAP)中越來越重要。查詢變換是通常推薦的用于優化此類子查詢的技術。子查詢是SQL的一種強大的組件，大大擴展了它的聲明性和表達能力。SQL標準允許子查詢被使用在 SELECT, FROM, WHERE 和 HAVING 子句中。決策支持系統的基準測試 TPC-H 文獻14 和

5、 TPC-DS 文獻15大量使用了子查詢。TPC-H 基準測試的22個查詢中，差不多有一半用了子查詢。大部分是相關子查詢，很多都含有聚合函數。所以，高效地執行復雜子查詢對數據庫至關重要。1.1 ORACLE中的查詢變換Oracle執行很多種的查詢變換子查詢展開(譯者注：Subquery Unnesting, 指的是把ANY和EXISTS這類子查詢變成連接)，分組和DISTINCT視圖的合并(譯者注：group-by and distinct view merging, 指的是在帶有GROUP BY/DISTICNT的視圖/內聯視圖中，先和外層的表進行連接，過濾掉一些數據然后再做聚合操作)，相同

6、子表達式的消除(譯者注：common  sub-expression elimination, 指的是同樣的一個表達式出現多次，只需計算一次并多次引用計算結果)，連接謂詞下推(譯者注：join predicate pushdown，指的是把外層的連接條件推入里層從而達到預先過濾的目的)，連接因式分解(譯者注：join factorization, 指的是把UNION的兩個子查詢中的公共部分提取出來放到UNION之后做，類似提取公因式)，集合操作INTERSECT和MINUS到連接/反連接的轉換，OR謂詞的擴展(譯者注：OR expansion, 指的是把OR或者IN變成一系

7、列UNION ALL)，星型轉換(譯者注：star transformation, 用于數據倉庫的事實表和維表連接，轉換為事實表的位圖索引的一系列BITAND運算)，分組和DISTINCT的置換（譯者注：group-by and distinct  placement，指的是在有GROUP BY或DISTINCT, 同時有WHERE連接條件，CBO先做分組聚合減少行數再做連接操作, 和先前的group-by and distinct view merging恰好相反）。Oracle中的查詢變換可能是試探式的或基于成本的。在基于成本的變換中，邏輯變換和物理優化結合起來生成了優

8、化的執行計劃。Oracle 10g引進了一種用作基于成本的查詢變換的通用框架文獻8，和幾種狀態空間的搜索策略。在基于成本的查詢變換過程中，一個查詢被復制、變換，同時，現有的基于成本的物理優化器會計算出它的成本。這個過程被重復多次，每次運用一套不同的轉換方案；最后，一種或多種轉換被選中并應用于原來的查詢，如果它的成本計算結果很理想的話。基于成本的變換框架提供了一種機制，能夠試探一種或多種變換所生成的狀態空間，從而使得Oracle能夠以一種高效的方式選擇理想的轉換方案。基于成本的變換框架能夠處理用戶查詢的多個查詢塊和多種轉換方案之間的依賴關系造成的復雜性。因為有了這種基于成本的查詢變換的通用框架，

9、其他富于創新的轉換方案能夠被添加到Oracle豐富的查詢轉換技術中。本文介紹了新的轉換技術子查詢合并，子查詢消除，和過濾連接消除。1.2 子查詢展開(Subquery Unnesting)子查詢展開文獻 1,2,8,9是一種數據庫系統中廣泛使用的轉換技術。當一個相關子查詢未被展開時，它被元組迭代語義多次求值。這類似于嵌套循環連接(nested-loop join), 因而有效的訪問路徑、連接方法和連接順序都無法顧及。Oracle對幾乎所有的子查詢都進行展開。有兩種范圍廣泛的展開方式一種生成衍生表(內聯視圖), 另一種把一個子查詢合并到它的外層查詢。在Oracle中，前者是以一種基于成本的方式應

10、用的，而后者則是以一種試探式的方法完成的。對于非標量子查詢（譯者注：scalar subqueries標量子查詢指的是出現在SELECT部分的子查詢）的展開往往變成半連接(semijoin)或反連接(antijoin)。Oracle能夠使用索引查找，哈希，排序-合并來進行半連接或反連接。Oracle執行引擎對反連接或半連接結果中的左表元組進行緩存，所以當左表的連接列中有大量重復數據時，對子查詢的多次求值能夠避免。在缺乏相關索引的情況下，Oracle對存在量詞或全稱量詞的不等比較子查詢(例如: > ANY,  < ANY, 等等)進行展開，在不等謂詞上做排序-合并

11、連接。如果子查詢在全稱量詞比較（例如, <>ALL）中帶有可空列，則無法展開為常規的反連接。Oracle使用了一種反連接的變種，稱為“已知空值反連接”（null-aware antijoin），來展開此類子查詢。1.3 窗口函數SQL 2003標準文獻11 為SQL擴充了窗口函數（注：在Oracle文檔中被稱作析函數），不僅在表達上簡潔優雅，而且可以使得查詢優化更為有效，通過避免大量的自連接、查詢塊從而提高執行效率。窗口函數被廣泛使用在許多分析類的應用系統中。Oracle從8i版本開始支持窗口函數。窗口函數的語法看起來像這樣：Window_Function (arguments)

12、OVER ( PARTITION BY pk1 , pk2,. ORDER BY ok1 , ok2, . WINDOW clause ) 窗口函數在由分區鍵 PARTITION BY pk1, pk2, .定義的分區中求值，每個分區的數據以排序鍵ORDER BY ok1,ok2,.進行排序。WINDOW子句為每行數據定義窗口(起止點)。SQL聚合函數(SUM, MIN, COUNT等等), 排名函數(RANK, ROW_NUMBER, 等等)，或參照函數(LAG, LEAD, FIRST_VALUE, 等等) 可被用作窗口函數。ANSI SQL標準文獻10,11包含了窗口函數的語法語義細節。

13、在一個查詢塊之中，窗口函數在 WHERE,GROUP-BY,和 HAVING 子句之后被求值。在計算一個窗口函數時，Oracle按分區鍵和排序鍵對數據進行排序，并且根據需要遍歷數據。我們稱之為窗口排序執行。顯然，如果窗口函數沒有分區鍵和排序鍵，則排序就沒有必要。在這種情況下，Oracle為了計算窗口函數對數據進行緩存，這稱作窗口緩存執行。如果Oracle的基于成本的優化器選擇了一個計劃，使得數據能夠以分區鍵和排序鍵的順序產生，那么排序就可以去掉。在這種情況下，窗口緩存執行被使用，Oracle僅僅是把數據緩存并多次訪問來計算窗口函數。可是，對于像RANK, ROW_NUMBER, 累計窗口聚合函

14、數(譯者注：例如SUM,COUNT等)這些窗口函數來說，假如數據是按順序產生的，那么連緩存也沒有必要。只要保留某些上下文信息（窗口函數值和分區鍵值），這些函數就能夠在處理輸入數據的同時被計算。1.3.1 報表類窗口函數本文展示的子查詢優化利用了窗口函數中被稱為報表窗口函數的一類。這些窗口函數，根據它們的定義，對于每行返回相應分區(按照分區鍵的定義)中所有行的聚合值。如果一個窗口函數沒有排序鍵和WINDOW子句，或者當每行的WINDOW包含了它所屬分區的每一行，則可稱為報表窗口函數。在本文中，我們有時候也把這些函數成為窗口匯總。報表窗口函數在比較型分析時很有用，你可以用它來比較一行數據的某個等級

15、的值和更高等級的值。例如，為了計算一只股票的每日交易量對總交易量的比率，每一行（在一天的等級）必須具有橫跨所有天數的總計SUM。獲得所有天數的總計SUM窗口函數和輸出看起來像這樣子：Q1 SELECT ticker, day, volume,    SUM(volume) OVER (PARTITION   BY   ticker)  AS "Reporting SUM" FROM   stocks; Table 1. Reporting Window SUM Example

16、 Ticker   Day           Volume      Reporting SUM -GOOG     02-Feb-09     5           18            GOOG 

17、    03-Feb-09     6           18            GOOG     04-Feb-09     7           18     

18、0;      YHOO     02-Feb-09     21          62            YHOO     03-Feb-09     19          62 

19、           YHOO     04-Feb-09     22          62            如果一個報表聚合函數沒有任何分區鍵，那么它返回的值就是所有行的總計，因為僅有一個隱含的分區。我們把這類報表聚合函數稱為總計函數。在某些情況下，我們的子查詢變換會把總計函數引入到查詢中。2.

20、子查詢合并子查詢合并指的是這樣一種技術，即兩個子查詢在某些條件下能夠合并成一個，從而把多次表掃描、多次連接匹配減少為單次表掃描和單次連接匹配。雖然子查詢合并被定義為二元操作（譯者注：指合并的子查詢數目為兩個），它可以被依次應用到任意數目的子查詢。子查詢合并是可行的，因為一個子查詢的作用相當于在外層查詢的表之上的一個過濾謂詞。如果兩個查詢塊產生了同樣的結果集，則它們被認為是語義等價的。結構或語法相同的兩個查詢塊也可以確定它們的等價性。如果一個查詢塊Y的結果是X的結果的子集（不一定是真子集），那么我們就認為查詢塊X包容查詢塊Y。X稱為包容查詢塊，而Y則稱為被包容查詢塊。換而言之，假如Y含有一些&q

21、uot;與"過濾謂詞P，并且當P不被考慮時X和Y變得等價，則X和Y滿足包容屬性。（譯者注：假設Y是在X的基礎上多加一些WHERE過濾謂詞，這組謂詞P是用AND連到X上去的，那么X就包容Y）包容屬性是一個重要屬性，它使得我們能夠把兩個子查詢的動作合并到一起。如果兩個相連的子查詢違背了包容屬性，那么它們的過濾謂詞就不能結合到一個子查詢，因為這個子查詢只會產生交集。（譯者注：例如 EXISTS A AND EXISTS B, A和B可以是“分別存在”即可，如果改為 EXISTS A AND B則要求滿足兩個條件的同一行存在，和原來不等價）目前，當兩個 EXISTS (或NOT EXISTS

22、) 子查詢出現在一個邏輯相連或邏輯分離之中（譯者注：指AND或者OR。為方便起見，下文都把conjunctive和disjunctive翻譯為AND和OR），Oracle會執行不同的子查詢合并。既然ANY和ALL子查詢能被相應轉換成EXISTS和NOT EXISTS子查詢，我們這里不再不討論ANY/ALL子查詢的合并。兩個子查詢等價而且是同一種類型（即都是EXISTS或都是NOT EXISTS）的情況是微不足道的，因為子查詢合并僅僅是把其中一個去除。如果兩個等價子查詢是不同類型，則合并過程會把兩個都去除并代之以FALSE/TRUE謂詞，取決于這兩個子查詢是AND或者OR的關系。2.1 同類型的

23、子查詢合并如果兩個 AND EXISTS 子查詢或者兩個OR NOT EXISTS子查詢滿足包容屬性，那么它們就能被合并為一個，合并結果是被包容的那個子查詢留下，包容子查詢去除。如果是OR EXISTS或者 AND NOT EXISTS的情況，則合并結果是包容子查詢被留下，被包容子查詢去除。不滿足包容屬性的子查詢也可以被合并，如果它們在去除了一些AND過濾和相關謂詞之后是等價的。例如，兩個 OR EXISTS 子查詢只是在AND過濾和相關謂詞不同，其他部分等價，那么就可以被合并為一個EXISTS子查詢，帶有從兩個查詢里面取出的不同謂詞的OR條件。（譯者注：例子：EXISTS (SELECT .

24、 WHERE 條件A AND 條件B) OR EXISTS (SELECT . WHERE 條件A AND 條件C) 可合并為: EXISTS (SELECT . WHERE 條件A AND (條件B OR 條件C) ）兩個AND NOT EXISTS子查詢也能用相似的辦法合并。請看查詢Q2, 它有兩個OR EXISTS子查詢；子查詢有相同的相關謂詞，但是AND過濾謂詞不同。Q2:SELECT   o_orderpriority,   COUNT(*)   FROM   orders WHERE 

25、60;o_orderdate   >=   '1993-07-01'   AND         (EXISTS   (SELECT   *                      FROM   lineitem      &

26、#160;              WHERE   l_orderkey   =   o_orderkey   AND                             l_returnflag   = 

27、;  "R')  OR          EXISTS   (SELECT   *                      FROM   lineitem                &#

28、160;    WHERE   l_orderkey   =   o_orderkey   AND                             l_receiptdate   > l_commitdate)        

29、  )GROUP   BY   o_orderpriority; 我們的子查詢合并會把兩個EXISTS子查詢并成單個帶OR過濾謂詞的子查詢，變成Q3:Q3 SELECT   o_orderpriority,   COUNT(*)   FROM   orders WHERE   o_orderdate   >=   '1993-07-01'   AND  

30、       EXISTS   (SELECT   *                      FROM   lineitem                     WHERE   l_

31、orderkey   =   o_orderkey   AND                             (l_returnflag   =   "R'   OR             

32、                 l_receiptdate   >   l_commitdate) GROUP   BY   o_orderpriority; 2.2 不同類型的子查詢的合并合并兩個滿足包容屬性的不同類型的AND子查詢需要不同的技術。請看子查詢Q4, 這是一個 TPC-H第21號查詢的簡化版：Q4 SELECT   s_name   

33、FROM   supplier,   lineitem   L1 WHERE   s_suppkey   =   l_suppkey   AND          EXISTS   (SELECT   *                   

34、;   FROM   lineitem   L2                     WHERE   l_orderkey = L1.l_orderkey                          

35、   AND   l_suppkey   <>   L1.l_suppkey)          AND   NOT   EXISTS                   (SELECT   *          &#

36、160;           FROM   lineitem   L3                     WHERE   l_orderkey   =   L1.l_orderkey AND           

37、                 l_suppkey   <>   L1.l_suppkey   AND                             l_receiptdate > l_commitdate); Q4中的

38、兩個子查詢僅僅是類型不同，同時NOT EXISTS子查詢多了一個過濾謂詞，l_receiptdate > l_commitdate。子查詢合并形成了查詢Q5, 它只有單個EXISTS子查詢，因此去除了一個lineitem表的訪問。Q5 SELECT   s_name   FROM   supplier,   lineitem   L1 WHERE   s_suppkey   =   l_suppkey   AN

39、D          EXISTS   (SELECT   1                      FROM   lineitem   L2                    &#

40、160;WHERE   l_orderkey   =                             L1.l_orderkey   AND                         &

41、#160;   l_suppkey <> L1.l_suppkey                    HAVING   SUM(CASE WHEN l_receiptdate > l_commitdate                          

42、           THEN 1                                   ELSE 0                    &#

43、160;              END)   =   0); （譯者注：子查詢里不帶GROUP BY的HAVING很有些趣味）HAVING子句里的聚合函數返回了滿足子查詢謂詞的行數。合并后的子查詢引入了HAVING子句，它帶有一個新的過濾謂詞檢查是否有滿足子查詢過濾謂詞的數據，從而模擬了被去除的NOT EXISTS子查詢的動作。對于每一組相關值（譯者注：指來自外層的L1表的值），Q4中的子查詢的狀態可能為如下的三種之一：. 當EIXSTS子查詢沒有返回

44、數據（即結果為假），兩個子查詢的AND結果為假。在Q5中，HAVING子句被作用在一個空集合之上，合并后的EXISTS同樣也返回假。. 當EIXSTS子查詢返回一些數據（即結果為真）并且NOT EIXSTS子查詢也返回一些數據（即結果為假），兩個子查詢的AND結果為假。在Q5中，HAVING子句被作用于一個非空集合，而這個集合含有l_receiptdate > l_commitdate的數據，因此它結果為假。. 當EIXSTS子查詢返回一些數據而NOT EIXSTS子查詢沒有返回數據，因為它有額外的過濾謂詞，那么兩個子查詢的AND結果為真。在Q5中，HAVING子句被作用于一個非空集合，

45、而這個集合不含有l_receiptdate > l_commitdate的數據，因此它結果為真，從而使得合并后的子查詢結果為真。上面的討論證明了Q4和Q5是等價的。假如NOT EXISTS子查詢是包容查詢，而AND EXISTS子查詢被包容，合并過程將會去除兩個子查詢并以FALSE謂詞取代之。當EXISTS子查詢有返回數據(即結果為真)時NOT EXISTS子查詢必定同樣也返回數據(即結果為假)。當NOT EXISTS子查詢不返回數據，EXISTS子查詢同樣也不返回。因此，兩個子查詢的AND結果恒為假。類似的論證也可適用于兩個滿足包容屬性的EXISTS和NOT EXISTS子查詢在OR連

46、接謂詞中出現的合并情況。2.3 合并和其他變換在文獻8，我們討論了不同的變換之間是如何互相影響的，而我們的基于成本的變換框架又是如何處理這些可能的影響。子查詢合并也不例外，因為合并后的子查詢可能是另外的變換方法的作用對象。Q5中的子查詢可能進行展開變成Q6，里面含有一個內聯視圖（衍生表）V。Q6 SELECT   s_name   FROM   supplier,   lineitem   L1,       (SELECT   LX.

47、rowid   xrowid          FROM   lineitem   L2,   lineitem   LX         WHERE   L1.l_suppkey <> LX.l_suppkey   AND             

48、;    L1.l_orderkey   =   LX.l_orderkey        GROUP   BY   LX.rowid        HAVING   SUM(CASE WHEN L2.l_receiptdate > L2.l_commitdate                

49、;          THEN   1                            ELSE   0                       EN

50、D)   =   0)   V WHERE  s_suppkey   =   L1.l_suppkey   AND         L1.rowid   =   V.xrowid; 在視圖合并之后，Q6變成了查詢Q7，表LX被標記為多余的，既然子合并之后的查詢塊中LX和L1被用唯一的ROWID列連接起來。因此，LX被去除，所有對它的引用變成對L1的引用。Q7

51、 SELECT   s_name   FROM   supplier,   lineitem   L1,   lineitem   L2 WHERE   s_suppkey   =   L1.l_suppkey   AND          L1.l_orderkey   =   

52、;L2.l_orderkey GROUP   BY   L1.rowid,   S.rowid,   S.s_name HAVING   SUM(CASE   WHEN   L2.l_receiptdate   > L2.l_commitdate                     THE

53、N   1                       ELSE   0                END)   =   0); 這里我們至少有了四種不同的查詢供取舍。在大部分情況下，這四種中的哪一種是最佳選擇并不清楚。在1.1節中討論的Oracle的基于

54、成本的變換框架可以用于作出選擇。2.4 查詢執行的增強Q7中的HAVING謂詞，把那些組中至少含有一條收據日期大于提交日期的數據都排除出去。這個謂詞和其他類似謂詞，比如MIN(l_receiptdate)>'18-Feb-2001', COUNT(*)<=10, SUM(amount_sold) < 2000 （當amount_sold已知為正數，例如在數據庫中有一個可信賴的約束）, 等等, 假如不滿足，則整個組立刻可以判斷為無用（即不會出現子結果集中），并可被推入分組操作(GROUP-BY)來進行對那一組的聚合短路處理。這樣提高了執行效率。例如，在Q7中，有

55、一個輸入數據l_receiptdate > l_commitdate 導致那一組的SUM聚合出現了值1, 因此使得整個組的數據不可用。類似地，當謂詞是SUM(amount_sold)<2000，而且數據庫中有一個amount_sold為正數的可信賴約束條件，那么一當某個組的SUM超過了2000, 整個組立即不可用。GROUP-BY 會跳過那些不可用的組的聚合處理。（譯者注：那些堅持把約束拿到數據庫之外的應用程序去實現的人，請睜大你的雙眼，這可能會導致你的查詢失去了優化的機會！）并行分組執行也從那些用來降低數據傳輸量的謂詞之中獲益。Oracle利用并行分組下推技術(parallel

56、group-by pushdown, 縮寫GPD), 分組求值被推入到產生輸入的進程（生產者子進程，producer slaves），從而降低通訊成本，提高分組操作的可擴展性。生產者子進程把聚合后的數據分發給另一組進程（消費者子進程，consumer slaves），依據的是分組鍵的HASH值或值范圍。消費者子進程于是結束分組處理并產生結果。查詢Q7的帶GDP的并行查詢計劃如圖1所示。當生產者子進程P1.Pn在分組處理過程中根據HAVING謂詞把那些組過濾掉，數據傳輸量就能夠下降。類似地，那些能夠立即使得組被選中的謂詞也被推入到分組操作中。一旦一個組被發現為可選，那些不是結果集中所需要的聚合處

57、理就可被跳過（譯者注：比如HAVING中用到了COUNT(*)>0謂詞，而COUNT(*)沒有出現在SELECT中，那么一旦滿足了條件，剩下的計數就不必要繼續了）。這類謂詞的例子有MIN(l_receiptdate)<'18-Feb-2001',  COUNT(*)>10,  SUM(amount_sold)>2000, 當amount_sold已知為正數。圖1 并行分組操作下推3. 分組視圖消除在這一節，我們討論一種成為過濾表消除的技術，這是基于過濾連接的思想。一個過濾連接或者是一個半連接(semijoin)或者

58、是一個等值內連接，連接發生在所涉及的兩個表之一的一個唯一列。在這里我們把一個唯一列Y以下劃線來表示，并用一個非標準的記號=來表示一個等值半連接。R是一個表，而T1和T2分別是來自同一個基表或衍生表T的兩個實例。T1,T2要么是含有完全相同的過濾謂詞，如果有的話，要么是T1上的過濾謂詞比T2上的更為嚴格。在下列的情形中，T2和過濾連接可以被去除。R.X = T1._Y_ AND R.X = T2._Y_ R.X = T1._Y_R.X = T1.Y AND R.X = T2.Y R.X = T1.YR.X = T1.Y AND R.X = T2.Y R.X = T1.Y假設非過濾連接（如果有的話

59、）先發生。過濾連接最多會保持R中的所有結果行，既然一個過濾連接僅僅能夠濾掉R中的數據，這與內連接不同，內連接既可濾掉數據也可生成重復數據。過濾連接使得T2表變成多余的，因此可以去除。雖然這種技術看上去和 AND EXISTS 子查詢的合并非常相似，接下來我們要展示一下這種技術的不同應用。3.1 視圖消除請看Q8, 它是一個TPC-H第18號查詢的簡化版本： Q8 SELECT o_orderkey,c_custkey,   SUM(l_quantity)   FROM orders,   lineitem   L1

60、,   customers WHERE o_orderkey   =   l_orderkey   AND        c_custkey   =   o_custkey   AND        o_orderkey   IN (SELECT   l_orderkey        

61、                  FROM   lineitem   L2                         GROUP   BY   l_orderkey       &#

62、160;                 HAVING   SUM(l_quantity)   >   30) GROUP   BY   o_orderkey,   o_totalprice; 查詢Q8經過展開變成Q9。Q9中由展開變形產生的內聯視圖（衍生表）V2 不需要半連接，既然它是一個等值連接，并且V2上的連接列是唯一的，這是V2上對此列做分組操作的結果。

63、Q9 SELECT   o_orderkey,c_custkey,   SUM(l_quantity)   FROM   orders,   lineitem   L1,   customers,         (SELECT   l_orderkey            FROM 

64、 lineitem   L2           GROUP   BY   l_orderkey          HAVING   SUM(l_quantity)   >   30)   V2 WHERE   o_orderkey   =   V2.l_orde

65、rkey   AND          o_orderkey   =   L1.l_orderkey   AND          c_custkey   =   o_custkey GROUP   BY   o_orderkey,   c_custkey; 利用分組和連接置換（即分組置換）文獻5,

66、6,8，另一個包含表L1的視圖V1能被產生出來，如Q10所示；SUM(l_quantity)被加到V2的SELECT列表中，Q9的語義不變。Q10 SELECT   o_orderkey, c_custkey, SUM(V1.qty)   FROM   orders,   customers,          (SELECT l_orderkey, SUM(l_quantity) qty        

67、    FROM   lineitem   L2            GROUP   BY   l_orderkey           HAVING   SUM(l_quantity)   >   30)   V2,      &

68、#160;   (SELECT   l_orderkey, SUM(l_quantity) qty             FROM   lineitem   L1           GROUP   BY   l_orderkey)   V1 WHERE   o_orderkey  &#

69、160;=   V1.l_orderkey   AND         o_orderkey   =   V2.l_orderkey   AND         c_custkey   =   o_custkey GROUP   BY   o_orderkey,   c_cust

70、key; 正如所示，V1和V2是同一視圖的兩個不同實例，只是V2的過濾謂詞比V1更嚴格，因為V2多了個HAVING子句。不僅如此，V1和V2是在一個唯一列o_orderkey之上和ORDERS表進行等值連接的，因為它是視圖中唯一的分組鍵；因此這兩個連接是過濾連接。所以，V1可以去除，對V1的引用可以被對V2的引用取代。去除Q10的過濾視圖后得到了Q11。Q11 SELECT   o_orderkey, c_custkey, SUM(V2.qty)   FROM   orders,   customers, 

71、0;        (SELECT   o_orderkey,   SUM(l_quantity)             FROM   lineitem           GROUP   BY   l_orderkey           HAV

72、ING   SUM(l_quantity)   >   30)   V2, WHERE   o_orderkey   =   V2.l_orderkey   AND         c_custkey   =   o_custkey GROUP   BY   o_orderkey, 

73、  c_custkey; 如果Q9中的視圖V2被合并，另外一種利用過濾連接的論證方法也能得到去除外層查詢的lineitem表的同樣結果。4. 利用窗口函數的子查詢消除這種技術利用窗口函數代替子查詢文獻11，因此減少了表訪問、連接求值的次數并改善查詢的性能。這里討論的子查詢消除技術有些在Oracle 9i引入，有些只是作為文獻出版文獻13。在它的簡化版中，包含聚合子查詢(subsumed aggregation subqueries)被利用窗口函數所消除。當一個外層查詢塊如果含有在子查詢中出現的所有的表和謂詞，它就稱為包含一個子查詢。外層查詢塊可能還有額外的表和謂詞。顯然，包含屬性和第

74、二節談到的包容屬性是不同的。這種技術利用了無損連接屬性和代數聚合（例如 SUM, MIN, MAX, COUNT, AVG等等）。Q12 展示了適用子查詢消除的包含聚合子查詢的一種形式。T1和T2可能是基表或衍生表或多表的連接結果。子查詢中的聚合AGG參與了一種和外層查詢的列T2.z的關系比較 (relop)，相關列則在T1.y列。Q12 SELECT   T1.x FROM   T1,   T2 WHERE   T1.y   =   T2.y   and

75、          T2.z   relop   (SELECT   AGG(T2.w)                            FROM   T2              

76、             WHERE   T2.y   =   T1.y); 假設T1和T2的連接是一個無損連接，即T2.y是一個指向主鍵T1.y的外鍵，那么引入一個把相關列作為分區鍵的窗口函數就可消除子查詢。如Q13所示。Q13 SELECT   V.x   FROM   (SELECT   T1.x,   T2.z,    

77、                AGG   (T2.w) OVER   (PARTITION   BY   T2.y)                          AS   win_agg      &#

78、160;      FROM   T1,   T2            WHERE   T1.y   =   T2.y)   V WHERE   V.z   relop   win_agg; 為了利用窗口函數做子查詢消除，T1和T2的連接并不要求是無損的。然而，無損連接可以導致另一種變形，允許優化

79、器考慮更多連接置換。上述Q12的變種形式，如非相關子查詢，或者有額外表和謂詞，或者沒有聚合，或者當子查詢和外層查詢都有分組，都可以利用子查詢消除技術進行變形。我們在隨后的章節中會給出例子。4.1 相關包含子查詢請看查詢 Q14, 這是一個TPC-H第二號查詢的簡化版本。外層查詢多了表PARTS和那個表上的謂詞。子查詢和PARTS表相關并且被外層查詢包含。 Q14 SELECT   s_name,   n_name,   p_partkey   FROM   parts   P

80、,   supplier,   partsupp,          nation,   region WHERE   p_partkey   =   ps_partkey   AND          s_suppkey   =   ps_suppkey   AND  

81、;        s_nationkey   =   n_nationkey   AND          n_regionkey   =   r_regionkey   AND          p_size   =   36   AND 

82、0;        r_name   =   'ASIA'   AND          ps_supplycost IN                        (SELECT   MIN   (ps_su

83、pplycost)                           FROM   partsupp,   supplier,   nation, region                       

84、  WHERE   P.p_partkey   =   ps_partkey   AND                                  s_suppkey   =   ps_suppkey   AND 

85、0;                                s_nationkey   =   n_nationkey   AND                      

86、0;           n_regionkey   =   r_regionkey   AND                                  r_name   =   'ASIA&

87、#39;); 子查詢消除技術把Q14變換為Q15: Q15 SELECT   s_name,   n_name,   p_partkey   FROM   (SELECT ps_supplycost,                  MIN   (ps_supplycost) OVER (PARTITION   BY 

88、60;ps_partkey)                        AS   min_ps,                  s_name,   n_name,   p_partkey        

89、     FROM parts,   supplier,   partsupp,                  nation,   region            WHERE   p_partkey   =   ps_partkey 

90、;  AND                    s_suppkey   =   ps_suppkey   AND                    s_nationkey   =   n_nationkey   AND &

91、#160;                  n_regionkey   =   r_regionkey   AND                    p_size   =   36   AND       

92、;             r_name   =   'ASIA')   V WHERE    V.ps_supplycost   =   V.min_ps; 由PARTSUPP和PARTS表的連接產生的重復行，如果有的話，在這里無關緊要，因為聚合函數是MIN。如果聚合函數不是MIN/MAX，或者對額外表的連接（在本例中是PARTS表）不是無損的，那么窗口函數的計算必須在視圖中完成

93、，然后才和附加表連接。這正是TPC-H第17號查詢的情形，子查詢消除把它變換為Q16: Q16 SELECT   SUM(V.avg_extprice)/7   AS   avg_yearly   FROM   parts,          (SELECT   (CASE WHEN l_quantity < (1.2*AVG(l_quantity) OVER (PARTITION BY l_partkey)

94、                         THEN l_extprice                          ELSE   NULL             

95、        END)   avg_extprice,                     l_partkey             FROM   lineitem)   V WHERE   p_partkey  

96、0;=   V.l_partkey   AND          V.avg_extprice   IS   NOT   NULL   AND          P_brand   =   'Brand#23'   AND       

97、0;  p_container   =   'MED  BOX' 4.2 非相關包含子查詢請看查詢Q17, 這是TPC-H第15號查詢的一個簡化版。Q17有一個和外層查詢不相關的聚合子查詢，子查詢和外查詢同時引用一個相同的分組視圖（衍生表）V.Q17 WITH  V  AS  (SELECT l_suppkey,                      SUM(l_extprice) revenue