分布式内存列式数据库的索引建立方法

摘要

本发明公开了一种分布式内存列式数据库的索引建立方法，包括：将单列数据切分为至少两个数据分片；并行计算每个数据分片的列式压缩索引的中间数据和行表向量的中间数据，所述列式压缩索引包括字典向量、索引向量以及位置向量；按序存储并更新每个数据分片的列式压缩索引的中间数据和行表向量的中间数据，以形成列式压缩索引和行表向量。本发明提供的分布式内存列式数据库的索引建立方法，对于巨表的导入计算节点并不需要多大的内存，可以节约硬件成本。

说明书

技术领域

本发明涉及数据库技术领域，具体涉及一种分布式内存列式数据库的索引建立方法。

背景技术

Groupkey索引，即列式压缩索引，是一种在分布式内存列式数据库中的数据组织方式，其采用字典压缩对每列内容进行压缩，采用索引（index）向量对字典向量中某个值对应的行数进行索引，采用位置（position）向量存储字典向量对应的行号（rowid）。同时，有一个行表（rowtable）向量维持行关系，里面存储的是元素值在字典向量中的下标。为分布式内存列式数据库建立Groupkey索引的传统方法为：将数据从数据源中读入内存；对读入内存中的数据进行排序处理并去重，生成字典向量；根据排序后的字典向量建立索引向量、位置向量和行表向量；将字典向量、索引向量、位置向量以及行表向量发送给存储节点，Groupkey索引建立完成。

由于需要将所有数据读入内存后开始排序，现有最快的快速排序算法的时间复杂度也是O（NlogN）。另一方面，在Groupkey索引的建立过程中，向量是没有进行位压缩的。以一个2^30行（约10亿行）的double类型为列，字典压缩后的数据大小是原始数据大小的μ倍（0＜μ≤1）。原始数据大小为：2^30×8byte；字典向量所占用的内存大小为：μ×2^30×8byte；索引向量所占用的内存大小为：μ×2^30×8byte；位置向量所占用的内存大小为：2^30×8byte；行表向量所占用的内存大小为：2^30×8byte。总共耗费的内存至少为：（16μ+24）Gb，而原始数据大小为：8Gb，导入的内存倍数为：2μ+3倍。如果μ为1（也就是说原始数据中数据没有重复），内存的消耗是原始数据大小的5倍。

并且，上述计算是基于采用STL中的vector形式存储数据。采用vector形式存储数据，内存需要是连续的才能够分配成功，因而需要更加大的内存。如果不采用vector形式存储数据，采用链表等其他形式还会有指针开销，此时的内存消耗会更大。综上所述，采用传统方式建立Groupkey索引无论在时间上还是空间上都存在瓶颈，对于巨表的导入无能为力。其中，巨表为单列大小超过节点内存的表。

为了缩短建立Groupkey索引的时间，现有技术中采用多线程排序。该方法利用多核可以显著提高字典排序的速度，然而内存消耗大的问题依然无法解决。

发明内容

本发明所要解决的是建立分布式内存列式数据库的Groupkey索引内存消耗大的问题。

本发明通过下述技术方案实现：

一种分布式内存列式数据库的索引建立方法，包括：将单列数据切分为至少两个数据分片；并行计算每个数据分片的列式压缩索引的中间数据和行表向量的中间数据，所述列式压缩索引包括字典向量、索引向量以及位置向量；按序存储并更新每个数据分片的列式压缩索引的中间数据和行表向量的中间数据，以形成列式压缩索引和行表向量。

本发明采用分布式并行导入思想，一方面，并行计算每个数据分片的列式压缩索引的中间数据和行表向量的中间数据保证了计算列式压缩索引和行表向量的效率；另一方面，每个数据分片的列式压缩索引的中间数据和行表向量的中间数据由不同的计算节点进行计算，也就是说每个计算节点只会拿到列数据中的一个数据分片，因而计算节点并不需要装下整个列数据，能够实现在计算节点内存较小的情况下，依然能够对任意巨表的导入以及快速建立索引。进一步，本发明采用分布式集群架构具有拓展性，只需要通过增加计算节点的个数，就可提升导入性能。

可选的，所述分布式内存列式数据库包括域控制器、读取组件、存储节点、主数据服务器以及至少两个从数据服务器。

