文章目錄

• 8 查詢優化
• • 8.1 概述
  • 8.2 查詢數和語法樹
  • 8.3 代數優化
  • 8.4 物理優化
  • 8.5 連接操作優化
  • • 8.5.1 嵌套循環法
    • 8.5.2 利用B+樹索引或哈希索引尋找匹配元組法
    • 8.5.3 散列連接法
  • 8.6 后話

8 查詢優化

8.1 概述

我們不管是在數據庫軟件如MySQL、SQLServer等，還是通過應用程序連接數據庫如JDBC、ODBC等。本質上我們如果要查詢數據庫中的數據，都是使用SQL去查詢。而這個查詢的過程說大不大說小不小，如果數據庫中一個表內含有許多數據，一個數據庫含有很多個表，那么你的SQL寫法將大大影響到你查數據的效率。

查詢優化并不是由用戶決定的，而是由DBMS決定的。當用戶寫了一條SQL語句后，查詢系統會對SQL語句做一個重寫，然后變成一個執行效率更高的形式。

換而言之，如果你在數據庫中寫入了select e.ENAME,d.DNAME from emp e (inner) join dept d on e.DEPTNO = d.DEPTNO;這樣的查詢語句，實際上傳入數據庫時，DBMS會自動幫你改寫為效率更高的SQL語句。

查詢優化一般從四個方面入手：

• 把查詢語句進行變換，改變基本操作的次序，然后查詢起來更加有效，這個叫做代數優化。
• 根據系統所提供的存取路徑，選擇合理的存取策略，也就是對存取的方法進行優化，我們叫做物理優化。
• 有限查詢優化根據啟發式規則和選擇執行的策略去先做選擇，投影等一元操作，然后做連接操作，這叫規則優化，代數優化和物理優化屬于規則優化。
• 在很多的優化策略里面，選取代價最小的優化執行策略，叫做代價估算優化。

需要注意的是，雖然DBMS會幫你重寫查詢語句，但是如果重寫的過程比原SQL查詢的過程還久，那顯然不合適。

8.2 查詢數和語法樹

數據庫查詢語言的處理過程和一般高級程序設計語言相仿。都是經歷了解釋和編譯的過程。

讓我們看回這個圖。應用調用接口傳入命令語句，詞法和語法分析器會去解釋命令語句，在這里他就會用到一個語法樹，將命令語句轉變為SQL語句，然后授權檢查是否有權限；當有權限后，就會執行sql語句，這里就涉及到查詢優化的問題了，其會利用查詢樹來優化該SQL語句。

8.3 代數優化

代數優化是對查詢進行等效變換，以減少執行的開銷。最常用的變化原則是，盡量縮短查詢過程中的中間結果。由于選擇、投影等一元操作分別從水平方向或垂直方向減少關系的大小，而連接、并等二元操作本身的開銷較大，而且很可能產生大的中間結果。因此在變換查詢時，我們讓選擇和投影先做，再做二元操作。在連接時，也是先做小關系之間的連接，再做大關系的連接。在有些DBMS中還會找出查詢中相同的部分，統一處理，以避免重復運算，還有些DBMS把嵌套查詢變為非嵌套查詢。

簡單來說，假如現在有兩張10000個元組的表，想做查詢和連接兩個操作，根據笛卡爾乘積現象，簡單來說，假如現在有兩張10000個元組的表，根據笛卡爾乘積現象，當兩張表進行連接查詢的時候，沒有任何條件進行限制，最終的查詢結果條數是兩張表記錄條數的乘積。也就是要做10000乘以10000次乘積，這無疑是很大的，那如果我們根據選擇操作先篩選掉一部分，然后在做連接操作，那么執行效率就會大大提高。

8.4 物理優化

代數優化只是在各種操作中變換次序達到提高效率的目的，雖然這樣很方便，但是優化效果有限。但是如果通過合理選擇存取路徑，往往能夠收到顯著的優化效果。

