第十章基本的查詢處理與最佳化 資料庫程式的執行 SQL 敘述的處理流程 SQL 查詢樹 基本關聯代數運算子的處理 SELECT 的處理方式和成本 外部排序的處理方式和成本 10-1 資料庫程式的執行 通常 SQL 的敘述都是由程式執行所產生, 但交由 DBMS 來處理 DBMS 看到的是一串 SQL 敘述 10-2 1
資料庫程式的部分程式碼 ' 建立資料庫連結物件 1 set conn = ServerCreateObject("ADODBConnection") ' 開啟資料庫連結 2 connopen "onlinedb" 3 query = "SELECT * FROM product" 4 Set rs = connexecute(query) 5 while not rseof 下達查詢並取得結果 一筆一筆取出結果 10-3 SQL 敘述的處理流程 10-4 2
練習 10-1 考慮圖 10-2, 如果第 4 行的 SQL 指令在檢查時發現錯誤, 會有什麼後果? Ans: 此時該 SQL 指令便不會執行, 也因此 rs 裡不會有值 所以不會執行 WHILE 迴圈 10-5 SQL 查詢樹 一顆 SQL 查詢樹是用來表達一種執行方案 每一葉節點記錄查詢所用到的每一資料表 每一中間節點記載處理的動作 標準的處理動作如關聯代數裡的運算子 SELECT name FROM Product, Author WHERE pname = ` 系統分析理論與實務 ' AND ProductpNo = AuthorpNo; π name ProductpNo = AuthorpNo σ pname = 系統分析理論與實務 Author Product 10-6 3
SQL 查詢樹 (Cont) 查詢樹的執行次序是由下而上 由左至右 上例的執行方式如下 Temp1=σ pname=' 系統分析理論與實務 ' (Product); Temp2= Temp1 Temp1pNo=AuthorpNo Author; Result= π name (Temp2); SQL 剖析器所產生的查詢樹是最簡單的查詢樹, 稱為初始查詢樹 查詢最佳化模組會將初始查詢樹轉換成較有效率的查詢樹 10-7 SQL 查詢樹 (Cont) 從 SQL 查詢句建立初始查詢 樹 FROM 子句裡的每一個資料表是一個葉節點 葉節點用集合乘法 ( 卡迪森乘積 ) 當中間節點兩兩串連起來 加上一個 SELECT(σ) 的中間節點, 以 WHERE 子句當作其運算 加上一個 PROJECT(π) 的根節點, 以 SELECT 子句當作其運算 SELECT name FROM Product, Author WHERE pname = 系統分析理論與實務 AND ProductpNo = AuthorpNo; 10-8 4
初始查詢樹 10-9 SQL 查詢樹 (Cont) 初始查詢樹最佳化的轉換步驟 將 SELECT 的動作往下移, 盡量接近葉節點 10-10 5
SQL 查詢樹 (Cont) 將條件較嚴格的 SELECT 中間節點盡量往左邊移 10-11 SQL 查詢樹 (Cont) 將相鄰的 中間節點和 σ 中間節點合併成一個 中間節點 10-12 6
SQL 查詢樹 (Cont) 將 PROJECT 的動作往下移, 盡量接近葉節點 10-13 練習 10-2 找出 黃三益 所瀏覽過單價超過 500 元的商品資訊的最佳化查詢 π pid, name, pname, unitprice π pid, name, pname, unitprice σ ProductunitPrice>500 AND ProductpNo=BrowsepNo AND BrowsemId = MembermId AND Membername =' 黃三益 ' σ B row sem Id = M em berm Id σ ProductpNo = BrowsepNo σ nam e = ' 黃三益 ' Member Member Product Browse σ ProductunitPrice > 500 Browse Product 10-14 7
π pid, name, pname, unitprice π pid, name, pname, unitprice σ ProductpNo = BrowsepNo ProductpNo = BrowsepNo BrowsemId = MembermId σ ProductunitPrice > 500 σ BrowsemId = MembermId σ ProductunitPrice > 500 Product Product σ name = ' 黃三益 ' Member Browse σ name = ' 黃三益 ' π pid, name, pname, unitprice Member Browse ProductpNo = BrowsepNo BrowsemId = MembermId π pno,pname,unitprice π mid,pid,name Product π pno,mid σ ProductunitPrice > 500 σ name = ' 黃三益 ' Browse Member 10-15 查詢成本的預估指標 查詢樹的每一中間節點, 實作的方式可能有數種, 到底該採取哪一種? 沒有哪一種處理方式必然可以得到比較有效率的運算 對於一個查詢句, 現代的 DBMS 於是採用成本預估 (Cost estimate) 的方式來決定該採取哪一種處理方式 查詢最佳化模組試圖計算出和比較它們的 成本 10-16 8
何謂運算成本 何謂成本 : 執行時間 硬碟的存取成本 大部分 DBMS 的瓶頸 CPU 的計算成本 主記憶體 DBMS 的瓶頸 網路的通訊成本 分散式 DBMS 的成本 佔大部分時間 10-17 資料表和索引的相關符號 資料表的相關數據 r: 資料表裡的記錄筆數 r Product = 100,000 b: 資料表所佔的資料頁數 b Product = 5000 bfr: 每一資料頁可容納幾筆記錄 r Product /b Product = bfr Product = 20 索引的相關數據 x:b + -tree 的層數 x unitprice = 3 bi1:b + -tree 裡葉節點的個數 bi1 unitprice = 500 d: 不同索引值的個數 d catalog = 100, d SEX = 2 參考下頁圖 9-6 10-18 9
n1 450 n2 n3 350 400 500 600 n4 n5 n6 n7 n8 n9 (300,<p3,3>) (350,<p15,3>) (400, <p9,2> ) (450,<p15,2> )(450,<p15,1>) (500,<p3,2>) (500,<p3,1>) (550, <p15,4> ) (600,<p3,4>) (700, <p9,1> ) P3 資料表 Product 第一頁 512 128 256 1024 'b30999, 資料庫理論與實務,500, Book' 'd11222, 任賢齊專輯三,300, CD' 'b20666, OLAP 進階,500, Book' P9 'b10234, 管理資訊,600, Book' 15 'b51111, 電子商務,700, Book' P15 'v00111, 英雄,400, DVD' NULL 'b40555, 系統分析,550, Book' 'd20777, 蔡依林,350, CD' 'v01888, 哈利波特,450, DVD' 'd03333,5566 專輯,450, CD 9 10-19 基本 SELECT 的處理方式 SELECT 條件裡只有單一屬性 σ catalog= Book Product σ unitprice>500 Product σ pno= b30999 Product 三種處理方式 (SL) 資料頁循序搜尋 (SI) 利用索引結構 ( 參考圖 9-6) (SIC) 利用群聚索引結構 10-20 10
假設有 unitprice 的群聚索引, 參考下頁圖 10-7 CREATE INDEX I3 ON Product(unitPrice) CLUSTER; 利用該索引結構來處理 σ unitprice>500 Product 非常有效率 利用該索引結構找到包含 unitprice>500 的資料頁指標 到該資料頁和以下資料頁找出所有記錄 10-21 10-22 11
SELECT 的選擇幅度 SELECT 的選擇幅度即是查詢結果的預估資料筆數, 以 s 表示 σ catalog= Book Product d catalog = 100,r Product = 100,000 s=r Product / d catalog = 1000 σ pno= b30999 Product s=1 σ unitprice > 500 Product s=r Product /2 = 50,000 10-23 練習 10-3 考慮圖 9-6 的索引結構, 要列出所有 unitprice>500 的 Product 記錄, 請問需造訪哪些索引頁? 會造訪哪些資料頁? Ans: 索引頁 :n1, n3, n8, n9 資料頁 :p15, p3, p9 10-24 12
練習 10-4 考慮圖 10-7 的索引結構, 要列出所有 unitprice>500 的 Product 記錄, 請問需造訪哪些索引頁? 會造訪哪些資料頁? Ans: 索引頁 :n1, n3, n8 資料頁 :p2, p3 10-25 複合 SELECT 的處理方式 SELECT 條件裡包括一個以上的基本子條件, 這些子條件用 AND 或 OR 連結起來 σ catalog= Book AND unitprice<500 Product σ catalog= Book OR unitprice<500 Product 有以下的四種作法 (SL): 資料頁循序搜尋 (SSI): 單一索引結構搜尋 ( 參考圖 9-6) (SMI): 多索引結構搜尋 (SCI): 複合索引結構搜尋 假設有一多屬性值索引 :(catalog, unitprice) 參考下頁圖 9-7 10-26 13
複合 SELECT 的處理方式 (Cont) CREATE INDEX I2 ON Product(catalog ASC, unitprice DESC); 'Book', 600 n1 n2 n3 'Book', 550 'Book', 500 'CD', 350 'DVD', 450 n4 n5 n6 n7 n8 n9 ( 'Book', 700, ) ( 'Book', 600, ) ('Book', 550, ) 'Book', 500, ) 'Book', 500, ) ( 'CD', 450, ) ( 'CD', 350, ) σ catalog= Book AND unitprice<500 Product ( 'CD', 300, ) ( 'DVD', 450, ) ( 'DVD', 400, ) 10-27 練習 10-5: 考慮圖 9-7 的 (catalog, unitprice) 索引結構, 要列出所有 catalog = `Book' AND unitprice=500 的 Product 記錄, 請問需造訪哪些索引頁? Ans: n1, n2, n6 10-28 14
SELECT 處理方式的成本推估 σ A=a R (SL) 資料頁循序搜尋 case 1: A 為 R 的關聯鍵 : ( 1+b R )/2 case 2: A 不為 R 的關聯鍵 : b R (SI) 利用索引結構搜尋 +s,a 上建有一 B + A -tree case 1: A 為 R 的關聯鍵 :x A +1 s A case 2: A 不為 R 的關聯鍵 :x A -1+ bi1 A +s rr A (SIC) 利用群聚索引結構搜尋,A 上有建置一群聚索引 s A x A + bfrr 10-29 範例一 : 假設 r Product = 100,000,b Product = 5000,bfr Product = 20,x pno =3, 計算 σ pno= b30999 Product 的成本如下 ( 請注意 pno 為 Product 關聯的主鍵 ) (SL): (1+b Product )/2 2500 (SI): x pno +1=3+1=4 (SIC): x pno +1=3+1=4 10-30 15
範例二 假設 r Product = 100,000,b Product = 5000 ( 因此 bfr Product = 20),x catalog =2,d catalog =100( 因此 s catalog = 1000),bI1 catalog =100, 計算 σ catalog= Book Product 的成本如下 : (SL): b Product =5000 s catalog (SI): x catalog -1 + bi1 catalog +s r catalog Product =2-1 +1+1000 =1002 scatalog (SIC): x catalog + =2+50=52 bfrproduct ( 假設 catalog 為群聚索引 ) 10-31 SELECT 處理方式的成本推估 (Cont) σ A>a R (SL) 資料頁循序搜尋 b R (SI) 利用索引結構搜尋 bi1 A r R x A 1 + + 2 2 (SIC) 利用群聚索引結構,A 上有建置一群聚索引 x A + b R 2 10-32 16
範例三 假設 r Product = 100,000,b Product = 5000 ( 因此 bfr Product = 20),x unitprice =3, bi1 unitprice =1000, 計算 σ unitprice > 500 Product 的成本如下 (SL): b Product =5000 r Product bi1 unitprice 2 (SI): x unitprice 1+ + 2 =2+500+50000=50502 (SIC): x unitprice + 為群聚索引 ) b Product 2 =3+2500=2503 ( 假設 unitprice 10-33 範例四 假設 r Product = 100,000,b Product = 5000( 因此 bfr Product = 20), 有三個索引 :catalog, unitprice, 和 (catalog, unitprice) x catalog =2,d catalog =100( 因此 s catalog = 1000),bI1 catalog =100,x unitprice =3, bi1 unitprice =1000, x catalog,unitprice =4,bI1 catalog,unitprice =2000, 這三個索引皆非群聚索引 計算 σ catalog= Book AND unitprice > 500 Product 的成本 (SL): b Product =5000 (SSI): 這裡有兩個索引可以使用 使用 catalog 索引 : 1002 ( 參考範例二 ) 使用 unitprice 索引 :50502 ( 參考範例三 ) 10-34 17
範例四 (Cont) (SMI): 根據 catalog 索引取得記錄指標共需花費成本 scatalog x catalog -1+ bi1 catalog =2 rproduct 根據 unitprice 索引取得記錄指標共需花費成本 x unitprice -1 + =2+500=502 2 取這些記錄指標的交集 可在上一步驟裡一併處理, 故成本為 0 Product 選擇幅度為 s catalog,unitprice = =500 總成本為 bi1 unitprice 2+502+0+500 = 1004 r d catalog 1 2 10-35 範例四 (Cont) (SCI): 由上述 (SMI) 的推論, 我們知道 s catalog,unitprice =50, 所以成本為 bi1 x catalog,unitprice -1+ =4-1 +10 +500=513 catalog,unitprice s catalog,unitprice r Product +s catalog,unitprice 10-36 18
練習 11-1 在範例四的 (SSI) 中, 利用 catalog 索引比利用 unitprice 索引的成本低許多, 你可以因此得到什麼結論嗎? Ans: 選擇幅度小的屬性之索引成本較低 以本例來說,catalog= Book 的選擇幅度為 1000, 而 unitprice>500 的選擇幅度為 50,000 10-37 外部排序的運算 有些查詢句要求結果要排序 SELECT * FROM Product ORDER BY unitprice; 排序也有助於某些查詢句的處理 ( 如下一章的 JOIN) 資料表裡的記錄是位於次記憶體 ( 硬碟 ) 我們需要的是能處理位於次記憶體裡記錄的排序演算法, 稱為外部排序法 10-38 19
外部排序的運算 (Cont) 類似 Merge Sort 先將所有的資料切成數塊, 每一塊都可放入主記憶體裡分別作排序 再將這些排序好的數塊資料作適當的合併 成本 假設主記憶體裡最多可容納 n B 個讀入的資料頁 資料被切成 b R /n B 個資料塊 假設 n B b R /n B 資料塊排序總成本 :2b R 資料塊合併總成本 : 2b R 總成本 :4b R 10-39 外部排序的運算 (Cont) 成本 假設 n B < b R /n B 資料塊排序總成本 :2b R 資料塊合併總成本 : 2bR log 總成本 :2b R + 2b R log b nb R nb b R 成本通常簡化成 K 2 b R log b R 10-40 20