联接顺序 (Join Order)

在多表联接的场景中，优化器的一个很重要的任务是决定各个表之间的联接顺序，因为不同的联接顺序会影响中间结果集的大小，进而影响到计划整体的执行代价。为了减少执行计划的搜索空间和计划执行态的内存占用，OceanBase 数据库优化器在生成联接顺序时主要考虑左深树的联接形式。下图展示了左深树, 右深树和多支树的计划形状。

image

OceanBase 数据库联接顺序的生成采用了 System-R 的动态规划算法，考虑到的因素包括每一个表可能的访问路径、interesting order、可能的联接算法（NESTED-LOOP，BLOCK-BASED NESTED-LOOP, SORT-MERGE 等）以及不同表之间的联接选择率等等。

给定 N 个表的联接，OceanBase 数据库生成联接顺序的方法如下:

  1. 为每一个基表生成访问路径，保留代价最小的访问路径以及有所有有 interesting order 的路径。一个路径如果具有 interesting order，它的序能够被后续的算子使用。

  2. 生成所有表集合的大小为 i (1 < i <= N) 的计划。 OceanBase 数据库一般只考虑左深树，表集合大小为 i 的计划可以由一个表集合大小为 i 的计划和一个基表的计划组成。OceanBase 数据库按照这种策略，考虑了所有的联接算法，interesting order 的继承等因素把所有表集合大小为 i 的计划生成。这里也只是保留代价最小的计划以及所有具有 interesting order 的计划。