我谈论查询优化器时谈论的内容（第一部分）：IR设计
内容提要
本文讨论了在The IR（Intermediate Representation）中设计SQL查询优化器的概念。它解释了查询优化器的概念以及为SQL设计不同IR的重要性。文章还涵盖了优化器中的设计模式，SQL IR中关系代数的表示以及关系和物理属性的推导。最后讨论了在The IR设计中使用本地和全局属性ID的优缺点。
延伸解读
SQL IR 设计中的命名难题与解决思路
文章通过多个示例展示了在 SQL IR 中使用名称表示属性时遇到的歧义问题，例如自连接中同名列的引用、自然连接中的列合并、以及内联视图导致的别名冲突。这些问题使得谓词下推等优化变得复杂，需要引入限定名和额外的重命名操作。作者指出，名称本身对优化并无帮助，反而增加了维护负担，最终引导出使用唯一 ID 替代名称的设计方向。
本地 ID 与全局 ID 的权衡
文章对比了两种属性 ID 设计：本地 ID 使用元组中的索引，优点是不依赖外部状态，但操作符转换时需要频繁重映射；全局 ID 通过全局生成器分配唯一 ID，优点是可以使用无序集合表示属性，便于集合运算和属性推导，但操作符树依赖外部上下文。作者以索引扫描和连接顺序优化为例，说明全局 ID 在复制操作符树时更复杂，但在大多数场景下更易用，并最终选择了全局 ID 设计。
属性推导与关系代数扩展
文章介绍了属性推导的过程：递归计算子节点的属性，再根据当前操作符计算自身属性。关系属性包括列信息、基数、统计信息等，物理属性包括顺序、并行度等。在实现 Project 和 Aggregate 的属性推导时，由于引入了派生列，传统关系代数不再足够，需要扩展定义。作者通过“村规”形式给出了 Project 和 Aggregate 的形式化定义，并指出派生列打破了所有数据源指向 Get 的约定，优化时需要更小心。
Q&A
什么是查询优化器？
查询优化器是数据库组件，负责优化查询的执行计划。不同数据库优化方法不同，有的直接重写AST，有的在AST lowering时转换，有的在查询执行时动态重写。为统一概念，文章将SQL解析器到执行器之间的所有部分统称为查询优化器。
为什么SQL需要设计中间表示（IR）？
SQL可以视为一种编程语言，关系数据库是执行SQL的虚拟机。查询优化器负责将SQL语句翻译成执行计划，就像编译器将Java代码翻译成字节码。为了进行各种分析和优化，需要为SQL设计不同的IR，类似于编译器中的HIR、MIR或LLVM IR。
SQL IR中如何表示关系代数？
SQL IR通常将SQL AST转换为关系代数表示，每个查询语句对应一个关系代数表达式。关系代数是递归树结构，节点称为操作符，整个操作符树称为查询计划。主流数据库如System R、DB2、Oracle、SQL Server、PostgreSQL和MySQL 8.0都采用关系代数表示，基于此开发优化和执行框架。
在SQL IR中，本地ID和全局ID有什么区别？
本地ID使用属性在元组中的索引作为ID，同一逻辑属性的ID会随操作符变化，优点是可从操作符树推断，无需外部状态，但转换操作符时需频繁重映射。全局ID维护全局ID生成器，为所有属性分配唯一ID，优点是与元组模式解耦，可用HashMap表示，便于属性推导和集合操作，但依赖外部状态，操作符树不能独立存在。
属性推导在SQL IR中有什么作用？
属性推导是分析和优化IR的重要步骤，通过递归计算子节点的属性来推导当前节点的属性。属性分为关系属性（如属性信息、基数、统计信息、约束、函数依赖）和物理属性（如顺序、并行度、数据分布、数据分区）。利用属性推导，可以应用关系代数定理优化IR并确保正确性。
为什么在SQL IR中引入标量表达式（ScalarExpr）？
最初Select谓词和Project表达式以字符串形式存在，无法满足分析和优化需求。直接使用AST的Expr节点缺乏类型信息、未解析标识符、子查询未处理。因此需要设计ScalarExpr，要求所有标识符解析为完全限定名，注入类型信息并进行类型检查，所有子查询转换为SQL IR形式。
