數(shù)據(jù)庫概論第十一章 查詢處理

數(shù)據(jù)庫概論第十一章查詢處理目錄查詢處理簡介統(tǒng)計數(shù)據(jù)代價估計算子實(shí)現(xiàn)SQL提示簡單示例R(A,B,C)S(C,D,E)select B,Dfrom R,Swhere R.A=“c”

and S.E=2and R.C=S.C

R A B C S C D E a 1 10 10 x 2 b 1 20 20 y 2 c 2 10 30 z 2 d 2 35 40 x 1 e 3 45 50 y 3Answer BD 2x如何執(zhí)行該查詢？笛卡爾積-選擇-投影方案一 B,D

sR.A=“c”S.E=2R.C=S.C

X R SB,D[

sR.A=“c”S.E=2R.C=S.C(RXS)]RXS R.A R.B R.C S.C S.D S.E a 1 10 10 x 2 a 1 10 20 y 2 . . C 2 10 10 x 2 . .Bingo!Gotone...如何執(zhí)行該查詢？ B,D

sR.A=“c”

sS.E=2 R S方案二

R SABC s(R) s(S) CDEa110ABCCDE 10x2b120 c21010x220y2c210 20y230z2d235 30z240x1e34550y3

如何執(zhí)行該查詢？使用R.A和S.C上的索引使用R.A的索引選擇R.A=“c”的元組對每個找到的元組的R.C值,使用S.C上的索引查找S中匹配的元組消除S中S.E2的元組連接匹配的R,S元組，投影B,D屬性方案三

R SABC

CDEa110 10x2b120 20y2c210 30z2d235 40x1e34550y3

