前置知识语法树AST是Abstract Syntax Tree中文通常叫抽象语法树。在数据库里用户写的 SQL 文本会先经过词法分析和语法分析被转换成一种树形结构这棵树就是 AST。它描述的是 SQL 的语法结构而不是最终怎么执行。例如 SQLSELECT name, age FROM users WHERE age 18;可以抽象成一棵 ASTSelectStatement ├── SelectList │ ├── Column: name │ └── Column: age ├── From │ └── Table: users └── Where └── GreaterThan ├── Column: age └── Literal: 18它的意思是这是一个 SELECT 查询 查询的列是 name 和 age 查询的表是 users 过滤条件是 age 18AST 的作用主要有三个让数据库理解 SQL 的结构SQL 文本只是字符串数据库不能直接优化字符串必须先把它变成结构化形式。为语义分析做准备例如检查users表是否存在、age列是否存在、类型是否匹配、函数是否合法等。为逻辑计划生成做准备数据库会根据 AST 生成逻辑查询计划例如选择、投影、连接等关系代数表达式。可以把整个流程理解为SQL 文本 → 词法分析拆成 token → 语法分析生成 AST → 语义分析检查表名、列名、类型 → 逻辑计划关系代数表达式 → 逻辑优化查询重写 → 物理计划选择具体执行算法 → 执行简单说AST 是数据库把 SQL 从“字符串”变成“结构化语法表示”的第一步。它还不是执行计划只是 SQL 的语法骨架。逻辑查询计划逻辑查询计划是数据库把 SQL 的含义转换成的一种关系代数形式的操作树。它描述“要做哪些逻辑操作”但还不决定“具体用什么物理算法执行”。可以理解为SQL 文本 → AST 抽象语法树 → 语义分析 → 逻辑查询计划 → 逻辑优化 → 物理执行计划 → 执行1. 逻辑查询计划描述什么逻辑查询计划主要描述这些逻辑算子SQL 部分逻辑算子FROM表扫描WHERE选择 / 过滤σSELECT投影πJOIN连接⋈GROUP BY分组聚合γHAVING聚合后过滤DISTINCT去重ORDER BY排序LIMIT限制输出行数例如 SQLSELECT name FROM users WHERE age 18;可以转换成逻辑查询计划Projection[name] └── Selection[age 18] └── TableScan[users]用关系代数表示就是π_name(σ_age18(users))意思是从users表取数据过滤age 18的行只输出name列。2. 逻辑查询计划不是物理执行计划逻辑查询计划只说明做什么不说明怎么做。例如SELECT * FROM orders o JOIN customers c ON o.customer_id c.customer_id;逻辑查询计划可能是Join[o.customer_id c.customer_id] ├── TableScan[orders] └── TableScan[customers]它只说明要把orders和customers按条件连接起来。但它还没有决定用 Hash Join 还是 Nested Loop Join 先扫描 orders 还是先扫描 customers 用全表扫描还是索引扫描 是否并行执行 内存如何分配这些属于物理执行计划阶段。3. 逻辑查询计划和 AST 的区别AST 是 SQL 的语法结构逻辑查询计划是 SQL 的关系操作语义。同一个 SQLSELECT name FROM users WHERE age 18;AST 更像SelectStatement ├── SelectList │ └── Column: name ├── From │ └── Table: users └── Where └── GreaterThan ├── Column: age └── Literal: 18逻辑查询计划更像Projection[name] └── Selection[age 18] └── TableScan[users]区别是对比项AST逻辑查询计划表示内容SQL 的语法结构查询的关系代数操作更接近SQL 文本数据库内部执行语义关注点SELECT、FROM、WHERE怎么写扫描、过滤、投影、连接怎么组合是否可优化不方便直接优化适合做查询重写和逻辑优化4. 一个 JOIN 查询的例子SELECT c.name, o.amount FROM customers c JOIN orders o ON c.customer_id o.customer_id WHERE c.region Asia AND o.amount 100;初始逻辑查询计划可能是Projection[c.name, o.amount] └── Selection[c.region Asia AND o.amount 100] └── Join[c.customer_id o.customer_id] ├── TableScan[customers] └── TableScan[orders]关系代数表示π_c.name,o.amount( σ_c.regionAsia AND o.amount100( customers ⋈_c.customer_ido.customer_id orders ) )逻辑优化后可以变成Projection[c.name, o.amount] └── Join[c.customer_id o.customer_id] ├── Projection[c.customer_id, c.name] │ └── Selection[c.region Asia] │ └── TableScan[customers] └── Projection[o.customer_id, o.amount] └── Selection[o.amount 100] └── TableScan[orders]也就是π_c.name,o.amount( π_c.customer_id,c.name(σ_c.regionAsia(customers)) ⋈_c.customer_ido.customer_id π_o.customer_id,o.amount(σ_o.amount100(orders)) )这里做了两个重要优化选择下推先过滤行 投影下推先减少列5. 总结逻辑查询计划就是数据库把 SQL 转换成的“关系代数操作树”。它回答的是这个查询在逻辑上需要扫描哪些表、过滤哪些行、保留哪些列、执行哪些连接、做哪些聚合。但它还不回答具体用哪个索引、哪个连接算法、哪个扫描方式、多少并行度。这些要到物理执行计划阶段才决定。关系代数基础下面用一个大表总结关系代数基础符号符号名称作用输入输出SQL 对应示例说明R、S、T关系表示一张表或中间结果—一个关系表名 / 子查询Student关系可以理解为数据库中的表元组Tuple表中的一行—一行数据一行记录(1, Alice, 20)关系由多个元组组成属性Attribute表中的一列—一列字段列名name、age属性组成关系的 schemaσ_p(R)选择按条件筛选行一个关系R满足条件的行WHEREσ_age18(Student)横向筛选保留满足谓词p的元组π_A(R)投影选择需要的列一个关系R指定列组成的新关系SELECT 列π_name,age(Student)纵向裁剪经典关系代数中投影会去重R × S笛卡尔积两个关系的所有行两两组合两个关系组合后的关系FROM R, S/CROSS JOINStudent × Dept若R有 m 行、S有 n 行结果有m × n行R ⋈_p S条件连接 / θ 连接按条件连接两个关系两个关系满足连接条件的组合行JOIN ... ONStudent ⋈_Student.dept_idDept.dept_id Dept可理解为σ_p(R × S)R ⋈ S自然连接自动按同名属性连接两个关系按同名列匹配后的关系NATURAL JOINStudent ⋈ Dept会合并同名属性工程中要谨慎使用R ⟕_p S左外连接保留左表所有行右表无匹配则补 NULL两个关系左表完整保留的连接结果LEFT JOIN ... ONStudent ⟕_Student.dept_idDept.dept_id Dept不满足普通内连接的交换律R ⟖_p S右外连接保留右表所有行左表无匹配则补 NULL两个关系右表完整保留的连接结果RIGHT JOIN ... ONStudent ⟖_Student.dept_idDept.dept_id Dept可视为左右表交换后的左外连接R ⟗_p S全外连接保留左右两边所有行无匹配处补 NULL两个关系双方都完整保留的连接结果FULL OUTER JOINStudent ⟗_Student.dept_idDept.dept_id DeptSQL 支持情况因数据库而异R ⋉_p S半连接返回R中能在S找到匹配的行两个关系只包含左表属性的关系EXISTS/INStudent ⋉_Student.dept_idDept.dept_id Dept不输出右表列常用于子查询优化R ▷_p S反连接返回R中不能在S找到匹配的行两个关系只包含左表属性的关系NOT EXISTS/NOT INStudent ▷_Student.dept_idDept.dept_id DeptNOT IN受 NULL 影响实际优化要谨慎R ∪ S并合并两个关系的元组两个兼容关系出现在R或S中的元组UNIONπ_name(Student) ∪ π_name(Teacher)要求两个关系属性个数和类型兼容R ∩ S交取两个关系共同的元组两个兼容关系同时出现在R和S中的元组INTERSECTπ_name(Student) ∩ π_name(Teacher)不是所有数据库都直接支持INTERSECTR − S差从R中去掉也在S中的元组两个兼容关系属于R但不属于S的元组EXCEPT/MINUSπ_name(Student) − π_name(Teacher)不满足交换律即R − S ≠ S − Rρ_x(R)关系重命名给关系改名一个关系改名后的关系表别名ρ_S1(Student)常用于自连接ρ_{a/b}(R)属性重命名给属性改名一个关系改列名后的关系列别名ρ_{student_name/name}(Student)防止列名冲突或统一 schemaγ_G,F(R)分组聚合按属性分组并计算聚合函数一个关系聚合后的关系GROUP BYγ_dept_id,COUNT(*)(Student)G是分组列F是聚合函数δ(R)去重删除重复元组一个关系无重复元组的关系DISTINCTδ(Student)经典关系代数默认集合语义SQL 默认多重集语义τ_A(R)排序按属性排序一个关系有序结果ORDER BYτ_age DESC(Student)经典关系代数通常无序排序属于扩展算子LIMIT_n(R)限制行数只取前 n 行一个关系最多 n 行LIMIT/FETCH FIRSTLIMIT_10(Student)通常需要和排序一起使用才有确定意义attrs(R)属性集合表示关系R的所有列一个关系属性集合schemaattrs(Student)常用于描述规则前提attrs(p)谓词属性集合表示条件p用到的列一个谓词属性集合条件涉及列attrs(age 18) {age}常用于判断谓词能否下推p、q谓词过滤或连接条件表达式TRUE / FALSE / UNKNOWNWHERE/ONage 18SQL 中还要考虑 NULL 三值逻辑A ⊆ B子集表示属性集合包含关系两个集合布尔判断—{name} ⊆ {id,name,age}常用于投影规则前提≡等价表示两个表达式结果相同两个表达式等价关系查询重写σ_p(σ_q(R)) ≡ σ_{p AND q}(R)查询优化的理论基础最核心的几个符号口诀SQL 对应σ选行WHEREπ选列SELECT⋈连表JOINγ分组统计GROUP BY∪ / ∩ / −集合运算UNION / INTERSECT / EXCEPTρ改名别名AS回到顶部查询重写 / 逻辑优化回到顶部一、查询重写 / 逻辑优化阶段的作用在数据库系统中用户提交的是 SQL 查询而数据库内部通常不会直接执行 SQL 文本。SQL 会先被解析成一种内部表示例如SQL 语句 → 语法树 AST → 逻辑查询计划 → 关系代数表达式 → 物理执行计划