一种代价优化器与代价估计的方法及其设备

技术领域

本申请涉及计算机领域，尤其涉及一种代价优化器与代价估计的方法及其设备。

背景技术

代价优化器(CBO，Cost Based Optimizer)是数据库系统中的核心部件，由于对数据库系统的性能影响显著，因而在现代数据库系统中占据重要地位。代价优化器的核心是代价估计模型，用于对数据库系统生成的执行计划进行代价估计，从而选择最优的执行计划。估计模型的好坏影响最终执行计划的优劣。代价优化器基于目标数据的统计信息对执行计划进行优化，统计信息的完整性和精确性直接影响到估计模型对执行计划的估计。

一般代价优化步骤和不足：

进行代价优化需要统计信息，因此收集完整而精确的统计信息是所有代价优化器必不可少的环节。代价优化器优化的目标是生成最优的执行计划。在数据库系统中，执行计划一般用操作树表示，操作树由不同类型的操作构成，典型的操作树包括扫表、选择、过滤、聚合、连接、投影等。基于统计信息，代价优化器可以借助代价估算模型，对执行计划的每一步操作进行代价估算，并从所有可能的执行计划中选取整体代价最小者作为最终的执行计划，由此就完成了整个代价优化的过程。从中可知，代价优化器的核心在于基于统计信息的代价估算，统计信息是代价优化器的基础。

现有的代价优化器需要统计信息，在缺少必要统计信息的情况下无法完成代价优化，例如，运行时创建的临时表或者存在子查询的场景，在编译阶段不能确定其统计信息，因此无法利用代价优化。另一方面，当代价优化器被应用到大数据系统中时，处理海量数据成为典型的应用场景，对于海量数据的统计信息收集，代价巨大，甚至成为应用代价优化器的瓶颈所在。最后，对于给定的数据集，并非需要对全量数据收集统计信息，基于部分统计信息也可能得到最优计划。在统计信息不完整或者不可获取的情况下，现有代价优化器失效。

申请内容

本申请的一个目的是提供一种代价优化器与代价估计的方法及其设备，解决现有技术中统计信息不完备时无法进行代价估计的问题。

根据本申请的一个方面，提供了一种代价估计的方法，该方法包括：

判断获取到的统计信息是否完备，若否，则根据依赖于所述统计信息的操作树的操作类型确定对应的代价估计方式；

基于所述代价估计方式确定所述对应操作类型的代价估计；

根据依赖于所述统计信息的操作类型对应的代价估计及未依赖于统计信息的操作类型对应的代价估计确定所述操作树的累积代价估计。

进一步地，所述依赖于所述统计信息的操作树的操作类型包括扫表操作、过滤操作、连接操作和聚合操作。

进一步地，所述方法还包括：

根据所述累积代价优化结构化查询语言语句对应的执行计划。

进一步地，基于所述代价估计方式确定所述对应操作类型的代价估计，包括：

根据数据集的记录数确定扫表操作的代价估计；

根据过滤谓词的类型确定过滤条件的选择率之后，根据所述选择率确定过滤操作的代价估计；

根据确定的连接结果集的记录数确定连接操作的代价估计；

根据聚合字段及聚合函数确定聚合字段的聚合率，根据所述聚合率确定聚合操作的代价估计。

进一步地，根据过滤谓词的类型确定过滤条件的选择率，包括：

判断过滤谓词的类型对应的计算选择率的对象是否可获取，若否，则指定S＝1/指定值。

进一步地，判断过滤谓词的类型对应的计算选择率的对象是否可获取，若否，则指定S＝1/指定值，包括：

当过滤谓词的类型为恒等谓词时，判断所述过滤操作的异值数是否可获取，若否，则指定S＝1/指定值；

当过滤谓词的类型为范围谓词时，若谓词的字段的极值或异值数未能获取，则选择率S＝1/指定值；

当过滤谓词的类型为判空谓词时，判断谓词字段的空值数是否可获取，若否，则确定所述过滤条件的选择率为S＝1/指定值。

进一步地，根据过滤谓词的类型确定过滤条件的选择率，包括：

当过滤谓词的类型为like时，所述过滤条件的选择率为1/指定值；

当过滤谓词的类型为和级联谓词时，根据级联谓词的选择率的乘积与和级联谓词中过滤率最小值确定过滤条件的选择率；

当过滤谓词的类型为或级联谓词时，根据所述或级联谓词对应的级联谓词的选择率确定过滤条件的选择率。

进一步地，根据确定的连接结果集的记录数确定连接操作的代价估计，包括：

当相连接的左表和右表的连接字段的异值数不可获取时，基于连接字段的连接类型确定连接结果集的记录数。

进一步地，基于连接字段的连接类型确定连接结果集的记录数，包括：

当连接字段的连接类型为主键外键形式连接，则根据外键字段的记录数与主键字段的过滤条件的选择率确定连接结果集的记录数；

当连接字段的连接类型为内连接，则将相连接的左表的记录数及右表的记录数中的最大值作为连接结果集的记录数；

当连接字段的连接类型为叉乘连接，则将相连接的左表的记录数及右表的记录数的乘积作为连接结果集的记录数；

当连接字段的连接类型为左外连接或右外连接，则将对应的相连接的左表的记录数或右表的记录数作为连接结果集的记录数；

当连接字段的连接类型为全连接，则将相连接的左表的记录数及右表的记录数的累加作为连接结果集的记录数。

进一步地，根据聚合字段及聚合函数确定聚合字段的聚合率，包括：

