4月17日-19日，全球规模最大的 PostgreSQL 会议之一——Postgres Conference 2024 在美国 San Jose 隆重举行，本届大会包含 Ops、Dev、Essentials 和 Google Cloud 四个 Track，话题围绕 PostgreSQL 内核、数据库管理与应用、用户实例与经验等主题展开，邀请了来自谷歌、AWS、EDB、Yugabyte、DBeaver 等企业的资深讲师出席大会。拓数派凭借其强大的国际技术社区影响力，受邀作为会议赞助商参与本次盛会，并发表技术演讲。
在大会中，PieCloudDB 技术专家 Richard Guo 作为新 PostgreSQL Contributor，受邀发表技术演讲《A high-level introduction to the query planner in PostgreSQL》，结合 PieCloudDB Database 优化器打造经验，从开发者的角度阐述 PostgreSQL 优化器的工作原理，并详细介绍查询树转换为计划树的过程。Richard 的演讲得到了参会观众的积极反馈，并进行了深入的互动和沟通。
数据库管理系统（DBMS）中，SQL 查询处理是一个复杂且关键的过程。对于 PostgreSQL，一条 SQL 语句从接收到执行一共需要经过下面五个主要步骤：
- 解析（Parser）： 负责检查语法错误并生成解析树（parser tree）；
- 分析（Analyzer）： 根据解析树进行语义分析，生成一棵查询树（query tree）；
- 重写（Rewriter）： 按照系统存在的规则对查询树进行重写；
- 规划/优化（Planner）： 基于查询树生成一棵执行效率最高的计划树（plan tree）；
- 执行（Executor）： 按照计划树中的顺序访问表和索引，执行相应查询。
对于同一个查询语句，一般可以由多种方式去执行，查询优化器作为数据库的重要组件，它的作用就是从每一种可能的执行方式中，找到代价最小的查询计划，并把它转换成可执行的计划树。
下面将着重介绍 PostgreSQL 查询处理过程中的规划/优化阶段，这也是整个流程中最重要以及最复杂的阶段。该过程一般被分为四个阶段：预处理阶段，扫描/连接优化阶段，扫描/连接之外的优化阶段以及后处理阶段。
1. 预处理阶段
在预处理阶段的早期一般会通过简化常量表达式（函数、布尔、CASE 等）、内联简单的 SQL 函数等方式，尽可能的简化查询。同时，还会通过把 IN, EXISTS 等类型的子查询转换为半连接、提升子查询以及把消除外连接（将其转换为内连接或反连接）等操作来简化连接树。
除了这些方法，在预处理阶段的后期还会采用多种优化方式，包括：
- 分发 WHERE 和 JOIN/ON 约束条件
- 构建等价类
- 收集关于连接顺序限制的信息
- 消除无用连接
- …
2. 扫描/连接优化阶段
扫描/连接优化阶段主要处理查询语句中 FROM 和 WHERE 部分，同时也会考虑 ORDER BY 的信息。这一部分都是由代价来驱动的。
该阶段首先为基表确定扫描路径，估计扫描路径的代价，然后利用动态规划和遗传算法，搜索整个连接顺序空间，生成连接路径。而在搜索连接顺序空间时，还需要考虑到由外连接带来的连接顺序的限制。
在动态规划中，连接搜索会按照如下的过程进行：
- 首先为每一个基表生成扫描路径
- 为所有可能的两个表的连接生成连接路径
- 为所有可能的三个表的连接生成连接路径
- 为所有可能的四个表的连接生成连接路径
- …
- 直到所有基表都连接在了一起
然而这个过程的代价是非常高的，n 个表的连接，理论上有 n! 个不同的连接顺序，遍历所有可能的连接顺序是不现实的。因此通常会使用一些启发式办法，减少搜索空间，对于不存在连接条件的表，尽量不做连接；把一个大的问题，分解成多个子问题，从而降低复杂度。
3. 扫描/连接之外的优化阶段
在该阶段优化器会优先处理 GROUP BY、聚集、窗口函数和 DISTINCT，再对集合（UNION/INTERSECT/EXCEPT）操作进行处理，最后再处理 ORDER BY。以上的每个步骤都会产生一个或多个路径，优化器会对这些路径基于代价进行筛选，并为筛选出的路径添加 LockRows，Limit 和 ModifyTable 节点。
4. 后处理阶段
在这一阶段，优化器需要把代价最小的路径转换成计划树，并且调整计划树中的一些细节：
- 展平子查询的范围表
- 把上层计划节点中的变量变成 OUTER_VAR 或 INNER_VAR 的形式，来指向子计划的输出
- 删除不必要的 SubqueryScan、Append、MergeAppend 等节点
做完这一步，优化器就得到了完整的计划树，并可以将该计划树交予执行器去执行，最终得到查询结果。
作为立足中国的高科技创新企业，拓数派近年来通过代码贡献、讲师布道、会议赞助与参与、生态合作等多种形式，深耕于国际开源技术与生态体系。未来，拓数派将不断拓宽国际视野，积极融入全球科技创新的浪潮，扩大国际影响力，打造为国际化的技术驱动型企业。
