第1章 數(shù)據(jù)管理系統(tǒng)的查詢優(yōu)化

數(shù)據(jù)庫(kù)管理系統(tǒng)（DataBase Management System，DBMS，簡(jiǎn)稱數(shù)據(jù)庫(kù)）是位于用戶與操作系統(tǒng)之間的一層數(shù)據(jù)管理軟件，主要功能包括：數(shù)據(jù)定義、數(shù)據(jù)操縱、數(shù)據(jù)庫(kù)的運(yùn)行管理、數(shù)據(jù)庫(kù)的建立和維護(hù)

數(shù)據(jù)操縱是數(shù)據(jù)庫(kù)管理系統(tǒng)中一種最基本的操作，這種操作包括查詢、插入、刪除和修改等，其中，查詢操作稱為查詢處理。

查詢的執(zhí)行，就是查詢處理的過(guò)程，即數(shù)據(jù)庫(kù)按用戶指定的SQL語(yǔ)句中的語(yǔ)義，執(zhí)行語(yǔ)義所限定的操作。但SQL語(yǔ)句的執(zhí)行效率對(duì)數(shù)據(jù)庫(kù)的效率影響較大。為了提高查詢語(yǔ)句的執(zhí)行效率，對(duì)查詢語(yǔ)句進(jìn)行優(yōu)化是必不可少的。

對(duì)查詢語(yǔ)句進(jìn)行優(yōu)化的技術(shù)就是查詢優(yōu)化技術(shù)，運(yùn)用查詢技術(shù)實(shí)現(xiàn)數(shù)據(jù)操縱功能的過(guò)程是確定給定查詢的高效執(zhí)行計(jì)劃的過(guò)程。所謂執(zhí)行計(jì)劃就是查詢樹(shù)，它由一系列內(nèi)部的操作符組成，這些操作符按一定的運(yùn)算關(guān)系構(gòu)成查詢的一個(gè)執(zhí)行方案。查詢優(yōu)化的追求目標(biāo)，就是在數(shù)據(jù)庫(kù)查詢優(yōu)化引擎生成一個(gè)執(zhí)行策略的過(guò)程中，盡量使查詢的總開(kāi)銷（總開(kāi)銷通常包括IO、CPU、網(wǎng)絡(luò)傳輸?shù)龋┻_(dá)到最小。

數(shù)據(jù)庫(kù)查詢優(yōu)化技術(shù)主要包括查詢重用技術(shù)、查詢重寫(xiě)規(guī)則、查詢算法優(yōu)化技術(shù)、并行查詢優(yōu)化技術(shù)、分布式查詢優(yōu)化技術(shù)及其他方面（如框架結(jié)構(gòu)）的優(yōu)化技術(shù)，這6項(xiàng)技術(shù)構(gòu)成了一個(gè)“廣義的數(shù)據(jù)庫(kù)查詢優(yōu)化”的概念。

本書(shū)重點(diǎn)探討“查詢重寫(xiě)規(guī)則”和“查詢算法優(yōu)化”，這是多數(shù)書(shū)籍在提及“數(shù)據(jù)庫(kù)查詢優(yōu)化”時(shí)所限定的范圍，這兩項(xiàng)技術(shù)在本書(shū)中稱為“狹義的數(shù)據(jù)庫(kù)查詢優(yōu)化”。從優(yōu)化的內(nèi)容角度看，查詢優(yōu)化又分為代數(shù)優(yōu)化和非代數(shù)優(yōu)化，或稱為邏輯優(yōu)化和物理優(yōu)化。邏輯優(yōu)化主要依據(jù)關(guān)系代數(shù)的等價(jià)變換做一些邏輯變換，物理優(yōu)化主要根據(jù)數(shù)據(jù)讀取、表連接方式、表連接順序、排序等技術(shù)對(duì)查詢進(jìn)行優(yōu)化。“查詢重寫(xiě)規(guī)則”屬于邏輯優(yōu)化方式，運(yùn)用了關(guān)系代數(shù)和啟發(fā)式規(guī)則；“查詢算法優(yōu)化”屬于物理優(yōu)化方式，運(yùn)用了基于代價(jià)估算的多表連接算法求解最小花費(fèi)的技術(shù)。

