执行计划的生成与执行方法、数据库引擎及存储介质

摘要

本申请实施例提供一种执行计划的生成与执行方法、数据库引擎及存储介质。在本申请实施例中，针对支持列式存储的数据库定义新的数据单位“行组”，并针对“行组”重新定义物理算子的输入输出格式从而形成新的物理算子“行组转行”以及输入输出为行组的物理算子、输出为行组的物理算子等，进而在新的物理算子的基础上提供适配的执行计划生成与执行方法，由于这些内容都是针对列式存储的特点提出的，更加适用于支持列式存储的数据库，在充分发挥列式存储优势的同时，能够进一步提高支持列式存储的数据库的查询效率。

权利要求

1.一种执行计划的生成方法，其特征在于，包括：

根据数据库查询语句生成语法树，所述语法树上的节点表示逻辑算子；

若所述逻辑算子是所述语法树上的非叶子节点，结合已经为所述逻辑算子的子逻辑算子选择出的物理算子C的输出格式和至少一个物理算子各自的输入格式，计算所述至少一个物理算子各自的基准代价；从所述至少一个物理算子中，选择基准代价符合设定要求的物理算子作为目标物理算子；

若所述逻辑算子是所述语法树上的叶子节点，则计算所述至少一个物理算子各自的代价，并从中选择代价符合设定要求的物理算子作为所述目标物理算子；

根据所述目标物理算子生成所述逻辑算子对应的物理执行计划；

其中，所述至少一个物理算子是以行和行组为数据单位定义输入输出格式的物理算子，所述行组是列式存储中若干行形成的数据单位；

对物理算子S，若所述物理算子C的输出格式与所述物理算子S的输入格式不相同，确定在所述物理算子C与所述物理算子S之间进行格式转换的物理算子D，并计算所述物理算子S的代价以及所述物理算子D的代价之和，作为所述物理算子S的基准代价；

其中，所述物理算子S是所述至少一个物理算子中的任一物理算子。

2.根据权利要求1所述的方法，其特征在于，所述物理算子C的输出格式为输出行组，所述物理算子S的输入格式为输入行，则物理算子D为行组转行物理算子，所述行组转行物理算子用于将行组中关于行的描述转换为全局行的描述；或者所述物理算子C的输出格式为输出行，所述物理算子S的输入格式为输入行组，则物理算子D为逐行物化物理算子，所述逐行物化物理算子用于将全局行的描述转换为行组中关于行的描述。

3.根据权利要求1所述的方法，其特征在于，还包括：

若所述物理算子C的输出格式与所述物理算子S的输入格式相同，计算所述物理算子S的代价作为所述物理算子S的基准代价。

4.根据权利要求3所述的方法，其特征在于，计算所述物理算子S的代价，包括：结合所述逻辑算子所关联的行组的统计信息，计算所述物理算子S的代价。

5.根据权利要求4所述的方法，其特征在于，结合所述逻辑算子所关联的行组的统计信息，计算所述物理算子S的代价，包括：根据所述逻辑算子所关联的行组的统计信息，对所述物理算子所需处理的行组数量进行过滤；

根据过滤后剩余的行组数量计算所述物理算子S的代价。

6.一种执行计划的执行方法，其特征在于，包括：

获取执行树，所述执行树包括具有父子关系的至少一个物理算子；

运行所述执行树，以使所述至少一个物理算子按照所述父子关系自上而下调用执行并反向返回查询结果；

输出所述查询结果；

其中，所述至少一个物理算子是以行和行组为数据单位定义输入输出格式的物理算子，所述行组是列式存储中若干行形成的数据单位；

在所述至少一个物理算子按照所述父子关系自上而下调用执行的过程中包括：输入为行的物理算子调用行组转行物理算子的下一行接口，所述行组转行物理算子调用输出为行组的物理算子的下一行组接口，所述输出为行组的物理算子从支持列式存储的数据库中读取指定行组数据；或者在所述至少一个物理算子按照所述父子关系自上而下调用执行的过程中包括：输入为行组的物理算子调用输出为行组的物理算子的下一行组接口，所述输出为行组的物理算子从支持列式存储的数据库中读取指定行组数据；或者在所述至少一个物理算子按照所述父子关系自上而下调用执行的过程中包括：输入为行组且具有物化属性的物理算子调用逐行物化物理算子的下一行接口，所述逐行物化物理算子调用输出为行的物理算子的下一行接口，所述输出为行的物理算子从支持列式存储的数据库中读取指定行数据；或者在所述至少一个物理算子按照所述父子关系自上而下调用执行的过程中包括：输入为行的物理算子调用输出为行的物理算子的下一行接口，所述输出为行的物理算子从支持列式存储的数据库中读取指定行数据。

7.根据权利要求6所述的方法，其特征在于，在反向返回查询结果的过程中，所述输出为行组的物理算子向行组转行物理算子返回行组数据；行组转行物理算子将所述行组数据中的第一行数据返回给输入为行的物理算子，并在所述输入为行的物理算子每调用行组转行物理算子的下一行接口一次返回一行数据，直至所述行组数据中的数据均被返回为止。

8.一种数据库引擎，其特征在于，包括：存储器和处理器；

所述存储器，用于存储计算机程序；

所述处理器，用于执行所述计算机程序，以用于：

根据数据库查询语句生成语法树，所述语法树上的节点表示逻辑算子；

若所述逻辑算子是所述语法树上的非叶子节点，结合已经为所述逻辑算子的子逻辑算子选择出的物理算子C的输出格式和至少一个物理算子各自的输入格式，计算所述至少一个物理算子各自的基准代价；从所述至少一个物理算子中，选择基准代价符合设定要求的物理算子作为目标物理算子；

若所述逻辑算子是所述语法树上的叶子节点，则计算所述至少一个物理算子各自的代价，并从中选择代价符合设定要求的物理算子作为所述目标物理算子；

根据所述目标物理算子生成所述逻辑算子对应的物理执行计划；

其中，所述至少一个物理算子是以行和行组为数据单位定义输入输出格式的物理算子，所述行组是列式存储中若干行形成的数据单位；

对物理算子S，若所述物理算子C的输出格式与所述物理算子S的输入格式不相同，确定在所述物理算子C与所述物理算子S之间进行格式转换的物理算子D，并计算所述物理算子S的代价以及所述物理算子D的代价之和，作为所述物理算子S的基准代价；

其中，所述物理算子S是所述至少一个物理算子中的任一物理算子。

9.根据权利要求8所述的数据库引擎，其特征在于，所述物理算子C的输出格式为输出行组，所述物理算子S的输入格式为输入行，则物理算子D为行组转行物理算子，所述行组转行物理算子用于将行组中关于行的描述转换为全局行的描述；或者所述物理算子C的输出格式为输出行，所述物理算子S的输入格式为输入行组，则物理算子D为逐行物化物理算子，所述行组转行物理算子用于将全局行的描述转换为行组中关于行的描述。