当聚合字段的集合中至少存在一个主键时，聚合字段的聚合率为1；

当聚合字段对应的聚合函数为简单聚合函数时，

其中，R_agg为聚合字段的聚合率，n为聚合字段的集合中聚合字段的个数；

当聚合字段对应的聚合函数为Rollup时，

其中，R_agg为聚合字段的聚合率，n为聚合字段的集合中聚合字段的个数，k为正整数；

当聚合字段对应的聚合函数为Cube时，

其中，R_agg为聚合字段的聚合率，n为聚合字段的集合中聚合字段的个数，k为正整数。

根据本申请的另一方面，还提供了一种代价估计的设备，所述设备包括：

判断装置，用于判断获取到的统计信息是否完备，若否，则根据依赖于所述统计信息的操作树的操作类型确定对应的代价估计方式；

确定装置，用于基于所述代价估计方式确定所述对应操作类型的代价估计；

估算装置，用于根据依赖于所述统计信息操作类型对应的代价估计及未依赖于统计信息的操作类型对应的代价估计确定所述操作树的累积代价估计。

进一步地，所述依赖于所述统计信息的操作树的操作类型包括扫表操作、过滤操作、连接操作和聚合操作。

进一步地，所述设备还包括：

执行装置，用于根据所述累积代价优化结构化查询语言语句对应的执行计划。

进一步地，上述设备中，所述确定装置用于：

根据数据集的记录数确定扫表操作的代价估计；

根据过滤谓词的类型确定过滤条件的选择率之后，根据所述选择率确定过滤操作的代价估计；

根据确定的连接结果集的记录数确定连接操作的代价估计；

根据聚合字段及聚合函数确定聚合字段的聚合率，根据所述聚合率确定聚合操作的代价估计。

进一步地，上述设备中，所述确定装置用于：

判断过滤谓词的类型对应的计算选择率的对象是否可获取，若否，则指定S＝1/指定值。

进一步地，所述确定装置用于：

当过滤谓词的类型为恒等谓词时，判断所述过滤操作的异值数是否可获取，若否，则指定S＝1/指定值；

当过滤谓词的类型为范围谓词时，若谓词的字段的极值或异值数未能获取，则选择率S＝1/指定值；

当过滤谓词的类型为判空谓词时，判断谓词字段的空值数是否可获取，若否，则确定所述过滤条件的选择率为S＝1/指定值。

进一步地，所述确定装置用于：

当过滤谓词的类型为like时，所述过滤条件的选择率为1/指定值；

当过滤谓词的类型为和级联谓词时，根据级联谓词的选择率的乘积与和级联谓词中过滤率最小值确定过滤条件的选择率；

当过滤谓词的类型为或级联谓词时，根据所述或级联谓词对应的级联谓词的选择率确定过滤条件的选择率。

进一步地，所述确定装置用于：

当相连接的左表和右表的连接字段的异值数不可获取时，基于连接字段的连接类型确定连接结果集的记录数。

进一步地，所述确定装置用于：

当连接字段的连接类型为主键外键形式连接，则根据外键字段的记录数与主键字段的过滤条件的选择率确定连接结果集的记录数；

当连接字段的连接类型为内连接，则将相连接的左表的记录数及右表的记录数中的最大值作为连接结果集的记录数；

当连接字段的连接类型为叉乘连接，则将相连接的左表的记录数及右表的记录数的乘积作为连接结果集的记录数；

当连接字段的连接类型为左外连接或右外连接，则将对应的相连接的左表的记录数或右表的记录数作为连接结果集的记录数；

当连接字段的连接类型为全连接，则将相连接的左表的记录数及右表的记录数的累加作为连接结果集的记录数。

进一步地，所述确定装置用于：

当聚合字段的集合中至少存在一个主键时，聚合字段的聚合率为1；

当聚合字段对应的聚合函数为简单聚合函数时，

其中，R_agg为聚合字段的聚合率，n为聚合字段的集合中聚合字段的个数；

当聚合字段对应的聚合函数为Rollup时，

其中，R_agg为聚合字段的聚合率，n为聚合字段的集合中聚合字段的个数，k为正整数；

当聚合字段对应的聚合函数为Cube时，

其中，R_agg为聚合字段的聚合率，n为聚合字段的集合中聚合字段的个数，k为正整数。

根据本申请再一个方面，还提供了一种代价优化器，其中，所述代价优化器用于：

生成原始执行计划；

判断获取到的统计信息是否完备，若是，则根据基于统计信息的第一代价估算模型估算代价，若否，则根据基于第一代价估算模型进行优化的第二代价估算模型估算代价；

根据所述第一代价估算模型估算的代价或所述第二代价估算模型估算的代价生成最优执行计划。

进一步地，基于第一代价估算模型进行优化的第二代价估算模型，包括：

根据依赖于所述统计信息的操作树的操作类型确定对应的代价估计方式；

基于所述代价估计方式确定所述对应操作类型的代价估计；

根据依赖于所述统计信息操作类型对应的代价估计及未依赖于统计信息的操作类型对应的代价估计确定所述操作树的累积代价估计。

根据本申请再一个方面，还提供了一种基于计算的设备，包括：

处理器；以及

被安排成存储计算机可执行指令的存储器，所述可执行指令在被执行时使所述处理器：

判断获取到的统计信息是否完备，若否，则根据依赖于所述统计信息的操作树的操作类型确定对应的代价估计方式；

