一种对分布式顺序表进行多维区间查询的方法及其系统

摘要

本发明公开了一种对分布式顺序表进行多维区间查询的方法及其系统，其中方法包括：分别为所述分布式顺序表的每个索引列创建一张对应的二级索引表，各索引列对应的二级索引表的主键为该索引列值、所述分布式顺序表的主键值和该索引列值的长度三者的拼接值；当接收到区间查询请求时，依据所述查询请求的字段名称，从各所述二级索引表中查找所述字段名称对应的二级索引表，依据所述查询请求的字段值，从所述对应的二级索引表中查找所述查询请求字段值对应的记录位置，直接从所述分布式顺序表中的该记录位置读取相应的数据。本发明能大幅增加多维区间查询的速度，能够同时满足高性能、低存储开销和高可靠性的要求。

说明书

技术领域

本发明涉及分布式信息处理技术领域，尤其涉及一种对分布式顺序表进行多维区间查询的方法及其系统。

背景技术

分布式顺序表（Distributed Ordered Table简称DOT）是一种最适用于海量数据（TB到PB级）下多维区间查询的数据库系统。在分布式顺序表上进行多维区间查询时，通常直接扫描全表筛选出满足条件的数据。在数据量非常大的时候，这种方法的查询速度缓慢，并且使系统负载很大，响应时间过长不能满足目前网络应用对海量数据进行实时检索的需求。

发明内容

本发明的主要目的即基于分布式顺序表构建索引，使其能够满足多维区间查询时的高性能、低存储开销和高可靠性要求。

为达此目的，本发明采用以下技术方案：

本发明提出了一种对分布式顺序表进行多维区间查询的方法，包括：

分别为所述分布式顺序表的每个索引列创建一张对应的二级索引表，各索引列对应的二级索引表包括该索引列信息、所述分布式顺序表的主键信息；

当接收到区间查询请求时，依据所述查询请求中查询条件对应的字段名称，从各所述二级索引表中查找所述字段名称对应的二级索引表，依据所述查询请求的查询条件，从所述对应的二级索引表中查找符合所述条件的记录，从各记录中读出该记录对应的主键值，依据所述主键值直接从所述分布式顺序表中读取相应的数据。

进一步地，各所述二级索引表的主键为该二级索引表对应的索引列、所述分布式顺序表的主键和该索引列的长度三者的拼接值，

或者，各所述二级索引表的主键为该二级索引表对应的索引列、所述分布式顺序表的主键和所述分布式顺序表的主键的长度三者的拼接值。

进一步地，当接收到区间查询请求时，首先对所述查询请求中的查询条件进行合并去重预处理，将预处理结果转化为析取式，从合取子式中选择结果集最小的子查询作为所述区间查询请求的查询条件。

进一步地,所述从合取子式中选择结果集最小的子查询的方法包括：分别根据各合取子式中每个分片的起止主键，计算各合取子式的查询范围所覆盖的分片数量，选择分片数量最少的合取子式的结果集。

进一步地，还包括：

当需要进行数据更新时，首先将更新写入日志中，然后再分别更新所述分布式顺序表和索引表；

当出现故障使部分数据丢失，使所述分布式顺序表和索引表数据不一致时，依据所述日志进行数据恢复。

根据同一发明构思，本发明还提供了一种对分布式顺序表进行多维区间查询的系统，包括：

索引表建立模块，用于分别为所述分布式顺序表的每个索引列创建一张对应的二级索引表，各索引列对应的二级索引表包括该索引列信息、所述分布式顺序表的主键信息；

区间查询模块，用于当接收到区间查询请求时，依据所述查询请求中查询条件对应的字段名称，从各所述二级索引表中查找所述字段名称对应的二级索引表，依据所述查询请求的查询条件，从所述对应的二级索引表中查找符合所述条件的记录，从各记录中读出该记录对应的主键值，依据所述主键值直接从所述分布式顺序表中读取相应的数据。

进一步地，各所述二级索引表的主键为该二级索引表对应的索引列、所述分布式顺序表的主键和该索引列的长度三者的拼接值，

或者，各所述二级索引表的主键为该二级索引表对应的索引列、所述分布式顺序表的主键和所述分布式顺序表的主键的长度三者的拼接值。

