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

[size=medium]
引子
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);

Java代码 

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

Java代码 

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+ x*scoreTable.size()  (0<=x<=1)
对于x，这样理解。例如本例子中的子查询 (select student_id from score where total>90);
total上建立上索引，如果只有一个人超过90分，那么x可以视作0
total上建立上索引，如果所有人都超过90分，那么x可以视作1.


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

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

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

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

ref：http://lazy2009.iteye.com/blog/1697458