查詢優(yōu)化技術(shù)中“查詢重寫(xiě)規(guī)則”的理論基礎(chǔ)是關(guān)系代數(shù)，但本書(shū)的重點(diǎn)不是討論關(guān)系代數(shù)理論，而是著眼于關(guān)系代數(shù)和查詢優(yōu)化相結(jié)合的部分，指出理論與實(shí)踐的對(duì)應(yīng)關(guān)系，分析理論是如何指導(dǎo)數(shù)據(jù)庫(kù)引擎執(zhí)行查詢優(yōu)化的，進(jìn)而使讀者明白數(shù)據(jù)庫(kù)查詢優(yōu)化器的實(shí)現(xiàn)原理，掌握SQL語(yǔ)句的優(yōu)化方法。這些主要包括以下內(nèi)容：

?查詢優(yōu)化引擎能做什么樣的查詢優(yōu)化操作。這第1章的重點(diǎn)內(nèi)容，將全面指明查詢優(yōu)化技術(shù)的范圍，以期建立查詢優(yōu)化技術(shù)的全局概念。

?查詢優(yōu)化引擎為什么能進(jìn)行查詢優(yōu)化。這是第2章和第3章的重點(diǎn)內(nèi)容，將從理論的角度出發(fā)進(jìn)行介紹。其中第2章介紹邏輯優(yōu)化包括的具體技術(shù)、為什么可做邏輯優(yōu)化，以及怎么做邏輯優(yōu)化；第3章介紹物理優(yōu)化的具體技術(shù)、為什么可做物理優(yōu)化，以及怎么做物理優(yōu)化。

對(duì)于并行查詢優(yōu)化、分布式并行查詢優(yōu)化、其他優(yōu)化等只做簡(jiǎn)單介紹，之所以如此，是為了保持全文的完整性，提醒讀者從概念上要明確“數(shù)據(jù)庫(kù)的查詢優(yōu)化技術(shù)”的范圍。

本章先從數(shù)據(jù)庫(kù)層面的優(yōu)化進(jìn)行概述，這是全局級(jí)別的優(yōu)化，著眼點(diǎn)在整個(gè)數(shù)據(jù)庫(kù)管理系統(tǒng)，借以區(qū)別本書(shū)重點(diǎn)——查詢優(yōu)化技術(shù)。接著，詳細(xì)介紹查詢優(yōu)化技術(shù)，這是局部的、SQL語(yǔ)句級(jí)別的優(yōu)化，也是本書(shū)著重探討的內(nèi)容。

1.1 數(shù)據(jù)庫(kù)調(diào)優(yōu)

數(shù)據(jù)庫(kù)調(diào)優(yōu)可以使數(shù)據(jù)庫(kù)應(yīng)用運(yùn)行得更快，其目標(biāo)是使數(shù)據(jù)庫(kù)有更高的吞吐量和更短的響應(yīng)時(shí)間。被調(diào)優(yōu)的對(duì)象是整個(gè)數(shù)據(jù)庫(kù)管理系統(tǒng)總體。

在數(shù)據(jù)庫(kù)層面進(jìn)行調(diào)優(yōu)，有很多的資源、數(shù)據(jù)庫(kù)配置參數(shù)需要考慮。數(shù)據(jù)庫(kù)調(diào)優(yōu)的方式通常有如下幾種：

?人工調(diào)優(yōu)。主要依賴于人，效率低下；要求操作者完全理解常識(shí)所依賴的原理，還需要對(duì)應(yīng)用、數(shù)據(jù)庫(kù)管理系統(tǒng)、操作系統(tǒng)以及硬件有廣泛而深刻的理解。

?基于案例的調(diào)優(yōu)。總結(jié)典型應(yīng)用案例情況中數(shù)據(jù)庫(kù)參數(shù)的推薦配置值、數(shù)據(jù)邏輯層設(shè)計(jì)等情況，從而為用戶的調(diào)優(yōu)工作提供一定的參考和借鑒。但這種方式忽略了系統(tǒng)的動(dòng)態(tài)性和不同系統(tǒng)間存在的差異。

?自調(diào)優(yōu)。為數(shù)據(jù)庫(kù)系統(tǒng)建立一個(gè)模型，根據(jù)“影響數(shù)據(jù)庫(kù)系統(tǒng)性能效率的因素”，數(shù)據(jù)庫(kù)系統(tǒng)自動(dòng)進(jìn)行參數(shù)的配置。一些商業(yè)數(shù)據(jù)庫(kù)實(shí)現(xiàn)了部分自調(diào)優(yōu)技術(shù)，典型的如Oracle提供了如下一些技術(shù)或工具。

○Redo Logfile Sizing Advisor：為避免因頻繁出現(xiàn)的檢查點(diǎn)而導(dǎo)致過(guò)多的磁盤IO，系統(tǒng)可推薦重做日志文件的最佳大小。

