联接算法 · k8s原理与实践

[TOC] # 联接算法 OceanBase 数据库当前版本支持 NESTED LOOP JOIN、 HASH JOIN 和 MERGE 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 都可以根据索引快速找到满足条件的匹配行。 ~~~ obclient>CREATE TABLE t1(a INT PRIMARY KEY, b INT, c INT, KEY k1(b)); Query OK, 0 rows affected (0.24 sec) obclient>>CREATE TABLE t2(a INT PRIMARY KEY, b INT, c INT, KEY k1(b)); Query OK, 0 rows affected (0.29 sec) obclient> EXPLAIN EXTENDED_NOADDR SELECT/*+USE_NL(t1 t2)*/ * FROM t1, t2 WHERE t1.c = t2.c; +-----------------------------------------------------------------+ | Query Plan | +-----------------------------------------------------------------+ | =========================================== |ID|OPERATOR |NAME|EST. ROWS|COST | ------------------------------------------- |0 |NESTED-LOOP JOIN| |1980 |623742| |1 | TABLE SCAN |t1 |1000 |455 | |2 | TABLE SCAN |t2 |2 |622 | =========================================== Outputs & filters: ------------------------------------- 0 - output([t1.a], [t1.b], [t1.c], [t2.a], [t2.b], [t2.c]), filter(nil), conds(nil), nl_params_([t1.c]) 1 - output([t1.c], [t1.a], [t1.b]), filter(nil), access([t1.c], [t1.a], [t1.b]), partitions(p0), is_index_back=false, range_key([t1.a]), range(MIN ; MAX)always true 2 - output([t2.c], [t2.a], [t2.b]), filter([? = t2.c]), access([t2.c], [t2.a], [t2.b]), partitions(p0), is_index_back=false, filter_before_indexback[false], range_key([t2.a]), range(MIN ; MAX) obclient> EXPLAIN EXTENDED_NOADDR SELECT/*+USE_NL(t1 t2)*/ * FROM t1, t2 WHERE t1.b = t2.b; +-----------------------------------------------------------------+ | Query Plan | +-----------------------------------------------------------------+ | ============================================ |ID|OPERATOR |NAME |EST. ROWS|COST | -------------------------------------------- |0 |NESTED-LOOP JOIN| |1980 |94876| |1 | TABLE SCAN |t1 |1000 |455 | |2 | TABLE SCAN |t2(k1)|2 |94 | ============================================ Outputs & filters: ------------------------------------- 0 - output([t1.a], [t1.b], [t1.c], [t2.a], [t2.b], [t2.c]), filter(nil), conds(nil), nl_params_([t1.b]) 1 - output([t1.b], [t1.a], [t1.c]), filter(nil), access([t1.b], [t1.a], [t1.c]), partitions(p0), is_index_back=false, range_key([t1.a]), range(MIN ; MAX)always true 2 - output([t2.b], [t2.a], [t2.c]), filter(nil), access([t2.b], [t2.a], [t2.c]), partitions(p0), is_index_back=true, range_key([t2.b], [t2.a]), range(MIN ; MAX), range_cond([? = t2.b]) ~~~ NESTED LOOP JOIN 可能会对内表进行多次全表扫描，因为每次扫描都需要从存储层重新迭代一次，这个代价相对是比较高的，所以 OceanBase 数据库支持对内表进行一次扫描并把结果物化在内存中，这样在下一次执行扫描时就可以直接在内存中扫描相关的数据，而不需要从存储层进行多次扫描。但是物化在内存中是有代价的，所以 OceanBase 数据库的优化器基于代价去判断是否需要物化内表。 NESTED LOOP JOIN 的一个优化变种是 BLOCKED NESTED LOOP JOIN，它每次从外表中读取一个 block 大小的行，然后再去扫描内表找到满足条件的数据，这样可以减少内表的读取次数。 NESTED LOOP JOIN 通常用在内表行数比较少，而且外表在联接条件的列上有索引的场景，因为内表中的每一行都可以快速的使用索引定位到相对应的匹配的数据。同时，OceanBase 数据库也提供了 HINT 机制`/*+ USE_NL(table_name_list) */`去控制多表联接的时候选择 NESTED LOOP JOIN。例如下述场景联接算法选择的是 HASH JOIN，而用户希望使用 NESTED LOOP JOIN，就可以使用上述 HINT 进行控制。 ~~~ obclient>CREATE TABLE t1(c1 INT, c2 INT); Query OK, 0 rows affected (0.97 sec) obclient>CREATE TABLE t2(c1 INT, c2 INT); Query OK, 0 rows affected (0.29 sec) obclient>EXPLAIN SELECT * FROM t1,t2 WHERE t1.c1 = t2.c1; +-----------------------------------------------------------------+ | Query Plan | +-----------------------------------------------------------------+ | ======================================== |ID|OPERATOR |NAME|EST. ROWS|COST | ---------------------------------------- |0 |HASH JOIN | |98010000 |66774608| |1 | TABLE SCAN|T1 |100000 |68478 | |2 | TABLE SCAN|T2 |100000 |68478 | ======================================== Outputs & filters: ------------------------------------- 0 - output([T1.C1], [T1.C2], [T2.C1], [T2.C2]), filter(nil), equal_conds([T1.C1 = T2.C1]), other_conds(nil) 1 - output([T1.C1], [T1.C2]), filter(nil), access([T1.C1], [T1.C2]), partitions(p0) 2 - output([T2.C1], [T2.C2]), filter(nil), access([T2.C1], [T2.C2]), partitions(p0) obclient>EXPLAIN SELECT /*+USE_NL(t1, c2)*/* FROM t1, t2 WHERE t1.c1 = t2.c1; +-----------------------------------------------------------------+ | Query Plan | +-----------------------------------------------------------------+ | =============================================== |ID|OPERATOR |NAME|EST. ROWS|COST | ----------------------------------------------- |0 |NESTED-LOOP JOIN| |98010000 |4595346207| |1 | TABLE SCAN |T1 |100000 |68478 | |2 | MATERIAL | |100000 |243044 | |3 | TABLE SCAN |T2 |100000 |68478 | =============================================== Outputs & filters: ------------------------------------- 0 - output([T1.C1], [T1.C2], [T2.C1], [T2.C2]), filter(nil), conds([T1.C1 = T2.C1]), nl_params_(nil) 1 - output([T1.C1], [T1.C2]), filter(nil), access([T1.C1], [T1.C2]), partitions(p0) 2 - output([T2.C1], [T2.C2]), filter(nil) 3 - output([T2.C1], [T2.C2]), filter(nil), access([T2.C1], [T2.C2]), partitions(p0) ~~~ NESTED LOOP JOIN 还有以下两种实现的算法： * 缓存块嵌套循环联接（BLOCKED NESTED LOOP JOIN） BLOCKED NESTED LOOP JOIN 在 OceanBase 数据库中的实现方式是 BATCH NESTED LOOP JOIN，通过从外表中批量读取数据行（默认是 1000 行），然后再去扫描内表找到满足条件的数据。这样将批量的数据与内层表的数据进行匹配，减少了内表的读取次数和内层循环的次数。如下示例中，`batch_join=true`字段表示本次查询使用了 BATCH NESTED LOOP JOIN。 ~~~ obclient>CREATE TABLE t1(c1 INT PRIMARY KEY); Query OK, 0 rows affected (0.97 sec) obclient>CREATE TABLE t2(c1 INT PRIMARY KEY); Query OK, 0 rows affected (0.97 sec) obclient>EXPLAIN EXTENDED_NOADDR SELECT /*+USE_NL(t1,t2)*/* FROM t1,t2 WHERE t1.c1=t2.c1\G; *************************** 1. row *************************** Query Plan: ============================================ |ID|OPERATOR |NAME|EST. ROWS|COST | -------------------------------------------- |0 |NESTED-LOOP JOIN| |100001 |3728786| |1 | TABLE SCAN |t1 |100000 |59654 | |2 | TABLE GET |t2 |1 |36 | ============================================ Outputs & filters: ------------------------------------- 0 - output([t1.c1], [t2.c1]), filter(nil), conds(nil), nl_params_([t1.c1]), inner_get=false, self_join=false, batch_join=true 1 - output([t1.c1]), filter(nil), access([t1.c1]), partitions(p0), is_index_back=false, range_key([t1.c1]), range(MIN ; MAX)always true 2 - output([t2.c1]), filter(nil), access([t2.c1]), partitions(p0), is_index_back=false, range_key([t2.c1]), range(MIN ; MAX), range_cond([? = t2.c1]) ~~~ * 索引嵌套循环联接（INDEX NESTED LOOP JOIN） INDEX NESTED LOOP JOIN 是基于索引进行联接的算法，通过外层表匹配条件直接与内层表索引进行匹配，避免和内层表的每条记录进行比较，减少了对内层表的匹配次数。如下示例中存在联接条件`t1.c1 = t2.c1`，则在 t2 表的 c1 列上有索引或 t1 表的 c1 列上有索引的时候，会使用 INDEX NESTED LOOP JOIN。 ~~~ obclient>CREATE TABLE t1(c1 INT PRIMARY KEY); Query OK, 0 rows affected (0.97 sec) obclient>CREATE TABLE t2(c1 INT ,c2 INT); Query OK, 0 rows affected (0.97 sec) obclient>EXPLAIN SELECT /*+ORDERED USE_NL(t2,t1)*/ * FROM t2, (SELECT /*+NO_MERGE*/ * FROM t1)t1 WHERE t1.c1 = t2.c1 AND t2.c2 = 1\G; *************************** 1. row *************************** Query Plan: =========================================== |ID|OPERATOR |NAME|EST. ROWS|COST | ------------------------------------------- |0 |NESTED-LOOP JOIN| |981 |117272| |1 | TABLE SCAN |t2 |990 |80811 | |2 | SUBPLAN SCAN |t1 |1 |37 | |3 | TABLE GET |t1 |1 |36 | =========================================== Outputs & filters: ------------------------------------- 0 - output([t2.c1], [t2.c2], [t1.c1]), filter(nil), conds(nil), nl_params_([t2.c1]) 1 - output([t2.c1], [t2.c2]), filter([t2.c2 = 1]), access([t2.c1], [t2.c2]), partitions(p0) 2 - output([t1.c1]), filter(nil), access([t1.c1]) 3 - output([t1.c1]), filter(nil), access([t1.c1]), partitions(p0) ~~~ 在 outputs & filters 的输出结果中`nl_param`出现参数`[t2.c1]`，说明执行了条件下压优化。详细信息请参考[JOIN](https://open.oceanbase.com/docs/community/oceanbase-database/V3.1.0/JOIN-1-2)。一般地，在进行查询优化时，OceanBase 数据库优化器会优先选择 INDEX NESTED LOOP JOIN，然后检查是否可以使用 BATCH NESTED LOOP JOIN，这两种优化方式可以一起使用，最后才会选择 NESTED LOOP JOIN。 ## MERGE JOIN MERGE JOIN 首先会按照联接的字段对两个表进行排序（如果内存空间不够，就需要进行外排），然后开始扫描两张表进行合并。合并的过程会从每个表取一条记录开始匹配，如果符合关联条件，则放入结果集中；否则，将关联字段值较小的记录抛弃，从这条记录对应的表中取下一条记录继续进行匹配，直到整个循环结束。在多对多的两张表上进行合并时，通常需要使用临时空间进行操作。例如 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 排序的）。 ~~~ obclient> CREATE TABLE t1(a INT PRIMARY KEY, b INT, c INT, KEY k1(b)); Query OK, 0 rows affected (0.24 sec) obclient> CREATE TABLE t2(a INT PRIMARY KEY, b INT, c INT, KEY k1(b)); Query OK, 0 rows affected (0.29 sec) obclient> EXPLAIN SELECT/*+USE_MERGE(t1 t2)*/ * FROM t1, t2 WHERE t1.c = t2.c; *************************** 1. row *************************** Query Plan: | ===================================== |ID|OPERATOR |NAME|EST. ROWS|COST| ------------------------------------- |0 |MERGE JOIN | |1980 |6011| |1 | SORT | |1000 |2198| |2 | TABLE SCAN|t1 |1000 |455 | |3 | SORT | |1000 |2198| |4 | TABLE SCAN|t2 |1000 |455 | ===================================== Outputs & filters: ------------------------------------- 0 - output([t1.a], [t1.b], [t1.c], [t2.a], [t2.b], [t2.c]), filter(nil), equal_conds([t1.c = t2.c]), other_conds(nil) 1 - output([t1.a], [t1.b], [t1.c]), filter(nil), sort_keys([t1.c, ASC]) 2 - output([t1.c], [t1.a], [t1.b]), filter(nil), access([t1.c], [t1.a], [t1.b]), partitions(p0) 3 - output([t2.a], [t2.b], [t2.c]), filter(nil), sort_keys([t2.c, ASC]) 4 - output([t2.c], [t2.a], [t2.b]), filter(nil), access([t2.c], [t2.a], [t2.b]), partitions(p0) obclient>EXPLAIN SELECT/*+USE_MERGE(t1 t2),INDEX(t1 k1),INDEX(t2 k1)*/ * FROM t1, t2 WHERE t1.b = t2.b; *************************** 1. row *************************** Query Plan: | ======================================= |ID|OPERATOR |NAME |EST. ROWS|COST | --------------------------------------- |0 |MERGE JOIN | |1980 |12748| |1 | TABLE SCAN|t1(k1)|1000 |5566 | |2 | TABLE SCAN|t2(k1)|1000 |5566 | ======================================= Outputs & filters: ------------------------------------- 0 - output([t1.a], [t1.b], [t1.c], [t2.a], [t2.b], [t2.c]), filter(nil), equal_conds([t1.b = t2.b]), other_conds(nil) 1 - output([t1.b], [t1.a], [t1.c]), filter(nil), access([t1.b], [t1.a], [t1.c]), partitions(p0) 2 - output([t2.b], [t2.a], [t2.c]), filter(nil), access([t2.b], [t2.a], [t2.c]), partitions(p0) ~~~ 同时，OceanBase 数据库也提供了 HINT 机制`/*+ USE_MERGE(table_name_list) */`去控制多表联接的时候选择 MERGE JOIN 联接算法。例如下述场景中联接算法选择的是 HASH JOIN，而用户希望使用 MERGE JOIN，则可以使用上述 HINT 进行控制。 ~~~ obclient>CREATE TABLE t1(c1 INT, c2 INT); Query OK, 0 rows affected (0.97 sec) obclient>CREATE TABLE t2(c1 INT, c2 INT); Query OK, 0 rows affected (0.29 sec) obclient>EXPLAIN SELECT * FROM t1,t2 WHERE t1.c1 = t2.c1; *************************** 1. row *************************** Query Plan: | ======================================== |ID|OPERATOR |NAME|EST. ROWS|COST | ---------------------------------------- |0 |HASH JOIN | |98010000 |66774608| |1 | TABLE SCAN|T1 |100000 |68478 | |2 | TABLE SCAN|T2 |100000 |68478 | ======================================== Outputs & filters: ------------------------------------- 0 - output([T1.C1], [T1.C2], [T2.C1], [T2.C2]), filter(nil), equal_conds([T1.C1 = T2.C1]), other_conds(nil) 1 - output([T1.C1], [T1.C2]), filter(nil), access([T1.C1], [T1.C2]), partitions(p0) 2 - output([T2.C1], [T2.C2]), filter(nil), access([T2.C1], [T2.C2]), partitions(p0) obclient>EXPLAIN SELECT /*+USE_MERGE(t1,t2)*/* FROM t1, t2 WHERE t1.c1 = t2.c1; *************************** 1. row *************************** Query Plan: | ========================================= |ID|OPERATOR |NAME|EST. ROWS|COST | ----------------------------------------- |0 |MERGE JOIN | |98010000 |67488837| |1 | SORT | |100000 |563680 | |2 | TABLE SCAN|T1 |100000 |68478 | |3 | SORT | |100000 |563680 | |4 | TABLE SCAN|T2 |100000 |68478 | ========================================= Outputs & filters: ------------------------------------- 0 - output([T1.C1], [T1.C2], [T2.C1], [T2.C2]), filter(nil), equal_conds([T1.C1 = T2.C1]), other_conds(nil) 1 - output([T1.C1], [T1.C2]), filter(nil), sort_keys([T1.C1, ASC]) 2 - output([T1.C1], [T1.C2]), filter(nil), access([T1.C1], [T1.C2]), partitions(p0) 3 - output([T2.C1], [T2.C2]), filter(nil), sort_keys([T2.C1, ASC]) 4 - output([T2.C1], [T2.C2]), filter(nil), access([T2.C1], [T2.C2]), partitions(p0) ~~~ ## HASH JOIN HASH JOIN 就是用两个表中相对较小的表（通常称为 build table）根据联接条件创建 hash table，然后逐行扫描较大的表（通常称为 probe 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 计划的示例。 ~~~ obclient> CREATE TABLE t1(a INT PRIMARY KEY, b INT, c INT, KEY k1(b)); Query OK, 0 rows affected (0.24 sec) obclient>CREATE TABLE t2(a INT PRIMARY KEY, b INT, c INT, KEY k1(b)); Query OK, 0 rows affected (0.29 sec) obclient> EXPLAIN SELECT/*+USE_HASH(t1 t2)*/ * FROM t1, t2 WHERE t1.c = t2.c; *************************** 1. row *************************** Query Plan: | ==================================== |ID|OPERATOR |NAME|EST. ROWS|COST| ------------------------------------ |0 |HASH JOIN | |1980 |4093| |1 | TABLE SCAN|t1 |1000 |455 | |2 | TABLE SCAN|t2 |1000 |455 | ==================================== Outputs & filters: ------------------------------------- 0 - output([t1.a], [t1.b], [t1.c], [t2.a], [t2.b], [t2.c]), filter(nil), equal_conds([t1.c = t2.c]), other_conds(nil) 1 - output([t1.c], [t1.a], [t1.b]), filter(nil), access([t1.c], [t1.a], [t1.b]), partitions(p0) 2 - output([t2.c], [t2.a], [t2.b]), filter(nil), access([t2.c], [t2.a], [t2.b]), partitions(p0) ~~~ 同时，OcenaBase 数据库也提供了 HINT 机制`/*+ USE_HASH(table_name_list) */`去控制多表联接的时候选择 HASH JOIN 联接算法。例如下述场景中联接算法选择的是 MERGE JOIN，而用户希望使用 HASH JOIN，则可以使用上述 HINT 进行控制。 ~~~ obclient>CREATE TABLE t1(c1 INT, c2 INT, PRIMARY KEY(c1)); Query OK, 0 rows affected (0.31 sec) obclient>CREATE TABLE t2(c1 INT, c2 INT, PRIMARY KEY(c1)); Query OK, 0 rows affected (0.33 sec) obclient>EXPLAIN SELECT * FROM t1, t2 WHERE t1.c1 = t2.c1; *************************** 1. row *************************** Query Plan: | ====================================== |ID|OPERATOR |NAME|EST. ROWS|COST | -------------------------------------- |0 |MERGE JOIN | |100001 |219005| |1 | TABLE SCAN|T1 |100000 |61860 | |2 | TABLE SCAN|T2 |100000 |61860 | ====================================== Outputs & filters: ------------------------------------- 0 - output([T1.C1], [T1.C2], [T2.C1], [T2.C2]), filter(nil), equal_conds([T1.C1 = T2.C1]), other_conds(nil) 1 - output([T1.C1], [T1.C2]), filter(nil), access([T1.C1], [T1.C2]), partitions(p0) 2 - output([T2.C1], [T2.C2]), filter(nil), access([T2.C1], [T2.C2]), partitions(p0) obclient>EXPLAIN SELECT /*+USE_HASH(t1, t2)*/ * FROM t1, t2 WHERE t1.c1 = t2.c1; *************************** 1. row *************************** Query Plan: | ====================================== |ID|OPERATOR |NAME|EST. ROWS|COST | -------------------------------------- |0 |HASH JOIN | |100001 |495180| |1 | TABLE SCAN|T1 |100000 |61860 | |2 | TABLE SCAN|T2 |100000 |61860 | ====================================== Outputs & filters: ------------------------------------- 0 - output([T1.C1], [T1.C2], [T2.C1], [T2.C2]), filter(nil), equal_conds([T1.C1 = T2.C1]), other_conds(nil) 1 - output([T1.C1], [T1.C2]), filter(nil), access([T1.C1], [T1.C2]), partitions(p0) 2 - output([T2.C1], [T2.C2]), filter(nil), access([T2.C1], [T2.C2]), partitions(p0) ~~~