ACI1I2=“c”<c,2,10><10,x,2>check=2?output:<2,x>各種訪問方法R(A,B,C,P)表掃描select*fromR無序聚簇索引掃描createclusteredindexcidx1onR(P)select*fromR各種訪問方法無序覆蓋非聚簇索引掃描 createindexidx_AonR(A) selectAfromR各種訪問方法有序聚簇索引掃描 select*fromR orderbyP (索引碎片）各種訪問方法有序覆蓋非聚簇索引掃描 selectA,PfromR orderbyA各種訪問方法非聚簇索引查找+有序局部掃描+Lookupsselect*fromRwhereAbetween10and20(10000)各種訪問方法聚簇索引查找+有序局部掃描 select*fromR whereP='2002-12-0400:00:00.000'各種訪問方法索引交集

createindexidx_AonR(A), createindexidx_BonR(B) selectA,B,CfromR whereA<100andB='C0000005794'查詢處理查詢處理是指從數(shù)據(jù)庫中提取數(shù)據(jù)的一系列活動。主要包括：將用高層數(shù)據(jù)庫語言表示的查詢語句翻譯為能在文件系統(tǒng)這一物理層次上實(shí)現(xiàn)的表達(dá)式為優(yōu)化查詢而進(jìn)行各種轉(zhuǎn)換查詢的實(shí)際執(zhí)行輸入：SQL語句輸出：滿足查詢條件的數(shù)據(jù)查詢處理步驟

分析查詢選擇邏輯查詢計劃選擇物理計劃SQL查詢執(zhí)行計劃語法分析樹邏輯查詢計劃樹物理查詢計劃樹查詢優(yōu)化查詢優(yōu)化：對一個給定的查詢，從多種可能執(zhí)行方式中選擇出最有效率的作為查詢執(zhí)行計劃高效的執(zhí)行計劃有兩方面的衡量標(biāo)準(zhǔn)使中間結(jié)果最小化采用盡可能好的操作算法基于代價的方法和啟發(fā)式方法查詢優(yōu)化基于代價的方法(cost-based)生成所有可能的侯選計劃，通過統(tǒng)計信息和存取路徑確定每一計劃中的各個操作的代價和綜合代價，最后選擇代價最小的一個優(yōu)化代價較大啟發(fā)式方法(rule-based)主要是代數(shù)優(yōu)化，依據(jù)關(guān)系代數(shù)的等價變換做一些邏輯變換假定因素太多，優(yōu)化的代價雖小，但優(yōu)化的準(zhǔn)確程度較差兩種方法結(jié)合起來使用：利用啟發(fā)式方法盡量減少侯選計劃，利用基于代價的方法準(zhǔn)確地確定執(zhí)行計劃關(guān)系代數(shù)表達(dá)式的優(yōu)化將選擇運(yùn)算盡可能移向葉節(jié)點(diǎn)合并可能的投影操作將投影運(yùn)算盡可能移向葉節(jié)點(diǎn)關(guān)系代數(shù)表達(dá)式的等價規(guī)則各種結(jié)合律、分配律、交換律基于規(guī)則的優(yōu)化示例createtabletest(col1unique,col2)selectcol1,sum(col2)groupbycol1系統(tǒng)并不執(zhí)行分組操作查詢代價查詢處理對各種資源的使用情況磁盤存取（簡化為磁盤塊傳送數(shù)）CPU時間通信開銷一個重要的影響因素：主存中緩沖區(qū)的大小M最好的情形，所有的數(shù)據(jù)可以讀入到緩沖區(qū)中最壞的情形，緩沖區(qū)只能容納數(shù)目不多的數(shù)據(jù)塊代價估算訪問方法估計代價（邏輯讀的數(shù)量）表掃描表所占用的全部數(shù)據(jù)頁的數(shù)量聚簇索引索引的高度＋要掃描的頁的數(shù)量（要掃描的頁的數(shù)量＝滿足條件的行的數(shù)量/每個數(shù)據(jù)頁所包含的行的數(shù)量）堆上的非聚簇索引索引的高度＋葉結(jié)點(diǎn)所指的頁面數(shù)＋滿足條件的行的數(shù)量（可能所有的行均不在同一頁中，所以要得到一行就必須要一次邏輯讀）。由于相同的數(shù)據(jù)頁經(jīng)常要讀取多次（從緩沖區(qū)中讀?。赃@樣邏輯讀的數(shù)量將比表的頁面數(shù)要多聚簇索引上的非聚簇索引索引的高度＋葉結(jié)點(diǎn)所指的頁面數(shù)＋（滿足條件的行的數(shù)量×搜索一個聚簇索引碼的代價）非聚簇覆蓋索引索引的高度＋索引的葉結(jié)點(diǎn)所占用的索引頁（滿足條件的行數(shù)/每個葉頁面包含的行數(shù)）。這種方式并不需要訪問數(shù)據(jù)頁，因為所需的信息都已經(jīng)包含在索引的碼值中了。統(tǒng)計信息關(guān)系R的統(tǒng)計信息T(R):R中的元組數(shù)S(R)

:R中每個元組的字節(jié)數(shù)B(R):R中所有元組所占據(jù)的塊數(shù)V(R,A):R的屬性A上的唯一值的個數(shù)f(R):每個塊上的R中元組的最大數(shù)目索引i的統(tǒng)計信息HT(i):索引的層數(shù)LB(i):索引葉結(jié)點(diǎn)的塊數(shù)統(tǒng)計信息createstatisticsmy_statonR(A)select*fromsys.statsdbccshow_statistics('R','my_stat') withhistogram基本運(yùn)算的實(shí)現(xiàn)每一個基本的代數(shù)運(yùn)算都有多種不同的實(shí)現(xiàn)算法，適用于不同的情況等值條件，范圍條件數(shù)據(jù)是聚集的，數(shù)據(jù)是非聚集的相關(guān)屬性上有索引，相關(guān)屬性上沒有索引執(zhí)行代價不同選擇運(yùn)算全表掃描方法：依次訪問表的每一個塊，對于每一個元組，測試它是否滿足選擇條件。代價：B(R)

如果是碼查找，B(R)/2缺點(diǎn)：效率低優(yōu)點(diǎn)：對關(guān)系的存儲方式?jīng)]有要求，無需索引適用于任何選擇條件選擇運(yùn)算索引掃描條件：表在選擇條件的屬性上建有索引。方法：訪問索引，根據(jù)索引項的指示去訪問數(shù)據(jù)元組。有序索引：索引項按搜索碼值排序無序索引：索引項不按搜索碼值排序主索引：索引順序與文件中記錄的物理順序相同輔助索引：索引順序與文件中記錄的物理順序不同選擇運(yùn)算等值比較選擇σA＝v（r）利用有序主索引在B+樹索引中找到相應(yīng)的葉結(jié)點(diǎn)，其中包含指向滿足該等值條件的記錄的一個或多個指針。(滿足條件的記錄在一個塊或相鄰的多個塊中)代價：I/O操作次數(shù)等于B+樹的高度，加上包含具有搜索碼值的記錄的磁盤塊數(shù)選擇運(yùn)算利用有序輔助索引在B+樹索引中找到相應(yīng)的葉結(jié)點(diǎn)，其中包含指向滿足該等值條件的記錄的一個或多個指針。(滿足條件的記錄可能在不相鄰的多個塊中)代價：I/O操作次數(shù)等于B+樹的高度，加上檢索到的記錄數(shù)目選擇運(yùn)算利用無序索引通過計算散列函數(shù)找到相應(yīng)的桶，在桶中檢索到滿足該等值條件的一條或多條記錄代價：I/O操作次數(shù)等于到桶的定位，加上存儲桶所包含的塊數(shù)選擇運(yùn)算非等值比較選擇σA>v（r）利用有序主索引在索引中查找v值以檢索出滿足條件A＝v的首條記錄。從該元組開始到文件尾進(jìn)行文件掃描返回所有滿足該條件的元組代價：I/O操作次數(shù)等于B+樹的高度，加上包含滿足搜索條件的記錄的磁盤塊數(shù)選擇運(yùn)算利用有序輔助索引在索引中查找v值以檢索出滿足條件A＝v的首個索引條目，從該索引條目直至最大值索引條目提供了指向滿足條件的記錄的指針，根據(jù)指針逐個取實(shí)際記錄代價：I/O操作次數(shù)等于B+樹的高度，加上滿足搜索條件的記錄數(shù)目排序原因SQL查詢可以指定對輸出進(jìn)行排序關(guān)系運(yùn)算的某些操作，如連接運(yùn)算，排序后實(shí)現(xiàn)高效對于可放進(jìn)內(nèi)存的關(guān)系，使用如快排序之類的技術(shù)。對不能放進(jìn)內(nèi)存的關(guān)系，使用外排序排序內(nèi)排序當(dāng)數(shù)據(jù)集小于可用內(nèi)存時，采用快速排序算法快速排序的思想來源于分治策略。將數(shù)據(jù)塊劃分為兩個序列，第一個序列的值小于第二個序列，在兩個序列中按照遞歸排序的思想再次進(jìn)行上述的劃分，這樣直到?jīng)]有辦法劃分為止外排序創(chuàng)建有序段＋N路歸并所有的輸入數(shù)據(jù)最初分成許多有序的歸并段文件，然后不斷歸并成許多更大的歸并段文件，直到剩下一個文件為止排序第一階段，建立多個排序的歸并段文件i=o；repeat 讀入M塊關(guān)系數(shù)據(jù)或剩下的不足M塊的數(shù)據(jù)； 在內(nèi)存中對關(guān)系的這一部分進(jìn)行排序； 將排好序的數(shù)據(jù)寫到歸并段文件Ri中； i=i+1；until到達(dá)關(guān)系的末尾排序第二階段，對歸并段文件進(jìn)行歸并為N個歸并段文件Ri各分配一頁內(nèi)存緩沖頁，分別讀入一數(shù)據(jù)塊repeat 在所有的緩沖頁中按序挑選第一個元組； 把該元組作為輸出寫出，并且將它從緩沖區(qū)刪除； if任何一個歸并段文件Ri的緩沖頁為空并且沒有到達(dá)文件末尾 then讀入該歸并段文件的下一塊到相應(yīng)的緩沖頁中；until所有的緩沖頁為空排序刪除重復(fù)刪除重復(fù)元組可通過散列或排序?qū)崿F(xiàn).排序后，重復(fù)元組將相鄰，保留一個，刪除其余優(yōu)化：在外歸并排序中，刪除重復(fù)元組可以在序段生成和中間結(jié)果歸并階段進(jìn)行散列的情況類似–

