连接重排序

定义

连接重排序(Join Reordering)指优化器为多表连接选择执行顺序的过程。连接满足交换律与结合律,不同顺序语义相同但中间结果规模差异巨大,顺序选择是影响多表查询性能的首要因素。

搜索空间与算法

n 张表的连接顺序数量随 n 阶乘乃至更快增长。经典方法是 System R 提出的自底向上动态规划,只考虑左深树以控制规模;现代优化器(如 PostgreSQL)采用考虑 bushy 树的动态规划,表数超过阈值后退化为启发式或遗传算法(PostgreSQL 的 GEQO)。学术上 DPccp、DPhyp 等算法按连接图结构高效枚举。

依赖与风险

重排序的决策依据是各中间结果的基数估计,而多表连接的估计误差会逐级放大,因此"表越多计划越不可靠"。基准测试 Join Order Benchmark(JOB)专门用于评测优化器在真实相关性数据上的连接排序质量。

工程实践

实践中可通过 Hint(如 Oracle 的 LEADING、MySQL 的 JOIN_ORDER)或语法(STRAIGHT_JOIN)固定顺序,以规避估计失误;分布式引擎还需在重排序同时考虑数据分布与网络代价。