版本

  • v1.3-ossivalis

背景

DuckDB 是一个面向分析型工作负载的嵌入式数据库，引擎采用 C++ 编写，整体模块划分清晰，源码注释也非常到位，十分适合作为学习 AP 型数据库的入门项目。为了追踪逻辑计划在引擎中的完整生命周期，本文基于 v1.3-ossivalis 分支，编译 Debug 版本并配合 GDB 进行断点调试，便于观察每个阶段的内部状态。

1
2
3
4
5
6
7
8
9
10
git clone -b v1.3-ossivalis https://github.com/duckdb/duckdb

GEN=ninja make debug -j 8

./duckdb
v1.3.0-dev2068 022f826ddf
Enter ".help" for usage hints.
Connected to a transient in-memory database.
Use ".open FILENAME" to reopen on a persistent database.
D

SQL Parser

DuckDB 使用 PostgreSQL 的语法解析器来完成词法/语法分析阶段，随后借助 DuckDB 内部的 Transformer 将 PostgreSQL 的解析树转换成 DuckDB 的语法树（Parser::ParseQuery 返回的 ParserResult）。这一阶段的职责仅限于构造 SQL 的抽象语法树（AST），但不涉及语义校验。

在 Parser 段落调试时，可以配合 PRAGMA parser 将 SQL 转换成 JSON，或者直接在 Parser::ParseQuery 附近打断点，观察 statements 向量的增长过程。DuckDB 的 AST 会保留原始 SQL 的很多细节(例如关键字位置、原始字符串)。

1
2
3
4
5
6
7
8
9
Parser parser(db->con->context->GetParserOptions());

/* parser.ParseQuery() 会解析 SQL 语句, 将 PG 格式的 parse tree 转为 DuckDB 的 tree. */
parser.ParseQuery(query);

/* ... */

/* SQL 的 binder, 逻辑计划生成, 调用优化器进行查询计划的优化, 物理计划生成. */
auto pending = db->con->PendingQuery(std::move(statements.back()), false);

Binder

DuckDB 选择将绑定（Binding）与逻辑计划的生成耦合在 Planner 模块中完成。与许多传统数据库类似，绑定阶段既是”语义审计员”，也是逻辑计划构造的起点，主要负责以下几类工作：

  • 校验 SELECT 列是否存在于作用域内；
  • 确认 WHERE、GROUP BY、ORDER BY 等子句的字段或表达式是否合法；
  • 为表、列、函数等对象分配 Binding 信息，便于后续阶段定位到具体的 Catalog 条目。

Binder::Bind 会将 QueryNode 绑定为 BoundQueryNode，同时生成逻辑计划的根节点。调试时可以在此处打断点，观察 BoundStatement::plan 如何从空指针逐步填充：

  • Binder 维护着当前作用域的 BindContext，每当遇到子查询或 CTE 时都会临时切换上下文并在返回时合并结果；
  • 常量表达式会在绑定阶段尝试下折叠，从而避免在逻辑计划阶段重复构造相同的表达式树；
  • 如果 SQL 含有参数（$1、? 等），Binder 也会在此阶段推导出参数类型，并写入 PreparedStatementData 供执行阶段使用。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
BoundStatement Binder::Bind(QueryNode &node) {
	BoundStatement result;
	if (node.type != QueryNodeType::CTE_NODE && // Issue #13850 - Don't auto-materialize if users materialize (for now)
	    !Optimizer::OptimizerDisabled(context, OptimizerType::MATERIALIZED_CTE) && context.config.enable_optimizer &&
	    OptimizeCTEs(node)) {
		switch (node.type) {
		case QueryNodeType::SELECT_NODE:
			result = BindWithCTE(node.Cast<SelectNode>());
			break;
		case QueryNodeType::RECURSIVE_CTE_NODE:
			result = BindWithCTE(node.Cast<RecursiveCTENode>());
			break;
		case QueryNodeType::CTE_NODE:
			result = BindWithCTE(node.Cast<CTENode>());
			break;
		default:
			D_ASSERT(node.type == QueryNodeType::SET_OPERATION_NODE);
			result = BindWithCTE(node.Cast<SetOperationNode>());
			break;
		}
	} else {
		/* 进行 binder 操作. */
		auto bound_node = BindNode(node);

		result.names = bound_node->names;
		result.types = bound_node->types;

		/* 逻辑计划生成. */
		result.plan = CreatePlan(*bound_node);
	}

	return result;
}

