7

我正在尝试根据 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 = 县，S = mcd）。

我也知道页面大小 = 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”如何影响我的成本？

谢谢你的时间。

4

1 回答 1

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)次。

现在答案：

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

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

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

于 2015-10-20T12:38:12.853 回答