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

    下图展示了左深树, 右深树和多支树的计划形状。

    树.jpg

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

    同时，OceanBase 数据库提供了hint 机制 /*+ leading(table_name_list)*/ 去显示控制多表连接的顺序，比如下面开始选择的连接顺序是先做 t1、t2 的 join 连接，然后再和 t3 做 join 连接；如果用户希望先做 t2、t3 的 join 连接，然后再和 t1做 join 连接，则可以使用 /*+leading(t2,t3,t1)*/hint 去控制，而用户希望先做 t1、t3 的 join 连接，然后再和 t2做 join 连接，则可以使用 /*+leading(t1,t3,t2)*/hint 去控制。

    1. OceanBase(TEST@TEST)>create table t1(c1 int, c2 int, primary key(c1));
    2. Query OK, 0 rows affected (0.31 sec)
    4. OceanBase(TEST@TEST)>create table t2(c1 int, c2 int, primary key(c1));
    5. Query OK, 0 rows affected (0.33 sec)
    7. OceanBase(TEST@TEST)>create table t3(c1 int, c2 int, primary key(c1));
    8. Query OK, 0 rows affected (0.44 sec)
    10. OceanBase(TEST@TEST)>explain select * from t1,t2,t3 where t1.c1 = t2.c2 and t2.c1 = t3.c2;
    11. | =======================================
    12. |ID|OPERATOR    |NAME|EST. ROWS|COST  |
    13. ---------------------------------------
    14. |0 |HASH JOIN   |    |98010    |926122|
    15. |1 | TABLE SCAN |T3  |100000   |61860 |
    16. |2 | HASH JOIN  |    |99000    |494503|
    17. |3 |  TABLE SCAN|T1  |100000   |61860 |
    18. |4 |  TABLE SCAN|T2  |100000   |61860 |
    19. =======================================
    21. Outputs & filters: 
    22. -------------------------------------
    23.   0 - output([T1.C1], [T1.C2], [T2.C1], [T2.C2], [T3.C1], [T3.C2]), filter(nil), 
    24.       equal_conds([T2.C1 = T3.C2]), other_conds(nil)
    25.   1 - output([T3.C2], [T3.C1]), filter(nil), 
    26.       access([T3.C2], [T3.C1]), partitions(p0)
    27.   2 - output([T1.C1], [T1.C2], [T2.C1], [T2.C2]), filter(nil), 
    28.       equal_conds([T1.C1 = T2.C2]), other_conds(nil)
    29.   3 - output([T1.C1], [T1.C2]), filter(nil), 
    30.       access([T1.C1], [T1.C2]), partitions(p0)
    31.   4 - output([T2.C2], [T2.C1]), filter(nil), 
    32.       access([T2.C2], [T2.C1]), partitions(p0)
    34. OceanBase(TEST@TEST)>explain select /*+leading(t2,t3,t1)*/* from t1,t2,t3 where t1.c1 = t2.c2 and t2.c1 = t3.c2;
    35. | ========================================
    36. |ID|OPERATOR    |NAME|EST. ROWS|COST   |
    37. ----------------------------------------
    38. |0 |HASH JOIN   |    |98010    |1096613|
    39. |1 | HASH JOIN  |    |99000    |494503 |
    40. |2 |  TABLE SCAN|T2  |100000   |61860  |
    41. |3 |  TABLE SCAN|T3  |100000   |61860  |
    42. |4 | TABLE SCAN |T1  |100000   |61860  |
    43. ========================================
    45. Outputs & filters: 
    46. -------------------------------------
    47.   0 - output([T1.C1], [T1.C2], [T2.C1], [T2.C2], [T3.C1], [T3.C2]), filter(nil), 
    48.       equal_conds([T1.C1 = T2.C2]), other_conds(nil)
    49.   1 - output([T2.C1], [T2.C2], [T3.C1], [T3.C2]), filter(nil), 
    50.       equal_conds([T2.C1 = T3.C2]), other_conds(nil)
    51.   2 - output([T2.C2], [T2.C1]), filter(nil), 
    52.       access([T2.C2], [T2.C1]), partitions(p0)
    53.   3 - output([T3.C2], [T3.C1]), filter(nil), 
    54.       access([T3.C2], [T3.C1]), partitions(p0)
    55.   4 - output([T1.C1], [T1.C2]), filter(nil), 
    56.       access([T1.C1], [T1.C2]), partitions(p0)
    58. explain select /*+leading(t1,t3,t2)*/* from t1,t2,t3 where t1.c1 = t2.c2 and t2.c1 = t3.c2;
    59. | =============================================================
    60. |ID|OPERATOR                   |NAME|EST. ROWS  |COST       |
    61. -------------------------------------------------------------
    62. |0 |HASH JOIN                  |    |98010      |53098071243|
    63. |1 | NESTED-LOOP JOIN CARTESIAN|    |10000000000|7964490204 |
    64. |2 |  TABLE SCAN               |T1  |100000     |61860      |
    65. |3 |  MATERIAL                 |    |100000     |236426     |
    66. |4 |   TABLE SCAN              |T3  |100000     |61860      |
    67. |5 | TABLE SCAN                |T2  |100000     |61860      |
    68. =============================================================
    70. Outputs & filters: 
    71. -------------------------------------
    72.   0 - output([T1.C1], [T1.C2], [T2.C1], [T2.C2], [T3.C1], [T3.C2]), filter(nil), 
    73.       equal_conds([T1.C1 = T2.C2], [T2.C1 = T3.C2]), other_conds(nil)
    74.   1 - output([T1.C1], [T1.C2], [T3.C1], [T3.C2]), filter(nil), 
    75.       conds(nil), nl_params_(nil)
    76.   2 - output([T1.C1], [T1.C2]), filter(nil), 
    77.       access([T1.C1], [T1.C2]), partitions(p0)
    78.   3 - output([T3.C1], [T3.C2]), filter(nil)
    79.   4 - output([T3.C2], [T3.C1]), filter(nil), 
    80.       access([T3.C2], [T3.C1]), partitions(p0)
    81.   5 - output([T2.C2], [T2.C1]), filter(nil), 
    82.       access([T2.C2], [T2.C1]), partitions(p0)