Logical Plan 逻辑计划

逻辑计划由一棵 LogicalOperator 树组成，每个算子节点描述一次逻辑运算（投影、过滤、JOIN、聚合等）。DuckDB 在算子层面贯彻了“结构即语义”的设计：算子类型、子节点列表与表达式集合共同定义了逻辑意图。LogicalOperator 的骨架如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class LogicalOperator {
public:
        explicit LogicalOperator(LogicalOperatorType type);

        LogicalOperator(LogicalOperatorType type, vector<unique_ptr<Expression>> expressions);

        virtual ~LogicalOperator();

        /* 当前逻辑算子类型. */
        LogicalOperatorType type;

        /* 子逻辑算子. */
        vector<unique_ptr<LogicalOperator>> children;

        /* 当前算子持有的表达式. */
        vector<unique_ptr<Expression>> expressions;

        /* ... */
};

为了便于调试，我们构造一张测试表，并插入一些示例数据。这些数据既覆盖了 NULL、数组、唯一约束等场景，也方便在断点状态下观察列裁剪、谓词传播等细节：

在阅读 LogicalOperator 时可以先关注以下几个小技巧：

  • 结合 LogicalOperator::ToString 输出的树形结构与下文的 ASCII 图，可以快速确认算子嵌套是否符合预期；
  • 当逻辑计划出现循环依赖或缺失列时，Verify 会立刻报错，因此开发调试阶段推荐始终在 Debug 模式下运行。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
D CREATE TABLE test_table (
      id INTEGER PRIMARY KEY,
      name VARCHAR,
      age INTEGER,
      is_active BOOLEAN,
      created_at TIMESTAMP,
      salary DECIMAL(10, 2),
      tags TEXT[],
      category VARCHAR,
      UNIQUE(name, category)
  );

D INSERT INTO test_table (id, name, age, is_active, created_at, salary, tags, category)
  VALUES
      (1, 'Alice', 30, TRUE, '2024-01-01 10:00:00', 50000.00, ARRAY['dev', 'manager'], 'A'),
      (2, 'Bob', 25, FALSE, '2024-01-02 11:00:00', 45000.00, ARRAY['designer'], 'B'),
      (3, 'Charlie', NULL, TRUE, '2024-01-03 12:00:00', 60000.00, NULL, 'A'),
      (4, 'David', 40, TRUE, '2024-01-04 13:00:00', 70000.00, ARRAY['dev', 'lead'], 'C'),
      (5, 'Eve', 35, FALSE, '2024-01-05 14:00:00', 55000.00, ARRAY['marketing'], 'B'),
      (6, 'Frank', 28, TRUE, '2024-01-06 15:00:00', 48000.00, ARRAY['dev'], 'A'),
      (7, 'Grace', 22, TRUE, '2024-01-07 16:00:00', 40000.00, NULL, 'C'),
      (8, 'Hank', 33, FALSE, '2024-01-08 17:00:00', 49000.00, ARRAY['designer'], 'B'),
      (9, 'Ivy', 27, TRUE, '2024-01-09 18:00:00', 52000.00, ARRAY['dev'], 'A'),
      (10, 'Jack', 31, TRUE, '2024-01-10 19:00:00', 58000.00, ARRAY['lead'], 'C');

开启 PRAGMA explain_output = 'all' 后可以同时查看逻辑计划与物理计划。如下查询的未优化逻辑计划包含三个算子，我们可以借助它来快速验证逻辑树结构与列绑定是否符合预期：

