聯接順序 · k8s原理與實踐

[TOC] # 聯接順序在多表聯接的場景中，優化器的一個很重要的任務是決定各個表之間的聯接順序（Join Order），因為不同的聯接順序會影響中間結果集的大小，進而影響到計劃整體的執行代價。為了減少執行計劃的搜索空間和計劃執行的內存占用，OceanBase 數據庫優化器在生成聯接順序時主要考慮左深樹的聯接形式。下圖展示了左深樹、右深樹和多支樹的計劃形狀。 ![](https://img.kancloud.cn/07/4c/074c733b168e851fbd62583eeff9fbf6_804x317.png) OceanBase 數據庫聯接順序的生成采用了 System-R 的動態規劃算法，考慮的因素包括每一個表可能的訪問路徑、Interesting Order、聯接算法（NESTED-LOOP、BLOCK-BASED NESTED-LOOP 或者 SORT-MERGE 等）以及不同表之間的聯接選擇率等。給定 N 個表的聯接，OceanBase 數據庫生成聯接順序的方法如下: 1. 為每一個基表生成訪問路徑，保留代價最小的訪問路徑以及有所有有 Interesting Order 的路徑。一個路徑如果具有 Interesting Order，它的序能夠被后續的算子使用。 2. 生成所有表集合的大小為`i (1 < i <= N)`的計劃。 OceanBase 數據庫一般只考慮左深樹，表集合大小為 i 的計劃可以由一個表集合大小為 i 的計劃和一個基表的計劃組成。OceanBase 數據庫按照這種策略，考慮了所有的聯接算法以及 Interesting Order 的繼承等因素把所有表集合大小為 i 的計劃生成。這里也只是保留代價最小的計劃以及所有具有 Interesting Order 的計劃。同時，OceanBase 數據庫提供了 HINT 機制`/*+LEADING(table_name_list)*/`去控制多表聯接的順序。如下例所示，開始選擇的聯接順序是先做 t1、t2 的 JOIN 聯接，然后再和 t3 做 JOIN 聯接；如果用戶希望先做 t2、t3 的 JOIN 聯接，然后再和 t1做 JOIN 聯接，則可以使用 HINT`/*+LEADING(t2,t3,t1)*/`去控制；如果用戶希望先做 t1、t3 的 JOIN 聯接，然后再和 t2 做 JOIN 聯接，則可以使用 HINT`/*+LEADING(t1,t3,t2)*/`去控制。 ~~~ 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>CREATE TABLE t3(c1 INT, c2 INT, PRIMARY KEY(c1)); Query OK, 0 rows affected (0.44 sec) obclient>EXPLAIN SELECT * FROM t1,t2,t3 WHERE t1.c1 = t2.c2 AND t2.c1 = t3.c2; +-----------------------------------------------------------------+ | Query Plan | +-----------------------------------------------------------------+ | ======================================= |ID|OPERATOR |NAME|EST. ROWS|COST | --------------------------------------- |0 |HASH JOIN | |98010 |926122| |1 | TABLE SCAN |T3 |100000 |61860 | |2 | HASH JOIN | |99000 |494503| |3 | TABLE SCAN|T1 |100000 |61860 | |4 | TABLE SCAN|T2 |100000 |61860 | ======================================= Outputs & filters: ------------------------------------- 0 - output([T1.C1], [T1.C2], [T2.C1], [T2.C2], [T3.C1], [T3.C2]), filter(nil), equal_conds([T2.C1 = T3.C2]), other_conds(nil) 1 - output([T3.C2], [T3.C1]), filter(nil), access([T3.C2], [T3.C1]), partitions(p0) 2 - output([T1.C1], [T1.C2], [T2.C1], [T2.C2]), filter(nil), equal_conds([T1.C1 = T2.C2]), other_conds(nil) 3 - output([T1.C1], [T1.C2]), filter(nil), access([T1.C1], [T1.C2]), partitions(p0) 4 - output([T2.C2], [T2.C1]), filter(nil), access([T2.C2], [T2.C1]), partitions(p0) obclient>EXPLAIN SELECT /*+LEADING(t2,t3,t1)*/* FROM t1,t2,t3 WHERE t1.c1 = t2.c2 AND t2.c1 = t3.c2; +-----------------------------------------------------------------+ | Query Plan | +-----------------------------------------------------------------+ | ======================================== |ID|OPERATOR |NAME|EST. ROWS|COST | ---------------------------------------- |0 |HASH JOIN | |98010 |1096613| |1 | HASH JOIN | |99000 |494503 | |2 | TABLE SCAN|T2 |100000 |61860 | |3 | TABLE SCAN|T3 |100000 |61860 | |4 | TABLE SCAN |T1 |100000 |61860 | ======================================== Outputs & filters: ------------------------------------- 0 - output([T1.C1], [T1.C2], [T2.C1], [T2.C2], [T3.C1], [T3.C2]), filter(nil), equal_conds([T1.C1 = T2.C2]), other_conds(nil) 1 - output([T2.C1], [T2.C2], [T3.C1], [T3.C2]), filter(nil), equal_conds([T2.C1 = T3.C2]), other_conds(nil) 2 - output([T2.C2], [T2.C1]), filter(nil), access([T2.C2], [T2.C1]), partitions(p0) 3 - output([T3.C2], [T3.C1]), filter(nil), access([T3.C2], [T3.C1]), partitions(p0) 4 - output([T1.C1], [T1.C2]), filter(nil), access([T1.C1], [T1.C2]), partitions(p0) obclient>EXPLAIN SELECT /*+LEADING(t1,t3,t2)*/* FROM t1,t2,t3 WHERE t1.c1 = t2.c2 AND t2.c1 = t3.c2; +-----------------------------------------------------------------+ | Query Plan | +-----------------------------------------------------------------+ | ============================================================= |ID|OPERATOR |NAME|EST. ROWS |COST | ------------------------------------------------------------- |0 |HASH JOIN | |98010 |53098071243| |1 | NESTED-LOOP JOIN CARTESIAN| |10000000000|7964490204 | |2 | TABLE SCAN |T1 |100000 |61860 | |3 | MATERIAL | |100000 |236426 | |4 | TABLE SCAN |T3 |100000 |61860 | |5 | TABLE SCAN |T2 |100000 |61860 | ============================================================= Outputs & filters: ------------------------------------- 0 - output([T1.C1], [T1.C2], [T2.C1], [T2.C2], [T3.C1], [T3.C2]), filter(nil), equal_conds([T1.C1 = T2.C2], [T2.C1 = T3.C2]), other_conds(nil) 1 - output([T1.C1], [T1.C2], [T3.C1], [T3.C2]), filter(nil), conds(nil), nl_params_(nil) 2 - output([T1.C1], [T1.C2]), filter(nil), access([T1.C1], [T1.C2]), partitions(p0) 3 - output([T3.C1], [T3.C2]), filter(nil) 4 - output([T3.C2], [T3.C1]), filter(nil), access([T3.C2], [T3.C1]), partitions(p0) 5 - output([T2.C2], [T2.C1]), filter(nil), access([T2.C2], [T2.C1]), partitions(p0) ~~~