优化器：低调的 MVP

Tom Ebergen

2024-11-14 · 17 分钟

在数据库社区中，优化器通常不会给人留下“主角”的印象。数据库通常因其性能、易于集成或可靠性而受欢迎。作为主要从事 DuckDB 优化器工作的人，我一直想写一篇博客文章，说明优化器有多重要，以及为什么它们值得更多的认可。在这篇博客文章中，我们将分析属于以下三种类别之一的查询：未优化、手动优化和由 DuckDB 查询优化器优化。我还将解释为什么内置优化器几乎总是优于任何手动优化。希望在阅读完这篇博客文章后，您会同意优化器在使用数据库时发挥着默默但至关重要的作用。让我们首先了解查询优化发生在执行管道中的哪个位置。

在从数据库读取任何数据之前，必须解析和验证给定的 SQL 文本。如果此过程成功完成，则会创建一个基于树的查询计划。由解析器生成的查询计划是原始的，并且根据查询的不同，可能非常低效。这就是优化器发挥作用的地方，低效的查询计划被传递给优化器进行修改，并且，您猜对了，进行优化。优化器由许多优化规则组成。每个规则都能够重新排序、插入和删除查询操作，以创建一个稍微更高效的查询计划，该计划在逻辑上也是等效的。应用所有优化规则后，优化后的计划可能比解析器生成的计划高效得多。

在实践中，优化规则也可以称为优化器。对于这篇博文的其余部分，优化器规则将用于特定的优化，而优化器将指数据库优化器，除非优化器这个词命名了一个特定的优化规则（即，连接顺序优化器）。

普通查询 vs. 优化查询

为了检查 DuckDB 查询优化器的效果，让我们使用 NYC 出租车数据集的子集。您可以使用以下命令创建原生 DuckDB 表（请注意，taxi-data-2019.parquet 大约 1.3 GB）

CREATE TABLE taxi_data_2019 AS
    FROM 'https://blobs.duckdb.org/data/taxi-data-2019.parquet';
CREATE TABLE zone_lookups AS
    FROM 'https://blobs.duckdb.org/data/zone-lookups.parquet';

现在我们有了所有 2019 年的数据，让我们看看一个简单查询的未优化和优化计划。以下 SQL 查询获取曼哈顿行政区中最常见的上下车配对。

PRAGMA disable_optimizer;
PRAGMA explain_output = 'optimized_only';
EXPLAIN SELECT
    pickup.zone AS pickup_zone,
    dropoff.zone AS dropoff_zone,
    count(*) AS num_trips
FROM
    zone_lookups AS pickup, 
    zone_lookups AS dropoff,
    taxi_data_2019 AS data
WHERE pickup.LocationID = data.pickup_location_id
  AND dropoff.LocationID = data.dropoff_location_id
  AND pickup.Borough = 'Manhattan'
  AND dropoff.Borough = 'Manhattan'
GROUP BY pickup_zone, dropoff_zone
ORDER BY num_trips DESC
LIMIT 5;

运行此 EXPLAIN 查询会给我们以下计划。

