CN103324765B - 一种基于列存储的多核并行数据查询优化方法 - Google Patents

Abstract

本发明公开了一种基于列存储的多核并行数据查询优化方法，所述方法针对查询计划构建映射‑化简执行流程，该映射‑化简执行流程由多个子映射‑化简执行流程组成。通过各个子映射‑化简执行流程的执行，完成对数据库的查询操作。在子映射‑化简执行流程执行时，映射‑化简模型负责将各个映射任务分配给不同的核并行执行，各个核依次根据所分配的映射任务中的操作确定映射函数和化简函数的输入输出键值对，以此完成查询计划的执行。本发明很好的利用了在多核处理器上任务可并行执行的特性，缩短了大数据查询结果的返回时间，提高了数据查询的效率。

Description

一种基于列存储的多核并行数据查询优化方法

技术领域

本发明涉及计算机领域中的大数据并行计算、列存储相关架构数据存储查询领域，具体涉及一种基于列存储的多核并行数据查询优化方法，其中采用映射-化简并行编程模型实现多核环境下数据库查询任务的局部并行化。

背景技术

数据查询是指将经过选择、整理和评价的数据存入数据库中，并从数据库中查询出能满足用户需求的准确数据的过程和技术，是数据库系统的核心问题之一。随着互联网技术的发展，数据正在以令人难以想象的速度增长。面对这些大数据，如何对数据查询进行优化，提高数据库的查询效率，是数据库领域的一个重要研究方向。

国内外学者在此方面做了很多的研究，这些研究主要可以分为两类：分布式并行数据库查询优化技术和列存储数据库查询优化技术。

分布式并行数据库查询优化技术通过任务的分布式并行执行缩短响应时间，提高查询效率。该方法根据执行方式的不同又可细分为两类：一阶段并行查询优化方法和两阶段并行查询优化方法；一阶段方法可直接产生最优的并行执行计划，目前提出的一阶段方法大多数都是近似的或启发式的；在两阶段并行查询优化方法中，第一阶段使用传统的基于代价的查询优化方法产生高效率的顺序查询执行计划，第二阶段并行化第一阶段产生的查询执行计划，在一定的条件下，第一阶段产生的顺序查询执行计划也能保证并行化后有很好的性能。

列存储数据库查询优化技术通过改变数据库的物理存储层来实现查询效率的提高。它与传统的行存储数据库的区别在于列存储数据库中的表格是以列为单位进行存储的。这样一来，在执行查询计划时，只需读取与查询相关的列，不需要把数据库的整条记录的数据都加载到内存中，从而大大减少了磁盘和网络I/O的负载。同时，由于同列的数据不仅具有相同的数据结构，而且数据的重复性机率也将更大，因此这一存储结构更适合于对数据进行压缩。压缩态数据在减少存储成本的同时，也为查询效率的提高提供了极大的优势。这一优势主要体现在：压缩态数据可包含更多的信息量，在每次读取数据时，可获得更多的数据，而每次读取操作获取更多的数据则意味着更快的查询处理速度，更短的响应时间。

然而这些研究还存在着一定的问题：分布式并行数据查询优化技术利用分布式系统架构，提高了并行查询的效率，但是该架构的缺点也造成此方法容易受个别坏节点的影响，从而影响最后的输出结果；列存储数据查询优化技术通过改变数据的物理存储层使得查询效率得以提高，但是在查询优化阶段，并未过多的考虑查询任务的并行执行，以使得计算机硬件资源得到充分利用。因此，如何利用列存储本身的特性最大化查询任务的并行执行，成为目前急需解决的任务。

发明内容

鉴于现有技术的不足，本发明的目的是克服上述两种查询方法的缺陷，采用多核处理器，利用列存储技术和基于映射-化简模型的单CPU多核处理器并行技术，动态地将查询涉及的数据列加载到内存，并使用MR模型将查询操作分配到处理器的多个核上并行运行，缩短了大数据查询结果的返回时间，提高了数据查询的效率。

