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>