基于Bin位图索引的多维查询优化算法

Multi-dimensional query optimization algorithm for bitmap index with binning

在属性基数(该属性可能的取值数)很高的情况下,简单位图索引需要占用太大存储空间。Bin位图索引可以很好解决这个问题。这种索引不像简单位图索引那样建立在不同的属性值上,而是建立在属性范围上,但候选检查往往占用大部分的查询时间。为了提高查询性能,提出一种排序方法来对各属性进行排序,以减少候选检查数目,并在此基础上提出动态预扫描算法。实验结果表明,排序和动态预扫描算法都取得了良好的效果。

The storage requirements for simple bitmap index is unacceptable when cardinality the number of distinct values of the attribute is very high.A common approach to solve this problem is to build bitmap index with binning.This technique builds a bitmap for each bin in a certain attribute range rather than distinct values.But this approach cause the time waste during candidate check because candidate check usually dominates the most of query processing time.In order to improve query performance a new sort method for attributes was propsed to reduce the number of candidate check.And then a dynamic pre-scan algorithm was proposed.The experimental results show that our approach has a significant improvement over traditional strategies.