数据库算法简单嵌套循环连接

Question

给定关系:

Sailors (sid: integer, sname: string, rating: integer, age: real)
Reserves (sid: integer, bid: integer, day: dates, rname: string)

查询

SELECT  *
FROM   Reserves R, Sailors S
WHERE  R.sid=S.sid

假设:

M pages of R, pR tuples per page (i.e., number of tuples of R = M * pR) 
N pages of S, pS tuples per page (i.e., number of tuples of S = N * pS)

成本是I/O的数量(忽略输出成本)

查询算法

foreach tuple r in R do
    foreach tuple s in S do
        if ri == sj  then add <r, s> to result

成本

Scan of outer  +    for each tuple of outer, scan of inner relation.

Cost  =     M    +     pR * M * N  I/Os

我对成本的最终结果感到困惑。如果我们要扫描 R 中的每个元组，然后针对每个 r，扫描 S 中的每个元组，那么最终成本不是 R*S = M*pR*N*pS 吗？ (R = M * pR，S = N * pS)。我不确定为什么会有一个附加符号。 I/O 只考虑页面吗？而不是记录？

Answer 1

你给了自己正确的答案:

Does I/O only account for pages? and not records?

这些情况下的成本是根据磁盘访问 的数量计算的。 I/O 操作将整个页面而不是记录从磁盘传输到主内存，反之亦然(这正是页面的含义:两个内存之间传输的最小单位)。

因此，由于嵌套循环算法只读取一次关系R，因此第一项等于读取它的 I/O 操作数，也就是它的页数.