CN102467570B - 用于分布式数据仓库的连接查询系统和方法 - Google Patents

Abstract

一种用于分布式数据仓库的连接查询系统和方法。该系统包括主节点、映射工作节点和规约工作节点。主节点根据数据表的大小和系统性能来计算分片大小，基于计算得到的分片大小向映射工作节点分配数据块，并且规定映射工作节点中的分片映射规则和汇总规则。映射工作节点根据分片映射规则将数据块中的查询关键字映射到相应的分片编号，并根据汇总规则把具有相同分片编号的数据传输到指定的规约工作节点。规约工作节点接收映射工作节点传输的数据，合并具有相同分片编号的数据并按照查询关键字进行连接，以获得最终的连接查询结果。本发明减少了分布式系统内的数据传输，降低规约工作节点的数据量和程序复杂度，提高了分布式数据仓库的性能。

Description

用于分布式数据仓库的连接查询系统和方法

技术领域

本发明涉及数据库技术，具体涉及一种用于分布式数据仓库的连接查询系统和方法。

背景技术

随着信息技术的飞速发展，海量数据的存储、检索和分析变得非常关键。数据仓库即应运而生，其通常的定义是：一个面向主题的、集成的、稳定的、随时间变化的数据集合，用于支持管理决策。数据仓库有两个层次的含义，一是它用于支持决策，面向分析数据处理；二是它由多源异构数据组成，集成后按照主题重组，并包含历史数据。大容量、高性能、高可用性、可拓展性、可管理性以及按需服务成为衡量当今数据仓库和分布式文件系统的关键指标。

传统的数据仓库建立于重量级的服务器及数据仓库系统上，造价昂贵，拓展性差。数十台单机节点组成的集群，即已达到并行处理的瓶颈。但随着互联网服务的爆炸式发展，数据与信息呈现指数式增长，针对互联网数据的搜索引擎、用户数据挖掘、商业智能等应用，传统的数据仓库已经不能满足需求。基于分布式文件系统和映射/规约(Map/Reduce)分布式计算框架的大规模数据处理方法，可以建造在普通个人电脑之上，其造价低廉、拓展性强、支持异构数据格式，逐渐被业界采用，例如Google的GFS分布式文件系统、Facebook的Hive数据仓库等。

尽管如此，这些数据仓库目前一般用于离线的定时数据批处理，其效率还远不能达到实时性的要求。特别地，数据连接查询是基本的、频繁使用的功能，因此数据连接查询的效率对改善系统的总体性能来说意义重大。在分布式的数据环境中，数据连接查询的含义是查找集群中的数据并连接关联的字段，其本质是在海量的数据存储中建立一种合理的数据结构和分布式数据存储机制，以支持高效的连接查询。由于多个数据表可能存储于不同的数据节点上，如何快速定位这些分布式数据表并提高查询和排序的性能，是提升数据连接查询效率的关键所在。在传统的数据仓库技术中，数据聚簇、并行查询、数据分区是常见的提升性能的技术，下面一一加以介绍。

由于很多查询需要顺序访问大量的数据，数据聚簇技术解决了顺序访问的问题，聚簇通过物理地将表放在一起以获得顺序的数据聚簇，数据聚簇是数据库管理系统的功能，依赖于数据库本身的聚簇技术。很显然，这个技术在分布式的数据系统中不能直接使用。

并行处理是将大数据量的查询分成小的部分然后并行地执行以提高性能。并行处理技术可以用于数据加载和数据重组。并行处理技术和数据分区紧密联系。服务器硬件的并行架构也影响并行处理的方式。一些物理选项对高效的并行处理很重要。并行处理和分区技术一起提供了提高性能的巨大潜力。