基于所述代价估计方式确定所述对应操作类型的代价估计；

根据依赖于所述统计信息操作类型对应的代价估计及未依赖于统计信息的操作类型对应的代价估计确定所述操作树的累积代价估计。

与现有技术相比，本申请通过判断获取到的统计信息是否完备，若否，则根据依赖于所述统计信息的操作树的操作类型确定对应的代价估计方式；基于所述代价估计方式确定所述对应操作类型的代价估计；根据依赖于所述统计信息操作类型对应的代价估计及未依赖于统计信息的操作类型对应的代价估计确定所述操作树的累积代价估计。从而解决传统代价优化器对于运行时创建临时表和子查询无法进行代价估算，对海量数据的场景受数据规模限制的问题，进一步地，根据所述累积代价估计优化结构化查询语言语句对应的执行计划，可应用于数据库系统中结构化查询语言(Structured QueryLanguage，SQL)的优化，提高SQL的代价优化器代价估计的准确性，从而生成性能更好的执行计划。

附图说明

通过阅读参照以下附图所作的对非限制性实施例所作的详细描述，本申请的其它特征、目的和优点将会变得更明显：

图1示出根据本申请一个方面提供的一种代价估计的方法流程示意图；

图2示出本申请中的一实施例的一颗典型的操作树示意图；

图3示出根据本申请另一个方面提供的一种代价估计的设备结构示意图；

图4示出根据本申请再一个方面提供的一种改进的代价优化器示意图。

附图中相同或相似的附图标记代表相同或相似的部件。

具体实施方式

下面结合附图对本申请作进一步详细描述。

在本申请一个典型的配置中，终端、服务网络的设备和可信方均包括一个或多个处理器(CPU)、输入/输出接口、网络接口和内存。

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

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

图1示出根据本申请一个方面提供的一种代价估计的方法流程示意图，所述方法包括：步骤S11～步骤S13，其中，在步骤S11中，判断获取到的统计信息是否完备，若否，则根据依赖于所述统计信息的操作树的操作类型确定对应的代价估计方式；在步骤S12中，基于所述代价估计方式确定所述对应操作类型的代价估计；在步骤S13中，根据依赖于所述统计信息操作类型对应的代价估计及未依赖于统计信息的操作类型对应的代价估计确定所述操作树的累积代价估计。从而解决传统代价优化器对于运行时创建临时表和子查询无法进行代价估算，对海量数据的场景受数据规模限制的问题，进一步地，本申请所述方法包括：根据所述累积代价估计优化结构化查询语言语句对应的执行计划。本申请所述的代价估计的方法应用于数据库系统中SQL的优化，提高SQL的代价优化器代价估计的准确性，从而生成性能更好的执行计划。

在本申请一实施例中，基于本申请所述的代价估计的方法的一种改进的代价优化器，可以基于不完备的统计信息对执行计划进行代价优化。当统计信息完备时，利用现有的代价估算模型进行估算，基于估算结果生成最优执行计划；当统计信息不完备时，通过本申请所述的代价估计的方法，对相应操作进行代价估算，并基于估算结果生成最优执行计划。

在步骤S11中，判断获取到的统计信息是否完备，若否，则根据依赖于所述统计信息的操作树的操作类型确定对应的代价估计方式；进一步地，所述依赖于所述统计信息的操作树的操作类型包括扫表操作、过滤操作、连接操作和聚合操作。在此，一棵操作树由不同的操作符构成，每一种操作符代表一类操作，基本的操作包括扫表、过滤、连接、投影、聚合、选择等，如图2所示的一颗典型的操作树示意图，调整操作树上的不同操作，估算每一步操作的代价，最终生成一颗累积代价最小的操作树，生成执行计划，而不同操作类型的代价对统计信息的依赖不同，比如，扫表操作、过滤操作、连接操作、聚合操作的代价需要依赖统计信息，投影操作、选择操作的代价不依赖于统计信息。因此需要确定操作类型，采用对应的代价估计方式，进行每一步操作的代价估计。判断获取到的统计信息是否完备，若否，则对依赖于统计信息的操作类型的代价估算方法进行改进。

接着，在步骤S12中，确定哪些操作类型需要改进的代价估计方式，进行确定对应操作类型的代价估计；最后，在步骤S13中，根据依赖于所述统计信息操作类型对应的代价估计及未依赖于统计信息的操作类型对应的代价估计确定所述操作树的累积代价估计。比如，将依赖于统计信息的扫表操作、过滤操作、连接操作和聚合操作的代价估计与不依赖于统计信息的投影操作和选择操作的代价估计进行累积得到操作树的代价估计，进而生成最优执行计划。

在本申请一实施例中，在步骤S12中，根据数据集的记录数确定扫表操作的代价估计；根据过滤谓词的类型确定过滤条件的选择率之后，根据所述选择率确定过滤操作的代价估计；根据确定的连接结果集的记录数确定连接操作的代价估计；根据聚合字段及聚合函数确定聚合字段的聚合率，根据所述聚合率确定聚合操作的代价估计。在此，扫表操作的代价与数据集的大小相关，数据集越大，其扫表代价越高，因此可以根据数据集的记录数确定扫表操作的代价估计；过滤操作的代价与过滤条件的选择率相关，选择率又根据过滤条件计算得到，而过滤谓词类型不同时，选择率确定的方式也不同。连接操作的代价与参与连接的数据集大小有关，也与连接后结果集的大小有关，因此，先确定连接结果集的记录数，再根据记录数确定连接操作的代价估计。对于聚合操作，聚合操作的代价与参与聚合的数据量大小和聚合字段的聚合率有关，聚合字段的聚合率需要根据聚合字段的异值数计算得到，因此，需要计算聚合字段的异值数。

