高考申論題
115年
[資訊處理] 資料庫應用
第 四 題
📖 題組：
某機構資料庫有以下兩張 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 成本（需列計算過程）：
某機構資料庫有以下兩張 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 成本（需列計算過程）：
📝 此題為申論題，共 4 小題
小題 (四)
綜合比較上述三種結果，在本題情境下應選擇那種演算法？說明原因。（10 分）
思路引導 VIP
此題為判斷題，需整合前三小題的計算結果進行論證。
- 先列出前三題結果以供對比：SNLJ = 1,201,200；BNLJ = 1,220；Hash Join = 3,660。
小題 (一)
使用 SNLJ 法，以資料表 E 為驅動表。（5 分）
思路引導 VIP
看到本題，首要是從題目敘述中計算出公式所需的基本參數，然後代入公式：
- 先計算兩個資料表的區塊數 (Block 數)：
小題 (二)
使用 BNLJ 法，以資料表 C 為驅動表。（5 分）
思路引導 VIP
接著處理 BNLJ，並注意題目更改了驅動表：
- 驅動表 R = C，被驅動表 S = E。
小題 (三)
使用 Hash Join 法（假設分割後各 Partition 可完整放入記憶體）。（5 分）
思路引導 VIP
本題只需將資料套用 Hash Join 成本公式。
- 找出公式：
3 × (B(R) + B(S))