經常别人說EXISTS比IN快！NOT EXISTS比NOT IN快！然而事實真的如此麼？
我們先讨論IN和EXISTS。
select * from t1 where x in ( select y from t2 )
事實上可以了解為：
select *
from t1, ( select distinct y from t2 ) t2
where t1.x = t2.y;
——如果你有一定的SQL優化經驗，從這句很自然的可以想到t2絕對不能是個大表，因為需要對t2進行全表的“唯一排序”，如果t2很大這個排序的性能是不可忍受的。但是t1可以很大，為什麼呢？最通俗的了解就是因為t1.x=t2.y可以走索引。但這并不是一個很好的解釋。試想，如果t1.x和t2.y都有索引，我們知道索引是種有序的結構，是以t1和t2之間最佳的方案是走merge join。另外，如果t2.y上有索引，對t2的排序性能也有很大提高。
select * from t1 where exists ( select null from t2 where y = x )
可以了解為：
for x in ( select * from t1 )
loop
if ( exists ( select null from t2 where y = x.x )
then
OUTPUT THE RECORD!
end if
end loop
——這個更容易了解，t1永遠是個表掃描！是以t1絕對不能是個大表，而t2可以很大，因為y=x.x可以走t2.y的索引。
綜合以上對IN/EXISTS的讨論，我們可以得出一個基本通用的結論：IN适合于外表大而内表小的情況；EXISTS适合于外表小而内表大的情況。
如果你對上述說法表示懷疑，請看以下測試：
********************************************************************************
SQL> create table big as select * from all_objects;
表已建立。
SQL> insert into big select * from big;
已建立26872行。
SQL> commit;
送出完成。
SQL> insert into big select * from big;
已建立53744行。
SQL> commit;
送出完成。
SQL> insert into big select * from big;
已建立107488行。
SQL> commit;
送出完成。
SQL> create index big_idx on big(object_id);
索引已建立。
SQL> create table small as select * from all_objects where rownum < 100;
表已建立。
SQL> create index small_idx on small(object_id);
索引已建立。
********************************************************************************
運作SQL并設定EVENT=10046，用TKPROF格式化TRACE檔案，結果如下。
大表在外，小表在内的測試：
********************************************************************************
select count(subobject_name)
from big
where object_id in ( select object_id from small )
call count cpu elapsed disk query current rows
------- ------ -------- ---------- ---------- ---------- ---------- ----------
Parse 1 0.00 0.01 0 0 0 0
Execute 1 0.00 0.00 0 0 0 0
Fetch 2 0.00 0.14 29 900 0 1
------- ------ -------- ---------- ---------- ---------- ---------- ----------
total 4 0.00 0.15 29 900 0 1 Rows Execution Plan
------- ---------------------------------------------------
0 SELECT STATEMENT GOAL: CHOOSE
1 SORT (AGGREGATE)
792 TABLE ACCESS (BY INDEX ROWID) OF 'BIG'
892 NESTED LOOPS
99 VIEW OF 'VW_NSO_1'
99 SORT (UNIQUE)
99 TABLE ACCESS (FULL) OF 'SMALL'
792 INDEX (RANGE SCAN) OF 'BIG_IDX' (NON-UNIQUE) select count(subobject_name)
from big
where exists ( select null from small where small.object_id = big.object_id )
call count cpu elapsed disk query current rows
------- ------ -------- ---------- ---------- ---------- ---------- ----------
Parse 1 0.00 0.00 0 0 0 0
Execute 1 0.00 0.00 0 0 0 0
Fetch 2 1.90 2.72 2917 216125 0 1
------- ------ -------- ---------- ---------- ---------- ---------- ----------
total 4 1.90 2.72 2917 216125 0 1 Rows Execution Plan
------- ---------------------------------------------------
0 SELECT STATEMENT GOAL: CHOOSE
1 SORT (AGGREGATE)
792 FILTER
214976 TABLE ACCESS (FULL) OF 'BIG'
225 INDEX (RANGE SCAN) OF 'SMALL_IDX' (NON-UNIQUE)
********************************************************************************
用IN的性能資料：
cpu=0.00 elapsed=0.15 query=900 current=0 disk=29
用EXISTS的性能資料：
cpu=1.90 elapsed=2.72 query=216125 current=0 disk=2917
——在CPU的消耗和LIO、PIO上的對比十分明顯，IN的效率高得多！ 大表在内，小表在外的測試：
********************************************************************************
select count(subobject_name)
from small
where object_id in ( select object_id from big )
call count cpu elapsed disk query current rows
------- ------ -------- ---------- ---------- ---------- ---------- ----------
Parse 1 0.00 0.00 0 0 0 0
Execute 1 0.00 0.00 0 0 0 0
Fetch 2 0.41 1.71 2917 2982 0 1
------- ------ -------- ---------- ---------- ---------- ---------- ----------
total 4 0.41 1.72 2917 2982 0 1 Rows Execution Plan
------- ---------------------------------------------------
0 SELECT STATEMENT GOAL: CHOOSE
1 SORT (AGGREGATE)
99 TABLE ACCESS (BY INDEX ROWID) OF 'SMALL'
26972 NESTED LOOPS
26872 VIEW OF 'VW_NSO_1'
26872 SORT (UNIQUE)
214976 TABLE ACCESS (FULL) OF 'BIG'
99 INDEX (RANGE SCAN) OF 'SMALL_IDX' (NON-UNIQUE) select count(subobject_name)
from small
where exists ( select null from big where small.object_id = big.object_id )
call count cpu elapsed disk query current rows
------- ------ -------- ---------- ---------- ---------- ---------- ----------
Parse 1 0.00 0.00 0 0 0 0
Execute 1 0.00 0.00 0 0 0 0
Fetch 2 0.00 0.00 0 202 0 1
------- ------ -------- ---------- ---------- ---------- ---------- ----------
total 4 0.00 0.00 0 202 0 1 Rows Execution Plan
------- ---------------------------------------------------
0 SELECT STATEMENT GOAL: CHOOSE
1 SORT (AGGREGATE)
99 FILTER
99 TABLE ACCESS (FULL) OF 'SMALL'
99 INDEX (RANGE SCAN) OF 'BIG_IDX' (NON-UNIQUE)
********************************************************************************
用IN的性能資料：
cpu=0.41 elapsed=1.72 query=2982 current=26 disk=2917
用EXISTS的性能資料：
cpu=0.00 elapsed=0.00 query=202 current=0 disk=0
——在CPU的消耗和PIO、LIO上的對比十分明顯，EXISTS效率高得多！ 有些遺憾的是我這個測試是在RBO下進行的，RBO是個死闆的隻根據優先級來确定執行計劃的優化器，RBO不會評估實際的執行計劃對系統造成的影響。在RBO中NESTED LOOP的優先級要遠遠大于MERGE JOIN，隻要能走NESTED LOOP RBO就絕不會走MERGE JOIN。如果你用的是CBO，并且對表、索引做過統計分析，上面IN的測試一定會選擇走MERGE JOIN。我們用HINTS在RBO下強制走MERGE JOIN對比一下這個SQL分别走MJ和NL的性能：
********************************************************************************
select count(subobject_name)
from small
where object_id in ( select object_id from big )
call count cpu elapsed disk query current rows
------- ------ -------- ---------- ---------- ---------- ---------- ----------
Parse 1 0.01 0.17 0 0 0 0
Execute 1 0.00 0.00 0 0 0 0
Fetch 2 0.09 0.27 187 473 0 1
------- ------ -------- ---------- ---------- ---------- ---------- ----------
total 4 0.10 0.44 187 473 0 1 Rows Execution Plan
------- ---------------------------------------------------
0 SELECT STATEMENT GOAL: CHOOSE
1 SORT (AGGREGATE)
99 MERGE JOIN
26872 SORT (UNIQUE)
214976 INDEX (FULL SCAN) OF 'BIG_IDX' (NON-UNIQUE)
99 SORT (JOIN)
99 TABLE ACCESS (FULL) OF 'SMALL'
********************************************************************************
可以看到：
NESTED LOOP：cpu=0.41 elapsed=1.72 query=2982 current=26 disk=2917
MERGE JOIN：cpu=0.10 elapsed=0.44 query=437 current=2 disk=187
——這也證明了我上面的說法。很多人不敢讓自己的SQL走merge join，其實對于兩個已經具有排序結構的表merge join是最佳選擇。 下面我們讨論NOT IN和NOT EXISTS，我把它們放在一起讨論實屬被逼無奈，因為很多人喜歡拿它們比較。其實NOT IN/NOT EXISTS與IN/EXISTS不一樣，IN/EXISTS是完全可以作為等價替換結構的，而NOT IN/NOT EXISTS則不同，它們并不是等價替換結構！隻有當子查詢中不可能傳回空值時，NOT IN/NOT EXISTS才可以等價替換。
為什麼？請看：
********************************************************************************
SQL> conn scott/[email protected];
已連接配接。
SQL> select count(*)
2 from emp
3 where mgr is null;
COUNT(*)
----------------
1
SQL> select count(*)
2 from emp
3 where empno not in ( select mgr from emp );
COUNT(*)
----------------
SQL> select count(*)
2 from emp t1
3 where not exists ( select null
4 from emp t2
5 where t2.mgr = t1.empno );
COUNT(*)
----------------
7
********************************************************************************
如果子查詢中傳回的結果集含有空值NOT IN永遠是0，因為NULL代表“未知”，任何值和NULL比較永遠是false。
現在我們基于假設——子查詢中不傳回空值，來比較NOT IN和NOT EXISTS。
在RBO中如果不使用HINTS來改變NOT IN的執行計劃，幾乎任何時候NOT IN都比NOT EXISTS慢得多，在CBO中如果具有準确的統計資訊NOT IN的效率和NOT EXISTS的一樣，甚至會比NOT EXISTS快得多。
調整NOT IN性能的基本原則是：如果想讓NOT IN跑得快就必須走合适的連接配接。
select * from t1 where x not in ( select y from t2 )
以這個句子為例（y無空值）
這個句子可以等價替換為：
a) select * from t1 where not exists ( select null from t2 where t2.y=t1.x)
或
b) select t1.* from t1, t2 where t1.x=t2.y(+) and t2.y is null
測試如下：
********************************************************************************
SQL> create table t1 as select * from all_objects where rownum <= 5000;
表已建立。
SQL> create table t2 as select * from all_objects where rownum <= 4950;
表已建立。
SQL> create index t2_idx on t2(object_id);
索引已建立。
********************************************************************************
RBO下的測試：
********************************************************************************
select count(*)
from t1 rbo
where object_id not in ( select object_id from t2 )
call count cpu elapsed disk query current rows
------- ------ -------- ---------- ---------- ---------- ---------- ----------
Parse 1 0.00 0.00 0 0 0 0
Execute 1 0.00 0.00 0 0 0 0
Fetch 2 6.13 19.12 127487 197502 0 1
------- ------ -------- ---------- ---------- ---------- ---------- ----------
total 4 6.13 19.13 127487 197502 0 1 Rows Execution Plan
------- ---------------------------------------------------
0 SELECT STATEMENT GOAL: CHOOSE
1 SORT (AGGREGATE)
50 FILTER
5000 TABLE ACCESS (FULL) OF 'T1'
4950 TABLE ACCESS (FULL) OF 'T2' select count(*)
from t1 rbo
where not exists ( select null from t2 where t2.object_id = rbo.object_id)
call count cpu elapsed disk query current rows
------- ------ -------- ---------- ---------- ---------- ---------- ----------
Parse 1 0.01 0.00 0 0 0 0
Execute 1 0.00 0.00 0 0 0 0
Fetch 2 0.01 0.12 83 10075 0 1
------- ------ -------- ---------- ---------- ---------- ---------- ----------
total 4 0.02 0.12 83 10075 0 1 Rows Execution Plan
------- ---------------------------------------------------
0 SELECT STATEMENT GOAL: CHOOSE
1 SORT (AGGREGATE)
50 FILTER
5000 TABLE ACCESS (FULL) OF 'T1'
4950 INDEX (RANGE SCAN) OF 'T2_IDX' (NON-UNIQUE) select count(*)
from t1, t2 rbo
where t1.object_id = rbo.object_id(+) and rbo.object_id is null
call count cpu elapsed disk query current rows
------- ------ -------- ---------- ---------- ---------- ---------- ----------
Parse 1 0.00 0.00 0 0 0 0
Execute 1 0.00 0.00 0 0 0 0
Fetch 2 0.00 0.05 72 5087 0 1
------- ------ -------- ---------- ---------- ---------- ---------- ----------
total 4 0.00 0.06 72 5087 0 1 Rows Execution Plan
------- ---------------------------------------------------
0 SELECT STATEMENT GOAL: CHOOSE
1 SORT (AGGREGATE)
50 FILTER
5000 NESTED LOOPS (OUTER)
5000 TABLE ACCESS (FULL) OF 'T1'
4950 INDEX (RANGE SCAN) OF 'T2_IDX' (NON-UNIQUE)
********************************************************************************
RBO自己選擇的執行計劃，性能資料：
NOT IN：cpu=6.13 elapsed=19.13 query=197502 current=0 disk=127487
NOT EXISTS：cpu=0.02 elapsed=0.12 query=10075 current=0 disk=83
OUTER JOIN：cpu=0.00 elapsed=0.06 query=5087 current=0 disk=72
——NOT EXISTS的效率比NOT IN好很多，但與OUTER JOIN相比NOT EXISTS的效率略低。 RBO，用HINTS改變NOT IN的執行計劃：
********************************************************************************
select count(*)
from t1 rbo
where object_id not in ( select object_id from t2 )
call count cpu elapsed disk query current rows
------- ------ -------- ---------- ---------- ---------- ---------- ----------
Parse 1 0.04 0.45 0 3 0 0
Execute 1 0.00 0.00 0 0 0 0
Fetch 2 0.01 0.09 48 191 0 1
------- ------ -------- ---------- ---------- ---------- ---------- ----------
total 4 0.05 0.55 48 194 0 1 Rows Execution Plan
------- ---------------------------------------------------
0 SELECT STATEMENT GOAL: CHOOSE
0 SORT (AGGREGATE)
0 HASH JOIN (ANTI)
0 TABLE ACCESS (FULL) OF 'T1'
0 INDEX (FAST FULL SCAN) OF 'T2_IDX' (NON-UNIQUE)
********************************************************************************
在隻有t2.object_id有索引的情況下，hash join-anti性能資料如下：
HJ-ANTI：cpu=0.05 elapsed=0.55 query=194 current=0 disk=48
——性能好了很多！ 在t1.object_id上建立索引，使用merge join-anti：
********************************************************************************
select count(*)
from t1 rbo
where object_id not in ( select object_id from t2 )
call count cpu elapsed disk query current rows
------- ------ -------- ---------- ---------- ---------- ---------- ----------
Parse 1 0.00 0.00 0 0 0 0
Execute 1 0.00 0.00 0 0 0 0
Fetch 2 0.00 0.00 0 28 0 1
------- ------ -------- ---------- ---------- ---------- ---------- ----------
total 4 0.00 0.00 0 28 0 1 Rows Execution Plan
------- ---------------------------------------------------
0 SELECT STATEMENT GOAL: CHOOSE
1 SORT (AGGREGATE)
50 MERGE JOIN (ANTI)
5000 INDEX (FULL SCAN) OF 'T1_IDX' (NON-UNIQUE)
4950 SORT (UNIQUE)
4950 INDEX (FAST FULL SCAN) OF 'T2_IDX' (NON-UNIQUE)
********************************************************************************
在t1.object_id上建立索引，merge join-anti的性能資料如下：
MJ-ANTI：cpu=0.00 elapsed=0.00 query=28 current=0 disk=0
——這個NOT IN語句在t1.object_id、t2.object_id都有索引的情況下，merge join-anti的效率高于上面的任何SQL。 綜上，隻要NOT IN走合适的連接配接，其效率很高甚至高于NOT EXISTS和OUTER JOIN。
![查找算法之二分查找查找算法之二分查找[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)