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

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

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

查詢代價(jià)估計(jì)

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

包括： 1、將用高層數(shù)據(jù)庫(kù)語(yǔ)言表示的查詢語(yǔ)句翻譯成文件系統(tǒng)這一物理層次上實(shí)現(xiàn)的表達(dá)式； 2、為優(yōu)化查詢進(jìn)行各種轉(zhuǎn)換； 3、查詢的實(shí)際執(zhí)行。查詢處理過(guò)程查詢執(zhí)行計(jì)劃查詢結(jié)果數(shù)據(jù)基于數(shù)據(jù)的統(tǒng)計(jì)分析優(yōu)化器語(yǔ)法分析器和翻譯器執(zhí)行引擎DBMS關(guān)系代數(shù)表達(dá)式查詢分析在數(shù)據(jù)庫(kù)執(zhí)行查詢處理之前，系統(tǒng)先將查詢語(yǔ)句翻譯成可使用的形式。翻譯過(guò)程： 1、語(yǔ)法分析器將查詢翻譯成系統(tǒng)內(nèi)部表示形式； 2、翻譯的同時(shí)進(jìn)行語(yǔ)法檢查； 3、構(gòu)造查詢語(yǔ)句的語(yǔ)法分析樹(shù)； 4、翻譯成關(guān)系代數(shù)表達(dá)式。對(duì)于給出的一個(gè)查詢，一般經(jīng)過(guò)翻譯器翻譯后都會(huì)有多種關(guān)系代數(shù)表達(dá)式與之對(duì)應(yīng)。查詢分析實(shí)例查詢實(shí)例:求選修2號(hào)課程的學(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)換部分：對(duì)于一個(gè)語(yǔ)法樹(shù)，根據(jù)關(guān)系代數(shù)等價(jià)變換規(guī)則，得到所有的等價(jià)的關(guān)系代數(shù)表達(dá)式；物理轉(zhuǎn)換部分：對(duì)于每一個(gè)關(guān)系代數(shù)表達(dá)式，根據(jù)查詢引擎提供的物理操作，找出所有可能的查詢執(zhí)行計(jì)劃。比較和查找：根據(jù)代價(jià)估計(jì)函數(shù)，估計(jì)每一個(gè)查詢執(zhí)行計(jì)劃的代價(jià)，并從中找出代價(jià)最小的查詢執(zhí)行計(jì)劃。優(yōu)化器處理過(guò)程查詢請(qǐng)求等價(jià)變換規(guī)則集邏輯轉(zhuǎn)換物理轉(zhuǎn)換物理操作集查找代價(jià)估計(jì)函數(shù)代價(jià)最小QEP等價(jià)的語(yǔ)法樹(shù)集合等價(jià)的QEP查詢執(zhí)行引擎功能：查詢執(zhí)行引擎為每一個(gè)關(guān)系操作的實(shí)現(xiàn)提供多種物理實(shí)現(xiàn)方法。選擇操作有兩種可能的物理操作：順序掃描和索引掃描連接操作有三種可能的物理操作：嵌套循環(huán)連接、合并連接和散列連接。查詢執(zhí)行引擎還可以提供更多的物理實(shí)現(xiàn)方法。每一種物理實(shí)現(xiàn)方法利用不同的存取路徑（如索引、數(shù)據(jù)的存儲(chǔ)分布、元組的排序等）負(fù)責(zé)產(chǎn)生執(zhí)行查詢的代碼

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

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

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

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

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

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

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

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

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

sr：關(guān)系r中一個(gè)元組的大小。fr：關(guān)系r的塊因子，即一個(gè)物理塊中能存放的關(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上滿足某個(gè)等值條件（假設(shè)至少有一條記錄滿足該等值條件）的平均記錄數(shù)。用于代價(jià)估算的統(tǒng)計(jì)信息fi:索引i的內(nèi)節(jié)點(diǎn)的平均扇出,適用于樹(shù)結(jié)構(gòu)索引,如B+樹(shù)HTi:索引i的層數(shù)—即高度對(duì)于關(guān)系r上A屬性的平衡樹(shù)索引(如B+-樹(shù)),HTi=logfi(V(A,r))對(duì)于散列索引,HTi

為1LBi:索引i的底層索引塊數(shù)—即索引葉子層的塊數(shù)查詢代價(jià)估計(jì)舉例查詢實(shí)例:求選修2號(hào)課程的學(xué)生姓名SQL表示:selectSnamefromStudents,SCwhereStudents.Sno=SC.SnoandCno=‘2’;數(shù)據(jù)庫(kù)模式的樣例Students(Sno,Sname,Ssex,Sage,Sdept)SC(Sno,Cno,Grade)假定學(xué)生-課程數(shù)據(jù)庫(kù)中有1000個(gè)學(xué)生記錄，10000個(gè)選課記錄其中選修2號(hào)課程的選課記錄為50個(gè)可能的語(yǔ)句翻譯結(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))硬盤(pán)的數(shù)據(jù)以何種形式被加載到內(nèi)存中？?jī)?nèi)存是否足夠大？主要代價(jià)？查詢代價(jià)估計(jì)snosnamessexsagesdeptsnocnogradeStudentsSC硬盤(pán)/外存

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

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

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

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

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

2、選擇操作

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

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

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

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

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

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