需要说明的是，映射-化简模型(MapReduce)是由Dean et.al.提出的一种编程模型，可用于大规模数据集（大于1TB）的并行运算，并成功地应用于Google的各种应用中。它提供了简单的编程接口使得程序能自动地以并行的方式运行在大量的机器中，而不需要考虑并行、容错、优化和负载均衡等问题。该模型以键值(Key/value)对的方式处理数据，并将计算任务分成了映射和化简两个阶段。通过在运行时动态地对节点进行任务分配，分阶段的处理方式以及定期创建检查点和重做失败的任务，MR框架能够很好的应对任务失败和节点出错，具有很强的容错能力，本发明即采用MR模型将查询操作分配到多个核上并行运行并用键值对存储计算结果。

尽管MR模型的优点众多且功能强大，但现阶段仍主要应用于大规模集群下。随着微型和小型计算机CPU主频的提高及多核、多处理器、多线程技术的不断发展，单个计算机的计算能力已经不容小视。将微型或小型计算机上单个处理器上的多个核或者多个处理器看成一个集群，通过内存共享的方式来模拟作为集群间通信的媒介网络的方法，同样可以将MR模型运用于微型或小型计算机上解决大数据计算问题，这就是本发明使用的基于映射化简的单CPU多核并行技术。

通过映射化简框架实现多核处理器环境下的列存储数据库中的数据查询的局部并行执行，以达到数据查询优化的目的。

为了实现上述目的，本发明采用的技术方案如下：

一种基于列存储的多核并行数据查询优化方法，所述方法包括以下步骤：

（1）读取用户输入的查询语句；

（2）生成查询计划，其中，对所述用户输入的查询语句，利用延时物化策略生成针对该查询语句的查询计划，所述查询计划可用图的形式来表示；

（3）构建对应所述查询计划的映射-化简执行流程，根据所述查询计划图，利用映射-化简模型中的映射阶段和化简阶段的交叉使用构建基于图中操作节点的映射-化简执行流程，其中，一个映射-化简执行流程中可能包含一个或多个子映射-化简执行流程，而在子映射-化简执行流程中只包含一个映射阶段与一个化简阶段；

（4）按照映射-化简执行流程完成所述查询计划的执行，依次执行映射-化简执行流程中的各个子映射-化简执行流程；

（5）向所述用户输出查询结果。

需要说明的是，所述步骤（3）包括以下步骤：

（1）将所述查询计划划分成多个串行执行的子查询计划，构成子查询计划序列：

(plan₁,plan₂,plan₃,...,plan_m)；

其中，在某一操作符之前可并行执行的多个单独操作符或操作符集合作为一个子查询计划存在；

（2）遍历子查询计划序列，若某个子查询计划plan_p的执行是以子查询计划plan_q的执行为前提的，并且在plan_q中存在着多于一个的可并行执行的操作符，则将plan_p和plan_q合并为一个子映射-化简执行流程，同时，将plan_q标记为映射，将plan_p标记为化简；

需要说明的是，所述步骤（4）包括如下步骤：

（1）统计映射-化简执行流程队列中子映射-化简执行流程的个数，将其标记为count；

（2）遍历映射-化简执行流程队列中的各个子映射-化简执行流程；

（2.1）令k＝1；

（2.2）当k≤count时，读取映射-化简执行流程队列中第k个子映射-化简执行流程，通过对该子映射-化简执行流程中子查询计划的分析，确定在此子映射-化简执行流程中三个键值对的具体数据结构；

（2.3）依次执行如下的映射阶段与化简阶段，其中各阶段的具体执行过程如下:

映射阶段，读取该子流程中标记为映射的子查询计划，将该子查询计划中的多个并行操作分配给处于空闲状态的核；由这些核并行完成子查询计划中的多个操作；

化简阶段，读取该子流程中标记为化简的子查询计划，并从中间结果集中读取相关数据，完成该子查询计划中的操作；

（2.4）至k++，返回步骤（2.2）。

