目前OceanBase支持Nested Loop Join、Merge Join、Hash Join三种不同的连接算法。Hash join和Merge join只适用于等值的连接条件，但是Nested Loop Join是用于任意的连接条件。

    Nested Loop Join

    Nested Loop Join就是扫描一个表（外表），每读到该表中的一条记录，就去’扫描’另一张表（内表）找到满足条件的数据。这里的’扫描’可以是利用索引快速定位扫描，也可以是全表扫描。通常来说，全表扫描的性能是很差的，所以如果连接条件的列上没有索引，优化器一般就不会选择 Nested Loop Join。在Oceanbase中，计划中展示了是否能够利用索引快速定位扫描。如下图所示。图中第一个计划对于内表的扫描是全表扫描，因为连接条件是t1.c = t2.c，而t2没有在c上面的索引。第二个计划对于内表的扫描能够使用索引快速找到匹配的行，主要原因是因为连接条件是t1.b = t2.b, 而且t2选择了创建在b列上的索引k1作为访问路径，这样的话对于t1中的每一行的每个b值，t2都可以根据索引快速找到满足条件的匹配行。

    1. OceanBase (root@test)> create table t1(a int primary key, b int, c int, key k1(b));
    2. Query OK, 0 rows affected (0.24 sec)
    3. OceanBase (root@test)> create table t2(a int primary key, b int, c int, key k1(b));
    4. Query OK, 0 rows affected (0.29 sec)
    5. OceanBase (root@test)> explain extended_noaddr select/*+use_nl(t1 t2)*/ * from t1, t2 where t1.c = t2.c;
    6. | ===========================================
    7. |ID|OPERATOR        |NAME|EST. ROWS|COST  |
    8. -------------------------------------------
    9. |0 |NESTED-LOOP JOIN|    |1980     |623742|
    10. |1 | TABLE SCAN     |t1  |1000     |455   |
    11. |2 | TABLE SCAN     |t2  |2        |622   |
    12. ===========================================
    14. Outputs & filters:
    15. -------------------------------------
    16.   0 - output([t1.a], [t1.b], [t1.c], [t2.a], [t2.b], [t2.c]), filter(nil),
    17.       conds(nil), nl_params_([t1.c])
    18.   1 - output([t1.c], [t1.a], [t1.b]), filter(nil),
    19.       access([t1.c], [t1.a], [t1.b]), partitions(p0),
    20.       is_index_back=false,
    21.       range_key([t1.a]), range(MIN ; MAX)always true
    22.   2 - output([t2.c], [t2.a], [t2.b]), filter([? = t2.c]),
    23.       access([t2.c], [t2.a], [t2.b]), partitions(p0),
    24.       is_index_back=false, filter_before_indexback[false],
    25.       range_key([t2.a]), range(MIN ; MAX)
    26. OceanBase (root@test)> explain extended_noaddr select/*+use_nl(t1 t2)*/ * from t1, t2 where t1.b = t2.b;
    27. | ============================================
    28. |ID|OPERATOR        |NAME  |EST. ROWS|COST |
    29. --------------------------------------------
    30. |0 |NESTED-LOOP JOIN|      |1980     |94876|
    31. |1 | TABLE SCAN     |t1    |1000     |455  |
    32. |2 | TABLE SCAN     |t2(k1)|2        |94   |
    33. ============================================
    35. Outputs & filters:
    36. -------------------------------------
    37.   0 - output([t1.a], [t1.b], [t1.c], [t2.a], [t2.b], [t2.c]), filter(nil),
    38.       conds(nil), nl_params_([t1.b])
    39.   1 - output([t1.b], [t1.a], [t1.c]), filter(nil),
    40.       access([t1.b], [t1.a], [t1.c]), partitions(p0),
    41.       is_index_back=false,
    42.       range_key([t1.a]), range(MIN ; MAX)always true
    43.   2 - output([t2.b], [t2.a], [t2.c]), filter(nil),
    44.       access([t2.b], [t2.a], [t2.c]), partitions(p0),
    45.       is_index_back=true,
    46.       range_key([t2.b], [t2.a]), range(MIN ; MAX),
    47.       range_cond([? = t2.b])

    Nested Loop Join可能会对内表进行多次全表扫描，因为每次扫描都需要从存储层重新迭代一次，这个代价相对是比较高的，所以Oceanbase支持对内表进行一次扫描并把结果物化在内存中，这样的话下次就可以直接在内存中扫描相关的数据，而不需要从存储层进行多次扫描。但是物化在内存中是有代价的，所以Oceanbase的优化器基于代价去判断是否需要物化内表。

    Nested Loop Join的一个优化变种是Blocked Nested Loop Join，它的区别在于每个从外表中读取一个Block大小的行，然后再去扫描内表找到满足条件的数据。这样的一个好处是可以减少内表的读取次数。

    Nested Loop Join通常在内表行数比较少，而且外表在连接条件的列上有索引的时候会比较好，因为内表中的每一行都可以快速的使用索引定位到相对应的匹配的数据。

    Merge Join

    Merge Join首先会按照连接的字段对两个表进行sort(如果内存空间不够，就需要进行外排)，然后开始扫描两张表进行Merge。Merge的过程会从每个表取一条记录开始匹配，如果符合关联条件，则放入结果集中；否则，将关联字段值较小的记录抛弃，从这条记录对应的表中取下一条记录继续进行匹配，直到整个循环结束。在多对多的两张表上进行Merge时，通常需要使用临时空间进行操作。例如A join B使用Merge Join时，如果对于关联字段的某一组值，在A和B中都存在多条记录A1、A2…An、B1、B2…Bn，则为A中每一条记录A1、A2…An，都必须在B中对所有相等的记录B1、B2…Bn进行一次匹配。这样，指针需要多次从B1移动到Bn，每一次都需要读取相应的B1…Bn记录。将B1…Bn的记录预先读出来放入内存临时表中，比从原数据页或磁盘读取要快。在一些场景中，如果连接字段上有可用的索引，并且排序一致，那么可以直接跳过排序操作。通常来说，Merge join比较适合两个输入表已经有序的情况，否则Hash Join会更加好。下图展示了两个Merge join的计划，其中第一个是需要排序的，第二个是不需要排序的(因为两种表都选择了k1这两个索引访问路径，这两个索引本身就是按照b排序的)。

    1. OceanBase (root@test)> create table t1(a int primary key, b int, c int, key k1(b));
    2. Query OK, 0 rows affected (0.24 sec)
    3. OceanBase (root@test)> create table t2(a int primary key, b int, c int, key k1(b));
    4. Query OK, 0 rows affected (0.29 sec)
    5. OceanBase (root@test)> explain select/*+use_merge(t1 t2)*/ * from t1, t2 where t1.c = t2.c;
    6. | =====================================
    7. |ID|OPERATOR    |NAME|EST. ROWS|COST|
    8. -------------------------------------
    9. |0 |MERGE JOIN  |    |1980     |6011|
    10. |1 | SORT       |    |1000     |2198|
    11. |2 |  TABLE SCAN|t1  |1000     |455 |
    12. |3 | SORT       |    |1000     |2198|
    13. |4 |  TABLE SCAN|t2  |1000     |455 |
    14. =====================================
    16. Outputs & filters:
    17. -------------------------------------
    18.   0 - output([t1.a], [t1.b], [t1.c], [t2.a], [t2.b], [t2.c]), filter(nil),
    19.       equal_conds([t1.c = t2.c]), other_conds(nil)
    20.   1 - output([t1.a], [t1.b], [t1.c]), filter(nil), sort_keys([t1.c, ASC])
    21.   2 - output([t1.c], [t1.a], [t1.b]), filter(nil),
    22.       access([t1.c], [t1.a], [t1.b]), partitions(p0)
    23.   3 - output([t2.a], [t2.b], [t2.c]), filter(nil), sort_keys([t2.c, ASC])
    24.   4 - output([t2.c], [t2.a], [t2.b]), filter(nil),
    25.       access([t2.c], [t2.a], [t2.b]), partitions(p0)
    26. OceanBase (root@test)> explain select/*+use_merge(t1 t2),index(t1 k1),index(t2 k1)*/ * from t1, t2 where t1.b = t2.b;
    27. | =======================================
    28. |ID|OPERATOR   |NAME  |EST. ROWS|COST |
    29. ---------------------------------------
    30. |0 |MERGE JOIN |      |1980     |12748|
    31. |1 | TABLE SCAN|t1(k1)|1000     |5566 |
    32. |2 | TABLE SCAN|t2(k1)|1000     |5566 |
    33. =======================================
    35. Outputs & filters:
    36. -------------------------------------
    37.   0 - output([t1.a], [t1.b], [t1.c], [t2.a], [t2.b], [t2.c]), filter(nil),
    38.       equal_conds([t1.b = t2.b]), other_conds(nil)
    39.   1 - output([t1.b], [t1.a], [t1.c]), filter(nil),
    40.       access([t1.b], [t1.a], [t1.c]), partitions(p0)
    41.   2 - output([t2.b], [t2.a], [t2.c]), filter(nil),
    42.       access([t2.b], [t2.a], [t2.c]), partitions(p0)

    Hash Join

    Hash Join就是用两个表中相对较小的表(通常称为build table)根据连接条件创建hash table，然后逐行扫描较大的表（通常称为prob table）并通过探测hash table找到匹配的行。 如果build table非常大，构建的hash table无法在内存中容纳时，Oceanbase会分别将build table和probe table按照连接条件切分成多个分区（partition），每个partition都包括一个独立的、成对匹配的build table和probe table，这样就将一个大的hash join切分成多个独立、互相不影响的hash join，每一个分区的hash join都能够在内存中完成。在绝大多数情况下，Hash Join效率比其他join方式效率更高。下图展示了一个Hash Join的计划。

    1. OceanBase (root@test)> create table t1(a int primary key, b int, c int, key k1(b));
    2. Query OK, 0 rows affected (0.24 sec)
    3. OceanBase (root@test)> create table t2(a int primary key, b int, c int, key k1(b));
    4. Query OK, 0 rows affected (0.29 sec)
    5. OceanBase (root@test)> explain select/*+use_hash(t1 t2)*/ * from t1, t2 where t1.c = t2.c;
    6. | ====================================
    7. |ID|OPERATOR   |NAME|EST. ROWS|COST|
    8. ------------------------------------
    9. |0 |HASH JOIN  |    |1980     |4093|
    10. |1 | TABLE SCAN|t1  |1000     |455 |
    11. |2 | TABLE SCAN|t2  |1000     |455 |
    12. ====================================
    14. Outputs & filters:
    15. -------------------------------------
    16.   0 - output([t1.a], [t1.b], [t1.c], [t2.a], [t2.b], [t2.c]), filter(nil),
    17.       equal_conds([t1.c = t2.c]), other_conds(nil)
    18.   1 - output([t1.c], [t1.a], [t1.b]), filter(nil),
    19.       access([t1.c], [t1.a], [t1.b]), partitions(p0)
    20.   2 - output([t2.c], [t2.a], [t2.b]), filter(nil),
    21.       access([t2.c], [t2.a], [t2.b]), partitions(p0)