time 
设为首页】【收藏本站
当前位置: 主页 > 数据库 > 数据库理论 > JAVA伪代码直白分析SQL查询中in和exists的时间复杂度

JAVA伪代码直白分析SQL查询中in和exists的时间复杂度

时间:2012-10-14 13:29 点击:2170次 字体:[ ]




引子

in和exists的讨论从未间断过。关于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);

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

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

 

2 in方式

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

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

时间复杂度为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区别的一个原因。

 

转:http://lazy2009.iteye.com/blog/1697458



本文地址 : http://www.fengfly.com/plus/view-209619-1.html
标签: SQL in exists 时间复杂度
------分隔线----------------------------
最新评论 查看所有评论
发表评论 查看所有评论
请自觉遵守互联网相关的政策法规,严禁发布色情、暴力、反动的言论。
评价:
表情:
验证码: