【正文】 Silberschatz, Korth and Sudarshan Database System Concepts 3rd Edition Selections Involving Comparisons ? A6 (primary index, parison). The cost estimate is: where c is the estimated number of tuples satisfying the condition. In absence of statistical information c is assumed to be nr/2. ? A7 (secondary index, parison). The cost estimate: where c is defined as before. (Linear file scan may be cheaper if 。 condition is on searchkey of index. ? A3 (primary index on candidate key, equality). Retrieve a single record that satisfies the corresponding equality condition EA3 = HTi + 1 ? A4 (primary index on nonkey, equality) Retrieve multiple records. Let the searchkey attribute be A. ? A5 (equality on searchkey of secondary index). ? Retrieve a single record if the searchkey is a candidate key EA5 = HTi + 1 ? Retrieve multiple records (each may be on a different block) if the searchkey is not a candidate key. EA3 = HTi + SC(A,r) ???????? riA f rASCHTE ),(4169。 each block holds 20 tuples. ? Assume account is sorted on branchname. ? V(branchname,account) is 50 ? 10000/50 = 200 tuples of the account relation pertain to Perryridge branch ? 200/20 = 10 blocks for these tuples ? A binary search to find the first record would take ?log2(500)? = 9 block accesses ? Total cost of binary search is 9 + 10 1 = 18 block accesses (versus 500 for linear scan) ?branchname = “Perryridge”(account) 169。Silberschatz, Korth and Sudarshan Database System Concepts 3rd Edition 任務(wù) : Derby 查詢優(yōu)化器實(shí)現(xiàn)分析 ?任務(wù) : Derby 查詢優(yōu)化器實(shí)現(xiàn)分析 ?參考資料 : ?Derby Optimizer Design ?Derby v10 source code End of Chapter (Extra slides with details of selection cost estimation follow) 169。Silberschatz, Korth and Sudarshan Database System Concepts 3rd Edition 查詢優(yōu)化與物化視圖 ? 重寫查詢以利用物化視圖 : ?有物化視圖 v = r s 可用 ?用戶提交了查詢 r s t ?我們可以重寫查詢?yōu)?v t ?是否這么做取決于兩種選擇的代價(jià)估算 ? 用視圖定義代替物化視圖的使用 : ?有物化視圖 v = r s 可用 , 但是上面無(wú)任何索引 ?用戶提交查詢 ?A=10(v). ?再假設(shè) s 在公共屬性 B上有索引 , r 在屬性 A上有索引 . ?此查詢的最佳方案可能是用 r s 替換 v, 這導(dǎo)致查詢方案 ?A=10(r) s ? 應(yīng)該擴(kuò)展查詢優(yōu)化器以考慮所有上述替代方案并選擇最佳總體方案 169。Silberschatz, Korth and Sudarshan Database System Concepts 3rd Edition 其他操作 ? 集合交 : v = r ? s ?當(dāng)插入一條元組到 r 時(shí)我們檢查它是否存在于 s中 , 如果是則加入到 v 中 ?當(dāng)從 r 刪除一條元組時(shí) , 若它存在于交集中則刪除之 ?更新 s 是對(duì)稱的 ?其他集合操作 (并與差 )以類似方式處理 ? 外連接的處理方式基本與連接相同 , 但需要一些額外工作 169。Silberschatz, Korth and Sudarshan Database System Concepts 3rd Edition 聚合操作 ? count : v = Agcount(B)(r). ?當(dāng)插入元組集合 ir 時(shí) ?對(duì) ir 中的每條元組 r, 若對(duì)應(yīng)分組已經(jīng)存在于 v中 , 我們遞增其計(jì)數(shù) , 否則增加一條新元組 , 其 count = 1 ?當(dāng)刪除元組集合 dr 時(shí) ?對(duì) ir 中的每條元組 , 我們查找 v中的分組 , 并從該組計(jì)數(shù)中減去 1. – 若計(jì)數(shù)變成 0, 從 v 中刪除分組 ? sum: v = Agsum (B)(r) ?我們以類似于計(jì)數(shù)的方式來(lái)維護(hù)總和 , 只是要加 /減 B值而非對(duì)計(jì)數(shù)的加 /減 1 ?另外我們維護(hù)計(jì)數(shù)以便發(fā)現(xiàn)沒(méi)有元組的分組 . 這樣的分組要從 v中刪除 ?不能簡(jiǎn)單的測(cè)試 sum = 0 (why?) ? 為處理 avg, 我們維護(hù) sum 和 count 分別聚合值 , 最后再相除 169。Silberschatz, Korth and Sudarshan Database System Concepts 3rd Edition 選擇和投影操作 ? 選擇 : 考慮視圖 v = ??(r). ?vnew = vold ???(ir) ?vnew = vold ??(dr) ? 投影是更復(fù)雜的操作 ?R = (A,B), 且 r(R) = { (a,2), (a,3)} ? ?A(r) 具有單個(gè)元組 (a). ?如果我們從 r 中刪除元組 (a,2), 我們不能從 ?A(r)中刪除元組 (a), 但是若我們又刪除了 (a,3), 我們就應(yīng)該刪除該元組 169。Silberschatz, Korth and Sudarshan Database System Concepts 3rd Edition 增量視圖維護(hù) ?對(duì)一個(gè)關(guān)系或表達(dá)式的改變 (插入和刪除 )稱為其 差異 ?從 r 中插入和刪除的元組集合記為 ir 及 dr ?為簡(jiǎn)化描述 , 只考慮插入和刪除 ?更新元組替換為先刪除元組再插入更新后元組 ?我們描述當(dāng)給定輸入的改變時(shí) , 如何計(jì)算每個(gè)關(guān)系操作結(jié)果上的改變 ?然后概述如何處理關(guān)系代數(shù)表達(dá)式 169。Silberschatz, Korth and Sudarshan Database System Concepts 3rd Edition 物化視圖維護(hù) ?保持物化視圖相對(duì)基礎(chǔ)數(shù)據(jù)為最新的任務(wù)稱為物化視圖維護(hù) ?物化視圖可通過(guò)每次更新時(shí)重新計(jì)算得到維護(hù) ?更好的選擇是利用 增量視圖維護(hù) ?利用對(duì)數(shù)據(jù)庫(kù)關(guān)系的改變來(lái)計(jì)算物化視圖的改變 , 從而得到更新 169。Silberschatz, Korth and Sudarshan Database System Concepts 3rd Edition Optimizing Nested Subqueries ? Decorrelation is more plicated when ?the nested subquery uses aggregation, or ?when the result of the nested subquery is used to test for equality, or ?when the condition linking the nested subquery to the other query is ?not exists‘, ?and so on. 169。Silberschatz, Korth and Sudarshan Database System Concepts 3rd Edition Optimizing Nested Subqueries In general, SQL queries of the form below can be rewritten as shown ? Rewrite: select … from L1 where P1 and exists (select * from L2 where P2) ? To: create table t1 as select distinct V from L2 where P21 select … from L1, t1 where P1 and P22 ? P21 contains predicates in P2 that do not involve any correlation variables ? P22 reintroduces predicates involving correlation variables, with relations renamed appropriately ? V contains all attributes used in predicates with correlation variables 169。Silberschatz, Korth and Sudarshan Database System Concepts 3rd Edition Optimizing Nested Subqueries ? Correlated evaluation may be quite inefficient since ?a large number of calls may be made to the nested query ?there may be unnecessary random I/O as a result ? SQL optimizers attempt to transform nested subqueries to joins where possible, enabling use of efficient join techniques 169。 such variables are called correlation variables ? . select customername from borrower where exists (select * from depositor where = ) 169。Silberschatz, Korth and Sudarshan Database System Concepts 3rd Edition 查詢優(yōu)化器的結(jié)構(gòu) ?某些查詢優(yōu)化器集成了啟發(fā)式選擇和替換存取方案的生成 ?System R 和 Starburst 基于 SQL嵌套塊概念使用了層次式過(guò)程 ?啟發(fā)式重寫后接基于代價(jià)的連接次序優(yōu)化 ?即使使用了啟發(fā)式 , 基于代價(jià)的查詢優(yōu)化仍然帶來(lái)大量開銷 ?這個(gè)開銷通常被查詢執(zhí)行時(shí)的節(jié)省更多地補(bǔ)償 , 尤其是較慢的磁盤存取數(shù)目的減少 169。Silberschatz, Korth and Sudarshan Database System Concepts 3rd Edition 典型的啟發(fā)式優(yōu)化步驟 1. 分解合取選擇成為一個(gè)單選擇操作序列 (Equiv. rule 1.) 2. 將選擇操作移到查詢樹下方以便盡早執(zhí)行 (Equiv.