【正文】 , 使用散列的集合運(yùn)算 : 1. 利用相同的散列函數(shù)劃分兩個(gè)關(guān)系 , 從而創(chuàng)建了 r1, .., rn r0, 和 s1, s2.., sn 2. 如下處理每個(gè)分組 i. ri 讀進(jìn)內(nèi)存后 , 用一個(gè)不同的散列函數(shù)構(gòu)造 ri 上的內(nèi)存散列索引 3. r ? s: 將 si 中的元組加入散列索引 (如果不在其中的話 ). 最后將散列索引中的元組加入到結(jié)果中 4. r ? s: 將 si 中的元組輸出到結(jié)果 , 如果它們已經(jīng)在散列索引中 5. r – s: 對(duì) si 中的每個(gè)元組 , 如果已經(jīng)在散列索引中 , 則從索引中刪除之 . 6. 在 si 之末將散列索引中的剩余元組加到結(jié)果中 169。Silberschatz, Korth and Sudarshan Database System Concepts 其它操作 : 外聯(lián)接 ? 外連接可如下計(jì)算 ?連接后加入填充空值的未參加連接的元組 ?修改連接算法 ? 修改合并連接算法來(lái)計(jì)算 r s ?在 r s中 , 未參加聯(lián)接的元組都在 r – ?R(r s)中 ?修改合并連接算法計(jì)算 r s: 在合并時(shí) , 對(duì)每個(gè)來(lái)自 r 的并且不能匹配 s中任何元組的元組 tr , 輸出 tr 并用空值填充 ?右外連接和完全外連接可類似計(jì)算 ? 修改散列連接算法來(lái)計(jì)算 r s ?如果 r 是探測(cè)關(guān)系 , 輸出 r 中不能匹配的元組并填充空值 ?如果 r 是構(gòu)建關(guān)系 , 探測(cè)時(shí)記錄哪些 r 元組匹配 s 元組 . 在 si 之末輸出無(wú)匹配 r 元組并填充空值 169。Silberschatz, Korth and Sudarshan Database System Concepts Join 研究方法小結(jié) ?建立了數(shù)學(xué)模型，包括 : ?符號(hào)體系， 抓 主要矛盾，以及忽略原則 ?然后分情況，加定語(yǔ)，把問(wèn)題特化，分而治之 ?一次作一個(gè)小問(wèn)題，深入地導(dǎo)出多個(gè)公式 ?真正有用，可以指導(dǎo)實(shí)踐 ? 不怕 有問(wèn)題， 就怕找不到問(wèn)題 ? 只要有問(wèn)題 就可能出成果 169。Silberschatz, Korth and Sudarshan Database System Concepts 表達(dá)式求值 ?迄今為止，我們討論的是單個(gè)運(yùn)算的算法 ?計(jì)算整個(gè)表達(dá)式樹的可選方法 : ?物化 (Materialization): 生成輸入為關(guān)系或已計(jì)算結(jié)果的表達(dá)式的結(jié)果 , 在磁盤上物化 (存儲(chǔ) ), 重復(fù)此過(guò)程 ?流水線化 (Pipelining): 當(dāng)一個(gè)操作正在執(zhí)行中就將部分輸出元組送到父運(yùn)算，子樹結(jié)果傳給父結(jié)點(diǎn) 169。Silberschatz, Korth and Sudarshan Database System Concepts 物化 ? 物化求值 : 從最底層開(kāi)始每次計(jì)算一個(gè)運(yùn)算，將中間結(jié)果物化成臨時(shí)關(guān)系 , 再進(jìn)行下一層運(yùn)算 ? 例如 , 在下圖中計(jì)算并存儲(chǔ) 然后計(jì)算并存儲(chǔ)它與 customer 的聯(lián)接 , 最后計(jì)算 customername上的投影 )(2 5 0 0 a c c o u n tb a l a n c e ??169。Silberschatz, Korth and Sudarshan Database System Concepts 物化 ? 優(yōu)點(diǎn)：物化求值總是可行的 ? 缺點(diǎn)：將結(jié)果寫到磁盤并讀回來(lái)可能代價(jià)很高 ? 前面我們的代價(jià)公式都忽略了將結(jié)果寫到磁盤去的代價(jià) , 故 ?總代價(jià) = 各操作代價(jià)之和 + 中間結(jié)果寫到磁盤的代價(jià) ? 雙緩沖 (Double buffering): 對(duì)每個(gè)操作使用兩個(gè)輸出緩沖區(qū) , 當(dāng)一個(gè)滿的時(shí)候即寫入磁盤 , 同時(shí)使用另一個(gè)輸出 ? 允許磁盤寫與計(jì)算重疊進(jìn)行 , 減少執(zhí)行時(shí)間 169。Silberschatz, Korth and Sudarshan Database System Concepts 流水線 ? 流水線求值 : 同時(shí)計(jì)算多個(gè)運(yùn)算 , 將一個(gè)運(yùn)算的結(jié)果傳到下一個(gè)運(yùn)算 169。Silberschatz, Korth and Sudarshan Database System Concepts 流水線 ?優(yōu)點(diǎn)：比物化廉價(jià)很多，不需要將臨時(shí)關(guān)系存儲(chǔ)到磁盤 ?缺點(diǎn)：有時(shí)流水線不可用，如排序和散列聯(lián)接 ?為了使流水線有效 , 使用能在接受輸入元組的同時(shí)生成輸出元組的求值算法 ?流水線可以兩種方式執(zhí)行 : ?拉式：需求驅(qū)動(dòng) （ 買方市場(chǎng)）有人買，才生產(chǎn) ?推式：生產(chǎn)者驅(qū)動(dòng)（賣方市場(chǎng)）生產(chǎn)出來(lái)，再等買 169。Silberschatz, Korth and Sudarshan Database System Concepts 流水線 ? 在需求驅(qū)動(dòng)或 惰性 (lazy)求值 中 ? 系統(tǒng)從頂層操作重復(fù)請(qǐng)求下一元組 ? 每個(gè)操作向子操作請(qǐng)求下一元組 , 以便輸出它自己的下一元組 ? 在調(diào)用之間 , 操作必須維護(hù) ―狀態(tài) ‖ 以便知道下一步返回什么 ? 每個(gè)操作以 迭代子 的形式實(shí)現(xiàn)下列操作： ? open() ?例如對(duì)文件掃描 : 初始化文件掃描 , 在文件開(kāi)始處存儲(chǔ)指針作為狀態(tài) ?例如對(duì)合并連接 : 對(duì)關(guān)系排序并在已排序關(guān)系開(kāi)始處存儲(chǔ)指針作為狀態(tài) ? next() ?例如對(duì)文件掃描 : 輸出下一元組 , 前移并存儲(chǔ)文件指針 ?例如對(duì)合并連接 : 從前面的狀態(tài)繼續(xù)合并直至找到下一輸出元組 . 保存指針作為迭代子狀態(tài) ? close() 169。Silberschatz, Korth and Sudarshan Database System Concepts 流水線 ? 在生產(chǎn)者驅(qū)動(dòng)或急迫 eager流水線中 ? 操作迫切地產(chǎn)生元組并向上傳送到父操作 ? 在操作之間維護(hù)緩沖區(qū) , 子操作將元組放入緩沖區(qū) , 父操作將元組移出緩沖區(qū) ? 如果緩沖區(qū)滿 , 子操作等待直至緩沖區(qū)有空間 , 然后生成更多的元組 ? 系統(tǒng)調(diào)度在輸出緩沖區(qū)中有空間的操作 , 可以處理更多的輸入元組 169。Silberschatz, Korth and Sudarshan Database System Concepts 流水線的求值算法 ? 某些算法即使獲得了輸入元組也不能輸出結(jié)果，例如合并連接或者散列連接 ? 這導(dǎo)致了將中間結(jié)果寫到磁盤然后讀回 ? 某些算法變種可以在讀入輸入元組時(shí)即時(shí) (on the fly)生成 (至少部分 )結(jié)果 ? 例如 , 混合散列連接即可在讀入內(nèi)存分劃 (分劃 0)中的探測(cè)關(guān)系元組時(shí)生成輸出元組 ? 流水線連接技術(shù) : 修改混合散列連接將兩個(gè)關(guān)系的分劃 0的元組都放入內(nèi)存緩沖區(qū) , 可用時(shí)讀入之 , 輸出兩個(gè)分劃0元組之間的任何匹配作為結(jié)果 ? 當(dāng)新的 r0 元組找到時(shí) , 將它與現(xiàn)存的 s0 元組匹配 , 輸出匹配并保存在 r0中 ? 對(duì)稱地處理 s0 元組 169。Silberschatz, Korth and Sudarshan Database System Concepts 復(fù)雜連接 ? 涉及三個(gè)關(guān)系的連接 : loan depositor customer ? 策略 1： 計(jì)算 depositor customer。 利用其結(jié)果計(jì)算 loan (depositor customer) ? 策略 2：計(jì)算 loan depositor , 再將結(jié)果與 customer 連接 ? 策略 3： 同時(shí)執(zhí)行一對(duì)連接 . 在 loan上為 loannumber 建一索引 , 在 customer 上為 customername 建一索引 ? 對(duì) depositor 中的每個(gè)元組 t , 在 customer 中查找對(duì)應(yīng)的元組 ,在 loan中查找對(duì)應(yīng)的元組 . ? deposit 中每個(gè)元組只檢查一次 ? 策略 3 結(jié)合兩個(gè)操作為一個(gè)特殊目的的操作 , 它比實(shí)現(xiàn)兩個(gè)連接更高效 169。Silberschatz, Korth and Sudarshan Database System Concepts 任務(wù) : Derby 查詢處理實(shí)現(xiàn)分析 ?任務(wù) 1:Derby SQL Parser分析 ?任務(wù) 2:Derby Query Execution分析 ?參考資料 : ?Derby On Disk Page Format ?Derby Type System ?How Things Work ?_apache_derby_impl_store_access_btree ?Intersect amp。 Except Design ?Derby v10 source code End of Chapter