#Join调优介绍
# Join Orders介绍
Join是SQL语法中最常见的一个特性，只要稍微复杂一点的业务场景都会用到Join。在入门知识中，已经大体介绍了计划是各个算子排列组合成的。对于Join来说，常常会有非常多的组合方式。这无疑使得选出一个最优的Join组合变得异常困难。
EXPLAIN SELECT * FROM t1, t2, t3, t4 WHERE t1.c1 = t2.c1 AND t2.c1 = t3.c1 AND t4.c1 = t2.c1;
PLAN_DESCRIPTION
----------------------------------------------------------------
SQL hash value: 745528657
Optimizer: ADOPT_C
+----+--------------------------------+----------------------+------------+----------+-------------+--------------------------------+
| Id | Operation type | Name | Owner | Rows | Cost(%CPU) | Partition info |
+----+--------------------------------+----------------------+------------+----------+-------------+--------------------------------+
| 0 | SELECT STATEMENT | | | | | |
|* 1 | HASH JOIN INNER | | | 1| 2137( 0)| |
| 2 | JOIN FILTER USE | | | 100000| 442( 0)| |
|* 3 | TABLE ACCESS FULL | T4 | REGRESS | 100000| 442( 0)| |
|* 4 | JOIN FILTER CREATE | | | 1| 1499( 0)| |
|* 5 | MERGE JOIN INNER | | | 1| 1499( 0)| |
| 6 | MERGE SORT | | | | | |
|* 7 | HASH JOIN INNER | | | 3| 1068( 0)| |
| 8 | TABLE ACCESS FULL | T1 | REGRESS | 100000| 442( 0)| |
| 9 | TABLE ACCESS FULL | T2 | REGRESS | 3| 431( 0)| |
| 10 | MERGE SORT | | | | | |
| 11 | TABLE ACCESS FULL | T3 | REGRESS | 3| 431( 0)| |
+----+--------------------------------+----------------------+------------+----------+-------------+--------------------------------+
Operation Information (identified by operation id):
---------------------------------------------------
1 - Predicate : access("T4"."C1" = "T2"."C1")
3 - Predicate : RUNTIME FILTER(RUNTIME USE(0): "T4"."C1")
4 - Predicate : RUNTIME FILTER(RUNTIME CREATE(0): "T2"."C1")
5 - Predicate : access( "T1"."C1" = "T3"."C1" )
7 - Predicate : access("T1"."C1" = "T2"."C1")
对于上述SQL语句来说，即使仅仅只有四层Join，在考虑Join算子种类、Join内Scan表的左右顺序的和Scan算子的种类的情况后，可能一共会几十种组合。
实际上，在数据库领域中的Join Orders本质就是一个NP hard难题。因此对于调优复杂Join来说，需要一些特定的技巧来规避如此大的解空间。
但在实际讲解如何进行Join调优之前，有必要对Join Orders相应的算法进行了解。这能有助于理解Join的生成方式，从而做到知其然，也知其所以然。
目前YashanDB中主要有两种Join算法：
- Dynamic Programming - 动态规划：
- 在小于等于八张表连接时，目前会采用DP算法确定Join Orders。DP算法本质上是一种穷举法。基本思路为n张表join时，可以给定一个数字k，1<k<n，best(1..n) =best(1..k) + best(k..n) + cost(join(1..k), join(k..n))。 通过循环或者递归实现最佳join order的生成。因此在DP算法和正确的cost model下，一定能够找最优的Join计划。
- Greedy Operator Ordering - 贪心算法：
- 在超过八张表连接时，YashanDB会采用GOO算法。这是因为随着表的数量增加，DP算法的复杂度已经无法支撑高效的Join Orders生成了。 因此需要另外一种算法进行Join Orders的选择。GOO算法可以描述如下：对于n个节点所组成的集合，两两组合从中找到join cost最小的两个节点。 将其join作为新的节点代替原来的两个节点；重复这一过程直到得到一个Join Tree。可以看到此算法的时间复杂度是O(n^3)，空间复杂度为O(n)。
# 复杂Join的调优
复杂Join的调优需要遵循一个大体原则：能够低成本过滤掉大量数据的Join优先执行。
EXPLAIN SELECT * FROM t1, t2, t3, t4 WHERE t1.c1 = t2.c1 AND t2.c1 = t3.c1 AND t4.c1 = t2.c1;
PLAN_DESCRIPTION
----------------------------------------------------------------
SQL hash value: 3320065567
Optimizer: ADOPT_C
+----+--------------------------------+----------------------+------------+----------+-------------+--------------------------------+
| Id | Operation type | Name | Owner | Rows | Cost(%CPU) | Partition info |
+----+--------------------------------+----------------------+------------+----------+-------------+--------------------------------+
| 0 | SELECT STATEMENT | | | | | |
|* 1 | MERGE JOIN INNER | | | 4| 1724( 0)| |
| 2 | MERGE SORT | | | | | |
|* 3 | MERGE JOIN INNER | | | 1| 1293( 0)| |
| 4 | MERGE SORT | | | | | |
|* 5 | HASH JOIN INNER | | | 1| 862( 0)| |
| 6 | TABLE ACCESS FULL | T1 | REGRESS | 79| 431( 0)| |
| 7 | TABLE ACCESS FULL | T2 | REGRESS | 3| 431( 0)| |
| 8 | MERGE SORT | | | | | |
| 9 | TABLE ACCESS FULL | T3 | REGRESS | 3| 431( 0)| |
| 10 | MERGE SORT | | | | | |
| 11 | TABLE ACCESS FULL | T4 | REGRESS | 13| 431( 0)| |
+----+--------------------------------+----------------------+------------+----------+-------------+--------------------------------+
Operation Information (identified by operation id):
---------------------------------------------------
1 - Predicate : access( "T2"."C1" = "T4"."C1" )
3 - Predicate : access( "T1"."C1" = "T3"."C1" )
5 - Predicate : access("T1"."C1" = "T2"."C1")
对于T1、T2这种能够提前过滤掉大部分数据的Join，在复杂Join调优时就应当让其提前。由于先执行了这类过滤性强的Join，使得后续需要执行的条数大大降低，从而降低了整体SQL的执行成本。
正常来说如果连接表数量低于8，SQL引擎本身的DP算法已经足够优秀去选出较好的Join Orders。而在连接表数量超过8时，由于GOO算法本身的不足，Join Orders可能会出现不够优秀的问题，导致SQL执行效率不理想，此时需要人工介入对这种复杂Join进行调优。
对于复杂Join的SQL来说，穷举所有Join Orders的情况进行调优是比较困难的。因此需要基于某些规则进行调优的尝试。大体的规则如下：
- 选择率判断：判断各个算子的Rows评估是否准确。
- 算子选择判断：判断各个算子的选择是否合理。
# 选择率判断
在算子上如果存在filter，则会对算子生成的rows进行一层过滤。而过滤多少的预估则是由选择率来实现的。如果选择率的估计不够准确，则会导致rows评估偏差较大。进而导致cost model产生误判，使得Join Orders不够优秀。
因此实际调优Join Orders的第一步往往都是查看选择率判断是否准确。
EXPLAIN SELECT * FROM t1, t2, t3 WHERE t1.c1 = t2.c1 SELECTIVITY 0.0001 AND t2.c1 = t3.c1;
PLAN_DESCRIPTION
----------------------------------------------------------------
SQL hash value: 234816895
Optimizer: ADOPT_C
+----+--------------------------------+----------------------+------------+----------+-------------+--------------------------------+
| Id | Operation type | Name | Owner | Rows | Cost(%CPU) | Partition info |
+----+--------------------------------+----------------------+------------+----------+-------------+--------------------------------+
| 0 | SELECT STATEMENT | | | | | |
|* 1 | MERGE JOIN INNER | | | 1| 1293( 0)| |
| 2 | MERGE SORT | | | | | |
|* 3 | HASH JOIN INNER | | | 1| 862( 0)| |
| 4 | TABLE ACCESS FULL | T1 | REGRESS | 79| 431( 0)| |
| 5 | TABLE ACCESS FULL | T2 | REGRESS | 3| 431( 0)| |
| 6 | MERGE SORT | | | | | |
| 7 | TABLE ACCESS FULL | T3 | REGRESS | 3| 431( 0)| |
+----+--------------------------------+----------------------+------------+----------+-------------+--------------------------------+
Operation Information (identified by operation id):
---------------------------------------------------
1 - Predicate : access( "T1"."C1" = "T3"."C1" )
3 - Predicate : access("T1"."C1" = "T2"."C1")
SELECT COUNT(*) FROM t1, t2 WHERE t1.c1 = t2.c1 SELECTIVITY 0.0001;
COUNT(*)
---------------------
79
在上述例子中，可以看到对于T1和T2由于错误的估计了Join后的剩余条数，使得T1和T2先进行了Join。这将会导致Join Orders的判断错误。使得最终计划不佳。在实际调优的时候，YashanDB提供了两个能力判断Rows的评估是否准确。
# explain
如上述例子所示，通过实际select出来的值和explain出来的值可以判断rows评估是否准确。具体使用可见EXPLAIN文档。
# autotrace
直接开启autotrace可以替代上述过程。具体使用可见AUTOTRACE文档。
SELECT * FROM t1, t2, t3 WHERE t1.c1 = t2.c1 SELECTIVITY 0.0001 AND t2.c1 = t3.c1;
Execution Plan
----------------------------------------------------------------
SQL hash value: 234816895
Optimizer: ADOPT_C
+----+--------------------------------+----------------------+------------+----------+----------+-------------+----------+----------+----------+----------+--------------------------------+
| Id | Operation type | Name | Owner | E - Rows | A - Rows | Cost(%CPU) | A - Time | Loops | Memory | Disk | Partition info |
+----+--------------------------------+----------------------+------------+----------+----------+-------------+----------+----------+----------+----------+--------------------------------+
| 0 | SELECT STATEMENT | | | | 79| | 354| 79| | | |
|* 1 | MERGE JOIN INNER | | | 1| 79| 1293( 0)| 341| 79| | | |
| 2 | MERGE SORT | | | | 79| | 242| 79| | | |
|* 3 | HASH JOIN INNER | | | 1| 79| 862( 0)| 188| 79| | | |
| 4 | TABLE ACCESS FULL | T1 | REGRESS | 79| 79| 431( 0)| 24| 79| | | |
| 5 | TABLE ACCESS FULL | T2 | REGRESS | 3| 3| 431( 0)| 53| 3| | | |
| 6 | MERGE SORT | | | | 59| | 42| 59| | | |
| 7 | TABLE ACCESS FULL | T3 | REGRESS | 3| 3| 431( 0)| 26| 3| | | |
+----+--------------------------------+----------------------+------------+----------+----------+-------------+----------+----------+----------+----------+--------------------------------+
Operation Information (identified by operation id):
---------------------------------------------------
1 - Predicate : access( "T1"."C1" = "T3"."C1" )
3 - Execution : [BUILD] Memory : 327680 [BUILD] Time : 133 [HDT] RehashTimes : 0 [HDT] OriginPrime : 131071
Predicate : access("T1"."C1" = "T2"."C1")
# 算子选择判断
除了选择率判断之外，选择的算子是否准确也至关重要。一个错误的算子选择常常会导致非常低的效率。下面也将结合例子展开描述。
EXPLAIN SELECT /*+LEADING(t1,t2) USE_HASH(t1,t2)*/ * FROM t1, t2, t3 WHERE t1.c1 = t2.c1 AND t2.c1 = t3.c1;
PLAN_DESCRIPTION
----------------------------------------------------------------
SQL hash value: 4196032415
Optimizer: ADOPT_C
+----+--------------------------------+----------------------+------------+----------+-------------+--------------------------------+
| Id | Operation type | Name | Owner | Rows | Cost(%CPU) | Partition info |
+----+--------------------------------+----------------------+------------+----------+-------------+--------------------------------+
| 0 | SELECT STATEMENT | | | | | |
|* 1 | HASH JOIN INNER | | | 1651424| 4545( 0)| |
|* 2 | HASH JOIN INNER | | | 1651424| 885( 0)| |
| 3 | TABLE ACCESS FULL | T1 | REGRESS | 2528| 431( 0)| |
| 4 | TABLE ACCESS FULL | T2 | REGRESS | 1899| 431( 0)| |
| 5 | TABLE ACCESS FULL | T3 | REGRESS | 3| 431( 0)| |
+----+--------------------------------+----------------------+------------+----------+-------------+--------------------------------+
Operation Information (identified by operation id):
---------------------------------------------------
1 - Predicate : access("T1"."C1" = "T3"."C1")
2 - Predicate : access("T1"."C1" = "T2"."C1")
EXPLAIN SELECT /*+LEADING(t1,t2) USE_NL(t1)*/ * FROM t1, t2, t3 WHERE t1.c1 = t2.c1 AND t2.c1 = t3.c1;
PLAN_DESCRIPTION
----------------------------------------------------------------
SQL hash value: 462255180
Optimizer: ADOPT_C
+----+--------------------------------+----------------------+------------+----------+-------------+--------------------------------+
| Id | Operation type | Name | Owner | Rows | Cost(%CPU) | Partition info |
+----+--------------------------------+----------------------+------------+----------+-------------+--------------------------------+
| 0 | SELECT STATEMENT | | | | | |
|* 1 | HASH JOIN INNER | | | 1651424| 4848( 0)| |
|* 2 | NESTED LOOPS INNER | | | 1651424| 1189( 0)| |
| 3 | TABLE ACCESS FULL | T1 | REGRESS | 2528| 431( 0)| |
| 4 | TABLE ACCESS FULL | T2 | REGRESS | 1899| 431( 0)| |
| 5 | TABLE ACCESS FULL | T3 | REGRESS | 3| 431( 0)| |
+----+--------------------------------+----------------------+------------+----------+-------------+--------------------------------+
Operation Information (identified by operation id):
---------------------------------------------------
1 - Predicate : access("T1"."C1" = "T3"."C1")
2 - Predicate : filter("T1"."C1" = "T2"."C1")
在上例中，可以看到选择Nested Loops Inner时比选择Hash Join Inner时，代价要大一些。这是因为Join相关算子有各自的适用场景，对于大表之间Join来说，采用Hash Join可能更为合适。 此外，如果两个表的Join列都是有序的，可能选择Merge Join比较合适。 在一些复杂的场景中，很容易出现类似Join相关算子选择错误的问题。比如在大表Join时没有索引的情况下选择了Nest Loop Join而不是选择Hash Join，以及选择Hash Join时采用了大表进行Hash表的创建。因此如果要对算子进行判断，需要了解各个算子相关的适用场景，做到对各个算子心中有数。
# hint调优
结合上述的两类问题，主要有三种hint可以对Join Orders进行调节。
- Join Hint.
- Index Hint.
- Selectivity Hint.
# 选择率调整
上述出现选择率问题时，可以通过Selectivity Hint来进行调整。
EXPLAIN SELECT * FROM t1, t2, t3 WHERE t1.c1 = t2.c1 SELECTIVITY 0.0001 AND t2.c1 = t3.c1;
PLAN_DESCRIPTION
----------------------------------------------------------------
SQL hash value: 234816895
Optimizer: ADOPT_C
+----+--------------------------------+----------------------+------------+----------+-------------+--------------------------------+
| Id | Operation type | Name | Owner | Rows | Cost(%CPU) | Partition info |
+----+--------------------------------+----------------------+------------+----------+-------------+--------------------------------+
| 0 | SELECT STATEMENT | | | | | |
|* 1 | HASH JOIN INNER | | | 480| 1317( 0)| |
|* 2 | HASH JOIN INNER | | | 480| 885( 0)| |
| 3 | TABLE ACCESS FULL | T1 | REGRESS | 2528| 431( 0)| |
| 4 | TABLE ACCESS FULL | T2 | REGRESS | 1899| 431( 0)| |
| 5 | TABLE ACCESS FULL | T3 | REGRESS | 3| 431( 0)| |
+----+--------------------------------+----------------------+------------+----------+-------------+--------------------------------+
Operation Information (identified by operation id):
---------------------------------------------------
1 - Predicate : access("T1"."C1" = "T3"."C1")
2 - Predicate : access("T1"."C1" = "T2"."C1")
EXPLAIN SELECT * FROM t1, t2, t3 WHERE t1.c1 = t2.c1 AND t2.c1 = t3.c1 SELECTIVITY 1;
PLAN_DESCRIPTION
----------------------------------------------------------------
SQL hash value: 2568121636
Optimizer: ADOPT_C
+----+--------------------------------+----------------------+------------+----------+-------------+--------------------------------+
| Id | Operation type | Name | Owner | Rows | Cost(%CPU) | Partition info |
+----+--------------------------------+----------------------+------------+----------+-------------+--------------------------------+
| 0 | SELECT STATEMENT | | | | | |
|* 1 | HASH JOIN INNER | | | 1651424| 1321( 0)| |
|* 2 | HASH JOIN INNER | | | 2528| 866( 0)| |
| 3 | TABLE ACCESS FULL | T1 | REGRESS | 2528| 431( 0)| |
| 4 | TABLE ACCESS FULL | T3 | REGRESS | 3| 431( 0)| |
| 5 | TABLE ACCESS FULL | T2 | REGRESS | 1899| 431( 0)| |
+----+--------------------------------+----------------------+------------+----------+-------------+--------------------------------+
Operation Information (identified by operation id):
---------------------------------------------------
1 - Predicate : access("T1"."C1" = "T2"."C1")
2 - Predicate : access("T1"."C1" = "T3"."C1")
可以看到，YashanDB通过Selectivity Hint的方式可以立竿见影的完成对Join Orders的调整。但这类的调整由于粒度较小，需要大体了解选择率相关的处理逻辑。 具体选择率生成相关原理可见：选择率与统计信息命令。
# 算子调整
算子的调整则粒度更大一些，直接通过hint的方式将执行的算子进行改变。在进行这类操作之前，需要对各个算子的原理以及优劣了解清楚。
EXPLAIN SELECT /*+INDEX(t1)*/ c1 FROM t1;
PLAN_DESCRIPTION
----------------------------------------------------------------
SQL hash value: 1102139983
Optimizer: ADOPT_C
+----+--------------------------------+----------------------+------------+----------+-------------+--------------------------------+
| Id | Operation type | Name | Owner | Rows | Cost(%CPU) | Partition info |
+----+--------------------------------+----------------------+------------+----------+-------------+--------------------------------+
| 0 | SELECT STATEMENT | | | | | |
| 1 | COL TO ROW | | | | | |
| 2 | INDEX FAST FULL SCAN | C1_T1 | REGRESS | 8| 142( 0)| |
+----+--------------------------------+----------------------+------------+----------+-------------+--------------------------------+
Operation Information (identified by operation id):
---------------------------------------------------
1 - Projection: RemoteTable[1][INTEGER]
2 - Projection: Tuple[0, 0][INTEGER]
上述例子中，由于只需要拿c1列不需要回表，所以我们可以使用hint指定走index scan。从而手动使得计划最优。对于其他使用错的算子也是同理，比如在选错成nested loop join时，使用Hint指定使用hash join来进行规避。
下载文档
复制链接