SQL优化器庖丁解牛篇(一)

2018-02-25

打算写一个系列,讲一下 SQL 优化方面的东西。这一篇先整理一下要写内容。整个 SQL 优化器是一个很大的话题,不可能一二篇博客就能说得清楚的。所以这个系列得一点一点的写。

从输入一条 SQL 语句,到这条语句的执行,要经历很多阶段:将 SQL 解析成抽象语法树(AST),将 AST 变换到内部表示(IR)。然后优化器的输入就是 IR,它将生成最优的查询计划(Plan),然后会变成具体的执行器(Executor),里面有许多的算子。最的执行会获取数据,再给用户返回结果。

这个系列要专注的是从 IR 到生成 Plan 的过程。从大的方面,优化过程可以分为逻辑优化和物理优化两个部分。逻辑优化主要是基于规则的优化(RBO),物理优化会具体选择某一个算子具体的实现,比如 Join 用哪一种,读数据用哪一种,这里可能需要用到一些统计信息,决定哪一种方式代价最低,所以是基于代价的优化(CBO)。

在逻辑优化的步骤,我会挑一些具体的例子讲。比如,列裁剪,min/max消除,非关联子查询转 Join,谓词下推,投影消除,topN下推等等。

在物理优化里面,主要会写一下求最优解的算法,代价计算用到的公式,统计信息会提及一点,然后还打算写一下 join reorder。

执行器的部分不太涉及,如果所有内容都写话题就太大了,该是厚厚的一本书要讲的东西。感觉还是需要对执行器有一点点基础了解,像几种不同的 Join 的实现方式,像子查询的 Apply 算子,还有聚合 Aggregate 这些,完全不懂也是无法知道 SQL 到底是怎么被执行的。

好了,introduction 写完了,等下一篇再进入正题。

sql