数据库内核月报

数据库内核月报 - 2022 / 04

MySQL · 源码阅读 · 数据库的扫描方法

Author: 智邻

引言

关于存储引擎的介绍有很多,基于HEAP的传统存储引擎,以及基于聚簇索引的Innodb引擎等,但优化器如何充分利用存储引擎的特点来实现快速高效的扫描,从而以最小的代价得到用户所需要的结果,是一个非常复杂过程。为了了解优化器是如何运作的,首先我们要了解每一种扫描方式的特点,下面我们以MySQL为例,就一些常见的表扫描方式进行讨论。

全表扫描

MySQL的full table scan本质上还是通过Primary index scan来实现的,遍历整个B+tree,这是因为MySQL采用的是基于B+树实现的索引组织表,如下图所示,它的叶子节点上存储的就是实际的数据,而叶子节点上有一个双向链表,依次扫描所有的叶子节点即可以实现全表扫描。 早期的MySQL仅支持copy模式的DDL。在MySQL 5.5中,引入了inplace算法,可以将部分DDL操作交给引擎层进行处理,但是在进行DDL期间,依旧会阻塞DML操作。在5.6中,部分inplace DDL操作可以采用online算法。该算法允许用户在进行DDL操作过程中,并行的执行写入操作。有关上述三种DDL的差异及主要特点,可以参照文末的扩展阅读部分。

图1 索引组织表的全表扫描

而HEAP表也就是堆表就有非常明显的区别,对于HEAP表来说,如下图所示,全表扫描是在物理上顺序扫描所有的数据页面,所以也称之为顺序扫描(sequential scan),对于全新导入的数据,甚至在物理上这些页面都是连续的。然而如果经过不断的更新、删除操作,就无法再保证页面的连续性。

图2 HEAP表的全表扫描

比较与总结

由于组织方式的不同,这两种存储引擎的全表扫描各自不同的特点,主要的不同如下所示:

IO的特点
对于索引组织表,叶子节点虽然是依次扫描所有节点节点,但是这些叶子节点并不保证在物理上是连续的,也不保证是有序的,因此对应的IO是随机IO。而对于HEAP表,数据页在物理上是邻近的,可以顺序访问这些数据页,对应的IO是顺序IO。通常来说,随机IO的代价要比顺序IO的代价要高很多。

结果的有序性
对于索引组织表,全表扫描出来的数据对主键天然有序,这对优化器来说是一个非常有用的特性,如果查询的结果要求对主键有序,那么这样扫描出来的结果就无需再做额外的排序操作,节省了排序的开销。而对于HEAP表,扫描出来的结果是无序的,如果查询的结果要求有序,就必须对扫描出来的结果再进行排序方可。

并行扫描的分片方式
为了提升全表扫描的性能,还有一种显尔易见的方法,就是并行扫描,采用多个线程或进程,每个线程或进程只扫描全表的一个分片。对于索引组织表,可以按B+树的特点,分成几个子树,每个线程或进程只扫描一个子树;

图3 索引组织表的分片策略 对于HEAP表,可以直接按数据页分片,每个线程或进程扫描几个连续的数据页。因为数据组织方式的不同,会发现对于索引组织表的分片,数据其实是按Range分片的,而对于HEAP表的分片,数据分片是随机的,本身没有什么特殊的规律。 图4 HEAP表的全表扫描 这些分片方式的不同对于并行计划的生成是非常重要的,比如在并行扫描的结果上做group by操作,对于已经按range分片的数据,如果group by的列与range分片相兼容,那么聚集操作就可以直接下推到每个range分片上即可;而对于按随机分片的数据,聚集操作只能在分片上做第一次聚集,然后在所有分片聚集的结果上再做一次二次聚集方可。

数据倾斜
但是Range分片,有可能数据分片的大小不均匀,有些分片内的数据多,有些分片内的数据少,极端情况下如果数据倾斜特别严重时,可能会导致并行扫描效率更低,因为还增加了进线程的开销。而对于HEAP表的随机分片方式,数据分片不均的可能性就会小很多。 图5 数据倾斜

索引扫描

索引组织表的索引扫描

