MySQL-8.0执行器及其改进

腾讯数据库技术

修改于 2019-07-22 16:03:30

2.6K0

修改于 2019-07-22 16:03:30

数据库管理系统中，最重要的模块包括SQL优化器、SQL执行器、事务管理器等。SQL语句处理流程为：SQL输入->语法分析->语义检查->逻辑优化->物理优化->执行。其中SQL执行器就是按照SQL优化器生成的执行计划，有机的调用存储、索引、并发等模块，实现各种计划结点算法来完成数据的读取或者修改过程。在MySQL8.0中执行器部分代码发生了较大改变，新的执行器向经典的Iterator模型更接近了一步，我们暂时叫它iterator执行器。接下来我们分析一下这个新的执行器。

iterator模型

首先我们介绍一下iterator模型。在编程语言中的iterator模型是一种遍历对象列表常用的数据模型，尤其在数据源大小未知或者数据量过大不适合一次性加载所有数据的情况下。通常iterator模型需要实现至少两个接口：hasNext()和next()。hasNext()判断遍历是否结束，next()接口用来取得下一个数据元素。

Goetz Graefe曾对这种模型进行了很好的总结和扩展，发表论文阐述了业界知名的Volcano模型(Volcano-An Extensible and Parallel Query Evaluation System)。在这个模型中，将每一个代数操作实现为一个iterator，iterator支持一组简单的协议：open()—next()—close()，基本上就是一个循环的必须组件：初始化、增量、循环终止条件和内部处理。由多个关系代数操作组成的查询执行树转换成了一个iterator执行树。查询执行的时候，顶层iterator执行open()然后循环调用next()获取数据并进行处理直到结束，最后执行close()。树上的每个节点独立的将输入看成一个表，节点调用next()接口时递归的从下层节点获取一行输入数据，并进行处理后输出给上一层节点。从整体流程看，根节点调用next()后递归调用next()接口直到叶节点，而数据则是从叶节点依次流向根节点，这是一个数据的Pull模型。我们假设一个简单查询存在投影节点，过滤节点和扫描节点，则执行树和数据流如下图所示：

当然，如果支持将执行树划分为子树，并采用不同的线程并行执行，是可以灵活的实现Pull或Push。iterator模型有很多优点:

每个迭代器是相互独立的，不同的查询可以由不同的迭代器组合实现，使得查询执行变得非常简单。
迭代器满足相同的接口标准，扩展性非常好，当需要新增一个迭代器的时候，按接口标准实现就可以使用了。
数据以行的形式在迭代器之间流动，每个操作仅需要很少的资源就可以很好的运行起来，非常的节省内存资源。
非常容易扩展为多进程、线程的并发执行。

目标

MySQL8.0执行器改进的目的是创建一个新的用于迭代访问记录的API，它足够通用，可以替换MySQL中所有原有的记录迭代器，并逐步替代掉原有的执行器。

我们先来看一下原有的记录迭代器：

QUICK_SELECT_I接口。这个接口抽象了各种使用索引来访问表中数据的方式，例如range scans、index merge或group min / max。
READ_RECORD接口。抽象了QUICK_SELECT_I接口、full table scans、full index scans和 sort buffer results。
QEP_TAB包含的一个接口，没有自己的名字。它抽象了READ_RECORD中的函数指针，以及各种特定连接的访问类型（REF、EQ_REF、full-text search等）。
QEP_operation接口。它抽象了临时表或者join buffering(用作BNL和BKA的一部分)。
QEP_TAB::next_select接口。抽象了QEP_operation接口、nested-loop joins、GROUP BY以及其他一些操作。
Query_result接口。抽象了UNION、EXISTS操作提前结束的情况、将结果发送给用户、可能还有其他一些操作。

其中1、4和6接口基于C++类实现的，2、3和5基于C函数指针来实现的。4、5和6接口是使用的推送数据模型，而其他的是拉取模型。另外还有许多类型的操作是使用这些抽象之外的特殊代码来完成的，例如表的物化、排序和去重操作。

与iterator模型相比，原有执行器设计中有几个缺点：

没有标准的接口抽象，扩展性差。
实现的方式不统一，有C函数指针，也有C++类。
抽象层次不够清晰，代码难以阅读和理解。
代码耦合度高，后续难以优化。

