資料庫查詢優化：嵌套查詢Table of Contents

<a target="_blank">1. 嵌套查詢的分類和優化概述</a>

<a target="_blank">2. kim: on optimizing an sql-like nested query</a>

<a target="_blank">2.1. 嵌套查詢的分類</a>

<a target="_blank">2.1.1. a 類</a>

<a target="_blank">2.1.2. n 類</a>

<a target="_blank">2.1.3. j 類</a>

<a target="_blank">2.1.4. ja 類</a>

<a target="_blank">2.1.5. d 類</a>

<a target="_blank">2.2. 嵌套查詢的優化</a>

<a target="_blank">3. kiessling, sql-like and quel-like correlation queries with aggregates revisited</a>

<a target="_blank">4. ganski, wong: optimization of nested sql queries revisited</a>

<a target="_blank">4.1. count</a>

<a target="_blank">4.2. 非等值條件</a>

<a target="_blank">4.3. 重複值</a>

<a target="_blank">5. 總結</a>

嵌套查詢是 sql 中表達能力很強的一種機制，既給應用帶來了友善也給查詢優化帶來了很大的挑戰。本文總結一下經典的單機系統對嵌套查詢的優化。

kim 定義了嵌套查詢的 5 種基本形式并給出了轉換算法。最後組合成一個通用算法來處理任意複雜的嵌套查詢（一般稱為嵌套查詢的非嵌套化）。在一個 sql 語句中通路多個表的典型機制為： 連接配接謂詞（join）、嵌套謂詞、除法謂詞。非嵌套化就是把其他兩種形式的查詢轉換為 join。嵌套謂詞會形成 4 種形式的嵌套查詢，而除法謂詞會形成另 1 種形式的嵌套查詢，是以總共是 5 種。考慮到除法幾乎沒有系統實作它，後續可以略過。

首先，定義嵌套的層數。如果查詢中隻有一個查詢塊（select、from、where），顯然不存在嵌套查詢，此時嵌套的層數為0。如果查詢中有兩個查詢塊，外查詢的叫做外部塊，内查詢的叫做内部塊，此時嵌套層數為1。查詢塊嵌套的層次數顯然可以更多，而且一個 where 條件中可以有多個嵌套的子查詢。查詢塊的 from 子句後面可以出現多個表。where 條件以及子查詢的結果列也可以出現多個，例如：(sno, sname) = (select sno, sname from supply)。kim 劃分嵌套查詢種類是從子查詢有沒有連接配接條件以及聚集函數這兩個角度考慮的。

内查詢塊沒有對外查詢塊的表的引用（非相關子查詢），并且查詢結果是聚集函數（不帶 group by，結果集是單行）。

内查詢塊沒有對外查詢塊的表的引用（非相關子查詢），并且查詢結果沒有聚集函數（結果集是很可能是多行）。

内查詢塊有對外查詢塊的表的引用（相關子查詢），并且查詢結果沒有聚集函數。

内查詢塊有對外查詢塊的表的引用（相關子查詢），并且查詢結果集有聚集函數。

連接配接謂詞與除法謂詞一起形成的查詢中，帶有兩個内查詢塊。任何一個的連接配接謂詞引用了外查詢塊都會形成 d 型嵌套查詢。

如果采用最簡單直接的執行算法，對外查詢塊的每條記錄，需要執行内查詢塊一次。a 類查詢的子查詢可以隻計算一次，是以不再需要做特殊的轉換或優化。n 類沒有這麼直接的優化，有必要做優化。j、ja、d 類存在類似的問題。

n 類的嵌套查詢可以被等價轉換為連接配接。對于子查詢可能會産生的重複值，可通過 semi-join 來消除。op 可以是 in 或标量操作符。（注意，标量運算符要求結果集是單行。）嵌套1層的轉換算法比較直接，命名為 nest-n-j。j 類的嵌套查詢也可以用類似的算法來轉換。對于 not in 操作符，要采用 anti-join。而且，對于 j 類的查詢，還要確定 anti-join 的計算是發生在 join 條件之後。

ja 類的查詢可以引入一個做聚集運算的臨時表來等價轉換為 j 類查詢，算法命名為 nest-ja。op 是個标量操作（是以不需要考慮重複值），查詢最終被轉換為 join。多層嵌套的 ja 類查詢也可以被轉換為 j 類查詢。

略。

解決了 kim 算法 nest-ja 中的缺陷，并擴充到 sql 中常見的子句，包括 exists、not exists、any、all 等。

select pnum from parts where qoh = (select count(shipdate) from supply where supply.pnum = parts.pnum and shipdate &lt; '1-1-80')

算法引入的臨時表在處理聚集函數時會丢失掉記錄，進而導緻最終結果少了。臨時表丢失記錄的問題可以通過外連接配接解決。如果内查詢中用的是 count(*)，還需要在轉換時改成 count(col)，以避免因為外連接配接引入的 null 導緻的計數增加。

類似的，非等值條件也存在丢失資訊的問題，也可以通過連接配接來解決（如果是 count，則要用外連接配接）。

如果連接配接的列上有重複值，連接配接操作會放大結果集的記錄數。不過它們隻可能影響 count、avg、sum，而不會影響 max、min。在産生臨時表之前還要加一步，投影去掉連接配接列上的重複值。

容易發現，嵌套查詢的非嵌套化未必是最優的，kim 等的論文中都有代價分析。逐漸改進（打更新檔）的做法也逐漸增加了轉換後查詢的處理代價，需要代價優化器來判斷轉換是否有必要。

footnotes:

kim, on optimizing an sql-like nested query.

r.a. ganski etc., optimization of nested sql queries revisited.

<a target="_blank" href="https://blogs.oracle.com/optimizer/entry/optimizer_transformations_subquery_unesting_part_1">https://blogs.oracle.com/optimizer/entry/optimizer_transformations_subquery_unesting_part_1</a>

<a target="_blank" href="https://blogs.oracle.com/optimizer/entry/optimizer_transformations_subquery_unesting_part_2">https://blogs.oracle.com/optimizer/entry/optimizer_transformations_subquery_unesting_part_2</a>