10.根据权利要求8或9所述的数据库引擎，其特征在于，所述处理器在计算所述物理算子S的代价时，具体用于：结合所述逻辑算子所关联的行组的统计信息，计算所述物理算子S的代价。

11.根据权利要求10所述的数据库引擎，其特征在于，所述处理器在计算所述物理算子S的代价时，具体用于：根据所述逻辑算子所关联的行组的统计信息，对所述物理算子所需处理的行组数量进行过滤；

根据过滤后剩余的行组数量计算所述物理算子S的代价。

12.一种数据库引擎，其特征在于，包括：存储器和处理器；

所述存储器，用于存储计算机程序；

所述处理器，用于执行所述计算机程序，以用于：

获取执行树，所述执行树包括具有父子关系的至少一个物理算子；

运行所述执行树，以使所述至少一个物理算子按照所述父子关系自上而下调用执行并反向返回查询结果；

输出所述查询结果；

其中，所述至少一个物理算子是以行和行组为数据单位定义输入输出格式的物理算子，所述行组是列式存储中若干行形成的数据单位；

在所述至少一个物理算子按照所述父子关系自上而下调用执行的过程中包括：输入为行的物理算子调用行组转行物理算子的下一行接口，所述行组转行物理算子调用输出为行组的物理算子的下一行组接口，所述输出为行组的物理算子从支持列式存储的数据库中读取指定行组数据；或者在所述至少一个物理算子按照所述父子关系自上而下调用执行的过程中包括：输入为行组的物理算子调用输出为行组的物理算子的下一行组接口，所述输出为行组的物理算子从支持列式存储的数据库中读取指定行组数据；或者在所述至少一个物理算子按照所述父子关系自上而下调用执行的过程中包括：输入为行组且具有物化属性的物理算子调用逐行物化物理算子的下一行接口，所述逐行物化物理算子调用输出为行的物理算子的下一行接口，所述输出为行的物理算子从支持列式存储的数据库中读取指定行数据；或者在所述至少一个物理算子按照所述父子关系自上而下调用执行的过程中包括：输入为行的物理算子调用输出为行的物理算子的下一行接口，所述输出为行的物理算子从支持列式存储的数据库中读取指定行数据。

13.根据权利要求12所述的数据库引擎，其特征在于，所述处理器具体用于：控制所述输出为行组的物理算子向行组转行物理算子返回行组数据；行组转行物理算子将所述行组数据中的第一行数据返回给输入为行的物理算子，并在所述输入为行的物理算子每调用行组转行物理算子的下一行接口一次返回一行数据，直至所述行组数据中的数据均被返回为止。

14.一种存储有计算机程序的计算机可读存储介质，其特征在于，当所述计算机程序被执行时，能够实现权利要求1‑5任一项所述方法中的步骤。

15.一种存储有计算机程序的计算机可读存储介质，其特征在于，当所述计算机程序被执行时，能够实现权利要求6或7所述方法中的步骤。

说明书

执行计划的生成与执行方法、数据库引擎及存储介质

技术领域

[0001] 本申请涉及数据库技术领域，尤其涉及一种执行计划的生成与执行方法、数据库引擎及存储介质。

背景技术

[0002] 随着大数据的发展，传统的行(row)式数据库在查询性能和维护成本等方面逐渐不能满足需求，于是出现了列式数据库。列式数据库是以列式存储架构进行数据存储的数据库，主要适合批量数据处理和即时查询。

[0003] 在目前已出现的列式数据库中，大部分依旧采用成熟的流水线式SQL执行模型，即执行树形成倒三角形，数据从三角形底部，逐行涌向顶部。在这个执行过程中，仍以行为迭代单位，无法充分发挥列式存储的优势。因此，有必要针对列式数据库提供一种查询解决方案，用以充分发挥列式存储的优势。

发明内容

[0004] 本申请的多个方面提供一种执行计划的生成与执行方法、数据库引擎及存储介质，用以提供一种适用于支持列式存储的数据库的查询解决方案，以充分发挥列式存储的优势。

[0005] 本申请实施例提供一种执行计划的生成方法，包括：根据数据库查询语句生成语法树，所述语法树上的节点表示逻辑算子；针对所述语法树上的每个逻辑算子，从与所述逻辑算子等价的至少一个物理算子中选择目标物理算子；根据所述目标物理算子生成所述逻辑算子对应的物理执行计划；其中，所述至少一个物理算子是以行和行组为数据单位定义输入输出格式的物理算子，所述行组是列式存储中若干行形成的数据单位。

[0006] 本申请实施例还提供一种执行计划的执行方法，包括：获取执行树，所述执行树包括具有父子关系的至少一个物理算子；运行所述执行树，以使所述至少一个物理算子按照所述父子关系自上而下调用执行并反向返回查询结果；输出所述查询结果；其中，所述至少一个物理算子是以行和行组为数据单位定义输入输出格式的物理算子，所述行组是列式存储中若干行形成的数据单位。

[0007] 本申请实施例还提供一种数据库引擎，包括：存储器和处理器；所述存储器，用于存储计算机程序；所述处理器，用于执行所述计算机程序，以用于：根据数据库查询语句生成语法树，所述语法树上的节点表示逻辑算子；针对所述语法树上的每个逻辑算子，从与所述逻辑算子等价的至少一个物理算子中选择目标物理算子；根据所述目标物理算子生成所述逻辑算子对应的物理执行计划；其中，所述至少一个物理算子是以行和行组为数据单位定义输入输出格式的物理算子，所述行组是列式存储中若干行形成的数据单位。

[0008] 本申请实施例还提供一种数据库引擎，包括：存储器和处理器；所述存储器，用于存储计算机程序；所述处理器，用于执行所述计算机程序，以用于：获取执行树，所述执行树包括具有父子关系的至少一个物理算子；运行所述执行树，以使所述至少一个物理算子按照所述父子关系自上而下调用执行并反向返回查询结果；输出所述查询结果；其中，所述至少一个物理算子是以行和行组为数据单位定义输入输出格式的物理算子，所述行组是列式存储中若干行形成的数据单位。

[0009] 本申请实施例还提供一种存储有计算机程序的计算机可读存储介质，当所述计算机程序被执行时，能够实现上述执行计划的生成方法中的步骤。

[0010] 本申请实施例还提供一种存储有计算机程序的计算机可读存储介质，当所述计算机程序被执行时，能够实现上述执行计划的执行方法中的步骤。

