查詢處理與查詢代價估計(jì)

查詢處理與查詢代價估計(jì)目錄

查詢處理1、查詢分析2、查詢優(yōu)化3、查詢執(zhí)行

查詢代價估計(jì)

查詢處理查詢處理查詢處理是指從數(shù)據(jù)庫中提取數(shù)據(jù)的一系列活動。

包括： 1、將用高層數(shù)據(jù)庫語言表示的查詢語句翻譯成文件系統(tǒng)這一物理層次上實(shí)現(xiàn)的表達(dá)式； 2、為優(yōu)化查詢進(jìn)行各種轉(zhuǎn)換； 3、查詢的實(shí)際執(zhí)行。查詢處理過程查詢執(zhí)行計(jì)劃查詢結(jié)果數(shù)據(jù)基于數(shù)據(jù)的統(tǒng)計(jì)分析優(yōu)化器語法分析器和翻譯器執(zhí)行引擎DBMS關(guān)系代數(shù)表達(dá)式查詢分析在數(shù)據(jù)庫執(zhí)行查詢處理之前，系統(tǒng)先將查詢語句翻譯成可使用的形式。翻譯過程： 1、語法分析器將查詢翻譯成系統(tǒng)內(nèi)部表示形式； 2、翻譯的同時進(jìn)行語法檢查； 3、構(gòu)造查詢語句的語法分析樹； 4、翻譯成關(guān)系代數(shù)表達(dá)式。對于給出的一個查詢，一般經(jīng)過翻譯器翻譯后都會有多種關(guān)系代數(shù)表達(dá)式與之對應(yīng)。查詢分析實(shí)例查詢實(shí)例:求選修2號課程的學(xué)生姓名SQL表示:selectSnamefromStudents,SCwhereStudents.Sno=SC.SnoandCno=‘2’；翻譯結(jié)果：

Q1=πSname(σStudent.Sno=SC.Sno∧Sc.Cno='2'(Student×SC)) Q2=πSname(σSc.Cno='2'(StudentSC)) Q3=πSname(StudentσSc.Cno='2'(SC))優(yōu)化器功能功能：負(fù)責(zé)產(chǎn)生最有效的查詢執(zhí)行計(jì)劃（QEP）邏輯轉(zhuǎn)換部分：對于一個語法樹，根據(jù)關(guān)系代數(shù)等價變換規(guī)則，得到所有的等價的關(guān)系代數(shù)表達(dá)式；物理轉(zhuǎn)換部分：對于每一個關(guān)系代數(shù)表達(dá)式，根據(jù)查詢引擎提供的物理操作，找出所有可能的查詢執(zhí)行計(jì)劃。比較和查找：根據(jù)代價估計(jì)函數(shù)，估計(jì)每一個查詢執(zhí)行計(jì)劃的代價，并從中找出代價最小的查詢執(zhí)行計(jì)劃。優(yōu)化器處理過程查詢請求等價變換規(guī)則集邏輯轉(zhuǎn)換物理轉(zhuǎn)換物理操作集查找代價估計(jì)函數(shù)代價最小QEP等價的語法樹集合等價的QEP查詢執(zhí)行引擎功能：查詢執(zhí)行引擎為每一個關(guān)系操作的實(shí)現(xiàn)提供多種物理實(shí)現(xiàn)方法。選擇操作有兩種可能的物理操作：順序掃描和索引掃描連接操作有三種可能的物理操作：嵌套循環(huán)連接、合并連接和散列連接。查詢執(zhí)行引擎還可以提供更多的物理實(shí)現(xiàn)方法。每一種物理實(shí)現(xiàn)方法利用不同的存取路徑（如索引、數(shù)據(jù)的存儲分布、元組的排序等）負(fù)責(zé)產(chǎn)生執(zhí)行查詢的代碼

查詢代價的估計(jì)查詢的代價查詢執(zhí)行開銷主要包括

集中式數(shù)據(jù)庫

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

分布式數(shù)據(jù)庫

總代價=I/O代價+CPU代價+內(nèi)存代價+通信代價查詢代價主要取決于磁盤訪問的次數(shù)。

一個給定的查詢，對應(yīng)多種可能的處理策略。策略不同，訪問磁盤的次數(shù)相差很大，甚至相差幾個數(shù)量級。查詢代價的度量對于大型數(shù)據(jù)庫系統(tǒng)而言，在磁盤上存取數(shù)據(jù)的代價通常是最重要的代價，可以通過傳輸磁盤塊數(shù)以及搜索磁盤次數(shù)來度量。使用tT表示傳輸一塊數(shù)據(jù)的平均耗時，tS表示搜索一次磁盤的平均定位時間(包括搜索時間加旋轉(zhuǎn)時間)。則一個傳輸b塊并作s次磁盤搜索的操作將耗時b*tT+s*tS

毫秒(ms)寫磁盤塊的代價通常是讀磁盤塊的2倍執(zhí)行計(jì)劃所需掛鐘時間用于代價估算的統(tǒng)計(jì)信息相關(guān)的統(tǒng)計(jì)信息主要包括：

nr：關(guān)系r中的元組數(shù)目。

br：用于存儲關(guān)系r所有元組的塊數(shù)目。