需要进一步说明的是，所述三个键值对分别为，映射函数的输入键值对、映射函数的输出键值对和化简函数的输入键值对，其中，各键值对的结构为由键key和其相对应的值value构成的键值对。

本发明有益效果在于，很好的利用了在多核处理器上任务可并行执行的特性，通过映射-化简模型实现多核环境下列存储数据库中查询任务的局部并行化，缩短了大数据查询结果的返回时间，提高了数据查询的效率。

附图说明

图1为本发明的运行流程示意图；

图2为实际应用中某高校数据库中的学生信息表；

图3为图2中学生信息表的列存储结构图；

图4为查询计划图；

图5为映射-化简执行流程图；

图6为第一个子映射-化简执行流程的执行过程；

图7为图2中学生信息表的查询结果图。

具体实施方式

为了更好的理解本发明，下面将结合附图对本发明进行详细的说明。

如图1所示，本发明是一种基于映射-化简模型的列式数据库并行查询优化方法，应用于多核处理器环境下的列存储数据库查询中。利用映射-化简并行编程模型将查询任务动态分配到各个核来执行，并将所得到的中间结果集的键值对进行某种运算，最后返回所需的查询的结果，具体地说，

一种基于列存储的多核并行数据查询优化方法，所述方法包括以下步骤：

（1）读取用户输入的查询语句；

（2）生成查询计划，其中，对所述用户输入的查询语句，利用延时物化策略生成针对该查询语句的查询计划，所述查询计划可用图的形式来表示；

（3）构建对应所述查询计划的映射-化简执行流程，根据所述查询计划图，利用映射-化简模型中的映射阶段和化简阶段的交叉使用构建基于图中操作节点的映射-化简执行流程，其中，一个映射-化简执行流程中可能包含一个或多个子映射-化简执行流程，而在子映射-化简执行流程中只包含一个映射阶段与一个化简阶段；

（4）按照映射-化简执行流程完成所述查询计划的执行，依次执行映射-化简执行流程中的各个子映射-化简执行流程；

（5）向所述用户输出查询结果。

需要说明的是，所述步骤（3）包括以下步骤：

（1）将所述查询计划划分成多个串行执行的子查询计划，构成子查询计划序列：

(plan₁,plan₂,plan₃,...,plan_m)；

其中，在某一操作符之前可并行执行的多个单独操作符或操作符集合作为一个子查询计划存在；

（2）遍历子查询计划序列，若某个子查询计划plan_p的执行是以子查询计划plan_q的执行为前提的，并且在plan_q中存在着多于一个的可并行执行的操作符，则将plan_p和plan_q合并为一个子映射-化简执行流程，同时，将plan_q标记为映射，将plan_p标记为化简；

需要说明的是，所述步骤（4）包括如下步骤：

（1）统计映射-化简执行流程队列中子映射-化简执行流程的个数，将其标记为count；

（2）遍历映射-化简执行流程队列中的各个子映射-化简执行流程；

（2.1）令k＝1；

（2.2）当k≤count时，读取映射-化简执行流程队列中第k个子映射-化简执行流程，通过对该子映射-化简执行流程中子查询计划的分析，确定在此子映射-化简执行流程中三个键值对的具体数据结构；

（2.3）依次执行如下的映射阶段与化简阶段，其中各阶段的具体执行过程如下:

映射阶段，读取该子流程中标记为映射的子查询计划，将该子查询计划中的多个并行操作分配给处于空闲状态的核；由这些核并行完成子查询计划中的多个操作；

化简阶段，读取该子流程中标记为化简的子查询计划，并从中间结果集中读取相关数据，完成该子查询计划中的操作；

（2.4）至k++，返回步骤（2.2）。

需要进一步说明的是，所述三个键值对分别为，映射函数的输入键值对、映射函数的输出键值对和化简函数的输入键值对，其中，各键值对的结构为由键key和其相对应的值value构成的键值对。

下面将结合具体实施例对本发明作进一步的描述。

实施例1

在本实施例中，采用4核处理器，结合对某高校数据库中的学生信息表stuInfo的查询对本发明进行说明。

