《數(shù)據庫技術與應用》電子課件,數(shù)據庫技術與應用,數(shù)據庫技術,應用,電子,課件 第10章 查詢處理和優(yōu)化本章學習目標l了解并掌握查詢處理的過程。了解并掌握查詢處理的過程。l了解查詢處理代價的度量方法。了解查詢處理代價的度量方法。l了解查詢優(yōu)化在關系數(shù)據庫系統(tǒng)中的必要性和可行性。了解查詢優(yōu)化在關系數(shù)據庫系統(tǒng)中的必要性和可行性。l掌握查詢優(yōu)化的一般策略。掌握查詢優(yōu)化的一般策略。l理解并掌握代數(shù)優(yōu)化的思想和算法。理解并掌握代數(shù)優(yōu)化的思想和算法。l理解物理優(yōu)化的基本思想和方法。理解物理優(yōu)化的基本思想和方法。本章概述本本章章主主要要討討論論關關系系數(shù)數(shù)據據庫庫的的查查詢詢優(yōu)優(yōu)化化技技術術。查查詢詢處處理理是是關關系系數(shù)數(shù)據據庫庫系系統(tǒng)統(tǒng)最最主主要要的的功功能能。關關系系數(shù)數(shù)據據庫庫的的查查詢詢一一般般都都使使用用SQLSQL語語句句實實現(xiàn)現(xiàn)。對對于于同同一一個個用用SQLSQL表表達達的的查查詢詢要要求求，通通常?？煽梢砸詫獞谟诙喽鄠€個不不同同形形式式但但相相互互“等等價價”的的關關系系代代數(shù)數(shù)表表達達式式。對對于于描描述述同同一一查查詢詢要要求求但但具具有有不不同同形形式式的的關關系系代代數(shù)數(shù)表表達達式式來來說說，由由于于存存取取路路徑徑可可以以不不同同，相相同同的的查查詢詢，其其效效率率就就會會產產生生差差異異，有有時時這這種種差差異異會會相相當當巨巨大大。在在關關系系數(shù)數(shù)據據庫庫中中，查查詢詢優(yōu)優(yōu)化化是是查查詢詢處處理理中中一一項項重重要要和和必必要要的的工工作作，查查詢詢優(yōu)優(yōu)化化通通過過尋尋求求好好的的查查詢詢路路徑徑或或好好的等價代數(shù)表達式來提高查詢效率，通常包括代數(shù)優(yōu)化和物理優(yōu)化技術。的等價代數(shù)表達式來提高查詢效率，通常包括代數(shù)優(yōu)化和物理優(yōu)化技術。主要內容10.1 查詢處理10.3 代數(shù)優(yōu)化10.4 物理優(yōu)化10.2 查詢優(yōu)化10.5實際應用中的查詢優(yōu)化主要內容10.1 查詢處理10.3 代數(shù)優(yōu)化10.4 物理優(yōu)化10.2 查詢優(yōu)化10.5實際應用中的查詢優(yōu)化10.1 查詢處理 10.1.1 查詢處理步驟1.1.查詢分析查詢分析首先，對查詢語句進行掃描、詞法分析和語法分析。從查詢語句中識首先，對查詢語句進行掃描、詞法分析和語法分析。從查詢語句中識別出語言符號，如別出語言符號，如SQLSQL關鍵字，關系名和屬性名等，并進行語法檢查關鍵字，關系名和屬性名等，并進行語法檢查和分析，即判斷查詢語句是否符合和分析，即判斷查詢語句是否符合SQLSQL語法規(guī)則。語法規(guī)則。2.2.查詢檢查查詢檢查查詢檢查首先根據數(shù)據字典對合法的查詢語句進行語義檢查，檢查語查詢檢查首先根據數(shù)據字典對合法的查詢語句進行語義檢查，檢查語句中的數(shù)據庫對象句中的數(shù)據庫對象(如關系名、屬性名如關系名、屬性名)是否存在和是否有效。然后，是否存在和是否有效。然后，根據數(shù)據字典中的用戶權限和完整性約束定義對用戶的存取權限進根據數(shù)據字典中的用戶權限和完整性約束定義對用戶的存取權限進行檢查，如果用戶沒有相應的訪問權限或違反了完整性約束原則，行檢查，如果用戶沒有相應的訪問權限或違反了完整性約束原則，就拒絕執(zhí)行該查詢。檢查通過后，把查詢語句轉換成等價的關系代就拒絕執(zhí)行該查詢。檢查通過后，把查詢語句轉換成等價的關系代數(shù)表達式。數(shù)表達式。RDBMSRDBMS一般都用查詢樹一般都用查詢樹(query tree)(query tree)，也稱為語法分析樹，也稱為語法分析樹(syntax tree)(syntax tree)，來表示擴展的關系代數(shù)表達式。這個過程就是把數(shù)，來表示擴展的關系代數(shù)表達式。這個過程就是把數(shù)據庫對象的外部名稱換為內部表示。據庫對象的外部名稱換為內部表示。10.1 查詢處理 3.3.查詢優(yōu)化查詢優(yōu)化每個查詢都會有很多可供選擇的執(zhí)行策略和操作算法，查詢優(yōu)化是指每個查詢都會有很多可供選擇的執(zhí)行策略和操作算法，查詢優(yōu)化是指選擇一個高效執(zhí)行的查詢處理策略。選擇一個高效執(zhí)行的查詢處理策略。DBMSDBMS會調用系統(tǒng)的優(yōu)化處理器會調用系統(tǒng)的優(yōu)化處理器制定一個執(zhí)行策略，由此產生一個查詢計劃。對關系型數(shù)據庫來說，制定一個執(zhí)行策略，由此產生一個查詢計劃。對關系型數(shù)據庫來說，查詢優(yōu)化過程是由查詢優(yōu)化過程是由RDBMSRDBMS系統(tǒng)自動完成的，它與用戶提交的查詢語句系統(tǒng)自動完成的，它與用戶提交的查詢語句無關。無關。10.1 查詢處理 查詢優(yōu)化有多種方法。按照優(yōu)化的層次一般可分為代數(shù)優(yōu)化和物理優(yōu)化。查詢優(yōu)化有多種方法。按照優(yōu)化的層次一般可分為代數(shù)優(yōu)化和物理優(yōu)化。(1)(1)代數(shù)優(yōu)化：指關系代數(shù)表達式的優(yōu)化，即按照一定的啟發(fā)式規(guī)則，改變代數(shù)優(yōu)化：指關系代數(shù)表達式的優(yōu)化，即按照一定的啟發(fā)式規(guī)則，改變代數(shù)表達式中操作的次序和組合，使查詢執(zhí)行得更高效。例如代數(shù)表達式中操作的次序和組合，使查詢執(zhí)行得更高效。例如“優(yōu)先選擇、優(yōu)先選擇、投影而后連接投影而后連接”等就可完成優(yōu)化。等就可完成優(yōu)化。(2)(2)物理優(yōu)化：物理優(yōu)化：指存取路徑和底層操作算法的選擇。選擇的依據可以是基指存取路徑和底層操作算法的選擇。選擇的依據可以是基于語義的，也可以是基于代價的，還可以是基于規(guī)則的。于語義的，也可以是基于代價的，還可以是基于規(guī)則的。實際優(yōu)化過程都綜合運用了這些優(yōu)化技術，以獲得最好的查詢優(yōu)化效果。實際優(yōu)化過程都綜合運用了這些優(yōu)化技術，以獲得最好的查詢優(yōu)化效果。4.4.查詢執(zhí)行查詢執(zhí)行 依據查詢優(yōu)化器得到的查詢計劃，由代碼生成器生成執(zhí)行這個查詢計劃依據查詢優(yōu)化器得到的查詢計劃，由代碼生成器生成執(zhí)行這個查詢計劃的可執(zhí)行代碼。的可執(zhí)行代碼。10.1 查詢處理 查詢優(yōu)化有多種方法。按照優(yōu)化的層次一般可分為代數(shù)優(yōu)化和物理優(yōu)化。查詢優(yōu)化有多種方法。按照優(yōu)化的層次一般可分為代數(shù)優(yōu)化和物理優(yōu)化。(1)(1)代數(shù)優(yōu)化：指關系代數(shù)表達式的優(yōu)化，即按照一定的啟發(fā)式規(guī)則，改變代數(shù)優(yōu)化：指關系代數(shù)表達式的優(yōu)化，即按照一定的啟發(fā)式規(guī)則，改變代數(shù)表達式中操作的次序和組合，使查詢執(zhí)行得更高效。例如代數(shù)表達式中操作的次序和組合，使查詢執(zhí)行得更高效。例如“優(yōu)先選擇、優(yōu)先選擇、投影而后連接投影而后連接”等就可完成優(yōu)化。等就可完成優(yōu)化。(2)(2)物理優(yōu)化：物理優(yōu)化：指存取路徑和底層操作算法的選擇。選擇的依據可以是基指存取路徑和底層操作算法的選擇。選擇的依據可以是基于語義的，也可以是基于代價的，還可以是基于規(guī)則的。于語義的，也可以是基于代價的，還可以是基于規(guī)則的。實際優(yōu)化過程都綜合運用了這些優(yōu)化技術，以獲得最好的查詢優(yōu)化效果。實際優(yōu)化過程都綜合運用了這些優(yōu)化技術，以獲得最好的查詢優(yōu)化效果。4.4.查詢執(zhí)行查詢執(zhí)行 依據查詢優(yōu)化器得到的查詢計劃，由代碼生成器生成執(zhí)行這個查詢計劃依據查詢優(yōu)化器得到的查詢計劃，由代碼生成器生成執(zhí)行這個查詢計劃的可執(zhí)行代碼。的可執(zhí)行代碼。10.1 查詢處理 目前目前DBMSDBMS通過某種代價模型計算出各種查詢執(zhí)行策略的執(zhí)行代價，然后選取通過某種代價模型計算出各種查詢執(zhí)行策略的執(zhí)行代價，然后選取代價最小的執(zhí)行方案。代價最小的執(zhí)行方案。查詢執(zhí)行代價可以通過查詢對各種資源的使用情況進行度量。在集中式數(shù)據查詢執(zhí)行代價可以通過查詢對各種資源的使用情況進行度量。在集中式數(shù)據庫中，查詢的執(zhí)行開銷主要包括磁盤存取時間庫中，查詢的執(zhí)行開銷主要包括磁盤存取時間(I/O(I/O代價代價)，處理器時間，處理器時間(CPU(CPU代價代價)，查詢的內存時間。在并行，查詢的內存時間。在并行/分布式數(shù)據庫系統(tǒng)中還要加上通信分布式數(shù)據庫系統(tǒng)中還要加上通信代價，即：代價，即：查詢執(zhí)行總代價查詢執(zhí)行總代價=I/O=I/O代價代價+CPU+CPU代價代價+內存代價內存代價+通信代價。通信代價。10.1.2 查詢執(zhí)行代價度量主要內容10.1 查詢處理10.3 代數(shù)優(yōu)化10.4 物理優(yōu)化10.2 查詢優(yōu)化10.5實際應用中的查詢優(yōu)化10.2 查詢優(yōu)化 10.2.1 查詢優(yōu)化的必要性還可以寫出其他等價的關系代數(shù)表達式，但分析這三種就足以說明問題了。還可以寫出其他等價的關系代數(shù)表達式，但分析這三種就足以說明問題了。下面我們計算這下面我們計算這3 3種表達式查詢所需時間，可以發(fā)現(xiàn)由于查詢執(zhí)行策略的種表達式查詢所需時間，可以發(fā)現(xiàn)由于查詢執(zhí)行策略的不同，使得查詢時間有很大的差異。在計算之前做以下統(tǒng)一約定。不同，使得查詢時間有很大的差異。在計算之前做以下統(tǒng)一約定。10.2 查詢優(yōu)化 設設StudentStudent有有10001000個元組，個元組，SCSC有有1000010000個元組，其中選修個元組，其中選修“C003”C003”號課程的元號課程的元組數(shù)為組數(shù)為5050個。個。設一個物理塊能裝設一個物理塊能裝1010個個StudentStudent元組或元組或100100個個SCSC元組。元組。內存有內存有6 6個塊的緩沖區(qū)，其中個塊的緩沖區(qū)，其中5 5塊存放塊存放StudentStudent元組，元組，1 1塊存放塊存放SCSC元組。元組。讀讀/寫磁盤一物理塊的時間為寫磁盤一物理塊的時間為1/20s1/20s，即，即1s1s讀寫讀寫2020個磁盤塊。個磁盤塊。為簡化起見，所有內存操作所花時間可以忽略不計。為簡化起見，所有內存操作所花時間可以忽略不計。10.2 查詢優(yōu)化 10.2.2 查詢優(yōu)化的可行性 關系數(shù)據庫系統(tǒng)查詢語句表示查詢操作基于集合運算，稱之為關系代數(shù)。關系數(shù)據庫系統(tǒng)查詢語句表示查詢操作基于集合運算，稱之為關系代數(shù)。關系代數(shù)具有關系代數(shù)具有5 5種基本運算，這些運算間滿足一定的運算定律，如結合律、種基本運算，這些運算間滿足一定的運算定律，如結合律、交換律、分配律和串接律等，這就表示不同的關系代數(shù)表達式可以得到相交換律、分配律和串接律等，這就表示不同的關系代數(shù)表達式可以得到相同的結果，因此用關系代數(shù)語言進行查詢時可以進行必要的優(yōu)化，以獲取同的結果，因此用關系代數(shù)語言進行查詢時可以進行必要的優(yōu)化，以獲取較優(yōu)的查詢性能。較優(yōu)的查詢性能。由于關系查詢語言的特點，能夠找到有效的算法，使得查詢優(yōu)化過程在由于關系查詢語言的特點，能夠找到有效的算法，使得查詢優(yōu)化過程在DBMSDBMS內部自動完成，向用戶屏蔽優(yōu)化的細節(jié)實現(xiàn)。因此，用戶只需向內部自動完成，向用戶屏蔽優(yōu)化的細節(jié)實現(xiàn)。因此，用戶只需向DBMSDBMS提出提出“做什么做什么”，而不必指出，而不必指出“如何做如何做”，這樣用戶在編程時只需表示出，這樣用戶在編程時只需表示出所想要的結果，無需給出獲得結果的具體步驟，這一切由所想要的結果，無需給出獲得結果的具體步驟，這一切由DBMSDBMS完成。完成。查詢優(yōu)化一般可分為代數(shù)優(yōu)化和物理優(yōu)化。代數(shù)優(yōu)化是指關系代數(shù)表達式查詢優(yōu)化一般可分為代數(shù)優(yōu)化和物理優(yōu)化。代數(shù)優(yōu)化是指關系代數(shù)表達式的優(yōu)化；物理優(yōu)化是指存儲路徑和底層操作算法的優(yōu)化。的優(yōu)化；物理優(yōu)化是指存儲路徑和底層操作算法的優(yōu)化。主要內容10.1 查詢處理10.3 代數(shù)優(yōu)化10.4 物理優(yōu)化10.2 查詢優(yōu)化10.5實際應用中的查詢優(yōu)化10.3 代數(shù)優(yōu)化所謂關系代數(shù)表達式的等價是指用相同的關系代入兩個關系表達式中所得到所謂關系代數(shù)表達式的等價是指用相同的關系代入兩個關系表達式中所得到的結果是相同的。兩個關系表達式的結果是相同的。兩個關系表達式E1E1和和E2E2是等價的，可記作是等價的，可記作E1E2E1E2。常用的代數(shù)表達式的等價變換規(guī)則主要有以下幾類，證明從略。常用的代數(shù)表達式的等價變換規(guī)則主要有以下幾類，證明從略。(1)(1)連接、笛卡爾積的交換律連接、笛卡爾積的交換律設設E1E1和和E2E2是關系代數(shù)表達式，是關系代數(shù)表達式，F(xiàn) F是連接運算的條件，則下列等價公式成立。是連接運算的條件，則下列等價公式成立。10.3.1 關系代數(shù)表達式等價交換規(guī)則10.3 代數(shù)優(yōu)化(2)(2)連接、笛卡爾積的結合律連接、笛卡爾積的結合律設設E1E1、E2E2和和E3E3是關系代數(shù)表達式，是關系代數(shù)表達式，F(xiàn)1F1和和F2F2是連接運算條件，則下列等價公式是連接運算條件，則下列等價公式成立。成立。10.3 代數(shù)優(yōu)化(3)(3)投影的串接定律投影的串接定律設設E E是關系代數(shù)表達式，是關系代數(shù)表達式，Ai(i=1Ai(i=1，2 2，n)n)，Bj(j=1Bj(j=1，2 2，m)m)是是E E中的某中的某些屬性名，且些屬性名，且 構成構成 的子集，則下列等價的子集，則下列等價公式成立。公式成立。(4)(4)選擇的串接定律選擇的串接定律設設E E是關系代數(shù)表達式，、是選擇條件，則下列等價公式成立。是關系代數(shù)表達式，、是選擇條件，則下列等價公式成立。10.3 代數(shù)優(yōu)化10.3 代數(shù)優(yōu)化(7)(7)選擇與并運算的分配律選擇與并運算的分配律設設E1E1和和E2E2是兩個關系代數(shù)表達式，并且是兩個關系代數(shù)表達式，并且E1E1和和E2E2具有相同的屬性名，具有相同的屬性名，F(xiàn) F是選擇是選擇條件，則下列等價公式成立。條件，則下列等價公式成立。(8)(8)選擇與差運算的分配律選擇與差運算的分配律設設E1E1和和E2E2是兩個關系代數(shù)表達式，并且是兩個關系代數(shù)表達式，并且E1E1和和E2E2具有相同的屬性名，具有相同的屬性名，F(xiàn) F是選擇是選擇條件，則下列等價公式成立。條件，則下列等價公式成立。10.3 代數(shù)優(yōu)化10.3 代數(shù)優(yōu)化關系代數(shù)表達式的查詢優(yōu)化是由關系代數(shù)表達式的查詢優(yōu)化是由RBMSRBMS的的DMLDML編譯器自動完成的。因此，查詢編譯器自動完成的。因此，查詢優(yōu)化的基本前提是需要將關系代數(shù)表達式轉換為某種內部表示，常用的內優(yōu)化的基本前提是需要將關系代數(shù)表達式轉換為某種內部表示，常用的內部表示就是所謂的關系代數(shù)語法樹，簡稱為語法樹。其實現(xiàn)的過程是先對部表示就是所謂的關系代數(shù)語法樹，簡稱為語法樹。其實現(xiàn)的過程是先對一個關系代數(shù)表達式進行語法分析，將分析結果用樹的形式表達出來，此一個關系代數(shù)表達式進行語法分析，將分析結果用樹的形式表達出來，此時的樹就稱之為語法樹。語法樹具有如下特征：時的樹就稱之為語法樹。語法樹具有如下特征：(1)(1)樹中的葉節(jié)點表示關系。樹中的葉節(jié)點表示關系。(2)(2)樹中的非葉子結點表示操作。樹中的非葉子結點表示操作。例例10-2 10-2 下面給出下面給出 例例10-110-1中中SQLSQL語句的關系代數(shù)語法樹示例。語句的關系代數(shù)語法樹示例。10.3.2 語法樹10.3 代數(shù)優(yōu)化1.1.選擇運算優(yōu)先原則選擇運算優(yōu)先原則盡可能早地先做選擇運算。在優(yōu)化策略中這是最重要、最基本的一條，因為盡可能早地先做選擇運算。在優(yōu)化策略中這是最重要、最基本的一條，因為選擇運算往往會使關系運算中間結果的記錄數(shù)量大大減少，從而可以成數(shù)選擇運算往往會使關系運算中間結果的記錄數(shù)量大大減少，從而可以成數(shù)量級地減少執(zhí)行時間和存取磁盤次數(shù)。例如：同時執(zhí)行一串選擇運算或一量級地減少執(zhí)行時間和存取磁盤次數(shù)。例如：同時執(zhí)行一串選擇運算或一串連接運算。這樣可避免分開執(zhí)行時，造成多次掃描關系記錄的情況。串連接運算。這樣可避免分開執(zhí)行時，造成多次掃描關系記錄的情況。2.2.投影運算優(yōu)先原則投影運算優(yōu)先原則把投影運算同其前或其后的雙目運算結合起來，以避免對關系的重復掃描。把投影運算同其前或其后的雙目運算結合起來，以避免對關系的重復掃描。如有若干投影和選擇運算，并且它們都對同一個關系操作，則可以在掃描如有若干投影和選擇運算，并且它們都對同一個關系操作，則可以在掃描此關系的同時完成所有的這些運算以避免重復掃描關系。此關系的同時完成所有的這些運算以避免重復掃描關系。10.3.3 關系代數(shù)表達式優(yōu)化算法10.3 代數(shù)優(yōu)化5.5.必要的預處理必要的預處理在執(zhí)行連接在執(zhí)行連接(或乘積后跟選擇或乘積后跟選擇)運算之前，先對關系文件作一些預處理，比如排運算之前，先對關系文件作一些預處理，比如排序和建立索引，這樣會使兩個關系的連接效率高一些。序和建立索引，這樣會使兩個關系的連接效率高一些。下面根據上述的啟發(fā)式優(yōu)化策略以及關系表達式的等價交換規(guī)則，可以得到關下面根據上述的啟發(fā)式優(yōu)化策略以及關系表達式的等價交換規(guī)則，可以得到關系代數(shù)表達式的優(yōu)化算法。系代數(shù)表達式的優(yōu)化算法。算法：關系表達式的優(yōu)化。算法：關系表達式的優(yōu)化。輸入：一個關系表達式的查詢樹。輸入：一個關系表達式的查詢樹。輸出：優(yōu)化的查詢樹。輸出：優(yōu)化的查詢樹。方法：方法：(1)(1)利用選擇運算合取條件分解定律，把形如利用選擇運算合取條件分解定律，把形如 的表達式進行分解，的表達式進行分解，轉換為轉換為 。10.3 代數(shù)優(yōu)化(2)(2)對每一個選擇，利用等價交換規(guī)則盡可能把它移到樹的葉端。對每一個選擇，利用等價交換規(guī)則盡可能把它移到樹的葉端。(3)(3)對每一個投影，利用等價交換規(guī)則盡可能把它移向樹的葉端。其中，利用投對每一個投影，利用等價交換規(guī)則盡可能把它移向樹的葉端。其中，利用投影的串接定律使一些投影消失，而利用選擇與投影的交換律可把一個投影分裂影的串接定律使一些投影消失，而利用選擇與投影的交換律可把一個投影分裂為兩個，其中一個有可能被移向樹的葉端。為兩個，其中一個有可能被移向樹的葉端。(4)(4)利用等價轉換的各個規(guī)則把選擇和投影的串接合并成單個選擇，單個投影或利用等價轉換的各個規(guī)則把選擇和投影的串接合并成單個選擇，單個投影或一個選擇后跟一個投影。使多個選擇或投影能同時執(zhí)行，或在一次掃描中全部一個選擇后跟一個投影。使多個選擇或投影能同時執(zhí)行，或在一次掃描中全部完成，盡管這種交換似乎違背完成，盡管這種交換似乎違背“投影運算優(yōu)先原則投影運算優(yōu)先原則”，但這樣做效率更高。，但這樣做效率更高。(5)(5)把上述得到的語法樹的內節(jié)點分組。每一雙目運算和它所有的直接祖先為一把上述得到的語法樹的內節(jié)點分組。每一雙目運算和它所有的直接祖先為一組組(這些直接祖先是這些直接祖先是(運算運算)；如果其后代直到葉子全是單目運算，則也將它們并；如果其后代直到葉子全是單目運算，則也將它們并進該組。但當雙目運算是笛卡爾積，而且后面不是與它組成等值連接的選擇時，進該組。但當雙目運算是笛卡爾積，而且后面不是與它組成等值連接的選擇時，則不能把選擇與這個雙目運算組成同一組，應當把選擇條件單獨分為一組。則不能把選擇與這個雙目運算組成同一組，應當把選擇條件單獨分為一組。主要內容10.1 查詢處理10.3 代數(shù)優(yōu)化10.4 物理優(yōu)化10.2 查詢優(yōu)化10.5實際應用中的查詢優(yōu)化10.4 物理優(yōu)化1.1.選擇操作的啟發(fā)式規(guī)則選擇操作的啟發(fā)式規(guī)則 (1)(1)對于小關系，使用全表順序掃描方法，即使選擇列上有索引。對于小關系，使用全表順序掃描方法，即使選擇列上有索引。對于大關系，可以采用的啟發(fā)式規(guī)則如下：對于大關系，可以采用的啟發(fā)式規(guī)則如下：(2)(2)對于選擇條件是對于選擇條件是“主碼主碼=值值”的查詢，查詢結果最多是一個元組，的查詢，查詢結果最多是一個元組，可以選擇主碼索引。一般的可以選擇主碼索引。一般的RDBMSRDBMS會自動建立主碼索引。會自動建立主碼索引。(3)(3)對于選擇條件是對于選擇條件是“非主屬性非主屬性=值值”的查詢，并且選擇列上有索引，的查詢，并且選擇列上有索引，此時需要估算查詢結果的元組數(shù)目。如果比例較小此時需要估算查詢結果的元組數(shù)目。如果比例較小(10%)(10%)，可以使用索引，可以使用索引掃描方法，否則使用全表順序掃描。掃描方法，否則使用全表順序掃描。(4)(4)對于選擇條件是屬性上的非等值查詢或者范圍查詢，并且選擇列上對于選擇條件是屬性上的非等值查詢或者范圍查詢，并且選擇列上有索引，同樣要估算查詢結果的元組數(shù)目，如果比例較小有索引，同樣要估算查詢結果的元組數(shù)目，如果比例較小(10%)(62.5SELECT*FROM SC WHERE Grade 62.5 在這條語句中，如果在這條語句中，如果GradeGrade字段是字段是intint型的，則優(yōu)化器很難對其進行優(yōu)化，型的，則優(yōu)化器很難對其進行優(yōu)化，因為因為62.562.5是個是個floatfloat型的數(shù)據，應該在編程時將浮點型轉化為整型，而不是等型的數(shù)據，應該在編程時將浮點型轉化為整型，而不是等到運行時再轉化。到運行時再轉化。3.避免相關子查詢相關查詢效率不高。如果在主查詢和WHERE子句中的查詢出現(xiàn)了同一個列表簽，就會造成主查詢的列值改變后，子查詢也必須重新進行一次查詢。查詢的嵌套層次越多，查詢的效率就會越低，所以應該避免子查詢。如果子查詢不可避免，那么就要在查詢的過程中過濾掉盡可能多的行 本章小結 查查詢詢處處理理是是數(shù)數(shù)據據庫庫管管理理的的核核心心，而而查查詢詢優(yōu)優(yōu)化化又又是是查查詢詢處處理理的的關關鍵鍵技技術術。查查詢詢優(yōu)優(yōu)化化包包括括代代數(shù)數(shù)優(yōu)優(yōu)化化技技術術和和物物理理優(yōu)優(yōu)化化技技術術，而而物物理理優(yōu)優(yōu)化化又又包包括括基基于于存存取取路路徑徑的的優(yōu)優(yōu)化化技技術術和和基基于于代代價價估估算算的的優(yōu)優(yōu)化化方方法法。實實際際系系統(tǒng)統(tǒng)的的查查詢詢優(yōu)優(yōu)化化要要綜綜合合運運用用這這些些技技術。術。代代數(shù)數(shù)優(yōu)優(yōu)化化是是指指對對關關系系代代數(shù)數(shù)表表達達式式的的優(yōu)優(yōu)化化，即即按按照照一一定定的的規(guī)規(guī)則則，改改變變代代數(shù)數(shù)表表達達式式中中操操作作的的次次序序和和組組合合，從從而而提提高高查查詢詢執(zhí)執(zhí)行行的的效效率率。關關系系代代數(shù)數(shù)表表達達式式優(yōu)優(yōu)化化規(guī)規(guī)則則主主要要有有“優(yōu)優(yōu)先先執(zhí)執(zhí)行行選選擇擇”、“優(yōu)優(yōu)先先執(zhí)執(zhí)行行投投影影”、“笛笛卡卡爾爾積積合合并并”和和“提提取取公公共共表表達達式式”等等?；谟诖娲嫒∪÷仿窂綇降牡膬?yōu)優(yōu)化化是是指指存存取取路路徑徑和和底底層層操操作作算算法法的的選選擇擇和和優(yōu)優(yōu)化化?；谟趩l(fā)發(fā)式式規(guī)規(guī)則則的的存存取取路路徑徑優(yōu)優(yōu)化化是是定定性性的的選選擇擇，適適合合解解釋釋系系統(tǒng)統(tǒng)的的執(zhí)執(zhí)行行。代代價價估估算算的的優(yōu)優(yōu)化化是是對對多多個個查查詢詢策策略略的的優(yōu)優(yōu)化化選選擇擇，代代價價估估算算優(yōu)優(yōu)化化開開銷銷較較大大，而而且且產產生生所所有有的的執(zhí)執(zhí)行行策策略略也也是是不不可可能能的的，因因此此將將產產生生的的執(zhí)執(zhí)行行策策略略的的數(shù)數(shù)目目保保持持在在一一定定范范圍圍內內才才是是較較合合理理的的。在在編編譯譯模模式式下下查查詢詢優(yōu)優(yōu)化化后后，執(zhí)執(zhí)行行查查詢詢的的代代碼碼被被存存儲儲起起來來，稍稍后后運運行行。使使用用代代價價估估算算優(yōu)優(yōu)化化方方法法需需要要能能夠夠準準確確地地估估算算查查詢詢代代價價才才能能比比較較不不同同的的查查詢詢策策略略，比比較較適適合合在在編編譯譯模模式式下下使使用用。查查詢詢優(yōu)優(yōu)化化器器應應該該綜綜合合各各種種因因素素來來確確定最適合最合理的優(yōu)化方案。定最適合最合理的優(yōu)化方案。思 考 練 習l1.1.試述查詢優(yōu)化在關系數(shù)據庫系統(tǒng)中的必要性和可行性。試述查詢優(yōu)化在關系數(shù)據庫系統(tǒng)中的必要性和可行性。l2.2.試述查詢優(yōu)化的一般準則。試述查詢優(yōu)化的一般準則。l3.3.試述查詢優(yōu)化的一般步驟。試述查詢優(yōu)化的一般步驟。l4.4.在數(shù)據庫在數(shù)據庫(Student(Student，SCSC，Course)Course)，用戶需要查詢，用戶需要查詢“女同學選修課女同學選修課程的課程名稱和授課教師名程的課程名稱和授課教師名”l 試寫出該查詢的關系代數(shù)表達式。試寫出該查詢的關系代數(shù)表達式。l 試畫出作為查詢表達式的語法樹。試畫出作為查詢表達式的語法樹。l 對語法樹進行優(yōu)化，并畫出優(yōu)化后的語法樹。對語法樹進行優(yōu)化，并畫出優(yōu)化后的語法樹。l5.5.適用于選擇操作的啟發(fā)式規(guī)則有哪些？適用于選擇操作的啟發(fā)式規(guī)則有哪些？l6.6.總結適用于連接操作的啟發(fā)式原則?？偨Y適用于連接操作的啟發(fā)式原則。l7.7.試述影響代價估算的因素有哪些？試述影響代價估算的因素有哪些？