第十章基本的查詢(xún)處理與最佳化

第十章基本的查詢(xún)處理與最佳化Copyright黃三益2003資料庫(kù)核心理論與實(shí)務(wù)1第一頁(yè)，共四十頁(yè)，2022年，8月28日黃三益2007資料庫(kù)的核心理論與實(shí)務(wù)第三版10-2資料庫(kù)程式的執(zhí)行

通常SQL的敘述都是由程式執(zhí)行所產(chǎn)生，但交由DBMS來(lái)處理DBMS看到的是一串SQL敘述第二頁(yè)，共四十頁(yè)，2022年，8月28日黃三益2007資料庫(kù)的核心理論與實(shí)務(wù)第三版10-3資料庫(kù)程式的部分程式碼'建立資料庫(kù)連結(jié)物件setconn=Server.CreateObject("ADODB.Connection") '開(kāi)啟資料庫(kù)連結(jié)conn.Open"onlinedb" query="SELECT*FROMproduct"Setrs=conn.Execute(query)whilenotrs.EOF下達(dá)查詢(xún)並取得結(jié)果一筆一筆取出結(jié)果第三頁(yè)，共四十頁(yè)，2022年，8月28日黃三益2007資料庫(kù)的核心理論與實(shí)務(wù)第三版10-4SQL敘述的處理流程第四頁(yè)，共四十頁(yè)，2022年，8月28日黃三益2007資料庫(kù)的核心理論與實(shí)務(wù)第三版10-5練習(xí)10-1考慮圖10-2，如果第4行的SQL指令在檢查時(shí)發(fā)現(xiàn)錯(cuò)誤，會(huì)有什麼後果？Ans:此時(shí)該SQL指令便不會(huì)執(zhí)行，也因此rs裡不會(huì)有值。所以不會(huì)執(zhí)行WHILE迴圈第五頁(yè)，共四十頁(yè)，2022年，8月28日黃三益2007資料庫(kù)的核心理論與實(shí)務(wù)第三版10-6SQL查詢(xún)樹(shù)一顆SQL查詢(xún)樹(shù)是用來(lái)表達(dá)一種執(zhí)行方案每一葉節(jié)點(diǎn)記錄查詢(xún)所用到的每一資料表每一中間節(jié)點(diǎn)記載處理的動(dòng)作。標(biāo)準(zhǔn)的處理動(dòng)作如關(guān)聯(lián)代數(shù)裡的運(yùn)算子SELECTnameFROMProduct,AuthorWHEREpName=‘系統(tǒng)分析理論與實(shí)務(wù)’

ANDProduct.pNo=Author.pNo;第六頁(yè)，共四十頁(yè)，2022年，8月28日黃三益2007資料庫(kù)的核心理論與實(shí)務(wù)第三版10-7SQL查詢(xún)樹(shù)（Cont.)查詢(xún)樹(shù)的執(zhí)行次序是由下而上、由左至右上例的執(zhí)行方式如下Temp1=pName=’系統(tǒng)分析理論與實(shí)務(wù)’

(Product);Temp2=Temp1?Temp1.pNo=Author.pNoAuthor;Result=

name(Temp2);SQL剖析器所產(chǎn)生的查詢(xún)樹(shù)是最簡(jiǎn)單的查詢(xún)樹(shù)，稱(chēng)為初始查詢(xún)樹(shù)查詢(xún)最佳化模組會(huì)將初始查詢(xún)樹(shù)轉(zhuǎn)換成較有效率的查詢(xún)樹(shù)第七頁(yè)，共四十頁(yè)，2022年，8月28日黃三益2007資料庫(kù)的核心理論與實(shí)務(wù)第三版10-8SQL查詢(xún)樹(shù)（Cont.)從SQL查詢(xún)句建立初始查詢(xún)樹(shù)FROM子句裡的每一個(gè)資料表是一個(gè)葉節(jié)點(diǎn)。葉節(jié)點(diǎn)用集合乘法（卡迪森乘積）當(dāng)中間節(jié)點(diǎn)兩兩串連起來(lái)。加上一個(gè)SELECT()的中間節(jié)點(diǎn)，以WHERE子句當(dāng)作其運(yùn)算。加上一個(gè)PROJECT()的根節(jié)點(diǎn)，以SELECT子句當(dāng)作其運(yùn)算SELECTnameFROMProduct,AuthorWHEREpName=‘系統(tǒng)分析理論與實(shí)務(wù)’

