面向分析型数据库的大规模随机负载生成及验证方法及系统

摘要

本发明提出了一种面向分析型数据库的大规模随机负载生成及验证方法，可以生成大规模随机数据库、查询负载以及相应的查询执行结果，帮助高效地完成查询执行结果正确性验证。本发明还提出了一种面向分析型数据库的大规模随机负载生成及验证方系统。

说明书

技术领域

本发明涉及数据生成、查询生成、正确结果生成技术领域，尤其涉及一种面向分析型数据库的大规模随机负载生成及验证方法及系统。

背景技术

软件测试是保证软件可靠性的有效手段，在软件开发过程中占有重要的地位。然而，测试通常是一个十分消耗人力和时间的过程，这也就导致其在软件开发代价中占比很高。尤其，对于DBMS这种大型、复杂的系统软件，它的测试输入十分复杂，这使得测试DBMS的代价进一步上升。自动化测试案例生成能够显著地减少测试代价，帮助我们更加充分、系统地完成测试，增加系统可靠性，提高开发效率。

为了完成数据库系统的功能测试，需要测试数据库、测试查询、以及正确执行结果这三个部分帮助完成。如何高效地将数据生成、查询生成和结果集生成这三个部分的工作整合到一起是一个很难、也急需解决的问题。

在数据生成方面，主要包含两类工作，一种是查询无感的数据生成[1-5]，另一种是查询感知的数据生成[6-10]。对于查询无感的数据生成，在进行数据生成时只考虑目标数据库的数据特征，通常使用这种方法进行大规模数据库生成然后执行各种测试基准。这类工作的普遍问题是，测试查询在该数据库上执行时可能不会返回有意义的结果，例如返回空集，这会导致大量无效的数据库测试。查询感知的数据生成在数据生成时考虑测试查询带来的约束。这类工作致力于生成数据库使得在其中执行测试查询时可以得到期待的中间结果集，进而帮助我们测试内存管理器或者查询优化器中的基数估计组件等。

在查询生成方面，RAGS[11]是已知最早的随机SQL生成器，服务于SQL Server的测试工作。RAGS可以根据给定的schema信息生成大量随机的符和语法的SQL。由于RAGS会生成将近50％的无效查询，GARan[12]是第一个针对数据库系统的自适应随机测试技术，它能够帮助我们找到有效的查询。GARan根据负载执行的反馈信息使用遗传算法生成更符和预期的测试案例进而提高测试的代码覆盖度。RAGS和GARan都需要在多个数据库系统中执行相同的查询，并且逐行比对返回结果集来验证查询执行的正确性。为了提高测试效率，自适应随机测试思想和技术[13-14]的引入可以有效提高生成的测试案例质量。其他类型的负载生成器有固定的查询模板[15-17]。QGen[17]可以根据一组查询模板快速生成大量的查询，TPC-DS的查询负载便由其生成。工作[15,16]希望为查询模板填入合适的参数值，使查询满足指定的基数约束。

在正确结果生成方面，一些工作[18,19]在生成数据和负载的同时，也给出了查询执行结果。ADUSA[19]的数据生成和负载生成都依赖于Alloy[20]。然而，Alloy的数据生成复杂度过高，不足以支持大规模测试数据库生成。同时，ADUSA也存在负载类型支持较少的问题。工作[21,22]对ADUSA进行了补充，并且把查询生成，数据生成和结果生成整合到一个自动化框架中。然而还是具有负载类型不充分，不支持大数据集的问题。工作[18]扩展了在[23]中提出的RQP技术，先生成查询和期待的查询结果，之后再生成相应的数据库。但是其数据库生成代价高昂，生成大规模数据库也是不可行的。

上面提到的方法在大数据集下进行查询执行结果正确性验证，要么需要消耗大量的存储和计算资源(对比系统)，代价十分高昂，要么是无法适用的(生成大规模数据库代价过高，不具有实际使用意义)。

发明内容

数据库系统的功能模块越来越多并且越来越复杂，为了保证其可靠性，需要充分的功能测试，其中为了检测查询执行结果是否正确，需要测试数据库、测试查询和测试查询在测试数据库上执行的正确结果这三个部分帮助我们完成正确性检测。目前还没有技术可以有效地把这三部分结合起来，高效地完成查询执行结果正确性验证。

