【分布式 OLAP 查询引擎】SQL 解析、分析与逻辑计划

一条 SELECT 在 Trino Coordinator 上首先不是「直接扫表」，而是经过 词法/语法分析 → 语义分析 → 逻辑计划（Logical Plan） 三关。逻辑计划仍是 代数树：描述「算什么关系」，尚未绑定 HashJoin 还是 MergeJoin、数据是否在本地节点。

本文拆解这三关的输入输出与常见算子节点，并对照 postgresql-kernel 第 9 篇 的 parse/rewrite/plan 边界。文末用 DuckDB 1.5.4 本机实测 EXPLAIN 与 Trino 476+ 官方文档 描述的 logical plan 结构对照（不粘贴未在本机运行的 Trino CLI 输出）。

环境：WSL2、i9-12900K / 32 GiB；DuckDB 1.5.4（Python 绑定）；无 Docker Trino。Trino 计划结构引用 Trino Documentation, EXPLAIN（476+）。

一、前端三阶段：从字符串到 LogicalPlan

flowchart LR
  TXT["SQL text"] --> LEX["Lexer"]
  LEX --> PAR["Parser → AST"]
  PAR --> ANA["Analyzer"]
  ANA --> LOG["LogicalPlan"]
  CAT["Catalog / Metadata"] --> ANA

Trino 源码入口（A 级）：SqlParser → Analyzer → LogicalPlanner（包路径以 476+ 为准，见 Trino Developer guide）。Spark SQL 对应 Parsed → Analyzed → Optimized Logical Plan（第 13 篇）。

二、Parser 与 AST

Parser 输出 抽象语法树（AST）：仍保留 SQL 表面结构（SELECT 列表、FROM 子句、WHERE），未绑定 catalog 中的物理表 OID/handle。

Trino 使用 手写 + ANTLR 混合 parser（文档 SQL support）；Calcite 提供可嵌入的 SqlParser 与 SqlNode AST，许多项目复用或借鉴其 SQL 方言扩展机制（第 3 篇）。

逻辑上 AST 节点示例：

Constant folding 之前：1 + 2 在 AST 里仍是表达式节点，不是 3。

三、Analyzer：Catalog 与语义

Analyzer consult Catalog（Trino：ConnectorMetadata；PG：pg_catalog）：

3.1 Catalog 三层命名

Trino：Catalog → Schema → Table（类似 PG 的 database/schema/table，但 catalog 常映射一个 connector 实例）。Connector 返回 TableHandle：引擎内不透明的表引用 + ColumnHandle 列表，供后续 layout 与 split 规划（第 8 篇）。

Iceberg 表在 catalog 侧还带 snapshot id、partition spec 等（lakehouse/08）；Analyzer 阶段通常只确认 表可读，layout 在 planner 后期结合 snapshot 解析。

3.2 与 PostgreSQL 对照

PG 的 rewrite 规则（如 RIR）在 OLAP 引擎中部分被 逻辑优化规则 取代（谓词下推、列裁剪），但 「先语义、后代数」 顺序一致。

四、LogicalPlan 核心算子

逻辑计划节点描述 关系变换，与物理实现解耦。Trino / Calcite 常见节点（名称因引擎略有差异）：

flowchart BT
  SCAN_O["TableScan orders"]
  SCAN_C["TableScan customer"]
  FIL["Filter<br/>o_orderdate >= ..."]
  JOIN["Join<br/>c_custkey = o_custkey"]
  AGG["Aggregate<br/>GROUP BY c_name"]
  LIM["Limit 10"]
  SCAN_O --> FIL
  FIL --> JOIN
  SCAN_C --> JOIN
  JOIN --> AGG
  AGG --> LIM

逻辑 Join 尚未指定 inner/outer 的实现算法；Filter 可能在优化后 下推 到 TableScan 附近（第 3 篇）。

五、Trino logical plan 文档结构（无本机输出）

