mysql - 计算 block 嵌套循环连接的成本

Question

我正在尝试根据 NDPR(磁盘页面读取数)计算(最有效的) block 嵌套循环连接的成本。假设您有以下形式的查询:

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)| + 页数(R)/B - 2 。 |页面(S)|

(其中较小的表用作外部以产生较少的页面读取。因此:R = 县，S = mcd)。

我也知道 Page size = 2048 bytes

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) = |页数(R)| + |页数(R)|/(B-2) * |页数(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% 的元组平均符合条件，需要存储在内存中。这减少了连接内循环的迭代次数(即我们需要扫描关系 S/表 mcs 的次数)。 2% 的数字显然只是预期的平均值，会根据实际给定状态而变化。

• 因此，您的问题的公式变为:
  NPDR(R x S) = |页数(县)| + |页数(县)|/(B - 2) * |@NO 州的县|/|表县中的行| * |页面(Mcd)|