# 基于规则的查询重写/变换

## intro

blabla...

## industry

鉴于实际实际部署的应用程序性能直接由生产环境中的数据库优化和执行效率决定，我们在本节中将首先调研工业数据库中的查询优化规则。为了能从源代码的层面进行较为细致的分析，我们选择了“世界上最先进的开源数据库”PostgreSQL、“世界上最流行的开源数据库”MySQL、以及面向更广泛场景也更具有可拓展性的开源动态数据管理框架Apache Calcite。

一般地，从文本格式的SQL语句到最终的执行结果，数据库内部会进行SQL解析（parse）、优化（optimize）与规划（plan）、执行（execute）这三个阶段。其中SQL解析负责将文本格式的SQL语句转化为语法树，执行阶段负责将数据库中数据取出并按照此前优化与规划阶段产生的执行方案产生最终结果，两者与本文章主题关系较小而不在展开叙述。对于优化与规划阶段，通常又可以大致分为两类方法，其一是基于规则的、启发式的SQL重写，重写之后的SQL在语义上未发生改变，但得以更高效地执行；其二是基于代价的最优方案计算，例如采用动态规划或遗传算法等对多表JOIN的最优顺序进行求解。本文重点关注基于规则的查询重写，但需要注意的是部分数据库并没有对这两类方法进行清晰地划分，因此后一类方法也将简要提及，这个特点将在后文中具体展开描述。

### PostgreSQL

PostgreSQL中查询分为4个阶段进行处理，分别是解析（parse）、重写（rewrite）、优化（optimize）&规划（plan）、执行（execute）。

这里首先对其中的查询重写阶段进行解释。尽管从概念上它和基于规则的查询优化十分相似，它的输入是经解析后的SQL查询树和若干规则，输出是经过重写的SQL查询树；但它在功能上的默认行为与查询优化完全不存在关系。该模块的主要功能是用于实现视图（view），具体来说，当一个新的视图被创建时，如为表`mytab`创建一个视图，视图名为`myview`：

CREATE VIEW myview AS SELECT * FROM mytab;

实际上其内部实现是向规则系统中插入了一条规则，这条规则的内容是当对表`myview`进行查询时，将查询重写为查询表`mytab`：

CREATE TABLE myview (same column list as mytab);
CREATE RULE "_RETURN" AS ON SELECT TO myview DO INSTEAD
    SELECT * FROM mytab;

在用于实现视图功能之外，理论上数据库管理员可以向数据库中手动加入新的重写规则，以达到效率优化的目的，但是讨论数据库管理员手动添加的规则超出了本文章的讨论范围。因为PostgreSQL本身并不存在内置的为效率优化目的而添加的重写规则，这种情况下，重写阶段不会对不涉及视图的查询操作做任何变换，因此这里不再对此阶段进行过多的探讨。

TODO：上面的内容增加ref

TODO：PostgreSQL 15.1

TODO：介绍查询树对应的结构体 src/include/nodes/parsenodes.h struct Query

TODO：介绍优化&规划阶段的主要工作 src/backend/optimizer/plan/planner.c subquery_planner

### MySQL

MySQL中查询也分为4个阶段进行处理，但不同于PostgreSQL，这4个阶段分别是解析（parse）、分析（resolve）/准备（prepare）、优化（optimize）&规划（plan）、执行（execute）。

值得一提的是，MySQL中同样存在查询重写的功能，相应的逻辑再解析阶段后、分析/准备阶段前被触发，但和PostgreSQL类似，其默认情况下和查询优化完全无关，尽管其同样允许数据库管理员通过加载第三方重写插件的模式达到包括查询优化在内的各种目的。默认情况，重写的存在只是为了在打印日志时隐去SQL语句中的敏感信息（如用户密码，用“<secret>”字符串代替），这里不再过多赘述。

TODO：上面的内容增加ref

TODO：MySQL 8.0.31

TODO：介绍查询树对应的结构体 sql/sql_lex.h class Query_block 和 Query_expression

TODO：介绍分析/准备阶段涉及的查询重写 sql/sql_resolver.cc Query_block::prepare

TODO：介绍优化&规划阶段涉及的查询重写 sql/sql_optimizer.cc JOIN::optimize

### Apache Calcite

TODO: 介绍Apache Calcite相比传统数据库的特点（可拓展性强blabla...）

TODO：介绍Apache Calcite查询处理的阶段（待调研）

TODO：介绍Apache Calcite中的查询重写规则，以及使用的方法和特点

Apache Calcite待参考材料：
- https://calcite.apache.org/docs/tutorial.html 关注“Optimizing queries using planner rulesPermalink”
- https://github.com/michaelmior/calcite-notebooks/blob/master/query-optimization.ipynb 关注“FilterJoinRule”
- https://calcite.apache.org/javadocAggregate/org/apache/calcite/rel/rules/package-summary.html

[1]: https://www.postgresql.org/
[2]: https://www.mysql.com/
[3]: https://calcite.apache.org/
[4]: https://www.postgresql.org/docs/current/query-path.html
[5]: https://dev.mysql.com/doc/dev/mysql-server/latest/PAGE_SQL_Optimizer.html

## academic

### [VLDB'21] A Learned Query Rewrite System Using Monte Carlo Tree Search

blabla...

### [SIGMOD'22] WeTune: Automatic Discovery and Verification of Query Rewrite Rules

blabla...

### [SIGMOD'22] Optimizing Recursive Queries with Program Synthesis

blabla...

## discussion

blabla...