【文章內(nèi)容簡介】 each tuple ts in s do begin 測試元組對(duì) (tr ,ts) 是否滿足聯(lián)接條件 ? 如果是 , 將 tr ? ts 加入到結(jié)果中 end end ? r 稱為聯(lián)接的 外關(guān)系 , s 稱為 內(nèi)關(guān)系 ? 不需要索引 , 可用于任何聯(lián)接條件 ? 代價(jià)高 , 因?yàn)橐獧z查兩個(gè)關(guān)系的每一對(duì)元組 169。Silberschatz, Korth and Sudarshan Database System Concepts 嵌套循環(huán)聯(lián)接 169。Silberschatz, Korth and Sudarshan Database System Concepts 嵌套循環(huán)聯(lián)接 ? 在最壞情況下 , 內(nèi)存只能存放每個(gè)關(guān)系的一個(gè)塊 , 則求值代價(jià)為 nr ? bs + br 次磁盤存取 . ? 如果較小關(guān)系可完全放入內(nèi)存 , 則利用其作為內(nèi)關(guān)系，代價(jià)減少到 br + bs 次磁盤存取 ? 假設(shè)最壞情況下的內(nèi)存可用性 , 則求值代價(jià)為 ?以 depositor 為外關(guān)系時(shí) , 5000 ? 400 + 100 = 2,000,100 次磁盤存取 . ?以 customer 為外關(guān)系時(shí) , 1000 ? 100 + 400 = 1,000,400 次磁盤存取 . ? 若較小關(guān)系 (depositor) 可完全放入內(nèi)存 , 則求值代價(jià)為 500次磁盤存取 ? 塊嵌套循環(huán)算法更可取 169。Silberschatz, Korth and Sudarshan Database System Concepts 塊嵌套循環(huán)聯(lián)接 ? 這是嵌套循環(huán)聯(lián)接的變種 , 內(nèi)關(guān)系的每個(gè)塊與外關(guān)系的每個(gè)塊配對(duì) 169。Silberschatz, Korth and Sudarshan Database System Concepts 塊嵌套循環(huán)聯(lián)接 ? 最壞情況下求值代價(jià) : br ? bs + br 次塊存取 ?內(nèi)關(guān)系的每個(gè)塊要為外關(guān)系的每個(gè) 塊 (而不是每個(gè) 元組 )讀一次 ? 最好情況下 : br + bs 次塊存取 ? 對(duì)嵌套循環(huán)和塊嵌套循環(huán)算法的改進(jìn) : ?在塊嵌套循環(huán)中 , 使用 M 2 個(gè)磁盤塊作為外關(guān)系的存儲(chǔ)塊 , 其中 M = 內(nèi)存大小 (以塊計(jì) )。 利用剩下的兩個(gè)塊作為內(nèi)關(guān)系和輸出的緩沖區(qū) ? Cost = ?br / (M2)? ? bs + br ?若等值聯(lián)接屬性構(gòu)成內(nèi)關(guān)系的鍵 , 則在第一次匹配之后可終止 ?內(nèi)循環(huán)交替向前和向后掃描 , 以利用保留在緩沖區(qū)中的塊 (采用 LRU 替換策略時(shí) ) ?如果可能 , 利用內(nèi)關(guān)系上的索引 (見下一幻燈片 ) 169。Silberschatz, Korth and Sudarshan Database System Concepts 索引嵌套循環(huán)聯(lián)接 ? 如果滿足下列條件 , 索引查找可以代替文件掃描 ?等值聯(lián)接或自然聯(lián)接 ?在內(nèi)關(guān)系的聯(lián)接屬性上存在索引 ?可以僅僅為計(jì)算聯(lián)接而構(gòu)造一個(gè)索引 ? 對(duì)外關(guān)系 r 的每個(gè)元組 tr , 利用索引查找內(nèi)關(guān)系 s 的與 tr 滿足聯(lián)接條件的元組 ? 最壞情形 : 緩沖區(qū)空間只夠存放 r 的一頁 , 并且對(duì) r 的每個(gè)元組 , 都在s 上執(zhí)行一次索引查找 ? 聯(lián)接的代價(jià) : br + nr ? c ?其中 c 是查找索引和讀取 s 的所有匹配元組 (對(duì) r 的每條元組 )的代價(jià) ? c 可以求值為利用聯(lián)接條件對(duì) s 做一次選擇的代價(jià) ? 如果在 r 和 s 的聯(lián)接屬性上都存在索引 , 則以元組數(shù)較小的關(guān)系作為外關(guān)系 169。Silberschatz, Korth and Sudarshan Database System Concepts 嵌套循環(huán)聯(lián)接代價(jià) :例 ? 計(jì)算 depositor customer, 以 depositor 作為外關(guān)系 ? 令 customer 在聯(lián)接屬性 customername上具有主 B+樹索引 , 每個(gè)索引節(jié)點(diǎn)包含 20個(gè)索引項(xiàng) ? 由于 customer 有 10,000 個(gè)元組 , 樹的高度為 4, 另外查找實(shí)際數(shù)據(jù)還需一次存取 ? depositor 有 5000個(gè)元組 ? 塊嵌套循環(huán)聯(lián)接的代價(jià) ?假設(shè)最壞情形的內(nèi)存 , 400*100 + 100 = 40,100 次磁盤存取 (隨著內(nèi)存增多可大大減少 ) ? 索引嵌套循環(huán)聯(lián)接的代價(jià) ? 100 + 5000 * 5 = 25,100 次磁盤存取 . ? CPU 代價(jià)可能少于塊嵌套循環(huán)聯(lián)接 169。Silberschatz, Korth and Sudarshan Database System Concepts 歸并連接 1. 將兩個(gè)關(guān)系在連接屬性上排序 (如果還沒有排序的話 ) 2. 歸并已排序關(guān)系來連接之 1. 連接步驟類似于歸并 排序算法的歸并階段 2. 主要不同在于連接屬性中重復(fù)值的處理 — 連接屬性上具有相同值的每一對(duì)都要匹配 3. 詳細(xì)算法在書中 4. 只能用于等值連接和自然連接 169。Silberschatz, Korth and Sudarshan Database System Concepts 歸并 連接 ? 每個(gè)塊只需要讀一次 (假設(shè)對(duì)連接屬性的任何給定值 , 所有元組能放進(jìn)內(nèi)存 ) ? 因此歸并連接的塊存取數(shù)目為 br + bs + 未排序關(guān)系的排序代價(jià) ? 混合歸并連接 : 如果一個(gè)關(guān)系已排序 , 而另一個(gè)在連接屬性上有輔助 B+樹索引 ? 已排序關(guān)系與 B+樹的葉子項(xiàng)歸并 ? 根據(jù)未排序關(guān)系的元組的地址將結(jié)果排序 ? 按物理地址順序掃描未排序關(guān)系并與前面的結(jié)果歸并 , 用實(shí)際元組替換地址 ? 順序掃描比隨機(jī)查找高效 169。Silberschatz, Korth and Sudarshan Database System Concepts HashJoin ? Applicable for equijoins and natural joins ? A hash function h is used to partition tuples of both relations 169。Silberschatz, Korth and Sudarshan Database System Concepts HashJoin 169。Silberschatz, Korth and Sudarshan Database System Concepts HashJoin ? r tuples in ri need only to be pared with s tuples in si ,Need not be pared with s tuples in any other partition, since: ? an r tuple and an s tuple that satisfy the join condition will have the same value for the join attributes ? If that value is hashed to some value i, the r tuple has to be in ri and the s tuple in si 169。Silberschatz, Korth and Sudarshan Database System Concepts HashJoin Algorithm 1. Partition the relation s using hashing function h. When partitioning a relation, one block of memory is reserved as the output buffer for each partition 2. Partition r similarly 3. For each i: (a)Load si into memory and build an inmemory hash index on it using the join attribute. This hash index uses a different hash function than the earlier one h (b)Read the tuples in ri from the disk one by one. For each tuple tr locate each matching tuple ts in si using the inmemory hash index. Output the concatenation of their attributes ?The hashjoin of r and s