基于成本的數據庫查詢優化淺析

摘要：主要介紹基于成本的數據庫查詢優化的一些基本概念，針對多表連接的三種方法：嵌套循環鏈接、歸并連接和混合連接進行分析和闡述，并成本估算，列出估算公式。

關鍵詞：數據庫系統；成本；存取路徑；連接順序；連接方法；NLJ；MJ；Hybrid Join

中圖分類號：TP311文獻標識碼：A文章編號：1009-3044(2008)34-1540-02

On Cost Based Database Query Optimization

CUI Yu-li， YIN Chang-qing

(School of Software Engineering， Tongji University， Shanghai 201804， China)

Abstract: Mainly presents some basic concept of database query optimization， and analyze the three multi-table join methods: nested loop join， merge join and hybrid join，give the cost of each join methods.

Key words: DBMS; cost; access path; join sequence; join methods; NLJ; MJ;Hybrid Join

1 引言

目前，數據庫系統是管理信息系統的核心。從大多數管理信息系統的數據庫操作來看，查詢操作在各種數據庫操作中所占據的比重最大，因而提高查詢的效率，優化數據庫查詢便成了提高數據庫管理系統乃至管理信息系統的關鍵所在。舉例來說，如果數據量累積到一定程度，比如一個銀行的賬戶數據庫表信息累積到上百萬甚至上千萬條記錄，全表掃描一次往往需要數十分鐘，甚至數小時。如果采用比全表掃描更好的查詢策略，往往可以使查詢時間大大縮短，由此可見查詢優化技術的重要性。

數據庫查詢優化器是RDBMS的一個重要組成部分。對于基于成本的優化，數據庫查詢優化器的任務是，通過產生可供選擇的執行計劃，找到最低估算成本的執行計劃，來優化一條SQL語句。它在SQL語句性能表現上扮演了至關重要的角色。本文就基于多表連接的三種方法簡單估算一下成本開銷，來說明基于成本的數據庫查詢優化。

2 成本含義

成本表示優化器對執行語句所用時間的最優估計。當一條SQL語句被輸入RDBMS服務器，它將會被解析并提交給數據庫查詢優化器。查詢優化器將會對其進行查詢重寫和表達式評估，以產生可供選擇的執行計劃。對于每個待選的執行計劃，數據庫優化器根據相應的統計量進行估計每個執行計劃的成本，成本估計最小的執行計劃將被選取用來執行SQL語句。在實際的數據庫產品(如Oracle、Sybase、DB2等)的高版本中都是采用基于代價的優化方法，這種優化能根據從系統字典表所得到的信息來估計不同的執行計劃的成本，然后選擇一個較優的執行計劃。

成本主要由CPU Cost 和I/O Cost兩部分組成，具體圖示如圖1。

其中：Base cost 是CPU初始化花費的時間，是確定的。

Page cost 是緩沖池中定位請求頁所花費時間。

Scan cost 是掃描每條記錄的時間。

Row cost 是復制記錄到線程私有存儲空間所花費的時間。

I/O cost 是從硬盤中讀取所需頁面所花費的時間。

3 存取路徑

那么什么是存取路徑呢？當將 SQL 語句提交給 DBMS 執行時，DBMS 會“實時”地為動態 SQL 語句設計出存取路徑。對分析者而言，在執行每條 SQL 語句之前，無法檢查 DBMS 為這些語句所選擇的存取路徑。

當DBMS優化器為每條 SQL 語句創建優化的存取路徑時，可以挑選各種不同的技術。查詢優化器將主要執行兩個步驟來最終決定選擇哪個存取路徑：1) 列舉出可能的存取路徑；2) 對列舉出的存取路徑成本評估，選擇出最快的一個存取路徑。影響存取路徑的因素主要有以下幾個方面：連接順序， 連接方法， 存取方法等，本文就具體針對表連接做個簡單的分析。

4 連接的理解

多張數據表查詢時就要用到連接操作，連接表的順序及連接的算法將極大地影響這數據庫查詢的速度和效率。數據庫優化器提供了一系列技術來用于連接表數據。當在 FROM 子句中引用多個數據庫表（或指定了 JOIN 子句）時，SQL 會請求DBMS執行連接操作。

那么DBMS優化器是如何做這件事？每個多表查詢會分解成數個單獨的存取路徑。為完成此連接操作， DBMS優化器首先選擇一個連接順序，DBMS優化器先根據它認為是最優的連接方式來進行選擇其中的兩張表并創建一條經過優化的存取路徑，然后，優化器繼續連接其它表，直到優化完整條查詢。其次，在連接表時，優化器將必須確定要使用的最佳連接算法。連接算法（或連接方法）定義了組合表的基本過程。每種連接方法的運行方式各不相同，但可得出相同的結果。然而，連接方法的選用會極大地影響到連接性能。

