第十章基本的查询处理与最佳化精选文档.ppt

《第十章基本的查询处理与最佳化精选文档.ppt》由会员分享，可在线阅读，更多相关《第十章基本的查询处理与最佳化精选文档.ppt（40页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第十章基本的查询处理与最佳化Copyright 黃三益 2003 資料庫核心理論與實務1本讲稿第一页，共四十页黃三益2007資料庫的核心理論與實務第三版10-2資料庫程式的執行資料庫程式的執行 通常SQL的敘述都是由程式執行所產生，但交由DBMS來處理 DBMS看到的是一串SQL敘述 本讲稿第二页，共四十页黃三益2007資料庫的核心理論與實務第三版10-3資料庫程式的部分程式碼 建立資料庫連結物件 1.set conn=Server.CreateObject(ADODB.Connection)開啟資料庫連結2.conn.Open onlinedb3.query=SELECT*FROM prod

2、uct4.Set rs=conn.Execute(query)5.while not rs.EOF下達查詢並下達查詢並取得結果取得結果一筆一筆一筆一筆取出結果取出結果本讲稿第三页，共四十页黃三益2007資料庫的核心理論與實務第三版10-4SQL敘述的處理流程 本讲稿第四页，共四十页黃三益2007資料庫的核心理論與實務第三版10-5練習10-1考慮圖10-2，如果第4行的SQL指令在檢查時發現錯誤，會有什麼後果？Ans:此時該SQL指令便不會執行，也因此rs裡不會有值。所以不會執行WHILE迴圈 本讲稿第五页，共四十页黃三益2007資料庫的核心理論與實務第三版10-6SQL查詢樹 一顆SQL查詢

3、樹是用來表達一種執行方案每一葉節點記錄查詢所用到的每一資料表每一中間節點記載處理的動作。標準的處理動作如關聯代數裡的運算子SELECT nameFROM Product,AuthorWHERE pName=系統分析理論與實務 AND Product.pNo=Author.pNo;本讲稿第六页，共四十页黃三益2007資料庫的核心理論與實務第三版10-7SQL查詢樹（Cont.)查詢樹的執行次序是由下而上、由左至右上例的執行方式如下Temp1=pName=系統分析理論與實務(Product);Temp2=Temp1 Temp1.pNo=Author.pNo Author;Result=name(T

4、emp2);SQL剖析器所產生的查詢樹是最簡單的查詢樹，稱為初始查詢樹查詢最佳化模組會將初始查詢樹轉換成較有效率的查詢樹 本讲稿第七页，共四十页黃三益2007資料庫的核心理論與實務第三版10-8SQL查詢樹（Cont.)從SQL查詢句建立初始查詢樹FROM子句裡的每一個資料表是一個葉節點。葉節點用集合乘法（卡迪森乘積）當中間節點兩兩串連起來。加上一個SELECT()的中間節點，以WHERE子句當作其運算。加上一個PROJECT()的根節點，以SELECT子句當作其運算 SELECT nameFROM Product,AuthorWHERE pName=系統分析理論與實務 AND Product

5、.pNo=Author.pNo;本讲稿第八页，共四十页黃三益2007資料庫的核心理論與實務第三版10-9初始查詢樹本讲稿第九页，共四十页黃三益2007資料庫的核心理論與實務第三版10-10SQL查詢樹（Cont.)初始查詢樹最佳化的轉換步驟將SELECT的動作往下移，盡量接近葉節點 本讲稿第十页，共四十页黃三益2007資料庫的核心理論與實務第三版10-11SQL查詢樹（Cont.)將條件較嚴格的SELECT中間節點盡量往左邊移 本讲稿第十一页，共四十页黃三益2007資料庫的核心理論與實務第三版10-12SQL查詢樹（Cont.)將相鄰的中間節點 和 中間節點合併成一個 中間節點 本讲稿第十二页

