数据库内核杂谈(七):数据库优化器(上)

阅读数:1 2019 年 12 月 24 日 16:13

数据库内核杂谈(七):数据库优化器(上)

在上一篇文章中,我们挖了一个坑:在大部分情况下,HashJoin 都是表现最优的,那为什么还需要去支持其他 Join 比如 SortMergeJoin 或者 NestLoopJoin 的算子实现呢?因为不同表的大小,是否有索引支持,以及查询语句是否对某些 column 需要排序都会对执行算子产生影响,从而进一步影响执行时间。就是只看 HashJoin,hash 表到底是对表 A 来建,还是对表 B 来建,也会造成非常大的差别 (通常,我们选取数据量小的表来做 Hash 表,这能使得需要用到的内存更少,更小概率需要借助外部 Hash 表来进行分批次的 join)。而拥有最终决定权的,就是我们今天要聊的主角:数据库优化器 (Query Optimizer)。

首先来谈谈为什么叫优化器。它优化的又是什么呢?最常见的优化指标就是查询语句的运行时间,譬如上述例子中的 HashJoin,优化器选择用数据量小的表来建 Hash 表,运行时间就比选择用大的表要快。那我们再问深一层,为什么对应一个查询语句,可以优化执行时间?归根到底是因为 SQL 是一种 declarative language(声明式语言),它只是告知了数据库系统,它希望数据以什么形式返回,但并没有告诉系统,要怎么去一步一步执行算子来得到最终结果。这和我们通常使用的编程语言是有所不同的。比如用 C 语言写一个冒泡排序和快速排序,虽然最终排序结果一样,但是快速排序确实只用到了更少的比较和交换,所以性能比冒泡排序要快。因为算法交代了应该如何去排序 (当然,编译器还是可以进一步地来优化代码,比如 function-inline,dead code elimination 等等)。这就给了优化器变魔术的空间。

除了时间,还有什么可以优化的维度呢?比如计算资源,一个查询语句,需要发生多少次 IO,使用多少内存,总共运行多少个 CPU cycle,耗费了多少电量,等等。虽然,绝大部分情况下,这些资源都是正比于运行时间。再如,对于一个高并发的数据库系统,单个语句的运行时间可能并不是最好的优化指标,优化整体的吞吐量才是王道:相较于让每个语句都能在 5 秒内完成,可能更希望每 10 秒能运行完 100 个语句。

今天的内容我们主要围绕如何优化运行时间,因为对于单个语句优化执行时间,就已经是 NP-HARD 复杂度的问题了。不知大家是否还有印象,在讨论数据库执行模式的那章,我们简单介绍了整个数据库内核的架构,其中就谈到了优化器:优化器的输入是数据库的元数据以及语义绑定的语法树,输出是最终的物理算子的执行计划。那它内部又是怎么得到最终的物理算子的执行计划的呢?我们一步一步来看。

Query Rewrite (语句重写)

优化器的第一个阶段叫做 Query Rewrite(语句重写)。这个阶段,主要是对原来的语法树进行等价语义的重写,通常是根据预先定义好的规则来进行重写,优化掉一些无效或者无意义的操作。换句话说,有时候程序员写的 SQL 通常是结果导向的,并不专门针对执行去优化,而且,很多时候还会有意无意引入无意义的操作。你可能会纳闷,怎么会呢?一起来看一些简单的示例。

复制代码
SELECT
    class.name AS class_name,
    student.name AS student_name, 
    student.id AS student_id
FROM
    class, student
WHERE   
    class.id = student.class_id AND   
    student.name = 'ZhangSan';

上述语句返回这个学校所有叫 ZhangSan 的学生的姓名,学号,以及班级。那这样一个语句转换成语法树应该是下面这个形式:

数据库内核杂谈(七):数据库优化器(上)

Logical Operator Tree

这里我用了简单的关系型代数模型符号来表达语法树的逻辑算子,只用到了最基本的 projection,equality join,和 filtering operator。看了这个语法树,你可能觉得,没毛病啊,语义正确。但是,如果直接把这个语法树转换成物理算子的执行计划,就会发现可以优化的地方了。我们自下而上地来看。首先执行计划要求扫描全表 class 和表 student,然后对其进行 Join,join 条件是 class.id = student.class_id。join 完之后,对于 tuple 进行 filter,filter 条件是 student.name = ‘ZhangSan’。最后,对于 filter 后的 tuple,进行 projection,只有 3 个 column 作为输出 class.name, student.name 和 student.id。

可能看完了这个执行计划的流程,读者依然会说,没毛病啊。其实不然。比如,对于 class 表,总共只用到了两个 column:id 和 name,因此我们可以在读取表的时候直接进行 projection。一是,相对于把整个表全部读取放进内存中,只读取 2 个 column 所需的内存要少很多。另外,如果考虑到使用列存形式存储数据,只读两个 column 和读取全部的 column 速度上也快很多。这里,我们引出了第一个语句重写的规则:Projections push down。通过把用到的哪些 column 往下推送直到叶节点的 table scan,可以减少扫描后数据的大小,同时也可以提升扫描速度。同样的,我们也可以对学生表的读取进行优化,学生表只用到了 id, class_id, 和 name column。更进一步的是,对于学生表,除了 projections push down,我们还能把 filter predicates 也往下推送。因为最终的结果里面只需要姓名为’ZhangSan’的学生,与其把所有的学生信息都读取进来和 class 表进行 join,我们可以先 filter 掉其他的学生,使得 join 的数据大大减少 (假设叫’ZhangSan’的同学应该不会很多)。这便是我们提到的第二个重写规则:Predicates push down。通过把 filter predicates 往下推送,以减少后续操作的数据量。经过这两步的改写,新的语法树变成了如下这个形式:

数据库内核杂谈(七):数据库优化器(上)

new logical operator tree with projections/predicates push down

通过上述两个重写规则,我们使得自下而上读取的数据量减小到最少,继而减少后续处理的数据量,以此来优化执行时间。并且,这些重写规则,属于有百利而无一弊,只要规则允许,就应该进行重写。有读者可能有疑问了,这些语句重写能带来多少运行速度的提高呢?这完全取决于表的大小,数据分布和查询语句。试想,如果把 student 表换做是一个有万亿数据的超级大表,通过 Predicates push down,可能最后只保留了几行数据。并且,由于 Predicates push down,优化器可能会选择使用 IndexScan 而非全表扫描 (如果对应的 Predicate column 有建立相应的 index),这进一步极大提高了表读取速度,此为后话,暂且不表。

这些重写规则都是提前实现好了,在对语法树进行分析的时候,如果满足了某类触发条件,就会加载相应的重写规则。下面,我们再来看一些常见的重写规则。查询语句如下图所示:

复制代码
SELECT * FROM super_large_table WHERE 1 = 0;

对 SQL 比较熟悉的读者可能一眼就看出来了,由于 where condition 的 predicate 始终为 false,所以无论这个表有多大,最终结果都为空集。通过引入重写规则 Impossible/Unnecessary Predicates: 计算出 Predicates 的值,如果值衡为 false,直接返回空集;如果值衡为 true,直接去掉 predicates。相对应的语法树发生如下变化:

数据库内核杂谈(七):数据库优化器(上)

original logical operator tree

重写后变为

数据库内核杂谈(七):数据库优化器(上)

new logical operator tree

这类规则有点类似传统编译器里的 constant folding/propagation 和 dead code elimination 的优化策略:试图在编译阶段就确定 predicates 的值,以此来简化 expression。虽然上述的例子很简单,但有些查询语句的 predicates 会很复杂,优化器是否足够 " 聪明 " 作出优化,是考验优化器的一个标准。 笔者曾经对不同的数据库进行过比较,每一款优化器支持的语句重写规则都不同,正所谓没有比较就没有伤害!有时候会觉得,某某优化器怎么那么“笨”,连这个都看不出来。曾有个前辈这样说过,那些商用数据库之所以贵,就贵在优化器的聪明上。最后,我们一起来看几个并不是非常显而易见的重写规则。

