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.html#)。 ~~~ 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 算子的具体输出信息如下： <table data-tag="table" id="table-9ao-pos-h15" class="table"><colgroup width="175" span="1" data-tag="col" id="col-cmw-vf9-xse" colwidth="1*" colnum="1" colname="col1" style="width:50%" class="col"></colgroup><colgroup width="557" span="1" data-tag="col" id="col-0su-522-etl" colwidth="1*" colnum="2" colname="col2" style="width:50%" class="col"></colgroup><thead id="thead-pzc-xxn-f99" class="thead"><tr id="tr-jxk-vmc-ii7"><th id="td-ift-col-zfw"><p id="p-hps-3hn-376"><b>信息名称</b></p></th><th id="td-14d-znw-dko"><p id="p-j50-6ei-cmr"><b>含义</b></p></th></tr></thead><tbody data-tag="tbody" id="tbody-kyx-0n0-wik" class="tbody"><tr data-tag="tr" id="tr-m83-rx6-kf9" class="tr"><td data-tag="td" id="td-lpe-wkr-fym" class="td"><p id="p-5ws-yoz-68o">output</p></td><td data-tag="td" id="td-r0x-k8i-kjm" class="td"><p id="p-1mu-fvu-j2m">该算子输出的表达式。</p></td></tr><tr data-tag="tr" id="tr-wnl-2cj-uxm" class="tr"><td data-tag="td" id="td-qc9-1sa-3np" class="td"><p id="p-n90-jgt-gb9">filter</p></td><td data-tag="td" id="td-0uo-82k-lql" class="td"><p id="p-h6d-tcm-fzg">该算子上的过滤条件。</p><p id="p-dfm-a9d-nl6">由于示例中 NLJ 算子没有设置 filter，所以为 nil。</p></td></tr><tr data-tag="tr" id="tr-kwx-cs5-bj6" class="tr"><td data-tag="td" id="td-xzr-1jf-bw6" class="td"><p id="p-hyy-4a1-c5g">conds</p></td><td data-tag="td" id="td-wcl-evp-a6k" class="td"><p id="p-v7e-q8w-y92">联接条件。</p><p id="p-v7o-cb5-6d8">例如 Q1 查询中 <code data-tag="code" class="code">t1.c2 = t2.d2</code> 联接条件。</p></td></tr><tr data-tag="tr" id="tr-r7h-cdq-slg" class="tr"><td data-tag="td" id="td-of9-jfn-d6k" class="td"><p id="p-vso-mb0-6b9">nl_params_</p></td><td data-tag="td" id="td-yx1-1s5-5mn" class="td"><p id="p-cy6-1eb-69r">根据 NLJ 左表的数据产生的下推参数。</p><p id="p-1jd-izf-554">例如 Q2 查询中的 <code data-tag="code" class="code">t1.c1</code>。</p><p id="p-k6h-1le-2rr">NLJ 在迭代到左表的每一行时，都会根据 <code data-tag="code" class="code">nl_params</code> 构造一个参数，根据这个参数和原始的联接条件 <code data-tag="code" class="code">c1 = d1</code> ，构造一个右表上的过滤条件： <code data-tag="code" class="code">d1 = ?</code>。这个过滤条件会下推到右表上，并抽取索引上的查询范围，即需要扫描索引哪个范围的数据。在 Q2 查询中，由于存在下推条件 <code data-tag="code" class="code">d1 = ?</code>，所以 2 号算子是 TABLE GET 算子。</p></td></tr></tbody></table> 如下示例中，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 算子的具体输出信息如下： <table data-tag="table" id="table-702-w2k-qqd" class="table"><colgroup width="194" span="1" data-tag="col" id="col-buz-q9u-mvv" colwidth="1*" colnum="1" colname="col1" style="width:50%" class="col"></colgroup><colgroup width="557" span="1" data-tag="col" id="col-e84-4la-nav" colwidth="1*" colnum="2" colname="col2" style="width:50%" class="col"></colgroup><thead id="thead-893-o7w-bop" class="thead"><tr id="tr-q96-8t6-uck"><th id="td-d21-par-96a"><p id="p-y0f-2i0-g2h"><b>信息名称</b></p></th><th id="td-c1b-t8k-ph3"><p id="p-7l9-mz0-ny2"><b>含义</b></p></th></tr></thead><tbody data-tag="tbody" id="tbody-u32-704-9ah" class="tbody"><tr data-tag="tr" id="tr-9gd-r8d-zkj" class="tr"><td data-tag="td" id="td-eqd-ofe-99b" class="td"><p id="p-yrn-3g2-omi">output</p></td><td data-tag="td" id="td-25e-is1-qvo" class="td"><p id="p-zdk-nob-v3g">该算子输出的表达式。</p></td></tr><tr data-tag="tr" id="tr-qld-r2q-8hq" class="tr"><td data-tag="td" id="td-gul-l2p-iea" class="td"><p id="p-d0g-72u-0q4">filter</p></td><td data-tag="td" id="td-jpl-err-pv2" class="td"><p data-tag="p" id="p-soc-x1t-ifa" class="p">该算子上的过滤条件。</p><p data-tag="p" id="p-ldc-1uu-sbs" class="p">由于 MJ 算子没有设置 filter，所以为 nil。</p></td></tr><tr data-tag="tr" id="tr-klb-6g7-qhv" class="tr"><td data-tag="td" id="td-jp4-921-0gw" class="td"><p id="p-7hj-k84-uc6">equal_conds</p></td><td data-tag="td" id="td-4jc-q0j-9so" class="td"><p data-tag="p" id="p-qod-c9z-b76" class="p">归并联接时使用的等值联接条件，左右子节点的结果集相对于联接列必须是有序的。</p></td></tr><tr data-tag="tr" id="tr-3t3-sv2-838" class="tr"><td data-tag="td" id="td-szm-ghg-exs" class="td"><p data-tag="p" id="p-80v-hqf-pob" class="p">other_conds</p></td><td data-tag="td" id="td-53g-m83-a4a" class="td"><p data-tag="p" id="p-dkp-0kk-6ik" class="p">其他联接条件。</p><p data-tag="p" id="p-uf2-dx8-4wz" class="p">例如 Q4 查询中的 <code data-tag="code" class="code">t1.c1 + t2.d1 > 10</code> 。</p></td></tr></tbody></table> ## 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>