对IN & EXISTS NOT IN & NOT EXISTS的优化

转自http://yaanzy.itpub.net/post/1263/10217
在平时工作中,IN & EXISTS NOT IN & NOT EXISTS是使用频率比较高的SQL语句,
所以对它们的优化工作是很有必要的

测试环境：Oracle 9.2.0.1 for Windows2000



1、IN 和 EXISTS

IN和EXISTS的处理流程是不一样的：

IN的执行流程
select * from T1 where x in ( select y from T2 )
可以理解为:
select * from t1, ( select distinct y from t2 ) t2 where t1.x = t2.y;

EXISTS的执行流程
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

创建测试用例表big(4000 row)和small(400 row)

create table big as select * from dba_objects where rownum <= 10000;
insert into big select * from big;
insert into big select * from big;
commit;
create table small as select * from dba_objects where rownum <= 400;

当内层表为small,外层表为big时,两种语法的查询如下：

SQL> select count(1) from big a where a.object_id in
(select b.object_id from sall b);

COUNT(1)
----------
1600

已用时间: 00: 00: 00.56

Execution Plan
-----------------------------------------------------
0 SELECT STATEMENT Optimizer=CHOOSE
1 0 SORT (AGGREGATE)
2 1 MERGE JOIN
3 2 SORT (JOIN)
4 3 TABLE ACCESS (FULL) OF 'BIG'
5 2 SORT (JOIN)
6 5 VIEW OF 'VW_NSO_1'
7 6 SORT (UNIQUE)
8 7 TABLE ACCESS (FULL) OF 'SMALL'

Statistics
-----------------------------------------------------
0 recursive calls
0 db block gets
543 consistent gets
0 physical reads

SQL> select count(1) from big a where exists
(select 1 from small b where a.object_id=b.object_id);

COUNT(1)
----------
1600

已用时间: 00: 00: 03.10

Execution Plan
-----------------------------------------------------
0 SELECT STATEMENT Optimizer=CHOOSE
1 0 SORT (AGGREGATE)
2 1 FILTER
3 2 TABLE ACCESS (FULL) OF 'BIG'
4 2 TABLE ACCESS (FULL) OF 'SMALL'

Statistics
-----------------------------------------------------
0 recursive calls
0 db block gets
312157 consistent gets
0 physical reads

当内层表为big,外层表为small时,两种语法的查询如下：

SQL> select count(1) from small a where a.object_id in
(select b.object_id from big b);

COUNT(1)
----------
400

已用时间: 00: 00: 00.56

Execution Plan
-----------------------------------------------------
0 SELECT STATEMENT Optimizer=CHOOSE
1 0 SORT (AGGREGATE)
2 1 MERGE JOIN
3 2 SORT (JOIN)
4 3 TABLE ACCESS (FULL) OF 'SMALL'
5 2 SORT (JOIN)
6 5 VIEW OF 'VW_NSO_1'
7 6 SORT (UNIQUE)
8 7 TABLE ACCESS (FULL) OF 'BIG'

Statistics
-----------------------------------------------------
0 recursive calls
0 db block gets
543 consistent gets
0 physical reads

SQL> select count(1) from small a where exists
(select null from big b where a.bject_id=b.object_id);

COUNT(1)
----------
400

已用时间: 00: 00: 00.25

Execution Plan
-----------------------------------------------------
0 SELECT STATEMENT Optimizer=CHOOSE
1 0 SORT (AGGREGATE)
2 1 FILTER
3 2 TABLE ACCESS (FULL) OF 'SMALL'
4 2 TABLE ACCESS (FULL) OF 'BIG'

Statistics
-----------------------------------------------------
0 recursive calls
0 db block gets
2562 consistent gets
0 physical reads


在对表big、small进行分析后,发现CBO下两种语法的执行计划是一样的,都使用hash连接或者hash半连接

SQL> analyze table big compute statistics;
SQL> analyze table small compute statistics;