1
2
D PRAGMA explain_output = 'all';
D EXPLAIN SELECT * FROM test_table WHERE age > 30;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
┌─────────────────────────────┐
│┌───────────────────────────┐│
││ Unoptimized Logical Plan  ││
│└───────────────────────────┘│
└─────────────────────────────┘
┌───────────────────────────┐
│         PROJECTION        │
│    ────────────────────   │
│        Expressions:       │
│             id            │
│            name           │
│            age            │
│         is_active         │
│         created_at        │
│           salary          │
│            tags           │
│          category         │
└─────────────┬─────────────┘
┌─────────────┴─────────────┐
│           FILTER          │
│    ────────────────────   │
│        Expressions:       │
│(age > CAST(30 AS INTEGER))│
└─────────────┬─────────────┘
┌─────────────┴─────────────┐
│          SEQ_SCAN         │
│    ────────────────────   │
│     Table: test_table     │
│   Type: Sequential Scan   │
└───────────────────────────┘
  • LOGICAL_PROJECTION：对应 SELECT 列表，负责输出最终的列集；
  • LOGICAL_FILTER：表达式为 age > 30，对扫描结果做行级过滤；
  • LOGICAL_GET：数据源算子，从 test_table 顺序扫描数据。

更多算子类型可以参考 logical_operator_type.hpp。

Logical Plan 生成

逻辑计划生成的核心入口是 Binder::CreatePlan(BoundSelectNode &statement)。函数内部按照 SQL 子句的语义顺序构建算子树，整体遵循“自下而上拼装子树、再逐层加壳”的思路：

  1. FROM 子句：BoundSelectNode::from_table 在绑定阶段已经转换成相应的 LogicalGet 或其他子查询算子，作为整个算子树的初始根节点。
  2. SAMPLE：若存在 USING SAMPLE 语法，将 LogicalSample 包裹在当前根节点外层。
  3. WHERE：使用 PlanFilter 将过滤谓词包装为 LogicalFilter，并挂在现有根节点之上。
  4. GROUP BY / 聚合：当存在聚合或分组时，提前遍历子查询并生成 LogicalAggregate；Grouping Sets、Grouping Functions 等高级语法也在此处处理。
  5. HAVING：再次生成 LogicalFilter，与 WHERE 类似，只是输入来自聚合结果。
  6. 窗口函数与 QUALIFY：依次生成 LogicalWindow 和 LogicalFilter，并处理其中可能嵌套的子查询。
  7. UNNEST：针对 LATERAL 或 UNNEST 场景，构造 LogicalUnnest。
  8. SELECT 列表与投影：遍历 select_list 处理子查询后，创建 LogicalProjection 作为新的根节点。
  9. ORDER BY / LIMIT / DISTINCT：调用 VisitQueryNode 追加排序、去重、限制行数等算子。
  10. 列裁剪：若 need_prune 标记为 True，插入额外的 LogicalProjection 以仅保留需要的列。

