第2章 邏輯查詢優化

查詢優化器在邏輯優化階段主要解決的問題是：如何找出SQL語句等價的變換形式，使得SQL執行更高效。

一條SQL查詢語句結構復雜，包含多種類型的子句，優化操作依賴于表的一些屬性信息（如索引和約束等）。可用于優化的思路包括：

?子句局部優化。每種類型子句都可能存在優化方式，這是子句局部的優化，如等價謂詞重寫、WHERE和HAVING條件化簡中的大部分情況，都屬于這種子句范圍內的局部優化。

?子句間關聯優化。子句與子句之間關聯的語義存在優化的可能，如外連接消除、連接消除、子查詢優化、視圖重寫等都屬于子句間的關聯優化，因為它們的優化都需要借助其他子句、表定義或列屬性等信息進行。

?局部與整體的優化。需要協同考慮局部表達式和整體的關系，如OR重寫并集規則需要考慮UNION操作（UNION是變換后的整體的形式）的花費和OR操作（OR是局部表達式）的花費。

?形式變化優化。多個子句存在嵌套，可以通過形式的變化完成優化，如嵌套連接消除。

?語義優化。根據完整性約束、SQL表達的含義等信息對語句進行語義優化。

?其他優化。根據一些規則對非SPJ做的其他優化、根據硬件環境進行的并行查詢優化等。

各種邏輯優化技術依據關系代數和啟發式規則進行。

2.1 查詢優化技術的理論基礎

查詢優化技術的理論基礎是關系代數。本節就關系代數的最基本內容進行介紹，目的是引出關系代數對查詢優化的指導意義。

2.1.1 關系代數

1970年，E.F.Codd在題為《A Relational Model of Data for Shared Data Banks》的論文中提出了數據的關系模型的概念。Codd提議將關系代數作為數據庫查詢語言的基礎。關系數據庫基于關系代數。關系數據庫的對外接口是SQL語句，所以SQL語句中的DML、DQL基于關系代數實現了關系的運算。

作為數據庫查詢語言的基礎，關系模型由關系數據結構、關系操作集合和關系完整性約束三部分組成。以下是幾個和關系模型有關的概念：

?關系模型的數據結構就是我們在關系數據庫中提到的二維結構，是一個橫縱結合的二維表。在關系模型中，現實世界的實體以及實體間的各種聯系均用關系來表示。

?關系是一種對象。

?關系的另外一個常用詞是表，在本書中，關系和表混用，因為它們基本表達同一含義，只是關系更偏向于理論，表更偏向于實際數據庫中可進行增、刪、改、查等操作的表對象。

?關系的元數據，即表的結構，通常稱為列或屬性。數據庫實現中，有的用field表示，有的用Item表示。

?關系的數據，即表的行數據，通常稱為元組（tuple），也稱為記錄（record）。一個表可有多行元組。

?對關系進行的操作就是關系運算。關系運算是將一定的運算符作用于一定的關系對象上，得到預期的運算結果（預期就是用戶語義，用戶語義通過運算符表達基本語義，通過對不同對象上的各種運算進行組合表達其對關系操作的真實語義）。運算對象、運算符、運算結果是運算的三大要素，所以關系運算就是關系運算符作用在關系上、得到的結果形式也是關系形式的操作。

關系代數的運算符包括以下4類：

?傳統集合運算符。并（UNION）、交（INTERSECTION）、差（DIFFERENCE）、積（EXTENDED CARTESIAN PRODUCT）。

?專門的關系運算符。選擇（SELECT）、投影（PROJECT）、連接（JOIN）、除（DIVIDE）。

?輔助運算符。用來輔助專門的關系運算符進行操作的，包括算術比較符和邏輯運算符。

?Codd定義了8個基本關系運算符后，許多人提出了新的代數操作符——關系擴展運算符，如半連接（SEMIJOIN）、半差（SEMIDIFFERENCE）、擴展（EXTEND）、合計（COMPOSITION）、傳遞閉包（TCLOSE）等，這些操作符增強了關系代數的表達能力，但不常用。

關系代數基本關系運算如表2-1所示，各種連接運算的語義如表2-2所示。

表2-1 基本關系運算與對應的SQL表

表2-2 各種連接運算的語義表

2.1.2 關系代數等價變換規則對優化的指導意義

關系代數表達式的等價：也就是說用相同的關系代替兩個表達式中相應的關系，所得到的結果是相同的。兩個關系表達式El和E2是等價的，記為E1≡E2。

查詢語句可以表示為一棵二叉樹，其中：

?葉子是關系。

?內部結點是運算符（或稱算子、操作符，如LEFT OUT JOIN），表示左右子樹的運算方式。

?子樹是子表達式或SQL片段。

?根結點是最后運算的操作符。

?根結點運算之后，得到的是SQL查詢優化后的結果。

?這樣一棵樹就是一個查詢的路徑。

?多個關系連接，連接順序不同，可以得出多個類似的二叉樹。

?查詢優化就是找出代價最小的二叉樹，即最優的查詢路徑。每條路徑的生成，包括了單表掃描、兩表連接、多表連接順序、多表連接搜索空間等技術。

?基于代價估算的查詢優化就是通過計算和比較，找出花費最少的最優二叉樹。

上述的最后兩項，主要依據本章查詢重寫規則和第3章物理查詢優化中涉及的技術，對查詢優化引擎做關系代數和啟發式規則的邏輯查詢優化、基于代價估算模型擇優的物理查詢優化，從而幫助數據庫查詢優化器實現查詢優化。

1.從運算符的角度考慮優化

不同運算符根據其特點，可以對查詢語句做不同的優化，優化可以減少中間生成物的大小和數量，節約IO、內存等，從而提高了執行速度。但優化的前提是：優化前和優化后的語義必須等價。不同運算符的優化規則和可優化的原因如表2-3所示。

表2-3 運算符主導的優化

表2-4 選擇下推到集合的運算

表2-5 投影下推到集合的運算

對于表2-4和表2-5，我們以“σA(R×S)”為例，表明它們可做優化的共同意義。

初始式是σA(R×S)，條件A可分解為“B∧C∧D”，條件B只與關系R有關，條件C只與關系S有關，則初始式可以變形為：σB∧C∧D(R×S)，表示為查詢樹的結構如圖2-1所示。

圖2-2所示為第一層做完選擇后，每個葉子結點對應的元組數“可能”比圖2-1中的R和S少，如果B條件和C條件至少有一個能夠大量減少R或S的元組，則中間結果大量減少，優化的效果會更好（B條件和C條件對元組過濾程度依賴于“選擇率”）。如果R和S上有B條件、C條件可以使用的索引，則利用索引可加快元組的獲取，優化的效果會更好。

如果索引是唯一索引或主鍵（主鍵不允許重復，不允許為NULL值，多數數據庫為主鍵實現了一個唯一索引）之類，條件表達式是等值表達式（=運算非范圍運算），定位元組的速度更快（可直接利用索引而不用掃描數據）、滿足條件的元組更少，所以優化的效果會更佳。

圖2-1中在連接后進行選擇操作，一是中間結果的元組數量大，二是需要對中間結果的每條元組都進行B、C、D3個條件的判斷，增加了條件判斷的成本，效率很低。

經過等價變換優化帶來的好處，再加上避免了原始方式引入的壞處，使得查詢效率明顯獲得提升。

2.從運算規則的角度考慮優化

前面我們從運算符的角度出發考慮了優化。因為運算符中考慮的子類型（見表2-3中的“子類型”列）實則是部分考慮了運算符間的關系、運算符和操作數間的關系，其本質是運算規則在起作用。所以前節考慮過關系代數運算規則對優化的作用，但不完整，這里補充余下的對優化有作用的主要關系代數運算規則。下面的運算規則是查詢重寫技術作等價轉換的基礎，如表2-6所示。

表2-6 運算規則主導的優化

2.2 查詢重寫規則

傳統的聯機事務處理（On-line Transaction Processing，OLTP）使用基于選擇（SELECT）、投影（PROJECT）、連接（JOIN）3種基本操作相結合的查詢，這種查詢稱為SPJ查詢。

數據庫在查詢優化的過程中，會對這3種基本操作進行優化。優化的方式如下：

?選擇操作。對應的是限制條件（格式類似field＜op＞consant，field表示列對象，op是操作符，如=、＞等），優化方式是選擇操作下推，目的是盡量減少連接操作前的元組數，使得中間臨時關系盡量少（元組數少，連接得到的元組數就少），這樣可減少IO和CPU的消耗，節約內存空間。

?投影操作。對應的SELECT查詢的目的列對象，優化方式是投影操作下推，目的是盡量減少連接操作前的列數，使得中間臨時關系盡量小（特別注意差別：選擇操作是使元組的個數“盡量少”，投影操作是使一條元組“盡量小”），這樣雖然不能減少IO（多數數據庫存儲方式是行存儲，元組是讀取的最基本單位，所以要想操作列則必須讀取一行數據），但可以各減少連接后的中間關系的元組大小，節約內存空間。

?連接操作。對應的是連接條件（格式類似field_1＜op＞field_2，field_1和field_2表示不同表上的列對象，op是操作符，如=、＞等），表示兩個表連接的條件。這里涉及以下兩個子問題。