SQL> select count(1) from big a where a.object_id in
(select b.object_id from small b);

COUNT(1)
----------
1600

已用时间: 00: 00: 00.09

Execution Plan
-------------------------------------------------------
0 SELECT STATEMENT Optimizer=CHOOSE (Cost=58
Card=1 Bytes=8)
1 0 SORT (AGGREGATE)
2 1 HASH JOIN (Cost=58 Card=1600 Bytes=12800)
3 2 SORT (UNIQUE)
4 3 TABLE ACCESS (FULL) OF 'SMALL' (Cost=2 Card=400 Bytes=1600)
5 2 TABLE ACCESS (FULL) OF 'BIG' (Cost=53 Card=40000 Bytes=160000)

Statistics
-------------------------------------------------------
0 recursive calls
0 db block gets
543 consistent gets
0 physical reads

SQL> select count(1) from big a where exists
(select 1 from small b where a.object_id=b.object_id);

COUNT(1)
----------
1600

已用时间: 00: 00: 00.09

Execution Plan
----------------------------------------------------------
0 SELECT STATEMENT Optimizer=CHOOSE (Cost=58 Card=1 Bytes=8)
1 0 SORT (AGGREGATE)
2 1 HASH JOIN (Cost=58 Card=1600 Bytes=12800)
3 2 SORT (UNIQUE)
4 3 TABLE ACCESS (FULL) OF 'SMALL' (Cost=2 Card=400 Bytes=1600)
5 2 TABLE ACCESS (FULL) OF 'BIG' (Cost=53 Card=40000 Bytes=160000)

Statistics
--------------------------------------------------------
0 recursive calls
0 db block gets
543 consistent gets
0 physical reads


SQL> select count(1) from small a where a.object_id in
(select b.object_id from big b);

COUNT(1)
----------
400

已用时间: 00: 00: 00.09

Execution Plan
------------------------------------------------------
0 SELECT STATEMENT Optimizer=CHOOSE (Cost=56 Card=1 Bytes=8)
1 0 SORT (AGGREGATE)
2 1 HASH JOIN (SEMI) (Cost=56 Card=400 Bytes=3200)
3 2 TABLE ACCESS (FULL) OF 'SMALL' (Cost=2 Card=400 Bytes=1600)
4 2 TABLE ACCESS (FULL) OF 'BIG' (Cost=53 Card=40000 Bytes=160000)

Statistics
------------------------------------------------------
0 recursive calls
0 db block gets
543 consistent gets
0 physical reads

SQL> select count(1) from small a where exists
(select 1 from big b where a.object_id=b.object_id);

COUNT(1)
----------
400

已用时间: 00: 00: 00.09

Execution Plan
-------------------------------------------------------
0 SELECT STATEMENT Optimizer=CHOOSE (Cost=56 Card=1 Bytes=8)
1 0 SORT (AGGREGATE)
2 1 HASH JOIN (SEMI) (Cost=56 Card=400 Bytes=3200)
3 2 TABLE ACCESS (FULL) OF 'SMALL' (Cost=2 Card=400 Bytes=1600)
4 2 TABLE ACCESS (FULL) OF 'BIG' (Cost=53 Card=40000 Bytes=160000)

Statistics
-------------------------------------------------------
0 recursive calls
0 db block gets
543 consistent gets
0 physical reads

删除表分析,使用提示/*+ use_hash(a,b) */ 或者 /*+ hash_sj */,
两种语法都可以达到CBO的执行计划

SQL> analyze table big delete statistics;
SQL> analyze table small delete statistics;

SQL> select /*+ use_hash(a,b) */count(1) from big a where a.object_id in
(select b.object_id from small b);

SQL> select /*+ use_hash(a,b) */count(1) from big a where exists
(select 1 from small b where a.object_id=b.object_id);

SQL> select count(1) from small a where a.object_id in
(select /*+ hash_sj */ b.object_id from big b);

