For queries to join multiple tables, an important task of the optimizer is to determine the Join Order of tables, which has effects on the size of the intermediate result sets and the overall cost of plan execution.
To reduce the search range and memory usage for plan execution, the OceanBase Database optimizer uses the left-deep join tree to determine the join order.
The following figure shows the shapes of a left-deep tree, a right-deep tree, and a bushy tree.
OceanBase Database uses the System-R dynamic programming algorithm to generate the join order. It takes into account many factors, such as the possible access paths of each table, Interesting Order, join selectivity of different tables, and join algorithms (Nested Loop Join, Block Based Nested Loop Join, and Sort Merge Join).
To join N tables, OceanBase Database determines the join order in the following steps:
Generate an access path for every base table and reserve the path that has the lowest cost and those with the Interesting Order. If a path has an Interesting Order, its order is usable by subsequent operators.
Generate all plans with a table set size of
i (1 < i <= N). OceanBase Database generally only chooses the left-deep tree. A plan with a table set size ofican comprise a plan of its own and a base table plan. Based on this strategy, OceanBase Database generates all plans with a table set size ofi, taking into account factors such as all join algorithms and the inheritance of the Interesting Order. Again, only the plan that has the lowest cost and plans with an Interesting Order are kept.
OceanBase Database also allows you to use the hint /*+LEADING(table_name_list)*/ to control the order of a multi-table join.
In the following example, tables t1 and t2 are joined first, followed by table t3. If you want to join tables t2 and t3 first before the join of t1, you can add the hint /*+LEADING(t2,t3,t1)*/ to the query. If you want to join t1 and t3 first before the join of t2, you can add the hint /*+LEADING(t1,t3,t2)*/.
obclient> CREATE TABLE t1(c1 INT, c2 INT, PRIMARY KEY(c1));
Query OK, 0 rows affected
obclient> CREATE TABLE t2(c1 INT, c2 INT, PRIMARY KEY(c1));
Query OK, 0 rows affected
obclient> CREATE TABLE t3(c1 INT, c2 INT, PRIMARY KEY(c1));
Query OK, 0 rows affected
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)