○多表連接中每個表被連接的順序決定著效率。如果一個查詢語句只有一個表，則這樣的語句很簡單；但如果有多個表，則會涉及表之間以什么樣的順序連接效率最高效（如A、B、C三表連接，如果ABC、ACB、BCA等連接后的結果集一樣，則計算哪種連接次序的效率最高，是需要考慮的問題）。

○多表連接每個表被連接的順序由用戶語義決定。查詢語句多表連接有著不同的語義（如是笛卡兒集、內連接，還是外連接中的左外連接等），這決定著表之間的前后連接次序是不能隨意更換的，否則，結果集中數據是不同的。因此，表的前后連接次序是不能隨意交換的。

另外，根據SQL語句的形式特點，還可以做如下區分：

?針對SPJ的查詢優化。基于選擇、投影、連接3種基本操作相結合的查詢。

?針對非SPJ的查詢優化。在SPJ的基礎上存在GROUPBY操作的查詢，這是一種較為復雜的查詢。

所以，針對SPJ和非SPJ的查詢優化，其實是對以上多種操作的優化。“選擇”和“投影”操作，可以在關系代數規則的指導下進行優化。表連接，需要多表連接的相關算法完成優化。其他操作的優化多是基于索引和代價估算完成的。

2.2.1 子查詢的優化

子查詢是查詢語句中經常出現的一種類型，是比較耗時的操作。優化子查詢對查詢效率的提升有著直接的影響，所以子查詢優化技術，是數據庫查詢優化引擎的重要研究內容。

從子查詢出現在SQL語句的位置看，它可以出現在目標列、FROM子句、WHERE子句、JOIN/ON子句、GROUPBY子句、HAVING子句、ORDERBY子句等位置。子查詢出現在不同位置對優化的影響如下：

?目標列位置。子查詢如果位于目標列，則只能是標量子查詢，否則數據庫可能返回類似“錯誤：子查詢必須只能返回一個字段”的提示。

?FROM子句位置。相關子查詢出現在FROM子句中，數據庫可能返回類似“在FROM子句中的子查詢無法參考相同查詢級別中的關系”的提示，所以相關子查詢不能出現在FROM子句中；非相關子查詢出現在FROM子句中，可上拉子查詢到父層，在多表連接時統一考慮連接代價后擇優。

?WHERE子句位置。出現在WHERE子句中的子查詢是一個條件表達式的一部分，而表達式可以分解為操作符和操作數；根據參與運算的數據類型的不同，操作符也不盡相同，如INT型有＞、＜、=、＜＞等操作，這對子查詢均有一定的要求（如INT型的等值操作，要求子查詢必須是標量子查詢）。另外，子查詢出現在WHERE子句中的格式也有用謂詞指定的一些操作，如IN、BETWEEN、EXISTS等。

?JOIN/ON子句位置。JOIN/ON子句可以拆分為兩部分，一是JOIN塊類似于FROM子句，二是ON子句塊類似于WHERE子句，這兩部分都可以出現子查詢。子查詢的處理方式同FROM子句和WHERE子句。2010-10-12

?GROUPBY子句位置。目標列必須和GROUPBY關聯。可將子查詢寫在GROUPBY位置處，但子查詢用在GROUPBY處沒有實用意義。

?ORDERBY子句位置。可將子查詢寫在ORDERBY位置處。但ORDERBY操作是作用在整條SQL語句上的，子查詢用在ORDERBY處沒有實用意義。

1.子查詢的分類

根據子查詢中涉及的關系對象與外層關系對象間的關系，子查詢可以分為以下兩類：

?相關子查詢。子查詢的執行依賴于外層父查詢的一些屬性值。子查詢因依賴于父查詢的參數，當父查詢的參數改變時，子查詢需要根據新參數值重新執行（查詢優化器對相關子查詢進行優化有一定意義），如：

SELECT * FROM t1 WHERE col_1 = ANY
   (SELECT col_1 FROM t2 WHERE t2.col_2 = t1.col_2);/* 子查詢語句中存在父查詢的t1表的col_2列 */

?非相關子查詢。子查詢的執行不依賴于外層父查詢的任何屬性值，這樣的子查詢具有獨立性，可獨自求解，形成一個子查詢計劃先于外層的查詢求解，如：

SELECT * FROM t1 WHERE col_1 = ANY
   (SELECT col_1 FROM t2 WHERE t2.col_2 = 10);//子查詢語句中(t2)不存在父查詢(t1)的屬性

從特定謂詞看，子查詢可分為以下3類：

?[NOT]IN/ALL/ANY/SOME子查詢。語義相近，表示“[取反]存在/所有/任何/任何”，左面是操作數，右面是子查詢，是最常見的子查詢類型之一。

?[NOT]EXISTS子查詢。半連接語義，表示“[取反]存在”，沒有左操作數，右面是子查詢，也是最常見的子查詢類型之一。

?其他子查詢。除了上述兩種外的所有子查詢。

從語句的構成復雜程度看，子查詢可分為以下3類：

?SPJ子查詢。由選擇、連接、投影操作組成的查詢。

?GROUPBY子查詢。SPJ子查詢加上分組、聚集操作組成的查詢。

?其他子查詢。GROUPBY子查詢中加上其他子句如Top-N、LIMIT/OFFSET、集合、排序等操作。后兩種子查詢有時合稱非SPJ子查詢。

從結果集的角度看，子查詢分為以下4類：

?標量子查詢。子查詢返回的結果集類型是一個單一值（return a scalar，a single value）。

?列子查詢。子查詢返回的結果集類型是一條單一元組（return a single row）。

?行子查詢。子查詢返回的結果集類型是一個單一列（return a single column）。

?表子查詢。子查詢返回的結果集類型是一個表（多行多列）（return a table，one or more rows of one or more columns）。

2.子查詢的優化思路

通過上面的介紹，我們知道了都有哪些類型的子查詢及每類子查詢的特點，下面就講一下子查詢的優化思路。要明白子查詢是如何優化的，就要先明白為什么要做子查詢優化。

（1）做子查詢優化的原因

為什么要做子查詢優化呢？

在數據庫實現早期，查詢優化器對子查詢一般采用嵌套執行的方式，即對父查詢中的每一行，都執行一次子查詢，這樣子查詢會執行很多次。這種執行方式效率很低。

而對子查詢進行優化，可能帶來幾個數量級的查詢效率的提高。子查詢轉變成為連接操作之后，會得到如下好處：

?子查詢不用執行很多次。

?優化器可以根據統計信息來選擇不同的連接方法和不同的連接順序。

?子查詢中的連接條件、過濾條件分別變成了父查詢的連接條件、過濾條件，優化器可以對這些條件進行下推，以提高執行效率。

（2）子查詢優化技術

子查詢優化技術的思路如下：

?子查詢合并（Subquery Coalescing）。在某些條件下（語義等價：兩個查詢塊產生同樣的結果集），多個子查詢能夠合并成一個子查詢（合并后還是子查詢，以后可以通過其他技術消除子查詢）。這樣可以把多次表掃描、多次連接減少為單次表掃描和單次連接，如：

SELECT * FROM t1 WHERE a1＜10 AND (
    EXISTS (SELECT a2 FROM t2 WHERE t2.a2＜5 AND t2.b2=1) OR
    EXISTS (SELECT a2 FROM t2 WHERE t2.a2＜5 AND t2.b2=2)
);

可優化為：