ANDProduct.pNo=Author.pNo;第八頁(yè)，共四十頁(yè)，2022年，8月28日黃三益2007資料庫(kù)的核心理論與實(shí)務(wù)第三版10-9初始查詢(xún)樹(shù)第九頁(yè)，共四十頁(yè)，2022年，8月28日黃三益2007資料庫(kù)的核心理論與實(shí)務(wù)第三版10-10SQL查詢(xún)樹(shù)（Cont.)初始查詢(xún)樹(shù)最佳化的轉(zhuǎn)換步驟將SELECT的動(dòng)作往下移，盡量接近葉節(jié)點(diǎn)第十頁(yè)，共四十頁(yè)，2022年，8月28日黃三益2007資料庫(kù)的核心理論與實(shí)務(wù)第三版10-11SQL查詢(xún)樹(shù)（Cont.)將條件較嚴(yán)格的SELECT中間節(jié)點(diǎn)盡量往左邊移第十一頁(yè)，共四十頁(yè)，2022年，8月28日黃三益2007資料庫(kù)的核心理論與實(shí)務(wù)第三版10-12SQL查詢(xún)樹(shù)（Cont.)將相鄰的×中間節(jié)點(diǎn)和σ中間節(jié)點(diǎn)合併成一個(gè)?中間節(jié)點(diǎn)第十二頁(yè)，共四十頁(yè)，2022年，8月28日黃三益2007資料庫(kù)的核心理論與實(shí)務(wù)第三版10-13SQL查詢(xún)樹(shù)（Cont.)將PROJECT的動(dòng)作往下移，盡量接近葉節(jié)點(diǎn)第十三頁(yè)，共四十頁(yè)，2022年，8月28日黃三益2007資料庫(kù)的核心理論與實(shí)務(wù)第三版10-14練習(xí)10-2找出「黃三益」所瀏覽過(guò)單價(jià)超過(guò)500元的商品資訊的最佳化查詢(xún)第十四頁(yè)，共四十頁(yè)，2022年，8月28日黃三益2007資料庫(kù)的核心理論與實(shí)務(wù)第三版10-15第十五頁(yè)，共四十頁(yè)，2022年，8月28日黃三益2007資料庫(kù)的核心理論與實(shí)務(wù)第三版10-16查詢(xún)成本的預(yù)估指標(biāo)查詢(xún)樹(shù)的每一中間節(jié)點(diǎn)，實(shí)作的方式可能有數(shù)種，到底該採(cǎi)取哪一種？沒(méi)有哪一種處理方式必然可以得到比較有效率的運(yùn)算對(duì)於一個(gè)查詢(xún)句，現(xiàn)代的DBMS於是採(cǎi)用成本預(yù)估（Costestimate）的方式來(lái)決定該採(cǎi)取哪一種處理方式查詢(xún)最佳化模組試圖計(jì)算出和比較它們的「成本」第十六頁(yè)，共四十頁(yè)，2022年，8月28日黃三益2007資料庫(kù)的核心理論與實(shí)務(wù)第三版10-17何謂運(yùn)算成本何謂成本：執(zhí)行時(shí)間硬碟的存取成本大部分DBMS的瓶頸CPU的計(jì)算成本主記憶體DBMS的瓶頸網(wǎng)路的通訊成本分散式DBMS的成本佔(zhàn)大部分時(shí)間第十七頁(yè)，共四十頁(yè)，2022年，8月28日黃三益2007資料庫(kù)的核心理論與實(shí)務(wù)第三版10-18資料表和索引的相關(guān)符號(hào)資料表的相關(guān)數(shù)據(jù)r：資料表裡的記錄筆數(shù)rProduct=100,000b：資料表所佔(zhàn)的資料頁(yè)數(shù)bProduct=5000bfr：每一資料頁(yè)可容納幾筆記錄rProduct／bProduct=bfrProduct=20索引的相關(guān)數(shù)據(jù)x：B+-tree的層數(shù)

