计算块嵌套循环连接的开销

Question

我试图根据NDPR(磁盘页面读取次数)计算(最有效的)块嵌套循环连接的开销.假设您有一个表单查询:

SELECT COUNT(*)
FROM county JOIN mcd
ON count.state_code = mcd.state_code
AND county.fips_code = mcd.fips_code
WHERE county.state_code = @NO

其中@NO代替每次执行查询时的状态代码.

我知道我可以使用以下方法推导出NPDR: NPDR(R x S) = |Pages(R)| + Pages(R) / B - 2 . |P ages(S)|

(其中较小的表用作外部以便产生较少的页面读数.Ergo:R = county,S = mcd).

我也知道Page size = 2048字节

Pointer = 8 byte
Num. rows in mcd table = 35298
Num. rows in county table = 3141
Free memory buffer pages B = 100
Pages(X) = (rowsize)(numrows) / pagesize

我想弄清楚的是" WHERE county.state_code = @NO"会影响我的成本吗？

谢谢你的时间.

Answer 1

首先，关于您编写​​的公式的一些观察：

• 我不知道为什么你写“B - 2”而不是“B - 1”。从理论角度来看，您需要单个缓冲区页面来读取关系 S（您可以通过一次读取一页来完成）。

• 确保使用所有括号。我会把公式写成：
  NPDR(R x S) = |Pages(R)| + |Pages(R)| / (B-2) * |Pages(S)|

• 公式中的所有数字都需要向上舍入（但这很挑剔）。

• 通用BNLJ公式的解释：
  

  • 您可以从较小的关系 (R) 中读取尽可能多的元组（相当于 B-1 或 B-2 页的元组）。

  • 对于每组 B-2 页的元组，您必须读取整个 S 关系 (|Pages(S)|) 才能对关系 R 的特定范围执行联接。

  • 在连接结束时，关系 R 被读取一次，关系 S 被读取与我们填充内存缓冲区一样多的次数，即|Pages(R)| / (B-2)times。

现在给出答案：

• 在您的示例中，选择标准应用于关系 R（本例中为表 Country）。这是WHERE county.state_code = @NO查询的部分。因此，通用公式并不直接适用。

• 当从关系 R（即示例中的表 Country）读取时，我们可以丢弃所有不符合选择标准的非合格元组。假设美国有 50 个州，并且所有州都有相同数量的县，则表 Country 中的元组平均只有 2% 符合条件，需要存储在内存中。这减少了join的内循环的迭代次数（即我们需要扫描关系S/表mcs的次数）。2% 的数字显然只是预期的平均值，并且会根据实际给定状态而变化。

• 因此，您的问题的公式变为：
  NPDR(R x S) = |Pages(County)| + |Pages(County)| / (B - 2) * |Counties in state @NO| / |Rows in table County| * |Pages(Mcd)|