数据分区是指针对大量的数据表(超过百万行记录)，因其载入效率低、索引时间长、备份和还原耗时大、遍历更新慢，故采用数据表分区将表和索引都进行分区管理，这样便于维护且操作方便。对于数据仓库来说，数据分区是关键的决策，必须在实施前计划好，因为后续的更改将耗费巨大。数据分区可以垂直分区和水平分区，在垂直分区中，将选择的列编组分割为分区，每个分区和原始表都具有相同的行数；在水平分区中，将选择的行分组进行分区，每个分区和原始表都具有相同的列数。数据分区具有很多关键的优点，如查询时只需查必要的分区、分区可脱机维护、更快地建立索引、数据损坏不扩散、分区与磁盘映射是输入输出平衡等。但是，传统的数据分区技术，基于数据库构建的数据仓库，在分区时，一般从业务逻辑出发来设定数据分区的准则，没有考虑到分布式处理的能力。正因为此，在不同分区的数据合并时，效率较低。最重要的是，这项技术无法支持巨量的分布式数据处理请求。而且，一旦发生数据更新，则所有的过程都要重新执行。

由于传统的数据仓库技术对分布式计算框架的支持不足，使得其拓展性、实时处理性具有瓶颈。在数据连接查询中，由于数据节点之间大量数据传输以及归并排序操作，导致资源利用率低下，性能较低。

在现有的研究成果中，由Facebook贡献的Hive数据仓库提出了一种大数据表的动态连接查询算法(下文称作第一参考方案)。该算法需要一个完整的映射/规约(Map/Reduce)过程，两个表都会作为映射过程的输入进入分布式处理。图1示出了分布式计算系统中通常采用的映射/规约(Map/Reduce)计算模型。如图1所示，分布式计算系统通常由若干个节点组成，这些节点被分为主节点和工作节点，主节点负责各工作节点的任务调度，各工作节点执行指定的任务。首先，如101处所示，用户程序根据映射/规约的编程规范，按照分布式文件系统规范准备输入，并准备映射和规约任务的执行代码。然后，如102处所示，主节点将映射和规约任务分别指派给对应的计算节点。映射工作节点被激活后，开始读入分配的数据块，该数据块位于分布式文件系统中，参见103处所示。接下来，如104处所示，映射任务按照用户程序对输入数据块进行处理，处理完毕后将结果写入到本地磁盘。在此之后，规约任务被激活，开始读入映射任务生成的远程数据文件(参见105)，并按照用户程序对数据进行规约处理。最后，如106处所示，将处理结果输出并写入分布式文件系统。

图2示出了根据第一参考方案的连接查询过程的系统框图，其中示出了一个主节点20、3个映射工作节点30和2个规约工作节点40。附图中相同的标记表示相同的元件。一般来说，映射工作节点的个数大于规约工作节点的个数。该系统是一种分布式的文件系统，使用类SQL的查询语句，对海量的数据表进行查询分析。在映射阶段，连接的字段将作为输出关键字(Output Key)，其他属性将作为值(Value)。在规约阶段，关键字相同的记录将被设置在一起，这样就完成了一次连接查询。

具体地，图2中所示系统的输入是并行系统中的数据表和特定的关键字(连接字段)。主节点20中的连接工作调度器201接收数据表和关键字，向系统中的工作节点分配映射任务和规约任务。在本示例中，3个工作节点被分配执行映射任务(即映射工作节点30)，2个工作节点被分配执行规约任务(即规约工作节点40)。每一个映射工作节点30中的存储单元301从主节点20的连接工作调度器201接收所分配的特定数据表中的特定数据块。例如，在本示例中，主节点20的连接工作调度器201向每一个映射工作节点30分配固定大小为64M的数据块。映射工作节点30中的映射排序单元302产生<关键字，值>对，并按照关键字对其进行排序。映射工作节点30中的分发单元303将映射排序单元302的结果向每一个规约工作节点40分发。规约工作节点40中的合并单元401对来自每一个映射工作节点30的数据进行合并，规约单元402对合并后的数据执行查询，连接排序单元403将查询结果进行连接，以获得最终的连接结果。

尽管上述第一参考方案对并行处理有良好的支持，但在效率方面存在很大的提升空间。在一个基本的映射和规约过程之间，存在集群内数据分发的过程，该方案对映射过程中生成的<关键字，值>数据未做处理，这些数据将被全部向各个规约节点分发，因此耗费非常大，导致连接查询的效率较低。

