查詢優化的必要性：為何要估算成本？

數據庫系統中的查詢優化是一個復雜而關鍵的環節。當用戶提交一個查詢時，數據庫管理系統（DBMS）并非直接執行它，而是會生成大量可能的執行方案，即查詢計劃。每一種查詢計劃都對應著不同的執行路徑和資源消耗。例如，對于一個涉及多表連接的查詢，表連接的順序、使用的連接算法（如哈希連接、排序合并連接、嵌套循環連接）以及訪問數據的方式（如全表掃描、索引掃描）都會影響查詢的效率。

由于直接運行每一個可能的查詢計劃來評估其成本是極其昂貴且耗時的 （尤其當可能方案達到成千上萬個時）， DBMS 必須有一種方法來近似估算每個查詢計劃的執行成本 。這個估算模型允許優化器在實際執行之前評估計劃的“質量”或所需的工作量，并從中選擇成本最低的那個，以確保查詢以最高效的方式運行。

估算信息來源：數據庫內部統計信息

為了準確估算查詢計劃的成本，DBMS 依賴于其內部的 統計信息目錄 (internal catalog) 。這些統計信息詳細描述了數據庫中表、屬性和索引的特性。

核心的統計信息包括：

• 每張表的元組數量 (NR) ：表示表中包含的記錄總數。
• 每個屬性的唯一值數量 (V(A,R)) ：表示特定列中不同值的數量。

基于這些基本信息，可以派生出 選擇基數 (Selection Cardinality, SC(A,R)) ，它代表了給定屬性中具有相同值的記錄的平均數量，計算方式是 NR / V(A,R)。

統計信息的更新頻率因系統而異。通常，它們可以通過手動命令（如 Postgres/SQLite 的 ANALYZE，Oracle/MySQL 的 ANALYZE TABLE，SQL Server 的 UPDATE STATISTICS，DB2 的 RUNSTATS）進行刷新。一些系統也支持通過后臺任務（如 cron jobs）、在查詢執行時順便更新，或通過觸發器（如表數據變化達到一定百分比時）來自動更新。需要注意的是， 收集這些統計信息本身是昂貴的 ，因為它通常涉及對整個表的順序掃描。

核心概念：選擇率 (Selectivity)

選擇率 (Selectivity) 是優化器估算成本的關鍵指標，它定義為 滿足給定謂詞的元組在總元組中所占的比例 。本質上，選擇率可以被視為一個元組滿足某個條件的概率。

根據謂詞類型，選擇率的計算方式不同：

• 等值謂詞 (Equality Predicate) ：sel(A=constant) = SC(P) / NR。例如，age=2 的選擇率在均勻分布假設下可能是 1/5。
• 范圍謂詞 (Range Predicate) ：sel(A>=a) = (Amax – a) / (Amax – Amin)。例如，age>=2 的選擇率可能被估算為 (4-2)/(4-0) = 1/2。
• 否定謂詞 (Negation Predicate) ：sel(not P) = 1 – sel(P)。
• 合取謂詞 (Conjunction, AND) ：sel(P1 ? P2) = sel(P1) ? sel(P2)。
• 析取謂詞 (Disjunction, OR) ：sel(P1 ? P2) = sel(P1) + sel(P2) – sel(P1) ? sel(P2)。

優化器的估算假設與挑戰

為了簡化數學模型，查詢優化器通常會做出一些關鍵假設，但這些假設在現實世界中往往不成立，從而導致估算誤差。

假設1：數據均勻分布 (Uniform Data)

• 含義 ：假設一個屬性的所有唯一值出現的頻率都是相同的。
• 問題 ：實際數據往往是 傾斜的 (skewed) 。例如，在有10000名學生和10個學院的大學中，如果數據均勻分布，每個學院將有1000名學生。但實際上，計算機科學學院的學生數量可能遠多于美術學院。這種不準確的假設會導致對結果集大小的低估或高估。

假設2：謂詞獨立 (Independent Predicates)

