1. 连接操作的背景与问题定义

在关系型数据库中，我们通常面对以下问题： 给定一个数据库实例 $\mathcal{I}$，包含若干关系（表） R = { R 1 , R 2 , ⋯ , R n } \mathcal{R}=\{R_1, R_2, \cdots, R_n\} R={R1​,R2​,⋯,Rn​} 和属性集合 A = { a 1 , a 2 , ⋯ , a m } \mathcal{A}=\{a_1, a_2, \cdots, a_m\} A={a1​,a2​,⋯,am​}，如何高效地计算连接结果 $Q=R_1\bowtie R_2\bowtie \cdots \bowtie R_n$？

在这个问题中，我们仅考虑等值连接。在实际应用中，我们可以通过下推选择操作、得到结果之后再执行投影和聚合的方式，将含有选择、投影和聚合的复杂查询划归到连接查询上。

由于执行过程中会产生大量中间结果，因此需要仔细选择合适的执行计划（包括连接顺序）和连接算法，重点在于减少不必要的中间结果和计算代价。

2. 连接操作的经典方法

2.1 二元连接（Binary Join）

这是最常用的连接方法，适用于两个关系表的连接。实现方式包括嵌套循环连接（nested loop join）、块嵌套循环连接（Block Nested Loop Join）、哈希连接（Hash Join，在小表上建立 hash 表，对于大表的每一条元组探查 hash 表，查看是否存在满足连接条件的结果）和排序-合并连接（Sort-Merge Join，先对数据排序，再通过合并实现连接）等方式。

虽然这些方法简单且直观，但在处理复杂查询和多表连接时，可能会产生性能瓶颈。

2.2 Yannakakis 算法（适用于无环查询）

对于无环查询（acyclic queries），Yannakakis算法^[1]可以达到最优复杂度。其分为两个阶段：

• 自底向上的半连接（Bottom-up Semi-Join）：逐步减少数据规模。
• 自顶向下的半连接（Top-down Semi-Join）：递归计算最终结果。
  通过自底向上的半连接，可以保证后续自顶向下的连接中，每一条来自上层的元组，都能产生最终的连接结果，从而避免悬空元组（dangling tuple）带来的高代价。

3 最优连接算法

3.1 AGM 上界

如下图所示，考虑三角形连接查询 $Q=R(a,b)\bowtie S(b,c)\bowtie T(c,a)$ ，若每个表的大小都为 $N$，无论采用何种二元连接，在中间步骤连接任意两个表时，最坏情况下会产生 $N^2$ 的中间结果，而此三角形查询最坏情况下能产生的结果数目仅为 $N^{1.5}$^[2]。所以二元连接在某些情况下，会产生过多的中间结果。

给定连接查询里每个表的基数（元组数量）时，AGM 上界^[2]给出了所有满足该基数限制的数据库实例中，能够产生最多连接结果的数量，其可以通过超图和线性规划的方法求出。

值得注意的是，AGM上界仅为最坏情况下连接结果的大小，尽管这是个紧的上界（可以构造出数据库实例，产生出这么多数量的连接结果），但具体到某个实例上，最终的结果数量可能远小于该上界。

3.2 最坏情况最优连接（Worst-Case Optimal Join, WCOJ）

传统的二元连接算法并不能保证在最坏情况下达到最优性能。而 WCOJ 算法则通过逐属性连接的方法，每步骤产生的中间结果数量都不会超过对应子查询的 AGM 上界，从理论上保证了最坏情况下的时间复杂度最优。

典型算法：

• NPRR算法^[3]
  首次提出了最坏情况最优连接的概念。NPRR 通过将属性值分类为“轻节点”和“重节点”，对重节点进行特殊处理（采用检查策略而非连接策略），从而避免了不必要的计算。 后续工作 Generic Join^[4] ，拓展了 NPRR 算法，不必再将属性值分类，而直接每次连接一个属性，便可达到最坏情况最优的性质。
• Leapfrog Triejoin算法^[5]
  这是一个简单且高效的WCOJ算法，主要利用了对单属性的蛙跳求交算法（leapfrog join）。