○Automatic Checkpoint Tuning：為取得良好的恢復(fù)速度，同時(shí)降低對(duì)正常吞吐量的影響，系統(tǒng)可以自動(dòng)優(yōu)檢查點(diǎn)。

○Automatic Shared Memory Tuning：為高效地利用可用內(nèi)存并提高性能，系統(tǒng)可自動(dòng)地配置與System Global Area（SGA）內(nèi)存相關(guān)的參數(shù)（如緩沖區(qū)緩存、共享池等）。

○Transaction Rollback and Recovery Monitoring：為掌握事務(wù)狀況，系統(tǒng)可估計(jì)回滾一個(gè)事務(wù)要花多少時(shí)間，監(jiān)視被恢復(fù)的事務(wù)的進(jìn)度，并估計(jì)事務(wù)恢復(fù)的平均速度。

○SQL Tuning Advisor：為提高SQL語(yǔ)句的執(zhí)行效率，系統(tǒng)可自動(dòng)調(diào)優(yōu)高成本的SQL語(yǔ)句，給出建立索引的建議、SQL重寫(xiě)的建議等。

○SQL Analyzer：對(duì)SQL語(yǔ)句的不同查詢執(zhí)行計(jì)劃進(jìn)行性能分析和比較。

○SQL Access Advisor：對(duì)物理設(shè)計(jì)給出改進(jìn)建議。

○SQL Plan Management：使SQL語(yǔ)句能夠根據(jù)環(huán)境的變化選擇穩(wěn)定、高效的查詢執(zhí)行計(jì)劃。

○Segment Advisor：根據(jù)對(duì)象內(nèi)的空間碎片化程度，給出是否應(yīng)該對(duì)對(duì)象執(zhí)行新的在線收縮操作的建議；提供關(guān)于段的歷史增長(zhǎng)趨勢(shì)的報(bào)告，為容量規(guī)劃提供有效的信息。

Undo Advisor：幫助管理員在flashback和非flashback特性中調(diào)整撤銷表空間大小時(shí)做出正確的判斷；為管理員恰當(dāng)?shù)卦O(shè)置UNDO_RETENTION提供建議，避免快照過(guò)于陳舊。

通常，數(shù)據(jù)庫(kù)調(diào)優(yōu)主要分為5階段，如表1-1所示。涉及的技術(shù)主要有以下幾種：

?應(yīng)用情況的估算。應(yīng)用的使用方式（把業(yè)務(wù)邏輯轉(zhuǎn)換為數(shù)據(jù)庫(kù)的讀寫(xiě)分布邏輯，以讀多寫(xiě)少或讀寫(xiě)均衡等來(lái)區(qū)分OLAP和OLTP；應(yīng)用對(duì)數(shù)據(jù)庫(kù)的并發(fā)情況、并發(fā)是否可以池化等）、數(shù)據(jù)量、對(duì)數(shù)據(jù)庫(kù)的壓力、峰值壓力等做一個(gè)預(yù)估。

?系統(tǒng)選型策略。確定什么樣的數(shù)據(jù)庫(kù)可以適用應(yīng)用需求，并確定使用開(kāi)源的數(shù)據(jù)庫(kù)還是商業(yè)的數(shù)據(jù)庫(kù)，使用集群還是單機(jī)的系統(tǒng)，同時(shí)對(duì)操作系統(tǒng)、中間件、硬件、網(wǎng)絡(luò)等進(jìn)行選型。

?數(shù)據(jù)模型的設(shè)計(jì)。主要根據(jù)業(yè)務(wù)邏輯，從幾個(gè)角度考慮表的邏輯結(jié)構(gòu)，內(nèi)容如下。

○E-R模型設(shè)計(jì)：遵循E-R模型設(shè)計(jì)原理。偶爾的、適當(dāng)程度的非規(guī)范化可以改善系統(tǒng)查詢性能。

○數(shù)據(jù)邏輯分布策略：目的是減少數(shù)據(jù)請(qǐng)求中不必要的數(shù)據(jù)量，只返回用戶需要的數(shù)據(jù)。可用的技術(shù)如分區(qū)、用E-R模型分表等（如互聯(lián)網(wǎng)企業(yè)典型的用法，根據(jù)業(yè)務(wù)的不同，進(jìn)行分庫(kù)、分表等操作）。

○數(shù)據(jù)物理存儲(chǔ)策略：目的是減少IO操作，如啟用壓縮技術(shù)、把索引和表數(shù)據(jù)的存儲(chǔ)分開(kāi)，不同的表數(shù)據(jù)分布在不同的表空間上，不同的表空間分布在不同的物理存儲(chǔ)上（尤其是讀寫(xiě)量大的表空間分布在不同的物理存儲(chǔ)上），日志、索引和數(shù)據(jù)分布在不同的物理存儲(chǔ)上等。