对应源码片段如下 (省略与主题无关的细节):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
unique_ptr<LogicalOperator> Binder::CreatePlan(BoundSelectNode &statement) {
	unique_ptr<LogicalOperator> root;
	D_ASSERT(statement.from_table);

	/* 在通用查询中，物理存储表的 LogicalOperator 是 LogicalOperatorType::LOGICAL_GET,
	 * LOGICAL_GET 会在 SELECT 语句 binder 阶段就被生成. */
	root = CreatePlan(*statement.from_table);
	D_ASSERT(root);

	/* 处理 samples 语句: DuckDB 支持采样语法
	 * SELECT * FROM tbl USING SAMPLE 10% (选择表大约 10% 的样本). */
	if (statement.sample_options) {
		root = make_uniq<LogicalSample>(std::move(statement.sample_options), std::move(root));
	}

	/* 处理 where 条件. */
	if (statement.where_clause) {
		root = PlanFilter(std::move(statement.where_clause), std::move(root));
	}

	/* 聚合算子. */
	if (!statement.aggregates.empty() || !statement.groups.group_expressions.empty()) {
		if (!statement.groups.group_expressions.empty()) {
			// visit the groups
			for (auto &group : statement.groups.group_expressions) {
				PlanSubqueries(group, root);
			}
		}
		// now visit all aggregate expressions
		for (auto &expr : statement.aggregates) {
			PlanSubqueries(expr, root);
		}
		// finally create the aggregate node with the group_index and aggregate_index as obtained from the binder
		auto aggregate = make_uniq<LogicalAggregate>(statement.group_index, statement.aggregate_index,
		                                             std::move(statement.aggregates));
		aggregate->groups = std::move(statement.groups.group_expressions);
		aggregate->groupings_index = statement.groupings_index;
		aggregate->grouping_sets = std::move(statement.groups.grouping_sets);
		aggregate->grouping_functions = std::move(statement.grouping_functions);

		aggregate->AddChild(std::move(root));
		root = std::move(aggregate);
	} else if (!statement.groups.grouping_sets.empty()) {
		// edge case: we have grouping sets but no groups or aggregates
		// this can only happen if we have e.g. select 1 from tbl group by ();
		// just output a dummy scan
		root = make_uniq_base<LogicalOperator, LogicalDummyScan>(statement.group_index);
	}

	/* 处理 having 语句, 使用 LogicalFilter 过滤算子. */
	if (statement.having) {
		PlanSubqueries(statement.having, root);
		auto having = make_uniq<LogicalFilter>(std::move(statement.having));

		having->AddChild(std::move(root));
		root = std::move(having);
	}

	/* 处理窗口函数语句. */
	if (!statement.windows.empty()) {
		auto win = make_uniq<LogicalWindow>(statement.window_index);
		win->expressions = std::move(statement.windows);
		// visit the window expressions
		for (auto &expr : win->expressions) {
			PlanSubqueries(expr, root);
		}
		D_ASSERT(!win->expressions.empty());
		win->AddChild(std::move(root));
		root = std::move(win);
	}

	/* 处理 QUALIFY 语句, QUALIFY 是针对窗口函数结果的过滤. */
	if (statement.qualify) {
		PlanSubqueries(statement.qualify, root);
		auto qualify = make_uniq<LogicalFilter>(std::move(statement.qualify));

		qualify->AddChild(std::move(root));
		root = std::move(qualify);
	}

	/* Unnesting 算子. */
	for (idx_t i = statement.unnests.size(); i > 0; i--) {
		auto unnest_level = i - 1;
		auto entry = statement.unnests.find(unnest_level);
		if (entry == statement.unnests.end()) {
			throw InternalException("unnests specified at level %d but none were found", unnest_level);
		}
		auto &unnest_node = entry->second;
		auto unnest = make_uniq<LogicalUnnest>(unnest_node.index);
		unnest->expressions = std::move(unnest_node.expressions);
		// visit the unnest expressions
		for (auto &expr : unnest->expressions) {
			PlanSubqueries(expr, root);
		}
		D_ASSERT(!unnest->expressions.empty());
		unnest->AddChild(std::move(root));
		root = std::move(unnest);
	}

	/* 处理投影列. */
	for (auto &expr : statement.select_list) {
		/* 如果有子查询. */
		PlanSubqueries(expr, root);
	}

	/* 逻辑计划最上层为 LogicalProjection 投影算子. */
	auto proj = make_uniq<LogicalProjection>(statement.projection_index, std::move(statement.select_list)); auto &projection = *proj;
	proj->AddChild(std::move(root));
	root = std::move(proj);

	/* 处理 LIMIT, ORDER BY, DISTINCT 算子. */
	root = VisitQueryNode(statement, std::move(root));

	/* 处理需要剪枝的情况. */
	if (statement.need_prune) {
		D_ASSERT(root);
		vector<unique_ptr<Expression>> prune_expressions;
		for (idx_t i = 0; i < statement.column_count; i++) {
			prune_expressions.push_back(make_uniq<BoundColumnRefExpression>(
			    projection.expressions[i]->return_type, ColumnBinding(statement.projection_index, i)));
		}
		auto prune = make_uniq<LogicalProjection>(statement.prune_index, std::move(prune_expressions));
		prune->AddChild(std::move(root));
		root = std::move(prune);
	}

	return root;
}

通过上述流程可以看到，逻辑计划的生成并不是单纯的”语法树到逻辑树”的转换，而是伴随着大量的语义分析和子查询规划，确保每个算子都具备足够的上下文信息供后续优化与执行阶段使用。

Logical Plan Optimizer 逻辑计划优化