本发明提出的面向分析型数据库的大规模随机负载生成及验证方法，包括以下步骤：

步骤一：随机数据库schema生成，根据自定义的随机schema生成配置文件，其中包括常用的schema配置项，生成随机的数据库schema；

步骤二：数据生成，采用确定性随机数据生成机制，即为数据表中的属性确定随机生成函数，使其属性值与主键值保持某种关联关系，根据属性生成函数，采用分布式控制器将数据生成任务均匀划分到所有的数据生成器上，实现完全并行的数据生成，生成的数据先以文本格式存储在生成节点，之后再批量导入数据库中；

确定性随机数据生成机制如下：

根据属性本身数据类型，为其确定多个随机生成函数，为每个属性值选择相应的生成函数使用数值计算器计算出一个值，之后使用数值转换器，根据数值计算器的值生成实际的属性值。针对不同的数据类型，数值转换器会使用不同的方式；针对数值型数据类型，数值转换器根据数值计算器得出的值进行精度调整；而针对字符型数据类型，根据字符串长度限制，先生成一组种子字符串，然后根据数值计算器得出的值通过取余确定使用的种子字符串，再通过连接数值计算器得出的值和种子字符串作为输出。

步骤三：查询生成，采用数据感知的查询生成机制，基于支持的sql语法，首先生成符和语法和语义的具有参数化谓词的查询，之后，在查询参数实例化过程中，受益于确定性数据生成机制，高效实例化满足特定约束的查询参数；

数据感知的查询生成机制如下：

首先根据支持的sql语法，生成满足语法和语义的具有参数化谓词的查询，根据谓词形式的不同，采用随机计算或者蒙特卡洛算法进行参数实例化。

步骤四：结果集生成，根据数据之间的依赖关系，通过自计算的方式，得出在测试数据库上执行测试查询的正确结果，然后用于查询执行正确性验证。

结果集生成机制如下：

受益于确定性数据生成机制，数据之间存在依赖关系，通过主键约束链的形式表示当前查询操作下表中满足约束的元组的主键信息，不断地进行约束传递，最终表示出每张表中满足查询的所有元组。之后按照连接序，构建连接结果，然后进行选择、聚合等运算得出最终查询结果。

基于上述方法，本发明还提出了一种面向分析型数据库的大规模随机负载生成及验证系统的实现，包括以下模块：

随机数据库schema生成模块，根据自定义的schema生成配置文件，其中包括常用的schema配置项，生成随机的数据库schema；

数据生成模块，采用确定性随机数据生成机制，即为数据表中的属性确定随机生成函数，使其属性值与主键值保持某种关联关系，根据属性生成函数，采用分布式控制器将数据生成任务均匀划分到所有的数据生成器上，实现完全并行的数据生成，生成的数据先以文本格式存储在生成节点，之后再批量导入数据库中；

查询生成模块，采用数据感知的查询生成机制，基于支持的sql语法，首先生成符和语法和语义的具有参数化谓词的查询，之后，在查询参数实例化过程中，受益于确定性数据生成机制，高效实例化满足特定约束的查询参数；

结果集生成模块，根据数据之间的依赖关系，通过自计算的方式，得出在测试数据库上执行测试查询的正确结果，然后用于查询执行正确性验证。

数据生成主要包含两个模块，一个是数值计算器，一个是数值转换器：数值计算器会使用每个属性对应的生成函数为其计算出一个数值，之后，数值转换器针对不同的数据类型使用不同的方式进行转换；针对数值型数据类型，数值转换器根据数值计算器得出的值进行精度调整；而针对字符型数据类型，根据字符串长度限制，先生成一组种子字符串，然后根据数值计算器得出的值通过取余确定使用的种子字符串，再通过连接数值计算器得出的值和种子字符串作为输出。

本发明是一种面向分析型数据库(OLAP)的大规模随机负载生成及验证方法，可以生成大规模随机数据库、查询负载以及相应的查询执行结果，帮助高效地完成查询执行结果正确性验证。

参考文献