○索引：在查詢頻繁的對(duì)象上建立恰當(dāng)?shù)乃饕顾饕恼?yīng)大于負(fù)效應(yīng)（索引的維護(hù)存在消耗）。

?SQL設(shè)計(jì)。編寫(xiě)正確的、查詢效率高的SQL語(yǔ)句，依據(jù)的主要是“查詢重寫(xiě)規(guī)則”。編寫(xiě)語(yǔ)句的過(guò)程中要注意，要有意識(shí)地保障SQL能利用到索引。

?數(shù)據(jù)庫(kù)功能的啟用。數(shù)據(jù)庫(kù)為提高性能提供了一些功能，可合理使用，具體如下。

○查詢重用：根據(jù)實(shí)際情況進(jìn)行配置，可緩存查詢執(zhí)行計(jì)劃、查詢結(jié)果等。

○數(shù)據(jù)庫(kù)參數(shù)的設(shè)置：可設(shè)置合適的參數(shù)，如數(shù)據(jù)緩沖區(qū)等。

?模型系統(tǒng)預(yù)運(yùn)行。在備用系統(tǒng)上模擬實(shí)際運(yùn)行環(huán)境，加大壓力進(jìn)行系統(tǒng)測(cè)試，提前發(fā)現(xiàn)問(wèn)題。

?系統(tǒng)監(jiān)控與分析。在工業(yè)環(huán)境下，加強(qiáng)對(duì)系統(tǒng)的運(yùn)行監(jiān)控和日常的分析工作，具體如下。

○應(yīng)用系統(tǒng)表現(xiàn)：收集用戶對(duì)應(yīng)用系統(tǒng)的使用意見(jiàn)、系統(tǒng)存在問(wèn)題等，因?yàn)檫@些可能是用戶在第一時(shí)間發(fā)現(xiàn)的。

○OS環(huán)境監(jiān)控：實(shí)時(shí)監(jiān)控CPU、內(nèi)存、IO等，并對(duì)比實(shí)時(shí)情況與歷史正常情況。

○數(shù)據(jù)庫(kù)內(nèi)部狀況監(jiān)控：一些數(shù)據(jù)庫(kù)提供系統(tǒng)表、視圖、工具等手段，向用戶提供數(shù)據(jù)庫(kù)運(yùn)行過(guò)程中內(nèi)部狀況的信息，如鎖的情況，這些都需要實(shí)時(shí)監(jiān)控，并對(duì)比實(shí)時(shí)情況與歷史正常情況。

○日志分析：在數(shù)據(jù)庫(kù)的日志、操作系統(tǒng)的日志中找出異常事件，定位問(wèn)題。

表1-1 數(shù)據(jù)庫(kù)調(diào)優(yōu)5個(gè)階段

1.2 查詢優(yōu)化技術(shù)

查詢優(yōu)化技術(shù)是SQL層面的優(yōu)化，屬于局部?jī)?yōu)化，有別于“數(shù)據(jù)庫(kù)調(diào)優(yōu)”式的全局優(yōu)化。上面我們說(shuō)過(guò)，查詢優(yōu)化技術(shù)主要包括查詢重用技術(shù)、查詢重寫(xiě)規(guī)則技術(shù)、查詢算法優(yōu)化技術(shù)、并行查詢的優(yōu)化技術(shù)、分布式查詢優(yōu)化技術(shù)、其他優(yōu)化技術(shù)6個(gè)方面的技術(shù)。下面我們就從這6個(gè)方面介紹查詢優(yōu)化技術(shù)。

1.2.1 查詢重用

查詢重用是指盡可能利用先前的執(zhí)行結(jié)果，以達(dá)到節(jié)約查詢計(jì)算全過(guò)程的時(shí)間并減少資源消耗的目的。

目前查詢重用技術(shù)主要集中在兩個(gè)方面：

?查詢結(jié)果的重用。在緩存區(qū)中分配一塊緩沖塊，存放該SQL語(yǔ)句文本和最后的結(jié)果集，當(dāng)遇到同樣的SQL輸入時(shí)，可直接把結(jié)果返回。查詢結(jié)果的重用技術(shù)節(jié)約了查詢計(jì)劃生成時(shí)間和查詢執(zhí)行過(guò)程的時(shí)間，減少了查詢執(zhí)行全過(guò)程的資源消耗。

