ITPub博客

首页 > 数据库 > 数据库开发技术 > 散列连接,索引,嵌套循环

散列连接,索引,嵌套循环

原创 数据库开发技术 作者:haijie1984 时间:2007-11-20 16:52:15 0 删除 编辑

1 深入理解嵌套循环执行计划
为什么要引入散列连接呢?假设两张表t1(c1 int,c2 int),t2(d1 int,d2 int),查询语句为select c1,d1 from t1 inner join t2 on c1=d1。如果数据库没有实现散列连接、合并连接的话,只能选择使用嵌套循环。从上篇文章中我们可以得到,对于t1的每一条记录,都需要遍历t2的每一条记录。因此,当t1的记录数数为m,t2的记录数为n,那么该查询语句访问的记录次数为m*n。当m=10000n=10000时,那么m*n=1000000001亿)。这是比较夸张的浪费时间。如果m100万,n100万,那么m*n就是1万亿次,读一万亿次记录,这是不能忍受的。
这里需要提到的一点是:我们不以读取记录的多少作为评价标准,在实际代价评估中,采用数据页(也可称为数据块,I/O的基本单位)。但是两者之间又是有联系的,假设每个页存放100个数据,那么t1的数据页为100(10000/100)t2的数据页为100页,那么对于t1中的每一条记录,需要遍历t2100页,加上该记录在t1中也属于一个数据页。因此,对于t1中的每一个记录,需要访问101个数据页。那么该查询的I/O量为:10000*100+1=1010000页。如果考虑到数据页的缓冲,情况会更加复杂。代价评估是个很复杂的课题,可能需要单独写个系列来阐述数据库查询优化系统的代价评估模型。这里我们不考虑数据页缓冲,也就相当于假设数据库缓冲区的大小仅仅为1个页。
好了,继续前面的话题。
如果t1(c1)上建立有唯一索引iut1c1,那么可以将t2作为外表,对于t2的每一条记录,使用d1的值去命中索引iut1c1对应的B树。假设该B树的高度为3层,那么对于t2的每一条记录,需要访问t1表索引iut1c1中三个页(B树的高度),加上本身在t2中属于一个页。所以,在这种情况下,查询代价为:10000*(3+1)=40000页。
我们来对比一下,没有索引与有索引,两者之间的代价对比约等于25:1(比值101000040000)。也可以这么认为,假设没有索引的时候执行需要25s,那么有索引的情况下只需要1s
这里我们把话题再延展下,如果m,n都为1000000,占用的块都为10000页(1000000/100)。没有索引的情况的I/O量为:1000000*(10000+1)=10001000000页。在t1(c1)有索引,该索引的高度对应的高度为4的情况下,假设I/O量为:100000*(4+1)=5000000。对比一下,没有索引与有索引,两者之间的代价比约等于2000:1。相等于,假设没有索引的情况下执行需要2000s,那么有索引的情况下只需要1s
从上面的对比当中,我们可以发现索引的重要性,在实际应用当中,80%的查询性能问题来源于没有创建索引或者没有创建合适的索引。
2 数据库内核使用建立临时索引的方法
大家可能听到过一个这样的概念:“在sqlserver系统中,如果用户没有创建索引,执行查询时,sqlserver会自动创建该索引。”
这里我们先撇开sqlserver到底是使用临时索引还是散列连接,我们只是对这句话加以理解。
对于上文提到的查询语句,执行过程描述如下:
1)create index itemp on t1(c1);
2)执行查询语句select c1,d1 from t1 inner join t2 on c1=d1;
3)drop index itemp;
我们来评估下代价。如上文锁描述,假设m,n都为1000000,占用的块都为10000页。
首先是计算构造索引的代价:对t1的数据进行全扫描,对于每一条记录要插入到B树中,假设插入操作平均需要使用3个页。(因为起始时,B树只有一层,插入只需要访问1页,B树两层使需要访问2页,等等)。该步骤的代价为:1000000*(3+1)=4000000页。
然后计算查询的代价,前面已经计算过:100000*(4+1)=5000000页。
所以,整个代价为4000000+5000000=9000000页。
进行对比:10000:9:5(比值10001000000:9000000:5000000)。不使用索引的代价为10000,使用临时索引的代价为9,使用用户创建的索引代价为5。
所以,我们发现使用临时索引还是个不错的选择。
3 数据库内核使用散列连接的方法
首先我们讲下散列连接的原理:
1)对t1表(称为构建表)进行全扫描,对于每一个记录,对c1值进行使用内部散列函数,然后将该数据存放到相应的散列桶。
2)开始读t2表(称为探查散列表),对于t2的每一个记录,对d1值使用同样的散列函数,得到相应的散列值,查看该桶中是否有行。
如果相应的桶中没有行,则会丢失t2中这一行记录。如果散列桶中如果有一些行呢,则会精通的检查散列连接判断是否存在合适的匹配。因为不同的值可以产生同样的散列值。找到精确匹配的值,组合成记录放入结果集中。
我们来评估下代价。
1)首先我们先看构建散列的代价,对于t1的每一个记录,一般只需要访问一个散列桶。所以该步骤的代价为:1000000*(1+1)=2000000页。
2)对于t2的每一个记录,一般只需要访问一个散列桶。所以该步骤的代价为:1000000*(1+1)=2000000页。
所以,整个代价为2000000+2000000=4000000页。
进行对比:10000:4:5(比值10001000000:4000000:5000000),不使用索引的代价为10000,使用散列连接的代价为4,使用用户创建的索引代价为5。
是不是觉得不可思议?散列连接的代价竟然比使用索引的连接还小。我们通过一个例子来验证一下:
SQL> create table t1(c1 int,c2 int);
Table created.

总结:

1 循环嵌套

t1表的记录都要在t2全部查询。

2 索引

t1表的记录在t2种合适前几页查询。

3 散列
首先利用散列函数建立散列桶,t1散列桶每条的记录在t2散列桶查询

原文地址:http://blog.chinaunix.net/u1/40568/showart_380413.html

[@more@]

来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/7282477/viewspace-983066/,如需转载,请注明出处,否则将追究法律责任。

上一篇: 没有了~
请登录后发表评论 登录
全部评论

注册时间:2009-06-23

  • 博文量
    37
  • 访问量
    406878