[1]A.Alexandrov,K.Tzoumas,and V.Markl.Myriad:Scalable and expressivedata generation.Proceedings of the Vldb Endowment,5(12):1890-1893,2012.

[2]N.Bruno and S.Chaudhuri.Flexible database generators,2006.

[3]J.E.Hoag and C.W.Thompson.A parallel general-purpose syntheticdata generator.Acm Sigmod Record,36(1):19-24,2007.

[4]K.Houkjr,K.Torp,and R.Wind.Simple and realistic data generation.InProceedings of the 32nd International Conference on Very Large DataBases,Seoul,Korea,September 12-15,2006,2006.

[5]E.Torlak.Scalable test data generation from multidimensionalmodels.In Proceedings of the ACM SIGSOFT 20th International Symposium on theFoundations of Software Engineering,2012.

[6]A.Arasu,R.Kaushik,and J.Li.Data generation using declarativeconstraints pages 685-696,2011.

[7]C.Binnig,D.Kossmann,E.Lo,and M.T.zsu.Qagen:generating queryawaretest databases.In Acm Sigmod International Conference on Management of Data,2007.

[8]Li Y,Zhang R,Yang X,et al.Touchstone:Generating Enormous Query-Aware Test Databases[C]//Usenix Technical Conference.2018,pages 575-586..

[9]E.Lo,N.Cheng,and W.Hon.Generating databases for queryworkloads.Proc.VLDB Endow.3(1):848-859,2010.

[10]E.Lo,N.Cheng,W.W.K.Lin,W.K.Hon,and B.Choi.Mybenchmark:generatingdatabases for query workloads.Vldb Journal International Journal on VeryLarge Data Bases,23(6):895-913,2014.

[11]D.R.Slutz.Massive stochastic testing of sql.pages 618-622,1998.

[12]H.Bati,L.Giakoumakis,S.Herbert,and A.Surna.A genetic approach forrandom testing of database systems.In International Conference on Very LargeData Bases,2007.

[13]T.Y.Chen,F.Kuo,R.Merkel,and T.H.Tse.Adaptive random testing:Theart of test case diversity.Journal of Systems and Software,83(1):60-66,2010.

[14]A.Shahbazi,A.Tappenden,and J.Miller.Centroidal voronoitessellationsa new approach to random testing.IEEE Transactions on SoftwareEngineering,39(2):163-183,2013.

[15]N.Bruno,S.Chaudhuri,and D.Thomas.Generating queries withcardinality constraints for dbms testing.IEEE Transactions on Knowledge&DataEngineering,18:p.1721-1725,2006.

[16]C.Mishra,N.Koudas,and C.Zuzarte.Generating targeted queries fordatabase testing.pages 499-510,2008.

[17]M.Poess and J.M.Stephens.Generating thousand benchmark queries inseconds.In Thirtieth International Conference on Very Large Data Bases,2004.

[18]C.Binnig,D.Kossmann,E.Lo,and A.Saenzbadillos.Automatic resultverification for the functional testing of a query language.2008.

[19]S.A.Khalek,B.Elkarablieh,Y.O.Laleye,and S.Khurshid.Query-awaretest generation using a relational constraint solver.In IEEE/ACMInternational Conference on Automated Software Engineering,2008.

[20]Jackson and Daniel.Alloy:a lightweight object modellingnotation.Acm Transactions on Software Engineering&Methodology,11(2):256-290,2002.

[21]S.Abdul Khalek and S.Khurshid.In IEEE/ACM InternationalConference on Automated Software Engineering,2010.

[22]S.A.Khalek and S.Khurshid.Systematic testing of database enginesusing a relational constraint solver.pages 50-59,2011.

[23]C.Binnig,D.Kossmann,and E.Lo.Reverse query processing.In DataEngineering,2007.ICDE 2007.IEEE 23rd International Conference on,2007.

附图说明

图1为设计架构。

图2为属性生成函数。

图3为属性生成器。

图4为属性种子集。

图5为sql语法示例。

图6为随机生成的带有参数化谓词的查询。

图7为R,S,T三表的依赖关系。

图8为主键约束链表示。

图9为本发明中算法1的示意图。

图10为本发明中算法2的示意图。

具体实施方式

