聯接算法 · 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) ~~~