在MySQL中,主键索引是基于B+树的聚簇索引,相应的表被称为索引组织表,简称IOT表。MySQL在表上另外再创建的索引,称为二级辅助索引,简称二级索引。MySQL的二级索引其实是一个比较变态的组织方式,因为只有主键表中才真正存储数据,并且因为涉及到B+树的分裂和合并等,每个ROW的实际物理位置并不是总是固定不变的,因此二级索引只能记录ROW的逻辑地址,即主键,然后通过主键再确定其实际的物理位置。但这样也有一个优点,当数据更新时,如果没有更新主键或二级索引自身的键值时,就不需要更新二级索引。 如果要通过二级索引来扫描完整的ROW,必需要先扫描二级索引,找到对应的主键,再利用主键找到对应的ROW。因此在MySQL中,使用二级索引来进行扫描原始的ROW代价会很大,但二级索引利用的好,也还是非常有用的,MySQL针对二级索引也做了很多优化访问方式,优化器会根据二级索引的特点来确定是否选择二级索引。 如下图的IOT表,主键索引如下图所示:

图6 索引组织表的主键索引

如在Name列是新建二级索引,那么二级索引如下所示:

图7 索引组织表的二级索引

在二级索引的叶子节点中的ROW中,会记录主键,如果需要读取二级索引中未包含的列,就必须通过主键索引查询完整的ROW,如下图所示: 图8 索引组织表的二级索引扫描

HEAP表的索引扫描

在Heap表中,通常没有二级索引的概念,索引中记录的是记录的row_id,row_id指向实际的物理存储位置,可以通过这个row_id直接定位到记录所在的page和在page中的位置。如下图所示:

图9 HEAP表的索引扫描

如果数据更新导致ROW的物理位置发生变化,那么所有相关的索引都需要更新,如果索引比较多,就会导致效率比较低,从而遭遇到著名的”写放大”效应。通过HEAP表的索引访问ROW相对就比较简单,效率也比较高,而且是每个索引的效率基本都差不多,这点与IOT表的索引不同,IOT表只有主键索引效率比较高,所有其它二级索引的效率都比较低。当然如果只是访问索引自身包含的键值列,就另当别论了,这种称之谓covering index scan,或者覆盖索引扫描。通过索引访问物理ROW的方式如下图所示:

图10 Coverings覆盖索引扫描

比较与总结

总之,不同的数据和索引组织方式都有其特点,对于IOT表来说,主键索引效率最高,二级索引的效率比较差;对于HEAP表来说,索引的效率差不多,索引键的distinct值(不重复的键值)对索引的访问有一定影响,对于特别小的表来说,直接做全表的顺序扫描可能更有效率。两种不同索引方式的对比如下表所示:

点查询效率
HEAP表的索引的点查询效率和IOT表的主键索引的点查效率,差不多,但IOT表的二级索引的点查询效率就会差很多。

范围查询效率
IOT表的主键索引的范围查询效率很高,因为数据天然有序,可以直接定位到范围起点,然后沿着叶子节点向右查询,直到结束位置即可。但通过二级索引做范围查询的效率就比较低了,因为二级索引只能得到范围内的主键集合,还需要再次通过主键进行点查才能得到ROW,而且每个二级索引的效率基本都一样,除非是covering index查询。 与之IOT表的主键索引的范围查询效率相比,HEAP表的索引的范围查询效率也比较低,但比二级索引的范围查询效率略高。原因是虽然也可以通过定位范围的起点,沿着叶子节点向右查询,直到结束位置为止,但此时只能得到指同实际ROW存储的物理位置,还需要访问物理位置才能得到ROW,而且这些物理位置并不连续,属于随机分布,访问效率就会大大降低。但优点在于每个索引的效率基本都一样, 不会有太差的索引出现。
数据更新效率
由于IOT表的二级索引中保存的是ROW的逻辑地址,通常是主键,没有主键的表保存的是ROW-ID,那么在数据更新时,只要主键没有发生变化,二级索引是没有必要更新的。对于HEAP表来说,由于索引中保存的是ROW的物理地址,那么在数据更新时,如果ROW的物理地址发生变化,索引就必须更新,当然实际的实现中也有很多不同的实现机制,比如尽可能的原地更新,保持物理地址不变;有些数据库采用多版本之间的链表来实现保持物理地址不变,各有优劣和特点,这些特点对优化器在选择扫描方式时都有不同的影响。