SELECT * FROM t1 WHERE a1＜10 AND (
     EXISTS (SELECT a2 FROM t2 WHERE t2.a2＜5 AND (t2.b2=1 OR t2.b2=2) /*兩個EXISTS子句合并為一個,條件也進行了合并 */
);

?子查詢展開（Subquery Unnesting）。又稱子查詢反嵌套，又稱為子查詢上拉。把一些子查詢置于外層的父查詢中，作為連接關系與外層父查詢并列，其實質是把某些子查詢重寫為等價的多表連接操作（展開后，子查詢不存在了，外層查詢變成了多表連接）。帶來的好處是，有關的訪問路徑、連接方法和連接順序可能被有效使用，使得查詢語句的層次盡可能地減少。常見的IN/ANY/SOME/ALL/EXISTS依據情況轉換為半連接（SEMI JOIN）、普通類型的子查詢消除等情況屬于此類，如：

SELECT * FROM t1, (SELECT * FROM t2 WHERE t2.a2 ＞10) v_t2
WHERE t1.a1＜10 AND v_t2.a2＜20;

可優化為：

SELECT * FROM t1, t2 WHERE t1.a1＜10 AND t2.a2＜20 AND t2.a2 ＞10; /* 子查詢變為了t1、t2表的連接操作,相當于把t2表從子查詢中上拉了一層 */

?聚集子查詢消除（Aggregate Subquery Elimination）。聚集函數上推，將子查詢轉變為一個新的不包含聚集函數的子查詢，并與父查詢的部分或者全部表做左外連接。通常，一些系統支持的是標量聚集子查詢消除，如：

SELECT * FROM t1 WHERE t1.a1＞(SELECT avg(t2.a2) FROM t2);

?其他。利用窗口函數消除子查詢的技術（Remove Subquery using Window functions，RSW）、子查詢推進（Push Subquery）等技術可用于子查詢的優化，這里不展開討論。

（3）子查詢展開

子查詢展開是一種最為常用的子查詢優化技術，子查詢展開有以下兩種形式：

?如果子查詢中出現了聚集、GROUPBY、DISTINCT子句，則子查詢只能單獨求解，不可以上拉到上層。

?如果子查詢只是一個簡單格式（SPJ格式）的查詢語句，則可以上拉到上層，這樣往往能提高查詢效率。子查詢上拉討論的就是這種格式，這也是子查詢展開技術處理的范圍。

把子查詢上拉到上層查詢，前提是上拉（展開）后的結果不能帶來多余的元組，所以子查詢展開需要遵循如下規則：

?如果上層查詢的結果沒有重復（即SELECT子句中包含主碼），則可以展開其子查詢，并且展開后的查詢的SELECT子句前應加上DISTINCT標志。

?如果上層查詢的SELECT語句中有DISTINCT標志，則可以直接進行子查詢展開。

?如果內層查詢結果沒有重復元組，則可以展開。

子查詢展開的具體步驟如下：

1）將子查詢和上層查詢的FROM子句連接為同一個FROM子句，并且修改相應的運行參數。

2）將子查詢的謂詞符號進行相應修改（如：IN修改為=ANY）。

3）將子查詢的WHERE條件作為一個整體與上層查詢的WHERE條件合并，并用AND條件連接詞連接，從而保證新生成的謂詞與原謂詞的上下文意思相同，且成為一個整體。

3.最常見的子查詢類型的優化

子查詢的格式有多種，常見的子查詢格式有IN類型、ALL/ANY/SOME類型、EXISTS類型。下面我們就基于這3種常見類型對子查詢類型的優化進行介紹。

（1）IN類型

IN類型有3種不同的格式，具體如下。

格式一：

outer_expr [NOT] IN (SELECT inner_expr FROM ... WHERE subquery_where)

格式二：

outer_expr =ANY (SELECT inner_expr FROM ... WHERE subquery_where)

格式三：

(oe_1, ..., oe_N) [NOT] IN (SELECT ie_1, ..., ie_N FROM ... WHERE subquery_where)

對于IN類型子查詢的優化（可以轉換的形式和轉換需要的必備條件分為幾種情況），如表2-7所示。

表2-7 IN類型子查詢優化的情況表

情況一：outer_expr和inner_expr均為非NULL值。

優化后的表達式（外部條件outer_expr下推到子查詢中）如下：

EXISTS (SELECT 1 FROM ... WHERE subquery_where AND outer_expr=inner_expr)

即：

EXISTS (SELECT 1 FROM ... WHERE subquery_where
                          AND oe_1 = ie_1
                          AND ...
                          AND oe_N = ie_N)

子查詢優化需要滿足的以下兩個條件（全部滿足）：

?outer_expr和inner_expr不能為NULL。

?不需要從結果為FALSE的子查詢中區分NULL。

情況二：outer_expr是非NULL值（情況一的兩個轉換條件中至少有一個不滿足時）。

優化后的表達式（外部條件outer_expr下推到子查詢中，另外內部條件inner_expr為NULL）如下：

EXISTS (SELECT 1 FROM ... WHERE subquery_where AND
        (outer_expr=inner_expr OR inner_expr IS NULL))

假設outer_expr是非NULL值，但是如果outer_expr=inner_expr表達式不產生數據，則outer_expr IN(SELECT...)的計算結果如果是NULL值或FALSE值時，轉換條件如下：

?為NULL值。SELECT語句查詢得到任意的行數據，inner_expr是NULL（outer_expr IN(SELECT...)==NULL）。

?為FALSE值。SELECT語句產生非NULL值或不產生數據（outer_expr IN(SELECT...)==FALSE）。

情況三：outer_expr為NULL值。

原先的表達式等價于如下形式：

NULL IN (SELECT inner_expr FROM ... WHERE subquery_where)

假設outer_expr是NULL值，NULL IN(SELECT inner_expr...)的計算結果如果是NULL值或FALSE值時，轉換條件如下：

?為NULL值。SELECT語句產生任意行數據。

?為FALSE值。SELECT語句不產生數據。

對于上面的等價形式，還有兩點需要說明：

?謂詞IN等價于=ANY，例如下面的兩條SQL語句是等價的：

SELECT col_1 FROM t1 WHERE col_1 = ANY (SELECT col_1 FROM t2);
SELECT col_1 FROM t1 WHERE col_1 IN(SELECT col_1 FROM t2);

?帶有謂詞IN的子查詢，如果滿足上述3種情況，可以做等價變換，把外層的條件下推到子查詢中，變形為一個EXISTS類型的邏輯表達式判斷；而子查詢為EXISTS類型則可以被半連接算法實現優化。

下面我們看幾個具體的示例（以PostgreSQL為例說明子查詢優化的情況）。

示例1 初始數據如下所示：

test=# SELECT * FROM x;
x_num | x_name
------+-----------
    1 | X_1
    2 | X_2
     | X_3
(3 rows)
test=# SELECT * FROM y;
y_num | y_name
----------+-----------
    1 | Y_1
      | Y_2
    3 | Y_3
(3 rows)

執行如下子查詢命令：

test=# SELECT * FROM x WHERE x_num IN(SELECT y_num FROM y); //IN子查詢
 x_num | x_name
----------+-----------
     1 | X_1
(1 row)

執行計劃具體如下：

test=# EXPLAIN SELECT * FROM xWHERE x_num IN(SELECT y_num FROM y);
                         QUERY PLAN
-------------------------------------------------------------
Hash IN Join(cost=1.07..2.14 rows=3 width=18)
  Hash Cond: (x.x_num = y.y_num)
  -＞Seq Scan on x(cost=0.00..1.03 rows=3 width=18)
  -＞Hash(cost=1.03..1.03 rows=3 width=4)
      -＞Seq Scan on y(cost=0.00..1.03 rows=3 width=4)
(5 rows)

示例說明：

?Hash IN Join表示執行的是兩表Hash連接（已經使用兩表連接替代了子查詢），IN表示原子查詢是“IN子查詢”。

?原始查詢SQL中沒有(x.x_num=y.y_num)，只是一個IN子查詢，而查詢計劃中出現(x.x_num=y.y_num)，表明此IN子查詢被優化，優化后執行的是符合連接條件(x.x_num=y.y_num)的一個兩表連接的查詢。

示例2 表t_1、表t_2定義和數據如下所示：

CREATE TABLE t_1 (t_1_id INT UNIQUE, t_1_col_1 INT, t_1_col_2 VARCHAR(10));
CREATE TABLE t_2 (t_2_id INT UNIQUE, t_2_col_1 INT, t_2_col_2 VARCHAR(10));
INSERT INTO t_1 VALUES (1, 11, 't_1_1');
INSERT INTO t_1 VALUES (2, 12, NULL);
INSERT INTO t_1 VALUES (3, NULL, 't_1_3');
INSERT INTO t_1 VALUES (4, 14, 't_1_4');
INSERT INTO t_1 VALUES (5, 15, NULL);
INSERT INTO t_1 VALUES (7, NULL, NULL);
INSERT INTO t_2 VALUES (1, 11, 't_2_1');
INSERT INTO t_2 VALUES (2, NULL, 't_2_2');
INSERT INTO t_2 VALUES (3, 13, NULL);
INSERT INTO t_2 VALUES (4, 14, 't_2_4');
INSERT INTO t_2 VALUES (6, 16, 't_2_6');
INSERT INTO t_2 VALUES (7, NULL, NULL);

語句一 簡單的IN子查詢如下：

SELECT t_1.* FROM t_1 WHERE t_1_id IN (SELECT t_2_id FROM t_2);

語句二 簡單IN子查詢但子查詢結果不影響父查詢，如下所示：

SELECT t_1.* FROM t_1 WHERE 10 IN (SELECT t_2_id FROM t_2);

語句三 父查詢中的易失函數影響子查詢的優化，如下所示：

SELECT t_1.* FROM t_1 WHERE t_1_id + div((random()*10)::numeric,2) IN (SELECT t_2_idFROM t_2);

對于語句一，簡單的IN子查詢的查詢執行計劃如下：

test=# EXPLAIN SELECT t_1.* FROM t_1 WHERE t_1_id IN (SELECT t_2_id FROM t_2);
                            QUERY PLAN
-----------------------------------------------------------
Hash Semi Join(cost=45.33..94.58 rows=1570 width=22)
  Hash Cond: (t_1.t_1_id = t_2.t_2_id)
  -＞Seq Scan on t_1(cost=0.00..25.70 rows=1570 width=22)
  -＞Hash(cost=25.70..25.70 rows=1570 width=4)
      -＞Seq Scan on t_2(cost=0.00..25.70 rows=1570 width=4)
(5 rows)

查詢優化器對查詢做了優化，把子查詢轉換使用t_1.t_1_id=t_2.t_2_id作為連接條件的為Hash半連接（Hash Semi Join）。如果不做優化，則t_1表有多少條記錄，就需要掃描t_2表多少次，而且每次都得對t_2表做全表順序掃描，這樣會花費較多時間；而優化后，對t_2表只做了一次全表順序掃描，然后采用Hash Semi Join算法，對t_1和t_2做連接操作即可，節約了很多次對t_2表的全表掃描，達到了優化的目的。

對于語句二，簡單卻不影響父查詢的IN子查詢的查詢執行計劃如下：

test=# EXPLAIN SELECT t_1.* FROM t_1 WHERE 10 IN (SELECT t_2_id FROM t_2);
                            QUERY PLAN
---------------------------------------------------------------------------------
 Result(cost=29.63..55.33 rows=1570 width=22)
   One-Time Filter: (hashed SubPlan 1)
   -＞Seq Scan on t_1(cost=29.63..55.33 rows=1570 width=22)
 SubPlan 1
    -＞Seq Scan on t_2(cost=0.00..25.70 rows=1570 width=4)
(5 rows)

查詢優化器不能對查詢做優化。查詢計劃是對t_2做一個順序掃描，結果作為過濾器為t_1掃描服務。子查詢與上層查詢（t_1表所在的查詢）沒有關系，而IN子查詢的左操作符是常量，所以對子查詢直接求值，沒有辦法做上拉優化。

對于語句三，帶有易失函數random()的IN子查詢的查詢執行計劃如下：

test=# EXPLAIN SELECT t_1.* FROM t_1 WHERE t_1_id + div((random()*10)::numeric,2) IN (SELECT t_2_idFROM t_2);
                           QUERY PLAN
----------------------------------------------------------------------------------
 Seq Scan on t_1(cost=29.63..86.73 rows=785 width=22)
   Filter: (hashed SubPlan 1)
 SubPlan 1
    -＞Seq Scan on t_2(cost=0.00..25.70 rows=1570 width=4)
(4 rows)

查詢中出現了易失函數random()，子查詢結果不確定，查詢優化器就不能對子查詢做優化。

（2）ALL/ANY/SOME類型

ALL/ANY/SOME類型的子查詢格式，具體如下：

outer_expr operator ANY (subquery)
outer_expr operator SOME (subquery)
outer_expr operator ALL (subquery)

ALL表示對于子查詢的全部元組進行operator指定的操作；ANY表示對于子查詢的任何元組進行operator指定的操作；SOME表示對于子查詢的某些元組進行operator指定的操作。另外，使用ALL/ANY/SOME類型的子查詢，還需要注意：

?operator為操作符，通常可以是＜、=＜、＞、＞=中的任何一個。具體是否支持某個操作符，取決于表達式值的類型。

?=ANY與IN含義相同，可以采用IN子查詢優化方法。

?SOME與ANY含義相同。

?NOT IN與＜＞ALL含義相同。

?NOT IN與＜＞ANY含義不相同。

?＜＞ANY表示不等于任何值。

對于ALL/ANY/SOME類子查詢的優化，如果子查詢中沒有GROUPBY子句，也沒有聚集函數，則下面的表達式還可以使用聚集函數MAX/MIN做類似下面的等價轉換：

?val＞ALL(SELECT...)等價變化為val＞MAX(SELECT...)

?val＜ALL(SELECT...)等價變化為val＜MIN(SELECT...)

?val＞ANY(SELECT...)等價變化為val＞MIN(SELECT...)

?val＜ANY(SELECT...)等價變化為val＜MAX(SELECT...)

?val＞=ALL(SELECT...)等價變化為val＞=MAX(SELECT...)

?val＜=ALL(SELECT...)等價變化為val＜=MIN(SELECT...)

?val＞=ANY(SELECT...)等價變化為val＞=MIN(SELECT...)

?val＜=ANY(SELECT...)等價變化為val＜=MAX(SELECT...)

具體變換的形式如下：

val＞ANY (SELECT item ...)等價變化為val＞SELECT MIN(item)...

（3）EXISTS類型

EXISTS類型的子查詢格式如下：

[NOT] EXISTS (subquery)

這里有以下幾點需要注意：

?EXISTS對于子查詢而言，其結果值是布爾值；如果subquery有返回值，則整個EXISTS(subquery)的值為TRUE，否則為FALSE。

?EXISTS(subquery)不關心subquery返回的內容，這使得帶有EXISTS(subquery)的子查詢存在優化的可能。

?EXISTS(subquery)自身有著“半連接”的語義，所以，一些數據庫實現代碼中（如PostgreSQL），用半連接完成EXISTS(subquery)求值。

?NOT EXISTS(subquery)通常會被標識為“反半連接”處理。

?一些諸如IN(subquery)的子查詢可以等價轉換為EXISTS(subquery)格式，所以可以看到IN(subquery)的子查詢可被優化為半連接實現的表連接。

下面通過一個示例來進行說明。

示例3 沿用示例2的表和數據。

語句四 EXISTS類型的普通相關子查詢，子查詢條件和父查詢有關聯：

SELECT t_1.* FROM t_1 WHERE EXISTS (SELECT t_2_id FROM t_2 WHERE t_1_id=t_2_id);

語句五 EXISTS類型的普通相關子查詢，子查詢條件和子查詢沒有關系：

SELECT t_1.* FROM t_1 WHERE EXISTS (SELECT t_2_id FROM t_2 WHERE t_1_id=10);

語句六 EXISTS類型的普通非相關子查詢：

SELECT t_1.* FROM t_1 WHERE EXISTS (SELECT t_2_id FROM t_2 WHERE t_2_id=10);

語句七 EXISTS類型的普通非相關子查詢，子查詢簡單沒有表存在：

SELECT t_1.* FROM t_1 WHERE EXISTS (SELECT 10);

對于語句四，EXISTS類型的普通相關子查詢的查詢執行計劃如下：

test=# EXPLAIN SELECT t_1.* FROM t_1 WHERE EXISTS (SELECT t_2_id FROM t_2 WHERE t_1_id=t_2_id);
                            QUERY PLAN
---------------------------------------------------------------------------------
Hash Semi Join(cost=45.33..94.58 rows=1570 width=22)
   Hash Cond: (t_1.t_1_id = t_2.t_2_id)
   -＞Seq Scan on t_1(cost=0.00..25.70 rows=1570 width=22)
   -＞Hash(cost=25.70..25.70 rows=1570 width=4)
      -＞Seq Scan on t_2(cost=0.00..25.70 rows=1570 width=4)
(5 rows))