可选的，将单列数据切分为至少两个数据分片包括：域控制器下发列数据导入任务至主数据服务器；主数据服务器将列数据导入任务切分成子任务后下发给各个从数据服务器，子任务和从数据服务器一一对应；各个从数据服务器根据子任务向读取组件下发导入任务；读取组件根据导入任务向各个从数据服务器上传数据分片。

可选的，主数据服务器根据各个从数据服务器报告的内存大小下发子任务。通过内存大小下发子任务，内存较大的从数据服务器计算的数据分片更大，能够合理分配系统资源。

可选的，并行计算每个数据分片的列式压缩索引的中间数据和行表向量的中间数据包括：各个从数据服务器并行计算其自身对应的数据分片的列式压缩索引的中间数据和行表向量的中间数据。

可选的，按序存储并更新每个数据分片的列式压缩索引的中间数据和行表向量的中间数据包括：从数据服务器计算列式压缩索引的中间数据和行表向量的中间数据完成后，向主数据服务器发送准备就绪信号；若主数据服务器为首次接收准备就绪信号，则执行第一步骤，否则执行第二步骤，其中，第一步骤包括：主数据服务器向从数据服务器下发分片任务；从数据服务器对列式压缩索引的中间数据进行切分以形成索引分片，并将索引分片和行表向量的中间数据导入存储节点；导入完成后存储节点向从数据服务器发送确认消息；第二步骤包括：主数据服务器向从数据服务器下发分片任务和上一次分片结果；从数据服务器根据上一次分片结果对列式压缩索引的中间数据进行切分以形成索引分片，并将索引分片和行表向量的中间数据导入存储节点；存储节点将字典向量新增元素个数、已导入的字典向量的偏移量以及新导入的字典向量的偏移量告知从数据服务器；从数据服务器根据字典向量新增元素个数、已导入的字典向量的偏移量以及新导入的字典向量的偏移量更新全局字典向量的起始下标和行表向量；更新完成后存储节点向从数据服务器发送确认消息；从数据服务器在接收到所有存储节点发送的确认消息后，向主数据服务器汇报当前数据分片导入完成；若当前数据分片为最后导入的数据分片，则列数据导入完成，否则重复执行第二步骤。

对列式压缩索引的中间数据进行切分后，可以将一个大的列式压缩索引的中间数据散列到底层的分布式存储节点中。从存储硬件条件出发，在大规模数据库中，一个存储节点将不能够全部装下整个列的索引，通过将列式压缩索引的中间数据散列，可以通过简单的增加机器的方法，放下更大的表；从查询效率出发，将列式压缩索引的中间数据进行切分，可以充分利用存储节点的CPU核数，让一个线程计算一个索引分片，提高并行度。另一方面，从数据服务器根据上一次分片结果对列式压缩索引的中间数据进行切分，可以维持列式压缩索引的中间数据在建立好后依然是有序的，同一个区间范围内的数据依然能够落在一个区间范围内，避免字典向量中的会出现交叠。

可选的，所述存储节点包括行表存储节点和至少一个索引存储节点；索引存储节点用于存储索引分片；行表存储节点用于存储行表向量的中间数据。

可选的，所述上一次分片结果包括上一个列式压缩索引的中间数据对应的存储节点地址、索引分片上界以及索引分片下界。

可选的，在第二步骤中，从数据服务器将落在同一个区间内的字典向量中的元素切分在同一个索引分片。

可选的，更新全局字典向量的起始下标包括：叠加当前索引分片之前所有索引分片的字典向量新增元素个数以获得当前索引分片对应于全局字典向量的起始下标，第一个索引分片对应于全局字典向量的起始下标为0；

更新行表向量包括：将每个索引分片已导入的字典向量的偏移量中每个元素加上上一个索引分片字典向量新增元素个数，并拼接所有索引分片已导入的字典向量的偏移量以获得全局已导入的字典向量的偏移量；将每个索引分片新导入的字典向量的偏移量中每个元素加上上一个索引分片字典向量新增元素个数，并拼接所有索引分片新导入的字典向量的偏移量以获得全局新导入的字典向量的偏移量；将从数据服务器中行表向量的第i位元素与全局新导入的字典向量的偏移量的第rowtable[i]位元素相加以获得第一更新行表向量，其中，i为自然数，rowtable[i]为从数据服务器中行表向量的第i位元素的值；从数据服务器将全局已导入的字典向量的偏移量和第一更新行表向量发送至存储节点；将存储节点中行表向量的第j位元素与全局已导入的字典向量的偏移量的第rowtable[j]位元素相加以获得第二更新行表向量，其中，j为自然数，rowtable[j]为存储节点中行表向量的第j位元素的值；将第一更新行表向量追加到第二更新行表向量之后。

