`

不要再纠结in和exists——JAVA伪代码直白分析二者时间复杂度

 
阅读更多

引子

in和exists的讨论从未间断过。之前有“今年是龙年大哥”的有数据有真相的测试博文，现在有程序员老鸟写sql语句的经验之谈上的疯狂讨论。关于exists和in，就是很少人站出来，直白地分析二者本质上的差别，这方面的文章大都是用晦涩的文字表述，或者直接给结论——什么情况下用exists，什么情况下用in，而不给出原理。结果时至今日，还有许多人认为exists一定比in性能高。下面鄙人用JAVA的伪代码，从理论上分析exists和in的时间复杂度。

 

 

学生信息表(student_id 学生id, name 学生名称)

student(student_id,name) 

 

学生总分表

score(student_id,total)

 

现在查询出总分(total)超过90分的学生信息。

 

一、粗略的时间复杂度估算

 

1 exists方式

select * from student a where exists (select 1 from score b where b.total>90 and b.student_id = a.student_id);

 

List<Map<String,String>> studentList = select * from student ;
for(i=0;i<studentList.size();i++){
	String _student_id = studentList.get(i).get("student_id");
	if(exists("select 1 from score  where total>90 and student_id = " + _student_id )){//建立有索引，这执行很快,O(1)时间
		studentRow = studentList.get(i)
		println(studentList.get(i));
	}
}
 

 

时间复杂度为studentList.size() * 1

 

2 in方式

select * from student where student_id in (select student_id from score where total>90);

 

List<Map<String,String>> scoreList = select student_id from score where total>90;
for(i=0;i<scoreList.size();i++){
	String _student_id = scoreList.get(i).get("student_id ");
	String studentRow = select * from student where studentId=_student_id;//建立有索引，这执行很快O(1)时间
	if(null != studentRow {
		println(studentRow);
	}
}
 

 

时间复杂度为scoreList.size() * 1

 

根据时间复杂度，

exists的耗费的时间，与主表student的记录数成正比，student 表越大，exists耗费时间越长;

in耗费的时间，与子查询的记录数成正比，记录数越多，in耗费时间越长。

 

也就是说，理论上，注意是理论上，

如果子查询的结果集很大，即是scoreList.size()很大，可能就不适合用in。

如果主查询的表记录数很大，即使studentList.size()很大，而子查询的结果很小，可能就不适合用exists。

对比子查询结果集的大小scoreList.size()和主表student表的大小studentList.size()，相信大家能比较简单地对in和exists做出初步选择。

 

二、 细致的时间复杂度估算

上面的伪代码是粗略的估算。这里说细致一些。

 

1. 上面的两段伪代码中O(1)时间的部分，因为实际情况中未必使用到索引，所以未必为O(1)。

 

2. exists伪代码的第一句List<Map<String,String>> studentList = select * from student ;必然是全表扫描，算上这一句的，exists伪代码的时间复杂度就是，

studentList.size() * 1+studentTable.size() = 2*studentTable.size().

 

in伪代码的第一句，List<Map<String,String>> scoreList = select student_id from score where score>90;实际情况中，子查询未必是全表扫描。

如果是子查询是全表扫描，那么in的时间复杂度为

scoreList.size() * 1+scoreTable.size() 

如果使用到索引，不是全表扫描，那么in的时间复杂度为

scoreList.size() *1 +  scoreList.size() = 2*scoreList.size()

 

3. 综合1,2

exists:

studentTable.size() * Time(一条exists语句的执行时间)+studentTable.size()*Time(顺序扫描出一条记录的时间)

注释:studentTable就是主表。

 

in(子查询索引扫描):

scoreList.size() *Time(一条select语句的执行时间) +  scoreList.size()*Time(索引扫描出一条记录的时间)

注释: scoreList就是子查询的结果集。一条select 语句就是主表做in判断的select语句

 

       select * from student where studentId=_student_id


in(子查询全表扫描):

scoreList.size() *Time(一条select语句的执行时间) +  scoreTable.size()*Time(顺序扫描出一条记录的时间)

 

4 简化

 

现在简化对比in 和 exists的时间复杂度，二者的表达式有乘法和加法，我们只保留乘法。

Time_Exists = 主表记录数 * Time(一条exists语句的执行时间)

Time_IN = 子查询结果集记录数 *Time(一条select语句的执行时间) 

 

数据量大，在决定该使用exsits和in的时候，我们只需要根据主表记录数和子查询结果集记录数就可做出初步选择。主表记录数多，我们就该有限不考虑用exists;子查询结果集记录数多，我们就该优先不考虑用in。如果子查询结果多，主表记录数多，用哪个呢？那就看实际数据了，要测试具体的时间。

 

 

5 结论

显然，细致分析之后，我们不能很快就下结论孰快孰慢了，索引的情况增加了分析的步骤。特别地，如果in伪代码中每条语句都用到了索引，子查询结果集合很小，另一方面主查询表很大，那么我们可以马上确定用in了。觉得exists一定比in快的同学，现在需要思考下了。

 

三、结论

实际上，一切还是看具体的存储过程以及看测试结果。理论和实际总会有差距，数据量，索引，硬件，ORACLE版本等等都会对结果产生影响。我们要具体问题具体分析。首先，我们可以套用上面两段伪代码去做估算，某些情况下还是可以估算得出来的孰快孰慢。其次，如果数据量大的话，就必须看执行计划，进一步，如果可以的话，就直接执行sql语句查看耗费时间。有时候执行计划还真的对EXISTS，IN有区别对待，这时候估算的思想就要用上。

 

我建议大家不要去纠结in、exists究竟用谁好。数据量不大，in、exists根本无区别，数据量大的时候，你说能不去看看执行计划吗？

 

值得注意的是，据说oracle11g在CBO的情况下，ORACLE会根据数据，对IN,EXISTS做出最佳的选择，而不管你写SQL是IN或者EXISTS。细心想想这也是合理的，IN,EXISTS所表达出的要做的事情是一样的，数据库为什么要区分对待呢？性能的问题交给数据库自己判断好了，不要麻烦开发人员。这也是我建议大家不要纠结in和exists区别的一个原因。

 

四、后记

1. on 2012-10-15 09:00

 

后面我看到了一篇文章，同样比较简单易明，对in和exists的对比和我一致，但是我必须承认，老外的描述得比我更好一些(不知道是不是英语更适合表达技术的原因，呵呵)，所以摘录下来，与大家共享 ：）

from: 

http://asktom.oracle.com/pls/asktom/f?p=100:11:0::::P11_QUESTION_ID:953229842074

 

can you give me some example at which situation IN is better than exist, and vice versa. 
You Asked

Tom:

can you give me some example at which situation
IN is better than exist, and vice versa.

and we said...

Well, the two are processed very very differently.

Select * from T1 where x in ( select y from T2 )

is typically processed as:

select *
from t1, ( select distinct y from t2 ) t2
where t1.x = t2.y;

The subquery is evaluated, distinct'ed, indexed (or hashed or sorted) and then joined to
the original table -- typically.


As opposed to

select * from t1 where exists ( select null from t2 where y = x )

That is processed more like:


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

It always results in a full scan of T1 whereas the first query can make use of an index
on T1(x).


So, when is where exists appropriate and in appropriate?

Lets say the result of the subquery
( select y from T2 )

is "huge" and takes a long time. But the table T1 is relatively small and executing (
select null from t2 where y = x.x ) is very very fast (nice index on t2(y)). Then the
exists will be faster as the time to full scan T1 and do the index probe into T2 could be
less then the time to simply full scan T2 to build the subquery we need to distinct on.


Lets say the result of the subquery is small -- then IN is typicaly more appropriate.


If both the subquery and the outer table are huge -- either might work as well as the
other -- depends on the indexes and other factors.

  2. on 2012-10-15 09:22

     from ITPUB

  http://www.itpub.net/thread-936584-1-1.html

     一个比较厉害的人写的帖子，里面就提供了in比exists快的一个例子。

     他说：

 

in适合内外表都很大的情况，exists适合外表结果集很小的情况。
exists 和 in 使用一例
 

    其实意思是内外表都很大，连接后比较小，in会快一些。

 

 

 

EXISTS、IN对比 写道

EXISTS、IN、NOT EXISTS、NOT IN的区别：


in适合内外表都很大的情况，exists适合外表结果集很小的情况。
exists 和 in 使用一例
===========================================================
今天市场报告有个sql及慢，运行需要20多分钟，如下：
update p_container_decl cd
set cd.ANNUL_FLAG='0001',ANNUL_DATE = sysdate
where exists(
select 1
from (
select tc.decl_no,tc.goods_no
from p_transfer_cont tc,P_AFFIRM_DO ad
where tc.GOODS_DECL_NO = ad.DECL_NO
and ad.DECL_NO = 'sssssssssssssssss'
) a
where a.decl_no = cd.decl_no
and a.goods_no = cd.goods_no
)
上面涉及的3个表的记录数都不小，均在百万左右。根据这种情况，我想到了前不久看的tom的一篇文章，说的是exists和in的区别，
in 是把外表和那表作hash join，而exists是对外表作loop，每次loop再对那表进行查询。
这样的话，in适合内外表都很大的情况，exists适合外表结果集很小的情况。

而我目前的情况适合用in来作查询，于是我改写了sql，如下：
update p_container_decl cd
set cd.ANNUL_FLAG='0001',ANNUL_DATE = sysdate
where (decl_no,goods_no) in
(
select tc.decl_no,tc.goods_no
from p_transfer_cont tc,P_AFFIRM_DO ad
where tc.GOODS_DECL_NO = ad.DECL_NO
and ad.DECL_NO = ‘ssssssssssss’
)

让市场人员测试，结果运行时间在1分钟内。问题解决了，看来exists和in确实是要根据表的数据量来决定使用。
 

 

 

9
顶
8
踩
分享到：
| 1%的灵感最重要 & 改进沟通
评论
16 楼 lazy_ 2012-10-15  
leonayx123 写道
我一直都按以前有人给我说的。 子查询小表的话用in
子查询是大表用exists。

但是不知道这个大表 小表指的数量级到底是多少。几百？几千？几万？几百万？


在in、exists取舍的目标前提下

Time_Exists = 主表记录数 * Time(一条exists语句的执行时间)
Time_IN =  子查询记录数*Time(一条select语句的执行时间) 。

如果 子查询记录数 是几万条 ，而 主表记录数 是几百万条， 那么子查询记录数就是“小表”了。相对的。



15 楼 lazy_ 2012-10-15  
leonayx123 写道
引用
看看水墨江南的这篇分析。 从执行计划的角度做的分析，很明确。
相比下，你用时间复杂度来分析，我看着有点绕。。。

http://zhuyuehua.iteye.com/blog/898917



太棒了！谢谢你的指点！他写得太好了！

其实复杂度是其次，我最想表达的是那个伪代码和
Time_Exists = 主表记录数 * Time(一条exists语句的执行时间)
Time_IN =  子查询记录数*Time(一条select语句的执行时间) 。

不看细致分析的话，其实还是没有那么绕的。。。有时候想表达得精确一些，看起来就饶了。。。或许是我表达功力不够，嗯，以后写博文继续改进吧。。。
14 楼 leonayx123 2012-10-15  
我一直都按以前有人给我说的。 子查询小表的话用in
子查询是大表用exists。

但是不知道这个大表 小表指的数量级到底是多少。几百？几千？几万？几百万？
13 楼 leonayx123 2012-10-15  
看看水墨江南的这篇分析。 从执行计划的角度做的分析，很明确。
相比下，你用时间复杂度来分析，我看着有点绕。。。

http://zhuyuehua.iteye.com/blog/898917
12 楼 sgq0085 2012-10-15  
签个名晚上回去看
11 楼 hyneng 2012-10-14  
留个脚印..
10 楼 宇宙浪子 2012-10-14  
楼主高端啊
9 楼 paladin1988 2012-10-14  
mark之。。。
8 楼 巴巴米 2012-10-14  
先留个名，明天再看。。。
6 楼 宁辉522 2012-10-14  
http://ninghui521.iteye.com/blog/1697933
5 楼 jinnianshilongnian 2012-10-13  
vision2000 写道
专家请分析一下这俩SQL的执行效率（T_PER_ARCHIVES 主键：ARCHIVES_ID，T_SYS_DEPT 主键：DEPTID）：
（一）、
select *
  from (select T1.ARCHIVES_ID, T2.Deptcode
          from T_PER_ARCHIVES T1, T_SYS_DEPT T2
         WHERE T1.DEPTID = T2.DEPTID)
where rownum <= 20;


（二）、
select *
  from (select T1.ARCHIVES_ID,
               (SELECT Deptcode FROM T_SYS_DEPT N WHERE N.Deptid = T1.DEPTID) Deptcode
          from T_PER_ARCHIVES T1)
where rownum <= 20;


第二个效率更高 因为rownum<=20 因此oracle会使用COUNT STOPKEY优化，不知对否 
4 楼 vision2000 2012-10-13  
专家请分析一下这俩SQL的执行效率（T_PER_ARCHIVES 主键：ARCHIVES_ID，T_SYS_DEPT 主键：DEPTID）：
（一）、
select *
  from (select T1.ARCHIVES_ID, T2.Deptcode
          from T_PER_ARCHIVES T1, T_SYS_DEPT T2
         WHERE T1.DEPTID = T2.DEPTID)
where rownum <= 20;


（二）、
select *
  from (select T1.ARCHIVES_ID,
               (SELECT Deptcode FROM T_SYS_DEPT N WHERE N.Deptid = T1.DEPTID) Deptcode
          from T_PER_ARCHIVES T1)
where rownum <= 20;
3 楼 jinnianshilongnian 2012-10-13  
lazy_ 写道
jinnianshilongnian 写道
呵呵，具体还是要看执行计划， 用in/exists 可能产生的执行计划都是一样的 

龙年大哥起得真早！

早起看书 
2 楼 lazy_ 2012-10-13  
jinnianshilongnian 写道
呵呵，具体还是要看执行计划， 用in/exists 可能产生的执行计划都是一样的 

龙年大哥起得真早！
1 楼 jinnianshilongnian 2012-10-13  
呵呵，具体还是要看执行计划， 用in/exists 可能产生的执行计划都是一样的 
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

    in和exists的区别

    在Oracle数据库中，"IN"和"EXISTS"都是用于查询某个集合的元素是否存在于另一个集合中的关键字。然而，它们在处理数据时的效率和适用场景有所不同，这主要取决于涉及的数据量以及表之间的关联。 首先，让我们来看看...

    SQL语句优化——in,not in,exists,not exists, left join...on博客所需SQL语句.txt

    SQL语句优化——in,not in,exists,not exists, left join...on博客所需SQL语句.txt欢迎下载！

    PostgreSQL IN vs EXISTS vs ANYALL vs JOIN性能分析

    PostgreSQL作为一种强大的开源关系数据库系统，它支持多种SQL操作，其中包括IN、EXISTS...通过这样的深入分析和实际测试，开发人员可以更加高效和智能地利用PostgreSQL数据库的多种查询操作符，以支持复杂的业务需求。

    in和exists性能解析

    在数据库查询语言中，`IN` 和 `EXISTS` 子句是两种常见的用于关联两个表的方法，它们各自有其独特的性能特点和适用场景。本文将深入解析Oracle中`IN`与`EXISTS`的性能差异，以及如何根据具体需求选择最合适的查询...

    sql in,exists,not in,not exists区别

    SQL 中 IN、EXISTS、NOT IN、NOT EXISTS 的区别 IN、EXISTS、NOT IN、NOT EXISTS 是 SQL 中四种常用的条件判断运算符，它们之间的区别主要体现在使用场景、执行效率和语法结构上。 IN IN 是一种条件判断运算符，...

    in和exists的区别与执行效率问题解析

    标题和描述均聚焦于SQL查询语句中"IN"与"EXISTS"的区别及执行效率问题，这是一个在数据库操作中非常关键的话题，尤其对于优化查询性能有着不可忽视的作用。下面，我们将深入探讨这两种语句的不同之处及其对执行效率...

    SQL语句优化——in,not in,exists,not exists, left join...on博客所需SQL语句2.txt

    SQL语句优化——in,not in,exists,not exists, left join...on博客所需SQL语句2.txt，欢迎下载！

    简单的Windows资源管理器——Java版本

    1. **读取文件**：使用`File`类的`exists()`方法检查文件是否存在，`isDirectory()`判断是否为目录，`listFiles()`用于获取目录中的所有文件和子目录。`length()`方法返回文件大小，`getName()`获取文件名。 2. **...

    java在线查看PDF（csdn）————程序.pdf

    Java 在线查看 PDF 的实现 Java 在线查看 PDF 是一个常见的需求，特别是在项目中需要在线预览 PDF 文件时。在这个示例代码中，我们将看到如何使用 Java 实现在线查看 PDF 的功能。 标题解释: "java 在线查看PDF...

    oracle中exists_和in的效率问题详解

    Oracle 中 EXISTS 和 IN 的效率问题详解 EXISTS 和 IN 都是 Oracle 中的集合操作符，但它们在使用和执行效率上有所不同。本文将深入探讨 EXISTS 和 IN 的使用场景、执行机制和效率问题。 EXISTS 的使用场景和机制 ...

    SQL里的EXISTS与IN

    在SQL查询语言中，`EXISTS` 和 `IN` 子句都是非常常用且重要的操作符，它们被广泛应用于复杂的查询条件中，特别是当需要检查某个子查询是否返回结果时。根据给定的信息，本文将详细解析`EXISTS`与`IN`的区别以及如何...

    “exists”和“in”的效率问题

    ### "Exists"与"In"的效率问题详解 #### 引言 在数据库查询语言SQL中，“Exists”与“In”是两种常用的子查询方法，它们在实际应用中各有优势与局限。本文将深入探讨这两种方法的工作原理、应用场景以及性能差异，...

    sql case when exists not exists in not in

    这些概念对于理解和编写高效的SQL语句至关重要，尤其是在数据分析和数据库管理中。 `CASE WHEN` 是SQL中的一个条件表达式，允许我们根据不同的条件返回不同的结果值。基本语法结构如下： ```sql CASE WHEN 条件1 ...

    经典SQL查询总结关于Exists,not Exists.in ,not in效率的说明。

    ### 经典SQL查询总结关于Exists, not Exists, IN, not IN 效率的说明 在数据库查询操作中，存在着多种方法来实现相似的功能，但不同的实现方式在性能上可能会有显著差异。本文将深入探讨 SQL 中 `EXISTS`, `NOT ...

    Oracle In和exists not in和not exists的比较分析

    以下是对这些操作符的详细分析和比较。 1. `IN` 操作符： `IN` 用于检查某个值是否存在于子查询的结果集中。它通常更直观易读，因为其语法结构清晰。例如，如果你想找出部门ID在特定列表中的员工，你可以写成： ```...

    简述Oracle中in和exists的不同

    且看接下来的具体分析：in其实是将外表和内表进行hash join，exists是先对外表进行loop操作，然后每次loop后再对内表进行查询。 如果两张表大小差不多，那么exists和in的效率差不多。 例如： 一张大表为A，一张小表B...

    sql语句优化之用EXISTS替代IN、用NOT EXISTS替代NOT IN的语句

    SQL语句优化之用EXISTS替代IN、用NOT EXISTS替代NOT IN的语句 SQL语句优化是数据库性能优化的重要方面之一。在许多基于基础表的查询中，为了满足一个条件，往往需要对另一个表进行联接。在这种情况下，使用EXISTS...

    in与exists之争(11g).sql

    in与exists之争(11g).sql

Magicbox
Global site tag (gtag.js) - Google Analytics