数据库集合查询的优化
有一个应用,需要经常做类似这样的查询 select * from SomeTable where key in (KeySet) ,其中 KeySet 可能很大,比如包含几百甚至几千个元素。理想中的情况,数据库应该先在 BTree 中查找到 KeySet 中的 Key 所在的物理页面地址,然后再对这物理地址排序,最后按顺序读入这些页面内容并填充结果。如果这样做,那么在最坏情况下,KeySet 中元素的逻辑排序完全不等于其物理顺序,并且,每个Key所在的页面还不在相同的磁盘柱面上,这样,查询集合中所有 key 所花的磁盘时间就等于 Key 的数目乘以磁盘的“平均潜伏时间”(Average Latency)再加上“柱面切换时间”(Cylinder Switch Time) 和 传输时间(Transfer Time):
T = KeySet.size * (al + cst + tt)
其中 al = Average Latency, cst = Cylinder Switch Time,实际上我这里说的 cst 比Cylinder Switch Time要大一些,因为柱面不一定相邻,中间可能像个几十个甚至上百的柱面,但这个时间跟cst应该比较接近。
这里假定内部处理所花的时间基本上可以忽略,在一般情况下也的确如此。一般情况下一个物理页面很小,如8K到16K。
对于高速的每分钟15000转的服务器硬盘,Average Seek Time 是8ms,连续传输速度是 200M,al=2ms,cst=1ms,使用16K的页面尺寸,则 tt = 0.025ms,因此可以先忽略tt。
如果KeySet中有4000个元素,并且BTree的所有内部节点(索引结点)都已经缓存,那么一次这样的查询需要 4000*(2ms + 1ms) = 12 秒!
而如果每查找一个key都启动一次在整个 BTree 上的查找,也假定BTree的所有内部节点(索引结点)都已经缓存,那么这个时间就是:4000*(al+ast) = 4000 * 10ms = 40秒
虽然经过优化,这个优化版的时间仍然很长,但是,这是查询4000个Key的最坏情况,很可能这些Key有一些局部性,比如他们只位于200个不同的柱面上(平均每个柱面20个key),这是非常可能的。这样,这个时间就缩短到了0.6秒,如果我们把数据库进行集群,比如10个服务器结点,那么这个数据可以缩短到0.06秒,这个时间就基本上可以接受了。对于传统方法,在这种情况下是0.2秒。
我在一个项目中碰到这样的瓶颈(数据量大约2T,使用磁盘阵列),找不到支持这种优化的系统。使用BDB(BerkeleyDB),最多也只能减少数据拷贝和网络传输的时间,这样的一个查询经常需要40秒以上的时间。让我难以忍受,因为事先根据我的分析和计算,Key是有一定局部性的,这个时间应该在2秒以内,再不行也应该在5秒内。最后我自己写了一个只读的BTree索引系统(完整的BTree处理太复杂),使用了这种优化,查询时间一下子缩短到了1秒以内,最后使用了10个分开的阵列,时间缩短到了0.1秒,基本可以满足需求。这个效果比我预先估计的要快很多,因为基于BerkeleyDB的效果,我猜想可能也就比BerkeleyDB快4倍的时间。
不过这个结果也证实了我之前的猜想:数据有一定的局部性,虽然KeySet中有4000个Key,但是这些Key中有很多是相邻的。并且,BerkeleyDB的实现可能也没有我想象的好,也有可能是其它原因,比如可能每次查询的间隔时间较大,使得即使数据相邻,也需要重新调度磁头等等。
如果随着技术的发展,磁盘最终被其它介质(如Flash)代替,这种方法是不是就没了用武之地?