Nested-Loop-Join：有多少比较和多少页面访问？

Question

假设您有两个关系R和S，其中R有 1000 个元组和 100 个页面访问，而S有 50 个元组和 25 个页面访问。

假设R是外部关系，那么完成了多少元组比较和页面访问？

如果R是内部关系，那么有多少页面访问？

for each tuple r in R do
   for each tuple s in S do
      if r and s satisfy the join condition
         then output the tuple (r,s)

因此，为了找出完成了多少元组比较，我需要执行 1000 * 50 = 50000 因为算法正在“针对每个”元组执行此操作，并且我们总共有 1000 个元组R和 50 个元组S，因此总共 50000 次比较。

但是现在如何知道页面访问？如果R在外部，我们有 (1000 个元组) * ( S 的25 个页面访问) + ( R 的100 个页面访问) = 25100 个页面访问？

如果R在里面，那么： 50 * 100 + 25 = 5025 页访问

我不确定这样是否正确..或者这是如何正确完成的？：/

Answer 1

我们可以强制 SQL Server 做到这一点，看看实际发生了什么。

R 有 1000 个元组和 100 个页面访问 = 10 个元组/页 = 806 字节/元组。
S 有 50 个元组和 25 个页面访问 = 2 个元组/页 = 4030 字节/元组。

这些是表：

drop table if exists dbo.R;
drop table if exists dbo.S;
go

create table dbo.R(n int, filler char(785)  not null default '');
create table dbo.S(n int, filler char(3990) not null default '');

填充列大小已向下舍入以允许行开销。请注意，没有索引。我有一个“数字”表，我将用它来填充 R 和 S：

insert dbo.R(n) select Number from dbo.Numbers where Number between 1 and 1000;
insert dbo.S(n) select Number from dbo.Numbers where Number between 1 and 50;

我们可以检查涉及多少页：

set statistics io on;

select * from R
select * from S

SSMS 的消息选项卡显示

Table 'R'. Scan count 1, logical reads 100, ...
Table 'S'. Scan count 1, logical reads 25, ...

我们的页数恰到好处。一些jiggery-pokery会得到你想要检查的行为

select *
from dbo.R              -- R will be outer
inner loop join dbo.S
    on r.N = s.N
option
(
  force order,          -- dictate which table is outer and which inner
  NO_PERFORMANCE_SPOOL  -- stop the QO from doing something clever but distracting
);

select *
from dbo.S              -- S will be outer
inner loop join dbo.R
    on r.N = s.N
option (force order, NO_PERFORMANCE_SPOOL);

这在消息选项卡中给出了这个（内表列在外表之前）

Table 'S'. Scan count 1, logical reads 25000, ...
Table 'R'. Scan count 1, logical reads 100, ...

Table 'R'. Scan count 1, logical reads 5000, ..
Table 'S'. Scan count 1, logical reads 25, ...

在 SQL Server 中，查询执行按行进行。对于外部表中的每一行，将引用内部表中的相应行。由于没有索引，唯一的选择是每次从内部表中读取所有行（即所有页）。对于 R-join-S，我们有 1,000 个外行乘以 25 个内页，给出 25,000 个内页引用，当然还有 100 个外页引用。对于 S-join-R，有 50 行乘以 100 页，给出 5,000 个内页引用和 25 个外页引用。

在元组比较方面，您是正确的 - 会有 O(R)xO(S) 比较 - 50,000。这是通过查看查询计划来支持的。对于这两个查询，内表引用的“读取行数”都是 50,000。

如果有索引，则查询优化器 (QO) 除了表扫描之外还有其他选择。倒带可用于重复的外键。对于不匹配的键，不能读取任何页面。在约束说不可能有任何匹配的极端情况下，甚至可能不会引用内部表。

Answer 2

真相比你意识到的更复杂。连接的外部输入确实需要 1000 次逻辑读取，但前提是连接键是唯一的。如果不是，优化器可以对它进行预排序并在 at 处获取多行并一次匹配所有行。至于内循环，您假设每次迭代进行一次完整扫描。如果内部输入被索引，优化器通常更喜欢嵌套循环，在这种情况下，页面提取的数量将由该集合的基数确定。

我的 5 美分 - 不要担心物理实现细节。投资您的资源来完善数据模型、架构和代码。让引擎担心嵌套循环。

HTH