查詢優化器對查詢做了優化，通過子查詢上拉技術，把子查詢轉換為使用t_1.t_1_id=t_2.t_2_id作為連接條件實現Hash半連接（Hash Semi Join）操作。如果不做優化，則t_1表有多少條記錄，都需要掃描t_2表多少次，每次都得對t_2表做全表順序掃描，這樣會花費較多時間；而優化后，對t_2表只做了一次全表順序掃描，然后采用Hash Semi Join算法，對t_1和t_2做連接操作即可，節約了很多次對t_2表的全表掃描，達到了優化的目的。

對于語句五，EXISTS類型的普通相關子查詢的查詢執行計劃如下：

test=# EXPLAIN SELECT t_1.* FROM t_1 WHERE EXISTS (SELECT t_2_id FROM t_2 WHERE t_1_id=10);
                        QUERY PLAN
-----------------------------------------------------------------------------------------------------------
Nested Loop Semi Join(cost=0.00..33.99 rows=1 width=22)
 -＞Index Scan using t_1_t_1_id_key on t_1(cost=0.00..8.27 rows=1 width=22)
     Index Cond: (t_1_id = 10)
 -＞Seq Scan on t_2(cost=0.00..25.70 rows=1570 width=0)
(4 rows)

查詢優化器能對查詢做優化。通過子查詢上拉技術，查詢執行計劃對子查詢t_2做一個順序掃描，然后與做順序掃描的t_1表掃描的結果進行嵌套循環半連接（Nested Loop Semi Join）。

對于語句六，EXISTS類型的普通非相關子查詢的查詢執行計劃如下：

test=# EXPLAIN SELECT t_1.* FROM t_1 WHERE EXISTS (SELECT t_2_id FROM t_2 WHERE t_2_id=10);
                                     QUERY PLAN
--------------------------------------------------------------------------------------------------------------------------------------
 Result(cost=8.27..33.97 rows=1570 width=22)
 One-Time Filter: $0
 InitPlan 1 (returns $0)
    -＞Index Scan using t_2_t_2_id_key on t_2(cost=0.00..8.27 rows=1 width=0)
          Index Cond: (t_2_id = 10)
 -＞Seq Scan on t_1(cost=0.00..25.70 rows=1570 width=22)
(6 rows)

子查詢是非相關子查詢，子查詢只要執行一次即可推知EXISTS的結果是TRUE或FALSE，所以不會執行多次，也沒有必要進行優化，所以查詢執行計劃中存在One-Time，表示只執行一次。

對于語句七，EXISTS類型的非相關子查詢的查詢執行計劃如下：

test=# EXPLAIN SELECT t_1.* FROM t_1 WHERE EXISTS (SELECT 10);
                           QUERY PLAN