?查詢計(jì)劃的重用。緩存一條查詢語(yǔ)句的執(zhí)行計(jì)劃及其相應(yīng)語(yǔ)法樹(shù)結(jié)構(gòu)。查詢計(jì)劃的重用技術(shù)減少了查詢計(jì)劃生成的時(shí)間和資源消耗。

查詢重用技術(shù)有利有弊：弊端，如結(jié)果集很大會(huì)消耗很大的內(nèi)存資源，同樣的SQL不同用戶獲取的結(jié)果集可能不完全相同；益處，節(jié)約了CPU和IO消耗。在使用的過(guò)程中，趨利避害，應(yīng)根據(jù)實(shí)際情況選用。

1.2.2 查詢重寫(xiě)規(guī)則

查詢重寫(xiě)是查詢語(yǔ)句的一種等價(jià)轉(zhuǎn)換，即對(duì)于任何相關(guān)模式的任意狀態(tài)都會(huì)產(chǎn)生相同的結(jié)果（相同的關(guān)系替代兩個(gè)表達(dá)式中相應(yīng)的關(guān)系，所得到的結(jié)果是相同的）。查詢重寫(xiě)有兩個(gè)目標(biāo)：

?將查詢轉(zhuǎn)換為等價(jià)的、效率更高的形式，例如將效率低的謂詞轉(zhuǎn)換為效率高的謂詞、消除重復(fù)條件等。

?盡量將查詢重寫(xiě)為等價(jià)、簡(jiǎn)單且不受表順序限制的形式，為物理查詢優(yōu)化階段提供更多的選擇，如視圖的重寫(xiě)、子查詢的合并轉(zhuǎn)換等。

查詢重寫(xiě)的依據(jù)，是關(guān)系代數(shù)。關(guān)系代數(shù)的等價(jià)變換規(guī)則對(duì)查詢重寫(xiě)提供了理論上的支持。查詢重寫(xiě)后，查詢優(yōu)化器可能生成多個(gè)連接路徑，可以從候選者中擇優(yōu)。

對(duì)查詢優(yōu)化技術(shù)進(jìn)行分類，可有以下4個(gè)角度：

?語(yǔ)法級(jí)。查詢語(yǔ)言層的優(yōu)化，基于語(yǔ)法進(jìn)行優(yōu)化。

?代數(shù)級(jí)。查詢使用形式邏輯進(jìn)行優(yōu)化，運(yùn)用關(guān)系代數(shù)的原理進(jìn)行優(yōu)化。

?語(yǔ)義級(jí)。根據(jù)完整性約束，對(duì)查詢語(yǔ)句進(jìn)行語(yǔ)義理解，推知一些可優(yōu)化的操作。

?物理級(jí)。物理優(yōu)化技術(shù)，基于代價(jià)估算模型，比較得出各種執(zhí)行方式中代價(jià)最小的。

查詢重寫(xiě)是基于語(yǔ)法級(jí)、代數(shù)級(jí)、語(yǔ)義級(jí)的優(yōu)化，可以統(tǒng)一歸屬到邏輯優(yōu)化的范疇：基于代價(jià)估算模型是物理層面的優(yōu)化，是從連接路徑中選擇代價(jià)最小的路徑的過(guò)程。

查詢重寫(xiě)技術(shù)優(yōu)化思路主要包括：

?將過(guò)程性查詢轉(zhuǎn)換為描述性的查詢，如視圖重寫(xiě)。

?將復(fù)雜的查詢（如嵌套子查詢、外連接、嵌套連接）盡可能轉(zhuǎn)換為多表連接查詢。

?將效率低的謂詞轉(zhuǎn)換為等價(jià)的效率高的謂詞（如等價(jià)謂詞重寫(xiě)）。

?利用等式和不等式的性質(zhì)，簡(jiǎn)化WHERE、HAVING和ON條件。

如何改進(jìn)現(xiàn)有查詢重寫(xiě)規(guī)則的效率，如何發(fā)現(xiàn)更多更有效的重寫(xiě)規(guī)則，是查詢優(yōu)化的研究?jī)?nèi)容之一。常見(jiàn)的查詢重寫(xiě)技術(shù)類型，每一類都有自己的規(guī)則，這些規(guī)則沒(méi)有確定的、統(tǒng)一的規(guī)律，但重寫(xiě)的核心一定是“等價(jià)轉(zhuǎn)換”，只有等價(jià)才能轉(zhuǎn)換，這是需要特別強(qiáng)調(diào)的。

1.2.3 查詢算法優(yōu)化