[0011] 在本申请实施例中，针对支持列式存储的数据库定义新的数据单位“行组”，并针对“行组”重新定义物理算子的输入输出格式从而形成新的物理算子“行组转行”以及输入输出为行组的物理算子、输出为行组的物理算子等，进而在新的物理算子的基础上提供适配的执行计划生成与执行方法，由于这些内容都是针对列式存储的特点提出的，更加适用于支持列式存储的数据库，在充分发挥列式存储优势的同时，能够进一步提高支持列式存储的数据库的查询效率。

附图说明

[0012] 此处所说明的附图用来提供对本申请的进一步理解，构成本申请的一部分，本申请的示意性实施例及其说明用于解释本申请，并不构成对本申请的不当限定。在附图中：

[0013] 图1a为本申请示例性实施例提供的一种数据库访问系统的结构示意图；

[0014] 图1b为本申请实施例提供的部分数据表中行组的示意图；

[0015] 图1c为本申请实施例提供的以输入输出定义的各物理算子之间的父子关系示意图；

[0016] 图2为本申请示例性实施例提供的一种执行计划的生成方法流程示意图；

[0017] 图3a为本申请示例性实施例提供的一种执行计划的执行方法流程示意图；

[0018] 图3b为本申请示例性实施例提供的一种几个物理算子之间的交互流程示意图；

[0019] 图4为本申请示例性实施例提供的一种数据库引擎的结构示意图；

[0020] 图5为本申请示例性实施例提供的另一种数据库引擎的结构示意图。

具体实施方式

[0021] 为使本申请的目的、技术方案和优点更加清楚，下面将结合本申请具体实施例及相应的附图对本申请技术方案进行清楚、完整地描述。显然，所描述的实施例仅是本申请一部分实施例，而不是全部的实施例。基于本申请中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本申请保护的范围。

[0022] 针对现有列式数据库面临的查询性能问题，在本申请一些实施例中，针对支持列式存储的数据库定义新的数据单位“行组”，并针对“行组”重新定义物理算子的输入输出格式从而形成新的物理算子“行组转行”以及输入输出为行组的物理算子、输出为行组的物理算子等，进而在新的物理算子的基础上提供适配的执行计划生成与执行方法，由于这些内容都是针对列式存储的特点提出的，更加适用于支持列式存储的数据库，在充分发挥列式存储优势的同时，能够进一步提高支持列式存储的数据库的查询效率。

[0023] 以下结合附图，详细说明本申请各实施例提供的技术方案。

[0024] 图1a为本申请示例性实施例提供的一种数据库访问系统的结构示意图。如图1a所示，该系统包括：客户端101、数据库引擎102以及支持列式存储的数据库(Database)103。

[0025] 支持列式存储的数据库103是建立在计算机存储设备上，支持以列式存储架构来组织、存储和管理数据的仓库。在本申请实施例中，并不限定承载支持列式存储的数据库103的计算机存储设备的实现形式。支持列式存储的数据库103可以是但不限于列式数据库，还可以是行列混合的数据库。

[0026] 数据库引擎102是用于存储、处理和保护数据的核心服务，其任务包括处理与支持列式存储的数据库103相关的事务，例如设计并创建支持列式存储的数据库103，保存支持列式存储的数据库103所需的各种列表和文档等，针对支持列式存储的数据库103提供日常管理支持以优化支持列式存储的数据库103的性能。

[0027] 其中，为了便于处于与支持列式存储的数据库103相关的事务，数据库引擎102与支持列式存储的数据库103之间建立通信连接，该通信连接可以是有线或无线网络连接。可选地，在部署实现上，数据库引擎102与支持列式存储的数据库103可以部署在同一物理设备上实现，也可以部署在不同物理设备上实现。当数据库引擎102与支持列式存储的数据库103部署在不同物理设备上实现时，两者可以部署同一局域网内，也可以部署在不同局域网内。

[0028] 如图1所示，该数据库系统还包括：客户端101。其中，客户端101与数据库引擎102之间通信连接，该通信连接可以是有线或无线网络连接。可选地，客户端101可以与数据库引擎102处于同一局域网内，也可以处于不同局域网内。

[0029] 客户端101可以看作是支持列式存储的数据库103面向用户提供的交互接口，允许用户通过该客户端101访问支持列式存储的数据库103。在需要访问支持列式存储的数据库103时，客户端101可以向数据库引擎102发送数据库访问请求；数据库引擎102还可以响应客户端101的数据库访问请求对支持列式存储的数据库103进行相关操作并向客户端101返回相关操作结果，从而实现支持列式存储的数据库103中数据的查看、删除、修改、增加等。

[0030] 在一种数据库查询场景中，客户端101可以向数据库引擎102发送数据库查询语句。根据支持列式存储的数据库103支持的数据库语言的不同，数据库查询语句会有所不同，例如可以是SQL语句，也可以是Orcal语句。数据库引擎102主要根据数据库查询语句对支持列式存储的数据库103进行查询操作，并向客户端101返回查询结果。

[0031] 在本实施例中，数据库引擎102在根据数据库查询语句对支持列式存储的数据库103进行查询的过程中，可以对数据库查询语句进行语法解析、优化处理、物理执行计划的生成与执行等操作，从而完成数据库查询操作。这样可以减少计算量，提高查询效率。

[0032] 上述查询逻辑中涉及物理执行计划的生成与运行，而物理执行计划的好与坏一定程度上决定了查询效率的高低。在现有技术中，大部分数据库都会采用火山模型，即执行树构成倒三角形，执行时以行为单位，数据从三角形底部，逐行涌向顶部。这个火山模型源于行式数据库，应用于支持列式存储的数据库，不利于充分发挥支持列式存储的数据库的优势。在本实施例中，针对列式存储这一特性，提供一种新的执行解决方案，该方案更加适合支持列式存储的数据库103，能够在充分发挥列式存储优势的同时，进一步提高支持列式存储的数据库的查询效率。下面将对本实施例的计划解决方案进行描述：

[0033] 在本实施例中，针对支持列式存储的数据库103，在“列”的基础上定义了一种新的数据单位，即行组。行组是列式存储中若干行形成的数据单位。这里的行是指数据库领域中传统意义上的数据行。在列式存储中，数据被逐列存储，在一个列中，数据被进一步分割为行组。可选地，以行组为单位，可以对行组内的数据进行独立压缩和信息统计。其中，信息统计的结果即为行组的统计信息，行组的统计信息主要用于描述行组存储数据的特征。参见图1b所示，列式存储中部分表格中包括列1、列2、列3以及其他列(图1b中未示出)，另外还包括行组1、行组2、行组3以及其它行组(图1b中未示出)。在图1b中，列与行组的交叉部分表示该列包含的行组单元，每个交叉部分中的黑框表示该行组的统计信息，灰色框表示该行组包含的各行数据压缩后形成的数据包。参见图1b可知，从“行组”的角度来看，一个“行组”涉及若干列，每个列对应的部分称为行组单元；从列的角度来看，一个“列”包含若干个行组单元，若干个行组单元分别属于若干个行组。在此说明，本申请实施例并不限定若干个的具体数量，可以根据应用场景适应性设定。