重復(fù)元組將進(jìn)入相同桶投影的實(shí)現(xiàn)方法：在每個元組上執(zhí)行投影，再進(jìn)行重復(fù)元組刪除.連接運(yùn)算重要的運(yùn)算，多種不同的實(shí)現(xiàn)算法。嵌套循環(huán)連接塊嵌套循環(huán)連接索引嵌套循環(huán)連接歸并連接散列連接嵌套循環(huán)連接計算連接r

?

sforeachtuple

trinrdobegin foreachtuplets

insdobegin

測試元組對(tr,ts)是否滿足連接條件 如果是,將tr

?ts

加入到結(jié)果中

endendr

稱為連接的外關(guān)系,s

稱為內(nèi)關(guān)系不需要索引,可用于任何連接條件塊嵌套循環(huán)連接

foreachblockBrof

rdobegin foreachblockBsofsdobegin foreachtupletr

inBr

dobegin foreachtuplets

inBs

dobegin

檢查(tr,ts)是否滿足連接條件 如果是,將tr

?

ts

加入結(jié)果

end end end end嵌套循環(huán)連接算法代價估算T(R1)=10,000T(R2)=5,000S(R1)=S(R2)=1/10塊B(R1)=1000B(R2)=500可用內(nèi)存=101塊嵌套循環(huán)連接算法代價估算Cost:

