连接顺序 (Join Order)

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

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的计划。