一种使用索引式备份的范围查询方法

Range Search Method Based on Indexed Backup in Distributed Data Store

范围查询是数据库支持的重要功能之一.在分布式数据库中,范围查询具有结果不唯一且数据量大的特点,因而中间结果的传输成本较高;同时,在以唯一主键散列存储的数据上查询非主键列上的范围条件,得到的命中数据较为分散,造成传输开销大和计算复杂度的问题.针对以上问题和基于高可用系统中数据存在多个备份的观察,本文设计了一种使用索引式备份的范围查询方法,通过将备份数据依据索引列重构实现范围查询友好的索引式备份,优化基于非主键列的范围查询任务.使用索引式备份的范围查询具有数据聚集的特点,能够有效减少数据传输成本、提高计算效率.实验结果显示,在TPC-H基准测试中,本方法相对于传统B+树索引方法具有8.4至16.7倍的性能提升,且具有较好的可扩展性.

Range searching is one of the essential functionality that database should provide. In distributed database, the transmission cost of intermediate data is relatively high because of the non-unique, high-volume results matched by range conditions. Besides, range- searching on non-primary key columns will get scattered results when data is indexed by primary key, leading low efficiency in trans- mission and computation. In this paper, we design a range search method based on indexed backup, based on observation that data has multiple backups. Data in backup is reorganized by indexed columns to answer the range queries more efficiently. In this way, data fil- tered by range conditions is stored together,which largely benefit transmission and computation. Experiments on TPC-H benchmark show that range-searching on indexed backup outperforms B ＋ tree index methods by 8.4X-16.7X,and the design has good scalability.