图2表示了所述学生信息表的逻辑结构图，图3表示了所述学生信息表的列存储结构图。

步骤1，读取sql查询语句。

需要说明的是，在此实施例中，预设对stuInfo进行如下的简单查询：查出某学院中年龄小于某一固定值的学生的姓名、性别及其具体年龄。该查询的SQL语句如下。

Select name,sex,age

from stuInfo

where age<24and college=’Computer Science’

步骤2，生成查询计划：对用户输入的查询语句，利用延时物化策略生成针对该查询语句的查询计划。

延时物化策略是针对提前物化策略提出的，这两种策略都属于元组物化的范畴。元组物化即将逻辑上需要合并的元组(一列或几列数据)进行合并，生成实体化的元组，并将其存储于内存中。根据其合并的时间点的不同，可分为上述两种策略。提前物化策略在查询提交之前对元组进行物化；延时物化策略则尽量推迟物化时间，在查询中对元组进行物化。

对采取了压缩策略的列存储数据库而言，提前物化的空间和时间开销很大，因为其需要解压相关的已被压缩的列数据。同时，提前物化还有可能对某些不必要的列数据进行物化，使得中间结果集变大，增加了后续处理的开销。因此在列存储数据库中，往往采用的是延时物化策略。

生成的查询计划用图的形式来表示，图中的节点代表查询计划中的操作符，节点的输入边和输出边分别代表操作符的输入或输出。

以上述的延时物化策略为标准，生成该查询语句的查询计划，该计划如图4所示，需要说明的是，图4中所用到列存储数据库中的操作符的功能描述如下：

DS1：此操作符包含的两个操作数为列数据和判断条件，返回值为id，id为该列中符合判断条件的数据所在行的行号；

And：此操作符对两个id序列取交，得到在两个序列中同时出现的行号；

DS3：此操作符包含的两个操作数为列数据和id序列；取出在列数据对应于id序列中的id的数据，输出格式为(id,value)；

Merge：将n列数据中处于相同位置处的数据值合并输出，输出格

式为(id,value₁,value₂,...,value_n)。

步骤3，构建对应所述查询计划的映射-化简执行流程，根据所述查询计划图，利用映射-化简模型中的映射阶段和化简阶段的交叉使用构建基于图中操作节点的映射-化简执行流程，其中，一个映射-化简执行流程中可能包含一个或多个子映射-化简执行流程，而在子映射-化简执行流程中只包含一个映射阶段与一个化简阶段；

该实例的最终的映射-化简执行流程图如图5所示。

步骤4，按照映射-化简执行流程完成所述查询计划的执行，依次执行映射-化简执行流程中的各个子映射-化简执行流程；

步骤5，输出查询结果。

如图7所示，为最后的查询结果图。

需要说明的是，如图5所示，本发明中步骤3中的构建对应于查询计划的映射-化简执行流程具体包括如下步骤：

步骤3.1，对查询计划进行分析，将查询计划划分成多个串行执行的子查询计划，构成子查询计划序列：

(plan₁,plan₂,plan₃,...,plan_m)；

其中，在某一操作符之前可并行执行的多个单独操作符或操作符集合作为一个子查询计划存在；

步骤3.2，遍历子查询计划序列，若某个子查询计划plan_p的执行是以子查询计划plan_q的执行为前提的，并且在plan_q存在着多于一个的可并行执行的操作符，则将plan_p和plan_q合并为一个子映射-化简执行流程，同时，将plan_q标记为映射，将plan_p标记为化简；

将第一步生成的查询计划划分为多个串行执行的子查询计划，而一个子查询计划中可能存在着多个需要并行执行的任务。因此，在总的查询计划中，存在着这样的一些局部子查询计划执行次序：某个子查询计划的执行是以其它几个子查询计划的并行执行为前提的。而映射-化简模型的核心思想就是将多个可以并行执行的任务通过一定的方法分布到不同的核上执行，最终对各个核的执行结果进行统一处理。因此可以将查询计划中的某些局部操作符执行次序用映射-化简模型来处理，通过任务的并行执行使得查询效率得以提高。