6、，共四十页黃三益2007資料庫的核心理論與實務第三版10-13SQL查詢樹（Cont.)將PROJECT的動作往下移，盡量接近葉節點 本讲稿第十三页，共四十页黃三益2007資料庫的核心理論與實務第三版10-14練習10-2 找出黃三益所瀏覽過單價超過500元的商品資訊的最佳化查詢本讲稿第十四页，共四十页黃三益2007資料庫的核心理論與實務第三版10-15本讲稿第十五页，共四十页黃三益2007資料庫的核心理論與實務第三版10-16查詢成本的預估指標 查詢樹的每一中間節點，實作的方式可能有數種，到底該採取哪一種？沒有哪一種處理方式必然可以得到比較有效率的運算對於一個查詢句，現代的DBMS於是採用成

7、成本預估本預估（Cost estimate）的方式來決定該採取哪一種處理方式 查詢最佳化模組試圖計算出和比較它們的成本 本讲稿第十六页，共四十页黃三益2007資料庫的核心理論與實務第三版10-17何謂運算成本何謂運算成本何謂成本：執行時間硬碟的存取成本 大部分DBMS的瓶頸CPU的計算成本主記憶體DBMS的瓶頸 網路的通訊成本分散式DBMS的成本 佔大部分時間佔大部分時間本讲稿第十七页，共四十页黃三益2007資料庫的核心理論與實務第三版10-18資料表和索引的相關符號資料表的相關數據 r：資料表裡的記錄筆數r Product=100,000 b：資料表所佔的資料頁數bProduct=5000

8、bfr：每一資料頁可容納幾筆記錄rProductbProduct=bfrProduct=20 索引的相關數據 x：B+-tree的層數 xunitPrice=3 bI1：B+-tree裡葉節點的個數bI1unitPrice=500 d：不同索引值的個數dcatalog=100,dSEX=2 參考下頁圖9-6本讲稿第十八页，共四十页黃三益2007資料庫的核心理論與實務第三版10-19本讲稿第十九页，共四十页黃三益2007資料庫的核心理論與實務第三版10-20基本SELECT的處理方式 SELECT條件裡只有單一屬性 catalog=Book ProductunitPrice500 Product

9、pNo=b30999 Product三種處理方式（SL）資料頁循序搜尋（SI）利用索引結構（參考圖9-6）（SIC）利用群聚索引結構 本讲稿第二十页，共四十页黃三益2007資料庫的核心理論與實務第三版10-21假設有unitPrice的群聚索引，參考下頁圖10-7CREATE INDEX I3ON Product(unitPrice)CLUSTER;利用該索引結構來處理unitPrice500 Product 非常有效率利用該索引結構找到包含unitPrice500 的資料頁指標到該資料頁和以下資料頁找出所有記錄 本讲稿第二十一页，共四十页黃三益2007資料庫的核心理論與實務第三版10-22本

10、讲稿第二十二页，共四十页黃三益2007資料庫的核心理論與實務第三版10-23SELECT的選擇幅度選擇幅度 SELECT的選擇幅度即是查詢結果的預估資料筆數，以s表示catalog=BookProduct dcatalog=100，rProduct=100,000s=rProduct/dcatalog=1000 pNo=b30999Products=1 unitPrice 500Product s=rProduct/2=50,000 本讲稿第二十三页，共四十页黃三益2007資料庫的核心理論與實務第三版10-24練習10-3考慮圖9-6的索引結構，要列出所有unitPrice500的Produc

11、t記錄，請問需造訪哪些索引頁？會造訪哪些資料頁？Ans:索引頁：n1,n3,n8,n9資料頁：p15,p3,p9本讲稿第二十四页，共四十页黃三益2007資料庫的核心理論與實務第三版10-25練習10-4考慮圖10-7的索引結構，要列出所有unitPrice500的Product記錄，請問需造訪哪些索引頁？會造訪哪些資料頁？Ans:索引頁：n1,n3,n8資料頁：p2,p3本讲稿第二十五页，共四十页黃三益2007資料庫的核心理論與實務第三版10-26複合SELECT的處理方式 SELECT條件裡包括一個以上的基本子條件，這些子條件用AND或OR連結起來 catalog=Book AND unit

