设计精良的数据库旨在减少不必要的数据重复。为了实现这一目标，我们采用了规范化，它将数据拆分到更小、更易于管理的表中。然而，当我们需要从不同的表中组合信息时，我们就需要使用连接。
一种常见的连接类型是内部等值连接。这种连接将两个表中特定列（通常是键）的值相匹配的行组合在一起。
连接是如何工作的
当我们执行连接操作时，它会从两个不同的表中获取两段数据（称为元组）并将它们组合成一段新的数据。连接的关键部分在于基于共同属性（如唯一ID）在两个表中匹配值。
基本概念：连接基于相关的列，将两个或多个表中的行（元组）组合在一起。相关列通常是一个表中的外键，它与另一个表中的主键相匹配。
匹配值：连接操作会在为连接条件指定的列中查找匹配的值。例如，如果我们正在连接 Employees 表和 Departments 表，连接会将 Employees 表中的 department_id 与 Departments 表中的 id 进行匹配。
连接的结果：当找到匹配项时，SQL 会将匹配的行组合成结果集中的单个新行。这个新行包含来自两个表的匹配行的数据。
连接输出的类型
数据库组合数据的方式可能会根据其设置的不同而有所差异。主要有两种实现方式：
1. 数据复制：当执行连接操作时，数据库会将来自外部元组和内部元组的匹配属性的值复制到一个新的输出元组中。这意味着参与连接的两个表中的数据被组合在一起，并放入结果中。
一旦这些数据被组合到输出元组中，查询计划中的后续操作就可以继续处理结果，而无需返回原始基表获取更多数据。这种方法非常有用，因为它最大限度地减少了重新访问原始表的需求，这可能会很慢且在性能上代价高昂。相反，组合后的数据在中间结果中立即可用，从而加快了查询执行速度。
!join-1数据复制
2. 记录ID：在某些情况下，数据库不会复制匹配行中的所有数据，而是只复制连接键（用于匹配行的属性）和匹配元组的记录ID。这种方法效率更高，因为它避免了复制不必要的数据。
这种方法对于列式存储特别有用，因为数据库只存储查询所需的数据，从而减少了内存使用。
这种方法被称为延迟物化。这意味着数据库会延迟实际的数据复制，直到绝对必要时才进行，这有助于提高性能并减少存储在内存中的数据量。
!join-2记录ID
在现实世界的数据库系统中，执行连接的方法可能会有所不同。数据库管理系统（DBMS）通常会根据元组数量、列数和查询中的操作类型等因素，结合这两种方法（复制数据和复制记录ID）。策略的选择是动态的，旨在根据查询的具体需求优化性能。
I/O 成本分析
当我们分析不同的连接算法时，我们要关注的是 I/O 成本，即计算连接所需的磁盘读写操作次数。这是因为磁盘 I/O 操作通常占主导地位，特别是在基于磁盘的系统中，因此我们通常忽略连接算法的计算成本。
> I/O 成本仅考虑连接计算期间采取的操作。输出结果的成本不被考虑在内，因为这取决于输出数据的大小，而无论使用何种连接算法，输出数据的大小都是相同的。
变量：
- M：表 R（外部表）中的页面数。
- N：表 S（内部表）中的页面数。
- m：表 R 中的元组总数。
- n：表 S 中的元组总数。
> 考虑一个查询：
>
> SELECT R.id, S.cdate
> FROM R JOIN S
> ON R.id = S.id
> WHERE S.value > 100
这个查询在两个表 R 和 S 之间使用 id 属性执行连接。该查询还从表 S 中筛选出 value 大于 100 的行。
在连接的情况下，自然连接（INLINECODE4dcd5a18）是最常见的操作之一。然而，如果优化得不好，某些算法可能会效率低下。例如，可能会先计算交叉积（INLINECODEb86ae707），然后再筛选相关…