Trino 支持：

EXPLAIN (TYPE LOGICAL, FORMAT TEXT) SELECT ...

官方文档说明 logical plan 片段包含 布局缩进的算子树，典型顶层为 Output，子节点为 Aggregate → InnerJoin → ScanFilter / TableScan 等（476+ EXPLAIN 一节）。Distributed plan（默认 EXPLAIN）在此基础上 插入 Exchange、LocalExchange，并划分 Fragment（第 12 篇）。

概念对照表（来源：Trino Documentation EXPLAIN，非 CLI 实测）：

本机 未运行 Trino 时，判读客户集群 plan 应 对照官方示例 + 第 12 篇字段说明，勿凭记忆编造 Fragment id 或 estimated rows。

六、DuckDB 1.5.4 实测：同一条 join SQL

实验脚本：reproduce/run_duckdb_experiments.py。数据：tpch.orders 100000 行、tpch.customer 5000 行（合成 TPCH 子集，非官方 sf）。

查询 q_join：

SELECT c.c_name, sum(o.o_totalprice)
FROM tpch.customer c
JOIN tpch.orders o ON c.c_custkey = o.o_custkey
WHERE o.o_orderdate >= DATE '1996-06-01'
GROUP BY c.c_name
LIMIT 10;

EXPLAIN 输出（经删减，保留结构）：

physical_plan
├─ PROJECTION
├─ LIMIT
├─ HASH_GROUP_BY
├─ PROJECTION
├─ HASH_JOIN
│  ├─ SEQ_SCAN
│  │  └─ Filters: o_orderdate>=1996-06-01
│  └─ SEQ_SCAN
└─ ...

要点：

q_filter：SELECT count(*) FROM tpch.orders WHERE o_custkey = 3 → 单表 SEQ_SCAN，估算 ~14286 行（\(100000/7\)，因 `o_custkey = (i ) + 1$）。

EXPLAIN ANALYZE（q_join，3 次 wall time 中位数）：0.0028 s（100k + 5k，WSL2，DuckDB 1.5.4）。该数字只说明 嵌入式引擎在小数据上 pipeline 极快；不可外推 Trino 集群延迟（含 network shuffle、connector latency）。

七、逻辑计划 vs 物理计划

DuckDB 默认 EXPLAIN 展示 已优化物理计划；Trino 需 TYPE LOGICAL 才看纯逻辑层。对比实验时应 统一层级（见下节）。

八、对照实验设计

拓扑一致时常见模式：Filter 下推 + Project 列裁剪 + Join 在 Filter 之上。差异常在 Iceberg 表 Scan 带 layout predicate（Trino）vs 内存 SEQ_SCAN（DuckDB）。

九、常见前端故障

分布式场景另增：跨 catalog join 需两 connector 均可用；schema drift（湖表 evolution）在 Analyzer 或 plan 阶段暴露（lakehouse/16）。

十、小结

SQL 前端把 字符串 变成 带类型的 LogicalPlan：Parser 管语法，Analyzer 管 catalog 与类型，Logical builder 管代数结构。Trino 与 DuckDB 节点命名不同，代数同构；Trino 额外在 distributed plan 引入 Exchange。

下一篇进入 Calcite 式规则优化与 Trino planner：RelNode、Rule、Volcano/Cascades 搜索如何改写逻辑树。

参考资料

1. Trino Documentation, EXPLAIN / Developer guide（476+）。
2. Apache Calcite Documentation, SQL to Rel。
3. DuckDB Documentation, EXPLAIN（1.5.4 本机实验）。
4. postgresql-kernel 第 9 篇（parse/rewrite）。
5. 本系列第 1 篇（IR 地图）。
6. post/db/query-engine/reproduce/run_duckdb_experiments.py（实验脚本）。

返回 系列目录 ｜ 上一篇：OLAP 全景 ｜ 下一篇：Calcite 与优化框架