论文“A Switch Criteria for Datasets Merging on Top ofMapReduce”(The 8th International Conference on Grid and CloudComputing，GCC2009)介绍了一种数据归并标准，其中考虑单节点的处理能力和集群的并行处理能力，计算出每个映射任务最优的分块大小，并区分输入数据表的规模大小。如果小表的规模小于最优分块大小，则直接在全局文件中共享此小表，这样在连接查询的过程中，只需对大表进行映射处理。在映射过程中就将连接合并完成，无需进行规约过程的处理。这样，减少了映射与规约过程之间的数据分发，明显提高了效率。该方案在实际应用中非常重要，因为小表在分布式数据处理中普遍存在，所以提升小表处理的效率就提高了很多情形下数据处理的效率。然而，对于两个表规模都很大的情形(较小的数据表也超过单个任务的内存容量)，这个方案具有局限性。

专利申请WO2005076160A1(题目为“The Data WarehouseDistributed System and Architecture to Support Distributed QueryExecution”)提出了一种可拓展的、快速查询的分布式数据仓库架构。该专利申请考虑了分布式计算的性能以及负载均衡，也考虑了分片对于提升性能的重要作用，但其对分布式计算的拓展性支持不够。即，在分布式计算的情况下，未考虑到根据单个节点的性能，分配最优的任务及最优大小的数据片。因此，在大规模分布式环境下，资源利用率将比较低下。

发明内容

本发明旨在提出一种支持分布式存储和分布式计算框架的、以数据最优分片为核心的动态连接查询方案。在本文中，“分片”的含义是：根据规约节点的计算资源和映射规约计算框架，将分布式计算系统的输入文件进行适当的分割，以使得映射、规约过程中每个计算节点获得最优的资源利用率。具体地，本发明首先评估分布式集群系统的单机处理能力和集群的并行处理能力，基于评估结果对数据表进行动态分片，然后对每个工作节点上的每一个处理记录采用全局统一的映射算法，寻找既定规则下的处理节点，并将数据定向分发到特定的工作节点。这样，需要连接的数据表中具有相同分片编号的数据被分配到同一个处理节点上进行处理，这既减少了分布式系统中的文件传输，又提高了归并和排序的效率。同时，本发明提供了基于动态连接查询算法的缓存机制，可以大大提升查询效率。

根据本发明的一个方面，提供了一种用于分布式数据仓库的连接查询系统，包括主节点、映射工作节点和规约工作节点，其中：主节点根据数据表的大小和系统性能来计算分片大小，基于计算得到的分片大小向映射工作节点分配数据块，并且规定映射工作节点中的分片映射规则和汇总规则；映射工作节点根据分片映射规则将数据块中的查询关键字映射到相应的分片编号，并根据汇总规则把具有相同分片编号的数据传输到指定的规约工作节点；规约工作节点接收映射工作节点传输的数据，合并具有相同分片编号的数据并按照查询关键字进行连接，以获得最终的连接查询结果。

优选地，主节点包括：分片大小和数量计算单元，获取系统中每一个映射工作节点的物理资源配置信息，根据数据表的大小和所获得的物理资源配置信息来计算每一个映射工作节点所对应的分片大小以及每一个数据表所对应的分片数量；以及分片处理调度器，将每一个数据表按照相应的分片大小进行划分以传输至每一个映射工作节点，并规定每一个映射工作节点中的分片映射规则和汇总规则。

优选地，映射工作节点包括：存储单元，接收主节点传输的数据块；映射和分片处理单元，根据分片映射规则将数据块中的查询关键字映射到特定的分片编号，并把具有相同分片编号的数据存储在同一个数据集中；以及定向分发单元，根据汇总规则将各个数据集中存储的数据分别传输到指定的规约工作节点。

