JOIN · k8s原理与实践

[TOC] # JOIN JOIN 算子用于将两张表的数据，按照特定的条件进行联接。 JOIN 的类型主要包括内联接（INNER JOIN）、外联接（OUTER JOIN）和半联接（SEMI/ANTI JOIN）三种。 OceanBase 数据库支持的 JOIN 算子主要有 NESTED LOOP JOIN (NLJ)、MERGE JOIN (MJ) 和 HASH JOIN (HJ)。 ## NESTED LOOP JOIN (NLJ) 如下示例中，Q1 和 Q2 查询使用 HINT 指定了查询使用 NLJ。其中，0 号算子是一个 NLJ 算子。这个算子存在两个子节点，分别是 1 号算子和 2 号算子，它的执行逻辑为： 1. 从 1 号算子读取一行。 2. 打开 2 号算子，读取所有的行。 3. 联接接 1和 2 号算子的输出结果，并执行过滤条件，输出结果。 4. 重复第一步，直到 1 号算子迭代结束。 ~~~ obclient>CREATE TABLE t1 (c1 INT, c2 INT); Query OK, 0 rows affected (0.12 sec) obclient>CREATE TABLE t2 (d1 INT, d2 INT, PRIMARY KEY (d1)); Query OK, 0 rows affected (0.12 sec) Q1: obclient>EXPLAIN SELECT /*+USE_NL(t1, t2)*/ t1.c2 + t2.d2 FROM t1, t2 WHERE c2 = d2\G; *************************** 1. row *************************** Query Plan: =========================================== |ID|OPERATOR |NAME|EST. ROWS|COST | ------------------------------------------- |0 |NESTED-LOOP JOIN| |9782 |411238| |1 | TABLE SCAN |T1 |999 |647 | |2 | MATERIAL | |999 |1519 | |3 | TABLE SCAN |T2 |999 |647 | =========================================== Outputs & filters: ------------------------------------- 0 - output([T1.C2 + T2.D2]), filter(nil), conds([T1.C2 = T2.D2]), nl_params_(nil) 1 - output([T1.C2]), filter(nil), access([T1.C2]), partitions(p0) 2 - output([T2.D2]), filter(nil) 3 - output([T2.D2]), filter(nil), access([T2.D2]), partitions(p0) ~~~ 其中，MATERIAL 算子用于物化下层算子输出的数据，详细信息请参见[MATERIAL](https://open.oceanbase.com/docs/community/oceanbase-database/V3.1.0/MATERIAL-1-2)。 ~~~ Q2: obclient>EXPLAIN SELECT /*+USE_NL(t1, t2)*/ t1.c2 + t2.d2 FROM t1, t2 WHERE c1 = d1\G; *************************** 1. row *************************** Query Plan: | ========================================== |ID|OPERATOR |NAME|EST. ROWS|COST | ------------------------------------------ |0 |NESTED-LOOP JOIN| |990 |37346| |1 | TABLE SCAN |T1 |999 |669 | |2 | TABLE GET |T2 |1 |36 | ========================================== Outputs & filters: ------------------------------------- 0 - output([T1.C2 + T2.D2]), filter(nil), conds(nil), nl_params_([T1.C1]) 1 - output([T1.C1], [T1.C2]), filter(nil), access([T1.C1], [T1.C2]), partitions(p0) 2 - output([T2.D2]), filter(nil), access([T2.D2]), partitions(p0) ~~~ 上述示例中，执行计划展示中的 outputs & filters 详细展示了 NESTED LOOP JOIN 算子的具体输出信息如下： | **信息名称** | **含义** | | --- | --- | | output | 该算子输出的表达式。 | | filter | 该算子上的过滤条件。由于示例中 NLJ 算子没有设置 filter，所以为 nil。 | | conds | 联接条件。例如 Q1 查询中`t1.c2 = t2.d2`联接条件。 | | nl\_params\_ | 根据 NLJ 左表的数据产生的下推参数。例如 Q2 查询中的`t1.c1`。 NLJ 在迭代到左表的每一行时，都会根据`nl_params`构造一个参数，根据这个参数和原始的联接条件`c1 = d1`，构造一个右表上的过滤条件：`d1 = ?`。这个过滤条件会下推到右表上，并抽取索引上的查询范围，即需要扫描索引哪个范围的数据。在 Q2 查询中，由于存在下推条件`d1 = ?`，所以 2 号算子是 TABLE GET 算子。 | 如下示例中，Q3 查询中没有指定任何的联接条件，0 号算子展示成了一个`NESTED-LOOP JOIN CARTESIAN`，逻辑上它还是一个 NLJ 算子，代表一个没有任何联接条件的 NLJ。 ~~~ Q3: obclient>EXPLAIN SELECT t1.c2 + t2.d2 FROM t1, t2\G; *************************** 1. row *************************** Query Plan: | ===================================================== |ID|OPERATOR |NAME|EST. ROWS|COST | ----------------------------------------------------- |0 |NESTED-LOOP JOIN CARTESIAN| |998001 |747480| |1 | TABLE SCAN |T1 |999 |647 | |2 | MATERIAL | |999 |1519 | |3 | TABLE SCAN |T2 |999 |647 | ===================================================== Outputs & filters: ------------------------------------- 0 - output([T1.C2 + T2.D2]), filter(nil), conds(nil), nl_params_(nil) 1 - output([T1.C2]), filter(nil), access([T1.C2]), partitions(p0) 2 - output([T2.D2]), filter(nil) 3 - output([T2.D2]), filter(nil), access([T2.D2]), partitions(p0) ~~~ ## MERGE JOIN (MJ) 如下示例中，Q4 查询使用`USE_MERGE`的 HINT 指定了查询使用 MJ。其中，0 号算子是一个 MJ 算子，它有两个子节点，分别是 1 和 3 号算子。该算子会对左右子节点的数据进行归并联接，因此，要求左右子节点的数据相对于联接列是有序的。以 Q4 查询为例，联接条件为`t1.c2 = t2.d2`，它要求 t1 的数据是按照 c2 排序的，t2 的数据是按照 d2 排序的。在 Q4 查询中，2 号算子的输出是无序的；4 号算子的输出是按照 d2 排序的，均不满足 MERGE JOIN 对序的要求，因此，分配了 1 和 3 号算子进行排序。 ~~~ Q4: obclient>EXPLAIN SELECT /*+USE_MERGE(t1, t2)*/ t1.c2 + t2.d2 FROM t1, t2 WHERE c2 = d2 AND c1 + d1 > 10\G; *************************** 1. row *************************** Query Plan: | ====================================== |ID|OPERATOR |NAME|EST. ROWS|COST | -------------------------------------- |0 |MERGE JOIN | |3261 |14199| |1 | SORT | |999 |4505 | |2 | TABLE SCAN|T1 |999 |669 | |3 | SORT | |999 |4483 | |4 | TABLE SCAN|T2 |999 |647 | ====================================== Outputs & filters: ------------------------------------- 0 - output([T1.C2 + T2.D2]), filter(nil), equal_conds([T1.C2 = T2.D2]), other_conds([T1.C1 + T2.D1 > 10]) 1 - output([T1.C2], [T1.C1]), filter(nil), sort_keys([T1.C2, ASC]) 2 - output([T1.C2], [T1.C1]), filter(nil), access([T1.C2], [T1.C1]), partitions(p0) 3 - output([T2.D2], [T2.D1]), filter(nil), sort_keys([T2.D2, ASC]) 4 - output([T2.D2], [T2.D1]), filter(nil), access([T2.D2], [T2.D1]), partitions(p0) ~~~ 如下示例中，Q5 查询中联接条件是`t1.c1 = t2.d1`，它要求 t1 的数据是按照 c1 排序的，t2 的数据是按照 d1 排序的。在这个执行计划中，t2 选择了主表扫描，结果是按照 d1 有序的，因此不需要额外分配一个 SORT 算子。理想情况下，JOIN 的左右表选择了合适的索引，索引提供的数据顺序能够满足 MJ 的要求，此时不需要分配任何 SORT 算子。 ~~~ Q5: obclient>EXPLAIN SELECT /*+USE_MERGE(t1, t2)*/ t1.c2 + t2.d2 FROM t1, t2 WHERE c1 = d1\G; *************************** 1. row *************************** Query Plan: | ===================================== |ID|OPERATOR |NAME|EST. ROWS|COST| ------------------------------------- |0 |MERGE JOIN | |990 |6096| |1 | SORT | |999 |4505| |2 | TABLE SCAN|T1 |999 |669 | |3 | TABLE SCAN |T2 |999 |647 | ===================================== Outputs & filters: ------------------------------------- 0 - output([T1.C2 + T2.D2]), filter(nil), equal_conds([T1.C1 = T2.D1]), other_conds(nil) 1 - output([T1.C2], [T1.C1]), 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.D1], [T2.D2]), filter(nil), access([T2.D1], [T2.D2]), partitions(p0) ~~~ 上述示例中，执行计划展示的 outputs & filters 中详细展示了 MERGE JOIN 算子的具体输出信息如下： | **信息名称** | **含义** | | --- | --- | | output | 该算子输出的表达式。 | | filter | 该算子上的过滤条件。由于 MJ 算子没有设置 filter，所以为 nil。 | | equal\_conds | 归并联接时使用的等值联接条件，左右子节点的结果集相对于联接列必须是有序的。 | | other\_conds | 其他联接条件。例如 Q4 查询中的`t1.c1 + t2.d1 > 10`。 | ## HASH JOIN (HJ) 如下示例中，Q6 查询使用`USE_HASH`的 HINT 指定了查询使用 HJ。其中，0 号算子是一个 HJ 算子，它有两个子节点，分别是 1 和 2 号算子。该算子的执行逻辑步骤如下： 1. 读取左子节点的数据，根据联接列计算哈希值（例如`t1.c1`），构建一张哈希表。 2. 读取右子节点的数据，根据联接列计算哈希值（例如`t2.d1`），尝试与对应哈希表中 t1 的数据进行联接。 ~~~ Q6: obclient>EXPLAIN SELECT /*+USE_HASH(t1, t2)*/ t1.c2 + t2.d2 FROM t1, t2 WHERE c1 = d1 AND c2 + d2 > 1\G; *************************** 1. row *************************** Query Plan: | ==================================== |ID|OPERATOR |NAME|EST. ROWS|COST| ------------------------------------ |0 |HASH JOIN | |330 |4850| |1 | TABLE SCAN|T1 |999 |669 | |2 | TABLE SCAN|T2 |999 |647 | ==================================== Outputs & filters: ------------------------------------- 0 - output([T1.C2 + T2.D2]), filter(nil), equal_conds([T1.C1 = T2.D1]), other_conds([T1.C2 + T2.D2 > 1]) 1 - output([T1.C1], [T1.C2]), filter(nil), access([T1.C1], [T1.C2]), partitions(p0) 2 - output([T2.D1], [T2.D2]), filter(nil), access([T2.D1], [T2.D2]), partitions(p0) ~~~ 上述示例中，执行计划展示中的 outputs & filters 详细展示了 HASH JOIN 算子的输出信息如下： <table data-tag="table" id="table-8yx-mwt-i5p" class="table"><colgroup width="194" span="1" data-tag="col" id="col-mha-4k3-xug" colwidth="1*" colnum="1" colname="col1" style="width:50%" class="col"></colgroup><colgroup width="557" span="1" data-tag="col" id="col-1ka-zv9-5q7" colwidth="1*" colnum="2" colname="col2" style="width:50%" class="col"></colgroup><thead id="thead-gea-oio-sgm" class="thead"><tr id="tr-9kj-ide-bo9"><th id="td-tzy-kbn-2li"><p id="p-ifw-1qh-w08"><b>信息名称</b></p></th><th id="td-t7r-cn2-316"><p id="p-1nv-xy5-09t"><b>含义</b></p></th></tr></thead><tbody data-tag="tbody" id="tbody-oio-ain-7ts" class="tbody"><tr data-tag="tr" id="tr-whb-h0g-42d" class="tr"><td data-tag="td" id="td-kh4-fz8-hxm" class="td"><p id="p-ghi-3hc-r0u">output</p></td><td data-tag="td" id="td-pkk-q6l-zay" class="td"><p id="p-0qs-abu-1p1">该算子输出的表达式。</p></td></tr><tr data-tag="tr" id="tr-byl-ntl-0ba" class="tr"><td data-tag="td" id="td-3xp-w5l-8d0" class="td"><p id="p-pgn-3v0-2gz">filter</p></td><td data-tag="td" id="td-c56-atv-0u4" class="td"><p data-tag="p" id="p-p7w-mty-njv" class="p">该算子上的过滤条件。</p><p data-tag="p" id="p-jkl-nln-8fi" class="p">由于 HJ 算子没有设置 filter，所以为 nil。</p></td></tr><tr data-tag="tr" id="tr-f3j-0p6-3p5" class="tr"><td data-tag="td" id="td-ftb-ltx-kwx" class="td"><p id="p-m5r-nzw-8ay">equal_conds</p></td><td data-tag="td" id="td-b5m-yl1-9uy" class="td"><p data-tag="p" id="p-e2v-p2u-uz9" class="p">等值联接，左右两侧的联接列会用于计算哈希值。</p></td></tr><tr data-tag="tr" id="tr-6ya-809-5x3" class="tr"><td data-tag="td" id="td-f6c-kix-l28" class="td"><p data-tag="p" id="p-mh4-cu3-elh" class="p">other_conds</p></td><td data-tag="td" id="td-v1x-5x7-q7u" class="td"><p data-tag="p" id="p-cll-4xj-tw4" class="p">其他联接条件。</p><p data-tag="p" id="p-w9v-uq1-gha" class="p">例如 Q6 查询中的 <code data-tag="code" class="code">t1.c2 + t2.d2 > 1</code>。</p></td></tr></tbody></table>