逻辑计划完成生成后, 我们需要对逻辑计划展开优化:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

/* src/main/client_context.cpp */

shared_ptr<PreparedStatementData>
ClientContext::CreatePreparedStatementInternal(ClientContextLock &lock, const string &query,
                                               unique_ptr<SQLStatement> statement,
                                               optional_ptr<case_insensitive_map_t<BoundParameterData>> values) {
    /* ... */

    if (config.enable_optimizer && logical_plan->RequireOptimizer()) {
		profiler.StartPhase(MetricsType::ALL_OPTIMIZERS);

		/* 进行逻辑计划的优化. */
		Optimizer optimizer(*logical_planner.binder, *this);
		logical_plan = optimizer.Optimize(std::move(logical_plan));

		D_ASSERT(logical_plan);
		profiler.EndPhase();

#ifdef DEBUG
		logical_plan->Verify(*this);
#endif
	}

    /* ... */
}

Optimizer::Optimize 的整体框架如下：

DuckDB 的逻辑优化器本质上是一个多阶段的规则引擎：首先应用表达式重写（常量折叠、谓词归并等），随后执行逻辑层的算子改写（谓词下推、JOIN 重排、列裁剪），最后再把控制权交给扩展点，让用户注入自定义的优化规则。每个阶段都通过 RunOptimizer 计时，配合 EXPLAIN ANALYZE 中的 Profile 信息可以精确定位耗时的规则。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
unique_ptr<LogicalOperator> Optimizer::Optimize(unique_ptr<LogicalOperator> plan_p) {
	Verify(*plan_p);

	this->plan = std::move(plan_p);

	/* 用户自定义的优化规则. */
	for (auto &pre_optimizer_extension : DBConfig::GetConfig(context).optimizer_extensions) {
		RunOptimizer(OptimizerType::EXTENSION, [&]() {
			OptimizerExtensionInput input {GetContext(), *this, pre_optimizer_extension.optimizer_info.get()};
			if (pre_optimizer_extension.pre_optimize_function) {
				pre_optimizer_extension.pre_optimize_function(input, plan);
			}
		});
	}

	/* Built-in 优化规则. */
	RunBuiltInOptimizers();

	/* 用户自定义的优化规则. */
	for (auto &optimizer_extension : DBConfig::GetConfig(context).optimizer_extensions) {
		RunOptimizer(OptimizerType::EXTENSION, [&]() {
			OptimizerExtensionInput input {GetContext(), *this, optimizer_extension.optimizer_info.get()};
			if (optimizer_extension.optimize_function) {
				optimizer_extension.optimize_function(input, plan);
			}
		});
	}

	Planner::VerifyPlan(context, plan);

	return std::move(plan);
}

DuckDB 内置了很多启发式规则, 其中内置的优化规则包括:

  • EXPRESSION_REWRITER: 表达式重写.

表达式重写是 Optimizer 初始化时构造函数里就填好的规则, 包括常量折叠, 分配律优化, CASE 语句简化等等.

  • FILTER_PULLUP: 谓词上拉.

我们以下面这个 SQL 为例, FILTER_PULLUP 优化会将 vals1.i=5 提至FILTER算子下方, 方便后续的谓词下推:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
D explain SELECT * FROM (SELECT * FROM vals1, vals2 WHERE vals1.i=5) as tbl1,
                (SELECT * FROM vals1, vals2) as tbl2
  WHERE tbl1.i=tbl2.i;