优选地，规约工作节点包括：规约单元，接收从映射工作节点传输来的数据，合并具有相同分片编号的数据以形成分片数据文件；表分片存储单元，存储分片数据文件；以及连接排序单元，将分片数据文件中的数据按照查询关键字进行连接和排序，以输出最终的连接查询结果。

优选地，分片映射规则包括：按照查询关键字的值区间进行分片映射，或基于查询关键字的哈希函数值进行分片映射。

优选地，映射工作节点的物理资源配置信息包括映射工作节点的空闲内存容量。

优选地，分片大小和数量计算单元计算每一个映射工作节点的空闲内存容量与映射任务个数的商，把计算得到的商与该映射工作节点的虚拟机内存上限值进行比较，取两者中的较小值作为该映射工作节点所对应的分片大小。

优选地，规约工作节点还包括：全局分片索引单元，针对特定的查询关键字建立全局索引表，该全局索引表包括分片编号、对应的分片存储节点、数据表名称和分片数据文件的路径。当再次查询已经建立了全局索引表的查询关键字时，访问全局索引表，直接加载相应的分片数据文件。

根据本发明的另一个方面，提供了一种用于分布式数据仓库的连接查询方法，包括：在主节点处，根据数据表的大小和系统性能来计算分片大小，基于计算得到的分片大小向映射工作节点分配数据块，并且规定映射工作节点中的分片映射规则和汇总规则；在映射工作节点处，根据分片映射规则将数据块中的查询关键字映射到相应的分片编号，并根据汇总规则把具有相同分片编号的数据传输到指定的规约工作节点；在规约工作节点处，接收映射工作节点传输的数据，合并具有相同分片编号的数据并按照查询关键字进行连接，以获得最终的连接查询结果。

优选地，在主节点处执行的步骤包括：获取系统中每一个映射工作节点的物理资源配置信息，根据数据表的大小和所获得的物理资源配置信息来计算每一个映射工作节点所对应的分片大小以及每一个数据表所对应的分片数量；以及将每一个数据表按照相应的分片大小进行划分以传输至每一个映射工作节点，并规定每一个映射工作节点中的分片映射规则和汇总规则。

优选地，在映射工作节点处执行的步骤包括：接收主节点传输的数据块；根据分片映射规则将数据块中的查询关键字映射到特定的分片编号，并把具有相同分片编号的数据存储在同一个数据集中；以及根据汇总规则将各个数据集中存储的数据分别传输到指定的规约工作节点。

优选地，在规约工作节点处执行的步骤包括：接收从映射工作节点传输来的数据，合并具有相同分片编号的数据以形成分片数据文件；存储分片数据文件；以及将分片数据文件中的数据按照查询关键字进行连接和排序，以输出最终的连接查询结果。

优选地，分片映射规则包括：按照查询关键字的值区间进行分片映射，或基于查询关键字的哈希函数值进行分片映射。

优选地，映射工作节点的物理资源配置信息包括映射工作节点的空闲内存容量。

优选地，在主节点处，计算每一个映射工作节点的空闲内存容量与映射任务个数的商，把计算得到的商与该映射工作节点的虚拟机内存上限值进行比较，取两者中的较小值作为该映射工作节点所对应的分片大小。

优选地，在规约工作节点处还执行以下步骤：针对特定的查询关键字建立全局索引表，该全局索引表包括分片编号、对应的分片存储节点、数据表名称和分片数据文件的路径。当再次查询已经建立了全局索引表的查询关键字时，通过访问全局索引表，直接加载相应的分片数据文件。

本发明基于分布式文件系统，考虑到集群中计算节点的计算能力，采用数据分片、定向分发的方式进行数据连接查询处理，减少了数据在分布式系统内部的传输，降低了冗余数据带来的排序和连接成本，提升了集群系统的资源利用率，从而有效地提高了分布式数据仓库的性能。此外，本发明在执行定向分发、分片处理时，还可以建立全局索引，这能够提升后续的连接查询的效率。

附图说明

通过下文结合附图的详细描述，本发明的上述和其它特征将会变得更加明显，其中：