[0034] 在支持列式存储的数据库103中引入新的数据单位“行组”后，对支持列式存储的数据库103中的物理算子来说，除了“行”这种输入输出格式之外，增加了一种新的输入输出格式，即行组。相较于输入输出均为行的行式数据库来说，本实施例的支持列式存储的数据库103中的输入输出组合多了三种情况：输入为行输出为行组，输入为行组输出为行，输入为行组输出为行组。对支持列式存储的数据库103中的物理算子而言，所有输入输出的组合情况如下表1所示：

[0035] 表1

[0036]

[0037] 在增加新的输入输出格式之后，适应性地对物理算子的输入输出进行调整。首先，在本实施例中，根据物理算子是否具有物化属性，将物理算子划分为有物化属性的物理算子和没有物化属性的物理算子两种类型。其中，根据数据库以及物理算子实现上的不同，可以灵活设定物理算子是否具有物化属性。物理算子是否具有物化属性主要是根据它的输出结果的情况确定的，若其输出结果只需要行号，不需要该行号指向的整行数据，认为其不具有物化属性，反之，若其输出结果不仅需要行号，还需要获取该行号所指向的整行数据，认为其具有物化属性。例如，物理算子Group by以及(select A from table 1)Union all(select A+Bfrom table 2)中的Union all算子都具有物化属性。接着，对这两种类型的物理算子的输入输出进行调整，调整结果参见上述表1。

[0038] 由表1可知，对于有物化属性的物理算子，其输出均为行组，其输入可以是行组也可是行。进一步，根据输入的情况，可以将有物化属性的物理算子细分为：有物化属性的行迭代算子和有物化属性的行组迭代算子。其中，有物化属性的行迭代算子是指输入为行输出为行组的物理算子；有物化属性的行组迭代算子是指输入为行组输出为行组的物理算子。

[0039] 由表1可知，对于没有物化属性的物理算子，若其输入是行，则其输出也只能是行；若其输入是行组，其输出可以是行也可以是行组。为便于区分，将输入为行且没有物化属性的物理算子称为无物化属性的行迭代算子；将输入为行组且没有物化属性的物理算子称为无物化属性的行组迭代算子。

[0040] 在“行”和“行组”的基础行重新定义物理算子的输入输出格式之外，进一步增加一种新的物理算子“行组转行”，该“行组转行”算子的作用是将行组中关于行的描述转换为全局行的描述，以便在输入为行的物理算子与输出为行组的物理算子之间进行衔接，使得输入为行的物理算子能够通过“行组转行”这个算子间接与输出为行组的物理算子进行交互。

[0041] 从输入输出格式的角度，可以将物理算子划分为：输入为行组的物理算子、输入为行的物理算子、输出为行的物理算子、输出为行组的物理算子、行组转行的物理算子以及逐行物化的物理算子。相应地，结合输入输出格式之间的适配关系，这些物理算子之间的父子关系(或应该满足的调用关系)如图1c所示。在图1c中，圆角矩形表示物理算子，圆角矩形中的文字是物理算子的名称，圆角矩形之间的实线表示相应物理算子之间的父子关系，且实线的箭头指向子算子。另外，在图1c中，逻辑算子与物理算子之间的虚线以及相邻物理算子之间的虚线，表示该逻辑算子等价的物理算子，另外，与同一逻辑算子对应的两个物理算子之间是备选关系。

[0042] 例如，在图1c中，与上面圆形表示的逻辑算子等价的物理算子包括：输入为行组的物理算子和输入为行的物理算子，这两个物理算子之间是备选关系；与下面圆形所表示的逻辑算子等价的物理算子包括：输出为行的物理算子和输出为行组的物理算子，且这两个物理算子之间是备选关系。对于具有备选关系的两个物理算子，在物理执行计划生成过程中需要从中选择一个执行代价更优的物理算子。

[0043] 另外，还可以建立逻辑算子与物理算子之间的等价关系。可选地，可以将逻辑算子与物理算子之间的等价关系存储至列表中，这样在使用时，可以执行查表操作。或者，也可以将逻辑算子与物理算子之间的等价关系添加至知识网中，并将该知识网固化到执行计划生成程序中，这样在使用时可以直接跳到知识网所在代码段进行查询即可。

[0044] 经过上面描述可知，在支持列式存储的数据库103中存在的物理算子是以行和行组为数据单位定义输入输出格式的物理算子，并且将基于这些物理算子进行数据库查询。其中，数据库查询过程中会涉及物理执行计划的生成过程，执行计划生成过程如下：

[0045] 数据库查询语句到达数据库引擎102之后，数据库引擎102根据数据库查询语句生成语法树，该语法树是一颗逻辑执行计划树，包括由数据库查询语句生成的至少一个逻辑执行计划，每个逻辑执行计划包括逻辑算子和逻辑表达式，语法树上的节点表示逻辑算子。其中，数据库引擎102可以对数据库查询语句进行优化处理得到上述语法树。

[0046] 生成语法树之后，数据库引擎102可以按照语法树上逻辑算子之间的父子关系，自下而上为语法树上的逻辑算子选择需要生成物理执行计划所需的物理算子，为便于描述，将这里选择的生成物理执行计划所需的物理算子称为目标物理算子。其中，对语法树上的每个逻辑算子而言，为其选择目标物理算子的过程主要是从与该逻辑算子等价的至少一个物理算子中选择目标物理算子。在本实施例中，与各个逻辑算子等价的至少一个物理算子不同于常规数据库(例如行式数据库或采用火山模型的支持列式存储的数据库)中的物理算子，这里至少一个物理算子是以行和行组为数据单位定义输入输出格式的物理算子。

[0047] 在为每个逻辑算子选择出目标物理算子之后，可以根据每个逻辑算子对应的目标物理算子生成相应的物理执行计划。对一个逻辑算子而言，其对应的物理执行计划包括与该逻辑算子等价的目标物理算子和对应的执行表达式。执行表达式是根据逻辑表达式生成的。

[0048] 值得说明的是，每个逻辑算子对应的物理执行计划可以形成一颗执行树，该执行树上的节点表示物理算子，这些物理算子之间具有父子关系。对一条数据库查询语句来说，在得到由该语句优化出的每个逻辑算子对应的物理执行计划之后，数据库引擎102可以执行该物理执行计划，以使得该物理执行计划包含的至少一个物理算子按照父子关系自上而下调用执行并反向返回查询结果，在得到查询结果之后可以输出查询结果，完成数据库查询操作。