在本申请一实施例中，将数据集的记录数记为RC(Row Count)，数据集的大小(记为S)与RC成正比例关系，即：S∝RC，因此在本申请实施例中，可以使用RC代表数据集的大小，则扫表操作的代价为

cost＝Op·getOriginalCost(RC)；

表示可以根据数据集的记录数确定扫表操作的代价估计，其中，所述Op表示想要估计代价的目标操作，getOriginalCost表示使用现有方法和RC来估计代价。

在本申请一实施例中，在过滤操作中，过滤操作的代价与谓词的选择率相关，不同形式的谓词，其选择率的估算算法不同，可以通过判断过滤谓词的类型对应的计算选择率的对象是否可获取，若否，则指定S＝1/指定值。在此，过滤谓词的类型对应的计算选择率的对象包括异值数、谓词字段的极值、谓词字段的空值数，指定值根据具体的实际应用而定，为大于1的正数，在不同过滤谓词的类型中，可能相同也可能不同，例如，S＝1/5，S＝1/9等。

进一步地，过滤操作的代价与过滤条件的选择率有关，选择率又根据过滤条件计算得到，在本申请实施例中，定义选择率为S＝结果集记录总数/参与过滤操作记录总数。由此，根据过滤谓词的类型进行以下讨论：

过滤谓词的类型对应的计算选择率的对象不可获取时，当过滤谓词的类型为恒等谓词时，判断所述过滤操作的异值数是否可获取，若否，则指定S＝1/指定值；在此，恒等谓词(Equal、＝)时，若异值数(NDV)可获取，则选择率S＝1/NDV，当异值数不可获取时，S_{(恒等谓词)}＝1/10，其中，S＝1/10是根据经验值确定，也可以为其他指定值。当过滤谓词是不等谓词(Non-Equal、！＝)，恒等与不等是一对互补谓词，即其选择率之和应该为1，因此，不等谓词的选择率为S_{(不等谓词)}＝1-S_{(恒等谓词)}。

当过滤谓词的类型为范围谓词时，其中，范围谓词包括一边区间范围：形如>、<、>＝、<＝，两值区间范围：between，是否在集合内如In，若谓词的字段的极值或异值数未能获取，则选择率S＝1/指定值；在此，谓词形如>、<、>＝、<＝时，选择率根据谓词字段的极值确定，当极值不可获取时，定义S＝1/3。谓词形如between时，即过滤条件在两值之间，当极值不可获取时，定义其S＝1/9。当谓词形如In，C＝{v₁，v₂，…，v_n}，即过滤条件表述为：col>1，v₂，…，v_n)，n＝|C|，其中，v₁，v₂，…，v_n为过滤值，C为过滤值的集合，n为集合C中过滤值的个数，过滤时判断待过滤的数据是否属于该集合C内的值。当异值数不可获取时，定义S＝1/5。

当过滤谓词的类型为判空谓词时，判断谓词字段的空值数是否可获取，若否，则确定所述过滤条件的选择率为S＝1/指定值。在此，判空谓词时，选择率需要根据谓词字段的空值数估算，当空值数不可获取时，定义S＝1/10。对于非空谓词，其与判空谓词为互补谓词，则选择率S_非空谓词＝1-S_判空谓词。

过滤谓词的类型还包括以下几种情况：当过滤谓词的类型为like时，所述过滤条件的选择率为1/指定值；在此，当过滤谓词的类型为like时，定义选择率＝1/5。当过滤谓词的类型为和级联谓词时，根据级联谓词的选择率的乘积与和级联谓词中过滤率最小值确定过滤条件的选择率；在此，And级联的过滤谓词，记级联谓词为P＝P₁ANDP₂AND...P_n，为防止估算误差被级联放大，在本申请实施例中，通过以下方式估算其选择率：

其中，α定义了And级联过滤谓词过滤率的最小值，可以根据实际情况调整α的值；selectivity为选择率，上述公式表示And级联过滤谓词的级联的选择率值与And级联过滤谓词过滤率的最小值中的最大值作为选择率。

当过滤谓词的类型为或级联谓词时，根据所述或级联谓词对应的级联谓词的选择率确定过滤条件的选择率。在此，记或级联的过滤谓词为

P＝P₁ORP₂OR...P_n

则选择率按照如下方式确定：

通过以上分过滤谓词的类型进行讨论其对应的选择率，根据确定的选择率可计算过滤操作的代价：

cost＝Op·getOriginalCost(selectivity)

需要说明的是，本领域技术人员应能理解，上述实施例中出现的S＝1/指定值中的具体数值仅为举例，且在上述实施例中每种过滤谓词的选择率可以根据实际情况做调整，也可以通过参数传递等方式动态改变。

在本申请一实施例中，根据确定的连接结果集的记录数确定连接操作的代价估计之前，根据相连接的左表和右表的连接字段的异值数确定连接结果集的记录数。在此，参与连接的左表记为T_left，其记录数为RC_left，异值数为NDV_left；右表记为T_right，其记录数为RC_right，异值数为NDV_right；结果集的记录数记为RC_result。参与连接的左右表均有其他操作构成，例如选择操作、过滤操作、扫表操作等，分别构成了左边操作树和右边操作树，操作树上的每一种操作，其代价均可以估算得到，因此，参与连接的数据集大小(即RC_left和RC_right)可由其他对操作的估算和已有的计算方法计算得到。