本发明与现有技术相比，具有如下的优点和有益效果：

本发明提供的分布式内存列式数据库的索引建立方法，将列数据切分后再进行导入，因而对于巨表的导入计算节点并不需要多大的内存，可以节约硬件成本。计算列式压缩索引的中间数据和行表向量的中间数据过程采用并行方式处理，显著提高了列数据导入和索引建立效率。进一步，各个计算节点相互独立，通过简单增加计算节点就可以提高列数据导入能力，满足不断扩展的业务需求。

附图说明

此处所说明的附图用来提供对本发明实施例的进一步理解，构成本申请的一部分，并不构成对本发明实施例的限定。在附图中：

图1是本发明实施例涉及的分布式内存列式数据库的结构示意图；

图2是本发明实施例各个从数据服务器并行建立Groupkey索引的中间数据的示意图；

图3是本发明实施例首个从数据服务器进行分片的示意图；

图4是本发明实施例非首个从数据服务器进行分片的示意图；

图5是本发明实施例从数据服务器对字典向量、索引向量以及位置向量进行更新的示意图；

图6是本发明实施例对行表向量进行更新的示意图；

图7是本发明实施例进行分片后的最终结果示意图。

具体实施方式

Groupkey索引建立过程中最耗费时间的是建立字典向量的过程，而建立字典向量的过程实际上是一个排序和去重的过程。如果将整个列数据都导入到内存中后再建立字典向量将需要大量内存，且排序的过程会浪费太多时间，其时间复杂度是O（logN）。对于传统Groupkey索引的使用来说，Groupkey的更新主要用于有新的数据到来后才启用。Groupkey索引的建立过程是O（logN）时间复杂度，而更新流程是O（N）时间复杂度。

基于此，本发明提供一种分布式内存列式数据库的索引建立方法，将需要导入的巨表进行切分，分别在不同的计算节点上面进行Groupkey索引的建立，也就是将O（logN）复杂度的过程并行处理，最后将计算好的Groupkey索引再进行更新操作。使导入性能成倍增长，需要的内存成倍缩减。

所述分布式内存列式数据库的索引建立方法，包括：

步骤S1，将单列数据切分为至少两个数据分片；

步骤S2，并行计算每个数据分片的列式压缩索引的中间数据和行表向量的中间数据，所述列式压缩索引包括字典向量、索引向量以及位置向量；

步骤S3，按序存储并更新每个数据分片的列式压缩索引的中间数据和行表向量的中间数据，以形成列式压缩索引和行表向量。

为使本发明的目的、技术方案和优点更加清楚明白，下面结合实施例和附图，对本发明作进一步的详细说明，本发明的示意性实施方式及其说明仅用于解释本发明，并不作为对本发明的限定。

实施例

图1是本实施例涉及的分布式内存列式数据库的结构示意图，所述分布式内存列式数据库包括域控制器DC（Domain Controller）、索引服务器IS（Index Server）、数据导入管理模块IM（Import Manager）、内存数据库引擎MDE（In Memory Database Engine）、存储节点CS（Column Store）、数据导入系统DIS（Data Import System）、数据服务器DS以及读取组件RA（Replication Agent）。其中，域控制器DC负责对数据服务器DS下发数据导入任务；存储节点CS为内存数据库引擎中存储数据的服务节点，负责存储数据和对上层提供查询的功能，其包括行表存储节点rowtableCS和至少一个索引存储节点columnCS；数据服务器DS为数据导入系统DIS中的数据导入模块，负责将源数据导入内存数据库引擎MDE中，其包括主数据服务器和至少一个从数据服务器；读取组件RA为数据库访问的接口，用于外部数据源的适配与数据的读取，与Oracle数据库在同一节点上；索引服务器IS为内存数据库引擎MDE的控制节点；数据导入管理模块IM用于负责管理源数据导入整个流程。

如步骤S1所述，将单列数据切分为至少两个数据分片。具体地，域控制器DC下发列数据导入任务至主数据服务器；主数据服务器将列数据导入任务切分成子任务后下发给各个从数据服务器，每个子任务为导入一个数据分片且子任务和从数据服务器一一对应，即给每个从数据服务器下发一个子任务，在本实施例中，主数据服务器根据各个从数据服务器报告的内存大小下发子任务，内存越大的从数据服务器获得的子任务所需内存越大，如此能够合理分配系统资源；各个从数据服务器根据子任务向读取组件RA下发导入任务；读取组件RA根据导入任务向各个从数据服务器上传数据分片。

