查詢優(yōu)化概述

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

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

查詢優(yōu)化的兩種主要方法

查詢優(yōu)化主要有兩種方法：

1. 靜態(tài)規(guī)則/啟發(fā)式規(guī)則 (Static Rules / Heuristics)

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

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

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

靜態(tài)規(guī)則與查詢重寫

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

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

以下是一些常見的靜態(tài)規(guī)則優(yōu)化：

謂詞下推 (Predicate Pushdown)

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

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

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

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

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

投影下推 (Projection Pushdown)

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

這樣可以 最小化從一個操作符傳遞到下一個操作符的數(shù)據(jù)量 ，這在行式存儲系統(tǒng)（避免復(fù)制寬行中不必要的列）和分布式數(shù)據(jù)庫（減少網(wǎng)絡(luò)傳輸?shù)臄?shù)據(jù)量）中尤為重要。

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

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

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

這種優(yōu)化在以下場景中尤為重要：

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

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

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

簡化復(fù)雜的謂詞表達式。例如，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。

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

復(fù)雜查詢與基于成本的搜索

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

成本模型 (Cost Model)

數(shù)據(jù)庫系統(tǒng)內(nèi)部維護一個 成本模型 ，用于 估算每個潛在執(zhí)行計劃可能產(chǎn)生的成本 。

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

成本估算通?；诙喾N因素，包括 磁盤I/O次數(shù) 、 DRAM（內(nèi)存）占用量 ，以及在分布式數(shù)據(jù)庫中， 網(wǎng)絡(luò)消息的數(shù)量 （因為網(wǎng)絡(luò)I/O慢且低效）。

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

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

統(tǒng)計信息 (Statistics Information)

為了能夠準確估算查詢計劃的成本，DBMS需要 維護關(guān)于表結(jié)構(gòu)的內(nèi)部統(tǒng)計信息 。

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

統(tǒng)計信息的維護 可以通過以下方式進行：

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

準確的統(tǒng)計信息對于優(yōu)化器做出明智的成本估算至關(guān)重要 。它們幫助優(yōu)化器更好地理解數(shù)據(jù)的分布和選擇性，從而更準確地預(yù)測不同操作的開銷。