图1示出了根据现有技术的分布式计算系统中采用的映射/规约(Map/Reduce)计算模型的示意图；

图2示出了根据现有技术的用于分布式系统中的连接查询过程系统的框图；

图3示出了根据本发明一个实施例的用于分布式数据仓库的分片连接查询系统的框图；

图4示出了根据本发明另一个实施例的用于分布式数据仓库的分片连接查询系统的框图；

图5是示出了根据本发明一个实施例的全局索引表的示例的示意图；

图6是示出了根据本发明一个实施例的用于分布式数据仓库的分片连接查询方法的流程图；以及

图7是示出了根据本发明另一个实施例的用于分布式数据仓库的分片连接查询方法的流程图。

具体实施方式

下面，通过结合附图对本发明的具体实施例的描述，本发明的原理和实现将会变得明显。应当注意的是，本发明不应局限于下文所述的具体实施例。另外，为了简便起见，省略了对公知元件的详细描述。

图3示出了根据本发明一个实施例的用于分布式数据仓库的分片连接查询系统的框图。作为示例，在图3中示出了1个主节点50、3个映射工作节点60和2个规约工作节点70，并且附图中相同的标记表示相同的元件。然而应当理解的是，本发明可以应用于包括任意多个映射工作节点和任意多个规约工作节点的分布式系统中。一般来说，映射工作节点的个数要大于规约工作节点的个数。

具体地，图3所示系统的输入是并行系统中的数据表和特定的关键字(连接字段)。位于主节点50中的分片大小和数量计算单元501接收这些数据表和关键字，根据数据表的大小和系统性能来计算分片大小以及每一个数据表所对应的分片数量。在本示例中，系统的性能可以包括每一个工作节点的空闲内存容量。下面，详细描述本发明中的分片处理。

在传统的分布式计算系统中，输入数据在主节点处被分割成不同的数据块，不同的数据块在不同的映射工作节点上进行映射处理，并且处理结果将会被分发到所有的规约工作节点进行处理。这个过程造成了分布式系统内的网络传输数据量巨大和规约工作节点上的数据冗余。因此，在本发明中，考虑如下参数来计算分片大小和数量：

N_MapNum＝min(S_Lfile/S_split，N_mapcap)

其中，N_MapNum表示并行的映射任务的数目，S_Lfile表示数据表的大小，S_split表示一个分块的大小，N_mapcap表示映射/规约框架中所设定的映射任务的最大数目。当大文件的数据大小超过一定数值后，多个映射任务将在一个计算节点上并发地执行，映射/规约框架要求映射任务的平均数应当与数据大小除以分块大小的值相等。

同时，单个计算节点上的任务数，还受限于单机的硬件环境。在单个工作节点上，为了并发地将分片放入内存中，必须保证分片的大小与分片数的乘积小于机器的物理内存容量。即：

N_{MapNumPerNode}×S_parition≤S_memory

同时，在映射任务中，每个任务对应的进程还有内存堆上限。因此，分片大小不能大于映射进程的内存大小限制：

S_parition≤M_cap

其中，M_cap表示每个映射任务的内存上限值，这个上限值与采用的计算容器有关。例如，java运行环境中的java虚拟机运行时存在的内存上限值。

因此，分片大小可以由以下等式获得：

S_parition＝min(S_memory/N_{MapNumPerNode}，M_cap)

相应地，每一个数据表所对应的分片数量是该数据表的大小除以分片大小后得到的数值。

考虑到上述约束，分片大小和数量计算单元501获取各个节点的物理资源配置信息，计算S_parition＝min(S_memory/N_{MapNumPerNode}，M_cap)，以形成包括<节点编号，S_partion>数据对的信息表，并将该信息表保存到分布式系统中，以供主节点和各个工作节点在需要的时候访问。