[0049] 可选地，结合图1c可知，两个物理算子之间可能存在多条计算路径，尤其是对于输入格式与输出格式不同的两个物理算子有可能需要经过中间物理算子进行格式转换。例如，输入为行的物理算子与输出为行组的物理算子可以经过行组转行物理算子进行格式转换。

[0050] 基于上述分析，在为逻辑算子选择目标物理算子的过程中，可以根据逻辑算子是否是语法树上的叶子节点进行区分，若逻辑算子是语法树上的叶子节点，则可以直接计算与该逻辑算子等价的至少一个物理算子各自的代价，并从中选择代价符合设定要求的物理算子作为该逻辑算子对应的目标物理算子。可选地，可以从中选择代价最小的物理算子作为目标物理算子，这有利于减少资源消耗量。

[0051] 若逻辑算子是语法树上的非叶子节点，该逻辑算子会有自己的子逻辑算子，在为其选择物理算子时需要考虑其子逻辑算子对应的物理算子的输出格式，故可以结合已经为该逻辑算子的子逻辑算子选择出的物理算子C的输出格式以及与该逻辑算子等价的至少一个物理算子各自的输入格式，计算至少一个物理算子各自的基准代价，并从中选择基准代价符合设定要求的物理算子作为该逻辑算子对应的目标物理算子。

[0052] 值得说明的是，为了便于描述和区分，将已经为逻辑算子的子逻辑算子选择出的物理算子记为物理算子C，并将与逻辑算子等价的至少一个物理算子中的任一物理算子记为物理算子S。

[0053] 进一步，对任一物理算子S，在根据物理算子C的输出格式与物理算子S的输入格式计算物理算子S的基准代价时，若物理算子C的输出格式与物理算子S的输入格式相同，则直接计算物理算子S的代价作为物理算子S的基准代价；若物理算子C的输出格式与物理算子S的输入格式不相同，则先确定在物理算子C与物理算子S之间进行格式转换的物理算子D，并计算物理算子S的代价以及物理算子D的代价之和，作为物理算子S的基准代价。

[0054] 结合图1c，若物理算子C的输出格式为输出行组，物理算子S的输入格式为输入行，则物理算子D为行组转行物理算子，该行组转行物理算子用于将行组中关于行的描述转换为全局行的描述，这里全局行是指数据库领域中常规概念中的数据行。若物理算子C的输出格式为输出行，物理算子S的输入格式为输入行组，则物理算子D为逐行物化物理算子，该逐行物化物理算子用于将全局行的描述转换为行组中关于行的描述。

[0055] 更进一步，在上述计算物理算子S的代价时，可以结合与该物理算子S等价的逻辑算子所关联的行组的统计信息。可选地，可以根据逻辑算子所关联的行组的统计信息，对物理算子所需处理的行组数量进行过滤；根据过滤后剩余的行组数量计算物理算子S的代价。其中，通过统计信息对行组数量进行过滤，有利于减少参与代价计算所需的行组数量，有利于减少代价计算过程中的数据量，有利于节约资源，提高效率。值得说明的是，代价计算的详细过程可参考现有技术，本申请实施例对此不做过多说明。

[0056] 另外，考虑到本实施例中的物理算子是以行和行组为数据单位定义输入输出格式的物理算子，为了便于父物理算子能够成功调用其子物理算子，本实施例为物理算子提供了与其输出格式适配的调用接口，例如下一行接口、下一行组接口。基于上述物理算子的调用接口，在物理执行计划的执行过程中，具有父子关系的物理算子之间调用执行的方式包括以下几种情况：

[0057] 第一种情况：输入为行的物理算子作为父物理算子，可以调用作为子物理算子的行组转行物理算子的下一行接口，该行组转行物理算子作为父物理算子，可以继续调用作为其子物理算子的输出为行组的物理算子的下一行组接口，输出为行组的物理算子从支持列式存储的数据库103中读取指定行组数据。

[0058] 相应地，在反向返回查询结果时，输出为行组的物理算子可以将从支持列式存储的数据库103中读取行组数据，并返回给行组转行物理算子；行组转行物理算子将行组数据中的第一行数据返回给输入为行的物理算子，并在输入为行的物理算子每调用行组转行物理算子的下一行接口一次返回一行数据，直至行组数据中的数据均被返回为止。

[0059] 可选地，上述输出为行组的物理算子其输入可以是行，也可以是行组。若该输出为行组的物理算子的输入为行，则行转行组物理算子可以直接调用该输入为行输出为行组的物理算子。若该输出为行组的物理算子的输入为行组，则行转行组物理算子可以先调用输入为行输出为行组的物理算子，再由该输入为行输出为行组的物理算子调用该输出为行组输入也为行组的物理算子。

[0060] 第二种情况：输入为行组的物理算子作为父物理算子，可以调用作为其子物理算子的输出为行组的物理算子(子物理算子)的下一行组接口，输出为行组的物理算子从支持列式存储的数据库中读取指定行组数据。

[0061] 相应地，在反向返回查询结果时，输出为行组的物理算子将从支持列式存储的数据库中读取的行组数据返回给输入为行组的物理算子。

[0062] 第三种情况：输入为行组且具有物化属性的物理算子作为父物理算子，可以调用作为其子物理算子的逐行物化物理算子的下一行接口，逐行物化物理算子作为父物理算子，可以继续调用作为其子物理算子的输出为行的物理算子的下一行接口，输出为行的物理算子从支持列式存储的数据库中读取指定行数据。其中，若输入为行组且具有物化属性的物理算子所需的行组数据包括多行时，逐行物化物理算子需要多次调用输出为行的物理算子的下一行接口，以便通过多次调用获得多个行数据，形成最终行组数据。

[0063] 相应地，在反向返回查询结果时，输出为行的物理算子将从支持列式存储的数据库中读取的行数据返回给逐行物化物理算子，当返回的行数据的行数满足行组数据要求的行数时，逐行物化物理算子将行组数据返回给父物理算子是输入为行组且具有物化属性的物理算子。

[0064] 第四种情况：输入为行的物理算子作为父物理算子，可以调用作为其子物理算子的输出为行的物理算子的下一行接口，输出为行的物理算子从支持列式存储的数据库中读取指定行数据。

[0065] 相应地，在反向返回查询结果时，输出为行的物理算子直接将读取的行数据返回给输入为行的物理算子。

[0066] 在一可选实施方式，如图1a所示，数据库引擎102的一种内部实现结构包括：解析器1020、优化器1022和执行器1024。其中，解析器1020、优化器1022和执行器1024是数据库引擎102中的功能模块，在实现上，解析器1020、优化器1022和执行器1024可以是软件的程序模块，也可以是硬件的，例如基于FPGA或CPLD等实现。

[0067] 为了便于理解基于数据库查询语句的查询过程，下面结合图1a所示数据库引擎102的内部实现结构详细说明数据库查询过程。