查詢優(yōu)化即求解給定查詢語(yǔ)句的高效執(zhí)行計(jì)劃（有的書(shū)籍稱為執(zhí)行方案）的過(guò)程。

查詢計(jì)劃，也稱為查詢樹(shù)，它由一系列內(nèi)部的操作符組成，這些操作符按一定的運(yùn)算關(guān)系構(gòu)成查詢的一個(gè)執(zhí)行方案。簡(jiǎn)單說(shuō)，就是先將表A和表B連接得到中間結(jié)果，然后再和另外的表C連接得到新的中間方式，直至所有表連接完畢（連接操作就是操作符，這個(gè)示例有兩個(gè)連接操作符。A連接B連接C、C連接B連接A就是兩種不同的執(zhí)行方案，是兩個(gè)不同的執(zhí)行計(jì)劃，查詢優(yōu)化要選出最高效的一個(gè)執(zhí)行方案）。

查詢計(jì)劃，從形式上看是一顆二叉樹(shù)，樹(shù)葉是每個(gè)單表對(duì)象，兩個(gè)樹(shù)葉的父結(jié)點(diǎn)是一個(gè)連接操作符（如左外連接操作符，A left-out join B）連接后的中間結(jié)果（另外還有一些其他結(jié)點(diǎn)如排序操作等也可以作為中間結(jié)果），這個(gè)結(jié)果是一個(gè)臨時(shí)“關(guān)系”，這樣直至根結(jié)點(diǎn)。

所以從一個(gè)查詢計(jì)劃看，涉及的主要“關(guān)系結(jié)點(diǎn)”包括：

?單表結(jié)點(diǎn)。考慮單表的數(shù)據(jù)獲取方式，是直接通過(guò)IO獲得數(shù)據(jù)，還是通過(guò)索引獲取數(shù)據(jù)，或者是通過(guò)索引定位數(shù)據(jù)的位置后再經(jīng)過(guò)IO到數(shù)據(jù)塊中獲取數(shù)據(jù)。這是一個(gè)從物理存儲(chǔ)到內(nèi)存解析成邏輯字段的過(guò)程，即符合馮·諾依曼體系結(jié)構(gòu)的要求（外存數(shù)據(jù)讀入內(nèi)存才能被處理）。

?兩表結(jié)點(diǎn)。考慮兩表以何種方式連接、代價(jià)有多大、連接路徑有哪些等。表示的是內(nèi)存中的元組怎么進(jìn)行元組間的連接。此時(shí)，元組通常已經(jīng)存在于內(nèi)存中，直接使用即可。這是一個(gè)完成用戶語(yǔ)義的邏輯操作，但是只是局部操作，只涉及兩個(gè)具體的關(guān)系。完成用戶全部語(yǔ)義（用戶連接的語(yǔ)義），需要配合多表的連接順序的操作。不同的連接算法導(dǎo)致的連接效率不同，如數(shù)據(jù)多時(shí)可使用Hash連接，外表數(shù)據(jù)量小且內(nèi)表數(shù)據(jù)量大時(shí)可使用嵌套連接，數(shù)據(jù)如果有序可使用歸并連接或先排序后使用歸并連接等。

?多表中間結(jié)點(diǎn)。考慮多表連接順序如何構(gòu)成代價(jià)最少的“執(zhí)行計(jì)劃”。決定是AB先連接還是BC先連接，這是一個(gè)比較花費(fèi)大小的運(yùn)算。如果判斷的連接方式太多，也會(huì)導(dǎo)致效率問(wèn)題。多個(gè)關(guān)系采用不同次序進(jìn)行連接，花費(fèi)的CPU資源、內(nèi)存資源差異可能較大。許多數(shù)據(jù)庫(kù)采用左深樹(shù)、右深樹(shù)、緊密樹(shù)3種方式或其中一部分對(duì)多表進(jìn)行連接，得到多種連接路徑。

查詢優(yōu)化目的就是生成最好的查詢計(jì)劃。生成最好的查詢計(jì)劃的策略通常有兩個(gè)：

?基于規(guī)則優(yōu)化。根據(jù)經(jīng)驗(yàn)或一些已經(jīng)探知或被證明有效的方式，定義為“規(guī)則”（如根據(jù)關(guān)系代數(shù)得知的規(guī)則、根據(jù)經(jīng)驗(yàn)得知的規(guī)則等），用這些規(guī)則化簡(jiǎn)查詢計(jì)劃生成過(guò)程中符合可被化簡(jiǎn)的操作，使用啟發(fā)式規(guī)則排除一些明顯不好的存取路徑，這就是基于規(guī)則的優(yōu)化。

