查詢優化概述

查詢優化在數據庫管理系統（DBMS）中至關重要 。SQL是一種聲明性語言，這意味著用戶告訴DBMS他們想要什么結果，而不是如何獲取結果。然而，執行同一個查詢可以有多種不同的方式（例如，不同的連接算法），而這些執行計劃的性能差異可能非常大。例如，一個表操作可能在1.3小時和0.45秒之間產生巨大差異。因此，DBMS需要一種方法來選擇給定查詢的“最佳”執行計劃，這就是DBMS優化器的職責。

查詢優化非常困難，這被認為是構建DBMS最困難的部分。成功的查詢優化能力可以顯著區分高端數據庫系統（如Oracle、DB2、Teradata、SQL Server）與開源或免費系統（如Postgres，盡管Postgres也很好，但其查詢優化器不如SQL Server復雜）。IBM在20世紀70年代首次實現了查詢優化器，即System R項目。當時，人們認為DBMS無法選擇比人類手寫更好的查詢計劃。然而，System R證明了數據庫系統可以通過優化器生成與人類編寫的計劃一樣好甚至更好的計劃。System R的許多概念和設計決策至今仍在使用。

查詢優化的兩種主要方法

查詢優化主要有兩種方法：

1. 靜態規則/啟發式規則 (Static Rules / Heuristics)

• 通過重寫查詢來消除低效或不必要的元素。
• 這些技術 不需要檢查實際數據 ，但可能需要查閱系統目錄（即元數據）。

2. 基于成本的搜索 (Cost-based Search)

• 使用成本模型估算執行計劃的成本。
• 評估查詢的多個等效計劃，并選擇成本最低的那個。

靜態規則與查詢重寫

靜態規則的核心思想是 關系代數等價性 。如果兩個關系代數表達式或查詢計劃產生相同的元組集合，則它們是等效的。重要的是，這里強調的是“集合”，意味著 不要求結果的順序相同 。這種等價性允許DBMS在不改變最終結果的前提下，通過轉換或重排操作符來找到更高效的執行計劃。這種高級技術通常被稱為 查詢重寫 (Query Rewriting) 。

在查詢優化架構中，SQL查詢首先經過一個可選的 SQL重寫器 ，然后由 解析器 轉換為抽象語法樹。 綁定器 將語法樹中的命名對象（如表、列名）轉換為內部標識符，并查閱系統目錄，生成 邏輯計劃 。邏輯計劃以高層方式描述查詢要做什么（如掃描表、連接表），但不指定具體如何執行。隨后，邏輯計劃可以進入 樹重寫器 ，在這里應用靜態規則進行重寫。

以下是一些常見的靜態規則優化：

謂詞下推 (Predicate Pushdown)

什么是謂詞？如何理解？ 謂詞是指SQL查詢中用于過濾數據的條件，通常出現在WHERE子句中。例如，e.grade = 'A'就是一個謂詞。

如何理解下推？ 假設SQL查詢被分析并表示為一棵操作樹，謂詞下推就是將過濾操作從樹的較高層（例如，在連接之后）移動到較低層（例如，在連接之前）。

舉例子：把 WHERE 推到 JOIN 之前。 例如，對于一個連接了student和enrolled表的查詢，并且有一個WHERE e.grade = 'A'的條件。最初可能先執行連接，再應用過濾。通過謂詞下推，優化器會先在enrolled表上應用grade = 'A'的過濾，從而在執行連接之前就大大減少參與連接的元組數量。這樣做的目的是 盡早減少數據量 ，從而減少后續操作的工作量。

此外，還可以 重排謂詞的順序 ，優先應用選擇性更高的謂詞（即能過濾掉更多數據的謂詞），以更快地減少處理的數據量。

需要注意的是，并非所有謂詞都適合下推，例如，如果謂詞涉及計算成本較高的用戶定義函數（UDF），數據庫可能會選擇不將其下推。

投影下推 (Projection Pushdown)

在查詢早期階段執行投影操作，只保留查詢所需或連接所需的屬性。

這樣可以 最小化從一個操作符傳遞到下一個操作符的數據量 ，這在行式存儲系統（避免復制寬行中不必要的列）和分布式數據庫（減少網絡傳輸的數據量）中尤為重要。

當DBMS分析SQL查詢并將其轉換為操作樹時，投影下推意味著在查詢執行的早期階段， 只保留查詢所需或后續操作（例如連接操作）所需的屬性（列） 。其他不需要的列會在數據量較小的階段就被“投影掉”，從而避免將它們復制和傳遞到后續的昂貴操作中。

假設有一個SQL查詢，需要從student表和enrolled表中獲取學生姓名（s.name）和課程ID（e.cid），并且兩個表通過s.sid = e.sid進行連接。如果student表有上千個列，但這個查詢只需要其中的sid和name列，enrolled表也只需要sid和cid列，那么：