xunitPrice=3bI1：B+-tree裡葉節(jié)點(diǎn)的個(gè)數(shù)bI1unitPrice=500d：不同索引值的個(gè)數(shù)dcatalog=100,dSEX=2參考下頁(yè)圖9-6第十八頁(yè)，共四十頁(yè)，2022年，8月28日黃三益2007資料庫(kù)的核心理論與實(shí)務(wù)第三版10-19第十九頁(yè)，共四十頁(yè)，2022年，8月28日黃三益2007資料庫(kù)的核心理論與實(shí)務(wù)第三版10-20基本SELECT的處理方式SELECT條件裡只有單一屬性catalog=’Book’ProductunitPrice>500ProductpNo=’b30999’Product三種處理方式（SL）資料頁(yè)循序搜尋（SI）利用索引結(jié)構(gòu)（參考圖9-6）（SIC）利用群聚索引結(jié)構(gòu)第二十頁(yè)，共四十頁(yè)，2022年，8月28日黃三益2007資料庫(kù)的核心理論與實(shí)務(wù)第三版10-21假設(shè)有unitPrice的群聚索引，參考下頁(yè)圖10-7CREATEINDEXI3ONProduct(unitPrice)CLUSTER;利用該索引結(jié)構(gòu)來(lái)處理unitPrice>500Product非常有效率利用該索引結(jié)構(gòu)找到包含unitPrice>500

的資料頁(yè)指標(biāo)到該資料頁(yè)和以下資料頁(yè)找出所有記錄

第二十一頁(yè)，共四十頁(yè)，2022年，8月28日黃三益2007資料庫(kù)的核心理論與實(shí)務(wù)第三版10-22第二十二頁(yè)，共四十頁(yè)，2022年，8月28日黃三益2007資料庫(kù)的核心理論與實(shí)務(wù)第三版10-23SELECT的選擇幅度

SELECT的選擇幅度即是查詢(xún)結(jié)果的預(yù)估資料筆數(shù)，以s表示catalog=’Book’Productdcatalog=100，rProduct=100,000s=rProduct/dcatalog=1000pNo=’b30999’Products=1unitPrice>500Products=rProduct/2=50,000第二十三頁(yè)，共四十頁(yè)，2022年，8月28日黃三益2007資料庫(kù)的核心理論與實(shí)務(wù)第三版10-24練習(xí)10-3考慮圖9-6的索引結(jié)構(gòu)，要列出所有unitPrice>500的Product記錄，請(qǐng)問(wèn)需造訪哪些索引頁(yè)？會(huì)造訪哪些資料頁(yè)？Ans:索引頁(yè)：n1,n3,n8,n9資料頁(yè)：p15,p3,p9第二十四頁(yè)，共四十頁(yè)，2022年，8月28日黃三益2007資料庫(kù)的核心理論與實(shí)務(wù)第三版10-25練習(xí)10-4考慮圖10-7的索引結(jié)構(gòu)，要列出所有unitPrice>500的Product記錄，請(qǐng)問(wèn)需造訪哪些索引頁(yè)？會(huì)造訪哪些資料頁(yè)？Ans:索引頁(yè)：n1,n3,n8資料頁(yè)：p2,p3第二十五頁(yè)，共四十頁(yè)，2022年，8月28日黃三益2007資料庫(kù)的核心理論與實(shí)務(wù)第三版10-26複合SELECT的處理方式SELECT條件裡包括一個(gè)以上的基本子條件，這些子條件用AND或OR連結(jié)起來(lái)catalog=’Book’ANDunitPrice<500Productcatalog=’Book’ORunitPrice<500Product有以下的四種作法（SL）：資料頁(yè)循序搜尋（SSI）：?jiǎn)我凰饕Y(jié)構(gòu)搜尋（參考圖9-6）（SMI）：多索引結(jié)構(gòu)搜尋（SCI）：複合索引結(jié)構(gòu)搜尋假設(shè)有一多屬性值索引：（catalog,unitPrice）參考下頁(yè)圖9-7第二十六頁(yè)，共四十頁(yè)，2022年，8月28日黃三益2007資料庫(kù)的核心理論與實(shí)務(wù)第三版10-27複合SELECT的處理方式(Cont.)CREATEINDEXI2ONProduct(catalogASC,unitPriceDESC);catalog=’Book’ANDunitPrice<500

Product第二十七頁(yè)，共四十頁(yè)，2022年，8月28日黃三益2007資料庫(kù)的核心理論與實(shí)務(wù)第三版10-28練習(xí)10-5：考慮圖9-7的（catalog,unitPrice）索引結(jié)構(gòu)，要列出所有catalog=‘Book’ANDunitPrice=500的Product記錄，請(qǐng)問(wèn)需造訪哪些索引頁(yè)？Ans:n1,n2,n6第二十八頁(yè)，共四十頁(yè)，2022年，8月28日黃三益2007資料庫(kù)的核心理論與實(shí)務(wù)第三版10-29SELECT處理方式的成本推估A=aR

（SL）資料頁(yè)循序搜尋case1:A為R的關(guān)聯(lián)鍵：（1+bR）/2case2:A不為R的關(guān)聯(lián)鍵：bR