示例查询语句 1:

复制代码
SELECT * FROM table1
WHERE
    val BETWEEN 1 AND 50   
    OR val BETWEEN 45 AND 100;

通过 Merge predicates 重写规则,可以改写成如下 (介于查询语句也能很好地体现重写后的效果,直接上 SQL):

复制代码
SELECT * FROM table1
WHERE val BETWEEN 1 AND 100;

优化器把多个 predicates 合并到了一起。

示例查询语句 2:

复制代码
SELECT * FROM table1 AS t1
WHERE EXISTS (
    SELECT * FROM table1 AS t2
    WHERE t1.id = t2.id
);

这个就有点复杂啦,如果优化器能察觉到 EXISTS 中的查询条件其实是 table1 的 self join,这样 condition 就总是为 true,所以可以被重写为:

复制代码
SELECT * FROM table1;

再来看一个类似的示例语句 3:

复制代码
SELECT t1.*
FROM
    table1 AS t1
JOIN
    table1 AS t2
ON t1.id = t2.id;

因为依然是 table1 的 self join,所以通过 join elimination 重写规则,可以直接改写为如下:

复制代码
SELECT * FROM table1;

最后,来看一个不一样地去掉无意义语句的重写。示例语句如下:

复制代码
SELECT
    id, name, class_id
FROM (
    SELECT * FROM students
    ORDER BY id
) t
ORDER BY class_id;

不知道读者是否看出了这句语句中的无效操作,即 inner 语句中的 ORDER BY id。因为在 outter 语句中已经申明了以 class_id 排序的要求,内部的排序即可视为无效语句。聪明的优化器可以直接将其改写成:

复制代码
SELECT
    id, name, class_id
FROM
    students
ORDER BY
    class_id;

类似的语句重写规则还有很多很多,优化器也会根据查询语句的侧重点,来实现特定的语句重写。留个问题给大家,还能想到哪些显而易见的语句重写规则吗?

总结

总结一下,优化器引入了事先编写好的语句重写规则,在编译语法树的过程中,通过触发规则来加载语句重写规则,从而简化语句,去掉无意义的语句,以及通过 Predicates push down, Projectsions push down 来优化数据读取。这些规则虽然有时候能大大简化语句,提升执行速度,但对于复杂的多表查询语句,显然是不够的。 比如下面这个示例语句:

复制代码
SELECT
    t1.a,
    t2.b,
    t3.c,
    ...
    tn.x
FROM
    table1 AS t1,
    table2 AS t2,
    table3 AS t3,
    ...
    tablen AS tn
WHERE
    t1.a = t2.aa AND
    t2.b = t3.cc OR
    ...;

上述这句语句的复杂度在于,有 n 个表同时 join 在一起。对于表和表的 Join relation,是可传递且可交换的。即:

复制代码
table1 JOIN table2 = table2 JOIN table1
(table1 JOIN table2) JOIN table3 = table1 JOIN (table2 JOIN table3)

那上述 n 个表的 join,表达成两两 join 的关系后,一共有多少种可能性呢? 我这里直接给出结果,大致会有 4^n(4 的 n 次方) 种可能。要在那么多种可能中找到最优的 join ordering,已经是 NP-HARD 的问题。那优化器又是如何在巨大的搜索空间中,找出最优解呢?下一期,接着聊优化器。

相关阅读:

数据库内核杂谈(一):一小时实现一个基本功能的数据库

数据库内核杂谈(二):存储“演化论”

数据库内核杂谈(三):索引优化

数据库内核杂谈(四):执行模式

数据库内核杂谈(五):如何实现排序和聚合

数据库内核杂谈(六):表的 JOIN(连接)

评论

发布