在本申请一实施例中，当相连接的左表和右表的连接字段的异值数不可获取时，基于连接字段的连接类型确定连接结果集的记录数。具体根据连接字段的类型做如下讨论：

当连接字段的连接类型为主键外键形式连接，则根据外键字段的记录数与主键字段的过滤条件的选择率确定连接结果集的记录数；在此，如果连接字段分别是主键-外键形式连接：

RC_result＝RC_fk×selectivity(PK)

其中，RC_fk为RC_left和RC_right之一，是外键字段记录数，selectivity(PK)表示主键字段的选择率。如果主键字段存在过滤条件，则最终连接的结果也会受该过滤条件的影响，因此，这里乘以主键字段过滤条件的选择率，当不存在过滤条件时，则其值为1。

如果连接字段非主键-外键连接，则又可分为以下情况：

当连接字段的连接类型为内连接，则将相连接的左表的记录数及右表的记录数中的最大值作为连接结果集的记录数；在此，在本申请一实施例中，将结果记录数估算为连接记录数的最大值：

RC_result＝max(RC_left，RC_right)

即结果记录数为RC_left和RC_right中的最大值。

当连接字段的连接类型为叉乘连接，则将相连接的左表的记录数及右表的记录数的乘积作为连接结果集的记录数；对于叉乘连接，其记录数为连接记录数之乘积，即：RC_result＝RC_left×RC_right。

当连接字段的连接类型为左外连接或右外连接，则将对应的相连接的左表的记录数或右表的记录数作为连接结果集的记录数；在此，当是左外连接时，其记录数为T_left的记录数，即RC_result＝RC_left。当是右外连接时，其记录数为T_right的记录数，即RC_result＝RC_right。

当连接字段的连接类型为全连接，则将相连接的左表的记录数及右表的记录数的累加作为连接结果集的记录数。在此，全外连接时，其记录数为T_left和T_right的记录数之和，即：RC_result＝RC_left+RC_right。

最终，连接操作的代价为：cost＝Op.getOriginalCost(RC_left，RC_right，RC_result)。

在本申请一实施例中，对于聚合操作过程，聚合操作的代价与参与聚合的数据量大小和聚合字段的聚合率有关，可以定义聚合率为：

聚合字段的聚合率需要根据聚合字段的异值数计算得到，当聚合字段的异值数无法获取时，进行如下讨论：

记C＝{c₁，c₂，...，c_n}，n＝|C|，其中，c₁、c₂和c_n为聚合字段。

当聚合字段的集合C中至少存在一个主键时，聚合字段的聚合率R_agg为1，即R_agg＝1。

当聚合字段对应的聚合函数为简单聚合函数Group By时，

其中，R_agg为聚合字段的聚合率，n为聚合字段的集合中聚合字段的个数；

当聚合字段对应的聚合函数为Rollup时，

其中，R_agg为聚合字段的聚合率，n为聚合字段的集合中聚合字段的个数，k为正整数；

当聚合字段对应的聚合函数为Cube时，

其中，R_agg为聚合字段的聚合率，n为聚合字段的集合中聚合字段的个数，k为正整数。

综上所述，在统计信息不准确或不完整的情况下，可以通过本申请上述实施例中所述的代价估计的方法进行操作树的代价估算，本申请所述的代价估计的方法可以应用于运行时创建的临时表和子查询，以及对于海量数据的场景，可以快速地代价估计，不受数据规模的限制。另一方面，基于本申请所述的代价估计的方法进行改进代价优化器，可以基于不完备的统计信息对执行计划进行代价优化，当统计信息完备时，现有代价估算模型可以估算相应操作的代价，基于估算结果生成最优执行计划；当统计信息不完备时，现有代价优化器无法对相应操作进行代价估算，则利用本申请所述的改进的代价估算模型(即对操作树的相关操作的代价估计方法进行改进)，对相应操作进行代价估算，并基于估算结果生成最优执行计划。

图3示出根据本申请另一个方面提供的一种代价估计的设备结构示意图，所述设备包括：判断装置11、确定装置12和估算装置13，其中，判断装置11用于判断获取到的统计信息是否完备，若否，则根据依赖于所述统计信息的操作树的操作类型确定对应的代价估计方式；确定装置12用于基于所述代价估计方式确定所述对应操作类型的代价估计；估算装置13用于根据依赖于所述统计信息操作类型对应的代价估计及未依赖于统计信息的操作类型对应的代价估计确定所述操作树的累积代价估计。从而解决传统代价优化器对于运行时创建临时表和子查询无法进行代价估算，对海量数据的场景受数据规模限制的问题，进一步地，所述设备包括：执行装置，用于根据所述累积代价估计优化结构化查询语言语句对应的执行计划。本申请所述的代价估计的方法应用于数据库系统中SQL的优化，提高SQL的代价优化器代价估计的准确性，从而生成性能更好的执行计划。

在本申请一实施例中，基于本申请所述的代价估计的方法的一种改进的代价优化器，可以基于不完备的统计信息对执行计划进行代价优化。当统计信息完备时，利用现有的代价估算模型进行估算，基于估算结果生成最优执行计划；当统计信息不完备时，通过本申请所述的代价估计的方法，对相应操作进行代价估算，并基于估算结果生成最优执行计划。