结合以下具体实施例和附图，对发明做进一步的详细说明。实施本发明的过程、条件、实验方法等，除以下专门提及的内容之外，均为本领域的普通知识和公共常识，本发明没有特别限制内容。

本发明面向分析型数据库的大规模随机负载生成及验证方法，包括以下步骤：

步骤一：随机数据库schema生成，根据自定义的随机schema生成配置文件，其中包括常用的schema配置项，生成随机的数据库schema；

步骤二：数据生成，采用确定性随机数据生成机制，即为数据表中的属性确定随机生成函数，使其属性值与主键值保持某种关联关系，根据属性生成函数，采用分布式控制器将数据生成任务均匀划分到所有的数据生成器上，实现完全并行的数据生成，生成的数据先以文本格式存储在生成节点，之后再批量导入数据库中；

步骤三：查询生成，采用数据感知的查询生成机制，基于支持的sql语法，首先生成符和语法和语义的具有参数化谓词的查询，之后，在查询参数实例化过程中，受益于确定性数据生成机制，高效实例化满足特定约束的查询参数；

步骤四：结果集生成，根据数据之间的依赖关系，通过自计算的方式，得出在测试数据库上执行测试查询的正确结果，然后用于查询执行结果正确性验证。

本发明的实现包括以下模块：

1.schema生成器(Schema Generator)，根据自定义的随机schema生成配置文件，其中包括常用的schema配置项，如数据表个数、数据表大小、属性数目、外键数目、数据类型出现的比例、字符串长度、索引概率等等，生成随机的数据库schema；

2.数据生成器(Database Generator)，采用确定性随机数据生成机制，即为数据表中的属性确定随机生成函数，使其属性值与主键值保持某种关联关系，根据属性生成函数，采用分布式控制器将数据生成任务均匀划分到所有的数据生成器上，实现完全并行的数据生成，生成的数据先以文本格式存储在生成节点，之后再批量导入数据库中；

确定性随机数据生成机制如下：

根据属性本身特征，为其确定多个随机生成函数，为每个属性值选择相应的生成函数使用数值计算器(Numerical Calculator)计算出一个值，之后使用数值转换器(ValueConverter)，根据数值计算器的值生成实际的属性值。针对不同的数据类型，数值转换器会使用不同的方式；针对数值型数据类型，数值转换器根据数值计算器得出的值进行精度调整；而针对字符型数据类型，根据字符串长度限制，先生成一组种子字符串，然后根据数值计算器得出的值通过取余确定使用的种子字符串，再通过连接数值计算器得出的值和种子字符串作为输出。

3.查询生成器(Workload Generator)，采用数据感知的查询生成机制，基于支持的sql语法，首先生成符和语法和语义的具有参数化谓词的查询，之后，在查询参数实例化过程中，受益于确定性数据生成机制，高效实例化满足特定约束的查询参数；

数据感知的查询生成机制如下：

首先根据支持的sql语法，生成满足语法和语义的具有参数化谓词的查询，根据谓词形式的不同，采用随机计算或者蒙特卡洛算法进行参数实例化。

4.结果生成器(Oracle Generator)，根据数据之间的依赖关系，通过自计算的方式，得出在测试数据库上执行测试查询的正确结果，然后用于查询执行正确性验证。

结果集生成机制如下：

受益于确定性数据生成机制，数据之间存在依赖关系，通过主键约束链的形式表示当前查询操作下表中满足约束的元组的主键信息，不断地进行约束传递，最终表示出每张表中满足查询的所有元组。之后按照连接序，构建连接结果，然后进行选择、聚合等运算得出最终查询结果。

基本架构

基于上述的问题定义，系统的输入包含一个随机schema生成配置文件；系统的输出包含生成的数据库实例，查询负载和正确的查询执行结果。Artemis的基本架构主要包含四个模块，分别是schema生成模块、数据生成模块、查询生成模块和结果生成模块，如图1所示。

随机schema生成：根据自定义的schema生成配置文件，生成随机的数据库schema，保证测试的多样性，随机schema生成的算法见图9：Algorithm 1；