可以认为，MySQL现有执行器的实现方式也限制了它的演进。

具体实现

在MySQL8.0的实现中，主要实现了一个通用的C++类接口，叫做RowIterator，它具有以下成员函数：

构造函数和析构函数。
Init(QEP_TAB*)：打开所有必需的资源，也有可能执行部分功能性操作，比如SortingIterator中会进行排序操作，这个函数可多次调用，每次调用都会重置迭代器指示位置。
Read()：读取一行，将行放入记录缓存中，类似以前的read_record()。
UnlockRow()：与原有的rr_unlock_row类似，将一行过滤出结果集后，允许低事务隔离级别释放该行的所有锁。

通过使用这个通用的C++类接口，执行流程变化为下图：

8.0.16中主要实现了以下迭代器类型：

TableScanIterator：顺序扫描，调用存储引擎接口ha_rnd_next获取一行记录。
IndexScanIterator：全量索引扫描，根据扫描顺序，分别调用ha_index_next或者ha_index_prev来获取一行记录。
IndexRangeScanIterator：范围索引扫描，包装了下QUICK_SELECT_I，调用QUICK_SELECT_I::get_next来获取一行记录。
SortingIterator：对另一个迭代器输出进行排序。
SortBufferIterator：从缓冲区读取已经排好序的结果集，(主要给SortingIterator调用)
SortBufferIndirectIterator：从缓冲区读取行ID然后从表中读取对应的行（由SortingIterator和某些形式的unique操作使用）
SortFileIterator：从文件中读取已经排好序的结果集(主要给SortingIterator调用)
SortFileIndirectIterator：从文件读取行ID然后从表中读取对应的行（由SortingIterator和某些形式的unique操作使用）
RefIterator：从连接右表中读取指定key的行。
RefOrNullIterator：从连接右表中读取指定key或者为NULL的行。
EQRefIterator：使用唯一key来从连接的右表中读取行。
ConstIterator：从一个只可能匹配出一行的表(Const Table)中读取一行数据。
FullTextSearchIterator：使用全文检索索引读取一行数据。
DynamicRangeIterator：为每一行调用范围优化器，然后根据需要包装QUICK_SELECT_I或表扫描。
PushedJoinRefIterator:读取已下推到NDB的连接的输出。
FilterIterator: 读取一系列行，输出符合条件的行，用来实现WHERE/HAVING。
LimitOffsetIterator: 从offset开始读取行，直到满足limit限制，用来实现LIMIT/OFFSET。
AggregateIterator: 实现聚集函数并且如果需要的话进行分组操作。
NestedLoopiterator: 使用嵌套循环算法连接两个迭代器（内连接，外连接或反连接）。
MaterializeIterator: 从另一个迭代器读取结果，并放入临时表，然后读取临时表记录。
FakeSingleRowIterator: 返回单行，然后结束。仅在某些使用const表情况下才使用（例如只有const表，仍然需要一个迭代器来读取该单行）

目前新执行器支持primary表和const表组成的查询，各种连接（半连接除外），过滤（WHERE / HAVING），分组（除了汇总），limit/offset和某些形式的物化（派生表和在最终排序之前的物化）；不支持SELECT DISTINCT，CTE，窗口函数，半连接，松散扫描或BNL/BKA; 当新执行器执行不支持的查询时，MySQL就会回退到旧的执行器去执行。两个执行器将并存一段时间，但最终老执行器将会被替换。

未来展望

基于新的执行器，MySQL将支持更多代数查询操作，支持更丰富的功能。比如让EXPLAIN命令输出树格式的查询计划，并且输出更精确的执行信息，更好的帮助用户理解实际的执行方式，如：

-> Aggregate: sum((lineitem.l_extendedprice * (1 - lineitem.l_discount)))
    -> Nested loop inner join
        -> Filter: (((part.p_brand = 'Brand#22') and (part.p_container [...]
            -> Table scan: part
        -> Filter: (((lineitem.l_shipinstruct = 'DELIVER IN PERSON') and [...]
            -> Reference lookup on lineitem using i_l_partkey (l_partkey=part.p_partkey)

让我们拭目以待吧！