判断装置11，用于判断获取到的统计信息是否完备，若否，则根据依赖于所述统计信息的操作树的操作类型确定对应的代价估计方式；进一步地，所述依赖于所述统计信息的操作树的操作类型包括扫表操作、过滤操作、连接操作和聚合操作。在此，一棵操作树由不同的操作符构成，每一种操作符代表一类操作，基本的操作包括扫表、过滤、连接、投影、聚合、选择等，如图2所示的一颗典型的操作树示意图，调整操作树上的不同操作，估算每一步操作的代价，最终生成一颗累积代价最小的操作树，生成执行计划，而不同操作类型的代价对统计信息的依赖不同，比如，扫表操作、过滤操作、连接操作、聚合操作的代价需要依赖统计信息，投影操作、选择操作的代价不依赖于统计信息。因此需要确定操作类型，采用对应的代价估计方式，进行每一步操作的代价估计。判断获取到的统计信息是否完备，若否，则对依赖于统计信息的操作类型的代价估算方法进行改进。

接着，确定装置12，用于确定哪些操作类型需要改进的代价估计方式，进行确定对应操作类型的代价估计；最后，估算装置13，用于根据依赖于所述统计信息操作类型对应的代价估计及未依赖于统计信息的操作类型对应的代价估计确定所述操作树的累积代价估计。比如，将依赖于统计信息的扫表操作、过滤操作、连接操作和聚合操作的代价估计与不依赖于统计信息的投影操作和选择操作的代价估计进行累积得到操作树的代价估计，进而生成最优执行计划。

在本申请一实施例中，确定装置12用于根据数据集的记录数确定扫表操作的代价估计；根据过滤谓词的类型确定过滤条件的选择率之后，根据所述选择率确定过滤操作的代价估计；根据确定的连接结果集的记录数确定连接操作的代价估计；根据聚合字段及聚合函数确定聚合字段的聚合率，根据所述聚合率确定聚合操作的代价估计。在此，扫表操作的代价与数据集的大小相关，数据集越大，其扫表代价越高，因此可以根据数据集的记录数确定扫表操作的代价估计；过滤操作的代价与过滤条件的选择率相关，选择率又根据过滤条件计算得到，而过滤谓词类型不同时，选择率确定的方式也不同。连接操作的代价与参与连接的数据集大小有关，也与连接后结果集的大小有关，因此，先确定连接结果集的记录数，再根据记录数确定连接操作的代价估计。对于聚合操作，聚合操作的代价与参与聚合的数据量大小和聚合字段的聚合率有关，聚合字段的聚合率需要根据聚合字段的异值数计算得到，因此，需要计算聚合字段的异值数。

在本申请一实施例中，将数据集的记录数记为RC(Row Count)，数据集的大小(记为S)与RC成正比例关系，即：S∝RC，因此在本申请实施例中，可以使用RC代表数据集的大小，则扫表操作的代价为

cost＝Op.getOriginalCoat(RC)；

表示可以根据数据集的记录数确定扫表操作的代价估计，其中，所述Op表示想要估计代价的目标操作，getOriginalCost表示使用现有方法和RC来估计代价。

在本申请一实施例中，在过滤操作中，过滤操作的代价与谓词的选择率相关，不同形式的谓词，其选择率的估算算法不同，可以通过判断过滤谓词的类型对应的计算选择率的对象是否可获取，若否，则指定S＝1/指定值。在此，过滤谓词的类型对应的计算选择率的对象包括异值数、谓词字段的极值、谓词字段的空值数，指定值根据具体的实际应用而定，为大于1的正数，在不同过滤谓词的类型中，可能相同也可能不同，例如，S＝1/5，S＝1/9等。

进一步地，过滤操作的代价与过滤条件的选择率有关，选择率又根据过滤条件计算得到，在本申请实施例中，定义选择率为S＝结果集记录总数/参与过滤操作记录总数。由此，根据过滤谓词的类型进行以下讨论：

过滤谓词的类型对应的计算选择率的对象不可获取时，当过滤谓词的类型为恒等谓词时，判断所述过滤操作的异值数是否可获取，若否，则指定S＝1/指定值；在此，恒等谓词(Equal、＝)时，若异值数(NDV)可获取，则选择率S＝1/NDV，当异值数不可获取时，S_{(恒等谓词)}＝1/10，其中，S＝1/10是根据经验值确定，也可以为其他指定值。当过滤谓词是不等谓词(Non-Equal、！＝)，恒等与不等是一对互补谓词，即其选择率之和应该为1，因此，不等谓词的选择率为S_{(不等谓词)}＝1-S_{(恒等谓词)}。

当过滤谓词的类型为范围谓词时，其中，范围谓词包括一边区间范围：形如>、<、>＝、<＝，两值区间范围：between，是否在集合内如In，若谓词的字段的极值或异值数未能获取，则选择率S＝1/指定值；在此，谓词形如>、<、>＝、<＝时，选择率根据谓词字段的极值确定，当极值不可获取时，定义S＝1/3。谓词形如between时，即过滤条件在两值之间，当极值不可获取时，定义其S＝1/9。当谓词形如In，C＝{v₁，v₂，…，v_n}，即过滤条件表述为：col>1，v₂，…，v_n)，n＝|C|，其中，v₁，v₂，…，v_n为过滤值，C为过滤值的集合，n为集合C中过滤值的个数，过滤时判断待过滤的数据是否属于该集合C内的值。当异值数不可获取时，定义S＝1/5。