┌───────────────────────────┐
│           LIMIT           │
│    ────────────────────   │
└─────────────┬─────────────┘
┌─────────────┴─────────────┐
│          ORDER_BY         │
│    ────────────────────   │
│        count_star()       │
└─────────────┬─────────────┘
┌─────────────┴─────────────┐
│         PROJECTION        │
│    ────────────────────   │
│        Expressions:       │
│             0             │
│             1             │
│         num_trips         │
└─────────────┬─────────────┘
┌─────────────┴─────────────┐
│         AGGREGATE         │
│    ────────────────────   │
│          Groups:          │
│        pickup_zone        │
│        dropoff_zone       │
│                           │
│        Expressions:       │
│        count_star()       │
└─────────────┬─────────────┘
┌─────────────┴─────────────┐
│           FILTER          │
│    ────────────────────   │
│        Expressions:       │
│       (LocationID =       │
│     pickup_location_id)   │
│       (LocationID =       │
│    dropoff_location_id)   │
│ (Borough = CAST('Manhattan│
│       ' AS VARCHAR))      │
│ (Borough = CAST('Manhattan│
│       ' AS VARCHAR))      │
└─────────────┬─────────────┘
┌─────────────┴─────────────┐
│       CROSS_PRODUCT       │
│    ────────────────────   ├───────────────────────────────────────────┐
└─────────────┬─────────────┘                                           │
┌─────────────┴─────────────┐                             ┌─────────────┴─────────────┐
│       CROSS_PRODUCT       │                             │          SEQ_SCAN         │
│    ────────────────────   ├──────────────┐              │    ────────────────────   │
│                           │              │              │       taxi_data_2019      │
└─────────────┬─────────────┘              │              └───────────────────────────┘
┌─────────────┴─────────────┐┌─────────────┴─────────────┐
│          SEQ_SCAN         ││          SEQ_SCAN         │
│    ────────────────────   ││    ────────────────────   │
│        zone_lookups       ││        zone_lookups       │
└───────────────────────────┘└───────────────────────────┘

仅交叉连接就使这个查询效率极低。交叉连接产生 256 * 256 * |taxi_data_2019| 行数据，即 5 万亿行数据。过滤器仅匹配 7100 万行，仅占数据的 0.001%。聚合产生 4,373 行数据，这些数据需要按 ORDER BY 操作排序，该操作以 O(N * log N) 运行。仅生成 5 万亿个元组就是巨大的数据处理量，当您尝试运行查询并注意到它没有完成时，这一点就会变得很清楚。启用优化器后，生成的查询计划效率更高，因为操作被重新排序以避免数万亿行的中间数据。以下是启用优化器后的查询计划

PRAGMA enable_optimizer;
EXPLAIN ...

┌───────────────────────────┐
│           TOP_N           │
│    ────────────────────   │
│          ~5 Rows          │
└─────────────┬─────────────┘
┌─────────────┴─────────────┐
│         PROJECTION        │
│    ────────────────────   │
│        Expressions:       │
│             0             │
│             1             │
│         num_trips         │
│                           │
│         ~265 Rows         │
└─────────────┬─────────────┘
┌─────────────┴─────────────┐
│         AGGREGATE         │
│    ────────────────────   │
│          Groups:          │
│        pickup_zone        │
│        dropoff_zone       │
│                           │
│        Expressions:       │
│        count_star()       │
│                           │
│         ~265 Rows         │
└─────────────┬─────────────┘
┌─────────────┴─────────────┐
│      COMPARISON_JOIN      │
│    ────────────────────   │
│      Join Type: INNER     │
│                           │
│        Conditions:        ├───────────────────────────────────────────┐
│   (pickup_location_id =   │                                           │
│         LocationID)       │                                           │
│                           │                                           │
│       ~1977517 Rows       │                                           │
└─────────────┬─────────────┘                                           │
┌─────────────┴─────────────┐                             ┌─────────────┴─────────────┐
│      COMPARISON_JOIN      │                             │          SEQ_SCAN         │
│    ────────────────────   │                             │    ────────────────────   │
│      Join Type: INNER     │                             │          Filters:         │
│                           │                             │  Borough='Manhattan' AND  │
│        Conditions:        ├──────────────┐              │     Borough IS NOT NULL   │
│   (dropoff_location_id =  │              │              │                           │
│         LocationID)       │              │              │        zone_lookups       │
│                           │              │              │                           │
│       ~12744000 Rows      │              │              │          ~45 Rows         │
└─────────────┬─────────────┘              │              └───────────────────────────┘
┌─────────────┴─────────────┐┌─────────────┴─────────────┐
│          SEQ_SCAN         ││          SEQ_SCAN         │
│    ────────────────────   ││    ────────────────────   │
│       taxi_data_2019      ││          Filters:         │
│                           ││  Borough='Manhattan' AND  │
│                           ││     Borough IS NOT NULL   │
│                           ││                           │
│                           ││        zone_lookups       │
│                           ││                           │
│       ~84393604 Rows      ││          ~45 Rows         │
└───────────────────────────┘└───────────────────────────┘

在谈论发生的优化之前，让我们首先看看我的 MacBook（配备 M1 Max 和 32 GB 内存）上的执行时间差异。

希望这种性能优势说明了 DuckDB 优化器的强大功能。那么哪些优化规则负责这些巨大的性能改进呢？对于上面的查询，在优化查询时应用了三个强大的规则：过滤器下推、 连接顺序优化和 TopN 优化。

过滤器下推优化器非常有用，因为它减少了正在处理的中间数据量。对于人类来说，这是一个有时容易被忽略的优化规则，如果过滤器在任何方面具有选择性，它将始终导致更快的执行时间。它采用一个过滤器，例如 Borough = 'Manhattan'，并将其下推到首先引入过滤列的运算符，在本例中是表扫描。此外，它还会检测何时在相等条件中使用过滤列，例如 col1（即 WHERE col1 = col2）。在这些情况下，过滤器会被复制并应用于另一个列 col2，从而进一步减少正在处理的中间数据量。

连接顺序优化器识别出过滤器 pickup.LocationID = data.pickup_location_id 和 dropoff.LocationID = data.dropoff_location_id 可以用作连接条件，并相应地重新排列扫描和连接。此优化器规则做了很多繁重的工作来减少正在处理的中间数据量，因为它负责删除交叉连接。

当需要对聚合数据进行排序时，TopN 优化器非常有用。如果查询具有 ORDER BY 和 LIMIT 运算符，则 TopN 运算符可以替换这两个运算符。TopN 运算符仅对最高/最低 N 值进行排序，而不是对所有值进行排序。如果 N 为 5，则 DuckDB 只需要在内存中保留 5 行具有最小/最大值的行，并可以丢弃其余行。因此，如果您只对 M 中的前 N 个值感兴趣，其中 N << M，则 TopN 运算符可以以 O(M + N * log N) 而不是 O(M * log M) 运行。

这些只是 DuckDB 拥有的少数优化。更多优化在 所有优化器摘要部分中进行了解释。

手动优化查询

对于上面的查询，可以通过仔细手动编写 SQL 查询来实现几乎相同的计划。为了实现与 DuckDB 生成的计划类似的计划，您可以编写以下内容。

SELECT 
    pickup.zone AS pickup_zone,
    dropoff.zone AS dropoff_zone,
    count(*) AS num_trips
FROM
    taxi_data_2019 data
INNER JOIN
    (SELECT * FROM zone_lookups WHERE Borough = 'Manhattan') pickup
    ON pickup.LocationID = data.pickup_location_id
INNER JOIN
    (SELECT * FROM zone_lookups WHERE Borough = 'Manhattan') dropoff
    ON dropoff.LocationID = data.dropoff_location_id
GROUP BY pickup_zone, dropoff_zone
ORDER BY num_trips desc
LIMIT 5;

再次检查运行时，我们得到

上面的 SQL 产生了一个类似于 DuckDB 优化计划的计划，但它更冗长且更易于编写出错，这可能会导致错误。在极少数情况下，可以手动编写一个查询，该查询产生的计划比优化器更有效。这些情况是极端的异常值，在所有其他情况下，优化器将产生更好的计划。此外，手动优化的查询针对数据的当前状态进行了优化，该状态可能会随着时间的推移而发生多次更新而变化。一旦对数据应用了足够的更改，手动优化查询的假设可能不再成立，从而导致性能不佳。让我们看下面的例子。

假设一家新兴公司拥有一个 orders 和 parts 表，并且每次加载一些仪表板时，都需要计算最受欢迎的订购零件。由于该公司仍然相对较新，因此他们只有少量订单，但他们的零件目录仍然很大。手动优化的查询如下所示

CREATE OR REPLACE TABLE orders AS
    SELECT RANGE order_id, range % 10_000 pid FROM range(1_000);
CREATE TABLE parts AS
    SELECT range p_id, range::VARCHAR AS part_name FROM range(10_000);
SELECT
    parts.p_id,
    parts.part_name,
    count(*) AS ordered_amount
FROM parts
INNER JOIN orders 
    ON orders.pid = parts.p_id
GROUP BY ALL;

当然，随着该公司获得客户并越来越受欢迎，订单数量将会增加。如果上面的查询在不使用优化器的情况下继续运行，则性能会逐渐下降。这是因为执行引擎将在 orders 表上构建哈希表，该表可能具有 1 亿行。如果启用了优化器，则 连接顺序优化器将能够在优化过程中检查表的统计信息，并根据数据的新状态生成新的计划。

以下是在订单表增加的情况下运行带有和不带有优化器的查询的细分。

起初，执行时间的差异并不是很明显，因此没有人会认为重写查询是解决方案。但是一旦达到足够的订单，每次加载仪表板时等待 2 秒钟就会变得乏味。如果启用了优化器，则查询性能将提高 10 倍。因此，如果您认为您已经确定了一个您比优化器更聪明的情况，请确保您也考虑了对数据的所有可能的更新，并且也针对这些更新进行了手动优化。

无法手动进行的优化

一些优化规则也无法手动编写。例如，TopN 优化无法手动优化。

另一个很好的例子是连接过滤器下推优化。连接过滤器下推优化适用于哈希连接的构建端具有连接键的子集的情况。在其当前状态下，连接过滤器下推优化会跟踪最小键值和最大键值，并将表过滤器推送到探测端，以过滤掉大于最大连接值且小于最小连接值的键。

通过一个小的更改，我们可以使用上面的查询来演示这一点。假设我们首先过滤我们的 parts 表，使其仅包含 part_name 中具有特定前缀的零件。当 orders 表有 1 亿行，并且过滤后 parts 表只有大约 20,000 行时，orders 表将是探测端，parts 表将是哈希/构建端。构建哈希表时，会记录 parts 表中的最小和最大 p_id 值，在本例中可能为 20,000 和 80,000。这些最小值和最大值作为过滤器推送到 orders 表扫描中，过滤掉所有 p_id > 80,000 和 pid < 20,000 的零件。orders 表的 40% 的 pid 大于 80,000 且小于 20,000，因此此优化在连接查询中做了很多繁重的工作。

想象一下尝试在您最喜欢的数据框 API 中表达这种逻辑；这将非常困难且容易出错。该库需要为所有哈希连接自动实现此优化。连接过滤器下推优化可以将查询性能提高 10 倍，因此在决定使用哪种分析系统时，它应该是一个关键因素。

如果您使用数据框库，如 collapse、pandas、data.table、modin，那么您很可能无法享受查询优化技术的好处。这意味着您的优化需要手动应用，如果您的数据开始发生变化，这是不可持续的。此外，您很可能以命令式的方式编写代码，使用特定于数据框库的语法。这意味着负责分析数据的脚本的可移植性不高。另一方面，SQL 的编写可能更直观，因为它是一种声明式语言，并且可以移植到几乎任何其他数据库系统。

所有优化器摘要

以下是 DuckDB 应用的所有优化规则的非详尽列表。

表达式重写器

表达式重写器简化了每个运算符中的表达式。有时，查询会使用未完全计算的表达式编写，或者可以以利用执行引擎中的功能的方式重写它们。下面是一个常见表达式重写的表以及负责它们的优化规则。许多这些规则重写表达式以使用专门的 DuckDB 函数，因此在执行期间表达式的评估速度更快。如果可以在优化器阶段将表达式评估为 true，则无需将原始表达式传递给执行引擎。此外，优化后的表达式更有可能使 DuckDB 能够进一步改进查询计划。例如，“移动常量”规则可以使过滤器下推发生。

过滤器上拉 & 过滤器下推

上面简要解释了 过滤器下推。过滤器上拉对于识别可以在其他表中对列应用过滤器的情况也很重要。例如，下面的查询从 t1 和 t2 中扫描列 a。t1.a 有一个过滤器，但在相等条件 t1.a = t2.a 存在的情况下，t2.a 可以具有相同的过滤器。例如

SELECT *
FROM t1, t2
WHERE t1.a = t2.a
  AND t1.a = 50;

可以优化为

SELECT *
FROM t1, t2
WHERE t1.a = t2.a
  AND t1.a = 50
  AND t2.a = 50;

过滤器上拉将过滤器 t1.a = 50 拉到连接上方，当再次下推过滤器时，优化规则会识别出该过滤器可以应用于 t1.a 和 t2.a 这两列。

IN 子句重写器

如果存在带有 IN 子句的过滤器，有时可以重写它以使执行更有效。以下是一些示例

此外，IN 子句重写器会将昂贵的 IN 表达式转换为 MARK 连接。如果查询具有类似 c1 IN (x1, ..., xn) 的表达式，其中 n 很大，则为表中的每一行评估此表达式可能会很昂贵。运行时将为 O(n * m)，其中 n 是行数，m 是列表的长度。IN 子句重写器会将表达式转换为 SELECT c1 FROM t1, VALUES (x1, ..., xn) t(c0) WHERE c1 = c0，将表达式转换为 HASH 连接，该连接可以在 O(n + m) 时间内完成！

连接顺序优化器

连接顺序优化器可以通过限制在连接之间处理的中间元组的数量来提供巨大的性能优势。通过处理更少的中间元组，查询可以更快地执行。

统计信息传播

统计信息传播是另一种即使在数据状态发生变化时也能工作的优化。通过遍历查询计划并记录所有相等连接条件，统计信息传播优化器可以通过检查最终连接的列的统计信息来创建新的过滤器。例如，假设 t1.a 和 t2.a 将与相等条件 t1.a = t2.a 连接。如果我们的内部统计信息告诉我们 t1.a 的最大值为 50，最小值为 25，则优化器可以在扫描表 t2 时创建一个新的过滤器。过滤器将为 t2.a >= 25 AND t2.a <= 50。

重新排序过滤器

如果列上有多个过滤器，则执行这些过滤器的顺序也很重要。最好首先执行最有效的过滤器，将昂贵的过滤器的执行保存到以后。例如，DuckDB 可以非常快速地评估相等性。因此，对于像 ... WHERE a = 50 AND md5(b) LIKE '%d77%' 这样的查询，优化器将告诉 DuckDB 首先评估每一列上的 a = 50。如果列 a 中的值通过了检查 a = 50，则 DuckDB 将评估列 b 中的值的 md5 哈希。

结论

编写良好的优化器可以在允许自由优化时提供显着的性能改进。优化器不仅可以应用人类可能自然忽略的许多优化规则，而且优化器还可以响应数据中的更改。一些优化可能会导致 100 倍的性能提升，这可能是决定使用分析系统 A 与分析系统 B 的区别。使用 DuckDB，所有优化规则都会自动应用于每个查询，因此您可以不断享受这些好处。希望这篇博文已经说服您下次听到下一个让大家兴奋不已的数据库时，考虑一下优化器。