民國115年 高考三級 資訊處理 資料庫應用
第2題
某機構資料庫有以下兩張E 與C 資料表，並存在其關聯： E(SID, CID, Grade)：共60000 筆資料，每個區塊（Block）存50 筆資料。 C(…
題目
某機構資料庫有以下兩張E 與C 資料表，並存在其關聯： E(SID, CID, Grade)：共60000 筆資料，每個區塊（Block）存50 筆資料。 C(CID, Name, Credit)：共600 筆資料，每個區塊（Block）存30 筆資料。 假設該機構系統可用的緩衝區（Buffer）M 共22 頁，並執行下面SQL 語 法： SELECT E.SID, C.Name, E.Grade FROM E JOIN C ON E.CID = C.CID 目前已知關聯式資料庫中，常見的Join 演算法有三種，即Simple Nested Loop Join (SNLJ)、Block Nested Loop Join (BNLJ)與Hash Join，其I/O 成 本分別計算如下： Join 演算法 I/O 成本公式 說明 SNLJ B(R) + |R| × B(S) 對R 每一筆Tuple，掃描整個S BNLJ B(R) + ⌈B(R)/(M-2)⌉× B(S) 以Block 為單位分批載入R，每批掃描一次S；M-2 頁給外層，1 頁給內層，1 頁給輸出 Hash Join 3 × (B(R) + B(S)) 分割階段讀寫各一次，探測階段再讀一次 演算法內符號說明如下：B(R)代表資料表R 的區塊（Block）數，也就是 以R 作為JOIN 運算的驅動表（Driving Table / Outer Table）；|R|代表資料 表R 的資料筆數；M 代表可用緩衝區（Buffer）頁數；S 為要計算的資料 表。 請回答下面問題，並計算下列各演算法的I/O 成本（需列計算過程）： 使用SNLJ 法，以資料表E 為驅動表。（5 分） 使用BNLJ 法，以資料表C 為驅動表。（5 分） 使用Hash Join 法（假設分割後各Partition 可完整放入記憶體）。（5 分） 綜合比較上述三種結果，在本題情境下應選擇那種演算法？說明原 因。（10 分）
參考解答（AI 生成，非官方）
- 一、基本參數推算：區塊數 B(R) = 資料筆數 ÷ 每區塊筆數（向上取整）。B(E) = 60000 ÷ 50 = 1200 個區塊；B(C) = 600 ÷ 30 = 20 個區塊；|E| = 60000 筆、|C| = 600 筆；緩衝區 M = 22 頁，故外層可用頁數 M − 2 = 20 頁（1 頁給內層、1 頁給輸出）。以下 I/O 成本均以「頁（page/block）讀取次數」為單位，暫不計入結果寫出與索引成本。
- 二、SNLJ（以 E 為驅動表）：公式為 B(R) + |R| × B(S)，其中 R = E、S = C。成本 = B(E) + |E| × B(C) = 1200 + 60000 × 20 = 1200 + 1,200,000 = 1,201,200 次 I/O。此法的特性是對外層每一筆 tuple 都重新掃描整個內層表，因此成本與「外層筆數 × 內層區塊數」成正比，在大型資料表上極不經濟。
- 三、BNLJ（以 C 為驅動表）：公式為 B(C) + ⌈B(C)/(M−2)⌉ × B(E)。因 B(C) = 20，M − 2 = 20，故 ⌈20/20⌉ = 1，代表 C 的全部 20 個區塊可一次載入記憶體，內層 E 只需掃描一次。成本 = 20 + 1 × 1200 = 1,220 次 I/O。對照若改以 E 為驅動表，則 ⌈1200/20⌉ = 60，成本為 1200 + 60 × 20 = 2,400，明顯較差，可見小表當外層較有利。
- 四、Hash Join：公式為 3 × (B(R) + B(S))，即分割階段讀一次、寫一次，探測階段再讀一次。成本 = 3 × (1200 + 20) = 3 × 1220 = 3,660 次 I/O。此公式為簡化上限，隱含「分割後各 partition 可完整放入記憶體」的前提；若建置端（build side）整表可放入記憶體，實務上可採記憶體內雜湊表，成本可降至約 B(E) + B(C) = 1,220 次。
- 五、綜合比較與選擇：三者成本為 SNLJ 1,201,200、BNLJ 1,220、Hash Join 3,660（依題目公式），故應選擇「以 C 為驅動表的 BNLJ」。理由：（1）C 僅 20 個區塊，恰可完全放入 M − 2 = 20 頁的外層緩衝，內層 E 僅需完整掃描一次，達到理論下限；（2）SNLJ 因逐筆重掃內層，成本高出約千倍，不可採；（3）Hash Join 公式的 3 次讀寫在小表情境下反而較貴，且需額外記憶體與雜湊建置成本。惟若放寬假設、允許 build side 常駐記憶體，Hash Join 可與 BNLJ 相當（約 1,220），此時可再比較 CPU 與記憶體成本。
AI 依官方試題文字產生的參考解答，非考選部公告答案，內容僅供備考參考。