当过滤谓词的类型为判空谓词时，判断谓词字段的空值数是否可获取，若否，则确定所述过滤条件的选择率为S＝1/指定值。在此，判空谓词时，选择率需要根据谓词字段的空值数估算，当空值数不可获取时，定义S＝1/10。对于非空谓词，其与判空谓词为互补谓词，则选择率S_非空谓词＝1-S_判空谓词。

过滤谓词的类型还包括以下几种情况：当过滤谓词的类型为like时，所述过滤条件的选择率为1/指定值；在此，当过滤谓词的类型为like时，定义选择率＝1/5。当过滤谓词的类型为和级联谓词时，根据级联谓词的选择率的乘积与和级联谓词中过滤率最小值确定过滤条件的选择率；在此，And级联的过滤谓词，记级联谓词为P＝P₁AND>2AND...P_n，为防止估算误差被级联放大，在本申请实施例中，通过以下方式估算其选择率：

其中，α定义了And级联过滤谓词过滤率的最小值，可以根据实际情况调整α的值；selectivity为选择率，上述公式表示And级联过滤谓词的级联的选择率值与And级联过滤谓词过滤率的最小值中的最大值作为选择率。

当过滤谓词的类型为或级联谓词时，根据所述或级联谓词对应的级联谓词的选择率确定过滤条件的选择率。在此，记或级联的过滤谓词为

P＝P₁OR>2OR...Pn

则选择率按照如下方式确定：

通过以上分过滤谓词的类型进行讨论其对应的选择率，根据确定的选择率可计算过滤操作的代价：

cost＝Op.getOriginalCost(selectivity)

需要说明的是，本领域技术人员应能理解，上述实施例中出现的S＝1/指定值中的具体数值仅为举例，且在上述实施例中每种过滤谓词的选择率可以根据实际情况做调整，也可以通过参数传递等方式动态改变。

在本申请一实施例中，根据确定的连接结果集的记录数确定连接操作的代价估计之前，根据相连接的左表和右表的连接字段的异值数确定连接结果集的记录数。在此，参与连接的左表记为T_left，其记录数为RC_left，异值数为NDV_left；右表记为T_right，其记录数为RC_right，异值数为NDV_right；结果集的记录数记为RC_result。参与连接的左右表均有其他操作构成，例如选择操作、过滤操作、扫表操作等，分别构成了左边操作树和右边操作树，操作树上的每一种操作，其代价均可以估算得到，因此，参与连接的数据集大小(即RC_left和RC_right)可由其他对操作的估算和已有的计算方法计算得到。

在本申请一实施例中，当相连接的左表和右表的连接字段的异值数不可获取时，基于连接字段的连接类型确定连接结果集的记录数。具体根据连接字段的类型做如下讨论：

当连接字段的连接类型为主键外键形式连接，则根据外键字段的记录数与主键字段的过滤条件的选择率确定连接结果集的记录数；在此，如果连接字段分别是主键-外键形式连接：

RC_result＝RC_fk×selectivity(PK)

其中，RC_fk为RC_left和RC_right之一，是外键字段记录数，selectivity(PK)表示主键字段的选择率。如果主键字段存在过滤条件，则最终连接的结果也会受该过滤条件的影响，因此，这里乘以主键字段过滤条件的选择率，当不存在过滤条件时，则其值为1。

如果连接字段非主键-外键连接，则又可分为以下情况：

当连接字段的连接类型为内连接，则将相连接的左表的记录数及右表的记录数中的最大值作为连接结果集的记录数；在此，在本申请一实施例中，将结果记录数估算为连接记录数的最大值：

RC_result＝max(RC_left，RC_right)

即结果记录数为RC_left和RC_right中的最大值。

当连接字段的连接类型为叉乘连接，则将相连接的左表的记录数及右表的记录数的乘积作为连接结果集的记录数；对于叉乘连接，其记录数为连接记录数之乘积，即：RC_result＝RC_left×RC_right。

当连接字段的连接类型为左外连接或右外连接，则将对应的相连接的左表的记录数或右表的记录数作为连接结果集的记录数；在此，当是左外连接时，其记录数为T_left的记录数，即RC_result＝RC_left。当是右外连接时，其记录数为T_right的记录数，即RC_result＝RC_right。

当连接字段的连接类型为全连接，则将相连接的左表的记录数及右表的记录数的累加作为连接结果集的记录数。在此，全外连接时，其记录数为T_left和T_right的记录数之和，即：RC_result＝RC_left+RC_right。

最终，连接操作的代价为：cost＝Op.getOriginalCost(RC_left，RC_right，RC_result)。

在本申请一实施例中，对于聚合操作过程，聚合操作的代价与参与聚合的数据量大小和聚合字段的聚合率有关，可以定义聚合率为：

聚合字段的聚合率需要根据聚合字段的异值数计算得到，当聚合字段的异值数无法获取时，进行如下讨论：

记C＝{c₁，c₂，...，c_n}，n＝|C|，其中，c₁、c₂和c_n为聚合字段。

当聚合字段的集合C中至少存在一个主键时，聚合字段的聚合率R_agg为1，即R_agg＝1。

当聚合字段对应的聚合函数为简单聚合函数Group By时，

其中，R_agg为聚合字段的聚合率，n为聚合字段的集合中聚合字段的个数；

当聚合字段对应的聚合函数为Rollup时，

其中，R_agg为聚合字段的聚合率，n为聚合字段的集合中聚合字段的个数，k为正整数；