sr：關(guān)系r中一個元組的大小。fr：關(guān)系r的塊因子，即一個物理塊中能存放的關(guān)系r的元組數(shù)目。V(A,r)：關(guān)系r中屬性A所具有的不同值的數(shù)目，該數(shù)目與∏A(r)的大小相同。若A為關(guān)系r的碼，則V(A,r)=nr。SC(A,r)：關(guān)系r關(guān)于屬性A的選擇度，表示在屬性A上滿足某個等值條件（假設(shè)至少有一條記錄滿足該等值條件）的平均記錄數(shù)。用于代價估算的統(tǒng)計(jì)信息fi:索引i的內(nèi)節(jié)點(diǎn)的平均扇出,適用于樹結(jié)構(gòu)索引,如B+樹HTi:索引i的層數(shù)—即高度對于關(guān)系r上A屬性的平衡樹索引(如B+-樹),HTi=logfi(V(A,r))對于散列索引,HTi

為1LBi:索引i的底層索引塊數(shù)—即索引葉子層的塊數(shù)查詢代價估計(jì)舉例查詢實(shí)例:求選修2號課程的學(xué)生姓名SQL表示:selectSnamefromStudents,SCwhereStudents.Sno=SC.SnoandCno=‘2’;數(shù)據(jù)庫模式的樣例Students(Sno,Sname,Ssex,Sage,Sdept)SC(Sno,Cno,Grade)假定學(xué)生-課程數(shù)據(jù)庫中有1000個學(xué)生記錄，10000個選課記錄其中選修2號課程的選課記錄為50個可能的語句翻譯結(jié)果

Q1=πSname(σStudent.Sno=SC.Sno∧Sc.Cno='2'(Student×SC)) Q2=πSname(σSc.Cno='2'(StudentSC)) Q3=πSname(StudentσSc.Cno='2'(SC))硬盤的數(shù)據(jù)以何種形式被加載到內(nèi)存中？內(nèi)存是否足夠大？主要代價？查詢代價估計(jì)snosnamessexsagesdeptsnocnogradeStudentsSC硬盤/外存

查詢處理的過程snosnamessexsagesdeptsnocnogradeStudentsSC硬盤/外存第1步:加載數(shù)據(jù)10個Students元組10個Students元組10個Students元組10個Students元組10個Students元組100個SC元組第2步:內(nèi)存中進(jìn)行關(guān)系操作第3步:輸出最終結(jié)果;或產(chǎn)生臨時結(jié)果,寫回硬盤,重復(fù)1-2步第1步:加載數(shù)據(jù)內(nèi)存（DBMS駐留）Q1代價估計(jì)

Q1關(guān)系代數(shù)語法樹

1、笛卡爾集生產(chǎn)硬盤到內(nèi)存：讀取的總塊數(shù)

＋=100+2000=2100塊假設(shè)每秒讀寫20塊,則花費(fèi)105s連接后的元組數(shù)為103×104=107。設(shè)每塊能裝10個元組，則寫出這些塊要用106/20=5×104s10個Students元組10個Students元組10個Students元組10個Students元組10個Students元組100個SC元組Q1代價估計(jì)

Q1關(guān)系代數(shù)語法樹

2、選擇操作

依次讀入連接后的元組（107個），按照選擇條件選取滿足要求的記錄假定內(nèi)存處理時間忽略。讀取中間文件花費(fèi)的時間(同寫中間文件一樣)需5×104sQ1代價估計(jì)

Q1關(guān)系代數(shù)語法樹

3.投影操作把第2步的結(jié)果在Sname上作投影輸出，得到最終結(jié)果執(zhí)行查詢的總時間≈105+2×5×104≈105s（所有內(nèi)存處理時間均忽略不計(jì)）Q2代價估計(jì)1、自然連接執(zhí)行自然連接，讀取Student和SC表的策略不變，總的讀取塊數(shù)仍為2100塊，花費(fèi)105s；自然連接的結(jié)果比第一種情況大大減少，為104個；

寫出這些元組時間為104/10/20=50s；Q2代價估計(jì)2、選擇運(yùn)算讀取中間文件塊104個元組，執(zhí)行選擇運(yùn)算，花費(fèi)時間為104/10/20=50s。3、投影輸出總的執(zhí)行時間

≈105+50+50≈205s索引代價估計(jì)Q3=πSname(StudentσSc.Cno='2'(SC))假如SC表的Cno字段上有索引第一步只需讀取Cno=‘2’的元組(50個)存取的索引塊和SC中滿足條件的數(shù)據(jù)塊大約總共3～4塊若Student表在Sno上也有索引第二步也不必讀取所有的Student元組因?yàn)闈M足條件的SC記錄僅50個，涉及最多50個Student記錄讀取Student表的塊數(shù)也可大大減少總的存取時間將進(jìn)一步減少到數(shù)秒

查詢代價的優(yōu)化把代數(shù)表達(dá)式Q1變換為Q2，即有選擇和連接操作時，先做選擇操作，這樣參加連接的元組就可以大大減少，這種優(yōu)化是代數(shù)優(yōu)化在索引中SC表的選擇操作算法有全表掃描和索引掃描2種方法，經(jīng)過初步估算，索引掃描方法較優(yōu)，這種優(yōu)化是物理優(yōu)化問題數(shù)據(jù)庫模式的樣例Students(Sno,Sname,Ssex,Sage,Sdept)SC(Sno,Cno,Grade)假定學(xué)生-課程數(shù)據(jù)庫中有1000個學(xué)生記錄，10000個選課記錄其中選修