┌─────────────────────────────┐
│┌───────────────────────────┐│
││ Unoptimized Logical Plan  ││
│└───────────────────────────┘│
└─────────────────────────────┘
┌───────────────────────────┐
│         PROJECTION        │
│    ────────────────────   │
│        Expressions:       │
│             i             │
│            i_1            │
│             i             │
│            i_1            │
└─────────────┬─────────────┘
┌─────────────┴─────────────┐
│           FILTER          │
│    ────────────────────   │
│    Expressions: (i = i)   │
└─────────────┬─────────────┘
┌─────────────┴─────────────┐
│       CROSS_PRODUCT       │
│    ────────────────────   ├───────────────────────────────────────────┐
└─────────────┬─────────────┘                                           │
┌─────────────┴─────────────┐                             ┌─────────────┴─────────────┐
│         PROJECTION        │                             │         PROJECTION        │
│    ────────────────────   │                             │    ────────────────────   │
│        Expressions:       │                             │        Expressions:       │
│             i             │                             │             i             │
│             i             │                             │             i             │
└─────────────┬─────────────┘                             └─────────────┬─────────────┘
┌─────────────┴─────────────┐                             ┌─────────────┴─────────────┐
│           FILTER          │                             │       CROSS_PRODUCT       │
│    ────────────────────   │                             │    ────────────────────   │
│        Expressions:       │                             │                           ├──────────────┐
│  (i = CAST(5 AS INTEGER)) │                             │                           │              │
└─────────────┬─────────────┘                             └─────────────┬─────────────┘              │
┌─────────────┴─────────────┐                             ┌─────────────┴─────────────┐┌─────────────┴─────────────┐
│       CROSS_PRODUCT       │                             │          SEQ_SCAN         ││          SEQ_SCAN         │
│    ────────────────────   │                             │    ────────────────────   ││    ────────────────────   │
│                           ├──────────────┐              │        Table: vals1       ││        Table: vals2       │
│                           │              │              │   Type: Sequential Scan   ││   Type: Sequential Scan   │
└─────────────┬─────────────┘              │              └───────────────────────────┘└───────────────────────────┘
┌─────────────┴─────────────┐┌─────────────┴─────────────┐
│          SEQ_SCAN         ││          SEQ_SCAN         │
│    ────────────────────   ││    ────────────────────   │
│        Table: vals1       ││        Table: vals2       │
│   Type: Sequential Scan   ││   Type: Sequential Scan   │
└───────────────────────────┘└───────────────────────────┘

FILTER_PULLUP 优化后的逻辑计划:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
┌─────────────────────────────┐
│┌───────────────────────────┐│
││ Unoptimized Logical Plan  ││
│└───────────────────────────┘│
└─────────────────────────────┘
┌───────────────────────────┐
│         PROJECTION        │
│    ────────────────────   │
│        Expressions:       │
│             i             │
│            i_1            │
│             i             │
│            i_1            │
└─────────────┬─────────────┘
┌─────────────┴─────────────┐
│           FILTER          │
│    ────────────────────   │
│    Expressions: (i = i)   │
└─────────────┬─────────────┘
┌─────────────┴─────────────┐
│           FILTER          │
│    ────────────────────   │
│    Expressions: (i = 5)   │  /* 将谓词条件 vals1.i=5 提升至这里. */
└─────────────┬─────────────┘
┌─────────────┴─────────────┐
│       CROSS_PRODUCT       │
│    ────────────────────   ├───────────────────────────────────────────┐
└─────────────┬─────────────┘                                           │
┌─────────────┴─────────────┐                             ┌─────────────┴─────────────┐
│         PROJECTION        │                             │         PROJECTION        │
│    ────────────────────   │                             │    ────────────────────   │
│        Expressions:       │                             │        Expressions:       │
│             i             │                             │             i             │
│             i             │                             │             i             │
└─────────────┬─────────────┘                             └─────────────┬─────────────┘
              │                                           ┌─────────────┴─────────────┐
              │                                           │       CROSS_PRODUCT       │
              │                                           │    ────────────────────   │
              │                                           │                           ├──────────────┐
              │                                           │                           │              │
              │                                           └─────────────┬─────────────┘              │
┌─────────────┴─────────────┐                             ┌─────────────┴─────────────┐┌─────────────┴─────────────┐
│       CROSS_PRODUCT       │                             │          SEQ_SCAN         ││          SEQ_SCAN         │
│    ────────────────────   │                             │    ────────────────────   ││    ────────────────────   │
│                           ├──────────────┐              │        Table: vals1       ││        Table: vals2       │
│                           │              │              │   Type: Sequential Scan   ││   Type: Sequential Scan   │
└─────────────┬─────────────┘              │              └───────────────────────────┘└───────────────────────────┘
┌─────────────┴─────────────┐┌─────────────┴─────────────┐
│          SEQ_SCAN         ││          SEQ_SCAN         │
│    ────────────────────   ││    ────────────────────   │
│        Table: vals1       ││        Table: vals2       │
│   Type: Sequential Scan   ││   Type: Sequential Scan   │
└───────────────────────────┘└───────────────────────────┘
  • FILTER_PUSHDOWN: 谓词下推

