in和exists区别

引子

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));
    }
}

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);
    }
}

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

 select * from student where studentId=_student_id

in(子查询全表扫描):

 

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

4 简化

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

Time_Exists = studentTable.size() * Time(一条exists语句的执行时间)

Time_IN = scoreList.size() *Time(一条select语句的执行时间) 

通常情况下，我们不允许TABLE ACCESS FULL的出现，该加索引的地方加索引，因此进一步简化为

Time_Exists = studentTable.size()，即是主表大小

Time_IN = scoreList.size() ，即是子查询结果集大小

 

数据量大，在决定该使用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区别的一个原因。

 

四、后记

后面我看到了一篇文章，同样比较简单易明，应该描述得比我准确，摘录下来，与大家共享 ：）

from: 

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