T(R1)T(R2)+T(R1)=10,0005,000+10,000=50,010,000I/Os

或:

T(R2)T(R1)+T(R2)=5,00010,000+5,000=50,005,000I/Os在外層循環(huán)中使用較小的關(guān)系代價略小塊嵌套循環(huán)連接算法代價估算Cost:B(R1)B(R2)+B(R1)=1,000500+1,000=501,000I/Os

或:B(R2)B(R1)+B(R2)=5001,000+500=500,500I/Os在外層循環(huán)中使用較小的關(guān)系代價略小嵌套循環(huán)連接算法的改進(jìn)內(nèi)存使用Read100blocksofR1ReadallofR2(using1block)+joinRepeatuntildone例：B(R1)=1,000B(R2)=500Cost:ForeachR1chunkReadchunk:100I/OsReadR2:500I/OsTotal=10chunksx(100+500)=6,000I/Os或Total=5chunksx(100+1,000)=5,500I/Os在外層循環(huán)中使用較小的關(guān)系代價略小索引嵌套循環(huán)連接如果滿足下列條件,索引查找可以代替文件掃描是等值連接或自然連接在內(nèi)關(guān)系的連接屬性上存在索引可以僅僅為計算連接而構(gòu)造一個索引對外關(guān)系r的每個元組tr，利用索引查找內(nèi)關(guān)系s的與tr滿足連接條件的元組歸并連接在當(dāng)前R和S的塊的前端查找連接屬性的最小值如果這個值在另一個關(guān)系的前部沒有出現(xiàn)，那么就刪除具有這個值的元組否則，找出兩個關(guān)系中的這個值的所有的元組，如果需要，從排序的R或者S中讀取塊，直到不再有其他的元組進(jìn)行連接，輸出和這個值相關(guān)的所有得到的結(jié)果元組如果一個關(guān)系在內(nèi)存中已經(jīng)沒有要考慮的元組了，那么就重新裝載為這個關(guān)系而設(shè)定的緩沖區(qū)歸并連接(1)ifR1andR2notsorted,sortthem(2)i