在7.1我們談到過，對于關系小的，查詢量大的，我們可以用最原始的方法——順序掃描，按照關系存放的自然順序讀取各元組，然后按選擇條件檢驗，選取那些滿足條件的元組。但是這種方法對于關系大的顯然不適用。在目前，用得最多的存儲方式就是利用B+樹或其變種為結構的各種索引來提高查詢的效率。

8.5 連接操作優化

在高級數據庫工程師考試中，常見的就是考查連接操作優化。其優化方式有以下幾種：

• 嵌套循環法

• 利用索引或散列尋找匹配元組法

• 排序歸并法

• 散列連接法

8.5.1 嵌套循環法

大體來說他像我們編程語言里面的循環嵌套一樣。假如現在有兩個關系（表）：R和S，如下圖所示：

如果說我們要進行連接操作，本質上連接操作就是加了條件的笛卡爾乘積。那么我們是利用嵌套循環法就是先用R中的一條元組去匹配另外S表中的所有元組（S表中的所有元組相當于內層循環），然后R中的第二條元組再去匹配S中的所有元組，以此類推，直到R的所有元組和S的所有元組比較完為止。

在整個連接過程中，R只要掃描一次，S就要掃描n次（也就是S表中所有的元組），從程序設計的觀點來看，R的掃描相當于程序的外循環，而S相當于程序的內循環，因此我們把R叫做外關系，S叫做內關系。當然，兩張表的地位可以互換，這取決于兩者掃描的IO代價。

在前面的章節中，我們曾經談論過磁盤。如果說R中表中一條匹配S表中一條元組就要I/O一次，那么這顯然是效率極低的。但是實際上，在操作系統中硬盤是一種塊設備，他是以物理塊為單位，也就是說，假如一個物理塊是1040M，R中一條元組為100M，那么一個物理塊就可以容納R中十條元組去匹配S表。

我們可以設置兩個緩沖區，分為外循環和內循環。

外循環的緩沖區可以存放外循環的物理塊，內循環的緩沖區可以存放內循環的物理塊，當兩張表做連接，我們采用循環嵌套法的時候，我們不再是一條一條元組匹配，而是如上所說一個物理塊匹配內循環的一個物理塊，如果當你內存足夠大，你可以設置足夠大的緩沖區，存放更多的物理塊，如果這張表不大，甚至能做到一波全部匹配完，大大減少了匹配效率。

8.5.2 利用B+樹索引或哈希索引尋找匹配元組法

我們在兩個表中還是那樣：

R表作為外循環，S表作為內循環，然后給R表一個緩沖區，S表帶有B+樹索引。

之后R表一個物理塊讀進來，他要找S表中匹配的元組，就可以通過B+樹索引找到物理塊中符合連接條件的元組的地址，直接進行匹配，大大節省了尋找匹配元組的效率，不需要像嵌套循環法那樣去掃描。

但是這個需要考慮代價：假如在某個屬性上面，重復值的數量達到了總元組數的百分之二十以上的話，用索引反而不合算。什么意思呢？如果有過多的重復值，也就意味著你要在建樹的時候有許多重復值，這就會導致在辨別重復值的時候花費過多的代價，這樣還不如使用循環嵌套法來的方便。

8.5.3 散列連接法

具體來說就是：他把R表和S表中以后做連接有可能產生的結果全部哈希到一個柜子里，柜子有多個抽屜，不同的抽屜代表不同的結果，以后只要需要兩張表的連接，只需要在哈希出來的這個柜子（表）里面去找就行了。

但是考慮到代價，也就是說你這個R表和S表不會頻繁的去更新，否則的話會打亂哈希出來的表，定期做維護代價也會很大。

8.6 后話

實際上，查詢優化博大精深，但是對于初學者來說，這一講并不是其需要學習的重點，而對于數據庫老手，我更建議去看數據庫原書或者是東南大學王能斌老師的書。這里還有很多的知識我就不再細講了，有興趣的同學可以去自行探究。

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的数据库杂谈（八）——查询优化的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。