如步骤S2所述，并行计算每个数据分片的列式压缩索引的中间数据和行表向量的中间数据，所述列式压缩索引包括字典向量、索引向量以及位置向量。各个从数据服务器并行计算其自身对应的数据分片的列式压缩索引的中间数据和行表向量的中间数据，即同时计算每个数据分片的Groupkey向量和行表向量。

如步骤S3所述，按序存储并更新每个数据分片的列式压缩索引的中间数据和行表向量的中间数据，以形成列式压缩索引和行表向量。具体地，从数据服务器计算列式压缩索引的中间数据和行表向量的中间数据完成后，就向主数据服务器发送准备就绪信号。若主数据服务器为首次接收准备就绪信号，即发送准备就绪信号的从数据服务器是第一个向主数据服务器发送的，则执行第一步骤，否则执行第二步骤。

其中，第一步骤包括：主数据服务器向从数据服务器下发分片任务；从数据服务器对列式压缩索引的中间数据进行切分以形成索引分片，即对字典向量、索引向量以及位置向量进行切分，并将索引分片和行表向量导入存储节点CS，进一步，是将索引分片导入索引存储节点columnCS，将行表向量的中间数据导入行表存储节点rowtableCS；导入完成后存储节点向从数据服务器发送确认消息ACK。

第二步骤包括：主数据服务器向从数据服务器下发分片任务和上一次分片结果，所述上一次分片结果包括上一个列式压缩索引的中间数据对应的存储节点地址、索引分片上界以及索引分片下界；从数据服务器根据上一次分片结果对列式压缩索引的中间数据进行切分以形成索引分片，并将索引分片和行表向量的中间数据导入存储节点CS，进一步，是将索引分片导入索引存储节点columnCS，将行表向量的中间数据导入行表存储节点rowtableCS；索引存储节点columnCS将字典向量新增元素个数、已导入的字典向量的偏移量以及新导入的字典向量的偏移量告知从数据服务器；从数据服务器根据字典向量新增元素个数、已导入的字典向量的偏移量以及新导入的字典向量的偏移量更新全局字典向量的起始下标和行表向量；更新完成后存储节点向从数据服务器发送确认消息ACK。进一步，在第二步骤中，从数据服务器根据上一次分片结果对列式压缩索引的中间数据进行切分，因此，每个从数据服务器在生成索引分片的同时也生成分片结果，并将分片结果告知主数据服务器。在当前从数据服务器进行分片时，主数据服务器将上一次分片结果下发给当前从数据服务器。当前从数据服务器的分片规则是，将落在同一个区间内的字典向量中的元素切分在同一个索引分片。

在第一步骤或者第二步骤完成，从数据服务器在接收到所有存储节点发送的确认消息ACK后，向主数据服务器汇报当前数据分片导入完成。若当前数据分片为最后导入的数据分片，则列数据导入完成，否则重复执行第二步骤。

以下以导入图2所示的原始数据并建立索引为例说明本实施例的具体流程，其中，UM是列式压缩索引中的字典向量，Index是列式压缩索引中的索引向量，position是列式压缩索引中的位置向量，rowtable是列式压缩索引中的行表向量。原始数据被切分为三个数据分片，第一个数据分片包括数据E、I、C、E，第二个数据分片包括数据H、I、B、Y，第三个数据分片包括数据K、J、Z。第一个数据分片由从数据服务器1负责计算，第二个数据分片由从数据服务器2负责计算，第三个数据分片由从数据服务器3负责计算。

首先，每个从数据服务器将收到的每个数据分片建立列式压缩索引的中间数据和行表向量的中间数据，这个过程是并行的，如图2所示。当一个从数据服务器建立好了列式压缩索引的中间数据和行表向量的中间数据后，将会发送准备就绪信号给主数据服务器。假如此刻是从数据服务器2，即从数据服务器2是第一个告知主从数据服务器它的列式压缩索引的中间数据和行表向量的中间数据准备就绪的从数据服务器，该从数据服务器根据自己列式压缩索引的中间数据生成分片结果，并将索引分片下发给存储节点，同时将分片结果告知主数据服务器，如图3所示。其中，索引分片1下发给索引存储节点columnCS1，索引分片2下发给索引存储节点columnCS2，行表向量下发给行表存储节点rowtableCS。分片结果为：< columnCS1，B，H>，< columnCS2，I，Y>。