进一步地，还包括分片信息预估优化查询模块，用于当接收到区间查询请求时，首先对所述查询请求中的查询条件进行合并去重预处理，将预处理结果转化为析取式，从合取子式中选择结果集最小的子查询作为所述区间查询请求的查询条件。

进一步地,所述分片信息预估优化查询模块中从合取子式中选择结果集最小的子查询作为所述区间查询请求的查询条件包括：分别根据各合取子式中每个分片的起止主键，计算各合取子式的查询范围所覆盖的分片数量，选择分片数量最少的合取子式的结果集。

进一步地，还包括日志模块，用于当需要进行数据更新时，首先将更新写入日志中，然后再分别更新所述分布式顺序表和索引表；当出现故障使部分数据丢失，使所述分布式顺序表和索引表数据不一致时，依据所述日志进行数据恢复。

本发明能大幅增加多维区间查询的速度，能够同时满足高性能、低存储开销和高可靠性的要求。

附图说明

图1是本发明具体实施例一所述的对分布式顺序表进行多维区间查询的方法流程图；

图2是本发明具体实施例一所述的对分布式顺序表建立的二级索引表的示意图；

图3是本发明具体实施例三所述的对分布式顺序表进行多维区间查询的系统结构框图。

具体实施方式

下面结合附图并通过具体实施方式来进一步说明本发明的技术方案。

实施例一

图1是本发明具体实施例一所述的对分布式顺序表进行多维区间查询的方法流程图，如图1所示，本实施例具体方法包括：

S101、为各索引列创建二级索引表；

分布式顺序表所存储的数据按主键被水平划分为多个分片（Region）,每个分片存储一段按照主键排序的数据，同时将分片分配到多个分片服务器(RegionServer)上，支持按主键进行高速点查询和区间查询，支持高速随机数据读写。每张表可有一个或多个列，支持按列投影等操作。

当数据查询时，查询条件经常会指定一列或多列来给定，这些经常用作查询条件的一列或多列，通过对之前的查询条件进行统计，或依据分布式顺序表的结构特征的分析，可指定所述分布式顺序表中至少一个非主键的列作为索引列，用于分别基于这些列创建二级索引表。

分别为分布式顺序表的每个索引列创建一张对应的二级索引表，各索引列对应的二级索引表必须包括该索引列信息、所述分布式顺序表的主键信息，可有多种组织方式。

例如，各所述二级索引表的主键为该二级索引表对应的索引列、所述分布式顺序表的主键和该索引列的长度三者的拼接值；或者，各所述二级索引表的主键为该二级索引表对应的索引列、所述分布式顺序表的主键和所述分布式顺序表的主键的长度三者的拼接值。

图2是本实施例所述的对分布式顺序表建立的二级索引表的示意图，如图2所示，分布式顺序表(又称为原表)100包含列：id，idx1,idx2和info，其中，id表示原表的主键，idx1和idx2为两个索引列，info为其他的数据内容的一列或多列。

本示意图中为每个索引列分别创建索引表的方法为：各所述二级索引表的主键为该二级索引表对应的索引列、所述分布式顺序表的主键和该索引列的长度三者的拼接值。

参见图2，为所述分布式顺序表100的两个索引列idx1和idx2分别创建索引表101和102，其中，索引表101的主键key1由当前索引列idx1、原表的主键值id、以及当前索引列idx1的长度值idx1Length顺序拼接而成，索引表102的主键key2由当前索引列idx2、原表的主键值id、以及当前索引列idx2的长度值idx2Length顺序拼接而成。

这种方式使得索引表先按列值排序再按原主键排序，同时，通过对索引列值的长度的记载，可以从新主键中得到原主键和索引列值，即使索引列重复也能具有唯一的新主键。

S102、依据查询请求的字段名称，找到对应的二级索引表；

当需要对索引列进行区间查询时，连续扫描与该索引列对应的所述索引表，找到与该索引列相关的所有二级索引。

S103、依据查询条件，从二级索引表中查找符合条件的记录；

根据所找到的二级索引表，从所述二级索引表中查找符合条件的记录。

S104、从各记录中读出对应的主键值；

由于每个二级索引表中每一条记录均记载了索引列信息和对应的分布式顺序表的主键信息，所以，从所述二级索引表中查找符合条件的记录后，可在记录中查找该记录在对应的分布式顺序表的主键值。

S105、依据主键值直接从分布式顺序表中读取相应的数据。

