Arrow DataFusion 中多表连接优化的挑战与解决方案

背景介绍

在现代数据分析系统中，星型模式（star schema）是一种常见的数据模型设计，它由一个事实表（facts table）和多个维度表（dimension tables）组成。当执行涉及多个表的连接查询时，查询优化器需要做出明智的决定来确定最佳的执行计划。

在Arrow DataFusion项目中，开发者发现了一个关于多表连接优化的有趣问题：当连接3个或更多Delta表时，"右深树"（right deep tree）优化策略未能按预期工作，特别是在连接键为字符串类型且缺少列统计信息的情况下。

问题现象

具体表现为：在一个包含事实表和两个维度表的星型模式查询中，优化器尝试将事实表作为中间节点收集到内存中，导致内存不足（OOM）错误。理想情况下，优化器应该采用"右深树"策略，将维度表收集到内存中，而保持事实表在流水线的右侧。

技术分析

DataFusion的优化器在处理多表连接时，会考虑以下因素来决定是否交换连接顺序：

1. 表的统计信息（如行数、列的最小/最大值）
2. 连接键的数据类型
3. 现有的物理执行计划结构

在Delta表的情况下，delta-rs库目前只为基础类型生成列统计信息，而不包括字符串类型。这导致优化器无法准确评估连接顺序对性能的影响，从而做出了次优决策。

解决方案探讨

针对这一问题，社区提出了几种可能的解决方案：

1. 强制交换连接顺序：当检测到左侧节点已经是CollectLeft模式时，可以强制交换连接顺序，保持"右深树"的物理结构。这种方法简单直接，但可能需要配置开关来控制其行为。

2. 增强Delta表的统计信息：让delta-rs为字符串列也生成统计信息。不过这种方法价值有限，因为字符串类型的统计信息（如基数）难以准确计算。

3. 引入连接提示（Join Hints）：借鉴Spark SQL的做法，允许用户在SQL查询中通过特殊语法提示优化器使用特定的连接策略。

4. 语义优化器：利用DataFusion默认不重新排序连接的特性，通过调整SQL查询中表的顺序来隐式控制连接顺序。

5. 自定义优化器规则：开发专门的优化器规则，实现特定的启发式算法（如基于外键/主键约束的规则）。

专家建议

从系统设计的角度来看，DataFusion的核心应该保持通用性和灵活性，而将特定的优化策略留给扩展API实现。对于星型模式这种常见场景，建议：

1. 首先添加配置选项来控制是否允许优化器重新排序连接，让用户能够通过SQL语法隐式控制连接顺序。

2. 对于高级用户，可以开发自定义优化器规则，实现针对特定数据模型（如星型模式）的优化策略。

3. 长期来看，考虑引入连接提示机制，为用户提供更直接的执行计划控制能力。

总结

多表连接优化是查询引擎中最复杂的部分之一。Arrow DataFusion项目通过保持核心简单而可扩展的设计理念，为各种优化策略提供了实现空间。对于特定的使用场景如星型模式，用户可以通过配置调整、自定义规则或查询重写等方式获得理想的执行计划。这一案例也展示了开源项目中如何平衡通用性与特定优化需求的设计思路。