Lobsters | 原文链接 | 2026-10-01 收录 · 热度 3

连接顺序（一）：搜索空间的形状

来源: deferworks.org

这篇长文是连接顺序系列的第一部分，源于作者跟随 CMU OPTIMIZE! 课程所做的笔记。它先说明为什么连接顺序至关重要，再引出以 Moerkotte 与 Neumann 为核心的“德国系”动态规划路线。

核心要点

SQL 标准不规定连接顺序，只规定结果形状，选哪一棵连接树是优化器的职责。
三个关系的例子中，(R₀⋈R₂)⋈R₁ 先把 R₀ 缩小再完成，而 (R₀⋈R₁)⋈R₂ 要先造出高达 10¹² 元组的中间结果，代价相差十个数量级。
真实系统里规划器的顺序选择可以让执行时间相差 100 倍以上。
不同连接树的数量是 (2(n-1))!/(n-1)!：n=4 时 120，n=5 时 1680，n=15 时约 3.5×10¹⁸。
带真实代价函数的连接顺序问题通常是 NP 难的，但许多现代系统仍能用动态规划精确求解中等规模实例。
系列将依次讲解 DPccp（每个工作单元只碰一次）、DPhyp（从图推广到超图）、面向超大查询的自适应优化，以及 2025 年补上完整搜索空间枚举空白的 CD-E。
作者特意把 46 页笔记拆成 6 部分，因为一次读完对注意力并不友好。

对内连接来说所有连接树的结果都相同，但它们的代价可能天差地别，因为中间结果的大小相差悬殊。