【正文】 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。Silberschatz, Korth and Sudarshan Database System Concepts 復(fù)雜連接 ? 涉及三個(gè)關(guān)系的連接 : loan depositor customer ? 策略 1： 計(jì)算 depositor customer。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 流水線 ?優(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 物化 ? 優(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 表達(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 其它操作 : 外聯(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 其它操作 : aggregation ? aggregation的實(shí)現(xiàn)方法與重復(fù)元組刪除類似 ?排序或散列可以用來(lái)將同組元組聚到一起 , 然后即可對(duì)每一組應(yīng)用合計(jì)函數(shù) . ?優(yōu)化 : 通過(guò)計(jì)算部分合求值 , 可在序段生成與中間結(jié)果歸并階段合并同組元組 ?對(duì) count, min, max, sum: 保存組中當(dāng)前已找到的元組的合求值 ?當(dāng)合并 count的部分合求值時(shí) , 相加即可 ?對(duì) avg, 保存 sum和 count, 最后求 sum / count 169。Silberschatz, Korth and Sudarshan Database System Concepts 復(fù)雜連接 ? 帶有合取條件的連接 : r ?1? ? 2?... ? ? n s ? 使用嵌套循環(huán) /塊嵌套循環(huán) , 或者 ? 計(jì)算一個(gè)簡(jiǎn)單連接的結(jié)果 r ?i s ? 最終結(jié)果由中間結(jié)果中滿足下列剩余條件的元組組成 ?1 ? . . . ? ?i –1 ? ?i +1 ? . . . ? ?n ? 帶有析取條件的連接 r ?1 ? ?2 ?... ? ?n s ? 使用 嵌套循環(huán) /塊嵌套循環(huán) , 或者 ? 計(jì)算各簡(jiǎn)單連接 r ? i s的結(jié)果中記錄的并集 : (r ?1 s) ? (r ?2 s) ? . . . ? (r ?n s) 169。Silberschatz, Korth and Sudarshan Database System Concepts Hybrid Hash–Join ? Useful when memory sized are relatively large, and the build input is bigger than memory ? Main feature of hybrid hash join: Keep the first partition of the build relation in memory ? . With memory size of 25 blocks, depositor can be partitioned into five partitions, each of size 20 blocks ? Division of memory: ? The first partition occupies 20 blocks of memory ? 1 block is used for input, and 1 block each for buffering the other 4 partitions ? customer is similarly partitioned into five partitions each of size 80。Silberschatz, Korth and Sudarshan Database System Concepts Cost of HashJoin 169。Silberschatz, Korth and Sudarshan Database System Concepts Handling of Overflows ? Hashtable overflow occurs in partition si if si does not fit in memory ? Reasons could be ?Many tuples in s with same value for join attributes ?Bad hash function ? Partitioning is said to be skewed(偏斜 ) if some partitions have significantly more tuples than some others 169。Silberschatz, Korth and Sudarshan Database System Concepts HashJoin algorithm ? The value n and the hash function h is chosen such that each si should fit in memory ? Typically n is chosen as ?bs/M? * f where f is a ―fudge factor‖, typically around ? The probe relation partiti