SQL> select count(1) from small a where exists
(select /*+ hash_sj */ 1 from big b where a.object_id=b.object_id);

下表列出了各种情况下的速度情况：
┌───────────┬──────────────────────────┬─────────────────────────┬─────────────┐
│ │ outer big,inner small │ outer small,inner big │ table rows │
├───────────┼──────────┬───────────────┼──────────┬──────────────┼─────────────┤
│ │ IN SQL │ EXISTS SQL │ IN SQL │ EXISTS SQL │ │
├───────────┼──────────┼───────────────┼──────────┼──────────────┼─────────────┤
│un-analyze │ 0.56s │ 3.10s │ 0.56s │ 0.25s │ big=40000 │
├───────────┼──────────┼───────────────┼──────────┼──────────────┤ and │
│ analyzed │ 0.09s │ 0.09s │ 0.09s │ 0.09s │ small=400 │
├───────────┼──────────┼───────────────┼──────────┼──────────────┼─────────────┤
│un-analyze │ 0.72s │ 3.53s │ 0.25s │ 2.97s │ big=5000 │
├───────────┼──────────┼───────────────┼──────────┼──────────────┤ and │
│ analyzed │ 0.09s │ 0.09s │ 0.09s │ 0.09s │ small=4000 │
└───────────┴──────────┴───────────────┴──────────┴──────────────┴─────────────┘

结论：在未对表进行分析前,若两个表数据量差异很大,则外层表是大表时使用IN较快,
外层表是小表时使用EXISTS较快;若两表数据量接近,则使用IN较快;
分析表后无论用IN还是EXISTS都变得更快,由于执行计划一样,所以速度一样;

所以：无论使用IN还是EXISTS,只要使用散列连接,即提示/*+ use_hash(a,b) */,
或者在子句中散列半连接提示/*+ hash_sj */, 就使其达到最优速度;

附注：半连接的提示有hash_sj、merge_sj、nl_sj


***********************************************************************************************************************
***********************************************************************************************************************


2、NOT IN 和 NOT EXISTS

NOT EXISTS的执行流程
select .....
from rollup R
where not exists ( select 'Found' from title T
where R.source_id = T.Title_ID);
可以理解为:
for x in ( select * from rollup )
loop
if ( not exists ( that query ) ) then
OUTPUT
end if;
end;

注意:NOT EXISTS 与 NOT IN 不能完全互相替换，看具体的需求。如果选择的列可以为空，则不能被替换。

对于not in 和 not exists的性能区别：
not in 只有当子查询中，select 关键字后的字段有not null约束或者有这种暗示时用not in,另外如果主查询中表大，
子查询中的表小但是记录多，则应当使用not in,并使用anti hash join.

如果主查询表中记录少，子查询表中记录多，并有索引，可以使用not exists，另外not in最好也可以用/*+ HASH_AJ */
或者外连接+is null，NOT IN 在基于成本的应用中较好

创建测试用例表big(40000 row)和small(1000 row)：

truncate table big;
truncate table small;
insert into big select * from dba_objects where rownum <=20000;
insert into big select * from dba_objects where rownum <=20000;
insert into small select * from dba_objects where rownum <=1000;
commit;

基本句型：
<1> not in
SQL> select count(1) from big a where a.object_id not in (select b.object_id from small b);

COUNT(1)
----------
38000

已用时间: 00: 00: 12.56

Execution Plan
-----------------------------------------------------
0 SELECT STATEMENT Optimizer=CHOOSE
1 0 SORT (AGGREGATE)
2 1 FILTER
3 2 TABLE ACCESS (FULL) OF 'BIG'
4 2 TABLE ACCESS (FULL) OF 'SMALL'


Statistics

评论

2 楼 aop 2009-03-03  

zl584521 写道

我对于程序已经失去了兴趣.....

为啥捏？

1 楼 zl584521 2008-03-06  

我对于程序已经失去了兴趣.....