4 最新的研究与优化方向

4.1 Lookup & Expand

该工作^[6]将一个连接操作拆分为**查找（Lookup）和扩展（Expand）**两步：

• 查找：找到第一个匹配项。
• 扩展：生成剩余的匹配结果。

这种方法的好处在于：可以将查找操作下推，尽早发现无法匹配的中间结果，提前终止对这些中间结果的执行。作者还发现，对于实际应用的查询，采用该分解框架，仅用二元连接和三元连接便可在大部分查询上达到较好的性能。该论文还提出了根据两个启发式规则和代价模型，选择实际执行计划的策略，具体可以参考该论文对应的技术报告^[7]。

实验结果也展现了其方法的优越性。

4.2 Free Join

与一般的 WCOJ 的 Trie 树实现方式不同，Free Join^[8]利用**拓展哈希树（generalized hash trie, GHT）**来组织数据。其执行包含构建和连接两步骤。在其框架中，可以将任意二元连接计划转化为一个利用 GHT 执行的计划，随后采用若干启发式规则，下推查找进行优化。实际执行时，还可以采用延迟模式构建 GHT 以及向量化操作等方式进一步优化性能。在常见基准上，该方法展现了较好性能。

5 连接操作在图查询中的应用

在图查询中，连接操作通常用于子图匹配问题，给定查询图的节点顺序，便可根据该顺序，一次连接一个节点。下面两个子图匹配算法中也蕴含了上面连接操作的优化思想：

1. **NewSP算法^[9]：**通过延迟Expand操作，在有匹配结果的时候，能够减少中间结果，提高匹配效率。
2. **VEQ算法^[10]：**提前处理一度查询顶点的连接操作，提前发现不能产生匹配结果的情况，减少无用操作。

6 总结

连接操作是数据库系统的核心部件之一，从传统的二元连接到最坏情况最优连接，再到最新的Lookup & Expand和Free Join方法，连接算法在性能和可扩展性上不断取得突破。但这些方法的思想内涵都是一致的，总结为以下三点：

• 尽管任何一种连接顺序在WCOJ执行下都能保证最坏情况最优性，但具体到每一个实例上，执行效率差别会很大。
• 提前检查，延后拓展，减少无用中间结果。
• 合并某些操作会带来收益。

参考文献

[1] Algorithms For Acyclic Database Schemes. Mihalis Yannakakis. VLDB 1981.

[2] Size Bounds and Query Plans for Relational Joins. Atserias Albert, Martin Grohe, and Dániel Marx. Proceedings of the 2008 49th Annual IEEE Symposium on Foundations of Computer Science. 2008.

[3] Worst-case Optimal Join Algorithms. PODS 2012. Hung Q. Ngo, Ely Porat, Christopher Ré, Atri Rudra

[4] Skew Strikes Back: New Developments in the Theory of Join Algorithms. SIGMOD Record 2014. Hung Q Ngo, Christopher Ré, and Atri Rudra.

[5] Leapfrog triejoin: A simple, worst-case optimal join algorithm. Todd L. Veldhuizen. ICDT, 2014.

[6] Robust Join Processing with Diamond Hardened Joins. Altan Birler, Alfons Kemper, and Thomas Neumann. VLDB 2024.

[7] Technique report. https://mediatum.ub.tum.de/1732739?show_id=1736607.

[8] Free Join: Unifying Worst-Case Optimal and Traditional Joins. Yisu Remy Wang, Max Willsey, and Dan Suciu. SIGMOD 2023.

[9] NewSP: A New Search Process for Continuous Subgraph Matching over Dynamic Graphs. ICDE 2024. Ziming Li, Youhuan Li, Xinhuan Chen, Lei Zou, Yang Li, Xiaofeng Yang, Hongbo Jiang.

[10] Versatile Equivalences: Speeding up Subgraph Query Processing and Subgraph Matching. SIGMOD 2021. Hyunjoon Kim, Yunyoung Choi, Kunsoo Park, Xuemin Lin, Seok-Hee Hong, Wook-Shin Han.