通过主键值，直接从分布式顺序表中读取相应的数据。

实施例二

为了进一步优化对分布式顺序表的区间查询，当需要对索引列进行区间查询时，在实施例一的步骤S102之前还可以进一步包括分片信息预估优化查询步骤；为了保证所述分布式顺序表和索引表中的数据始终能保持一致，当需要对分布式顺序表进行更新时，本发明还可以包括步一致性更新步骤。

分片信息预估优化查询步骤：

当需要对索引列进行区间查询时，对查询计划树进行合并去重预处理，然后将查询逻辑转化为析取式后并行执行，执行时从合取子式中选择结果集最小的子查询来执行，而其它子查询以谓词形式对结果集进行过滤。

其中，选择结果集最小的子查询时利用分布式顺序表中存储的数据分片信息，根据每个分片的起止主键，计算查询范围覆盖的分片数量，由此即可估算出结果集大小，最后挑选结果集最小的子查询执行查询过程。

下面描述查询处理和优化的具体过程：首先将查询串转换为查询计划树，树的每个叶子节点是查询系统能直接处理的点查询和单个维度的区间查询，树的非叶子节点表示多个查询的逻辑关系。之后对查询计划树进行预处理，执行一些简单的合并去重优化。然后估算结果集大小，估算子查询结果集的大小具体包括：

步骤S1031，对于每个给定的区间查询，由其起始键值和结束键值通过对元信息中数据的查找确定此区间查询覆盖的分片数量；

步骤S1032，累加全部分片的大小，获得估算的结果集大小。最后，查询执行时，对计划树中“或关系”的子查询并行执行，而对“与关系”的子查询，选择结果集最小的一个实施查询，其它查询条件作为谓词。

查询优化的关键是估算结果集大小，由于DOT系统的数据量极大，而查询所需时间与结果集字节大小正相关，所以从多维属性中选取结果集最小的属性进行扫描操作可以极大地优化查询性能。本发明利用了DOT表中主结点(master)管理的数据分布信息进行结果集的预估，提高了区间查询的性能。

进行一致性更新步骤：

当需要对分布式顺序表进行更新时，本发明还可以包括步一致性更新步骤。具体为：在更新一条数据之前，首先将更新写入日志中，然后再分别更新所述分布式顺序表和索引表，更新时需遵循原子性操作要求二维索引表的更新，即：要么都更新，要么都不更新。

相应的，当由于出现故障而导致部分数据丢失，使所述分布式顺序表和索引表数据不一致的时候，通过写前日志来恢复丢失的数据。

在具体软件实现时，可基于Apache HBase来创建本发明所述的二级索引系统。HBase基于典型的分布式顺序表，构建于Apache HDFS，提供一个服务节点进程HMaster，并提供多个数据存储节点进程HRegionServer来管理数据。二级索引系统采用HBase v0.90.2作为代码基础，采用Java语言实现，在HBase中为每个索引列创建一张索引表，作为二级索引表。另外，HBase有一个元数据表，用于存储用户数据表的分片到存储节点的映射关系，二级索引系统通过扫描HBase中的元数据表，可以利用分片映射信息来估算结果集大小。以ApacheHBase作为基础，可以充分利用Apache Hadoop分布式存储技术现有的架构及代码，从而能够高效地构建本发明的二级索引系统。

实施例三

根据同一构思，本发明还提供了一种对分布式顺序表进行多维区间查询的系统，图3是本实施例所述的对分布式顺序表进行多维区间查询的系统结构框图。如图3所示，本实施例所述的对分布式顺序表进行多维区间查询的系统包括：

索引表建立模块301，用于在分布式顺序表上建立索引表，其中：为所述分布式顺序表的每个索引列分别创建一张索引表，将所述分布式顺序表的索引列值、主键值、索引列值的长度顺序拼接在一起作为所述索引表的主键，该主键即为所述分布式顺序表的二级索引；

当数据查询时，查询条件经常会指定一列或多列来给定，这些经常用作查询条件的一列或多列，通过对之前的查询条件进行统计，或依据分布式顺序表的结构特征的分析，可指定所述分布式顺序表中至少一个非主键的列作为索引列，用于分别基于这些列创建二级索引表。