------------------------------------------------------------------------------------------
 Result(cost=0.01..25.71 rows=1570 width=22)
   One-Time Filter: $0
   InitPlan 1 (returns $0)
      -＞Result(cost=0.00..0.01 rows=1 width=0)
     -＞Seq Scan on t_1(cost=0.00..25.70 rows=1570 width=22)
(5 rows)

子查詢比語句三更為簡單，道理同對語句六的分析。查詢執行計劃中存在One-Time，表示只執行一次。

2.2.2 視圖重寫

視圖是數據庫中基于表的一種對象，視圖重寫就是將對視圖的引用重寫為對基本表的引用。視圖重寫后的SQL多被作為子查詢進行進一步優化。所有的視圖都可以被子查詢替換，但不是所有的子查詢都可以用視圖替換。這是因為，子查詢的結果作為一個結果集，如果是單行單列（標量），則可以出現在查詢語句的目標列；如果是多行多列，可以出現在FROM、WHERE等子句中。但即使是標量視圖（視圖等同于表對象），也不可以作為目標列單獨出現在查詢語句中。

從視圖的構成形式看，類似于查詢的SPJ與非SPJ，視圖可以分為簡單視圖和復雜視圖。

?用SPJ格式構造的視圖，稱為簡單視圖。

?用非SPJ格式構造（帶有GROUPBY等操作）的視圖，稱為復雜視圖。

下面通過一個例子來具體看一下視圖重寫。SQL語句如下：

CREATE TABLE t_a(a INT, b INT);
CREATE VIEW v_a AS SELECT * FROM t_a;

基于視圖的查詢命令如下：

SELECT col_a FROM v_a WHERE col_b＞100;

經過視圖重寫后可變換為如下形式：

SELECT col_a FROM
(
    SELECT col_a, col_b FROM t_a
)
WHERE col_b＞100;

未來經過優化，可以變換為如下等價形式：

SELECT col_a FROM t_a WHERE col_b＞100;

簡單視圖能夠被查詢優化器較好地處理；但是復雜視圖則不能被查詢優化器很好地處理。一些商業數據庫，如Oracle，提供了一些視圖的優化技術，如“復雜視圖合并”、“物化視圖查詢重寫”等。但從整體上看，復雜視圖優化技術還有待繼續提高。

2.2.3 等價謂詞重寫

數據庫執行引擎對一些謂詞處理的效率要高于其他謂詞，基于這點，把邏輯表達式重寫成等價的且效率更高的形式，能有效提高查詢執行效率。這就是等價謂詞重寫。

常見的等價謂詞重寫規則如下。

1.LIKE規則

LIKE謂詞是SQL標準支持的一種模式匹配比較操作，LIKE規則是對LIKE謂詞的等價重寫，即改寫LIKE謂詞為其他等價的謂詞，以更好地利用索引進行優化。如列名為name的LIKE操作示例如下：

name LIKE 'Abc%'

重寫為：

name＞='Abc' AND name ＜'Abd'

應用LIKE規則的好處是：轉換前針對LIKE謂詞只能進行全表掃描，如果name列上存在索引，則轉換后可以進行索引范圍掃描。

LIKE其他形式還可以轉換：LIKE匹配的表達式中，若沒有通配符（%或_），則與=等價。如：

name LIKE 'Abc'

重寫為：

name='Abc'

2.BETWEEN-AND規則

BETWEEN-AND謂詞是SQL標準支持的一種范圍比較操作，BETWEEN-AND規則是指BETWEEN-AND謂詞的等價重寫，即改寫BETWEEN-AND謂詞為其他等價的謂詞，以更好地利用索引進行優化。BETWEEN-AND謂詞的等價重寫類似于LIKE謂詞的等價重寫，如：

sno BETWEEN 10 AND 20

重寫為：

sno＞=10 AND sno ＜=20

應用BETWEEN-AND規則的好處是：如果sno上建立了索引，則可以用索引掃描代替原來BETWEEN-AND謂詞限定的全表掃描，從而提高了查詢的效率。

3.IN轉換OR規則

IN是只IN操作符操作，不是IN子查詢。IN轉換OR規則就是IN謂詞的OR等價重寫，即改寫IN謂詞為等價的OR謂詞，以更好地利用索引進行優化。將IN謂詞等價重寫為若干個OR謂詞，可能會提高執行效率。如：

age IN (8,12,21)

重寫為：

age=8 OR age=12 OR age=21

應用IN轉換OR規則后效率是否能夠提高，需要看數據庫對IN謂詞是否只支持全表掃描。如果數據庫對IN謂詞只支持全表掃描且OR謂詞中表的age列上存在索引，則轉換后查詢效率會提高。

4.IN轉換ANY規則

IN轉換ANY規則就是IN謂詞的ANY等價重寫，即改寫IN謂詞為等價的ANY謂詞。因為IN可以轉換為OR，OR可以轉為ANY，所以可以直接把IN轉換為ANY。將IN謂詞等價重寫為ANY謂詞，可能會提高執行效率。如：

age IN (8,12,21)

重寫為：

age ANY(8,12,21)

應用IN轉換ANY規則后效率是否能夠提高，依賴于數據庫對于ANY操作的支持情況。如，PostgreSQL沒有顯式支持ANY操作，但是在內部實現時把IN操作轉換為了ANY操作，如下所示：

test=# \d t1;
  資料表 "public.t1"
 欄位 |型別 | 修飾詞
--------+----------+----------
 id1| integer | 非空
 a1 | integer |
 b1 | integer |
索引：
   "t1_pkey" PRIMARY KEY, btree (id1)
test=# EXPLAIN SELECT * FROM t1 WHERE a1 IN (1,3,5);
                       QUERY PLAN
---------------------------------------------------------------------------
Seq Scan on t1(cost=0.00..192.50 rows=3 width=12)
  Filter: (a1 = ANY ('{1,3,5}'::integer[]))
(2 行記錄)

5.OR轉換ANY規則

OR轉換ANY規則就是OR謂詞的ANY等價重寫，即改寫OR謂詞為等價的ANY謂詞，以更好地利用MIN/MAX操作進行優化。如：

sal＞1000 OR dno=3 AND (sal＞1100 OR sal＞base_sal+100) OR sal＞base_sal+200 OR sal＞base_sal*2

重寫為：

dno=3 AND (sal＞1100 OR sal＞base_sal+100) OR sal＞ANY (1000, base_sal+200, base_sal*2)

OR轉換ANY規則依賴于數據庫對于ANY操作的支持情況。PostgreSQL V9.2.3和MySQLV5.6.10目前都不支持本條規則。

6.ALL/ANY轉換集函數規則

ALL/ANY轉換集函數規則就是將ALL/ANY謂詞改寫為等價的聚集函數MIN/MAX謂詞操作，以更好地利用MIN/MAX操作進行優化。如：

sno＞ANY(10, 2*5+3, sqrt(9))

重寫為：

sno＞sqrt(9)

上面這個ALL/ANY轉換集函數規則的示例，有以下兩點需要注意：

?本示例中存在＞和ANY，其意是在找出(10，2*5+3，sqrt(9))中的最小值，所以可以重寫為sno＞sqrt(9)。

?通常，聚集函數MAX()、MIN()等的執行效率比ANY、ALL謂詞的執行效率高，因此在這種情況下對其進行重寫可以起到比較好的效果。如果有索引存在，求解MAX/MIN的效率更高。

7.NOT規則

NOT謂詞的等價重寫。如下：

NOT (col_1 !=2)重寫為col_1=2
NOT (col_1 !=col_2)重寫為col_1=col_2
NOT (col_1 =col_2)重寫為col_1!=col_2
NOT (col_1 ＜col_2)重寫為col_1＞=col_2
NOT (col_1 ＞col_2)重寫為col_1＜=col_2

NOT規則重寫的好處是：如果在col_1上建立了索引，則可以用索引掃描代替原來的全表掃描，從而提高查詢的效率。

8.OR重寫并集規則

OR條件重寫為并集操作，形如以下SQL示例：

SELECT *
FROM student
WHERE(sex='f' AND sno＞15) OR age＞18;

假設所有條件表達式的列上都有索引（即sex列和age列上都存在索引），數據庫可能對于示例中的WHERE語句強迫查詢優化器使用順序存取，因為這個語句要檢索的是OR操作的集合。為了能利用索引處理上面的查詢，可以將語句改成如下形式：

SELECT *
FROM student
WHERE sex='f' and sno＞15
UNION
SELECT *
FROM student
WHERE age＞18;

改寫后的形式，可以分別利用列sex和age上的索引，進行索引掃描，然后再提供執行UNION操作獲得最終結果。

2.2.4 條件化簡

WHERE、HAVING和ON條件由許多表達式組成，而這些表達式在某些時候彼此之間存在一定的聯系。利用等式和不等式的性質，可以將WHERE、HAVING和ON條件化簡，但不同數據庫的實現可能不完全相同。

將WHERE、HAVING和ON條件化簡的方式通常包括如下幾個：

?把HAVING條件并入WHERE條件。便于統一、集中化解條件子句，節約多次化解時間。但不是任何情況下HAVING條件都可以并入WHERE條件，只有在SQL語句中不存在GROUPBY條件或聚集函數的情況下，才能將HAVING條件與WHERE條件的進行合并。