分片处理调度器502负责将各个数据表按照指定的分片大小进行分割，并将分割后的数据块分发到每一个映射工作节点60。具体地，分片处理调度器502访问包括<节点编号，S_partion>数据对的信息表，获取与某个特定的工作节点相对应的分片大小，并相应地分割N_{MapNumPerNode}个分片的数据给该工作节点。另外，分片处理调度器502还规定了每一个映射工作节点60中的数据块的分片映射规则和汇总规则(即，每片数据汇总时所对应的规约工作节点)。分片映射规则可以是区间分片(即，按照查询关键字的取值区间进行分片映射)，也可以是基于哈希算法的分片(即，按照查询关键字的哈希函数值进行分片映射)。

映射工作节点60中的存储单元601从主节点50的分片处理调度器502接收所分配的特定数据块。然后，映射和分片处理单元602对查询关键字进行映射。具体地，在执行映射时，映射和分片处理单元602根据分片处理调度器502所规定的分片映射规则，将关键字值映射到某个分片编号，并把具有相同分片编号的数据存储在同一个数据集中。

映射工作节点60中的定向分发单元603将不同分片编号所对应的数据集分发到指定的规约工作节点。其中，根据分片处理调度器502中的规定，每一个分片编号所对应的数据只被传输到指定的规约工作节点。由此，极大地降低了分布式系统内的网络传输数据量，并降低了规约工作节点上的数据冗余。

规约工作节点70中的规约单元701接收相应的映射工作节点所传输的数据，合并具有相同分片编号的数据以形成分片数据文件。之后，规约工作节点70中的表分片存储单元702存储具有相同分片编号的数据，连接排序单元703将各个分片数据文件中的数据按照指定的关键字进行连接和排序，并输出最终的查询结果。

在实际使用中，某些关键字可能经常被查询。因此，为了减少相应的查询时间，可以考虑将针对这些关键字查询得到的结果进行保存，以便下次快速查询。关于某个关键字是否属于经常被查询的关键字，可以按照系统的查询次数统计来判断。

图4示出了根据本发明另一个实施例的用于分布式数据仓库的分片连接查询系统的框图。该系统与图3中的系统的不同之处在于，规约工作节点70中还包括全局分片索引单元704。

在对某个关键字进行第一次查询后，全局分片索引单元704可以将产生的分片编号、对应的分片存储节点、数据表名称和分片文件路径建立索引，并将建立好的全局索引表存储在分布式系统中。例如，图5示出了由全局分片索引单元建立的全局索引表的一个示例。

这样，当再次执行对已经查询过的关键字的查询时，主节点50在分配映射任务时不再向各个映射工作节点60分发数据块，而是利用索引表中的各个分片索引，这样可以从分布式系统中直接加载相应的数据文件。因此，根据该实施例的查询系统能够减少针对经常被查询的关键字的查询时间，从而提升了系统的性能。

图6是示出了根据本发明一个实施例的用于分布式数据仓库的分片连接查询方法的流程图。该方法在步骤S1000处开始。

在步骤S1100，分布式系统中的主节点根据系统的性能(例如系统中的工作节点的空闲内存容量)和数据表的大小，计算分片大小和分片数量。根据计算得到的分片大小和数量，向工作节点分配映射任务。同时，主节点还规定了映射工作节点中的数据块的分片映射规则和汇总规则。

在步骤S1200，映射工作节点按照主节点中所规定的分片映射规则(例如区间分片或基于哈希算法的分片)，将关键字值映射到某个分片编号，并把具有相同分片编号的数据存储在同一个数据集中。

在步骤S1300，映射工作节点将不同分片编号所对应的数据集分发到指定的规约工作节点。其中，每一个分片编号所对应的数据只被传输到指定的规约工作节点。

在步骤S1400，规约工作节点接收相应的映射工作节点所传输的数据，合并具有相同分片编号的数据以形成分片数据文件。之后，规约工作节点将各个分片数据文件中的数据按照指定的关键字进行连接和排序，并输出最终的连接查询结果。最后，方法在步骤S1500结束。