[0068] 在数据库查询语句到达数据库引擎102之后，首先，解析器1020对数据库查询语句进行语法解析，将数据库查询语句解析成一颗语法树，然后将该语法树输入优化器1022。优化器1022负责对语法树进行优化处理以得到优化后的语法树，优化后的语法树包含至少一个逻辑执行计划，每个逻辑执行计划包括逻辑算子和逻辑表达式，语法树上的节点表示逻辑算子。

[0069] 如图1a所示，优化器1022包括优化功能和执行计划生成功能，但并不限于此。执行计划生成功能也可以作为独立模块单独存在。无论是哪种情况，物理执行计划的生成过程主要包括：针对语法树上的每个逻辑算子，从与逻辑算子等价的至少一个物理算子中选择目标物理算子；根据目标物理算子生成逻辑算子对应的物理执行计划。生成物理执行计划的详细过程可参见上述实施例，在此不再赘述。

[0070] 之后，针对至少一个逻辑执行计划生成至少一个物理执行计划，将至少一个物理执行计划送入执行器1024。执行器1024触发至少一个物理执行计划运行，使得至少一个物理算子按照所述父子关系自上而下调用执行并反向返回查询结果，将查询结果返回给客户端101。

[0071] 除上述系统实施例之外，本申请实施例还提供一些方法实施例。该方法实施例分别描述了物理执行计划的生成过程和运行过程。

[0072] 图2为本申请示例性实施例提供的一种执行计划的生成方法流程示意图。如图2所示，该方法包括：

[0073] 201、根据数据库查询语句生成语法树，该语法树上的节点表示逻辑算子。

[0074] 202、针对语法树上的每个逻辑算子，从与该逻辑算子等价的至少一个物理算子中选择目标物理算子，其中，至少一个物理算子的输入输出格式是以行和行组为数据单位定义的，行组是列式存储中若干行形成的数据单位。

[0075] 203、根据目标物理算子生成该逻辑算子对应的物理执行计划。

[0076] 在本实施例中，针对支持列式存储的数据库定义新的数据单位“行组”，并针对“行组”重新定义物理算子的输入输出格式从而形成新的物理算子“行组转行”以及“输入输出为行组”、“输出为行组”等新的物理算子，进而在新的物理算子的基础上提供适配的执行计划生成与执行方法，由于这些内容都是针对列式存储的特点提出的，更加适用于支持列式存储的数据库，在充分发挥列式存储优势的同时，能够进一步提高支持列式存储的数据库的查询效率。

[0077] 在一可选实施方式中，步骤202，即从与逻辑算子等价的至少一个物理算子中选择目标物理算子的一种实施方式包括：若逻辑算子是语法树上的非叶子节点，结合已经为逻辑算子的子逻辑算子选择出的物理算子C的输出格式和至少一个物理算子各自的输入格式，计算至少一个物理算子各自的基准代价；从至少一个物理算子中，选择基准代价符合设定要求的物理算子作为目标物理算子。若逻辑算子是语法树上的叶子节点，则计算至少一个物理算子各自的代价，并从中选择代价符合设定要求的物理算子作为目标物理算子。

[0078] 在一可选实施方式中，结合已经为逻辑算子的子逻辑算子选择出的物理算子C的输出格式和至少一个物理算子各自的输入格式，计算至少一个物理算子各自的基准代价的过程包括：对物理算子S，若物理算子C的输出格式与物理算子S的输入格式不相同，确定在物理算子C与物理算子S之间进行格式转换的物理算子D，并计算物理算子S的代价以及物理算子D的代价之和，作为物理算子S的基准代价；其中，物理算子S是至少一个物理算子中的任一物理算子。

[0079] 进一步，若物理算子C的输出格式为输出行组，物理算子S的输入格式为输入行，则物理算子D为行组转行物理算子，行组转行物理算子用于将行组中关于行的描述转换为全局行的描述。或者，若物理算子C的输出格式为输出行，物理算子S的输入格式为输入行组，则物理算子D为逐行物化物理算子，逐行物化物理算子用于将全局行的描述转换为行组中关于行的描述。

[0080] 进一步地，若物理算子C的输出格式与物理算子S的输入格式相同，计算物理算子S的代价作为物理算子S的基准代价。

[0081] 可选地，上述计算物理算子S的代价的一种实施方式包括：结合逻辑算子所关联的行组的统计信息，计算物理算子S的代价。例如，可以根据逻辑算子所关联的行组的统计信息，对物理算子所需处理的行组数量进行过滤；根据过滤后剩余的行组数量计算物理算子S的代价。其中，通过统计信息对行组数量进行过滤，有利于减少参与代价计算所需的行组数量，有利于减少代价计算过程中的数据量，有利于节约资源，提高效率。值得说明的是，代价计算的详细过程可参考现有技术，本申请实施例对此不做过多说明。

[0082] 图3a为本申请示例性实施例提供的一种执行计划的执行方法流程示意图。如图3a所示，该方法包括：

[0083] 301、获取执行树，该执行树包括具有父子关系的至少一个物理算子。

[0084] 302、运行该执行树，以使其中至少一个物理算子按照父子关系自上而下调用执行并反向返回查询结果。

[0085] 303、输出查询结果；其中，至少一个物理算子的输入输出格式是以行和行组为数据单位定义的，行组是列式存储中若干行形成的数据单位。

[0086] 其中，列式存储包括但不限于列式数据库，还可以包括行列混合的数据库。

[0087] 可选地，结合图3b所示物理算子之间的交互流程，对至少一个物理算子按照父子关系自上而下调用执行并反向返回查询结果的几种情况进行示例性说明。

[0088] 第一种情况：如图3b所示，输入为行的物理算子作为父物理算子，可以调用作为子物理算子的行组转行物理算子的下一行接口，该行组转行物理算子作为父物理算子，可以继续调用作为其子物理算子的输出为行组的物理算子的下一行组接口，输出为行组的物理算子从支持列式存储的数据库103中读取指定行组数据。

[0089] 相应地，在反向返回查询结果时，输出为行组的物理算子可以将从支持列式存储的数据库103中读取行组数据，并返回给行组转行物理算子；行组转行物理算子将行组数据中的第一行数据返回给输入为行的物理算子，并在输入为行的物理算子每调用行组转行物理算子的下一行接口一次返回一行数据，直至行组数据中的数据均被返回为止。

[0090] 可选地，上述输出为行组的物理算子其输入可以是行，也可以是行组。参见图3b中从左到右前三个物理算子之间的交互流程，若该输出为行组的物理算子的输入为行，则行转行组物理算子可以直接调用该输入为行输出为行组的物理算子。

