pulaaa數(shù)據(jù)庫6章(編輯修改稿)
2024-08-31 09:47 本頁面
【文章內(nèi)容簡介】 ? 實現(xiàn)關(guān)系代數(shù)操作的算法 ? 將單個操作算法結(jié)合起來形成一個對表達式的完整求值 ? 如何實現(xiàn)查詢優(yōu)化，即如何尋求一個具有最低代價的執(zhí)行計劃。 關(guān)系 DBS的查詢處理－代價度量 ? 代價通常是利用回答查詢所需的時間來度量的。 ? 很多因素會影響查詢時間 ? 磁盤存取 , CPU, 網(wǎng)絡(luò)連接等 ? 通常磁盤存取是最耗時的部分 , 并且容易估算 , 主要考慮 . ? Number of seeks * averageseekcost ? Number of blocks read * averageblockreadcost ? Number of blocks written * averageblockwritecost ? 寫的代價大于讀的代價 ? 寫以后需要回讀以確保正確的寫 關(guān)系 DBS的查詢處理－代價度量 ? 簡化起見，僅使用 number of block 從磁盤傳送塊的數(shù)目作為代價的度量。 ? 代價依賴于內(nèi)存緩沖區(qū)的大小 ? 更多內(nèi)存降低磁盤存取次數(shù) ? 可用內(nèi)存數(shù)與 OS 其它進程相關(guān) , 難以事先確定 ? 一般使用最壞估計 , 假設(shè)可用內(nèi)存最小時的情況。 ? 是實際模型的簡化 ? 忽略了順序和隨機讀寫的區(qū)別 ? 忽略了 CPU的代價 ? 忽略了寫到磁盤的代價。 關(guān)系 DBS的查詢處理－表達式求值 ? 求整個表達式樹的方法 ? 實化視圖 : 產(chǎn)生每個表達式的結(jié)果，將其實化（存儲）到磁盤上。重復(fù)執(zhí)行。 ? 流水線技術(shù) : 當一個操作還在執(zhí)行的時候，就將元組傳遞給其父操作。 ? 流水線方法比實化視圖方法廉價，當并不一定總是可行，例如 sort, hashjoin；此外，實化視圖的結(jié)果可被重復(fù)利用。 ? 為什么要查詢優(yōu)化？ ? 例 : Student表有 l000個學(xué)生記錄，每人平均選 10門課程， SC表共有 1000*10=l0000個選課記錄。 （統(tǒng)計信息）。 要求 : 查學(xué)生“王林”所選課程的成績在 85分以上的課程號 。 ? SELECT Cno ? FROM S， SC ? WHERE = AND Sname=‘ 王林’ AND Grade 85 ； ? 等價的關(guān)系代數(shù)表示： ? ① ∏ Cno(σ F1 ∧F2 ∧F3 ( S SC ) ) ? ② ∏Cno(σ F2 ∧ F3 ( S ? SC ) ) ? ③ ∏Cno(σ F2 (S) ? σ F3 (SC) ) 條件 F1 條件 F2 條件 F3 分析： 哪種效率高？ ? 關(guān)系 DBS的查詢優(yōu)化 關(guān)系 DBS的查詢優(yōu)化 ? ① ∏Cno(σ F1 ∧ F2 ∧ F3 ( S SC ) ) ? ② ∏Cno(σ F2 ∧ F3 ( S ? SC ) ) ? ③ ∏Cno(σ F2 (S) ? σ F3 (SC) ) ?① 先在兩表上做 ，產(chǎn)生 1000*10000=107個連接記錄，再在其上進行先 σ后 ∏操作。其基本運算的次數(shù)為： 3*107。 ?②先在兩個表上做 ? ，產(chǎn)生 1000*10=104個連接記錄，再在其上進行先 σ后 ∏操作。其基本運算的次數(shù)為： 107+2*104。 ?③先分別在兩個表上做 σ,再 做 ? ，產(chǎn)生 1*10=10個連接記錄，再在其上進行 ∏ 。其基本運算的次數(shù)為： 104+103+*101。 ?連接時間復(fù)雜度為： ① O(107) ② O(104) ③ O(101) 關(guān)系 DBS的查詢優(yōu)化 ? 1. 查詢優(yōu)化概述 ? 一個給定查詢有多種可選擇的求值方法 ? 等價表達式 ? 一個操作有若干不同算法 ? 一個查詢求值方法的好壞帶來的代價差別可能是巨大的 ? 例如 : 執(zhí)行 r X s 后續(xù)選擇 = 比執(zhí)行一個同樣條件的自然連接慢得多 ? 需要估計操作的代價 ? 非常依賴于數(shù)據(jù)庫必須維護的關(guān)系的統(tǒng)計信息 ? 例如元組數(shù) , 連接屬性的不同值的數(shù)目 , 等等 . ? 需要對中間結(jié)果估計統(tǒng)計信息以便對復(fù)雜表達式計算代價 關(guān)系 DBS的查詢優(yōu)化 ? 對一個表達式的查詢計值方案的生成涉及幾個步驟 : 利用 等價規(guī)則 將一個表達式轉(zhuǎn)換成另一個等價的表達式 . (Annotate)結(jié)果表達式以得到其他查詢計劃 估計代價 選擇最廉價的計劃 ? 整個過程稱為 基于代
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號-1