?去除表達式中冗余的括號。這樣可以減少語法分析時產生的AND和OR樹的層次。如((a AND b)AND(c AND d))就可以化簡為a AND b AND c AND d。

?常量傳遞。對不同關系可以使得條件分離后有效實施“選擇下推”，從而可以極大地減小中間關系的規模。如col_1=col_2AND col_2=3就可以化簡為col_1=3AND col_2=3。操作符=、＜、＞、＜=、＞=、＜＞、LIKE中的任何一個，在col_1＜操作符＞col_2條件中都會發生常量傳遞。

?消除死碼。化簡條件，將不必要的條件去除。如WHERE(0＞1AND s1=5)，0＞1使得AND恒為假，則WHERE條件恒為假。此時就不必再對該SQL語句進行優化和執行了，加快了查詢執行的速度。

?表達式計算。對可以求解的表達式進行計算，得出結果。如WHERE col_1=1+2變換為WHERE col_1=3。

?等式變換。化簡條件（如反轉關系操作符的操作數的順序），從而改變某些表的訪問路徑。如-a=3可化簡為a=-3。這樣的好處是如果a上有索引，則可以利用索引掃描來加快訪問。

?不等式變換。化簡條件，將不必要的重復條件去除。如a＞10AND b=6AND a＞2可化簡為b=6AND a＞10。

?布爾表達式變換。在上面的內容中，涉及了一些布爾表達式參與的變換（如上一條中的示例是AND的表達式）。布爾表達式還有如下規則指導化簡。

○謂詞傳遞閉包。一些比較操作符，如＜、＞等，具有傳遞性，可以起到化簡表達式的作用。如由a＞b AND b＞2可以推導出a＞b AND b＞2AND a＞2，a＞2是一個隱含條件，這樣把a＞2和b＞2分別下推到對應的關系上，就可以減少參與比較操作a＞b的元組了。

○任何一個布爾表達式都能被轉換為一個等價的合取范式（CNF）。因為合取項只要有一個為假，整個表達式就為假，故代碼中可以在發現一個合取項為假時，即停止其他合取項的判斷，以加快判斷速度。另外因為AND操作符是可交換的，所以優化器可以按照先易后難的順序計算表達式，一旦發現一個合取項為假時，即停止其他合取項的判斷，以加快判斷速度。

○索引的利用。如果一個合取項上存在索引，則先判斷索引是否可用，如能利用索引快速得出合取項的值，則能加快判斷速度。同理，OR表達式中的子項也可以利用索引。

2.2.5 外連接消除

外連接消除是查詢優化器的主要功能之一。下面從外連接消除的意義和條件兩方面對外連接優化技術進行介紹。

1.外連接消除的意義

外連接操作可分為左外連接、右外連接和全外連接。連接過程中，外連接的左右子樹不能互換，并且外連接與其他連接交換連接順序時，必須滿足嚴格的條件以進行等價變換。這種性質限制了優化器在選擇連接順序時能夠考慮的表與表交換連接位置的優化方式。

查詢重寫的一項技術就是把外連接轉換為內連接，轉換的意義（對優化的意義）如下：

?查詢優化器在處理外連接操作時所需執行的操作和時間多于內連接。

?優化器在選擇表連接順序時，可以有更多更靈活的選擇，從而可以選擇更好的表連接順序，加快查詢執行的速度。

?表的一些連接算法（如塊嵌套連接和索引循環連接等）將規模小的或篩選條件最嚴格的表作為“外表”（放在連接順序的最前面，是多層循環體的外循環層），可以減少不必要的IO開銷，極大地加快算法執行的速度。

為什么外連接可以轉換為內連接？為了弄明白其中的原因，我們先來看一下表2-8（借助PostgreSQL對外連接的注釋）。

表2-8 PostgreSQL外連接注釋表

下面我們分3種情況討論表2-8。

情況一：左外連接向內連接轉換。

?觀察表2-8，先看θ-連接和左外連接，相同之處在于都具有A部分，不同之處表現在B部分有差異。左外連接比θ-連接多了B部分。這表明左外連接的結果中，會比θ-連接多出“不滿足連接條件的外表中的元組（unmatched LHS tuples）”。

?假設一個左外連接執行之后，其結果等同于內連接，即B部分不存在，則這種情況下，左外連接就可以向內連接轉換。這種轉換是有條件的，條件是：右面關系中對應的條件，保證最后的結果集中不會出現B部分這樣特殊的元組（這樣的條件稱為“reject-NULL條件”）。

?不是所有的左外連接都可以向內連接轉換，需要滿足一定的條件才可以是等價轉換。

?左外連接向內連接轉換，語義滿足左外連接，但實際結果因兩個表中數據的有特點（滿足reject-NULL條件）。形式上看是外連接，其實質成為一種褪化的內連接。

情況二：全外連接向左外連接轉換。

?觀察表2-8，先看全外連接和左外連接，相同之處在于都具有A、B部分，不同之處表現在C部分有差異。全外連接比左外連接多了C部分。

?假設一個全外連接執行之后，其結果等同于左外連接，即C部分不存在，則這種情況下，全外連接就可以向左外連接轉換。這種轉換是有條件的，條件是：左面關系中對應的條件，保證最后的結果集中不會出現C部分這樣特殊的元組。

?不是所有的全外連接都可以向左外連接轉換，需要滿足一定條件才可以是等價轉換。

?全外連接向左連接轉換，形式滿足全外連接，但實際結果因兩個表中數據的特點，其實質成為一種褪化的左外連接。

?全外連接向右外連接轉換，基本道理等同向左外連接轉換，不贅述。

?全外連接如果能同時向左外連接和右外連接轉換，則意味著全外連接能轉換為內連接。其條件是：左面和右面關系中對應的條件，均能滿足reject-NULL條件。

情況三：右外連接向內連接轉換。

?在實際處理中，因右外連接對稱等同左外連接，所以通常都是把右外連接轉換為左外連接，然后再向內連接轉換。

?右外連接向左外連接轉換，通常是發生在語法分析階段（這是一種外表樣式的轉換，但不是全部），在進入查詢優化階段后，才對左外連接和全外連接進行等價轉換（進入優化器后執行的這個轉換，需要對連接的列和查詢的列做判斷，所以語法分析階段沒有得到列的詳細信息是不能進行此優化的）。

下面我們通過一個例子，來幫助讀者對上述知識加深理解。

示例4 具體的示例代碼如下：

SELECT * FROM t_1 LEFT JOIN t_2 ON t_2.a=t_1.a WHERE t_2.b = 5;

由上述示例代碼可知，左外連接的內表（t_2）不能先于外表（t_1）被訪問，所以查詢計劃優化階段，只能將表的連接順序定為(t_1，t_2)，而不是(t_2，t_1)。

如果t_1表的元組數很大，t_2.b上建有唯一索引，但查詢效率會很低。但是，如果能交換t_1和t_2的表連接順序，即表的連接順序為(t_2，t_1)，則可以利用t_2.b=5條件迅速降低運算的中間規模，提高查詢的速度。

2.外連接消除的條件

外連接可轉換為內連接的條件：WHERE子句中與內表相關的條件滿足“空值拒絕”（reject-NULL條件）。那么條件怎么才算是滿足空值拒絕呢？一般認為滿足下面任意一種情況時，即滿足空值拒絕：

?條件可以保證從結果中排除外連接右側（右表）生成的值為NULL的行（即條件確保應用在右表帶有空值的列對象上時，條件不滿足，條件的結果值為FLASE或UNKOWEN，這樣右表就不會有值為NULL的行生成），所以能使該查詢在語義上等效于內連接。

?外連接的提供空值的一側（可能是左側的外表也可能是右側的內表）為另一側的每行只返回一行。如果該條件為真，則不存在提供空值的行，并且外連接等價于內連接。

示例5 以PostgreSQL對外連接的優化為例，初始數據如下：

create table X (X_num int, X_name varchar(10));
create table Y (Y_num int, Y_name varchar(10));
insert into X values(1, 'X_1');
insert into X values(2, 'X_2');
insert into X values(NULL, 'X_3');
insert into Y values(1, 'Y_1');
insert into Y values(NULL, 'Y_2');
insert into Y values(3, 'Y_3');

例如，如下3種外連接查詢語句，外連接處理方式不同。

語句一 表X和Y執行簡單左外連接：

SELECT * FROM X LEFT JOIN Y on (X.X_num=Y.Y_num);

語句二 表X和Y執行簡單左外連接，但帶有WHERE條件且內表Y的連接條件列非空：

SELECT * FROM X LEFT JOIN Y ON (X.X_num=Y.Y_num) WHERE Y.Y_num IS NOT NULL;

語句三 表X和Y執行內連接，帶有WHERE條件：

SELECT * FROM X, Y WHERE X.X_num=Y.Y_num;

通過查詢計劃看優化結果，具體如下：

對于語句一，左外連接不滿足優化條件，沒有被優化。查詢執行計劃如下：

test=# EXPLAIN SELECT * FROM X LEFT JOIN Y on (X.X_num=Y.Y_num);
                            QUERY PLAN