1;j1; While(i

T(R1))(jT(R2))do ifR1{i}.C=R2{j}.CthenOutputTuples elseifR1{i}.C>R2{j}.Cthenjj+1 elseifR1{i}.C<R2{j}.Ctheni

i+1歸并連接ProcedureOutput-Tuples While(R1{i}.C=R2{j}.C)(i

T(R1))do [jj

j;while(R1{i}.C=R2{jj}.C)(jj

T(R2))do [outputpairR1{i},R2{jj};

jj

jj+1]

i

i+1] 歸并連接 R1.C R2.C 10 5 20 20 20 20 30 30 40 30 50 52 ijxxjjxxxxxxxxxFinished散列連接適用于自然連接和等值連接基本思想將兩個關(guān)系按連接屬性值劃分成有相同散列函數(shù)值的元組集合關(guān)系r在一個散列劃分中的元組只需要與關(guān)系s在對應(yīng)的劃分中的元組相比較在r和s的每一對劃分中進(jìn)行索引嵌套循環(huán)連接（散列索引）散列連接Hashfunctionh,range0kBucketsforR1:G0,G1,...GkBucketsforR2:H0,H1,...HkAlgorithm(1)HashR1tuplesintoGbuckets(2)HashR2tuplesintoHbuckets(3)Fori=0tokdo matchtuplesinGi,Hibuckets散列連接541231381114243589hash:mod4R1 BucketsR2

4，84，8，125，95，1321433，11各種連接策略比較如果一個連接輸入很?。ū热绮坏?0行），而另一個連接輸入很大而且已在其連接列上創(chuàng)建索引，則索引嵌套循環(huán)是最快的連接操作如果兩個連接輸入很大，并已在二者連接列上排序（連接列上有索引），則合并連接是最快的連接操作哈希連接可以處理很大的、未排序的非索引輸入如果兩個連接輸入都很大，而且這兩個輸入的大小差不多，則預(yù)先排序的合并連接提供的性能與哈希連接相似。然而，如果兩個輸入的大小相差很大，則哈希連接操作通?？斓枚嗪喜⑦B接和哈希連接只能用于等值連接，對于非等值連接，只能用嵌套循環(huán)連接多表連接N個表可能的連接種類有N!個SQLServer對少于或等于4個的表連接采用驗證全部組合的方法，對于超過4個的表連接，以4個表為一組進(jìn)行驗證ABCDEF6個表，先求出其任意4個表組合中代價最小的，不妨設(shè)為BCDF，則表B作為最外層表，剩余5個表ACDEF，再求出其任意4個表組合中代價最小的，不妨設(shè)為CDEF，則表C作為次外層表，最后按通常方法確定剩余表的最佳連接順序，假設(shè)為DEFA，則最后表連接順序為BCDEFA集合運(yùn)算用相同的散列函數(shù)對兩個關(guān)系進(jìn)行劃分，由此得到各個劃分，對關(guān)系r的一個劃分建立內(nèi)存中的hash索引，然后針對每一個劃分進(jìn)行以下的步驟：并把S中相應(yīng)劃分中的元組加入以上的hash索引中，條件是元組不在hash索引中。把hash索引中的元組加入到結(jié)果中交對S中相應(yīng)劃分中的每一個元組，檢索hash索引，若它出現(xiàn)在其中，就將該元組寫入結(jié)果差對關(guān)系s相應(yīng)劃分中的每一個元組，檢索hash索引，若它出現(xiàn)在其中，就將它從hash索引中刪除。將hash索引中剩余的元組加入結(jié)果中去重用排序的方法創(chuàng)建歸并段文件時可以發(fā)現(xiàn)重復(fù)元組，并在將歸并段文件寫回磁盤之前去除重復(fù)元組，從而減少塊傳輸次數(shù)歸并時再去除剩余的重復(fù)元組用散列的方法基于整個元組上的一個散列函數(shù)對關(guān)系進(jìn)行劃分。每個分劃被讀入內(nèi)存，建立內(nèi)存中的散列索引建立散列索引時，只有不在