關(guān)系查詢處理和查詢優(yōu)化

1、關(guān)系查詢處理和查詢優(yōu)化第1頁，共31頁，2022年，5月20日，7點(diǎn)24分，星期一第九章 關(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)化 -關(guān)系代數(shù)表達(dá)式的優(yōu)化9.4 物理優(yōu)化 -存取路徑和底層操作算法的選擇第2頁，共31頁，2022年，5月20日，7點(diǎn)24分，星期一9.1關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢處理查詢處理的任務(wù)：是把用戶提交給RDBMS的查詢語句轉(zhuǎn)換為高效的執(zhí)行計(jì)劃.查詢處理步驟查詢分析查詢檢查查詢優(yōu)化查詢執(zhí)行第3頁，共31頁，2022年，5月20日，7點(diǎn)24分，星期一查詢處理步驟：詞法分析語法分析語義分析符號名轉(zhuǎn)換安全性檢查完整性檢查

2、查詢樹代數(shù)優(yōu)化物理優(yōu)化等執(zhí)行策略描述代碼生成查詢計(jì)劃的執(zhí)行代碼查詢語句數(shù)據(jù)庫數(shù)據(jù)字典查詢分析查詢檢查查詢優(yōu)化查詢執(zhí)行第4頁，共31頁，2022年，5月20日，7點(diǎn)24分，星期一實(shí)現(xiàn)查詢操作的算法示例一、選擇操作的實(shí)現(xiàn)例1 SELECT * FROM Student WHERE ； ：C1：無條件 C2：Sno=200215121； C3：Sage 20； C4：Sdept=CS AND Sage20；1、簡單的全表掃描方法 順序掃描，逐一檢查每個(gè)元組是否滿足選擇條件，把滿足條件的元組作為結(jié)果輸出。 適合：小表2、索引（或散列）掃描方法 如果條件表達(dá)式的屬性上有索引（如B+樹索引或Hash索引）

3、,通過索引先找到滿足條件的元組主碼或元組指針，再通過元組指針直接在查詢的基本表中找到元組。如 C2：第5頁，共31頁，2022年，5月20日，7點(diǎn)24分，星期一二、連接操作的實(shí)現(xiàn)例2 SELECT * FROM Student，SC WHERE Student.Sno=SC.Sno ；1、嵌套循環(huán)方法(nested loop)簡單。對外層循環(huán)Student的每一個(gè)元組，檢查內(nèi)層循環(huán)SC中的每一個(gè)元組，并檢查連接屬性是否相等2、排序-合并方法(sort-merge join)常用，適合有序表步驟：若沒排序，首先對Student、SC按連接屬性Sno排序；取Student第一個(gè)Sno，一次掃描SC

4、中具有相同Sno元組，連接起來；當(dāng)掃描到SC中第一個(gè)不相同Sno元組時(shí)，返回Student掃描下一個(gè)元組，在掃描SC中具有相同Sno元組，把它們連接起來；重復(fù)上述步驟，直到Student掃描完。第6頁，共31頁，2022年，5月20日，7點(diǎn)24分，星期一二、連接操作的實(shí)現(xiàn)3、索引連接法在SC上建立屬性Sno索引；對Student的每一個(gè)元組，由Sno值通過索引查找相應(yīng)SC元組；把這些SC元組和Student元組連接起來；循環(huán)執(zhí)行，直到Student元組處理完。4、Hash Join方法把連接屬性作為Hash碼，用同一個(gè)Hash函數(shù)把R和S中的元組散列到同一個(gè)Hash文件中；第一步，劃分階段，對

5、小表R進(jìn)行一遍處理，把它的元組按Hash函數(shù)分散到Hash表的桶中；（假設(shè)：R完全裝入內(nèi)存）第二步，試探階段（連接階段），對表S進(jìn)行一遍處理，把它的元組散列到適當(dāng)?shù)腍ash桶中，并把元組與來自R并與之匹配的元組連接起來。第7頁，共31頁，2022年，5月20日，7點(diǎn)24分，星期一9.2 關(guān)系數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化 9.2.1 查詢優(yōu)化概述查詢優(yōu)化的必要性查詢優(yōu)化極大地影響RDBMS的性能。查詢優(yōu)化是RDBMS關(guān)鍵技術(shù)、關(guān)系系統(tǒng)的優(yōu)點(diǎn)（關(guān)系系統(tǒng)：支持表結(jié)構(gòu)、選擇連接（自然）操作）查詢優(yōu)化的可能性關(guān)系表達(dá)式語義的級別很高，使DBMS可以從關(guān)系表達(dá)式中分析查詢語義。 第8頁，共31頁，2022年，5月

