为什么 nr * bs + br 在最坏的嵌套循环连接情况下进行块传输？

Question

考虑以下连接算法：

 For each r ∈ R do
    For each s ∈ S do
        if r.C = s.C then output r,s pair

nr是R中元组的个数，br是R中块的个数

教科书上说最坏情况下buffer只能放一个block，需要nr ∗ bs + br次传输

但是我想，如果buffer只能容纳一个block，那么每次我们加载完S中的block之后，我们之前加载的R中的block就会被换出。那么如果我们想访问R的下一个元组，即使之前已经加载过，难道我们不应该再次加载这个块吗？即我最初加载 R 中的第一个元组，为此我需要加载 R 中的第一个块；然后我加载整个 S，并比较它们的密钥。完成内部循环后，R 的第一个块已被换出，因此当我尝试在 R 中加载第二个元组时，我需要再次加载第一个块。因此，每次尝试访问 R 中的元组时，我都需要加载 R。

那为什么最坏的情况不是nr ∗ bs + nr？

Answer 1

在最坏的情况下，数据库缓冲区只能容纳每个关系的一个块。因此，让我们假设块是 R 的块。现在对于 R 中的每个元组，我们将检查它与 S 的每个元组的连接条件。

缓冲区有1块R和1块S。

Total blocks of R = B(R)
Total tuples in R = N(R)
Total blocks of S = B(S)

R X S is done.

数据库缓冲区中有 2 个 space。第1space可以填B(R)号。次。第 2 个 space 将填写 N(R) X B(R) 编号。 R 中的每个元组将与 S 中的每个元组匹配的次数。

因此将发生 B(R) + N(R) X B(R) 次磁盘访问。

为什么 nr * bs + br 在最坏的嵌套循环连接情况下进行块传输？

why nr ∗ bs + br for block transfer in worst case Nested-Loop Join?

database

join

nested-loops