FILTER_PULLUP 将过滤条件提至了上端, FILTER_PUSHDOWN 搜集这些过滤条件下推到底层投影列, 这样在 SQL 执行的过程中可以提早的过滤数据, 减少 CPU 和 IO 的开销.

  • EMPTY_RESULT_PULLUP,

  • CTE_FILTER_PUSHER,

  • REGEX_RANGE,

  • IN_CLAUSE,

  • JOIN_ORDER:

    JOIN_ORDER 优化方法主要目标是重新排列多表 JOIN 的顺序，以获得最优的查询执行性能.

  • DELIMINATOR,

  • UNNEST_REWRITER,

  • UNUSED_COLUMNS,

  • STATISTICS_PROPAGATION,

  • COMMON_SUBEXPRESSIONS,

  • COMMON_AGGREGATE,

  • COLUMN_LIFETIME,

  • BUILD_SIDE_PROBE_SIDE,

  • LIMIT_PUSHDOWN:

    LIMIT_PUSHDOWN 优化是将 LIMIT 操作符下推到 PROJECTION 操作符之下，以减少不必要的行处理和提高查询性能.

  • TOP_N:

    针对 ORDER BY ... LIMIT 的查询，将排序限制在 Top-N 元素范围内执行，避免对全部数据排序。

  • COMPRESSED_MATERIALIZATION:

    在物化中保留压缩格式，仅在必要时解压以减少内存带宽和缓存占用。

  • DUPLICATE_GROUPS:

    在聚合之前检测并消除重复的分组键组合，降低 GROUP BY 需要处理的行数。

  • REORDER_FILTER:

    调整同一节点下多个过滤条件的顺序，优先执行选择性更高的条件以尽早裁剪数据。

  • SAMPLING_PUSHDOWN:

    将采样操作下推到扫描算子，从数据源直接获取样本行，缩短上层管线等待时间。

  • JOIN_FILTER_PUSHDOWN:

    将连接产生的过滤条件继续向下推送到参与连接的输入上，减少参与 JOIN 的候选行。

  • EXTENSION:

    为用户自定义或外部扩展预留的规则集合，可在此阶段注入定制优化。

  • MATERIALIZED_CTE:

    判断 CTE 是否需要物化，若可复用则缓存一次结果供多处引用，若仅使用一次则改为内联避免额外开销。

  • SUM_REWRITER: SUM() 聚合表达式的重写.

    官方注释里标明了具体的优化规则即: SUM(x + C) -> SUM(x) + C * COUNT(x), x 为某列字段, C 为常量:
    SUM(x + C) 需要对每列的数据先多一次加法, 每列数据额外引入了一条加法指令.
    SUM(x) 对一大列连续内存做加法, 可以使用 SIMD，比如 AVX 指令一轮处理8或16个元素, 然后使用一条乘法指令 C * count(X) 即可.

  • LATE_MATERIALIZATION:

    在列式执行中尽量延迟宽列或大对象的加载，等到真正需要输出阶段再取回具体字段。

这些规则以流水线的方式运行：例如在 FILTER_PULLUP 将谓词统一收集到上层后，FILTER_PUSHDOWN 会立刻尝试把同一组谓词重新分发到 LogicalGet、LogicalJoin 等算子上，从而达到“上提 → 分发 → 裁剪”的闭环。

总结

本文梳理了 DuckDB 在逻辑层面的执行流程：从 PostgreSQL Parser 得到 AST，到 Binder 绑定语义，再到 LogicalOperator 树的逐步构建，最后交由启发式优化器对计划进行重写。逻辑计划优化器仍然是 DuckDB 中最值得深挖的部分，例如谓词上下推、JOIN 重排、统计信息传播等策略都蕴含着大量实现细节。后续文章将针对其中几类优化算法展开更深入的源码分析。