数据生成：采用确定性随机数据生成机制，即为数据表中的属性确定随机生成函数，使其属性值与主键值保持某种关联关系，根据属性生成函数，采用分布式控制器将数据生成任务均匀划分到所有的数据生成器上，实现完全并行的数据生成，生成的数据先以文本格式存储在生成节点，之后再批量导入数据库中；

确定性随机数据生成机制如下：

根据属性本身特征，为其确定多个随机生成函数，为每个属性值选择相应的

生成函数使用数值计算器(Numerical Calculator)计算出一个值，之后使用数值转换器(Value Converter)，根据数值计算器的值生成实际的属性值。针对不同的数据类型，数值转换器会使用不同的方式；针对数值型数据类型，数值转换器根据数值计算器得出的值进行精度调整；而针对字符型数据类型，根据字符串长度限制，先生成一组种子字符串，然后根据数值计算器得出的值通过取余确定使用的种子字符串，再通过连接数值计算器得出的值和种子字符串作为输出。

图2展示了为某个属性att准备的生成函数，以及确定使用哪一个生成函数的HitFunction.。图3展示了属性值生成的流程。假设att的数据类型为字符型，图4展示了属性att的随机种子集以及使用哪一个随机种子的Hit Fuction。主键id为3的元组对应的att的值的计算过程如下。根据生成函数选择的Hit Function得出使用的生成函数为Func

查询生成，采用数据感知的查询生成机制，我们把查询生成分为两步，基于支持的sql语法，首先生成符和语法和语义的具有参数化谓词的查询，之后，在查询参数实例化过程中，受益于确定性数据生成机制，高效实例化满足特定约束的查询参数；

图5展示了一个查询生成语法样例，图6展示了一个根据示例语法随机生成的带有参数化谓词的查询，其中有4个参数。对于其中的点值参数p

结果集生成：根据数据之间的依赖关系，通过自计算的方式，得出在测试数据库上执行测试查询的正确结果，然后用于查询执行正确性验证。

结果集生成机制如下：

受益于确定性数据生成机制，数据之间存在依赖关系，通过主键约束链的形式表示当前查询操作下表中满足约束的元组的主键信息，在发生连接时，进行约束传递，最终表示出每张表中满足查询的所有元组。之后按照连接序，构建连接结果，然后进行选择、聚合等运算得出最终查询结果。

结果生成的算法见图10：Algorithm 2.

图7展示了数据表R,S,T之间的依赖关系。图8展示了对于查询select*from Rinnerjoin S on R.r1＝S.s2,T where R.r3>3and S.s3<10and T.t2＝8and T.t1＝R.r2的主键约束链表示和约束传递的过程。对于n1，n2，n3三个节点，它们分别将自身的过滤谓词产生的约束转换为其主键约束信息。之后对于节点n4,R和S的连接使两张表发生了约束传递，分别为两张表产生蓝色的全局约束。最后，对于节点n5，T和S的连接使两张表发生主键约束信息传递，之后通过R表再传递给S表，最终三张表都产生橙色的全局约束。

实验结论

实验环境

实验硬件配置：8个物理节点上，每个节点含有2个CPU，型号为Intel Xeon Silver4110@2.1GHz CPU；内存为120GB；存储为4TB，RAID-5，7200转的HDD磁盘。物理节点之间使用千兆以太网通信。

性能评测

实验一：生成一个数据库实例，其中包含20张表，每张表的大小为10

实验二：生成一个数据库实例，其中包含20张表，每张表的非主键属性数为20，包含int,float,varchar,datetime,decimal五种数据类型且出现概率相等。每张表的大小分别为10

实验三：根据schema生成器随机生成的schema，进行数据生成，然后生成1000条随机查询使用一个物理节点，最后计算出查询执行的结果。观察查询生成时间和查询结果计算时间。把生成的数据导入MySQL5.7并执行相应的查询，验证查询的有效性，然后比较结果集，验证计算的正确性。

通过实验数据可知，本发明对于数据生成节点数和生成数据库实例的大小都是线性可扩展的，并且可以生成有效的查询负载然后计算出正确的执行结果，帮助我们高效地完成结果验证。

本发明的保护内容不局限于以上实施例。在不背离发明构思的精神和范围下，本领域技术人员能够想到的变化和优点都被包括在本发明中，并且以所附的权利要求书为保护范围。