第三章查詢處理步驟

查詢處理步驟

查詢分析首先，對(duì)查詢語句進(jìn)行掃描、詞法分析和語法分析。查詢檢查根據(jù)數(shù)據(jù)字典對(duì)合法的查詢語句進(jìn)行語義檢查，即檢查語句中的數(shù)據(jù)庫(kù)對(duì)象是否存在和是否有效。RDBMS一般用查詢樹（querytree）或稱為語法分析樹，來表示擴(kuò)展的關(guān)系代數(shù)表達(dá)式。查詢優(yōu)化查詢優(yōu)化就是選擇一個(gè)高效執(zhí)行的查詢處理策略。按照優(yōu)化的層次，查詢優(yōu)化可分為代數(shù)優(yōu)化和物理優(yōu)化。查詢執(zhí)行依據(jù)優(yōu)化器得到的執(zhí)行策略生成查詢計(jì)劃，由代碼生成器生成執(zhí)行這個(gè)查詢計(jì)劃的代碼。查詢優(yōu)化概述查詢優(yōu)化的必要性查詢優(yōu)化極大地影響RDBMS的性能。查詢優(yōu)化的可能性關(guān)系數(shù)據(jù)語言的級(jí)別很高，使DBMS可以從關(guān)系表達(dá)式中分析查詢語義。一、由DBMS進(jìn)行查詢優(yōu)化的好處二、查詢優(yōu)化目標(biāo)三、實(shí)際系統(tǒng)的查詢優(yōu)化步驟四、代價(jià)模型由DBMS進(jìn)行查詢優(yōu)化的好處好處一：用戶不必選擇存取路徑，不必考慮如何可以最好地表達(dá)查詢以獲得較好的效率；

好處二：系統(tǒng)可以比用戶程序的優(yōu)化做得更好。(1)優(yōu)化器可以從數(shù)據(jù)字典中獲取許多統(tǒng)計(jì)信息，而用戶程序則難以獲得這些信息；(2)如果數(shù)據(jù)庫(kù)的物理統(tǒng)計(jì)信息改變了，系統(tǒng)可以自動(dòng)對(duì)查詢重新優(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ù)，自動(dòng)優(yōu)化使所有人擁有這些技術(shù)。查詢優(yōu)化目標(biāo)查詢優(yōu)化的總目標(biāo)

選擇有效策略，求得給定關(guān)系表達(dá)式的值，使得查詢代價(jià)最?。▽?shí)際上是較?。?。實(shí)際系統(tǒng)的查詢優(yōu)化步驟實(shí)際系統(tǒng)的查詢優(yōu)化步驟1.將查詢轉(zhuǎn)換成某種內(nèi)部表示，通常是語法樹；2.根據(jù)一定的等價(jià)變換規(guī)則把語法樹轉(zhuǎn)換成標(biāo)準(zhǔn)（優(yōu)化）形式；3.選擇低層的操作算法，對(duì)于語法樹中的每一個(gè)操作：計(jì)算各種執(zhí)行算法的執(zhí)行代價(jià)選擇代價(jià)小的執(zhí)行算法4.生成查詢計(jì)劃(查詢執(zhí)行方案)查詢計(jì)劃是由一系列內(nèi)部操作組成的。

代價(jià)模型集中式數(shù)據(jù)庫(kù)單用戶系統(tǒng) 總代價(jià)=I/O代價(jià)+CPU代價(jià)多用戶系統(tǒng) 總代價(jià)=I/O代價(jià)+CPU代價(jià)+內(nèi)存代價(jià)分布式數(shù)據(jù)庫(kù)

總代價(jià)=I/O代價(jià)+CPU代價(jià)+內(nèi)存代價(jià)+通信代價(jià)

執(zhí)行策略1Ｑ1＝ПＳname(бStudent.Sno=SC.Sno∧SC.Cno='2'(Student×SC))

①Student×SC（計(jì)算廣義笛卡兒積）讀取總塊數(shù)=讀Student表塊數(shù)+讀SC表遍數(shù)*每遍塊數(shù)

=1000/10+(1000/(10×5))×(10000/100)=100+20×100=2100

讀數(shù)據(jù)時(shí)間=2100/20=105秒執(zhí)行策略1（續(xù)）

中間結(jié)果大小=1000*10000=107(1千萬條元組)

寫中間結(jié)果時(shí)間=10000000/10/20=50000秒

②б（選擇操作）

讀數(shù)據(jù)時(shí)間=50000秒

③П（投影操作）總時(shí)間=105＋50000＋50000秒=100105秒=27.8小時(shí)執(zhí)行策略2Ｑ2＝ПＳname(бSC.Cno='2'(StudentSC))

①（計(jì)算自然連接） 讀取總塊數(shù)=2100塊 讀數(shù)據(jù)時(shí)間=2100/20=105秒 中間結(jié)果大小=10000（減少1000倍） 寫中間結(jié)果時(shí)間=10000/10/20=50秒

②б（讀取中間文件塊，做選擇操作）

讀數(shù)據(jù)時(shí)間=50秒

③П（把上一步結(jié)果投影輸出）總時(shí)間＝105＋50＋50秒＝205秒=3.4分

執(zhí)行策略3Ｑ3＝ПSname(StudentбSC.Cno='2'(SC))

①б（先對(duì)SC做選擇操作） 讀SC表總塊數(shù)=10000/100=100塊

讀數(shù)據(jù)時(shí)間=100/20=5秒

中間結(jié)果大小=50條不必寫入外存

②（讀Student，把讀入的元組與內(nèi)存中的SC元組連接） 讀Student表總塊數(shù)=1000/10=100塊

讀數(shù)據(jù)時(shí)間=100/20=5秒

③П（將連接結(jié)果投影輸出）總時(shí)間＝5＋5秒＝10秒執(zhí)行策略4Ｑ4＝ПＳname(StudentбSC.Cno='2'(SC))假設(shè)SC表在Cno上有索引，Student表在Sno上有索引①б（若SC表在Cno上有索引，則選擇讀取SC表中Cno=‘2’的50個(gè)元組即可）中間結(jié)果大小=50條不必寫入外存。②（若Student表在Sno上有索引，則僅讀取SC表中滿足條件的50個(gè)元組進(jìn)行連接操作即可）

③П（將結(jié)果投影輸出）總時(shí)間<10秒查詢優(yōu)化的一般準(zhǔn)則

選擇運(yùn)算應(yīng)盡可能先做

目的：減小中間關(guān)系在執(zhí)行連接操作前對(duì)關(guān)系適當(dāng)進(jìn)行預(yù)處理按連接屬性排序在連接屬性上建立索引

投影運(yùn)算和選擇運(yùn)算同時(shí)做目的：避免重復(fù)掃描關(guān)系將投影運(yùn)算與其前面或后面的雙目運(yùn)算結(jié)合目的：減少掃描關(guān)系的遍數(shù)查詢優(yōu)化的一般準(zhǔn)則（續(xù)）某些選擇運(yùn)算＋在其前面執(zhí)行的笛卡爾積===>連接運(yùn)算

例：бStudent.Sno=SC.Sno(Student×SC)

StudentSC提取公共子表達(dá)式舉例SELECTStudent.SnameFROMStudent,SCWHEREStudent.Sno=SC.SnoANDSC.Cno='2';查詢樹結(jié)果project(Sname)

select(SC.Cno=

2

)

join(Student.Sno=SC.Sno)

StudentSC舉例（續(xù)）關(guān)系代數(shù)語法