打字猴:1.700509435e+09
1700509435
1700509436 如图13-10所示,以英文中记录“东、西、南、北”的索引值“East、West、South、North”为例,在建立索引时要以图中所示的方式进行标注,这样就没有B-TREE树来做二分查找了。纵列是4个键值,横列是各行的行号或物理地址,如果某行上有这个值就用1来表示,如果没有就用0来表示,这样就形成了一个二维数组。一旦在用于查询的SQL语句中使用where谓词对Bitmap索引建立的列进行限制,就可以立刻过滤出所有带有这个键值的数据块的物理地址列表。
1700509437
1700509438
1700509439
1700509440
1700509441 图13-10 Bitmap索引
1700509442
1700509443
1700509444 因为通过索引键值(也就是枚举值)可以直接指向一个表示行信息的地址数组,所以这种方式的扫描效率很高。以Oracle的RowID为例,使用18字节作为数据行的物理地址,理论上一个8KB的块可以存放约455个数据行的地址信息。对于枚举类型来说,至少可以避开其他枚举值所在行的扫描。在字段A中有n个枚举值且分布均匀的情况下,检索花费的时间会比没有Bitmap索引短,占比为。
1700509445
1700509446 需要注意的是,索引的使用也不是万能的。如果where限制谓词不能通过索引的描述特性避开大部分的数据块扫描,那么索引一定会失效。举个例子,在一个INT类型的字段A上建立B-TREE索引,如果使用谓词
1700509447
1700509448 SELECT ……WHERE A<>10;
1700509449
1700509450 当数据库的SQL解释器拿到这个谓词之后,由于无法通过B-TREE树的二分查找原理避开相应的数据块,因此只能进行穷举查找,这时索引将会失效。
1700509451
1700509452 3.QUBE模型
1700509453
1700509454 如果在扫描时,结果集中的数据量在整个扫描数据集中占比非常小,就表示索引的效果非常好,反之,索引速度就会变慢。这是为什么呢?熟悉Oracle的朋友应该知道,Oracle的SQL策略优化是基于一个叫作“CBO模型”(Cost-Based Optimizer)的东西。CBO模型从中文直译的角度看就是一种基于成本(Cost)的优化器,这个成本是指访问成本。有一个与CBO模型近似的成本评估模型叫作“QUBE模型”(Quick Upper-Bound Estimation)。这个模型很简洁,也便于我们研究和评估。
1700509455
1700509456 QUBE模型有几个重要的公式:
1700509457
1700509458
1700509459
1700509460
1700509461 其中,“LRT”代表“Local response time”,“TR”代表“Number of random touches”,“TS”代表“Number of sequential touches”,“F”代表“Number of successful FETCHes”。
1700509462
1700509463 这个公式的含义是:
1700509464
1700509465 响应时间=随机读的次数×10ms+顺序读的次数×0.01ms+处理的记录数×0.1ms
1700509466
1700509467 在这个模型中有一个假设,就是一次随机读取时间大约为10ms。这10ms是怎么估算出来的呢?以SCSI硬盘为例,转速为10000~15000rpm,则每秒转动167~250圈,平均每圈耗时4~6ms。除了转动消耗的4~6ms外,还有排队时间、传输时间。计算可知,共计约10ms完成一次完整的访问。每次每条记录的读取耗时0.01ms,这个假设的前提是磁盘带宽为40MB/s,一个数据块(4KB)上平均存放10条记录。每条记录的传输时间是
1700509468
1700509469
1700509470
1700509471
1700509472 因此,有如下推论。
1700509473
1700509474 假设索引的选择率(Selectivity)是s,表中的记录数是N,按照QUBE模型会得到
1700509475
1700509476
1700509477
1700509478
1700509479 单位都是ms。
1700509480
1700509481 经过计算,当s < 0.001时,使用索引的时间才会小于全表扫描的时间(因为索引访问本身也有成本)。在工程实践中,结合使用缓存等诸多因素,s通常会取到10%~20%。如果s再大一些,就建议使用全表扫描。在这个讨论中有特殊的数值假设,在实际应用中会使用指标不同的硬件设备,所以会对s临界值的估算会有一定影响。在这里,我们只讨论考虑问题的思路,具体的场景要在具体的环境中测算和推定,切莫刻舟求剑。
1700509482
1700509483
1700509484
[ 上一页 ]  [ :1.700509435e+09 ]  [ 下一页 ]