?基于代價(jià)優(yōu)化。根據(jù)一個(gè)代價(jià)評(píng)估模型，在生成查詢計(jì)劃的過(guò)程中，計(jì)算每條存取路徑（存取路徑主要包括上述3個(gè)“關(guān)系結(jié)點(diǎn)”）的花費(fèi)，然后選擇代價(jià)最小的作為子路徑，這樣直至所有表連接完畢得到一個(gè)完整的路徑。主流數(shù)據(jù)庫(kù)都采用了基于代價(jià)策略進(jìn)行優(yōu)化的技術(shù)。

基于規(guī)則優(yōu)化具有操作簡(jiǎn)單且能快速確定連接方式的優(yōu)點(diǎn)，但這種方法只是排除了一部分不好的可能，所以得到的結(jié)果未必是最好的；基于代價(jià)優(yōu)化是對(duì)各種可能的情況進(jìn)行量化比較，從而可以得到花費(fèi)最小的情況，但如果組合情況比較多則花費(fèi)的判斷時(shí)間就會(huì)很多；查詢優(yōu)化器的實(shí)現(xiàn)，多是兩種優(yōu)化策略組合使用，如MySQL和PostgreSQL就采取了基于規(guī)則和代價(jià)估算的查詢優(yōu)化策略。

多表連接的優(yōu)化算法中，使用最廣泛的算法有如下幾種：

?SYSTEM-R算法。近乎窮舉的搜索算法（一種空間搜索算法，其變形算法與其本質(zhì)相同）。

?啟發(fā)式搜索算法。基于規(guī)則（基于“啟發(fā)式規(guī)則”拋棄不好的存取路徑挑選好的）。

?貪婪算法。根據(jù)某種優(yōu)化方式，以當(dāng)前情況為基礎(chǔ)做出最優(yōu)選擇，認(rèn)為每次搜索過(guò)的局部存取路徑是最優(yōu)的，然后繼續(xù)探索與其他表的連接路徑。

?動(dòng)態(tài)規(guī)劃算法。將待求解的問(wèn)題分解為若干個(gè)子問(wèn)題（階段），按順序求解子問(wèn)題，前一子問(wèn)題的解，為后一子問(wèn)題的求解提供了有用的信息。在求解任一子問(wèn)題時(shí)，列出各種可能的局部解，通過(guò)決策保留那些可能達(dá)到最優(yōu)的局部解，丟棄其他局部解。依次解決各子問(wèn)題，最后一個(gè)子問(wèn)題就是初始問(wèn)題的解。

?遺傳算法。一種啟發(fā)式的優(yōu)化算法，拋棄了傳統(tǒng)的搜索方式，模擬自然界生物進(jìn)化過(guò)程，基于自然群體遺傳演化機(jī)制，采用人工進(jìn)化的方式對(duì)目標(biāo)空間進(jìn)行隨機(jī)化搜索。

我們知道，查詢的基本操作是選擇、投影和連接。選擇和投影的優(yōu)化規(guī)則適用于SPJ（Select-Project-Join）和非SPJ（SPJ+GROUPBY等操作）；連接包括兩表連接和多表連接，多表連接是其中最難的，因?yàn)槎鄠€(gè)表連接時(shí)可以有多種不同的連接次序，所以查詢的執(zhí)行計(jì)劃的數(shù)目會(huì)隨著該查詢包含的表個(gè)數(shù)呈指數(shù)級(jí)增長(zhǎng)（最大組合次數(shù)是n個(gè)關(guān)系全排列），當(dāng)表個(gè)數(shù)很多時(shí)，將導(dǎo)致搜索空間極度膨脹，僅搜索花費(fèi)最小的查詢計(jì)劃就需要耗費(fèi)巨大的時(shí)間和資源，這是查詢優(yōu)化器實(shí)現(xiàn)時(shí)需要考慮的問(wèn)題。

1.2.4 并行查詢優(yōu)化

傳統(tǒng)單機(jī)數(shù)據(jù)庫(kù)系統(tǒng)中，給定一個(gè)查詢（Query），查詢優(yōu)化算法只需找到查詢的一個(gè)具有最小執(zhí)行花費(fèi)的執(zhí)行計(jì)劃，這樣的計(jì)劃必定具有最快的響應(yīng)時(shí)間。

在并行數(shù)據(jù)庫(kù)系統(tǒng)中，查詢優(yōu)化的目標(biāo)是尋找具有最小響應(yīng)時(shí)間的查詢執(zhí)行計(jì)劃，這需要把查詢工作分解為一些可以并行運(yùn)行的子工作。一些商業(yè)數(shù)據(jù)庫(kù)提供了并行查詢的功能，用以優(yōu)化查詢執(zhí)行操作。

