華科數(shù)據(jù)庫系統(tǒng)原理第九章

1、第9章 關(guān)系查詢處理和查詢優(yōu)化9.1 問題的提出 非過程化，無需顯示指明存取路經(jīng)。 查詢操作的多解性：同一個查詢操作可能存在多種實現(xiàn)途徑（算法不同、存取方法不同）。 代數(shù)優(yōu)化優(yōu)化關(guān)系代數(shù)表達式 物理優(yōu)化優(yōu)化存取路徑和底層操作算法，可進一步分為基于規(guī)則的（rule based）、基于代價的（cost based）和基于語義的（semantic based）。12基于規(guī)則的基于代價的基于語義的關(guān)系代數(shù)等價變換規(guī)則查詢處理步驟基本概念1查詢分析（詞法、語法、語義、符號名）查詢樹（query tree）語法分析樹（syntax tree）執(zhí)行樹執(zhí)行計劃3實例 設(shè)有如下關(guān)系： 學生（學號，姓名，性別，出

2、生日期，所在系） 課程（課號，名稱，學分） 成績（學號，課號，成績） 要求查詢選修了2號課程的學生姓名。 可用如下等價的代數(shù)表達式來完成這一查詢： Q1姓名（學生.學號=成績.學號課號=2（學生成績） Q2姓名（課號=2 (學生 成績） Q3姓名（學生 課號=2（成績） 由于查詢執(zhí)行的策略不同,查詢時間相差很大。4統(tǒng)計量：學生記錄1000條；成績記錄10000條；選修了2號課程的記錄50條。一個物理塊（頁面）能容納： 10條學生記錄 或100條成績記錄。內(nèi)存僅提供7個存儲頁面，其中5頁存放學生記錄，1頁存放成績記錄，1頁存放中間結(jié)果。磁盤每秒鐘讀/寫20塊數(shù)據(jù)記錄。采用嵌套循環(huán)實現(xiàn)方式。5外表

3、:學生表內(nèi)表:成績表第一種情況： Q1姓名（學生.學號=成績.學號課號=2（學生成績） 1計算：學生成績 讀取的總塊數(shù)為： 1000/10+1000/(105)10000/100=2100(塊) 所需時T1=2100/20=105(秒) 笛卡兒集的元組個數(shù)為103104107，設(shè)每塊能裝10個元組，則寫出這些塊所需的時間T2=106/20=5104(秒) 6學生表塊數(shù)學生表批量讀次數(shù)成績表塊數(shù)注意:寫出!2作選擇 依次讀入連接后的結(jié)果，選擇滿足條件的記錄，假定內(nèi)存處理時間忽略不計，則讀取中間結(jié)果的時間T3與T2相等，即T3=5104 (秒)，滿足條件的記錄僅有50條，結(jié)果直接駐留內(nèi)存。3作投影

4、 將內(nèi)存中的結(jié)果在“姓名”上作投影，得最終結(jié)果，因此第一種情況下執(zhí)行查詢的總時間為：T=T1+T2+T3105(秒)（總時間約28小時）7第二種情況 Q2姓名（課號=2 (學生 成績）1計算自然連接 讀取學生表和成績表的策略不變，總的讀取時間仍105秒，但自然連接的結(jié)果比第一種情況大大減少，為104條，因此，寫出這些元組所需時間為104/10/2050（秒）。2作選擇 讀取中間結(jié)果所需的時間仍為50（秒），符合條件的記錄為50條。3作投影 將中間結(jié)果投影輸出。 第二種情況總的執(zhí)行時間為：1055050205（秒）810000條成績記錄第三種情況 Q3姓名（學生 課號=2（成績）1先對成績表作選

5、擇運算，只讀取一遍成績表，存取花費時間為5秒，因滿足條件的記錄為50條，不必使用中間文件。2讀取學生表并與內(nèi)存中的成績記錄作連接，花費時間5秒。3輸出投影結(jié)果。 第三種情況總的執(zhí)行時間為10秒。 上例充分說明查詢優(yōu)化的必要性，同時給出一些查詢優(yōu)化方法的基本思想（避免笛卡兒積,盡量讓選擇運算在連接運算之前執(zhí)行）。91000/10/20基本概念2選擇運算的實現(xiàn)方法： 全表掃描 索引掃描連接運算的實現(xiàn)方法： 嵌套循環(huán)連接（nested loop） 排序合并連接（sort-merge join） Hash連接（hash join） 索引連接（index join）10兩個關(guān)系是否只掃描一次？如果兩個關(guān)

6、系的連接屬性均存在重復值又會如何？HASH連接9.2 查詢優(yōu)化的任務：提高速度（DBMS）9.3 查詢優(yōu)化的目標1、減少中間關(guān)系規(guī)模2、減少I/O關(guān)系代數(shù)表達式的等價變換規(guī)則（課本269271頁）SQL查詢的代數(shù)處理過程（課本272頁，圖9.39.5）9.4 一般策略（查詢樹的啟發(fā)式優(yōu)化）1、“選擇”盡可能提前執(zhí)行；最基本一條，因為“選擇”使中間結(jié)果變小。2、索引和排序特別是對連接運算，連接前“先排序”或“建立”索引，提高速度。11例如：對Borrower 與Loans進行自然聯(lián)接計算時： 對loans 按card-no建立索引； 對Borrower 每一元組的card-no值：通過loans

7、 索引查元組Borrower 元組與相應元組連接起來 無需反復掃描loans3、“投影”和“選擇”同時進行，（避免多次掃描關(guān)系，否則投影選擇各掃描一次）。 前提是兩種運算對同一關(guān)系運算才成立。124、 （某些）選擇與選擇前的笛卡爾積結(jié)合掃描得到的元組立即與參與計算的另一元組做匹配條件過濾，將這種笛卡爾積轉(zhuǎn)變?yōu)檫B接運算。連接運算（特別是等值連接運算）比笛卡爾積快。5、投影與其前后的其它雙目運算同時進行，避免重復掃描關(guān)系。6、提取公共子表達式。計算公共子表達式結(jié)果 結(jié)果存入外存 需要時從外存調(diào)入內(nèi)存使用（無需重計算） 前提：外存調(diào)入內(nèi)存的時間大大少于計算公共表達式時間13關(guān)系表達式代數(shù)優(yōu)化算法1）

8、運用選擇的串接定律，得到選擇運算“串”；2）對每個選擇運算符，利用等價變換盡量將其移至樹的葉端；3）對每個投影運算符，利用等價變換盡量將其移至樹的葉端；4）嘗試將“選擇”和“投影”串接合并成單個“選擇”或“投影”，或“選擇”后跟一個“投影”；5）上述得到的語法樹內(nèi)結(jié)點分組：雙目運算和它的父節(jié)點為一組。若其后代直至葉節(jié)點全是單目運算，也合并為一組。笛卡爾積的子節(jié)點若是不能組合成等值連接的“選擇”，則二者不合并。14查詢樹15關(guān)系代數(shù)語法樹16代數(shù)優(yōu)化后的查詢樹117代數(shù)優(yōu)化后的查詢樹2189.5 物理優(yōu)化 常常先使用啟發(fā)式規(guī)則選取若干較優(yōu)的候選查詢方案，然后分別估算這些候選方案的執(zhí)行代價，從而選

9、取代價最小的作為執(zhí)行計劃。 總代價I/O代價CPU代價內(nèi)存代價通信代價 啟發(fā)式規(guī)則 選擇操作的啟發(fā)式規(guī)則1）對于小關(guān)系，使用全表順序掃描，即使選擇列上有索引。2）對于選擇條件是“主碼=值”的查詢，可以選擇主碼索引。 （一般的DBMS會自動的建立主碼索引）193）對于選擇條件是“非主屬性=值”的查詢，并且選擇列上有索引，則估算查詢結(jié)果元組數(shù)目，如果比例較小，可以使用索引掃描算法，否則還是使用全表順序掃描。（DBA監(jiān)控）4）對于選擇條件是屬性上的非等值查詢或者范圍查詢，并且選擇列上有索引，則估算查詢結(jié)果的元組數(shù)目，如果比例較小，可以使用索引掃描，否則使用全表順序掃描。5）對于用AND連接的合取選擇

10、條件，如果有涉及這些屬性的組合索引，則優(yōu)先采用組合索引；如果有多個一般索引，可以用索引掃描并求交集的方法；否則采用全表順序掃描。6）對于用OR連接的析取選擇條件，一般使用全表順序掃描。20selectivity連接操作的啟發(fā)式規(guī)則1）如果2個表都已按照連接屬性排序，則選用merge-sort方法。2）如果1個表在連接屬性上有索引，則可選用索引連接方法。3）如果上述2個規(guī)則均不適用，且其中1個表較小，可選用hash join方法。4）對于nested loop join方法，選擇占用塊數(shù)較小的表作外表。 問題：內(nèi)存塊的分配？外表的選擇？21為什么采用啟發(fā)式規(guī)則？ 可能的執(zhí)行策略很多，要窮盡所有的

11、策略進行代價估算需要的計算開銷往往與被連接的關(guān)系數(shù)成指數(shù)復雜度關(guān)系。 可能造成查詢優(yōu)化過程的開銷大于獲得的查詢開銷的減小，得不償失。22啟發(fā)式規(guī)則在一般情況下適用，但不一定保證獲得最優(yōu)執(zhí)行計劃。（試運行、DBA性能調(diào)整） 和啟發(fā)式方法類似的其他解決方法： 貪婪算法、遺傳算法。 其思想都是類似求近似最優(yōu)解。 啟發(fā)式方法適用于解釋執(zhí)行方式（優(yōu)化開銷包含在查詢總開銷中），對于編譯執(zhí)行方式，可采用基于代價的優(yōu)化方法。23代價估算 與數(shù)據(jù)庫的狀態(tài)密切相關(guān)，需要在數(shù)據(jù)字典中存儲優(yōu)化器所要的統(tǒng)計信息。統(tǒng)計信息1.基本表 元組總數(shù)、元組長度、占用塊數(shù)、溢出塊數(shù)2.列 不同值的個數(shù)、選擇率selectivity

12、、最大值、最小值、是否有索引、索引類型3.索引 索引層數(shù)、不同索引值個數(shù)、索引選擇基數(shù)（同索引值的情況）、葉結(jié)點個數(shù)24代價估算公式 B：表的塊數(shù)； L：索引深度； S：索引選擇基數(shù)； Y：索引葉結(jié)點數(shù)； Frs:連接選擇性； Mrs:連接結(jié)果單塊記錄數(shù)； Nr關(guān)系R元組數(shù)； Ns關(guān)系S元組數(shù)。1.全表掃描 cost=B, 對于單值搜索，cost=B/22.索引掃描 cost=L+1 碼=值 cost=L+S 非碼屬性=值 cost=L+Y/2+B/2 、=、=3.nested loop join cost=Br+Br*Bs/(K-1)+(Frs*Nr*Ns)/Mrs4.merge join

13、cost=Br+Bs+(Frs*Nr*Ns)/Mrs259.6 查詢優(yōu)化小結(jié)優(yōu)化是為了減小查詢的代價，包括I/O、CPU、內(nèi)存和通信代價，是關(guān)系數(shù)據(jù)庫的重要問題。導致查詢代價較高的一個主要原因是關(guān)系代數(shù)的笛卡兒積運算。理解優(yōu)化的問題需要先了解關(guān)系操作的執(zhí)行過程。26優(yōu)化的手段包括代數(shù)和邏輯兩種類型，涉及眾多方面：關(guān)系代數(shù)運算符執(zhí)行的先后順序和組合情況、運算符執(zhí)行所采用的算法、數(shù)據(jù)的聚集存儲、表的分區(qū)、文件中的碎片、跨頁鏈接的數(shù)量、元組的排序、索引的建立、緩沖區(qū)的大小、 DBMS對語句的緩存機制、語句的解釋或者編譯執(zhí)行、優(yōu)化算法的開銷和準確性、統(tǒng)計信息的時效性與詳細程度、代價估算模型的精確與否等等。27查詢優(yōu)化的過程：查詢樹經(jīng)過變形后得到語法樹，然后根據(jù)代數(shù)優(yōu)化的啟發(fā)式規(guī)則對語法樹進行邏輯優(yōu)化，再考慮存取路徑、底層操作算法的不同，根據(jù)物理操作的啟發(fā)式規(guī)則提出多種查詢計劃，然后可根據(jù)某種代價模型評估這些查詢計劃的執(zhí)行代價，從中選取評估結(jié)果最小的作為執(zhí)行計劃。28DBMS查詢優(yōu)化1）優(yōu)化器可以獲取數(shù)據(jù)字典中的統(tǒng)計信息