索引表建立模块301用于分别为分布式顺序表的每个索引列创建一张对应的二级索引表，各索引列对应的二级索引表必须包括该索引列信息、所述分布式顺序表的主键信息，可有多种组织方式。

例如，各所述二级索引表的主键为该二级索引表对应的索引列、所述分布式顺序表的主键和该索引列的长度三者的拼接值；或者，各所述二级索引表的主键为该二级索引表对应的索引列、所述分布式顺序表的主键和所述分布式顺序表的主键的长度三者的拼接值。

本实施例优选的为每个索引列分别创建索引表的方法为：各所述二级索引表的主键为该二级索引表对应的索引列、所述分布式顺序表的主键和该索引列的长度三者的拼接值。

这种方式使得索引表先按列值排序再按原主键排序，同时，通过对索引列值的长度的记载，可以从新主键中得到原主键和索引列值，即使索引列重复也能具有唯一的新主键。

区间查询模块302，用于对索引列进行区间查询，其中：连续扫描与该索引列对应的所述索引表，找到与该索引列相关的所有二级索引，然后根据所找到的二级索引直接从所述分布式顺序表中读取相应的数据。

当需要对索引列进行区间查询时，连续扫描与该索引列对应的所述索引表，找到与该索引列相关的所有二级索引。

根据所找到的二级索引表，从所述二级索引表中查找符合条件的记录。

由于每个二级索引表中每一条记录均记载了索引列信息和对应的分布式顺序表的主键信息，所以，从所述二级索引表中查找符合条件的记录后，可在记录中查找该记录在对应的分布式顺序表的主键值。

通过主键值，就可直接从分布式顺序表中读取相应的数据。

分片信息预估优化查询模块303，用于当接收到区间查询请求时，首先对所述查询请求中的查询条件进行合并去重预处理，将预处理结果转化为析取式，从合取子式中选择结果集最小的子查询作为所述区间查询请求的查询条件。

为了进一步优化对分布式顺序表的区间查询，本发明还可以进一步包括，用于对查询计划树进行合并去重预处理，然后将查询逻辑转化为析取式后并行执行，执行时从析取式中选择结果集最小的子查询来执行，而其它子查询以谓词形式对结果集进行过滤。其中，所述分片信息预估优化查询模块在选择结果集最小的子查询时利用分布式顺序表中存储的数据分片信息，根据每个分片的起止主键，计算查询范围覆盖的分片数量，由此估算结果集大小。

日志模块304，用于当需要进行数据更新时，首先将更新写入日志中，然后再分别更新所述分布式顺序表和索引表；当出现故障使部分数据丢失，使所述分布式顺序表和索引表数据不一致时，依据所述日志进行数据恢复。

为了保证所述分布式顺序表和索引表中的数据始终能保持一致，本发明还可以进一步包括日志模块304，用于在更新一条数据之前首先将更新写入日志中，然后再分别更新所述分布式顺序表和索引表。更新时需遵循原子性操作要求进行这两个表的更新，即：要么都更新，要么都不更新。

相应的，当由于出现故障而导致部分数据丢失，使所述分布式顺序表和索引表数据不一致的时候，通过写前日志来恢复丢失的数据。

在具体软件实现时，可基于Apache HBase来创建本发明所述的二级索引系统。HBase基于典型的分布式顺序表，构建于Apache HDFS，提供一个服务节点进程HMaster，并提供多个数据存储节点进程HRegionServer来管理数据。二级索引系统采用HBase v0.90.2作为代码基础，采用Java语言实现，在HBase中为每个索引列创建一张索引表，作为二级索引表。另外，HBase有一个元数据表，用于存储用户数据表的分片到存储节点的映射关系，二级索引系统通过扫描HBase中的元数据表，可以利用分片映射信息来估算结果集大小。以ApacheHBase作为基础，可以充分利用Apache Hadoop分布式存储技术现有的架构及代码，从而能够高效地构建本发明的二级索引系统。

本发明在仅增加少量存储开销用于存储二级索引表的情况下，能大幅增加多维区间查询的速度，能够同时满足高性能、低存储开销和高可靠性的要求。

以上实施例提供的技术方案中的全部或部分内容可以通过软件编程实现，其软件程序存储在可读取的存储介质中，存储介质例如：计算机中的硬盘、光盘或软盘。

以上所述仅为本发明的较佳实施例，并不用以限制本发明，凡在本发明的精神和原则之内，所作的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。