[0091] 参见图3b中从左到右四个物理算子之间的交互流程，若该输出为行组的物理算子的输入为行组，则行转行组物理算子可以先调用输入为行输出为行组的物理算子，再由该输入为行输出为行组的物理算子调用该输出为行组输入也为行组的物理算子。

[0092] 第二种情况：如图3b所示最右侧两个算子之间的交互流程，输入为行组的物理算子作为父物理算子，可以调用作为其子物理算子的输出为行组的物理算子(子物理算子)的下一行组接口，输出为行组的物理算子从支持列式存储的数据库中读取指定行组数据。

[0093] 相应地，在反向返回查询结果时，输出为行组的物理算子将从支持列式存储的数据库中读取的行组数据返回给输入为行组的物理算子。

[0094] 除上述两种情况之外，还有另外一些情况，在图3b中未示出，下面对其中两种情况进行简单说明。

[0095] 第三种情况：输入为行组且具有物化属性的物理算子作为父物理算子，可以调用作为其子物理算子的逐行物化物理算子的下一行接口，逐行物化物理算子作为父物理算子，可以继续调用作为其子物理算子的输出为行的物理算子的下一行接口，输出为行的物理算子从支持列式存储的数据库中读取指定行数据。其中，若输入为行组且具有物化属性的物理算子所需的行组数据包括多行时，逐行物化物理算子需要多次调用输出为行的物理算子的下一行接口，以便通过多次调用获得多个行数据，形成最终行组数据。

[0096] 相应地，在反向返回查询结果时，输出为行的物理算子将从支持列式存储的数据库中读取的行数据返回给逐行物化物理算子，当返回的行数据的行数满足行组数据要求的行数时，逐行物化物理算子将行组数据返回给父物理算子是输入为行组且具有物化属性的物理算子。

[0097] 第四种情况：输入为行的物理算子作为父物理算子，可以调用作为其子物理算子的输出为行的物理算子的下一行接口，输出为行的物理算子从支持列式存储的数据库中读取指定行数据。

[0098] 相应地，在反向返回查询结果时，输出为行的物理算子直接将读取的行数据返回给输入为行的物理算子。

[0099] 需要说明的是，上述实施例所提供方法的各步骤的执行主体均可以是同一设备，或者，该方法也由不同设备作为执行主体。比如，步骤201至步骤203的执行主体可以为设备A；又比如，步骤201和202的执行主体可以为设备A，步骤203的执行主体可以为设备B；等等。

[0100] 另外，在上述实施例及附图中的描述的一些流程中，包含了按照特定顺序出现的多个操作，但是应该清楚了解，这些操作可以不按照其在本文中出现的顺序来执行或并行执行，操作的序号如201、202等，仅仅是用于区分开各个不同的操作，序号本身不代表任何的执行顺序。另外，这些流程可以包括更多或更少的操作，并且这些操作可以按顺序执行或并行执行。需要说明的是，本文中的“第一”、“第二”等描述，是用于区分不同的消息、设备、模块等，不代表先后顺序，也不限定“第一”和“第二”是不同的类型。

[0101] 图4为本申请示例性实施例提供的一种数据库引擎的结构示意图。如图4所示，该引擎包括：存储器401和处理器402。

[0102] 存储器401，用于存储计算机程序。处理器402，与存储器401耦合，用于执行存储器401中的计算机程序，以用于：根据数据库查询语句生成语法树，语法树上的节点表示逻辑算子；针对语法树上的每个逻辑算子，从与逻辑算子等价的至少一个物理算子中选择目标物理算子；根据目标物理算子生成逻辑算子对应的物理执行计划；其中，至少一个物理算子的输入输出格式是以行和行组为数据单位定义的，行组是列式存储中若干行形成的数据单位。

[0103] 其中，列式存储包括但不限于列式数据库，还可以包括行列混合的数据库。

[0104] 在一可选实施方式中，处理器402在选择目标物理算子时，具体用于：若逻辑算子是语法树上的非叶子节点，结合已经为逻辑算子的子逻辑算子选择出的物理算子C的输出格式和至少一个物理算子各自的输入格式，计算至少一个物理算子各自的基准代价；从至少一个物理算子中，选择基准代价符合设定要求的物理算子作为目标物理算子；或者，若逻辑算子是语法树上的叶子节点，则计算至少一个物理算子各自的代价，并从中选择代价符合设定要求的物理算子作为目标物理算子。

[0105] 在一可选实施方式中，处理器402在计算基准代价时，具体用于：

[0106] 对物理算子S，若物理算子C的输出格式与物理算子S的输入格式不相同，确定在物理算子C与物理算子S之间进行格式转换的物理算子D，并计算物理算子S的代价以及物理算子D的代价之和，作为物理算子S的基准代价；

[0107] 其中，物理算子S是至少一个物理算子中的任一物理算子。

[0108] 在一可选实施方式中，若物理算子C的输出格式为输出行组，物理算子S的输入格式为输入行，则物理算子D为行组转行物理算子，行组转行物理算子用于将行组中关于行的描述转换为全局行的描述；或者，若物理算子C的输出格式为输出行，物理算子S的输入格式为输入行组，则物理算子D为逐行物化物理算子，行组转行物理算子用于将全局行的描述转换为行组中关于行的描述。

[0109] 在一可选实施方式中，处理器402在计算物理算子S的代价时，具体用于：结合逻辑算子所关联的行组的统计信息，计算物理算子S的代价。

[0110] 进一步，处理器402在计算物理算子S的代价时，具体用于：根据逻辑算子所关联的行组的统计信息，对物理算子所需处理的行组数量进行过滤；根据过滤后剩余的行组数量计算物理算子S的代价。

[0111] 进一步，如图4所示，该数据库引擎还包括：通信组件403、电源组件404等其它组件。图4中仅示意性给出部分组件，并不意味着数据库引擎只包括图4所示组件。

[0112] 相应地，本申请实施例还提供一种存储有计算机程序的计算机可读存储介质，计算机程序被执行时能够实现上述执行计划的生成方法实施例中的各步骤。

[0113] 图5为本申请示例性实施例提供的另一种数据库引擎的结构示意图。如图5所示，该引擎包括：存储器501和处理器502。

[0114] 存储器501，用于存储计算机程序。处理器502，与存储器501耦合，用于执行存储器501中的计算机程序，以用于：获取执行树，所述执行树包括具有父子关系的至少一个物理算子；运行所述执行树，以使其中至少一个物理算子按照父子关系自上而下调用执行并反向返回查询结果；输出查询结果；其中，至少一个物理算子的输入输出格式是以行和行组为数据单位定义的，行组是列式存储中若干行形成的数据单位。其中，列式存储包括但不限于列式数据库，还可以包括行列混合的数据库。