依上所述，构建步骤2中生成的查询计划的映射-化简执行流程。根据对查询计划的分析，可得出该查询计划通过以下4个子查询计划的串行执行完成：

Plan1:DS1(age,age<24)=>pos1、DS1(dept_name,dept_name=‘Comp.Sci’)=>pos2;

Plan2:pos1And pos2=>pos3;

Plan3:DS3(pos3,(pos,namevalue))=>(pos,namevalue);

DS3(pos3,(pos,sexvalue))=>(pos,sexvalue);

DS3(pos3,(pos,agevalue))=>(pos,agevalue);

Plan4:Merge((pos,namevalue),(pos,sexvalue),(pos,agevalue))=>

(namevalue,sexvalue,agevalue);

其中plan1和plan3所对应的子查询计划可以并行执行，plan2和plan4所对应的子查询计划是对上一步的结果进行合并。依照映射-化简模型构建该计划的映射-化简执行模型，则plan1和plan2组成一个子映射-化简过程映射-化简1，plan3和plan4组成另一个映射-化简过程映射-化简2。

需要说明的是，在进行步骤4时，包括如下步骤：

步骤4.1，统计映射-化简执行流程队列中子映射-化简执行流程的个数，记为count；

步骤4.2，遍历映射-化简执行流程队列中的各个子映射-化简执行流程；

步骤4.2.1，令k＝1；

步骤4.2.2，若k≤count，读取映射-化简执行流程队列中第k个子映射-化简执行流程，通过对该子映射-化简执行流程中子查询计划的分析，确定在此映射-化简执行流程中三个键值对（映射函数的输入键值对、映射函数的输出键值对和化简函数的输入键值对，各键值对的结构为由键key和其相对应的值value构成的键值对）中的key和value具体代表的数据结构。

步骤4.2.3，依次执行如下的映射阶段和化简阶段，其中各阶段的具体执行过程如下：

映射阶段：读取该子流程中标记为映射的子查询计划，将该子查询计划中的多个并行操作分配给处于空闲状态的核；由这些核并行完成子查询计划中的多个操作；

化简阶段：读取该子流程中标记为化简的子查询计划，并从中间结果集中读取相关数据，完成该子查询计划中的操作；

步骤4.2.4，至k++，返回步骤4.2.2。

需要进一步说明的是，映射-化简编程模型的主要思想体现在映射和化简上。映射就是将一个任务分解成多个任务，化简就是将分解后的多任务处理结果汇总起来，得出最后的分析结构。该模型的内部细节对用户来说是透明的，用户只需要实现相应的映射和化简函数，即可完成相关任务的并行化计算，这样编程人员需要关注的就只是如何设计好映射和化简函数，而无需过多的关注其内部是如何进行并行调度的，使得在编写并行任务时大大的减少了编程人员的工作量。

在编写映射函数和化简函数中，最重要的一个方面就是如何针对特定的应用设计出合适的键值对。映射函数对用户输入的键值对(k1,v1)进行处理，得到中间形式的键值对(k2,v2)，同时按照k2的值对(k2,v2)进行排序或聚合得到中间形式的键值对序列list(k2,v2)。映射-化简模型把在中间形式的键值对中具有相同key值的value值集合在一起后形成键值对(k2,list(v2))，并将其作为输入参数传递给化简函数。化简函数以此中间形式的键值对(k2,list(v2))作为输入值，通过一定的处理得到程序的最终输出。