每種連接方法通常都涉及一些特定的基本步驟。通常，首先確定先處理哪個表。稱這個表為外表。做出決定之后，對該外表執行一系列的操作，為連接做準備。然后，將該表中的各行與第二個表（稱之為內表）進行組合。另外，還要對內表執行的一系列操作，這可以在連接發生之前進行，也可以連接發生時進行，或者在這兩者時進行。優化器知道每種方法的優缺點，知道采用哪種方法會怎樣影響到性能。根據系統目錄中的當前統計，優化器還知道哪些表最適合做內表，哪些表最適合做外表。以下是查詢優化器所要考慮的一些基本規律：

1) 表越小，越有可能被選為外表。這有助于減少必須再次訪問內表的次數。

2) 如果選擇謂詞可以應用到某個表，則該表更適合于被選作外表

3) 如果可能對其中某個表做索引查找，則該表很適合于作為內表。

4) 在連接操作中，重復元素最少的表傾向于被選作外表。

當然，這些不是固定不變的規則。最后，優化器將根據詳細的代價估計來選擇外表和內表。

4.1 連接順序

通常，查詢的連接順序很大程度上決定了查詢的執行性能，因為越早地過濾行，效率越高。表與表之間的連接順序滿足交換律（t1■t2 = t2■t1）和結合律（（t1■t2）■t3 =t1■（t2■t3）），假設有n個表，那么這n個表的連接順序數目就是n！，可想而知，隨著n的增大，連接順序的個數將迅速增加，以致無法全部枚舉所有連接順序，一般只考慮左深樹連接循序。左深樹連接順序的簡明特點就是每一個連接的右孩子節點都是一個單獨的表，而不是由其他表連接后的結果。

4.2 連接方法

通常可以采用三類連接方法：嵌套循環連接（nested loop join）、歸并連接（merge join）和混合連接（hybrid join）。每種連接方法的運行方式各不相同。DBMS優化器會基于一組統計，選擇連接方法，以求可以達到最佳性能。

1) 嵌套循環連接（nested loop join，NLJ）。要執行 NLJ，首先要確定一個驅動表(outer table)，另一個表為inner table，先在外表中確定符合條件的行，然后掃描內表來搜索匹配。驅動表中的每一行與inner表中的相應的記錄JOIN，在完成對內表的掃描之后，再在外表中確定另一符合條件的行。然后，再掃描內表以查找匹配，如此反復，類似一個嵌套的循環。該連接方法適用于驅動表的記錄集比較小（<10000）而且inner表需要有有效的訪問方法（Index）。需要注意的是：JOIN的順序很重要，驅動表的記錄集一定要小，返回結果集的響應時間是最快的。通常，用索引來重復掃描內表以將 I/O 代價降到最低。圖示如圖2。

cost= I/O cost + CPU cost

= I/O cost + (inner access cost * outer cardinality)

2)歸并連接（merge join，MJ），又叫排序歸并連接（sort merge join，SMJ）。用 MJ 時，需要按照連接謂詞對要連接的表進行排序。這意味著必須按照指定連接標準的列的順序訪問每個表。這個順序可以用排序或索引式訪問來實現。在確保對外表和內表正確排序之后，按照順序讀取每個表，然后匹配連接列。在歸并掃描連接中，每個表只掃描一遍。圖示如圖3。

cost = I/O cost + cpu cost

= I/O cost + (inner access cost + outer access cost + qualified row * sort record size + workfile access cost)

3) 混合連接（hybrid join）。

■

混合連接主要有以下幾個步驟：

1) 采用有效的單表存取方法存取外表。（下轉第1544頁）

（上接第1541頁）

2) 將外表的數據與內表索引的rid連接，拼成rid list。

3) 如果內表的索引沒有很好的聚集，對中間表和rid list進行排序。

4) 根據rid list 預取內表。

5) 將內表與外表匹配的記錄與外表記錄連接。

Cost = I/O cost + cpu cost

= I/O cost + (optional sort cost + semi_join cost + workfile access cost)

5 結論

數據庫性能直接影響整個應用系統的性能。在數據庫管理和開發過程中，優化設計可以提高數據庫的性能，特別是大型數據庫，優化過程更為重要，不僅可以提高查詢相應速度，還可以減少對內存的需求。oracle、db2等數據庫系統都十分注重數據庫查詢優化技術，另外，基于成本估算的數據庫查詢優化技術已被大多數數據庫系統所采用。對數據庫查詢優化的概念有所了解之后，又著重分析了連接的三種方法，對其成本進行了估算，以利于寫出較優的查詢語句，提高數據庫查詢效率。

參考文獻：

[1] Dennis S，Bonnet P.數據庫性能調優：原理與技術[M].北京:電子工業出版社，2004.

[2] Silberschatz A，Korth H F，Sudarshan S.Database Systems Concepts[M].北京:機械工業出版社，2006.

[3] 薩師煊，王珊.數據庫系統概論[M].北京:高等教育出版社，2002.

[4] ibm技術網站.數據庫性能調優專題[EB/OL].http://www.ibm.com/developerworks/cn/db2/zones/performance/.