------------------------------------------------------------------
Merge Left Join(cost=236.43..461.68 rows=14450 width=36)//左外連接
   Merge Cond: (x.x_num = y.y_num)
   -＞Sort(cost=118.22..122.47 rows=1700 width=18)
       Sort Key: x.x_num
       -＞Seq Scan on x(cost=0.00..27.00 rows=1700 width=18)
   -＞Sort(cost=118.22..122.47 rows=1700 width=18)
       Sort Key: y.y_num
       -＞Seq Scan on y(cost=0.00..27.00 rows=1700 width=18)
(8 rows)

查詢語句中只有連接條件X.X_num=Y.Y_num，沒有WHERE條件，所以不滿足空值拒絕中的任何一個條件，所以查詢優化器沒有把左外連接優化為連接操作，執行的是歸并左外連接操作（Merge Left Join）。

對于語句二，左外連接被優化為內連接，查詢執行計劃如下：

test=# EXPLAIN SELECT * FROM X LEFT JOIN Y ON (X.X_num=Y.Y_num) WHERE Y.Y_num ISNOT NULL;
                             QUERY PLAN
--------------------------------------------------------------------------------------------
Merge Join(cost=235.88..459.93 rows=14373 width=36)/* 因為存在WHERE子句中內表對應的列滿足“空值拒絕”，使得左外連接可以被優化為內連接 */
   Merge Cond: (y.y_num = x.x_num)
   -＞Sort(cost=117.67..121.90 rows=1691 width=18)
       Sort Key: y.y_num
       -＞Seq Scan on y(cost=0.00..27.00 rows=1691 width=18)
           Filter: (y_num IS NOT NULL)
    -＞Sort(cost=118.22..122.47 rows=1700 width=18)
        Sort Key: x.x_num
        -＞Seq Scan on x(cost=0.00..27.00 rows=1700 width=18)
(9 rows)

查詢語句除了連接條件X.X_num=Y.Y_num外，包含WHERE條件（Y.Y_num IS NOT NULL），滿足空值拒絕中的第一個條件，所以查詢優化器把左外連接優化為連接操作，執行的是歸并連接操作（Merge Join）。

對于語句三，內連接等價于上一種的可被優化的左外連接，查詢執行計劃如下：

test=# explain SELECT * FROM X, Y WHERE X.X_num=Y.Y_num;
                             QUERY PLAN
-----------------------------------------------------------------------------------------
Merge Join (cost=236.43..461.68 rows=14450 width=36)//內連接
   Merge Cond: (x.x_num = y.y_num)
   -＞Sort(cost=118.22..122.47 rows=1700 width=18)
       Sort Key: x.x_num
       -＞Seq Scan on x(cost=0.00..27.00 rows=1700 width=18)
   -＞Sort (cost=118.22..122.47 rows=1700 width=18)
       Sort Key: y.y_num
       -＞Seq Scan on y(cost=0.00..27.00 rows=1700 width=18)
 (8 rows)

普通查詢語句連接條件為X.X_num=Y.Y_num，查詢優化器把執行連接操作等價于上一種的可被優化的左外連接，查詢執行計劃除花費（cost）外完全相同。

最后，可以通過執行上兩條SQL語句，查看查詢結果，驗證兩者等價。具體結果如下：

test=# SELECT * FROM X, Y WHERE X.X_num=Y.Y_num;
x_num | x_name | y_num | y_name
----------+------------+-----------+--------
    1 | X_1 |1 | Y_1
(1 row)
test=# SELECT * FROM X LEFT JOIN Y on (X.X_num=Y.Y_num) WHERE Y.Y_num IS NOT NULL;
x_num | x_name | y_num | y_name
----------+------------+-----------+--------
    1 | X_1 |1 | Y_1
(1 row)

注意

對于外連接的查詢優化，從格式上看用戶書寫的SQL可能是語句一的格式，但這種格式因其他原因，存在被改寫為語句二的格式的可能。查詢優化前通過對條件的分析，就是要確認是否可以為語句一的格式找到滿足語句二的格式中的WHERE Y.Y_num IS NOT NULL類似條件，如果能找到這樣的條件，則查詢優化器可自動對第一種左外連接做優化，轉換為語句二的格式。

2.2.6 嵌套連接消除

多表連接有時會存在嵌套的情況。對于一個無嵌套的多表連接，表之間的連接次序是可以交換的，這樣能靈活求解不同連接方式的花費，進而得到最小花費的連接方式。而嵌套連接則不能夠利用交換表的位置而獲得優化。

那么，什么是嵌套連接呢？

當執行連接操作的次序不是從左到右逐個進行時，就說明這樣的連接表達式存在嵌套。看下面的例子：

SELECT *
FROM t1 LEFT JOIN (t2 LEFT JOIN t3 ON t2.b=t3.b) ON t1.a=t2.a
WHERE t1.a ＞ 1

先t2與t3連接，得到中間結果{t2t3}后再與t1連接，這種方式就是嵌套連接，括號不可以去掉，沒有去掉括號的等價形式。如果連接順序是t1、t2、t3，則不存在嵌套。

另外，如下格式也是嵌套，這種格式用括號把連接次序做了區分。

SELECT * FROM A JOIN (B JOIN C ON B.b1=C.c1) ON A.a1=B.b1 WHERE A.a1 ＞ 1;

上面的格式可以等價轉換為（圓括號去掉，不影響原先語義）下面的格式：

SELECT * FROM A JOIN B JOIN C ON B.b1=C.c1 ON A.a1=B.b1 WHERE A.a1 ＞ 1;

綜上所述，我們得到以下兩條結論：

?如果連接表達式只包括內連接，括號可以去掉，這意味著表之間的次序可以交換，這是關系代數中連接的交換律的應用。

?如果連接表達式包括外連接，括號不可以去掉，意味著表之間的次序只能按照原語義進行，至多能執行的就是外連接向內連接轉換的優化，該部分的內容詳見2.2.5節。

2.2.7 連接消除

根據不同分類角度，連接可以分成很多種：根據連接語義方式的不同分為內連接、外連接、半連接、反半連接等；根據連接對象的不同分為自連接（FROM子句后同一個表出現多次，并連接）和非自連接；根據連接條件的有無分為笛卡兒積式的連接和帶有限定條件的連接；根據連接條件形式的不同分為等值連接（如支持=）和范圍連接（如支持＞、＜、＜＞）。

有的連接類型可能有特定的優化方式（如外連接可優化）。除了以上可能的連接類型外，在某些特殊的情況下（例如下文的情況一、情況二、情況三），可能存在一些連接，這些連接中的連接對象可以被去掉（因為這樣的連接對象存在只會帶來連接計算的耗費，而對連接結果沒有影響），所以這類連接存在優化的可能，其中的一些連接是可以消除掉的。

下面我們就分情況看看這些連接。

情況一：主外鍵關系的表進行的連接，可消除主鍵表，這不會影響對外鍵表的查詢。

例如，創建表定義如下：

CREATE TABLE B (b1 INT, b2 VARCHAR(9), PRIMARY KEY(b1));
CREATE TABLE A (a1 INT, a2 VARCHAR(9), FOREIGN KEY(a1) REFERENCES B(b1) );
CREATE TABLE C (c1 INT, c2 VARCHAR(9));

對于關系A、B、C，如果存在A參照B（連接條件上是主外鍵關系，A依賴于B），且三者之間的連接條件是等值連接（A join B join C，連接條件是A.a1=B.b1AND B.b1=C.c1），結果集不包含關系B中的任何屬性，且在B上沒有任何限定條件，那么A的連接條件上添加連接屬性不為空的限制后（因為A.a1=B.b1連接，而B.b1是主鍵，不為NULL），可以去除關系B，這樣優化不會影響結果（即優化為A join C，連接條件變為A.a1=C.c1AND A.a1IS NOT NULL；因為等值連接A.a1=C.c1，如果遇到NULL=NULL的情況，通常的處理都是FALSE，所以。以上條件可以進一步簡化為A.a1=C.c1，但請注意A依賴于B的條件不變）。

如果關系A、B、C中B沒有主鍵（主鍵保證了非空約束的存在），則當B.b1=NULL時，A.a1和C.c1為非NULL時，A.a1=C.c1的連接方式（即消除B的連接方式）和A.a1=B.b1AND B.b1=C.c1的連接方式（即沒有消除B的連接方式）相比，前一種連接方式比后一種產生了新的元組，所以不存在連接可以消除的可能。

再進一步，如果關系A、B、C中B有主鍵，但A不依賴于B（無主外鍵關系），三者之間的連接條件是等值連接（A join B join C，連接條件是A.a1=B.b1AND B.b1=C.c1），因為B有主鍵，意味著B非NULL所以A.a1和C.c1都應該為非NULL，才可能保證連接可以消除（連接條件變為A.a1=C.c1AND A.a1IS NOT NULL AND C.c1IS NOT NULL）。但實際上不是這樣，B和A沒有依賴關系的時候，單純靠A、C之間的條件，因為去掉B使得A中存在的值沒有受到B的限制，所以不能保證B可被放心地去掉。在有主外鍵約束的情況下，A.a1依賴B.b1使得A.a1的值范圍受到約束（A.a1的值在生成時已經參照了B.b1)，所以可以放心地去掉B。