一個(gè)查詢能否并行執(zhí)行，取決于以下因素：

?系統(tǒng)中的可用資源（如內(nèi)存、高速緩存中的數(shù)據(jù)量等）。

?CPU的數(shù)目。

?運(yùn)算中的特定代數(shù)運(yùn)算符。如A、B、C、D4個(gè)表進(jìn)行連接，每個(gè)表的單表掃描可以并行進(jìn)行；在生成4個(gè)表連接的查詢計(jì)劃過(guò)程中，可選擇A和B連接的同時(shí)C和D進(jìn)行連接，這樣連接操作能并行運(yùn)行。不同商業(yè)數(shù)據(jù)庫(kù)，對(duì)查詢并行的實(shí)現(xiàn)也不盡相同。在同一個(gè)SQL內(nèi)，查詢并行可以分為以下兩種：

○操作內(nèi)并行。將同一操作如單表掃描操作、兩表連接操作、排序操作等分解成多個(gè)獨(dú)立的子操作，由不同的CPU同時(shí)執(zhí)行。

○操作間并行。一條SQL查詢語(yǔ)句可以分解成多個(gè)子操作，由多個(gè)CPU執(zhí)行。

1.2.5 分布式查詢優(yōu)化

在分布式數(shù)據(jù)庫(kù)系統(tǒng)中，查詢策略優(yōu)化（主要是數(shù)據(jù)傳輸策略，A、B兩結(jié)點(diǎn)的數(shù)據(jù)進(jìn)行連接，是A結(jié)點(diǎn)數(shù)據(jù)傳輸?shù)紹結(jié)點(diǎn)或從B到A或先各自進(jìn)行過(guò)濾然后再傳輸?shù)龋┖途植刻幚韮?yōu)化（傳統(tǒng)的單結(jié)點(diǎn)數(shù)據(jù)庫(kù)的查詢優(yōu)化技術(shù)）是查詢優(yōu)化的重點(diǎn)。

在查詢優(yōu)化策略中，數(shù)據(jù)的通信開(kāi)銷是優(yōu)化算法考慮的主要因素。分布式查詢優(yōu)化以減少傳輸?shù)拇螖?shù)和數(shù)據(jù)量作為查詢優(yōu)化的目標(biāo)。所以，分布式數(shù)據(jù)庫(kù)系統(tǒng)中的代價(jià)估算模型，除了考慮CPU代價(jià)和IO代價(jià)外，還要考慮通過(guò)網(wǎng)絡(luò)在結(jié)點(diǎn)間傳輸數(shù)據(jù)的代價(jià)。這是分布式并行查詢優(yōu)化技術(shù)與傳統(tǒng)單結(jié)點(diǎn)數(shù)據(jù)庫(kù)系統(tǒng)最大的不同之處。

在分布式數(shù)據(jù)庫(kù)系統(tǒng)中，代價(jià)估算模型如下：

總代價(jià)=IO代價(jià)+CPU代價(jià)+通信代價(jià)

1.2.6 其他優(yōu)化

數(shù)據(jù)庫(kù)的查詢性能，還取決于其他一些因素，如數(shù)據(jù)庫(kù)集群系統(tǒng)中的SD（Share Disk）集群和SN（Share Nothing）集群，不同的架構(gòu)查詢優(yōu)化技術(shù)也不同。SD集群采用的是共享存儲(chǔ)方式，在數(shù)據(jù)的讀寫(xiě)時(shí)可能產(chǎn)生讀寫(xiě)沖突，所以單表掃描會(huì)受到影響；SN集群采用的是非共享式存儲(chǔ)方式，所以在考慮了通信代價(jià)后單結(jié)點(diǎn)的優(yōu)化方式依然適用。這些都不作為本書(shū)的重點(diǎn)，所以就不過(guò)多介紹了。

1.3 本章小結(jié)

本章辨析了數(shù)據(jù)庫(kù)調(diào)優(yōu)和查詢優(yōu)化技術(shù)的區(qū)別，從整體上介紹了查詢優(yōu)化涉及的主要技術(shù)，但本章內(nèi)容不涉及原理的證明，只是從利于工程實(shí)踐的角度出發(fā)，力圖構(gòu)建查詢優(yōu)化技術(shù)的整體概念，描繪查詢優(yōu)化技術(shù)的范圍，從而幫助讀者全面了解查詢優(yōu)化的技術(shù)。