第十一章进阶的查询处理与最佳化.pptVIP

Copyright 黃三益 2003 資料庫核心理論與實務 第十一章進階的查詢處理與最佳化 JOIN的處理方式和成本推估 PROJECT的處理方式和成本推估 集合運算子的處理方式和成本推估 彙總函數的處理方式和成本推估 多個關聯代數運算子的整合處理方式 實體資料庫設計與微調 JOIN的處理方式 JOIN運算子包括兩個資料表，其運算往往是最耗時的 R ? R.A=S.B S有三種處理方式 （JNL）巢狀迴圈法 假設主記憶體裡有三個資料頁，分別用來容納資料表R，資料表S和資料表Result 每擷取一個R資料頁，就要擷取所有S的資料頁，以便兩兩配對。如下頁圖所示 JOIN的處理方式（Cont.) JOIN的處理方式（Cont.) （JIL）索引迴圈法 利用其中一個匹配屬性的索引結構 JOIN的處理方式（Cont.) （JSM）排序合併法 假設在硬碟裡，兩個資料表的記錄恰好是依照R.A和S.B排序 按次序輪流將R和S分別載入主記憶體一次即可完成將所有R的記錄和相匹配的S記錄結合 JOIN處理方式的成本推估 R ? R.A=S.B S （JNL）巢狀迴圈法 資料表R的載入成本：bR 資料表S的載入成本：bR×bS 因此總成本為bR＋bR×bS （JIL）索引迴圈法 資料表R的載入成本：bR 資料表S和S.B索引的載入成本 case 1: S.B為非群聚索引：rR×(xB+sB) case 2: S.B為群聚索引：rR×(xB+ ) 因此總成本為 case 1: S.B為非群聚索引：bR＋rR×(xB+sB) case 2: S.B為群聚索引：bR＋rR×(xB+ ) JOIN處理方式的成本推估(Cont.) （JSM）排序合併法 資料表R的載入成本：bR 資料表S的載入成本：bS 因此總成本為bR＋bS 如果R和S的記錄並沒有依照R.A和S.B排序，要採用（JSM），則要加上排序的成本 K×（ ） 範例一 假設rProduct = 100,000，bProduct = 5000（因此bfrProduct = 20），rAuthor = 200,000，bAuthor = 500（因此bfrAuthor = 400），有二個索引Product.pNo和Author.pNo，且此二索引皆為群聚索引。xProduct.pNo=3，xAuthor.pNo=3，sAuthor.pNo=5。 考慮以下查詢式的成本 Product ?Product.pNo=Author.pNo Author 範例一 （JNL）： case 1: 以Product為外部迴圈：bProduct＋bProduct×bAuthor=5000＋5000×500=2,505,000 case 2: 以Author為外部迴圈：bAuthor＋bProduct×bAuthor=500＋5000×500=2,500,500 （JIL）： case 1: 利用Product.pNo的索引。由於Product.pNo為主鍵，所以sProduct.pNo=1，因此，成本為bAuthor＋rAuthor×(xProduct.pNo+1)=500＋200000×4=800,500 case 2: 利用Author.pNo的索引。成本為 bProduct＋rProduct×(xAuthor.pNo+1)=5000+100000×(3+1)=405,000。 （JSM）：因為Product.pNo和Author.pNo為群聚索引，可知Product和Author裡的記錄已分別按照Product.pNo和Author.pNo排序。因此成本為 bR＋bS=5000＋500=5,500。 PROJECT的處理方式 允許重複的PROJECT運算子實作方式有兩種 (PL) 資料頁循序搜尋 (PI) 利用索引結構 假設有(catalog, unitPrice)的索引結構 處理以下查詢句只要搜尋該索引結構的葉節點即可 Q4: SELECT catalog, unitPrice FROM Product; 參考下頁圖9-7 練習11-2 考慮上頁圖9-7的索引，若要利用該索引結構來處理以下查詢句 SELECT catalog, unitPrice FROM Product; 請問要造訪哪些硬碟頁？ Ans: n1, n2, n4, n5, n6, n7, n8, n9 PROJECT的處理方式(Cont.) 不允許重複的PROJECT運算子 RESULT = ? 屬性串列(R) SELECT DISTINCT catalog, uni