第6章查詢處理和優(yōu)化-閱讀頁
2024-11-13 15:07本頁面
【正文】 足連接條件的元組就進(jìn)行連接并且作為結(jié)果輸出。 R S = R (n個(gè) ) S (m個(gè) ) i j 嵌套循環(huán)算法 /*設(shè) R有 n個(gè)元組， S有 m個(gè)元組 */ i:=1,j:=1。 j := j + 1 } j:=1,i:=i+1 } T為 R和 S連接的結(jié)果 R為外關(guān)系（ outer relation） , S為內(nèi)關(guān)系（ inner relation）。則 R每次 I/O取 PR個(gè)元組，可改進(jìn)上述算法，使 S掃描一次可以與 R的 PR個(gè)元組比較，那么 S的掃描次數(shù)為 bR=[n/PR] 。若將其中的 nB1塊作為外關(guān)系緩沖塊， 1塊作為內(nèi)關(guān)系緩沖塊 。 問題： 增加外關(guān)系 R的緩沖塊（每次多取幾塊 R的數(shù)據(jù)）或增加內(nèi)關(guān)系 S的緩沖塊都能減少 I/O次數(shù)。還是以 S為外關(guān)系、 R為內(nèi)關(guān)系所需 I/O次數(shù)更少？作為外層循環(huán)的關(guān)系，有什么要求？ 應(yīng)將占用物理塊少的關(guān)系，作為外關(guān)系！ 2).利用索引或散列尋找匹配元組法 在嵌套循環(huán)法中，內(nèi)關(guān)系上要做多次順序掃描， 若內(nèi)關(guān)系上有合適的存取路徑（連接屬性上的索引散列等） ，可以避免內(nèi)關(guān)系上的順序掃描，以減少 I/O次數(shù)。 內(nèi)關(guān)系的連接屬性上有簇集索引時(shí)，索引對減少連接所需 I/O次數(shù)的作用最明顯。 跳過 2 1 3 2 3 3 5 3 7 6 8 7 跳過 跳過 算法： R按屬性 A排序 /*設(shè) R有 n個(gè)元組 */ S按屬性 B排序 /*設(shè) S有 m個(gè)元組 */ i?1,j?1。 /*輸出 R(i)和 S中除 S(j)外 的其他元組所組成的連接元組 */ l?j+1。 l?l+1。 While(k?n) and (R(k)[A]=S(j)[B]) do{輸出 R(k),S(j) 至 T。} i?i+1,j?j+1。符合連接條件的元組必然在同一通中（ 注意：同一桶中的元組未必都滿足連接條件 ）。 關(guān)鍵在于建立一個(gè)供連接用的散列文件。 建立散列文件需要對 R、 S各掃描一次，且關(guān)系 R和S一般不會對連接屬性進(jìn)行簇集。 如何減少 I/O次數(shù) ? 掃描 R和 S時(shí)，取出 ?A(R)、 ?B(S)， 附在相應(yīng)的 tid后，連接時(shí)以桶為單位，按 ?A(R)=?B(S)找出匹配元組的 tid對。 連接方法的啟發(fā)式規(guī)則 1）兩個(gè)關(guān)系都已按連接屬性排序，則優(yōu)先用排序歸并法； 兩個(gè)關(guān)系中已有一個(gè)關(guān)系按連接屬性排序，另一個(gè)關(guān)系較 小，也可先對未排序關(guān)系按連接屬性排序，再用排序歸并 法。 3）不具備上述條件且關(guān)系較小，可用嵌套循環(huán)法。 投影操作的實(shí)現(xiàn) 一般與選擇、連接同時(shí)進(jìn)行，無需附加的 I/O開銷。 消除重復(fù)元組可以用排序或散列等方法 。 用排序法消除重復(fù)元組 對關(guān)系 R的每個(gè)元組 t， 生成 t[投影屬性集 ]，并存于 T’中； /* T’ 是未消除重復(fù)元組的投影結(jié)果 */ If 投影屬性集 含有 R的主鍵 then T?T’ else{T’按所有屬性排序； i?1,j?2。 while T’(i)= T’(j) do j?j+1。 } } 集合操作 常用集合操作：笛卡爾乘積、并、交、差等。 笛卡爾乘積將兩個(gè)關(guān)系的元組無條件地互相拼接， 一般用嵌套循環(huán)法實(shí)現(xiàn)，做起來很費(fèi)時(shí)，結(jié)果要比參與運(yùn)算的關(guān)系大的多。同時(shí)檢查桶中有無重復(fù)元組。 組合操作 有時(shí)，多個(gè)操作組合起來同時(shí)進(jìn)行，如投影和選擇操作組合起來執(zhí)行（消除重復(fù)元組另外單獨(dú)進(jìn)行），可提高效益。 R S 1 2 1? 2? 假設(shè)連接用嵌套循環(huán)法， R為外關(guān)系， S為內(nèi)關(guān)系， R的選擇、投影可在掃描 R時(shí)執(zhí)行， S的選擇、投影可在首次掃描 S時(shí)執(zhí)行，并將選擇、投影的結(jié)果存入臨時(shí)文件，之后各輪只需掃描臨時(shí)文件即可。 結(jié)束語 在執(zhí)行前進(jìn)行優(yōu)化稱為 靜態(tài)優(yōu)化 ，只能利用統(tǒng)計(jì)數(shù)據(jù)，有時(shí)不一定準(zhǔn)。只能利用統(tǒng)計(jì)數(shù)據(jù)，有時(shí)不一定準(zhǔn)。
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1