优化 DataFusion 中的 SQL（和 DataFrames）：第 1 部分

作者：Andrew Lamb / Mustafa Akur / 开发者
2025 年 3 月 31 日

简介

有时，查询优化器被视为一种黑魔法，“计算机科学中最具挑战性的问题，”根据 Father Pavlo 的说法，或者是一些幕后玩家。我们认为这种看法是因为

1. 必须在优化器变得至关重要之前¹实现数据库系统的其余部分（数据存储、事务、SQL 解析器、表达式评估、计划执行等）。
2. 优化器的某些部分与系统的其余部分（例如，存储或索引）紧密相关，因此许多经典的优化器都使用特定于系统的术语来描述。
3. 一些优化器任务，例如访问路径选择和连接顺序是众所周知的挑战，并且尚未（在实践中）解决——也许它们真的需要黑魔法 🤔。

然而，查询优化器在理论或实践上并不比数据库系统的其他部分更复杂，正如我们将在系列文章中论证的那样

第 1 部分

• 回顾什么是查询优化器，它做什么，以及为什么 SQL 和 DataFrames 需要一个。
• 描述工业查询优化器的结构和标准优化类别。

第 2 部分

• 通过示例和指向实现的指针来描述优化类别。
• 描述 Apache DataFusion 对查询优化的基本原理和方法，特别是针对访问路径和连接排序。

阅读这些博客后，我们希望人们将使用 DataFusion 来

1. 构建他们自己的系统特定优化器。
2. 进行关于优化的实践学术研究（特别是研究新优化/连接排序的研究人员——看着你 CMU 15-799，明年）。

查询优化器背景

查询数据库的关键卖点，以及 SQL 长寿的关键（尽管人们对 SQL 有爱恨交加的关系——参见 SQL or Death? Seminar Series – Spring 2025），在于它将您想要计算的 WHAT 与 HOW 执行计算的方式分离开来。SQL 是一种声明式语言——它描述了所需的答案，而不是像 Python 这样的命令式语言，在 Python 中，您描述如何执行计算，如图 1 所示。

图 1：查询执行：用户使用 DataFrame 或 SQL 描述他们想要的答案。查询计划器或 DataFrame API 将该描述转换为初始计划，该计划是正确的但速度很慢。然后，查询优化器将初始计划重写为优化计划，该计划计算相同的结果，但速度更快、效率更高。最后，执行引擎执行优化计划并生成结果。

SQL、DataFrames、LogicalPlan 等价性

鉴于它们的名称，查询优化器可以提高 SQL 查询的性能并不奇怪。然而，人们低估了这同样适用于 DataFrame 风格的 API。

经典的 DataFrame 系统，例如 pandas 和 Polars（默认情况下）是急切执行的，因此优化机会有限。然而，更现代的 API，例如 Polar 的 lazy API、Apache Spark DataFrame 和 DataFusion 的 DataFrame 速度更快，因为它们使用了图 1 中所示的设计并应用了许多查询优化技术。

查询优化器示例

本节通过一个示例来说明查询优化器的价值。假设您有一些动物行为的观察结果，如表 1 所示。

表 1：示例观测数据。

如果用户想知道过去一个月中某些物种的平均种群数量，用户可以编写 SQL 查询或 DataFrame，例如以下内容

SELECT location, AVG(population)
FROM observations
WHERE species = ‘contrarian spider’ AND 
  observation_time >= now() - interval '1 month'
GROUP BY location

df.scan("observations")
  .filter(col("species").eq("contrarian spider"))
  .filter(col("observation_time").ge(now()).sub(interval('1 month')))
  .agg(vec![col(location)], vec![avg(col("population")])

在 DataFusion 中，SQL 和 DataFrame 都被转换为相同的 LogicalPlan，即“关系运算符树”。这是一种描述数据流图的巧妙方式，其中边表示表格数据（行 + 列），节点表示转换（有关更多详细信息，请参见 此 DataFusion 概述视频）。上面查询的初始 LogicalPlan 如图 2 所示。

图 2：SQL 和 DataFrame 查询的示例初始 LogicalPlan。该计划从下往上读取，计算每个步骤的结果。

优化器的工作是获取此查询计划并将其重写为备用计划，该计划计算相同的结果但速度更快，例如图 3 所示的计划。

图 3：一个优化的计划示例，该计划比图 2 中的计划更有效地计算相同的结果。该图突出显示了优化器应用投影下推、过滤器下推和常量求值的位置。请注意，这是一个简化的示例，仅用于解释目的，DataFusion 等实际优化器会执行其他任务，例如选择特定的聚合算法。

查询优化器实现

工业优化器，例如 DataFusion 的（源代码）、ClickHouse 的（源代码，源代码）、DuckDB 的（源代码）和 Apache Spark 的（源代码）实现为一系列传递或规则，用于重写查询计划。整个优化器由一系列这些规则⁶组成，如图 4 所示。规则的特定顺序通常也很重要，但我们不会在本篇文章中讨论此细节。

多遍设计是标准的，因为它有助于

1. 隔离地理解、实现和测试每个传递
2. 通过添加新的传递来轻松扩展优化器

图 4：查询优化器实现为一系列规则，每个规则都重写查询计划。每个规则的算法都表示为先前计划的转换。

工业优化器中存在三个主要的优化类别

1. 始终优化：这些优化始终是好的，因此始终应用。此类优化包括表达式简化、谓词下推和限制下推。这些优化在理论上通常很简单，但实际上需要大量的代码和测试才能实现。
2. 引擎特定优化： 这些优化利用了特定的引擎功能，例如表达式的评估方式或可用的特定哈希或连接实现。
3. 访问路径和连接顺序选择：这些传递为每个表选择一种访问方法，并为执行选择连接顺序，通常使用启发式方法和成本模型来权衡选项。数据库通常有多种访问数据的方式（例如，索引扫描或全表扫描），以及组合（连接）多个表的许多潜在顺序。这些方法计算相同的结果，但在性能上可能差异很大。

这使我们来到了第 1 部分的结尾。在 第 2 部分 中，我们将更详细地解释这些优化类别，并提供有关如何在 DataFusion 和其他系统中实现它们的示例。

1. 因此，在学术课堂上，当您开始研究优化器时，学期已经结束，每个人都准备好结束学期了。一旦工业系统成熟到优化器成为瓶颈的地步，炒作周期 的闪亮光环已经褪去，并且很可能处于失望的低谷。