在列存储数据库的数据查询中使用映射-化简模型，主要是键值对的设计。在本发明中，根据每个映射任务的操作符的不同，映射函数的输入键值对也不同。由于在映射任务中，主要是对单列数据进行条件判断或位置过滤，因此将映射函数的输入键值对定义为(col,pred)（条件判断）或(col,pos)（位置过滤）。在映射函数体中调用相应的操作符进行处理。映射函数的输出键值对定义为(id,value)，其中id代表某列数据中满足给定条件pred或通过位置过滤的值所在行的行号，value代表该值本身。同时，映射函数对(id,value)进行排序，得到中间形式的键值对序列list(id,value)。映射-化简模型把在中间形式的键值对中具有相同id值的value值集合在一起后形成键值对(id,list(value))。化简函数以此中间形式的键值对(id,list(value))作为其输入值，通过一定的处理得到程序的输出，该输出可为行号组成的序列（中间结果集，可为后续的子映射-化简流程提供输入数据），也可为由满足多个条件的列数据组成的元组，如(id,value₁,...,value_k)（最终输出）。

接下来，按照映射-化简执行流程完成对实施例1中的查询计划的执行。通过步骤3的执行将查询计划划分为相应的2个子映射-化简执行流程。

第一个子映射-化简执行流程的流程图如图6所示。第二个子映射-化简执行流程和第一个基本一样，只是最后的化简阶段输出的是最终的查询结果数据集(id,value₁,value₂,value₃)。

对于本领域的技术人员来说，可根据以上描述的技术方案以及构思，做出其它各种相应的改变以及变形，而所有的这些改变以及变形都应该属于本发明权利要求的保护范围之内。

Claims (2)

1.一种基于列存储的多核并行数据查询优化方法，所述方法包括以下步骤：

(1)读取用户输入的查询语句；

(2)生成查询计划，其中，对所述用户输入的查询语句，利用延时物化策略生成针对该查询语句的查询计划，所述查询计划可用图的形式来表示；

(3)构建对应所述查询计划的映射-化简执行流程，根据所述查询计划图，利用映射-化简模型中的映射阶段和化简阶段的交叉使用构建基于图中操作节点的映射-化简执行流程，其中，一个映射-化简执行流程中可能包含一个或多个子映射-化简执行流程，而在子映射-化简执行流程中只包含一个映射阶段与一个化简阶段；

(4)按照映射-化简执行流程完成所述查询计划的执行，依次执行映射-化简执行流程中的各个子映射-化简执行流程；

(5)向所述用户输出查询结果；

其特征在于，所述步骤(3)包括以下步骤：

(1)将所述查询计划划分成多个串行执行的子查询计划，构成子查询计划序列：

(plan₁,plan₂,plan₃,...,plan_m)；

其中，在某一操作符之前可并行执行的多个单独操作符或操作符集合作为一个子查询计划存在；

(2)遍历子查询计划序列，若某个子查询计划plan_p的执行是以子查询计划plan_q的执行为前提的，并且在plan_q中存在着多于一个的可并行执行的操作符，则将plan_p和plan_q合并为一个子映射-化简执行流程，同时，将plan_q标记为映射，将plan_p标记为化简。

2.根据权利要求1所述的数据查询优化方法，其特征在于，所述步骤(4)包括如下步骤：

(1)统计映射-化简执行流程队列中子映射-化简执行流程的个数，将其标记为count；

(2)遍历映射-化简执行流程队列中的各个子映射-化简执行流程；

(2.1)令k＝1；

(2.2)当k≤count时，读取映射-化简执行流程队列中第k个子映射-化简执行流程，通过对该子映射-化简执行流程中子查询计划的分析，确定在此子映射-化简执行流程中三个键值对的具体数据结构；

(2.3)依次执行如下的映射阶段与化简阶段，其中各阶段的具体执行过程如下:

映射阶段，读取该子流程中标记为映射的子查询计划，将该子查询计划中的多个并行操作分配给处于空闲状态的核；由这些核并行完成子查询计划中的多个操作；

化简阶段，读取该子流程中标记为化简的子查询计划，并从中间结果集中读取相关数据，完成该子查询计划中的操作；

(2.4)k++，返回步骤(2.2)；

其中，所述三个键值对分别为:映射函数的输入键值对、映射函数的输出键值对和化简函数的输入键值对，其中，各键值对的结构为由键key和其相对应的值value构成的键值对。