6、20日，7點(diǎn)24分，星期一由DBMS進(jìn)行查詢優(yōu)化的好處用戶不必考慮如何最好地表達(dá)查詢以獲得較好的效率系統(tǒng)可以比用戶程序的優(yōu)化做得更好(1) 優(yōu)化器可以從數(shù)據(jù)字典中獲取許多統(tǒng)計(jì)信息，而用戶程序則難以獲得這些信息 (2) 如果數(shù)據(jù)庫的物理統(tǒng)計(jì)信息改變了，系統(tǒng)可以自動(dòng)對查詢重新優(yōu)化以選擇相適應(yīng)的執(zhí)行計(jì)劃。 在非關(guān)系系統(tǒng)中必須重寫程序，而重寫程序在實(shí)際應(yīng)用中往往是不太可能的(3) 優(yōu)化器可以考慮數(shù)百種不同的執(zhí)行計(jì)劃，而程序員一般只能考慮有限的幾種可能性。(4) 優(yōu)化器中包括了很多復(fù)雜的優(yōu)化技術(shù)第9頁，共31頁，2022年，5月20日，7點(diǎn)24分，星期一代價(jià)模型集中式數(shù)據(jù)庫總代價(jià) = I/O代價(jià) + C

7、PU代價(jià) + 內(nèi)存代價(jià)分布式數(shù)據(jù)庫 總代價(jià) = I/O代價(jià) + CPU代價(jià)+ 內(nèi)存代價(jià) + 通信代價(jià) 查詢優(yōu)化的總目標(biāo)： 選擇有效策略,求得給定關(guān)系表達(dá)式的值,使得查詢代價(jià)最小。第10頁，共31頁，2022年，5月20日，7點(diǎn)24分，星期一9.2.2 一個(gè)實(shí)例 例：求選修了課程2的學(xué)生姓名SELECT Student.SnameFROM Student, SCWHERE Student.Sno=SC.Sno AND SC.Cno=2; 假設(shè)1：外存：Student:1000條,SC:10000條, 選修2號課程:50條假設(shè)2： 一個(gè)內(nèi)存塊裝元組:10個(gè)Student, 或100個(gè)SC或10個(gè)連