• 含義 ：假設查詢中不同謂詞（如 WHERE 子句中的多個條件）之間沒有關聯，它們的滿足概率可以簡單相乘或相加。
• 問題 ：在現實中，謂詞之間往往存在 關聯性 (correlated) 。例如，查詢汽車數據庫中 make="Honda" AND model="Accord" 的車輛。如果假設獨立性，計算結果是 1/10 * 1/100 = 0.001 (假設有10個品牌和100個型號)。但我們知道只有本田生產 Accord 車型，因此實際上，只要知道 model="Accord"，make 就必然是 Honda，正確選擇率應是 1/100 = 0.01。這種情況下，優化器會 低估 查詢將要處理的數據量，導致對中間數據結構（如哈希連接的哈希表、排序的緩沖區）的大小估算錯誤，進而影響查詢的實際運行時性能。

假設3：包含原則 (Inclusion Principle)

• 含義 ：在連接操作中，假設內部表中的每一個連接鍵值都能在外部表中找到匹配的鍵值。
• 問題 ：實際中可能存在 懸空引用 (dangling references) ，即內部表中的值在外部表中沒有對應的記錄。

這些假設使得優化器的數學模型更易于處理，但同時也引入了誤差。研究表明，許多數據庫系統在估算操作符的選擇率時普遍存在低估的問題。

數據庫如何彌補估算誤差？

為了應對數據分布不均勻和謂詞關聯性等問題，現代數據庫系統采用更復雜的技術來維護和利用統計信息：

直方圖 (Histograms)

最簡單的直方圖會為每個唯一值存儲其出現次數，但這在唯一值數量巨大時會占用過多存儲空間。

• 重度打擊器 (Heavy Hitters) ：對于出現頻率特別高的值（即傾斜數據中的“熱點”），數據庫會單獨存儲它們的精確計數，而對于其余數據則可能繼續使用均勻分布的假設。
• 等寬直方圖 (Equi-width Histograms) ：將數據值范圍分成等寬的桶，每個桶存儲其內值的總計數。這節省了空間，但如果桶內數據分布仍不均勻，估算精度會下降。
• 等深直方圖/分位數直方圖 (Equi-depth/Quantile Histograms) ：通過調整桶的寬度，使每個桶包含大致相同數量的元組（即每個桶的“深度”或總計數大致相同）。這種方法通常能提供更準確的估算，因為它能更好地捕捉數據分布的特征。
• 更新機制 ：直方圖通常是定期 重新計算 的，而不是在每次插入、更新或刪除時實時維護的，因為實時維護的成本太高，會影響事務性能。

采樣 (Sampling)

一些現代 DBMS 會從表中隨機選擇并維護一個較小的 數據樣本 (sample) 。

當需要估算謂詞的選擇率時，優化器將謂詞應用到這個樣本上，然后根據樣本中符合條件的元組比例來推斷整個表的選擇率。

• 優點 ：樣本可以比直方圖更準確地反映實際數據分布，尤其在處理復雜謂詞時。
• 挑戰 ：如何生成一個對所有查詢都具有代表性的樣本是一個難題。同時，對樣本進行掃描以計算選擇率可能比簡單查詢直方圖要慢，因此通常只在預計查詢本身會運行很長時間時才值得使用。
• 高級系統 ：像 SQL Server 這樣的高端商業數據庫通常會 結合使用直方圖和采樣 來獲得最佳的估算精度。

數據庫如何找到最優計劃？

查詢優化器在進行完基于規則的查詢重寫（例如消除冗余操作、推拉謂詞等）之后，會進入 基于成本的搜索 (Cost-based Search) 階段，以將邏輯查詢計劃轉換為物理查詢計劃。

單表查詢優化

對于只涉及單個表的查詢，優化器主要關注選擇最佳的 訪問方法 (access method) ，例如是進行全表掃描（最慢但總是正確）、使用聚簇索引的二分查找，還是使用一個或多個索引進行索引掃描。

此外，它還會考慮謂詞的評估順序，優先評估選擇率更高的謂詞，以便更快地過濾掉不符合條件的元組。

對于在線事務處理 (OLTP) 查詢，由于它們通常只訪問少量數據并主要進行單表查找，優化通常相對簡單，主要依賴于 啟發式規則 (heuristics) 和識別 可索引查詢 (sargable queries) 來選擇最佳索引。

多表連接優化

當涉及多表連接時，查詢計劃的替代方案數量會急劇增長。對于 N 個表的連接，可能的連接順序和算法組合可以達到 4^N 甚至更多。

