跳跃式索引扫描的结构猜想

jeffli73

最近赋闲在家，倒是很高兴有机会跟大家多交流一些技术问题

在我刚工作接触数据库时就有一个疑问，如果在一个SQL的WHERE条件中只包含某一个索引的次关键字，而不包括主关键字，为什么DBMS不能利用这个索引呢？
想索引的问题，我总是拿字典作为参照实例。如果现在我面临这样一个任务，统计某本英文字典中第二个字母为B的单词有哪些，我为什么要从头到尾扫描整本字典，而不是针对每一个首字母（从A开始），分别统计其中符合条件的单词，由于有序统计会比较快；一个首字母统计完后，再统计下一个首字母（为B），直到最后（Z），显然这种跳跃式地扫描应该比从头到尾扫描整本字典快很多（当然还是比对第二个字母单独有一个索引慢）。
我首先接触的数据库是SYBASE，当时应该是版本10，没有这个功能，不久之后我开始使用ORACLE，当时是7.3也没有这个功能。当然作为学计算机的，我可以理解，毕竟这个功能有些象锦上添花的功能，其实现的优先级不会很高。但我心理总有这样一个疑问，究竟DBMS的优化机制何时能考虑这种情况。终于在两年前接触ORACLE 9I时，发现其实现了这种算法。

其具体的算法，在Oracle9i New Features Overview中有些介绍，我觉得大体够用，特此摘录出来作为附件，供大家参考。

我想说明几点个人看法：
我想ORACLE并没有增加新的索引类型，也没有改变原有的索引结构，它只是引入了新的算法来满足一些查询的需求；
对于a的选择性对效率的影响，几位朋友的观点我非常赞同。（A,B,C)作为索引关键字，对于A这个首关键字我们不防假设两个极端情况，A没有取值或只取一个值，那么此时按照此种算法，从理论上说（A,B,C)这个索引从效果上已跟（B,C)索引差不多了，B实际上跟主关键字差不多了，效果肯定相对是好的；相反，如果A是主键，那么按照此种算法，实际上对每个索引项都要比较，效果肯定相对是差的；
应该注意该算法对索引块的取舍原则；
总的来说，该算法为我们一些不是很重要的SQL（不重要体现在我们不愿意为其单独建立相应的索引，或者是怕建立索引对其它SQL产生比较大的负面）提供了进一步优化的一种手段。

个人看法，供大家参考、指正。

biti_rainy

当初我没有做实验去dump  block 来观察是一大失败

从算法的角度来考虑

也就是说结构本身没有发生变化，但是在索引的搜索算法上可以从多个root ,branch进入进行扫描数据，这样当索引层次多的时候代价获取会高一些，但是不用维护结构的变化。


这样是可以的。 比如，如果8i的数据库升级到9i能使用 skip  scan,那也一定是从算法的角度来考虑的，现在回想起来，当初应该是考虑的过于精细了，假设了很多列的复合索引下使用复杂结构来维护最小的查询代价，但实际上可能得不偿失。

likaiabc

www.**.org,会屏蔽么，我来做个测试。

yulihua49

原帖由 biti_rainy 于 2002-12-27 10:29 发表
首先oracle 肯定不会是使用多个索引来掩盖问题的本质，那现在请允许我

假设索引(a,b,c)
我猜测是索引b或者c也有一个相临值之间的 “地址指针”
但他们之间是否具有树型结构不清楚
若不具有树结构则每次从该a 不同值进入从第一个b 值开始寻找符合条件数据
若具有树结构则每次进入一个a然后就迅速定位到符合条件b值
这样可能对每一个a值都要进入一次

我这样猜测
那么就可以通过控制a 或者 b值的数据分布和符合条件比例来逐步证明自己的猜测是否正确

举个例子
假设数据分布:
a      b     c
1      1     1
1      2      2
1      2      3
1      3       1
2      1       1
2       2       2
2       2       3

当查询  b = 2  的时候
不存在树结构： 先进入a=1,  然后顺序((也可2分法等方法,因为是排序好的)
)b=1,b=2,发现2条，不用比较3了，因为是有序的
存在树结构：  进入a= 1  ,迅速定位到2，然后找出和服条件记录

然后进入a=2 重复上面的过程

当查询 c =  3 的时候，先进入 a = 1,b=1,发现没有
进入 a=1,b=2,无树结构能快速定位到3(也可顺序可2分法,因为是排序好的),如此重复上面的步骤


由这个猜想
当数据量特别大并且数据可选择性很大的时候这种方式具有很大的优点
但这种猜测方式，假如 a 不具有相同值，而b  或者c 选择性比较小，那么这种结构的跳跃式扫描将是一种灾难

所以，oracle将根据统计分析结构来决定

但是，假如上述猜测不成立！
那其实，根据现象我们也能猜想出一种适合的结构来
关键在于思想上的东西

你这个想法在B树结构里很难实现。
现在就连以下条件都不能索引：
where a=1 and (b=2 or b=3)

[ 本帖最后由 yulihua49 于 2008-8-13 16:12 编辑 ]

必有我师

index skip scan实际上可以简单的理解为多个SQL的union，只不过是oracle帮你做好了而已
对于上面的例子：
select * from t where b =2
可以看成是
select * from t where a=1 and b=2
union
select * from t whree a=2 and b=2
也就是说做了多个range scan，因此需要多次root block->leaf block，因此a字段的选择性对index skip scan的cost起着决定性的作用

Yong Huang

原帖由 必有我师 于 2009-3-4 23:40 发表
index skip scan实际上可以简单的理解为多个SQL的union，只不过是oracle帮你做好了而已
对于上面的例子：
select * from t where b =2
可以看成是
select * from t where a=1 and b=2
union
select * from t whree a=2 and b=2
也就是说做了多个range scan，因此需要多次root block->leaf block，因此a字段的选择性对index skip scan的cost起着决定性的作用

Why do you have that understanding? Does a in t only have two values, 1 and 2?

Yong Huang

必有我师

原帖由 Yong Huang 于 2009-3-6 02:35 发表


Why do you have that understanding? Does a in t only have two values, 1 and 2?

Yong Huang

举个例子
假设数据分布:
a      b     c
1      1     1
1      2      2
1      2      3
1      3       1
2      1       1
2       2       2
2       2       3
我只是就着biti的例子描述的。

Yong Huang

原帖由 必有我师 于 2009-3-6 01:22 发表

举个例子
假设数据分布:
a      b     c
1      1     1
1      2      2
1      2      3
1      3       1
2      1       1
2       2       2
2       2       3
我只是就着biti的例子描述的。

So if a has values from 1 through 10000, the skip scan is equivalent to a union of 10000 subqueries? That's not possible.

Yong Huang

simonwen

学习ing

qqmengxue

我觉得跳跃式索引实现原理其实简单的想就相当于叫你去查字典里所有的汉语拼音内的第二个字母的x的字，然后在字典里拼音也都是先根据第一个字母排列然后第二个，这样后面查询的时候也就很easy了。。