当聚合字段对应的聚合函数为Cube时，

其中，R_agg为聚合字段的聚合率，n为聚合字段的集合中聚合字段的个数，k为正整数。

根据本申请再一个方面，还提供了一种代价优化器，其中，所述代价优化器用于：生成原始执行计划；判断获取到的统计信息是否完备，若是，则根据基于统计信息的第一代价估算模型估算代价，若否，则根据基于第一代价估算模型进行优化的第二代价估算模型估算代价；根据所述第一代价估算模型估算的代价或所述第二代价估算模型估算的代价生成最优执行计划。在本申请一实施例中，如图4所示的一种改进的代价优化器，可以基于不完备的统计信息对执行计划进行代价优化。当存在完备统计信息时，使用第一代价估算模型估算代价，其中，第一代价估算模型为现有代价估算模型，现有代价估算模型进行代价优化需要统计信息，因此，需要收集完整而精确的统计信息。在数据库系统中，执行计划一般用操作树表示，操作树由不同类型的操作构成，典型的操作树包括扫表、选择、过滤、聚合、连接、投影等。基于统计信息，代价优化器可以借助代价估算模型，对执行计划的每一步操作进行代价估算，并从所有可能的执行计划中选取整体代价最小者作为最终的执行计划，由此就完成了整个代价优化的过程。而当不存在完备统计信息时，使用对第一代价估算模型进行优化的第二代价估算模型估算代价，即使用改进的代价估算模型估算代价，并基于估算结果生成最优执行计划。其中，改进的代价估算模型用于：根据依赖于所述统计信息的操作树的操作类型确定对应的代价估计方式；基于所述代价估计方式确定所述对应操作类型的代价估计；根据依赖于所述统计信息操作类型对应的代价估计及未依赖于统计信息的操作类型对应的代价估计确定所述操作树的累积代价估计。

综上所述，在统计信息不准确或不完整的情况下，可以通过本申请上述实施例中所述的代价估计的设备中执行的方法进行操作树的代价估算，本申请所述的代价估计的设备可以应用于运行时创建的临时表和子查询，以及对于海量数据的场景，可以快速地代价估计，不受数据规模的限制。另一方面，基于本申请所述的代价估计的设备进行改进代价优化器，可以基于不完备的统计信息对执行计划进行代价优化，当统计信息完备时，现有代价估算模型可以估算相应操作的代价，基于估算结果生成最优执行计划；当统计信息不完备时，现有代价优化器无法对相应操作进行代价估算，则利用本申请所述的改进的代价估算模型(即对操作树的相关操作的代价估计方法进行改进)，对相应操作进行代价估算，并基于估算结果生成最优执行计划。

在本申请一实施例中，还提供了一种基于计算的设备，包括：

处理器；以及

被安排成存储计算机可执行指令的存储器，所述可执行指令在被执行时使所述处理器：

判断获取到的统计信息是否完备，若否，则根据依赖于所述统计信息的操作树的操作类型确定对应的代价估计方式；

基于所述代价估计方式确定所述对应操作类型的代价估计；

根据依赖于所述统计信息操作类型对应的代价估计及未依赖于统计信息的操作类型对应的代价估计确定所述操作树的累积代价估计。

显然，本领域的技术人员可以对本申请进行各种改动和变型而不脱离本申请的精神和范围。这样，倘若本申请的这些修改和变型属于本申请权利要求及其等同技术的范围之内，则本申请也意图包含这些改动和变型在内。

需要注意的是，本申请可在软件和/或软件与硬件的组合体中被实施，例如，可采用专用集成电路(ASIC)、通用目的计算机或任何其他类似硬件设备来实现。在一个实施例中，本申请的软件程序可以通过处理器执行以实现上文所述步骤或功能。同样地，本申请的软件程序(包括相关的数据结构)可以被存储到计算机可读记录介质中，例如，RAM存储器，磁或光驱动器或软磁盘及类似设备。另外，本申请的一些步骤或功能可采用硬件来实现，例如，作为与处理器配合从而执行各个步骤或功能的电路。

另外，本申请的一部分可被应用为计算机程序产品，例如计算机程序指令，当其被计算机执行时，通过该计算机的操作，可以调用或提供根据本申请的方法和/或技术方案。而调用本申请的方法的程序指令，可能被存储在固定的或可移动的记录介质中，和/或通过广播或其他信号承载媒体中的数据流而被传输，和/或被存储在根据所述程序指令运行的计算机设备的工作存储器中。在此，根据本申请的一个实施例包括一个装置，该装置包括用于存储计算机程序指令的存储器和用于执行程序指令的处理器，其中，当该计算机程序指令被该处理器执行时，触发该装置运行基于前述根据本申请的多个实施例的方法和/或技术方案。

对于本领域技术人员而言，显然本申请不限于上述示范性实施例的细节，而且在不背离本申请的精神或基本特征的情况下，能够以其他的具体形式实现本申请。因此，无论从哪一点来看，均应将实施例看作是示范性的，而且是非限制性的，本申请的范围由所附权利要求而不是上述说明限定，因此旨在将落在权利要求的等同要件的含义和范围内的所有变化涵括在本申请内。不应将权利要求中的任何附图标记视为限制所涉及的权利要求。此外，显然“包括”一词不排除其他单元或步骤，单数不排除复数。装置权利要求中陈述的多个单元或装置也可以由一个单元或装置通过软件或者硬件来实现。第一，第二等词语用来表示名称，而并不表示任何特定的顺序。