http://www.cnblogs.com/killkill/archive/2011/04/11/2013044.html
原文地址：http://www.itpub.net/thread-1376537-1-2.html
“相关值”是我剽窃的一个词，与之相反的是“不相关值”，我借用来描述以下这种情况：在SQL中有两个表A和B要join，join条件是A.name=B.first_name，判定符“=”左右两边的值是“不相关”的，而substr(A.name,1,length(B.first_name))=B.first_name，判定符“=”左右两边的值是“相关”的，因为要通过“=”右边的值才能求出左边的值（相反亦然）。
由于这种“相关值”的情况，A、B表join的算法注定只能走Nested Loop了，因为每一个不同的驱动值（驱动表中的值，也就是B表中的值）将改变A表负责join的值，执行计划如下：
| 1 |
select a.*,b.object_name from TEST_OBJECT a, TEST_OBJ1 b |
| 2 |
where substr(a.object_name,1,length(b.object_name))=b.object_name; |
| 05 |
--------------------------------------------------------------------- |
| 06 |
| Id | Operation | Name | Rows | Bytes | Cost | |
| 07 |
--------------------------------------------------------------------- |
| 08 |
| 0 | SELECT STATEMENT | | | | | |
| 09 |
| 1 | NESTED LOOPS | | | | | |
| 10 |
| 2 | TABLE ACCESS FULL | TEST_OBJ1 | | | | |
| 11 |
|* 3 | TABLE ACCESS FULL | TEST_OBJECT | | | | |
| 12 |
--------------------------------------------------------------------- |
| 14 |
Predicate Information (identified by operation id): |
| 15 |
--------------------------------------------------- |
| 17 |
3 - filter("B"."OBJECT_NAME"=SUBSTR("A"."OBJECT_NAME",1,LENGTH("B"."OBJ |
| 21 |
---------------------------------------------------------- |
| 24 |
9262734 consistent gets |
这里展开一下，Nested Loop这个算法复杂度是 O(B*A) （B表示驱动表的记录数，A表示内部表），如果A、B都很大，那就杯具了，关于Nested Loop驱动表的选取就不展开了。
网友anlinew提供了一种非常精妙的，决的优化方法，将语句改写成：
| 1 |
select a.*,b.object_name from TEST_OBJECT a, TEST_OBJ1 b |
| 2 |
where substr(a.object_name,1,length(b.object_name))=b.object_name |
| 3 |
and substr(a.object_name,1,4)=substr(b.object_name,1,4) |
| 4 |
and length(b.object_name)>3 |
| 6 |
select a.*,b.object_name from TEST_OBJECT a, TEST_OBJ1 b |
| 7 |
where substr(a.object_name,1,length(b.object_name))=b.object_name |
| 8 |
and length(b.object_name)<4; |
| 05 |
----------------------------------------------------------------------------------- |
| 06 |
| Id | Operation | Name | Rows | Bytes | Cost (%CPU)| Time | |
| 07 |
----------------------------------------------------------------------------------- |
| 08 |
| 0 | SELECT STATEMENT | | 3468 | 365K| 90997 (100)| 00:18:12 | |
| 09 |
| 1 | UNION-ALL | | | | | | |
| 10 |
|* 2 | HASH JOIN | | 34 | 3672 | 176 (2)| 00:00:03 | |
| 11 |
|* 3 | TABLE ACCESS FULL| TEST_OBJ1 | 659 | 12521 | 35 (0)| 00:00:01 | |
| 12 |
| 4 | TABLE ACCESS FULL| TEST_OBJECT | 52544 | 4566K| 139 (1)| 00:00:02 | |
| 13 |
| 5 | NESTED LOOPS | | 3434 | 362K| 90821 (1)| 00:18:10 | |
| 14 |
|* 6 | TABLE ACCESS FULL| TEST_OBJ1 | 659 | 12521 | 35 (0)| 00:00:01 | |
| 15 |
|* 7 | TABLE ACCESS FULL| TEST_OBJECT | 5 | 445 | 138 (1)| 00:00:02 | |
| 16 |
----------------------------------------------------------------------------------- |
| 18 |
Predicate Information (identified by operation id): |
| 19 |
--------------------------------------------------- |
| 21 |
2 - access(SUBSTR("A"."OBJECT_NAME",1,4)=SUBSTR("B"."OBJECT_NAME",1,4)) |
| 22 |
filter("B"."OBJECT_NAME"=SUBSTR("A"."OBJECT_NAME",1,LENGTH("B"."OBJE |
| 24 |
3 - filter(LENGTH("B"."OBJECT_NAME")>3) |
| 25 |
6 - filter(LENGTH("B"."OBJECT_NAME")<4) |
| 26 |
7 - filter("B"."OBJECT_NAME"=SUBSTR("A"."OBJECT_NAME",1,LENGTH("B"."OBJE |
| 30 |
---------------------------------------------------------- |
执行计划虽然变复杂了，但是耗时大幅减少，consistent gets也大幅降低，作出巨大贡献的是Hash Join的引入。
这里再展开一下，Hash Join的复杂度是O(A+B)，简单来说就是对A、B表各扫描一次，如果A、B都比较大的情况来看，无疑Hash Join要比Nested Loop 优越很多。
扯远了，回到anlinew的具体方法上吧，导致Hash Join出现的关键因素是一个谓词的引入：
| 1 |
and substr(a.object_name,1,4)=substr(b.object_name,1,4) |
套用我剽窃的那个词来说，这是“不相关值”的对比！
anlinew的核心思想是将数据“分片”，该例子中分片的依据是多少位首字母（这里是4），其中“大头”由Hash Join处理，而“小头”走Nested Loop，这种“抓大放小”的做法直接就从复杂度上进行了优化。
这种“分片”的思想非常值得借鉴，将“相关值”判断转化成“不相关值”的判断也是处理问题的一种有效手法。
来自 “ ITPUB博客 ” ，链接：https://blog.itpub.net/8102208/viewspace-693309/
，如需转载，请注明出处，否则将追究法律责任。
