第9章關(guān)系查詢處理和查詢優(yōu)化.ppt

1 數(shù)據(jù)庫系統(tǒng)概論AnIntroductiontoDatabaseSystem第九章關(guān)系查詢處理和查詢優(yōu)化 2 第九章關(guān)系查詢處理和查詢優(yōu)化 9 1關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢處理9 2關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化9 3代數(shù)優(yōu)化9 4物理優(yōu)化9 5小結(jié) 3 9 1關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢處理 9 1 1查詢處理的步驟查詢分析查詢檢查查詢優(yōu)化查詢執(zhí)行 4 9 1 2實現(xiàn)查詢操作的算法舉例 一 選擇操作的實現(xiàn)例1 Select fromstudentwhere的幾種情況 C1 無條件 C2 Sno 200215121 C3 Sage 20 C4 Sdept CS ANDSage 20 5 選擇操作的實現(xiàn)方法 1簡單的全表掃描方法對查詢的基本表順序掃描 逐一檢查每個元組是否滿足條件 把滿足條件的元組作為結(jié)果輸出 小表有效 大表順序掃描效率低 6 索引掃描方法若選擇條件中的屬性上有索引 B 樹索引或Hash索引 可以用索引掃描方法 通過索引先找到滿足條件的元組主碼或元組指針 再通過元組指針直接在查詢的基本表中找到元組 選擇操作的實現(xiàn)方法 7 B 樹索引 25 351 516879 31530 798493 68697176 515465 3041 152025 37 25 8 索引掃描方法的實現(xiàn) C2 若Sno上有索引 則通過索引查找到該Sno元組的指針 從而檢索到該學(xué)生 C3 若Sage上有B 樹索引 則可以B 樹索引找到該索引項 從而根據(jù)B 樹的順序集得到該元組的指針 檢索到目標(biāo)元組 C4 若兩個條件都有索引 先分別找到滿足兩個條件的指針 再求交集 從而檢索到目標(biāo)元組 找到某一項的指針 找到滿足條件的元組集 在根據(jù)另一條件 找到滿足條件的元組 9 二 連接操作的實現(xiàn) 例2 SELECT FROMStudent SCWHEREStudent Sno SC Sno 1 嵌套循環(huán)方法 nestedloop 對外層循環(huán) Student 的每一個元組 s 檢索內(nèi)層循環(huán) SC 中的每一個元組 sc 并檢查這兩個元組在連接屬性 sno 上是否相等 滿足條件則串接后輸出 否則知道外層循環(huán)表中的元組處理完為止 最耗時的操作 10 用排序 合并連接方法步驟 若連接的表沒有排好序 首先對Student表和SC表按連接屬性Sno排序 取Student表中第一個Sno 依次掃描SC表中具有相同Sno的元組 把它們連接起來 當(dāng)掃描到Sno不相同的第一個SC元組時 返回Student表掃描它的下一個元組 再掃描SC表中具有相同Sno的元組 把它們連接起來 重復(fù)上述步驟直到Student表掃描完 2 排序 合并方法 sort mergejoin或mergejoin 11 用索引連接方法的步驟 如果原來沒有的話 在SC表上建立屬性Sno的索引 對Student中每一個元組 由Sno值通過SC的索引查找相應(yīng)的SC元組 把這些SC元組和Student元組連接起來 循環(huán)執(zhí)行2 3 直到Student表中的元組處理完為止 4 HashJoin方法 3 索引連接 indexjoin 方法 12 9 2關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化 9 2 1查詢優(yōu)化概述9 2 2實例 13 9 2 1查詢優(yōu)化概述 關(guān)系系統(tǒng)的查詢優(yōu)化是RDBMS實現(xiàn)的關(guān)鍵技術(shù) 是關(guān)系系統(tǒng)的優(yōu)點所在 查詢優(yōu)化的可能性關(guān)系數(shù)據(jù)語言的級別很高 使DBMS可以從關(guān)系表達式中分析查詢語義 從而提供了執(zhí)行查詢優(yōu)化的可能性 14 DBMS進行查詢優(yōu)化的便利條件 用戶不必考慮如何最好地表達查詢以獲得較好的效率系統(tǒng)可以比用戶程序的優(yōu)化做得更好 1 優(yōu)化器可以從數(shù)據(jù)字典中獲取許多統(tǒng)計信息 而用戶程序則難以獲得這些信息 15 由DBMS進行查詢優(yōu)化的好處 2 如果數(shù)據(jù)庫的物理統(tǒng)計信息改變了 系統(tǒng)可以自動對查詢重新優(yōu)化以選擇相適應(yīng)的執(zhí)行計劃 在非關(guān)系系統(tǒng)中必須重寫程序 而重寫程序在實際應(yīng)用中往往是不太可能的 3 優(yōu)化器可以考慮數(shù)百種不同的執(zhí)行計劃 而程序員一般只能考慮有限的幾種可能性 4 優(yōu)化器中包括了很多復(fù)雜的優(yōu)化技術(shù) 16 查詢優(yōu)化目標(biāo) 查詢優(yōu)化的總目標(biāo)選擇有效策略 求得給定關(guān)系表達式的值 使得查詢代價最小 實際系統(tǒng)的查詢優(yōu)化步驟1 將查詢轉(zhuǎn)換成某種內(nèi)部表示 通常是語法樹2 根據(jù)一定的等價變換規(guī)則把語法樹轉(zhuǎn)換成標(biāo)準(zhǔn) 優(yōu)化 形式 17 實際系統(tǒng)的查詢優(yōu)化步驟 3 選擇低層的操作算法對于語法樹中的每一個操作計算各種執(zhí)行算法的執(zhí)行代價選擇代價小的執(zhí)行算法4 生成查詢計劃 查詢執(zhí)行方案 查詢計劃是由一系列內(nèi)部操作組成的 18 代價模型 集中式數(shù)據(jù)庫單用戶系統(tǒng)總代價 I O代價 CPU代價多用戶系統(tǒng)總代價 I O代價 CPU代價 內(nèi)存代價 開銷 分布式數(shù)據(jù)庫總代價 I O代價 CPU代價 內(nèi)存代價 通信代價 19 9 2 2查詢優(yōu)化的必要性 舉例 例 求選修了2號課程的學(xué)生姓名SELECTStudent SnameFROMStudent SCWHEREStudent Sno SC SnoANDSC Cno 2 1 sname Student Sno SC Sno SC Cno 2 Student SC 2 Sname SC Cno 2 StudentSC 3 name Student SC Cno 2 SC 20 查詢優(yōu)化的必要性 續(xù) 假設(shè)1 外存 Student 1000條 SC 10000條 其中選修2號課程 50條假設(shè)2 一個內(nèi)存塊裝元組 10個Student元組 或100個SC元組 內(nèi)存中一次可以存放 5塊Student元組 1塊SC元組和若干塊連接結(jié)果元組假設(shè)3 讀寫速度 20塊 秒假設(shè)4 連接方法 基于數(shù)據(jù)塊的嵌套循環(huán)法 21 Student SC讀取總塊數(shù) 讀Student表塊數(shù) 讀SC表遍數(shù) 每遍塊數(shù) 1000 10 1000 10 5 10000 100 100 20 100 2100讀數(shù)據(jù)時間 2100 20 105秒 查詢優(yōu)化的必要性 續(xù) 1 1 sname Student Sno SC Sno SC Cno 2 Student SC 22 中間結(jié)果大小 1000 10000 107 1千萬條元組 寫中間結(jié)果時間 10000000 10 20 50000秒 讀數(shù)據(jù)時間 50000秒 總時間 105 50000 50000秒 100105秒 27 8小時 23 查詢優(yōu)化的必要性 續(xù) 2 2 name SC Cno 2 StudentSC 讀取總塊數(shù) 2100塊讀數(shù)據(jù)時間 2100 20 105秒中間結(jié)果大小 10000 減少1000倍 寫中間結(jié)果時間 10000 10 20 50秒 讀數(shù)據(jù)時間 50秒 總時間 105 50 50秒 205秒 3 4分 24 查詢優(yōu)化的必要性 續(xù) 3 3 Sname Student SC Cno 2 SC 讀SC表總塊數(shù) 10000 100 100塊讀數(shù)據(jù)時間 100 20 5秒中間結(jié)果大小 50條不必寫入外存 讀Student表總塊數(shù) 1000 10 100塊讀數(shù)據(jù)時間 100 20 5秒 總時間 5 5秒 10秒 25 查詢優(yōu)化的必要性 續(xù) 4 3 name Student SC Cno 2 SC 假設(shè)SC表在Cno上有索引 Student表在Sno上有索引 讀SC表索引 讀SC表總塊數(shù) 50 100 1塊讀數(shù)據(jù)時間中間結(jié)果大小 50條不必寫入外存 26 查詢優(yōu)化的必要性 續(xù) 讀Student表索引 讀Student表總塊數(shù) 50 10 5塊讀數(shù)據(jù)時間 總時間 10秒 27 9 3代數(shù)優(yōu)化 9 3 1關(guān)系代數(shù)表達式等價變換規(guī)則9 3 2查詢樹的啟發(fā)式優(yōu)化 28 9 3 1關(guān)系代數(shù)表達式等價變換規(guī)則 關(guān)系代數(shù)表達式等價指用相同的關(guān)系代替兩個表達式中相應(yīng)的關(guān)系所得到的結(jié)果是相同的上面的優(yōu)化策略大部分都涉及到代數(shù)表達式的變換 29 常用的等價變換規(guī)則 設(shè)E1 E2等是關(guān)系代數(shù)表達式 F是條件表達式l 連接 笛卡爾積交換律E1 E2 E2 E1E1E2 E2E1E1FE2 E2FE1 30 關(guān)系代數(shù)等價變換規(guī)則 續(xù) 2 連接 笛卡爾積的結(jié)合律 E1 E2 E3 E1 E2 E3 E1E2 E3 E1 E2E3 E1E2 E3 E1 E2E3 F1F2F1F2 31 關(guān)系代數(shù)等價變換規(guī)則 續(xù) 3 投影的串接定律 A1 A2 An B1 B2 Bm E A1 A2 An E 假設(shè) 1 E是關(guān)系代數(shù)表達式2 Ai i 1 2 n Bj j l 2 m 是屬性名3 A1 A2 An 構(gòu)成 Bl B2 Bm 的子集 32 關(guān)系代數(shù)等價變換規(guī)則 續(xù) 4 選擇的串接定律 F1 F2 E F1 F2 E 選擇的串接律說明選擇條件可以合并這樣一次就可檢查全部條件 33 關(guān)系代數(shù)等價變換規(guī)則 續(xù) 5 選擇與投影的交換律 1 假設(shè) 選擇條件F只涉及屬性A1 An F A1 A2 An E A1 A2 An F E 2 假設(shè) F中有不屬于A1 An的屬性B1 Bm A1 A2 An F E A1 A2 An F A1 A2 An B1 B2 Bm E 34 關(guān)系代數(shù)等價變換規(guī)則 續(xù) 6 選擇與笛卡爾積的交換律 1 假設(shè) F中涉及的屬性都是E1中的屬性 F E1 E2 F E1 E2 2 假設(shè) F F1 F2 并且F1只涉及E1中的屬性 F2只涉及E2中的屬性則由上面的等價變換規(guī)則1 4 6可推出 F E1 E2 F1 E1 F2 E2 35 關(guān)系代數(shù)等價變換規(guī)則 續(xù) 3 假設(shè) F F1 F2 F1只涉及E1中的屬性 F2涉及E1和E2兩者的屬性 F E1 E2 F2 F1 E1 E2 它使部分選擇在笛卡爾積前先做 36 關(guān)系代數(shù)等價變換規(guī)則 續(xù) 7 選擇與并的分配率假設(shè) E E1 E2 E1 E2有相同的屬性名 F E1 E2 F E1 F E2 8 選擇與差運算的分配率假設(shè) E1與E2有相同的屬性名 F E1 E2 F E1 F E2 37 關(guān)系代數(shù)等價變換規(guī)則 續(xù) 9選擇對自然連接的分配率 F E1E2 F E1 F E2 F只涉及E1與E2的公共屬性 38 關(guān)系代數(shù)等價變換規(guī)則 續(xù) 10 投影與笛卡爾積的分配率假設(shè) E1和E2是兩個關(guān)系表達式 A1 An是E1的屬性 B1 Bm是E2的屬性 A1 A2 An B1 B2 Bm E1 E2 A1 A2 An E1 B1 B2 Bm E2 39 關(guān)系代數(shù)等價變換規(guī)則 續(xù) 11 投影與并的分配率假設(shè) E1和E2有相同的屬性名 A1 A2 An E1 E2 A1 A2 An E1 A1 A2 An E2 40 9 3 2查詢樹的啟發(fā)式優(yōu)化 啟發(fā)式規(guī)則 heuristicrules 的代數(shù)優(yōu)化典型的啟發(fā)式規(guī)則 1選擇運算應(yīng)盡可能先做在優(yōu)化策略中這是最重要 最基本的一條 它常?？墒箞?zhí)行時節(jié)約幾個數(shù)量級 因為選擇運算一般使計算的中間結(jié)果大大變小 41 典型的啟發(fā)式規(guī)則 2把投影運算和選擇運算同時進行如有若干投影和選擇運算 并且它們都對同一個關(guān)系操作 則可以在掃描此關(guān)系的同時完戌所有的這些運算以避免重復(fù)掃描關(guān)系 42 典型的啟發(fā)式規(guī)則 3投影同雙目運算結(jié)合把投影同其前或其后的雙目運算結(jié)合起來 沒有必要為了去掉某些字段而掃描一遍關(guān)系 43 典型的啟發(fā)式規(guī)則 4選擇同某些笛卡爾積結(jié)合起來構(gòu)成一個連接運算把某些選擇同在它前面要執(zhí)行的笛卡爾積結(jié)合起來成為一個連接運算 連接特別是等值連接運算要比同樣關(guān)系上的笛卡爾積省很多時間 44 5找出公共子表達式如果重復(fù)出現(xiàn)的子表達式的查詢結(jié)果不是很大的關(guān)系 并且從外存中讀入這個關(guān)系比計算該子表達式的時間少得多 則先計算一次公共子表達式并把結(jié)果寫入中間文件是合算的 當(dāng)查詢的是視圖時 定義視圖的表達式就是公共子表達式的情況 典型的啟發(fā)式規(guī)則 45 關(guān)系代數(shù)表達式的優(yōu)化算法 輸入 一個關(guān)系表達式的查詢樹輸出 優(yōu)化的查詢樹方法 1 利用規(guī)則4將形如變換為 2 對每一選擇 利用等價變換規(guī)則4 9盡可能將它移到樹的葉端 46 優(yōu)化算法 3 對每一個投影 利用規(guī)則3 5 10 11中的一般形式盡可能將它移到樹的葉端 4 利用規(guī)則3 5將選擇和投影的串接合并成單個選擇 單個投影或一個選擇后跟一個投影 使多個選擇或投影能同時進行 或在一次掃描中全部完成 47 優(yōu)化算法 5 將上述得到的語法樹的內(nèi)節(jié)點分組 每一雙目運算 和它所有的直接祖先為一組 這些直接祖先是 運算 如果其后代直到葉子全部是單目運算 則將它并入該組 48 舉例 例 供應(yīng)商數(shù)據(jù)庫中有 供應(yīng)商 零件 項目 供應(yīng)四個基本表 關(guān)系 S Sno Sname Status City P Pno Pname Color Weight J Jno Jname City SPJ Sno Pno Jno Qty 49 舉例 用戶有一查詢語句 檢索使用上海供應(yīng)商生產(chǎn)的紅色零件的工程號 1 試寫出該查詢的關(guān)系代數(shù)表達式 2 試寫出查詢優(yōu)化的關(guān)系代數(shù)表達式 3 畫出該查詢初始的關(guān)系代數(shù)表達式的語法樹 4 使用優(yōu)化算法 對語法樹進行優(yōu)化 并畫出優(yōu)化后的語法樹 50 舉例 解 1 該查詢的關(guān)系代數(shù)表達式如下 2 查詢優(yōu)化的關(guān)系代數(shù)表達式如下 3 該查詢初始的關(guān)系代數(shù)表達式的語法樹如下圖1所示 4 優(yōu)化后的語法樹如圖2所示 51 優(yōu)化前的查詢樹 關(guān)系代數(shù)語法樹 圖1 52 優(yōu)化后的查詢樹 圖2 53 9 4物理優(yōu)化 代數(shù)優(yōu)化改變查詢語句中操作的次序和組合 不涉及底層的存取路徑 物理優(yōu)化是要選擇高效合理的操作算法或存取路徑 求得優(yōu)化的查詢計劃 達到查詢優(yōu)化的目的 54 物理優(yōu)化選擇的方法 基于規(guī)則的啟發(fā)式優(yōu)化 大多數(shù)情況下都適用基于代價估算的優(yōu)化 優(yōu)化器估算不同執(zhí)行策略的代價 并選出具有最小代價的執(zhí)行計劃兩者結(jié)合的優(yōu)化方法 先使用啟發(fā)式規(guī)則 選取若干較優(yōu)的候選方案 減少代價估算的工作量 然后分別計算這些候選方案的執(zhí)行代價 較快地選出最終的優(yōu)化方案 55 9 4 1基于啟發(fā)式規(guī)則的存取路徑選擇優(yōu)化 選擇操作的啟發(fā)式規(guī)則 使用全表順序掃描 即使選擇列上有索引 小關(guān)系 對于選擇條件是主碼 值的查詢 查詢結(jié)果最多是一個元組 可以選擇主碼索引 一般情況RDBMS會自動建立主碼索引 對于選擇條件是非主屬性 值的查詢 并且選擇列上有索引 則要估算查詢結(jié)果的元組數(shù)目 若比例較小 10 則使用索引掃描方法 否則使用全表順序掃描 56 選擇操作的啟發(fā)式規(guī)則 對于選擇條件是屬性上的非等值查詢或者范圍查詢 并且選擇列上有索引 同樣要估算查詢結(jié)果的元組數(shù)目 若比例較小 10 可以使用索引掃描方法 否則使用全表順序掃描 對于用AND連接的合取選擇條件 若有涉及這些屬性的組合索引 則優(yōu)先采用組合索引掃描方法 若某些屬性上有一般的索引 則可以用 例1 C4 中介紹的索引掃描方法 否則使用全表順序掃描 對于用OR連接的析取選擇條件 一般使用全表順序掃描 57 連接操作的啟發(fā)式規(guī)則 若兩個表都已經(jīng)按照連接屬性排序 則選用排序 合并方法 若一個表在連接屬性上有索引 則可以選用索引連接方法 若上面兩條規(guī)則都不適用 其中一個表較小 則可以選用HASHJoin方法 最后可以選用嵌套循環(huán)方法 并選擇其中較小的表 即占用塊數(shù)較小的表 作為外表 58 9 4 2基于代價的優(yōu)化 啟發(fā)式規(guī)則優(yōu)化是定性的選擇 較粗糙 但實現(xiàn)簡單而且優(yōu)化本身代價較小 適用于解釋執(zhí)行的系統(tǒng) 在編譯系統(tǒng)中 一次編譯優(yōu)化 多次執(zhí)行 查詢優(yōu)化和查詢執(zhí)行分開進行 因此適合用精細復(fù)雜的基于代價的優(yōu)化方法 59 一 統(tǒng)計信息 基于代價的優(yōu)化方法要計算各種操作算法的執(zhí)行代