OceanBase与TiDB优化器的基数预估准确度和连接顺序选择能力的评测

一、引言

查询优化器作为数据库查询引擎的大脑，负责生成理想的执行计划，一直以来都被认为是查询引擎中最重要最核心的部分。现代数据库系统的优化器都是基于代价的优化器（Cost-based Optimizer, CBO），使用代价模型选出最佳的执行计划。相关研究表明，提升基数预估的准确度比代价模型中的CPU权重、IO权重等参数的作用大的多。另一方面，由于多表连接负载存在着庞大的连接顺序搜索空间，为多表连接负载确定最优的连接顺序也是一项艰难的任务。因此，优化器在不同情况下的基数预估准确度和连接顺序选择的质量可作为评测优化器的两个关键要点。本文将使用自研的工具对OceanBase、TiDB的基数预估、连接顺序选择的质量以及对于复杂连接形状的处理能力做出评测和对比。

二、背景知识和实验设置

1.基数预估

基数预估的作用是预估查询执行计划中算子的输出结果集大小。作为代价模型中的重要参数，基数预估的准确度会对查询执行计划的选择造成很大的影响，确保基数预估的准确度十分重要。在OceanBase和TiDB中，均可使用Explain关键字来查看优化器选出的执行计划中所有算子的基数预估结果。比如，在OceanBase中，对负载SELECT * FROM t1,t2 WHERE t1.c2=t2.c2 AND t2.c1 > 4 的Explain结果如下所示[1]，表示OceanBase选定HashJoin作为表t1和t2之间连接的物理算法，预估的连接基数大小为9801000。

`Query Plan:
=======================================
|ID|OPERATOR   |NAME|EST. ROWS|COST   |
---------------------------------------
|0 |HASH JOIN  |    |9801000  |5933109|
|1 | TABLE SCAN|t2  |10000    |6219   |
|2 | TABLE SCAN|t1  |100000   |68478  |
=======================================`

2.连接形式和连接顺序

连接形式也叫连接图（Join Graph），文献[2]中总结了可能出现的一些连接图，如图1所示，主要包括链式连接（Chain）、星型连接（Star）、树型连接（Tree）、环型连接（Cycle）、集团连接（Clique）等。其中，Cycle、Clique、Cyclic及Grid形式的连接比较复杂，在构建连接的过程中，这些形式的连接会导致新参与连接的表与已经连接的表之间存在多个连接关系，在本文中，我们称这些连接形式为复杂连接形式。

图1 连接图[2]

对于N表连接负载，存在的连接顺序有(2*N-2)!/(N-1)!个，优化器会使用一些方法（比如动态规划或贪心算法）来枚举连接顺序。由于枚举所有可能的连接顺序的代价较大，因此优化器只会枚举其子集，这可能导致优化器无法为某些多表连接负载确定最佳的连接顺序。另一方面，基数预估和连接顺序的选择是相互影响的，基数预估通过影响代价模型，从而对连接顺序的选择造成影响。同时，不同的连接顺序也会影响基数预估。同样的多表连接，不同数据库的优化器可能选出不同的连接顺序，因此，使用相同的多表连接负载测试不同数据库对其连接算子的基数预估准确度时，应固定相同的连接顺序。OceanBase和TiDB分别提供了LEADING和/*! STRAIGHT_JOIN */关键字来指定数据库以特定的连接顺序执行多表连接负载。

3.实验环境

由于查询优化器代价模型暂时无法控制，为了降低分布式环境下代价模型的影响，本文实验使用的Oceanbase和TiDB均为单机版。Oceanbase的版本为3.1.2，TiDB的版本为6.0，其中TiDB单机版包括一个TiDB组件、一个PD组件、一个TiKV组件及一个TiFlash组件。两者均在操作系统为Centos 7.9，内存为8G，CPU型号为16核 Intel Xeon Processor (Cascadelake)的机器上运行。

OceanBase的配置文件如下所示：