動態規劃 (Dynamic Programming) ：為了應對這種爆炸式的搜索空間，IBM System R 在1970年代引入了動態規劃技術。這種方法將問題分解為更小的子問題，先解決這些子問題并存儲其最優解，然后逐步組合這些最優解以找到整個查詢的最優計劃。在每一步中，它只保留當前已知成本最低的路徑，從而剪枝大量不必要的搜索。

左深連接樹 (Left-deep Join Trees) ：System R 做出一個關鍵的簡化假設——只考慮 左深連接樹 。這意味著連接操作總是從左側開始，前一個連接的結果作為下一個連接的左輸入。

• 優點 ：這種結構有利于實現 流水線操作 (pipelining) ，即前一個操作符的結果可以立即作為下一個操作符的輸入，而無需將中間結果寫入磁盤上的臨時文件。這在內存受限的早期系統上尤為重要，因為它最大限度地減少了磁盤 I/O。
• 現代系統 ：雖然左深連接樹在歷史上很重要，但現代 DBMS 不再局限于此，它們通常會探索所有類型的連接樹，包括左深、右深和 灌木式 (bushy) 連接樹 。

混合優化策略（以 Postgres 為例）

Postgres 采用了一種混合策略：

• 對于 少于12個表 的查詢，它使用傳統的 動態規劃方法 。
• 對于 12個或更多表 的復雜查詢，它會切換到 遺傳查詢優化器 (Genetic Query Optimizer, GEQO) 。

遺傳算法 是一種隨機搜索算法，它模擬生物進化過程：

• 初始種群 ：首先生成一組隨機的查詢計劃（第一代）。
• 評估與選擇 ：對每個計劃計算成本，選擇其中成本最低的計劃作為當前“最優”方案，并淘汰掉成本最高的計劃。
• 交叉與變異 ：保留下來的計劃的“基因”（即計劃的組成部分，如連接順序、算法等）進行隨機“混合”和“變異”，生成下一代新的查詢計劃。
• 迭代 ：這個過程不斷重復，直到達到預設的時間限制或連續多代沒有發現更好的計劃為止。
• 適用場景 ：遺傳算法能夠處理更大的搜索空間，這對于數據倉庫中常見的 星型/雪花型 (snowflake schema) 查詢尤其有用，因為這些查詢通常涉及大量維度表和事實表之間的連接。

嵌套子查詢 (Nested Sub-queries) 的優化

WHERE 子句中的嵌套子查詢最初被視為一個函數，對外部查詢的每一行進行評估，效率極低。為了優化這類查詢，優化器通常采用兩種主要方法。

重寫/去相關/扁平化 (Rewrite/De-correlate/Flatten)

將相關的子查詢（即子查詢引用了外部查詢中的列）重寫為連接操作。

一旦重寫為連接，優化器就可以利用其成熟的連接優化技術（如動態規劃）來找到最優的執行計劃。

SELECT name FROM sailors WHERE EXISTS (SELECT * FROM reserves WHERE S.sid = R.sid AND R.day = '2018-10-15') 可以被重寫為 SELECT S.name FROM sailors AS S, reserves AS R WHERE S.sid = R.sid AND R.day = '2018-10-15'。

分解 (Decomposition)

將嵌套的子查詢（尤其是不相關的子查詢）作為一個獨立的查詢塊先執行，將其結果存儲在一個臨時表或變量中，然后將這個結果作為參數或數據源傳遞給外部查詢。

避免了對每一行外部查詢都重復執行子查詢的低效率問題。

在一個復雜查詢中，如果有一個子查詢是計算所有水手的最高等級 (SELECT MAX(S2.rating) FROM sailors S2)，優化器可以先單獨執行這個子查詢，得到最高等級的值，然后將這個值插入到外部查詢中 S.rating = [最高等級的值]，從而避免重復計算。

總結

查詢優化是一個 極其困難但又至關重要 的問題。盡管其中的數學模型和算法非常復雜，但現代數據庫系統能夠以驚人的速度完成這些優化，這使得用戶幾乎感知不到其中的開銷。通過結合統計信息、多樣的估算技術、復雜的搜索算法和智能的查詢重寫，DBMS 不斷努力為每條查詢找到最高效的執行路徑。

（額外信息：課程中還提到了一個名為 https://dbdb.io/ 的額外加分項目，鼓勵學生編寫關于不同數據庫管理系統的百科文章，以加深對數據庫架構和實現方式的理解）