8、接結(jié)果元組 ; 內(nèi)存中一次可以存放: 5塊Student元組, 1塊SC元組假設(shè)3：讀寫速度：20塊/秒假設(shè)4：連接方法：基于數(shù)據(jù)塊的嵌套循環(huán)法第11頁，共31頁，2022年，5月20日，7點(diǎn)24分，星期一執(zhí)行策略11 name(Student.Sno=SC.Sno SC.Cno=2 (StudentSC) StudentSC 讀取總塊數(shù)= 讀Student表塊數(shù) + 讀SC表遍數(shù) *每遍塊數(shù)=1000/10+(1000/(105) (10000/100) =100+20100=2100 讀數(shù)據(jù)時(shí)間=2100/20=105秒 中間結(jié)果大小 = 1000*10000 = 107 (1千萬條元組)

9、 寫中間結(jié)果時(shí)間 = 10000000/10/20 = 50000秒讀數(shù)據(jù)時(shí)間 = 50000秒 總時(shí)間 =1055000050000秒 = 100105秒 = 27.8小時(shí)第12頁，共31頁，2022年，5月20日，7點(diǎn)24分，星期一執(zhí)行策略2 2 name(SC.Cno= 2 (Student SC)讀取總塊數(shù)= 2100塊讀數(shù)據(jù)時(shí)間=2100/20=105秒中間結(jié)果大小 =10000 （減少1000倍）寫中間結(jié)果時(shí)間 =10000/10/20=50秒讀數(shù)據(jù)時(shí)間=50秒總時(shí)間1055050秒205秒=3.4分第13頁，共31頁，2022年，5月20日，7點(diǎn)24分，星期一執(zhí)行策略32 Sna

10、me(Student SC.Cno= 2 (SC)讀SC表總塊數(shù)= 10000/100=100塊讀數(shù)據(jù)時(shí)間=100/20=5秒中間結(jié)果大小=50條 不必寫入外存讀Student表總塊數(shù)= 1000/10=100塊讀數(shù)據(jù)時(shí)間=100/20=5秒 總時(shí)間55秒10秒 第14頁，共31頁，2022年，5月20日，7點(diǎn)24分，星期一執(zhí)行策略42 name(Student SC.Cno=2 (SC)假設(shè)SC表在Cno上有索引，Student表在Sno上有索引 讀SC表索引讀SC表總塊數(shù) = 50/1001塊讀數(shù)據(jù)時(shí)間中間結(jié)果大小=50條 不必寫入外存 讀Student表索引= 讀Student表總塊數(shù)=

11、 50/10=5塊讀數(shù)據(jù)時(shí)間 總時(shí)間 連接運(yùn)算 例：Student.Sno=SC.Sno (StudentSC) Student SC 找出公共子表達(dá)式（如：視圖定義表達(dá)式）第21頁，共31頁，2022年，5月20日，7點(diǎn)24分，星期一關(guān)系代數(shù)表達(dá)式的優(yōu)化算法 算法：關(guān)系表達(dá)式的優(yōu)化輸入：一個(gè)關(guān)系表達(dá)式的查詢樹。輸出：優(yōu)化的查詢樹。方法：（1）分解選擇運(yùn)算 利用規(guī)則4把形如F1 F2 Fn (E)變換為 F1 (F2( (Fn(E) ) （2）通過交換選擇運(yùn)算，將其盡可能移到葉端 對每一個(gè)選擇，利用規(guī)則48盡可能把它移到樹的葉端。（3）通過交換投影運(yùn)算，將其盡可能移到葉端對每一個(gè)投影利用規(guī)則3

12、，9，l0，5中的一般形式盡可能把它移向樹的葉端。 第22頁，共31頁，2022年，5月20日，7點(diǎn)24分，星期一關(guān)系代數(shù)表達(dá)式的優(yōu)化算法 (續(xù))（4）合并串接的選擇和投影，以便能同時(shí)執(zhí)行或在一次掃描中完成利用規(guī)則35把選擇和投影的串接合并成單個(gè)選擇、單個(gè)投影或一個(gè)選擇后跟一個(gè)投影。使多個(gè)選擇或投影能同時(shí)執(zhí)行，或在一次掃描中全部完成盡管這種變換似乎違背“投影盡可能早做”的原則，但這樣做效率更高。 （5）對內(nèi)結(jié)點(diǎn)分組把上述得到的語法樹的內(nèi)節(jié)點(diǎn)分組。每一雙目運(yùn)算(， ，-)和它所有的直接祖先為一組(這些直接祖先是，運(yùn)算)。如果其后代直到葉子全是單目運(yùn)算，則也將它們并入該組，但當(dāng)雙目運(yùn)算是笛卡爾積(

13、)，而且其后的選擇不能與它結(jié)合為等值連接時(shí)除外。把這些單目運(yùn)算單獨(dú)分為一組。 （6）生成程序生成一個(gè)程序，每組結(jié)點(diǎn)的計(jì)算是程序中的一步。各步的順序是任意的，只要保證任何一組的計(jì)算不會在它的后代組之前計(jì)算。 第23頁，共31頁，2022年，5月20日，7點(diǎn)24分，星期一例題例：求選修了課程2的學(xué)生姓名SELECT Student.SnameFROM Student, SCWHERE Student.Sno=SC.Sno AND SC.Cno=2; 第24頁，共31頁，2022年，5月20日，7點(diǎn)24分，星期一語法樹 結(jié)果project(Sname) select(SC.Cno=2) join(S

14、tudent.Sno=SC.Sno) StudentSC關(guān)系代數(shù)語法樹Sname SC.Cno=2 Student.Sno=SC.S StudentSC第25頁，共31頁，2022年，5月20日，7點(diǎn)24分，星期一利用優(yōu)化算法把語法樹轉(zhuǎn)換成標(biāo)準(zhǔn)（優(yōu)化）形式Sname Student.Sno=SC.Sno SC.Cno=2 StudentSCSname SC.Cno=2 StudentSC第26頁，共31頁，2022年，5月20日，7點(diǎn)24分，星期一9.4物理優(yōu)化：選擇低層的存取路徑代數(shù)優(yōu)化改變查詢語句中操作的次序和組合，不涉及底層的存取路徑物理優(yōu)化就是要選擇高效合理的操作算法或存取路徑，求得優(yōu)

15、化的查詢計(jì)劃，達(dá)到查詢優(yōu)化的目標(biāo)。方法：基于規(guī)則的啟發(fā)式優(yōu)化基于代價(jià)估算的優(yōu)化兩者結(jié)合的優(yōu)化方法基于啟發(fā)式規(guī)則的存取路徑優(yōu)化一、選擇操作的啟發(fā)式規(guī)則二、連接操作的啟發(fā)式規(guī)則第27頁，共31頁，2022年，5月20日，7點(diǎn)24分，星期一一、選擇操作的啟發(fā)式規(guī)則1、對于小關(guān)系，使用全表順序掃描，即使選擇列上有索引；對于大關(guān)系2、對于選擇條件是主碼=值的查詢，查詢結(jié)果最多是一個(gè)元組，可選擇主碼索引；3、對于選擇條件是非主屬性=值的查詢，且選擇列上有索引，則要估算查詢結(jié)果的元組數(shù)目，若比例小(10%)，可用索引掃描法，否則用全表掃描法。4、對于選擇條件是屬性上的非等值查詢或范圍查詢，且選擇列上有索引，

16、同樣要估算查詢結(jié)果的元組數(shù)目，若比例小(10%)，可用索引掃描法，否則用全表掃描法。5、對于用AND的合取選擇條件，如果有涉及這些屬性的組合索引，則優(yōu)先采用組合索引掃描法，否則使用全表掃描；6、對于用OR連接的析取選擇條件，一般使用全表順序掃描。第28頁，共31頁，2022年，5月20日，7點(diǎn)24分，星期一二、連接操作的啟發(fā)式規(guī)則如果兩個(gè)表都已按連接屬性排序，則選用合并-排序方法；如果一個(gè)表在連接屬性上有索引，則選用索引連接方法；如果上面2個(gè)規(guī)則都不適用，其中一個(gè)表較小，則選用Hash Join方法；最后選用嵌套循環(huán)法，并選用其中較小的表（占用的塊數(shù)較?。┳鳛橥獗?。？第29頁，共31頁，2022年，5月20日，7點(diǎn)24分，星期一基于代價(jià)的優(yōu)化啟