求Block-nested、Index-nested、Sort Merge三种连接算法的执行代价

查询语句 #

Select count(*) From Student s, Registration r Where s.sno = r.sno

已知条件 #

• Student关系：300个页面，每页100个元组
• Registration关系：900个页面，每页100个元组
• Registration上存在高度为3的B+树
• 可用缓冲页面数：50

需要计算I/O代价的三种算法 #

• 块嵌套循环连接（Block-nested loops join）
• 索引嵌套循环连接（Index-nested loops join）
• 归并排序连接（Sort Merge join）

自行计算结果 #

1. 块嵌套循环连接：300 × 900 = 270,000 I/O操作
2. 索引嵌套循环连接：300 × 3 = 900 I/O操作
3. 归并排序连接：300 + 900 = 1,200 I/O操作

结果验证与修正 #

1. 块嵌套循环连接 #

你的计算错误，误用了简单嵌套循环的公式。块嵌套循环会利用缓冲减少内层关系的扫描次数，正确代价公式为：
外层关系页面数 + (外层关系页面数 / (缓冲页面数 - 2)) × 内层关系页面数
选择较小的Student作为外层关系，代入数据得：
300 + (300 / (50 - 2)) × 900 ≈ 300 + 6×900 = 5700 I/O操作
（注：300/48=6.25，向上取整为7的话代价为6600，实际代价在5700-6600区间内，远小于270000）

2. 索引嵌套循环连接 #

你的计算不完整，忽略了读取Registration数据页的代价。正确代价公式为：
外层关系页面数 + 外层元组数量 × (索引高度 + 匹配元组的页面数)
Student元组总数为300×100=30000个，每个元组通过B+树查找需3次索引I/O，再加上读取匹配数据页的1次I/O（按常规场景计算），总代价为：
300 + 30000×(3+1) = 120300 I/O操作

3. 归并排序连接 #

你的计算遗漏了排序阶段的开销。归并排序连接总代价=排序阶段I/O+连接阶段I/O：

• 排序阶段：缓冲可用作排序的页面数为50-1=49。Student排序代价为2×300×ceil(log_49 300)=2×300×2=1200；Registration排序代价为2×900×ceil(log_49 900)=2×900×2=3600
• 连接阶段：扫描两个已排序关系的代价为300+900=1200
  总代价为1200+3600+1200=6000 I/O操作
  （注：若两个关系已按sno排序，排序代价为0，总代价才是1200，但题目未说明已排序，需包含排序开销）

内容的提问来源于stack exchange，提问作者Bathiudeen