[0115] 在一可选实施方式中，处理器502在运行执行树时，具体用于：控制输入为行的物理算子调用行组转行物理算子的下一行接口，行组转行物理算子调用输出为行组的物理算子的下一行组接口，所述输出为行组的物理算子从支持列式存储的数据库中读取指定行组数据。

[0116] 在一可选实施方式中，处理器502还用于：在反向返回查询结果的过程中，控制输出为行组的物理算子向行组转行物理算子返回行组数据；行组转行物理算子将所述行组数据中的第一行数据返回给输入为行的物理算子，并在所述输入为行的物理算子每调用行组转行物理算子的下一行接口一次返回一行数据，直至所述行组数据中的数据均被返回为止。

[0117] 在一可选实施方式中，处理器502在运行执行树时，具体用于：控制输入为行组的物理算子调用输出为行组的物理算子的下一行组接口，所述输出为行组的物理算子从支持列式存储的数据库中读取指定行组数据。

[0118] 在一可选实施方式中，处理器502在运行执行树时，具体用于：控制输入为行组且具有物化属性的物理算子调用逐行物化物理算子的下一行接口，所述逐行物化物理算子调用输出为行的物理算子的下一行接口，所述输出为行的物理算子从支持列式存储的数据库中读取指定行数据。

[0119] 在一可选实施方式中，处理器502在运行执行树时，具体用于：控制输入为行的物理算子调用输出为行的物理算子的下一行接口，所述输出为行的物理算子从支持列式存储的数据库中读取指定行数据。

[0120] 进一步，如图5所示，该数据库引擎还包括：通信组件503、电源组件504等其它组件。图5中仅示意性给出部分组件，并不意味着数据库引擎只包括图5所示组件。

[0121] 相应地，本申请实施例还提供一种存储有计算机程序的计算机可读存储介质，计算机程序被执行时能够实现上述执行计划的执行方法实施例中的各步骤。

[0122] 上述图4和图5中的存储器还可被配置为存储其它各种数据以支持在数据库引擎上的操作。这些数据的示例包括用于在数据库引擎上操作的任何应用程序或方法的指令，联系人数据，电话簿数据，消息，图片，视频等。

[0123] 上述图4和图5中的存储器可以由任何类型的易失性或非易失性存储设备或者它们的组合实现，如静态随机存取存储器(SRAM)，电可擦除可编程只读存储器(EEPROM)，可擦除可编程只读存储器(EPROM)，可编程只读存储器(PROM)，只读存储器(ROM)，磁存储器，快闪存储器，磁盘或光盘。

[0124] 上述图4和图5中的通信组件被配置为便于通信组件所在设备和其他设备之间有线或无线方式的通信。通信组件所在设备可以接入基于通信标准的无线网络，如WiFi，2G或3G，或它们的组合。在一个示例性实施例中，通信组件经由广播信道接收来自外部广播管理系统的广播信号或广播相关信息。在一个示例性实施例中，通信组件还包括近场通信(NFC)模块，以促进短程通信。例如，在NFC模块可基于射频识别(RFID)技术，红外数据协会(IrDA)技术，超宽带(UWB)技术，蓝牙(BT)技术和其他技术来实现。

[0125] 上述图4和图5中的电源组件，为电源组件所在设备的各种组件提供电力。电源组件可以包括电源管理系统，一个或多个电源，及其他与为电源组件所在设备生成、管理和分配电力相关联的组件。

[0126] 本领域内的技术人员应明白，本发明的实施例可提供为方法、系统、或计算机程序产品。因此，本发明可采用完全硬件实施例、完全软件实施例、或结合软件和硬件方面的实施例的形式。而且，本发明可采用在一个或多个其中包含有计算机可用程序代码的计算机可用存储介质(包括但不限于磁盘存储器、CD‑ROM、光学存储器等)上实施的计算机程序产品的形式。

[0127] 本发明是参照根据本发明实施例的方法、设备(系统)、和计算机程序产品的流程图和/或方框图来描述的。应理解可由计算机程序指令实现流程图和/或方框图中的每一流程和/或方框、以及流程图和/或方框图中的流程和/或方框的结合。可提供这些计算机程序指令到通用计算机、专用计算机、嵌入式处理机或其他可编程数据处理设备的处理器以产生一个机器，使得通过计算机或其他可编程数据处理设备的处理器执行的指令产生用于实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能的装置。

[0128] 这些计算机程序指令也可存储在能引导计算机或其他可编程数据处理设备以特定方式工作的计算机可读存储器中，使得存储在该计算机可读存储器中的指令产生包括指令装置的制造品，该指令装置实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能。

[0129] 这些计算机程序指令也可装载到计算机或其他可编程数据处理设备上，使得在计算机或其他可编程设备上执行一系列操作步骤以产生计算机实现的处理，从而在计算机或其他可编程设备上执行的指令提供用于实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能的步骤。

[0130] 在一个典型的配置中，计算设备包括一个或多个处理器(CPU)、输入/输出接口、网络接口和内存。

[0131] 内存可能包括计算机可读介质中的非永久性存储器，随机存取存储器(RAM)和/或非易失性内存等形式，如只读存储器(ROM)或闪存(flash RAM)。内存是计算机可读介质的示例。

[0132] 计算机可读介质包括永久性和非永久性、可移动和非可移动媒体可以由任何方法或技术来实现信息存储。信息可以是计算机可读指令、数据结构、程序的模块或其他数据。计算机的存储介质的例子包括，但不限于相变内存(PRAM)、静态随机存取存储器(SRAM)、动态随机存取存储器(DRAM)、其他类型的随机存取存储器(RAM)、只读存储器(ROM)、电可擦除可编程只读存储器(EEPROM)、快闪记忆体或其他内存技术、只读光盘只读存储器(CD‑ROM)、数字多功能光盘(DVD)或其他光学存储、磁盒式磁带，磁带磁磁盘存储或其他磁性存储设备或任何其他非传输介质，可用于存储可以被计算设备访问的信息。按照本文中的界定，计算机可读介质不包括暂存电脑可读媒体(transitorymedia)，如调制的数据信号和载波。

[0133] 还需要说明的是，术语“包括”、“包含”或者其任何其他变体意在涵盖非排他性的包含，从而使得包括一系列要素的过程、方法、商品或者设备不仅包括那些要素，而且还包括没有明确列出的其他要素，或者是还包括为这种过程、方法、商品或者设备所固有的要素。在没有更多限制的情况下，由语句“包括一个……”限定的要素，并不排除在包括所述要素的过程、方法、商品或者设备中还存在另外的相同要素。

[0134] 以上所述仅为本申请的实施例而已，并不用于限制本申请。对于本领域技术人员来说，本申请可以有各种更改和变化。凡在本申请的精神和原理之内所作的任何修改、等同替换、改进等，均应包含在本申请的权利要求范围之内。