`global:
    devname: eth0
    cluster_id: 1
    memory_limit: 8G
    system_memory: 4G
    stack_size: 512K
    cpu_count: 16
    cache_wash_threshold: 1G
    __min_full_resource_pool_memory: 268435456
    workers_per_cpu_quota: 10
    schema_history_expire_time: 1d
    net_thread_count: 4
    major_freeze_duty_time: Disable
    minor_freeze_times: 10
    enable_separate_sys_clog: 0
    enable_merge_by_turn: FALSE
    datafile_disk_percentage: 35
    syslog_level: WARN
    enable_syslog_recycle: true
    max_syslog_file_count: 4
    appname: obtest
    mysql_port: 2883
    rpc_port: 2882
    home_path: /root/observer
    data_dir: /data
    redo_dir: /redo
    zone: zone0

三、OceanBase基数预估准确度和TiDB的对比

优化器在进行基数预估时会进行均匀性(uniformity)假设，即会假定除了最频繁出现的数据，其他数据都是均匀分布的[3]，这种假设会导致基数预估在具有倾斜分布的数据中的不准确，从而对执行计划的选择造成影响。传统的基数预估方法有直方图和采样的方法，无法对多表连接算子的基数做出准确的预估。

为了测试OceanBase和TiDB在不同情况下的基数预估准确度，本实验随机生成不同基数大小的单表、3表、5表链式连接负载，所有参与连接的表大小均相同，分别为10000和50000，并控制过滤谓词涉及属性数据的倾斜度分别为均匀分布、倾斜度为1的ZipFian分布及倾斜度为3的ZipFian分布，以评测OceanBase和TiDB这些场景下的基数预估情况，获得的基数预估结果包括Analyze Table之前的结果、Analyze Table（OceanBase对应的命令为Alter System Major Freeze）之后的结果以及Analyze Table之后多次Explain的结果（Explain 5次）。每个测试场景均生成10个负载。不同的优化器可能对相同的多表连接负载选定不同的连接顺序，为了消除这种影响，本实验使用相同的负载进行测试时固定其连接顺序为其对应的SQL形式中From关键字后罗列的表顺序。

下列表展示了单表过滤算子在不同表大小及数据倾斜度下的基数预估情况。

 单表过滤算子，表大小10000，数据为均匀分布

 单表过滤算子，表大小10000，数据倾斜度为1

 单表过滤算子，表大小10000，数据倾斜度为3

 单表过滤算子，表大小50000，数据为均匀分布

 单表过滤算子，表大小50000，数据倾斜度为1

 单表过滤算子，表大小50000，数据倾斜度为3

从以上单表过滤算子的基数预估情况可以看出，不管有没有Analyze Table获得统计信息，OceanBase和TiDB对于单表过滤算子的基数预估结果比较固定，与表的大小有关，会随着表大小的成比例增大。有趣的是，TiDB在多次使用Explain获取基数预估结果的过程中，其基数预估的准确度会越来越高。

下列表展示了3表连接算子在不同表大小及数据倾斜度下的基数预估准确度。

3表连接，表大小均为10000，过滤谓词涉及属性的数据为均匀分布

 3表连接，表大小均为10000，过滤谓词涉及属性的数据倾斜度为1

3表连接，表大小均为10000，过滤谓词涉及属性的数据倾斜度为3 

 3表连接，表大小均为50000，过滤谓词涉及属性的数据为均匀分布

 3表连接，表大小均为50000，过滤谓词涉及属性的数据倾斜度为1

 3表连接，表大小均为50000，过滤谓词涉及属性的数据倾斜度为3

从以上3表连接算子在不同表大小以及数据倾斜度下的基数预估情况来看，在Analyze Table之前，由于OceanBase和TiDB都没有统计信息，因此会把这列数据当成均匀分布来看，其结果较为固定，不会随着真实基数的改变而改变。然而，在Analyze Table之后，首次使用Explain获取TiDB的基数预估结果已经会随着真实基数的改变而改变，呈现高估的现象，而OceanBase的基数预估结果相比Major Freeze之前有所改变，但仍然是固定的数值。另外，TiDB的基数预估是不稳定的，在表大小50000，数据均匀分布的情况下，我们可以发现，在Analyze Table之后，首次使用Explain并不能获得随真实基数变化的预估结果。

下列表展示了5表连接算子在不同表大小及数据倾斜度下的基数预估准确度。

5表连接，表大小均为10000，过滤谓词涉及属性的数据为均匀分布

 5表连接，表大小均为10000，过滤谓词涉及属性的数据倾斜度为1

5表连接，表大小均为10000，过滤谓词涉及属性的数据倾斜度为3 

 5表连接，表大小均为50000，过滤谓词涉及属性的数据为均匀分布

 5表连接，表大小均为50000，过滤谓词涉及属性的数据倾斜度为1

 5表连接，表大小均为50000，过滤谓词涉及属性的数据倾斜度为3

从以上5表连接算子的基数预估结果，我们可以得出与3表连接中类似的现象和结论。

四、OceanBase和TiDB对于星型连接顺序选择质量的对比

星型连接在数据仓库等OLAP场景中十分常见，主要包括一个事实表和多个维度表之间进行主键-外键连接，事实表一般比维度表大。数据库对于星型连接的处理能力反应了该数据库在OLAP领域的适用度。本实验控制维度表的大小范围在[10,50],事实表的大小分别为10000，50000，100000，500000，1000000，在不同事实表大小的情况下分别随机生成50个8表星型连接查询。基于贪心的思想，优先选择连接基数小的算子先进行连接（包括笛卡尔积），对多表星型连接进行连接顺序的重排。比如在A,B,C,D,E 5表连接中，首先两个连接基数最小的表做连接，中间结果为Join_a；接着从剩下的表中选择与Join_a连接基数最小的表进行连接，重复该过程直到所有的表都参与连接。本实验以重排后的连接顺序作为基准，对OceanBase和TiDB优化器选定的连接顺序进行平均执行时间的对比。为了避免执行计划缓存的影响，本实验在OceanBase和TiDB中均设置关闭执行计划缓存。

图2展示了维度表大小不同的情况下，两种数据库经过连接顺序重排前后的执行时间对比，横坐标表示事实表大小，纵坐标表示执行时间。可以发现，两种数据库的优化器在经典的星型连接场景下，均无法选出最优的连接顺序，存在连接顺序选择策略的提升空间。同时我们还可以从本实验场景中看出，在事实表大小为100000及以下，OceanBase和TiDB在处理星型连接时的性能接近，在事实表大小为500000和1000000时，OceanBase和TiDB处理星型连接的执行时间差异略大。

图2 OceanBase和TiDB优化器选择的连接顺序和本文基于连接基数最小原则重排后的连接顺序性能对比

为了评测两种数据库优化器对于星型连接的连接顺序选择策略的可提升空间，我们使用连接顺序重排后的执行计划作为基准计划，计算两种数据库重排前的连接顺序和重排后的连接顺序的执行时间的比值，当作执行效率提升的倍数。两种数据库的优化器对于星型连接的可提升空间如图3所示，横坐标表示事实表大小，纵坐标表示执行效率提升的倍数。由本实验可知，在事实表大小为100000及以下时，TiDB优化器对于星型连接的连接顺序选择策略的可提升空间大于OceanBase；在事实表大小为500000和1000000时，两种数据库的优化器选出的执行计划的性能和本实验的基准计划的执行性能相似。另一方面，OceanBase优化器所选的执行计划和我们重排连接顺序后的基准计划相比，其可提升空间随着事实表的增多呈现降低的趋势。

由于OceanBase支持Bushy Tree，我们目前的连接顺序重排算法只能基于连接基数最小原则给出基数最优的左深树，后续可改进我们的连接顺序重排算法，使得其支持Bushy Tree，从而做出更深度的连接顺序选择质量的评测。

图3 OceanBase和TiDB优化器对于星型连接的连接顺序选择策略的可提升空间

注：本实验的所有数据和负载可通过连接获取：https://drive.google.com/drive/folders/1P53_FWfusCa3xhSSZLDCBZm1VZy52hBi?usp=sharing，包括重排前的负载和重排后的负载。

五、OceanBase和TiDB对于复杂连接形式处理能力的对比

本节首先展示OceanBase和TiDB是否全部支持图1不同的连接形式（或连接图），随机生成有意义的7种不同连接形式的负载，查看两种数据库是否可执行，结果如下表所示。

为了评测OceanBase和TiDB处理复杂连接形式的性能，本实验设定所有表大小均为100万，分别随机生成50个4表连接、5表连接、6表连接、7表连接、8表连接和9表连接负载，将这些负载在OceanBase和TiDB分别执行并对比整体执行时间。本实验保证负载完全能产生有意义的非空结果，负载中涉及到的复杂连接方式包括Cycle Join、Cyclic Join及Clique Join，所有连接均为主键-外键连接。

图4、图5和图6展示了在本文的测试场景下，OceanBase和TiDB在Clique Join、Cycle Join及Cyclic Join情况下的执行时延(Latency)，横坐标表示参与连接的表数目。

图4 OceanBase和TiDB在不同连接数目的Clique Join中的执行时间

图5 OceanBase和TiDB在不同连接数目的Cycle Join中的执行时间

图6 OceanBase和TiDB在不同连接数目的Cyclic Join中的执行时间

从图4、图5和图6中可以看出，OceanBase处理复杂连接形式负载的整体时延高于TiDB，在我们随机生成的测试场景中，OceanBase处理复杂连接形式负载的时延大部分为千级别(ms)，而TiDB的时延为稳定的百级别(ms)。此外，在环型连接(Cycle Join)中，OceanBase处理8表连接和9表连接的时延达到了万级别(ms)。

六、总结

基于本文的实验，我们总结如下：

1.基数预估方面，在Analyze Table之前，OceanBase和TiDB都会默认数据为均匀分布，该种情况下的基数预估结果和真实基数无关，随着表大小成比例改变。在Analyze Table之后，TiDB的基数预估不固定，首次使用Explain获取预估结果和多次使用Explain获取结果可能不一致，而OceanBase经过Major Freeze后，其基数预估结果仍不会随真实基数的改变而改变。

2.在星型连接场景中，OceanBase和TiDB的优化器均无法选出最佳的连接顺序，其中OceanBase的优化器选择的连接顺序的质量比TiDB更接近于本文基于连接基数最小原则进行重排后的连接顺序。

3.在复杂连接形式的处理性能方面，在百万级别数据量的多表连接情况下，OceanBase的性能要低于TiDB，未来应在OLAP方面加强。

二、参考材料

[1] Explain, https://open.oceanbase.com/docs/observer-cn/V3.1.2/10000000000015437

[2] Join Order, https://db.in.tum.de/teaching/ws1415/queryopt/chapter3.pdf?lang=de

[3] Leis, Viktor, et al. “Query optimization through the looking glass, and what we found running the join order benchmark.” The VLDB Journal 27.5 (2018): 643-668.