如果對于關系A、B存在A參照B（連接條件上是主外鍵關系，A依賴于B），且二者之間的連接條件是等值連接（A join B，連接條件是A.a1=B.b1），則經過連接消除，二表連接變為單表掃描（A.a1IS NOT NULL），這樣能有效提高SQL的執行效率。

情況二：唯一鍵作為連接條件，三表內連接可以去掉中間表（中間表的列只作為連接條件）。

舉例說明，假設3個表都有唯一鍵存在，如下所示：

CREATE TABLE A (a1 INT UNIQUE, a2 VARCHAR(9), a3 INT);
CREATE TABLE B (b1 INT UNIQUE, b2 VARCHAR(9), c2 INT);
CREATE TABLE C (c1 INT UNIQUE, c2 VARCHAR(9), c3 INT);

B的列在WHERE條件子句中只作為等值連接條件存在，則查詢可以去掉對B的連接操作。

SELECT A.*, C.* FROM A JOIN B ON (a1=b1) JOIN CON (b1=c1);

相當于：

SELECT A.*, C.* FROM A JOIN C ON (a1= c1);

情況三：其他一些特殊形式，可以消除連接操作（可消除的表除了作為連接對象外，不出現在任何子句中，創建表的語句參見情況一）。示例如下：

SELECT MAX(a1) FROM A, B;/* 在這樣格式中的MIN、MAX函數操作可以消除連接,去掉B表不影響結果;其他聚集函數不可以 */
SELECT DISTINCT a3 FROM A, B; /* 對連接結果中的a3列執行去重操作*/
SELECT a1 FROM A, B GROUP BY a1;/* 對連接結果中的a1列執行分組操作 */

2.2.8 語義優化

因為語義的原因，使得SQL可以被優化。這里包括以下兩個基本概念：

?語義轉換。因為完整性限制等的原因使得一個轉換成立的情況稱為語義轉換。

?語義優化。因為語義轉換形成的優化稱為語義優化。

通常，任何的完整性限制條件等都可以用于語義優化。語義轉換其實是根據完整性約束等信息對“某特定語義”進行推理，進而得到的一種查詢效率不同但結果相同的查詢。語義優化是從語義的角度對SQL進行優化，不是一種形式上的優化，所以其優化的范圍，可能覆蓋其他類型的優化范圍。

語義優化常見的方式如下：

?連接消除（Join Elimination）。對一些連接操作先不必評估代價，根據已知信息（主要依據完整性約束等，但不全是依據完整性約束）能推知結果或得到一個簡化的操作。例如，利用A、B兩個基表做自然連接，創建一個視圖V，如果在視圖V上執行查詢只涉及其中一個基表的信息，則對視圖的查詢完全可以轉化為對某個基表的查詢。

?連接引入（Join Introduction）。增加連接有助于原關系變小或原關系的選擇率降低。

?謂詞引入（Predicate Introduction）。根據完整性約束等信息引入新謂詞，如引入基于索引的列，可能使得查詢更快。如一個表上，有c1＜c2的列約束，c2列上存在一個索引，查詢語句中的WHERE條件有c1＞200，則可以推知c2＞200，WHERE條件變更為c1＞200AND c2＞200AND c1＜c2，由此可以利用c2列上的索引，對查詢語句進行優化。如果c2列上的索引的選擇率很低，則優化效果會更高。

?檢測空回答集（Detecting the Empty Answer Set）。查詢語句中的謂詞與約束相悖，可以推知條件結果為FALSE，也許最終的結果集能為空；如CHECK約束限定score列的范圍是60到100，而一個查詢條件是score＜60，則能立刻推知條件不成立。

?排序優化（Order Optimizer）。ORDERBY操作通常由索引或排序（sort）完成；如果能夠利用索引，則排序操作可省略。另外，結合分組等操作，考慮ORDERBY操作的優化。

?唯一性使用（Exploiting Uniqueness）。利用唯一性、索引等特點，檢查是否存在不必要的DISTINCT操作，如在主鍵上執行DISTINCT操作，若有則可以把DISTINCT消除掉。

例如：

CREATE TABLE student (name VARCHAR(30) NOT NULL, age INT);

可被優化為如下形式：

SELECT * FROM student WHERE name IS NULL AND age＞18;

在上面的例子中，name列被定義為非空，這是完整性限制，但查詢條件和語義相悖，則可以直接返回name IS NULL=false，進而false AND age＞18=false，查詢語句可以終止。

2.2.9 針對非SPJ的優化

如果查詢中包含GROUPBY子句，那么這種查詢就稱為非SPJ查詢。

現在，決策支持系統、數據倉庫、OLAP系統的應用日益廣泛，SQL語句中的GROUPBY、聚集函數、WINDOWS函數（分析函數）等成為SQL語言的重要特性，被應用廣泛。

早期的關系數據庫系如System-R，對GROUPBY和聚集等操作一般都放在其所在的查詢的最后進行處理，即在執行完所有的連接和選擇操作之后再執行GROUPBY和聚集。這樣的處理方式比較簡單，而且編碼容易，但執行效率會比較低。所以，現代的商業數據庫和開源的數據庫，通常都使用了一些非SPJ的優化技術。

1.GROUPBY優化

對于GROUPBY的優化，可考慮分組轉換技術，即對分組操作、聚集操作與連接操作的位置進行交換。常見的方式如下：

?分組操作下移。GROUPBY操作可能較大幅度地減少關系元組的個數，如果能夠對某個關系先進行分組操作，然后再進行表之間的連接，很可能提高連接效率。這種優化方式是把分組操作提前執行。下移的含義，是在查詢樹上讓分組操作盡量靠近葉子結點，使得分組操作的結點低于一些選擇操作。

?分組操作上移。如果連接操作能夠過濾掉大部分元組，則先進行連接后進行GROUPBY操作，可能提高分組操作的效率。這種優化方式是把分組操作置后執行。上移的含義和下移正好相反。

對于帶有GROUPBY等操作的非SPJ格式的SQL語句，在本節之前提及的技術都適用，只是結合了GROUPBY操作的語義進行分組操作。因為GROUPBY操作下移或上移均不能保證重寫后的查詢效率一定更好，所以，要在查詢優化器中采用基于代價的方式來估算某幾種路徑的優劣。

另外，GROUPBY、ORDERBY優化的另外一個思路是盡量利用索引，這部分內容將在3.3節詳細討論。

2.ORDERBY優化

對于ORDERBY的優化，可有如下方面的考慮：

?排序消除（Order By Elimination，OBYE）。優化器在生成執行計劃前，將語句中沒有必要的排序操作消除（如利用索引），避免在執行計劃中出現排序操作或由排序導致的操作（如在索引列上排序，可以利用索引消除排序操作）。

?排序下推（Sort push down）。把排序操作盡量下推到基表中，有序的基表進行連接后的結果符合排序的語義，這樣能避免在最終的大的連接結果集上執行排序操作。

3.DISTICT優化

對于DISTICT的優化，可有如下方面的考慮：

?DISTINCT消除（Distinct Elimination）。如果表中存在主鍵、唯一約束、索引等，則可以消除查詢語句中的DISTINCT（這種優化方式，在語義優化中也涉及，本質上是語義優化研究的范疇）。

?DISTINCT推入（Distinct Push Down）。生成含DISTINCT的反半連接查詢執行計劃時，先進行反半連接再進行DISTICT操作，也許先執行DISTICT操作再執行反半連接更優，這是利用連接語義上確保唯一功能特性進行DISTINCT的優化。

?DISTINCT遷移（Distinct Placement）。對連接操作的結果執行DISTINCT，可能把DISTINCT移到一個子查詢中優先進行（有的書籍把這項技術稱為“DISTINCT配置”）。

2.3 啟發式規則在邏輯優化階段的應用

邏輯優化階段使用的啟發式規則通常包括如下兩類。

?一定能帶來優化效果的，主要包括：

○優先做選擇和投影（連接條件在查詢樹上下推）。

○子查詢的消除。

○嵌套連接的消除。

○外連接的消除。

○連接的消除。

○使用等價謂詞重寫對條件化簡。

○語義優化。

○剪掉冗余操作（一些剪枝優化技術）、最小化查詢塊。

?變換未必會帶來性能的提高，需根據代價選擇，主要包括：

○分組的合并。

○借用索引優化分組、排序、DISTINCT等操作。

○對視圖的查詢變為基于表的查詢。

○連接條件的下推。

○分組的下推。

○連接提取公共表達式。

○謂詞的上拉。

○用連接取代集合操作。

○用UNIONALL取代OR操作。

2.4 本章小結

本章從邏輯查詢優化的基礎關系代數講起，首先簡略概述了關系代數的基礎知識，這部分不側重關系代數原理的推導和證明，重點在于描繪關系代數的主要概念，分析關系代數的原理對查詢優化的指導意義，為查詢優化技術做鋪墊；然后以PostgresSQL為示例，全面分析了查詢優化可用的技術，這是本章的重點；最后對查詢優化技術做了一個簡單總結，從整體上提升對查詢優化的理解和認識。