图7是示出了根据本发明另一个实施例的用于分布式数据仓库的分片连接查询方法的流程图。其中，图7中的步骤S2100-S2400分别与图6中的步骤S1100-1400相同，此处不再赘述。另外，图7还包括步骤S2010、S2020和S2410。在实际使用中，某些关键字可能经常被查询。因此，为了减少相应的查询时间，可以考虑将针对这些关键字查询得到的结果进行保存，以便下次快速查询。针对于此，在步骤S2400之后的步骤S2410处，规约工作节点可以将针对经常查询的关键字产生的分片编号、对应的分片存储节点、数据表名称和分片文件路径建立索引，并将建立好的全局索引表存储在分布式系统中。这样，每当执行图7所示的方法时，在开始步骤S2000后先执行步骤S2010，判断所查询的关键字是否是经常查询的关键字。如果不是，则方法继续进行到步骤S2100，按照上文所述的过程进行连接查询。否则，方法直接进行到步骤S2020，在该步骤，访问先前生成的全局索引表，直接加载针对该关键字已经生成的查询数据文件。这样，能够减少针对经常被查询的关键字的查询时间。

本发明提供的方法和系统基于分布式文件系统，充分考虑到海量数据的分布式存储特征，通过使用最优分片和定向传输，使键值区间相同(或哈希函数的结果相同)的分片数据在同一个规约工作节点上进行数据连接处理，减少了数据在分布式系统内部的传输，从而提升了查询效率。同时，本发明还可以将使用过的分片记录保存在系统缓存中，使得后续的查询具有极高的效率。

本发明的方法和系统支持各种不同的数据格式，支持不同数量级的数据文件和数据表，在分布式数据仓库中具有广泛的应用价值。

另外，本发明提出的分布式环境下的分片连接查询方案在应用于并行关系数据库时更为有利。这是因为，并行关系数据库一般部署在高速局域网内，而且各个数据库服务器节点的性能相当。在这样的物理环境下，根据本发明的分片连接查询方案能够更加高效地执行。

尽管以上已经结合本发明的优选实施例示出了本发明，但是本领域的技术人员将会理解，在不脱离本发明的精神和范围的情况下，可以对本发明进行各种修改、替换和改变。因此，本发明不应由上述实施例米限定，而应由所附权利要求及其等价物来限定。

Claims (16)

1.一种用于分布式数据仓库的连接查询系统，包括主节点、映射工作节点和规约工作节点，其中：

主节点包括：

分片大小和数量计算单元，获取系统中每一个映射工作节点的物理资源配置信息，根据数据表的大小和所获得的物理资源配置信息来计算每一个映射工作节点所对应的分片大小以及每一个数据表所对应的分片数量；以及

分片处理调度器，将每一个数据表按照相应的分片大小进行划分以传输至每一个映射工作节点，并规定每一个映射工作节点中的分片映射规则和汇总规则；

映射工作节点根据分片映射规则将数据块中的查询关键字映射到相应的分片编号，并根据汇总规则把具有相同分片编号的数据传输到指定的规约工作节点；以及

规约工作节点接收映射工作节点传输的数据，合并具有相同分片编号的数据并按照查询关键字进行连接，以获得最终的连接查询结果；

其中，映射工作节点的物理资源配置信息包括映射工作节点的空闲内存容量，分片大小和数量计算单元计算每一个映射工作节点的空闲内存容量与映射任务个数的商，把计算得到的商与该映射工作节点的虚拟机内存上限值进行比较，取两者中的较小值作为该映射工作节点所对应的分片大小。

2.根据权利要求1所述的用于分布式数据仓库的连接查询系统，其中，映射工作节点包括：

存储单元，接收主节点传输的数据块；

映射和分片处理单元，根据分片映射规则将数据块中的查询关键字映射到特定的分片编号，并把具有相同分片编号的数据存储在同一个数据集中；以及

定向分发单元，根据汇总规则将各个数据集中存储的数据分别传输到指定的规约工作节点。

3.根据权利要求1所述的用于分布式数据仓库的连接查询系统，其中，规约工作节点包括：