12、Price500 Productcatalog=Book OR unitPrice500 Product有以下的四種作法（SL）：資料頁循序搜尋（SSI）：單一索引結構搜尋（參考圖9-6）（SMI）：多索引結構搜尋（SCI）：複合索引結構搜尋假設有一多屬性值索引多屬性值索引：（catalog,unitPrice）參考下頁圖9-7 本讲稿第二十六页，共四十页黃三益2007資料庫的核心理論與實務第三版10-27複合SELECT的處理方式(Cont.)CREATE INDEX I2ON Product(catalog ASC,unitPrice DESC);catalog=Book AND unit

13、PriceaR（SL）資料頁循序搜尋 bR（SI）利用索引結構搜尋xA-1+（SIC）利用群聚索引結構，A上有建置一群聚索引xA+本讲稿第三十二页，共四十页黃三益2007資料庫的核心理論與實務第三版10-33範例三範例三假設rProduct=100,000，bProduct=5000（因此bfr Product=20），xunitPrice=3，bI1unitPrice=1000，計算unitPrice 500Product的成本如下(SL):bProduct=5000(SI):xunitPrice-1 =25005000050502(SIC):xunitPrice+=325002503（假設

14、unitPrice為群聚索引）本讲稿第三十三页，共四十页黃三益2007資料庫的核心理論與實務第三版10-34範例四範例四假設rProduct=100,000，bProduct=5000（因此bfrProduct=20），有三個索引：catalog,unitPrice，和（catalog,unitPrice）。xcatalog=2，dcatalog=100（因此scatalog=1000），bI1catalog=100，xunitPrice=3，bI1unitPrice=1000，xcatalog,unitPrice=4，bI1catalog,unitPrice=2000，這三個索引皆非群聚索引

15、。計算catalog=Book AND unitPrice 500Product的成本(SL):bProduct=5000(SSI):這裡有兩個索引可以使用使用catalog索引：1002（參考範例二）使用unitPrice索引：50502（參考範例三）本讲稿第三十四页，共四十页黃三益2007資料庫的核心理論與實務第三版10-35範例四範例四(Cont.)(SMI):根據catalog索引取得記錄指標共需花費成本xcatalog1 =2根據unitPrice索引取得記錄指標共需花費成本xunitPrice 1 =2+500=502取這些記錄指標的交集可在上一步驟裡一併處理，故成本為0 選擇幅度

16、為scatalog,unitPrice=500總成本為2+502+0+500=1004 本讲稿第三十五页，共四十页黃三益2007資料庫的核心理論與實務第三版10-36範例四範例四(Cont.)(SCI):由上述（SMI）的推論，我們知道scatalog,unitPrice=500，所以成本為xcatalog,unitPrice1 scatalog,unitPrice=41 10+500513本讲稿第三十六页，共四十页黃三益2007資料庫的核心理論與實務第三版10-37練習11-1在範例四的（SSI）中，利用catalog索引比利用unitPrice索引的成本低許多，你可以因此得到什麼結論嗎？A

17、ns:選擇幅度小的屬性之索引成本較低。以本例來說，catalog=Book的選擇幅度為1000，而unitPrice500的選擇幅度為50,000。本讲稿第三十七页，共四十页黃三益2007資料庫的核心理論與實務第三版10-38外部排序的運算 有些查詢句要求結果要排序SELECT*FROM ProductORDER BY unitPrice;排序也有助於某些查詢句的處理（如下一章的JOIN）資料表裡的記錄是位於次記憶體（硬碟）我們需要的是能處理位於次記憶體裡記錄的排序演算法，稱為外部排序法外部排序法 本讲稿第三十八页，共四十页黃三益2007資料庫的核心理論與實務第三版10-39外部排序的運算（Cont)類似Merge Sort先將所有的資料切成數塊，每一塊都可放入主記憶體裡分別作排序排序 再將這些排序好的數塊資料作適當的合併合併成本假設主記憶體裡最多可容納nB個讀入的資料頁 資料被切成bR/nB 個資料塊假設nBbR/nB 資料塊排序總成本：2bR資料塊合併總成本：2bR總成本：4bR本讲稿第三十九页，共四十页黃三益2007資料庫的核心理論與實務第三版10-40外部排序的運算（Cont)成本假設nBbR/nB 資料塊排序總成本：2bR資料塊合併總成本：總成本：2bR+成本通常簡化成本讲稿第四十页，共四十页