（SI）利用索引結(jié)構(gòu)搜尋，A上建有一B+-treecase1:A為R的關(guān)聯(lián)鍵：xA+1case2:A不為R的關(guān)聯(lián)鍵：xA－1＋＋sA

（SIC）利用群聚索引結(jié)構(gòu)搜尋，A上有建置一群聚索引xA+

＋sA

第二十九頁(yè)，共四十頁(yè)，2022年，8月28日黃三益2007資料庫(kù)的核心理論與實(shí)務(wù)第三版10-30範(fàn)例一：假設(shè)rProduct=100,000，bProduct=5000，bfrProduct=20，xpNo=3，計(jì)算pNo=’b30999’Product的成本如下（請(qǐng)注意pNo為Product關(guān)聯(lián)的主鍵）(SL):(1+bProduct)/22500(SI):xpNo+1=3+1=4(SIC):xpNo+1=3+1=4

第三十頁(yè)，共四十頁(yè)，2022年，8月28日黃三益2007資料庫(kù)的核心理論與實(shí)務(wù)第三版10-31範(fàn)例二假設(shè)rProduct=100,000，bProduct=5000

（因此bfrProduct=20)，xcatalog=2，dcatalog=100（因此scatalog=1000），bI1catalog=100，計(jì)算catalog=’Book’Product的成本如下：(SL):bProduct=5000(SI):xcatalog－1

＋＋scatalog =2－1＋1＋1000 =1002(SIC):xcatalog+=2+50=52（假設(shè)catalog為群聚索引）第三十一頁(yè)，共四十頁(yè)，2022年，8月28日黃三益2007資料庫(kù)的核心理論與實(shí)務(wù)第三版10-32SELECT處理方式的成本推估(Cont.)A>aR（SL）資料頁(yè)循序搜尋bR

（SI）利用索引結(jié)構(gòu)搜尋xA-1+

+（SIC）利用群聚索引結(jié)構(gòu)，A上有建置一群聚索引xA+第三十二頁(yè)，共四十頁(yè)，2022年，8月28日黃三益2007資料庫(kù)的核心理論與實(shí)務(wù)第三版10-33範(fàn)例三假設(shè)rProduct=100,000，bProduct=5000

（因此bfrProduct=20），xunitPrice=3，bI1unitPrice=1000，計(jì)算unitPrice>500Product的成本如下(SL):bProduct=5000(SI):xunitPrice-1＋＋

=2＋500＋50000＝50502(SIC):xunitPrice+=3＋2500＝2503（假設(shè)unitPrice為群聚索引）第三十三頁(yè)，共四十頁(yè)，2022年，8月28日黃三益2007資料庫(kù)的核心理論與實(shí)務(wù)第三版10-34範(fàn)例四假設(shè)rProduct=100,000，bProduct=5000（因此bfrProduct=20），有三個(gè)索引：catalog,unitPrice，和（catalog,unitPrice）。xcatalog=2，dcatalog=100（因此scatalog=1000），bI1catalog=100，xunitPrice=3，bI1unitPrice=1000，xcatalog,unitPrice=4，bI1catalog,unitPrice=2000，這三個(gè)索引皆非群聚索引。計(jì)算catalog=’Book’ANDunitPrice>500Product的成本(SL):bProduct=5000(SSI):這裡有兩個(gè)索引可以使用使用catalog索引：1002（參考範(fàn)例二）使用unitPrice索引：50502（參考範(fàn)例三）第三十四頁(yè)，共四十頁(yè)，2022年，8月28日黃三益2007資料庫(kù)的核心理論與實(shí)務(wù)第三版10-35範(fàn)例四(Cont.)(SMI):根據(jù)catalog索引取得記錄指標(biāo)共需花費(fèi)成本xcatalog－1＋=2

根據(jù)unitPrice索引取得記錄指標(biāo)共需花費(fèi)成本xunitPrice－1

＋=2+500=502取這些記錄指標(biāo)的交集可在上一步驟裡一併處理，故成本為0選擇幅度為scatalog,unitPrice==500總成本為2+502+0+500=1004第三十五頁(yè)，共四十頁(yè)，2022年，8月28日黃三益2007資料庫(kù)的核心理論與實(shí)務(wù)第三版10-36範(fàn)例四(Cont.)(SCI):由上述（SMI）的推論，我們知道scatalog,unitPrice=500，所以成本為xcatalog,unitPrice－1＋＋scatalog,unitPrice=4－1＋10+500＝513第三十六頁(yè)，共四十頁(yè)，2022年，8月28日