1. 原始（未優化）計劃 ：可能會先將student表的全部列和enrolled表的全部列進行連接，然后再對連接后的巨大結果集進行投影，只保留name和cid。
2. 應用投影下推后 ：優化器會在這兩個表被連接 之前 ，就對student表執行一個投影操作，只保留sid和name列；對enrolled表執行投影操作，只保留sid和cid列。這樣，在執行連接時，參與連接的元組會更“窄”，大大減少了需要處理的數據量。

這種優化在以下場景中尤為重要：

• 行式存儲系統（Row-Store Systems） ：在行式存儲系統中，如果一個元組非常寬（即有很多列），并且查詢只需要其中的少數幾列，那么過早地將整個寬元組從一個操作符傳遞到下一個操作符會消耗大量內存和I/O。通過投影下推，可以盡早地剔除不必要的列，從而 減少在內存中復制和處理的數據量 。
• 分布式數據庫（Distributed Databases） ：在分布式環境中，數據可能存儲在不同的節點上，并且在執行連接等操作時需要在網絡上傳輸。 網絡I/O是慢且低效的 。如果能在數據傳輸到其他節點之前就進行投影，只發送必要的列，可以顯著 減少網絡傳輸的數據量 和開銷。
• 減少后續操作的開銷 ：當數據量減少后，后續的連接、排序、聚合等操作的處理效率會更高，因為它們需要處理的數據總量更小。

需要注意的是，投影下推對 列式存儲系統（Column-Store Systems） 來說可能不那么重要，因為列式存儲本身就是按列存儲數據，通常在讀取時就只讀取查詢所需的列。

表達式簡化與重寫 (Expression Simplification and Rewriting)

簡化復雜的謂詞表達式。例如，WHERE X = Y AND Y = 3 可以被簡化為 WHERE X = 3 AND Y = 3。

合并謂詞 ：將多個范圍謂詞合并為更緊湊的形式。例如，WHERE val BETWEEN 1 AND 100 OR val BETWEEN 50 AND 150 可以簡化為 WHERE val BETWEEN 1 AND 150。

這些處理屬于 明顯的邏輯優化 ，它們在不查看實際數據內容的情況下，僅憑查詢本身的結構和系統目錄中的元數據（例如，主鍵不能為NULL）即可識別并進行重寫。例如，優化器可以識別并移除不可能的謂詞（如WHERE 1 = 0，總是假）或不必要的謂詞（如WHERE 1 = 1，總是真），或者識別出冗余的自連接。

復雜查詢與基于成本的搜索

對于復雜的查詢，僅僅依靠靜態規則是不夠的。例如， 不同的連接順序 （例如，對于N個表的連接，可能存在4^N種連接順序，這是一個巨大的數字，即卡特蘭數）以及 使用什么連接算法 （如哈希連接與嵌套循環連接的性能差異巨大）等決策， 無法僅通過靜態規則來確定 。此時，就需要 基于成本的搜索 (Cost-based Search) 。

成本模型 (Cost Model)

數據庫系統內部維護一個 成本模型 ，用于 估算每個潛在執行計劃可能產生的成本 。

這個成本是一個 內部的、合成的數字 ，它 只用于在同一DBMS內部比較不同查詢計劃的相對性能 。它與實際的執行時間沒有直接的外部映射關系。

成本估算通常基于多種因素，包括 磁盤I/O次數 、 DRAM（內存）占用量 ，以及在分布式數據庫中， 網絡消息的數量 （因為網絡I/O慢且低效）。

成本模型的核心目的是在 不實際運行查詢計劃 的情況下，近似估算其成本。實際運行查詢是獲得真實成本的唯一方式，但由于可能的計劃數量巨大，這不切實際。

少數系統（如MongoDB）曾采用過簡單的方法，即并行觸發多個查詢計劃，選擇第一個返回結果的計劃，并將其作為后續相同查詢的默認計劃。

統計信息 (Statistics Information)

為了能夠準確估算查詢計劃的成本，DBMS需要 維護關于表結構的內部統計信息 。

這些統計信息通常存儲在 系統目錄 中， 包括表和索引的外觀、元組中的值分布 （如特定列的最小值/最大值、唯一值的數量、直方圖等）。

統計信息的維護 可以通過以下方式進行：

• 自動更新 ：當表數據發生一定比例（如10%）的變化時自動收集。
• 查詢時收集 ：在執行查詢時，DBMS可以查看數據并更新相關統計信息。
• 手動執行 ANALYZE 命令 ：用戶或管理員可以顯式運行ANALYZE函數（在不同系統中有不同的語法，但概念類似），這通常會啟動一次全表掃描，檢查數據并更新內部統計信息。

準確的統計信息對于優化器做出明智的成本估算至關重要 。它們幫助優化器更好地理解數據的分布和選擇性，從而更準確地預測不同操作的開銷。