数据分片2导入成功后，主数据服务器从准备就绪的从数据服务器中选择一个，向其下发数据分片2的分片结果。假设此时被选中的是从数据服务器1，则从数据服务器1根据数据分片2的分片结果将数据分片1的列式压缩索引的中间数据分片。此时的分片规则是，落在同一个区间内的字典向量中的元素切分在同一个索引分片，如图4所示。

此时，索引存储节点columnCS1和索引存储节点columnCS2都会收到索引分片的到达，索引存储节点columnCS1和索引存储节点columnCS2会根据自己原有的索引分片和新到达的索引分片，计算出每个索引分片字典向量新增元素个数expand、已导入的字典向量的偏移量main_x_vector和新导入的字典向量的偏移量delta_x_vector，并将此信息报告给从数据服务器1，如图5所示。

从数据服务器1通过接收每个索引分片字典向量新增元素个数expand计算出更新后的对应于全局字典向量的起始下标beginentry，并发送给索引存储节点columnCS1和索引存储节点columnCS2。更新后的对应于全局字典向量的起始下标beginentry的计算方式是叠加当前索引分片之前所有索引分片的字典向量新增元素个数expand以获得当前索引分片对应于全局字典向量的起始下标，第一个索引分片更新后的对应于全局字典向量的起始下标beginentry为0。同时，从数据服务器1通过接收已导入的字典向量的偏移量main_x_vector和新导入的字典向量的偏移量delta_x_vector来计算全局的已导入的字典向量的偏移量和全局的新导入的字典向量的偏移量。对于存储节点columnCS1，字典向量新增元素个数expand为两个，已导入的字典向量的偏移量main_x_vector为[0，2]，新导入的字典向量的偏移量delta_x_vector为[1，1]；对于存储节点columnCS2，字典向量新增元素个数expand为两个，已导入的字典向量的偏移量main_x_vector为[0，0]，新导入的字典向量的偏移量delta_x_vector为[0]。

计算全局已导入的字典向量的偏移量的偏移量具体过程为：将每个索引分片已导入的字典向量的偏移量main_x_vector中每个元素加上上一个索引分片字典向量新增元素个数expand（第一个索引分片除外），然后将所有索引分片已导入的字典向量的偏移量main_x_vector拼接在一起。计算全局新导入的字典向量的偏移量的偏移量具体过程为：将每个索引分片新导入的字典向量的偏移量delta_x_vector中每个元素加上上一个索引分片字典向量新增元素个数expand（第一个索引分片除外），然后将所有索引分片新导入的字典向量的偏移量delta_x_vector拼接在一起。

然后，从数据服务器1根据全局新导入的字典向量的偏移量进行行表向量的更新。更新的办法是，将从数据服务器上面的行表向量中的第i位元素rowtable[i]（i从0开始）与全局新导入的字典向量的偏移量中第rowtable[i]位元素delta_x_vector[rowtable[i]]相加，得到第一更新行表向量rowtable’中第i位元素的值rowtable’[i]，然后将全局已导入的字典向量的偏移量main_x_vector和第一更新行表向量rowtable’发送给行表存储节点rowtableCS。行表存储节点rowtableCS收到了全局已导入的字典向量的偏移向量main_x_vector和第一更新行表向量rowtable’后，将行表存储节点rowtableCS中原有的行表向量中的第j位元素rowtable[j]（j从0开始）与全局已导入的字典向量的偏移量的第rowtable[j]位元素main_x_vector [rowtable[j]]相加，得到第二更新行表向量rowtable’’中第j位元素的值rowtable’’[j]。将第一更新行表向量rowtable’追加到第二更新行表向量rowtable’’之后，行表存储节点rowtableCS上面的行表向量如图6所示。

当收到行表存储节点rowtableCS和所有索引存储节点columnCS的确认消息后，主数据服务器再选择下一个从数据服务器，此时为从数据服务器3。从数据服务器3进行和从数据服务器2相同的操作，更新完成后的列式压缩索引情况和相应的行表向量如图7所示。

以上所述的具体实施方式，对本发明的目的、技术方案和有益效果进行了进一步详细说明，所应理解的是，以上所述仅为本发明的具体实施方式而已，并不用于限定本发明的保护范围，凡在本发明的精神和原则之内，所做的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。