规约单元，接收从映射工作节点传输来的数据，合并具有相同分片编号的数据以形成分片数据文件；

表分片存储单元，存储分片数据文件；以及

连接排序单元，将分片数据文件中的数据按照查询关键字进行连接和排序，以输出最终的连接查询结果。

4.根据权利要求1所述的用于分布式数据仓库的连接查询系统，其中，分片映射规则包括按照查询关键字的值区间进行分片映射。

5.根据权利要求1所述的用于分布式数据仓库的连接查询系统，其中，分片映射规则包括基于查询关键字的哈希函数值进行分片映射。

6.根据权利要求3所述的用于分布式数据仓库的连接查询系统，其中，规约工作节点还包括：

全局分片索引单元，针对特定的查询关键字建立全局索引表，该全局索引表包括分片编号、对应的分片存储节点、数据表名称和分片数据文件的路径。

7.根据权利要求6所述的用于分布式数据仓库的连接查询系统，其中，当再次查询已经建立了全局索引表的查询关键字时，访问全局索引表，直接加载相应的分片数据文件。

8.根据权利要求1-7中任意一项所述的用于分布式数据仓库的连接查询系统，其中，所述分布式数据仓库包括并行关系数据库。

9.一种用于分布式数据仓库的连接查询方法，包括：

在主节点处，获取系统中每一个映射工作节点的物理资源配置信息，根据数据表的大小和所获得的物理资源配置信息来计算每一个映射工作节点所对应的分片大小以及每一个数据表所对应的分片数量，以及将每一个数据表按照相应的分片大小进行划分以传输至每一个映射工作节点，并规定每一个映射工作节点中的分片映射规则和汇总规则；

在映射工作节点处，根据分片映射规则将数据块中的查询关键字映射到相应的分片编号，并根据汇总规则把具有相同分片编号的数据传输到指定的规约工作节点；

在规约工作节点处，接收映射工作节点传输的数据，合并具有相同分片编号的数据并按照查询关键字进行连接，以获得最终的连接查询结果；

其中，映射工作节点的物理资源配置信息包括映射工作节点的空闲内存容量，在主节点处，计算每一个映射工作节点的空闲内存容量与映射任务个数的商，把计算得到的商与该映射工作节点的虚拟机内存上限值进行比较，取两者中的较小值作为该映射工作节点所对应的分片大小。

10.根据权利要求9所述的用于分布式数据仓库的连接查询方法，其中，在映射工作节点处执行的步骤包括：

接收主节点传输的数据块；

根据分片映射规则将数据块中的查询关键字映射到特定的分片编

号，并把具有相同分片编号的数据存储在同一个数据集中；以及

根据汇总规则将各个数据集中存储的数据分别传输到指定的规约工作节点。

11.根据权利要求9所述的用于分布式数据仓库的连接查询方法，其中，在规约工作节点处执行的步骤包括：

接收从映射工作节点传输来的数据，合并具有相同分片编号的数据以形成分片数据文件；

存储分片数据文件；以及

将分片数据文件中的数据按照查询关键字进行连接和排序，以输出最终的连接查询结果。

12.根据权利要求9所述的用于分布式数据仓库的连接查询方法，其中，分片映射规则包括按照查询关键字的值区间进行分片映射。

13.根据权利要求9所述的用于分布式数据仓库的连接查询方法，其中，分片映射规则包括基于查询关键字的哈希函数值进行分片映射。

14.根据权利要求11所述的用于分布式数据仓库的连接查询方法，其中，在规约工作节点处还执行以下步骤：

针对特定的查询关键字建立全局索引表，该全局索引表包括分片编号、对应的分片存储节点、数据表名称和分片数据文件的路径。

15.根据权利要求14所述的用于分布式数据仓库的连接查询方法，其中，当再次查询已经建立了全局索引表的查询关键字时，通过访问全局索引表，直接加载相应的分片数据文件。

16.根据权利要求9-15中任意一项所述的用于分布式数据仓库的连接查询方法，其中，所述分布式数据仓库包括并行关系数据库。

Images