一种面向非等值连接负载的数据生成方法及生成系统转让专利
申请号 : CN202010053458.9
文献号 : CN111240988B
文献日 : 2021-07-27
发明人 : 张蓉 , 李宇明
申请人 : 华东师范大学
摘要 :
本发明提出了一种面向非等值连接负载的数据生成方法，包括查询实例化，根据给定的数据库结构，以及每个属性的数据特征，首先生成每个属性的随机生成函数；如果某个属性没有指定数据特征，则采用相应数据类型默认的数据特征；基于相应属性的生成函数，实例化所有基数约束中涉及的符号参数，实例化后的参数保证了各个查询的中间结果集大小在概率期望上与约束的基数一致；查询实例化模块有两部分的输出，一个是填充了具体参数的实例化查询，供后续测试所用；一个是数据表中所有属性的生成函数，作为数据生成模块的输入；数据生成，根据给定的属性生成函数，分布式控制器会依据机器配置信息，将数据生成任务均匀划分到所有的数据生成器上，以便最大化地利用硬件资源进行完全并行的数据生成；生成的数据首先以文本的形式存储在各个节点上，然后再批量导入到待测试的数据库中。
权利要求 :
1.一种面向非等值连接负载的数据生成方法，其特征在于，包括以下步骤：步骤一：查询实例化，根据给定的数据库结构，以及每个属性的数据特征，首先生成每个属性的随机生成函数；如果某个属性没有指定数据特征，则采用相应数据类型默认的数据特征；
步骤二：基于相应属性的生成函数，实例化所有基数约束中涉及的符号参数，实例化后的参数保证了各个查询的中间结果集大小在概率期望上与约束的基数一致；查询实例化模块有两部分的输出，一个是填充了具体参数的实例化查询，供后续测试所用；一个是数据表中所有属性的生成函数，作为数据生成模块的输入；
步骤三：数据生成，根据给定的属性生成函数，分布式控制器会依据机器配置信息，将数据生成任务均匀划分到所有的数据生成器上，以便最大化地利用硬件资源进行完全并行的数据生成；生成的数据首先以文本的形式存储在各个节点上，然后再批量导入到待测试的数据库中。
2.如权利要求1所述的面向非等值连接负载的数据生成方法，其特征在于，针对各个数据类型的生成函数的具体生成机制如下：属性生成函数包含：随机索引生成和索引数值转化。
3.如权利要求2所述的面向非等值连接负载的数据生成方法，其特征在于，所述随机索引生成：根据该属性的指定基数，生成一个随机索引值，若该属性的指定基数为M，那么生成的随机基数为1至M之间的随机整数；索引数值转化器会依据输入的随机索引值，生成一个具体的数值作为输出。
4.如权利要求2所述的面向非等值连接负载的数据生成方法，其特征在于，所述索引数值转化针对不同的数据类型转化器会采用不同的转化函数；针对数值型数据类型，采用简单的线性函数作为转化函数；而针对字符型数据类型，先生成满足字符串长度要求的种子字符串，种子字符串的个数小于该属性的指定基数，然后转化器根据输入的索引值通过取余运算确定一个种子字符串的位置，再通过连接索引值和选择的种子字符串作为输出。
5.一种面向非等值连接负载的数据生成系统，其特征在于，包括以下模块：查询实例化模块：根据给定的数据库结构，以及每个属性的数据特征，首先生成每个属性的随机生成函数；如果某个属性没有指定数据特征，采用相应数据类型默认的数据特征；
生成函数模块：实例化所有基数约束中涉及的符号参数，实例化后的参数保证了各个查询的中间结果集大小在概率期望上与约束的基数一致；查询实例化模块有两部分的输出，一个是填充了具体参数的实例化查询，供后续测试所用；一个是数据表中所有属性的生成函数，作为数据生成模块的输入；
数据生成模块：根据给定的属性生成函数，分布式控制器会依据机器配置信息，将数据生成任务均匀划分到所有的数据生成器上，以便最大化地利用硬件资源进行完全并行的数据生成；生成的数据首先以文本的形式存储在各个节点上，然后再批量导入到待测试的数据库中。
6.如权利要求5所述的面向非等值连接负载的数据生成系统，其特征在于，所述属性生成函数主要包含两个模块，一个是随机索引生成器，一个是索引数值转化器：所述随机索引生成器会根据该属性的指定基数，生成一个随机索引值，若该属性的指定基数为M，那么生成的随机基数为1至M之间的随机整数；索引数值转化器会依据输入的随机索引值，生成一个具体的数值作为输出；
所述索引数值转化器针对不同的数据类型转化器会采用不同的转化函数；针对数值型数据类型，采用简单的线性函数作为转化函数；而针对字符型数据类型，先生成满足字符串长度要求的种子字符串，种子字符串的个数小于该属性的指定基数；然后转化器根据输入的索引值通过取余运算确定一个种子字符串的位置，再通过连接索引值和选择的种子字符串作为输出。
说明书 :
一种面向非等值连接负载的数据生成方法及生成系统
技术领域
[0001] 本发明涉及数据生成技术领域，尤其涉及一种面向非等值连接负载的数据生成方法及生成系统。
背景技术
[0002] 在数据库管理系统测试、数据库应用压力测试和应用驱动的测试基准的工作中，常常关注一些关键Query的系统性能。
[0003] 1.数据库管理系统测试(DBMS testing)：论文[1‑4]认为在数据库管理系统测试中能够控制查询操作的中间结果集大小是非常有意义的。当开发了一个新的数据库管理系
统组件(Join算子、内存管理器等)时，需要一个具有某种负载特征的模拟数据库实例以评
测新组件的性能。
统组件(Join算子、内存管理器等)时，需要一个具有某种负载特征的模拟数据库实例以评
测新组件的性能。
[0004] 2.数据库应用压力测试(Stress testing database applications)：在开发一个做海量数据分析的数据库应用时，需要一个与应用负载特征相关的模拟数据库实例以评测
该数据库应用的性能。
该数据库应用的性能。
[0005] 3.应用驱动的测试基准(Application‑driven benchmarking)：应用开发者在选择支撑应用的数据库管理系统时，需要针对自己的应用负载来选择适合的数据库管理系
统，但是由于数据的隐私性问题，需要生成一个与真实数据库实例在相同查询负载下性能
数据一致的模拟数据库实例以评测待选择数据库管理系统的性能。
统，但是由于数据的隐私性问题，需要生成一个与真实数据库实例在相同查询负载下性能
数据一致的模拟数据库实例以评测待选择数据库管理系统的性能。
[0006] 基于时空数据的非等值连接负载已成为现实应用中的不可或缺的一部分，如何生成一个满足多Query非等值连接基数约束的数据库实例是一个很难、也亟需解决的问题。
[0007] 当前数据生成主要有两条路线：一个是从数据特征角度生成数据，一个是从负载特征角度生成数据。由于复杂的负载特征以及数据特征上的约束使得属性之间具有复杂的
关联关系，可能导致数据生成需要大量的存储和计算并且难以实现并行化。如果仅从数据
特征角度生成模拟数据库实例，由于没有考虑查询负载，在相同的查询负载下模拟数据库
实例与真实数据库实例的性能数据难以一致。[1‑4]与本文一样，都是从负载特征角度生成
模拟数据库实例。[1‑3]是一个系列的工作。其中[1]针对每一个Query生成一个单独的数据
库实例；[2‑3]的工作继承于[1]，使用启发式算法尽可能融合利用[1]生成的针对多个
Query的多个数据库实例，但是不能保证最终仅生成一个数据库实例，并且也难以实现数据
生成的完全并行化。[4]利用概率图模型的思想来表示数据分布，但是针对含有多维度数值
型属性的基数约束，其算法复杂度太高。非等值连接负载作为一个非常重要和复杂的查询
负载，工作[1‑4]都无法处理该类型负载。
关联关系，可能导致数据生成需要大量的存储和计算并且难以实现并行化。如果仅从数据
特征角度生成模拟数据库实例，由于没有考虑查询负载，在相同的查询负载下模拟数据库
实例与真实数据库实例的性能数据难以一致。[1‑4]与本文一样，都是从负载特征角度生成
模拟数据库实例。[1‑3]是一个系列的工作。其中[1]针对每一个Query生成一个单独的数据
库实例；[2‑3]的工作继承于[1]，使用启发式算法尽可能融合利用[1]生成的针对多个
Query的多个数据库实例，但是不能保证最终仅生成一个数据库实例，并且也难以实现数据
生成的完全并行化。[4]利用概率图模型的思想来表示数据分布，但是针对含有多维度数值
型属性的基数约束，其算法复杂度太高。非等值连接负载作为一个非常重要和复杂的查询
负载，工作[1‑4]都无法处理该类型负载。
[0008] 从数据特征角度生成数据的工作有[5‑8,18]。[5]利用DGL(Data Generation Language)描述待生成数据库实例的数据特征。[6]利用图模型控制数据的生成，支持比较
复杂的表内和表外的关联关系。[7]提供一个基于XML的数据约束描述语言SDDL，可以在多
核的环境下尽可能地并发生成数据。[8]利用伪随机数字生成器实现数据的并行生成。[18]
利用数据库管理系统提供的属性上的基本数据特征生成模拟数据库实例。数据生成还有很
多其他的工作：[9]为数据流应用(dataflow programs)生成样例数据(example data)；
[10]在原始数据库实例的基础上生成模拟数据，既保证模拟数据库实例与原始数据库实例
的负载性能特征一致，也保证原始数据的隐私性；[15‑17]都是生成非关系型数据，[15]生
成XML数据，而[16‑17]生成图数据；[12]根据一个Query和一个输出，生成一个可能的数据
库实例，Query在该数据库实例上的操作结果即为已知输出。与数据生成工作相关还有
Query的生成，相关工作有[11,13‑14]。[11]根据一个数据库实例和一个输出，利用QRE
(Query Reverse Engineering)生成一个Query，而该Query在数据库实例上的操作结果即
为已知输出；[13‑14]都是在一个数据库实例上生成满足一定基数约束的Query，[13]使用
了抽样和空间剪枝的技术，而[14]使用了启发式算法提高搜索效率。
复杂的表内和表外的关联关系。[7]提供一个基于XML的数据约束描述语言SDDL，可以在多
核的环境下尽可能地并发生成数据。[8]利用伪随机数字生成器实现数据的并行生成。[18]
利用数据库管理系统提供的属性上的基本数据特征生成模拟数据库实例。数据生成还有很
多其他的工作：[9]为数据流应用(dataflow programs)生成样例数据(example data)；
[10]在原始数据库实例的基础上生成模拟数据，既保证模拟数据库实例与原始数据库实例
的负载性能特征一致，也保证原始数据的隐私性；[15‑17]都是生成非关系型数据，[15]生
成XML数据，而[16‑17]生成图数据；[12]根据一个Query和一个输出，生成一个可能的数据
库实例，Query在该数据库实例上的操作结果即为已知输出。与数据生成工作相关还有
Query的生成，相关工作有[11,13‑14]。[11]根据一个数据库实例和一个输出，利用QRE
(Query Reverse Engineering)生成一个Query，而该Query在数据库实例上的操作结果即
为已知输出；[13‑14]都是在一个数据库实例上生成满足一定基数约束的Query，[13]使用
了抽样和空间剪枝的技术，而[14]使用了启发式算法提高搜索效率。
[0009] 现有技术存在的问题：
[0010] 定义面向非等值连接负载的数据生成问题，并形式化了本文数据生成器(缩写为NejGen:Data Generator for Non‑Equi‑Join Workload)的输入和输出。
[0011] 如图1所示，NejGen的输入包含三部分，分别为：数据表结构(Database Schema H)，数据特征(Data Characteristics D)和目标负载及其负载特征(Query Execution
Trees，Table of Cardinality Constraints)。数据表结构包含了所有属性的数据类型声
明以及主键的声明。在图1中，有三个示例数据表，分别为表R，S和T，表大小分别为10，20和
50。其中表R的主键为R.r1，还有一个整型的属性R.r2和一个实型的属性R.r3。针对每个数
据表的所有属性都可以定义其数据特征。例如，在图1中，属性R.r2的取值范围为[0,10]，其
基数大小(非重复值个数)为5。属性S.s3的空值(Null)比例为10％，取值范围为[‑100,0]，
关于基数大小未作约束。针对字符串类型属性T.t3，可以定义其平均长度和最大长度，在图
1示例中分别为20和100。
Trees，Table of Cardinality Constraints)。数据表结构包含了所有属性的数据类型声
明以及主键的声明。在图1中，有三个示例数据表，分别为表R，S和T，表大小分别为10，20和
50。其中表R的主键为R.r1，还有一个整型的属性R.r2和一个实型的属性R.r3。针对每个数
据表的所有属性都可以定义其数据特征。例如，在图1中，属性R.r2的取值范围为[0,10]，其
基数大小(非重复值个数)为5。属性S.s3的空值(Null)比例为10％，取值范围为[‑100,0]，
关于基数大小未作约束。针对字符串类型属性T.t3，可以定义其平均长度和最大长度，在图
1示例中分别为20和100。
[0012] 针对查询负载，负载执行的代价主要取决于查询执行过程中每一个操作算子(operator)涉及的数据量，即记录数(number of tuples)。因此，查询负载的负载特征由一
组针对查询树(query tree)中间结果集的基数约束表示。在图1中，的示例输入包含两个参
数化的查询树(parameterized query trees)，即Q1和Q2。这两个查询树包含8个参数，分别
为P1,P2,…,P8。在查询树中每一个算子之上都有一个相应的基数约束(cardinality
constraint)，定义了针对该算子输出结果集的期望大小。因此，针对图1中的8个算子，有相
应的8个基数约束，分别为c1,c2,…,c8。下面，给出基数约束的形式化定义。
组针对查询树(query tree)中间结果集的基数约束表示。在图1中，的示例输入包含两个参
数化的查询树(parameterized query trees)，即Q1和Q2。这两个查询树包含8个参数，分别
为P1,P2,…,P8。在查询树中每一个算子之上都有一个相应的基数约束(cardinality
constraint)，定义了针对该算子输出结果集的期望大小。因此，针对图1中的8个算子，有相
应的8个基数约束，分别为c1,c2,…,c8。下面，给出基数约束的形式化定义。
[0013] 定义1基数约束(cardinality constraint)：
[0014] 针对查询树中的选择(filter)和连接(join)算子，基数约束由三元组[Q,p,s]组成，其中Q表示该基数约束涉及的Query，p表示该基数约束所针对算子的谓词表达式，s为针
对该算子输出结果集大小的约束要求。
对该算子输出结果集大小的约束要求。
[0015] 例如图1中的c1＝[Q1,R.r2的计算代价通常由处理的数据量决定。在后面的实验结构章节，也进一步验证了这个观点。
本文仅关注选择算子和连接算子，主要因为其他算子(如group by,order by,
aggregation)的输出结果集大小通常是一定的，并不需要附加相应的基数约束。如order
by算子的输出结果集大小必然与输入结果集大小一致，aggregation算子的输出结果集大
小必然为1(假设输入数据集不为空)，而group by算子的输出结果集的记录数必然也和输
入记录数一致，除非在分组之后有having过滤器。并且，这些算子一般都在查询树的顶端
(意味着在最后执行)，它们的输出结果集大小通常并不影响其他算子的执行代价。所以，本
文仅考虑选择算子和连接算子上的基数约束，工作[3]也是如此。由于NejGen是面向非等值
连接负载的数据生成器，因此本文的连接算子为非等值连接算子，如图1中Q1和Q2所示。同
时基于非等值连接负载的实际业务逻辑，本文的选择算子为范围选择算子(选择谓词中的
逻辑运算符可为>,>＝,<,<＝和between and)。基于上述的说明，给出了如下面向非等值连
接负载数据生成问题的定义。
本文仅关注选择算子和连接算子，主要因为其他算子(如group by,order by,
aggregation)的输出结果集大小通常是一定的，并不需要附加相应的基数约束。如order
by算子的输出结果集大小必然与输入结果集大小一致，aggregation算子的输出结果集大
小必然为1(假设输入数据集不为空)，而group by算子的输出结果集的记录数必然也和输
入记录数一致，除非在分组之后有having过滤器。并且，这些算子一般都在查询树的顶端
(意味着在最后执行)，它们的输出结果集大小通常并不影响其他算子的执行代价。所以，本
文仅考虑选择算子和连接算子上的基数约束，工作[3]也是如此。由于NejGen是面向非等值
连接负载的数据生成器，因此本文的连接算子为非等值连接算子，如图1中Q1和Q2所示。同
时基于非等值连接负载的实际业务逻辑，本文的选择算子为范围选择算子(选择谓词中的
逻辑运算符可为>,>＝,<,<＝和between and)。基于上述的说明，给出了如下面向非等值连
接负载数据生成问题的定义。
[0016] 定义2面向非等值连接负载的数据生成问题(data generation problem)：
[0017] 给定数据表结构，数据表的数据特征和目标负载及其负载特征，生成一个数据库实例(database instance)，该数据库实例满足要求的数据特征，并且实例化的目标负载
(查询树中的符号参数实例化为具体数值)在生成的模拟数据库实例上的运行与要求的负
载特征一致。
(查询树中的符号参数实例化为具体数值)在生成的模拟数据库实例上的运行与要求的负
载特征一致。
[0018] 数据生成问题已在工作[19]中被证明是NP‑hard的，因此不可能给出一个通用的没有误差的解决方案。本文针对定义2中关于负载特征的约束要求(即在生成的数据库实例
上执行实例化的查询负载，中间结果集的实际大小需要与基数约束中的指定值s一致)，进
行了适当的弱化，现在不要求中间结果集的实际大小与基数约束完全一致，仅要求其在概
率期望上与基数约束一致。因为Query的执行代价与中间结果集的大小是线性相关的，对于
中间结果集大小的细微变化，Query的执行代价并不会有很大的改变。例如，对于一个非等
值连接算子，当输入记录数为1000000和1000010时，其执行代价基本是相等的。
上执行实例化的查询负载，中间结果集的实际大小需要与基数约束中的指定值s一致)，进
行了适当的弱化，现在不要求中间结果集的实际大小与基数约束完全一致，仅要求其在概
率期望上与基数约束一致。因为Query的执行代价与中间结果集的大小是线性相关的，对于
中间结果集大小的细微变化，Query的执行代价并不会有很大的改变。例如，对于一个非等
值连接算子，当输入记录数为1000000和1000010时，其执行代价基本是相等的。
发明内容
[0019] 在评测数据库管理系统和数据库应用的查询性能时，通常在人工生成的数据库实例上执行相关的查询负载，然后观察系统的吞吐量和响应时间。由于巨大的数据量和复杂
的基于多表多属性的基数约束，模拟数据库的生成一直是一个难以解决的问题。当前，时空
数据在应用中越来越普遍，基于时空数据的非等值连接已成为一种常见的重要的应用负
载。目前在模拟数据库的生成过程中，还没有技术可以处理针对非等值连接负载的基数约
束。本发明文所描述的是一个面向非等值连接负载的数据生成器。本文并没有按照前人思
路那样根据约束(数据特征约束或负载特征约束)生成数据，而是按照某种特定规则先生成
数据，然后依据此规则计算出满足所有基数约束的查询参数。本文可以处理复杂的针对非
等值连接负载的基数约束及其相互依赖关系，其中算法的复杂度仅与基数约束中涉及的属
性维度相关，实现了数据生成在属性上的完全并发，并且支持在已有模拟数据库上进行动
态基数约束调整。
的基于多表多属性的基数约束，模拟数据库的生成一直是一个难以解决的问题。当前，时空
数据在应用中越来越普遍，基于时空数据的非等值连接已成为一种常见的重要的应用负
载。目前在模拟数据库的生成过程中，还没有技术可以处理针对非等值连接负载的基数约
束。本发明文所描述的是一个面向非等值连接负载的数据生成器。本文并没有按照前人思
路那样根据约束(数据特征约束或负载特征约束)生成数据，而是按照某种特定规则先生成
数据，然后依据此规则计算出满足所有基数约束的查询参数。本文可以处理复杂的针对非
等值连接负载的基数约束及其相互依赖关系，其中算法的复杂度仅与基数约束中涉及的属
性维度相关，实现了数据生成在属性上的完全并发，并且支持在已有模拟数据库上进行动
态基数约束调整。
[0020] 本发明提出的面向非等值连接负载的数据生成方法，包括以下步骤：
[0021] 步骤一：查询实例化，根据给定的数据库结构，以及每个属性的数据特征，首先生成每个属性的随机生成函数；如果某个属性没有指定数据特征，则采用相应数据类型默认
的数据特征；
的数据特征；
[0022] 针对各个数据类型的生成函数的具体生成机制如下：
[0023] 属性生成函数包含：随机索引生成和索引数值转化。
[0024] 所述随机索引生成：根据该属性的指定基数，生成一个随机索引值，若该属性的指定基数为M，那么生成的随机基数为1至M之间的随机整数；索引数值转化器会依据输入的随
机索引值，生成一个具体的数值作为输出。
机索引值，生成一个具体的数值作为输出。
[0025] 所述索引数值转化针对不同的数据类型转化器会采用不同的转化函数；针对数值型数据类型，采用简单的线性函数作为转化函数；而针对字符型数据类型，先生成一定量满
足字符串长度要求的种子字符串，种子字符串的个数一般远小于该属性的指定基数，然后
转化器根据输入的索引值通过取余运算确定一个种子字符串的位置，再通过连接索引值和
选择的种子字符串作为输出。
足字符串长度要求的种子字符串，种子字符串的个数一般远小于该属性的指定基数，然后
转化器根据输入的索引值通过取余运算确定一个种子字符串的位置，再通过连接索引值和
选择的种子字符串作为输出。
[0026] 步骤二：基于相应属性的生成函数，实例化所有基数约束中涉及的符号参数，实例化后的参数保证了各个查询的中间结果集大小在概率期望上与约束的基数一致；查询实例
化模块有两部分的输出，一个是填充了具体参数的实例化查询，供后续测试所用；一个是数
据表中所有属性的生成函数，作为数据生成模块的输入；
化模块有两部分的输出，一个是填充了具体参数的实例化查询，供后续测试所用；一个是数
据表中所有属性的生成函数，作为数据生成模块的输入；
[0027] 步骤三：数据生成，根据给定的属性生成函数，分布式控制器会依据机器配置信息，将数据生成任务均匀划分到所有的数据生成器上，以便最大化地利用硬件资源进行完
全并行的数据生成；生成的数据首先以文本的形式存储在各个节点上，然后再批量导入到
待测试的数据库中。
全并行的数据生成；生成的数据首先以文本的形式存储在各个节点上，然后再批量导入到
待测试的数据库中。
[0028] 本发明还提出了一种面向非等值连接负载的数据生成系统，包括以下模块：
[0029] 查询实例化模块：根据给定的数据库结构，以及每个属性的数据特征，首先生成每个属性的随机生成函数；如果某个属性没有指定数据特征，采用相应数据类型默认的数据
特征；
特征；
[0030] 生成函数模块：实例化所有基数约束中涉及的符号参数，实例化后的参数保证了各个查询的中间结果集大小在概率期望上与约束的基数一致；查询实例化模块有两部分的
输出，一个是填充了具体参数的实例化查询，供后续测试所用；一个是数据表中所有属性的
生成函数，作为数据生成模块的输入；
输出，一个是填充了具体参数的实例化查询，供后续测试所用；一个是数据表中所有属性的
生成函数，作为数据生成模块的输入；
[0031] 数据生成模块：根据给定的属性生成函数，分布式控制器会依据机器配置信息，将数据生成任务均匀划分到所有的数据生成器上，以便最大化地利用硬件资源进行完全并行
的数据生成；生成的数据首先以文本的形式存储在各个节点上，然后再批量导入到待测试
的数据库中。
的数据生成；生成的数据首先以文本的形式存储在各个节点上，然后再批量导入到待测试
的数据库中。
[0032] 所述属性生成函数主要包含两个模块，一个是随机索引生成器，一个是索引数值转化器：所述随机索引生成器会根据该属性的指定基数，生成一个随机索引值，若该属性的
指定基数为M，那么生成的随机基数为1至M之间的随机整数；索引数值转化器会依据输入的
随机索引值，生成一个具体的数值作为输出；所述索引数值转化器针对不同的数据类型转
化器会采用不同的转化函数；针对数值型数据类型，采用简单的线性函数作为转化函数；而
针对字符型数据类型，先生成一定量满足字符串长度要求的种子字符串，种子字符串的个
数一般远小于该属性的指定基数；然后转化器根据输入的索引值通过取余运算确定一个种
子字符串的位置，再通过连接索引值和选择的种子字符串作为输出。
指定基数为M，那么生成的随机基数为1至M之间的随机整数；索引数值转化器会依据输入的
随机索引值，生成一个具体的数值作为输出；所述索引数值转化器针对不同的数据类型转
化器会采用不同的转化函数；针对数值型数据类型，采用简单的线性函数作为转化函数；而
针对字符型数据类型，先生成一定量满足字符串长度要求的种子字符串，种子字符串的个
数一般远小于该属性的指定基数；然后转化器根据输入的索引值通过取余运算确定一个种
子字符串的位置，再通过连接索引值和选择的种子字符串作为输出。
[0033] 参考文献
[0034] [1]C.Binnig,D.Kossmann,E.Lo,et al.QAGen:Generating Query‑Aware Test Databases.In SIGMOD,pages 341‑352,2007.
[0035] [2]E.Lo,N.Cheng,and W.‑K.Hon.Generating Databases for Query Workloads.In VLDB,pages 848‑859,2010.
[0036] [3]E.Lo,N.Cheng,Wilfred W.K.Lin,et al.MyBenchmark:generating databases for query workloads.In VLDBJ,pages 895‑913,2014.
[0037] [4]A.Arasu,R.Kaushik,and J.Li.Data Generation using Declarative Constraints.In SIGMOD,pages 685‑696,2011.
[0038] [5]N.Bruno and S.Chaudhuri.Flexible Database Generators.In VLDB,pages 1097‑1107,2005.
[0039] [6]K.Houkjaer,K.Torp,and R.Wind.Simple and Realistic Data Generation.In VLDB,pages 1243‑1246,2006.
[0040] [7]Joseph E.Hoag,and Craig W.Thompson.A Parallel General‑Purpose Synthetic Data Generator.In SIGMOD,pages 19‑24,2007.
[0041] [8]Alexander Alexandrov,Kostas Tzoumas,and Volker Markl.Myriad:Scalable and Expressive Data Generation.In PVLDB,pages 1890‑1894,2012.
[0042] [9]C.Olston,S.Chopra,and U.Srivastava.Generating Example Data for Dataflow Programs.In SIGMOD,pages 245‑256,2009.
[0043] [10]Wentian Lu,Gerome Miklau,and Vani Gupta.Generating Private Synthetic Databases for Untrusted System Evaluation.In ICDE,pages 652‑663,
2014.
2014.
[0044] [11]Quoc Trung Tran,Chee Yong Chan,and Srinivasan Parthasarathy.Query Reverse Engineering.VLDBJ,23(5):721‑746,2014.
[0045] [12]C.Binnig,D.Kossmann,and E.Lo.Reverse Query Processing.In ICDE,pages 506‑515,2007.
[0046] [13]Chaitanya Mishra,Nick Koudas,and Calisto Zuzarte.Generating Targeted Queries for Database Testing,In SIGMOD,pages 499‑510,2008.
[0047] [14]N.Bruno,S.Chaudhuri,and D.Thomas.Generating Queries with Cardinality Constraints for DBMS Testing.IEEE Trans.Knowl.Data Eng.,18(12):
1271‑1275,2006.
1271‑1275,2006.
[0048] [15]S.Cohen.Generating XML Structure using Examples and Constraints.PVLDB,1(1):490‑501,2008.
[0049] [16]J.Leskovec,D.Chakrabarti,J.M.Kleinberg,et al.Realistic,Mathematically Tractable Graph Generation and Evolution,using Kronecker
Multiplication.In PKDD,pages 133‑145,2005.
Multiplication.In PKDD,pages 133‑145,2005.
[0050] [17]S.Lattanzi and D.Sivakumar.Affiliation Networks.In Proceedings of the 41st annual ACM symposium on Theory of computing,pages 427‑434.ACM,2009.
[0051] [18]Entong Shen,Lyublena Antova.Reversing Statistics for Scalable Test Databases Generation.In DBtest,pages 7:1‑7:6,2013.
[0052] [19]T. Logic programs and cardinality constraints–theory and practice.2009.
[0053] [20]P.J.Davis and P.Rabinowitz.Methods of numerical integration.Courier Corporation,2007.
附图说明
[0054] 图1为数据生成器的示例输入。
[0055] 图2为NejGen的基本架构。
[0056] 图3为属性随机生成函数(属性T.t3)。
[0057] 图4为查询参数实例化流程(针对查询Q1)。
具体实施方式
[0058] 结合以下具体实施例和附图，对发明作进一步的详细说明。实施本发明的过程、条件、实验方法等，除以下专门提及的内容之外，均为本领域的普遍知识和公知常识，本发明
没有特别限制内容。
没有特别限制内容。
[0059] NejGen的实现包括以下模块：
[0060] 1.查询实例化：根据给定的数据库结构，以及每个属性的数据特征，首先生成每个属性的随机生成函数。如果某个属性没有指定数据特征，采用相应数据类型默认的数据特
征。针对各个数据类型的生成函数的具体生成机制如下。
征。针对各个数据类型的生成函数的具体生成机制如下。
[0061] 属性生成函数主要包含两个模块，一个是随机索引生成器(Random Index Generator)，一个是索引数值转化器(Transformer)：
[0062] 随机索引生成器会根据该属性的指定基数，生成一个随机索引值，若该属性的指定基数为M，那么生成的随机基数为1至M之间的随机整数。索引数值转化器会依据输入的随
机索引值，生成一个具体的数值作为输出。
机索引值，生成一个具体的数值作为输出。
[0063] 索引数值转化器针对不同的数据类型转化器会采用不同的转化函数。针对数值型数据类型，可以采用简单的线性函数作为转化函数。例如针对属性R.r2，其数据特征为Null
值比例为0，值域为[0,10]，基数为5。采用的转化函数可以为value＝index*2。而针对字符
型数据类型，可以先生成一定量满足字符串长度要求的种子字符串，种子字符串的个数一
般远小于该属性的指定基数。然后转化器根据输入的索引值通过取余运算确定一个种子字
符串的位置，再通过连接索引值和选择的种子字符串作为输出。因为在大数据表的生成时，
指定的基数可能很大，利用少量的种子字符串组装生成满足要求基数的属性值可以大大降
低内存和CPU的消耗。
值比例为0，值域为[0,10]，基数为5。采用的转化函数可以为value＝index*2。而针对字符
型数据类型，可以先生成一定量满足字符串长度要求的种子字符串，种子字符串的个数一
般远小于该属性的指定基数。然后转化器根据输入的索引值通过取余运算确定一个种子字
符串的位置，再通过连接索引值和选择的种子字符串作为输出。因为在大数据表的生成时，
指定的基数可能很大，利用少量的种子字符串组装生成满足要求基数的属性值可以大大降
低内存和CPU的消耗。
[0064] 2.基于相应属性的生成函数，实例化所有基数约束中涉及的符号参数，实例化后的参数保证了各个查询的中间结果集大小在概率期望上与约束的基数一致。查询实例化模
块有两部分的输出，一个是填充了具体参数的实例化查询(供后续测试所用)，一个是数据
表中所有属性的生成函数(作为数据生成模块的输入)。
块有两部分的输出，一个是填充了具体参数的实例化查询(供后续测试所用)，一个是数据
表中所有属性的生成函数(作为数据生成模块的输入)。
[0065] 3.数据生成模块：根据给定的属性生成函数，分布式控制器(Distributed Controller)会依据机器配置信息，将数据生成任务均匀划分到所有的数据生成器(Data
Generator)上，以便最大化地利用硬件资源进行完全并行的数据生成。生成的数据首先以
文本的形式存储在各个节点上，然后再批量导入到待测试的数据库中。
Generator)上，以便最大化地利用硬件资源进行完全并行的数据生成。生成的数据首先以
文本的形式存储在各个节点上，然后再批量导入到待测试的数据库中。
[0066] 基本架构
[0067] 基于上述数据生成问题的定义，NejGen的输入包含：数据表结构，数据表的数据特征和目标负载及其负载特征；NejGen的输出包含：生成的数据库实例和实例化的查询。
NejGen的基本架构主要包含两个模块，分别是查询实例化模块和数据生成模块，如图2所
示。
NejGen的基本架构主要包含两个模块，分别是查询实例化模块和数据生成模块，如图2所
示。
[0068] 查询实例化：根据给定的数据库结构，以及每个属性的数据特征，首先生成每个属性的随机生成函数。如果某个属性没有指定数据特征，如图1示例中的属性R.r3，采用相应
数据类型默认的数据特征。针对各个数据类型的生成函数的具体生成机制见下一小节。然
后基于相应属性的生成函数，实例化所有基数约束中涉及的符号参数，实例化后的参数保
证了各个查询的中间结果集大小在概率期望上与约束的基数一致。查询实例化模块有两部
分的输出，一个是填充了具体参数的实例化查询(供后续测试所用)，一个是数据表中所有
属性的生成函数(作为数据生成模块的输入)。
数据类型默认的数据特征。针对各个数据类型的生成函数的具体生成机制见下一小节。然
后基于相应属性的生成函数，实例化所有基数约束中涉及的符号参数，实例化后的参数保
证了各个查询的中间结果集大小在概率期望上与约束的基数一致。查询实例化模块有两部
分的输出，一个是填充了具体参数的实例化查询(供后续测试所用)，一个是数据表中所有
属性的生成函数(作为数据生成模块的输入)。
[0069] 数据生成模块：根据给定的属性生成函数，分布式控制器(Distributed Controller)会依据机器配置信息，将数据生成任务均匀划分到所有的数据生成器(Data
Generator)上，以便最大化地利用硬件资源进行完全并行的数据生成。生成的数据首先以
文本的形式存储在各个节点上，然后再批量导入到待测试的数据库中。
Generator)上，以便最大化地利用硬件资源进行完全并行的数据生成。生成的数据首先以
文本的形式存储在各个节点上，然后再批量导入到待测试的数据库中。
[0070] 属性生成函数
[0071] 关于属性生成函数，有三点注意事项：1)主键属性并没有属性生成函数，因为主键一般都是按序递增的；2)如果一个属性没有指定相应的数据特征，根据相应数据类型的默
认数据特征构建其生成函数；3)属性的生成函数一旦确定，无论在查询实例化还是数据生
成过程中都不再更改。
认数据特征构建其生成函数；3)属性的生成函数一旦确定，无论在查询实例化还是数据生
成过程中都不再更改。
[0072] 针对不同的数据类型，属性随机生成函数的构建机制有一定的区别。针对数值数据类型的属性，可以指定的数据特征有：Null值比例，值域(最小值和最大值)，基数即非重
复值个数。目前NejGen支持的数值型数据类型有：Integer，Float，Double，Decimal，
DateTime和Boolean。针对字符数据类型的属性，可以指定的数据特征有：Null值比例，基
数，字符串的平均长度和最大长度。目前NejGen支持的字符类型有Varchar。
复值个数。目前NejGen支持的数值型数据类型有：Integer，Float，Double，Decimal，
DateTime和Boolean。针对字符数据类型的属性，可以指定的数据特征有：Null值比例，基
数，字符串的平均长度和最大长度。目前NejGen支持的字符类型有Varchar。
[0073] 属性生成函数主要包含两个模块，一个是随机索引生成器(Random Index Generator)，一个是索引数值转化器(Transformer)，针对属性T.t3的示例属性随机生成函
数见图3。随机索引生成器会根据该属性的指定基数，生成一个随机索引值，若该属性的指
定基数为M，那么生成的随机基数为1至M之间的随机整数。索引数值转化器会依据输入的随
机索引值，生成一个具体的数值作为输出。针对不同的数据类型有，转化器会采用不同的转
化函数。针对数值型数据类型，可以采用简单的线性函数作为转化函数。例如针对属性
R.r2，其数据特征为Null值比例为0，值域为[0,10]，基数为5。采用的转化函数可以为value
＝index*2。而针对字符型数据类型，可以先生成一定量满足字符串长度要求的种子字符
串，种子字符串的个数一般远小于该属性的指定基数。然后转化器根据输入的索引值通过
取余运算确定一个种子字符串的位置，再通过连接索引值和选择的种子字符串作为输出，
具体见图3中的Transformer。因为在大数据表的生成时，指定的基数可能很大，利用少量的
种子字符串组装生成满足要求基数的属性值可以大大降低内存和CPU的消耗。
数见图3。随机索引生成器会根据该属性的指定基数，生成一个随机索引值，若该属性的指
定基数为M，那么生成的随机基数为1至M之间的随机整数。索引数值转化器会依据输入的随
机索引值，生成一个具体的数值作为输出。针对不同的数据类型有，转化器会采用不同的转
化函数。针对数值型数据类型，可以采用简单的线性函数作为转化函数。例如针对属性
R.r2，其数据特征为Null值比例为0，值域为[0,10]，基数为5。采用的转化函数可以为value
＝index*2。而针对字符型数据类型，可以先生成一定量满足字符串长度要求的种子字符
串，种子字符串的个数一般远小于该属性的指定基数。然后转化器根据输入的索引值通过
取余运算确定一个种子字符串的位置，再通过连接索引值和选择的种子字符串作为输出，
具体见图3中的Transformer。因为在大数据表的生成时，指定的基数可能很大，利用少量的
种子字符串组装生成满足要求基数的属性值可以大大降低内存和CPU的消耗。
[0074] 查询实例化
[0075] 在确定所有属性的生成函数之后，生成数据库实例的数据分布就已经确定了。基于生成数据库实例已经确定的数据分布，NejGen采用二分搜索(binary search)的思想和
数值积分(numerical integration)[20]的计算方法实例化所有基数约束中的符号参数。
由于针对每个查询树中的基数约束处理是完全相同的，下面仅基于图1中Q1给出查询参数
实例化的基本流程，见图4。
数值积分(numerical integration)[20]的计算方法实例化所有基数约束中的符号参数。
由于针对每个查询树中的基数约束处理是完全相同的，下面仅基于图1中Q1给出查询参数
实例化的基本流程，见图4。
[0076] 针对一个查询树中的所有基数约束，必须采用自底向上的处理方式，因为孩子节点中的查询参数若没有确定，相应父亲节点的输入数据集便无法确定，从而后续的二分搜
索以及数值积分便无从开展。在图4中，针对查询Q1，先处理两个孩子节点上的基数约束，实
例化参数P1和P2后，父亲节点(即非等值连接R.r3+S.s2≥P3)的输入数据集便可以根据原
始数据表信息和两个孩子节点中的选择谓词(predicate)确定。接下来详细介绍针对一个
基数约束，如何实例化其中的符号参数。
索以及数值积分便无从开展。在图4中，针对查询Q1，先处理两个孩子节点上的基数约束，实
例化参数P1和P2后，父亲节点(即非等值连接R.r3+S.s2≥P3)的输入数据集便可以根据原
始数据表信息和两个孩子节点中的选择谓词(predicate)确定。接下来详细介绍针对一个
基数约束，如何实例化其中的符号参数。
[0077] 由于属性的生成函数是离散的，不利于查询参数实例化过程中的数学计算，因此首先需将离散的属性生成函数连续化，具体的转化机制通过属性R.r2和S.s3进行阐述。属
性R.r2的数据特征为Null值比例为0，值域为[0,10]，基数为5。随机生成函数为：index＝
random[1,5],value＝index*2。可以将该离散函数转化成连续函数：y＝x,x∈[0,10]。属性
S.s3的数据特征为Null值比例为10％，值域为[‑100,0]，基数未作设定(由于表S大小为20，
基数默认设置为20*(1–10％)＝18)。随机生成函数为：index＝random[1,18],value＝
index*5。该离散函数可转化为连续函数：y＝x,x∈[‑100,0]。
性R.r2的数据特征为Null值比例为0，值域为[0,10]，基数为5。随机生成函数为：index＝
random[1,5],value＝index*2。可以将该离散函数转化成连续函数：y＝x,x∈[0,10]。属性
S.s3的数据特征为Null值比例为10％，值域为[‑100,0]，基数未作设定(由于表S大小为20，
基数默认设置为20*(1–10％)＝18)。随机生成函数为：index＝random[1,18],value＝
index*5。该离散函数可转化为连续函数：y＝x,x∈[‑100,0]。
[0078] 针对基数约束c1＝[Q1,R.r2据表的大小；这里暂不考虑<,<＝的区别，因为在大数据集下两者基本没有区别，虽然在当
前示例下参数值为4.01更合适)。针对基数约束c2＝[Q1,S.s3>P2,13]，数据表S的大小为
20，P2的值可按比例在值域上直接取为‑100*(13/18)＝‑72(其中18＝20*(1–10％)，10％为
Null值的比例)。但是对于复杂的谓词表达式，这种方法显然是不通用的，如谓词R.r2^3‑
R.r3始数据表和孩子节点上实例化的谓词约束共同确定，上述方法显然也是不可行的。当然，对
于具有简单谓词表达式的选择操作，其基数约束可采用此种方法实例化查询参数。
前示例下参数值为4.01更合适)。针对基数约束c2＝[Q1,S.s3>P2,13]，数据表S的大小为
20，P2的值可按比例在值域上直接取为‑100*(13/18)＝‑72(其中18＝20*(1–10％)，10％为
Null值的比例)。但是对于复杂的谓词表达式，这种方法显然是不通用的，如谓词R.r2^3‑
R.r3
于具有简单谓词表达式的选择操作，其基数约束可采用此种方法实例化查询参数。
[0079]
[0080]
[0081] 通用参数实例化算法见Algorithm 1。算法1的主要思想是：将查询空间转化为数学空间，基数约束中关于中间结果集的期望大小可以由数学空间中关于基数约束中谓词的
数值积分值来表示。在待实例化参数的值域内，根据二分搜索的思想先给出符号参数的预
测值，然后基于当前预测的参数值，利用数值积分得到中间结果集在概率期望上的大小，再
根据误差判断直至搜索到满足误差要求的参数值。若迭代次数已达到上限，返回当前参数
的预测值。后面基于示例基数约束c3给出算法1的详细说明。c3＝[Q1,R.r3+S.s2≥P3,20]。
在处理c3之前，c1＝[Q1,R.r2P2,13]中的参数P1和P2应已经实例
化，由前文可知P1＝4,P2＝‑72。
数值积分值来表示。在待实例化参数的值域内，根据二分搜索的思想先给出符号参数的预
测值，然后基于当前预测的参数值，利用数值积分得到中间结果集在概率期望上的大小，再
根据误差判断直至搜索到满足误差要求的参数值。若迭代次数已达到上限，返回当前参数
的预测值。后面基于示例基数约束c3给出算法1的详细说明。c3＝[Q1,R.r3+S.s2≥P3,20]。
在处理c3之前，c1＝[Q1,R.r2
化，由前文可知P1＝4,P2＝‑72。
[0082] 在算法中的第1行，获取当前非等值连接操作的查询空间大小。针对非等值连接操作R.r3+S.s2≥P3，数据表R大小为10，数据表S大小为20，非等值连接操作涉及属性R.r3和
S.s2都没有Null值，孩子节点中涉及的属性R.r2也没有Null值，但属性S.s2含有10％的
Null值。因此查询空间大小应为：10*(20*(1‑10％))＝180(S表中10％的记录因为在属性
S.s2上含有Null值而被忽略不计；因为是多表，所以需作笛卡尔积)。因为c3.s＝20，所以q_
ratio＝20/180＝11.11％。基数约束c2的谓词表达式涉及两个属性R.r3和S.s2，两者相应
连续函数分别为y＝x1,x1∈[0,10](关于数值型数据类型，默认数据特征的值域最小值为
0，最大值为数据表大小)，y＝x2,x2∈[0,100]。c2孩子节点中的谓词表达式涉及另两个属
性R.r2和S.s3，连续函数分别为y＝x3,x3∈[0,10]和y＝x4,x4∈[‑100,0]。因此，算法第三
行中的数学空间大小为：10*100*10*|‑100|＝10^6。在算法第4行，需要计算出符号参数的
值域，即R.r3+S.s2表达式的最小值和最大值，易得min_value＝0,max_value＝110，此时参
数p被初始化为(0+110)/2＝55。算法5至13行是针对参数p(若输入为c3，即为参数P3)的二
分搜索。首先在算法第6行，将基数约束c中的符号参数实例化为预测值p＝55，此时c.p＝
R.r3+S.s2≥55(c.p为基数约束的谓词)。算法第7行基于当前的预测参数值(即p＝55)，利
用数值积分的方法计算出中间结果集在数学空间中的相对大小。数值积分的具体表示如
下：
S.s2都没有Null值，孩子节点中涉及的属性R.r2也没有Null值，但属性S.s2含有10％的
Null值。因此查询空间大小应为：10*(20*(1‑10％))＝180(S表中10％的记录因为在属性
S.s2上含有Null值而被忽略不计；因为是多表，所以需作笛卡尔积)。因为c3.s＝20，所以q_
ratio＝20/180＝11.11％。基数约束c2的谓词表达式涉及两个属性R.r3和S.s2，两者相应
连续函数分别为y＝x1,x1∈[0,10](关于数值型数据类型，默认数据特征的值域最小值为
0，最大值为数据表大小)，y＝x2,x2∈[0,100]。c2孩子节点中的谓词表达式涉及另两个属
性R.r2和S.s3，连续函数分别为y＝x3,x3∈[0,10]和y＝x4,x4∈[‑100,0]。因此，算法第三
行中的数学空间大小为：10*100*10*|‑100|＝10^6。在算法第4行，需要计算出符号参数的
值域，即R.r3+S.s2表达式的最小值和最大值，易得min_value＝0,max_value＝110，此时参
数p被初始化为(0+110)/2＝55。算法5至13行是针对参数p(若输入为c3，即为参数P3)的二
分搜索。首先在算法第6行，将基数约束c中的符号参数实例化为预测值p＝55，此时c.p＝
R.r3+S.s2≥55(c.p为基数约束的谓词)。算法第7行基于当前的预测参数值(即p＝55)，利
用数值积分的方法计算出中间结果集在数学空间中的相对大小。数值积分的具体表示如
下：
[0083]
[0084] 其中x1+x2≥55为基于预测参数值的c.p，x3＜4&x4＞‑72为孩子节点上实例化的谓词约束。NejGen中的数值积分目前由数学工具Mathematica计算，因此易得inte_size＝
1.44*10^5，此时m_ratio＝inte_size/m_size＝(1.44*10^5)/10^6＝14.4％。算法9‑11行
判断当前预测参数值的误差是否小于最大允许误差e和当前迭代次数是否达到上限k，确定
是否退出算法并返回实例化的参数值。若算法没有退出，算法12行根据二分搜索的思想重
置参数p的值。在上述示例中，因为14.4％大于11.11％，并且参数p前的逻辑运算符为≥，因
此重置p＝(55+110)/2＝82.5，继续迭代直至退出算法。由于算法1关于解(符号参数值)的
搜索是指数收敛的，解的精度可以得到有效的保证，并且算法1可处理含有任意连接谓词的
非等值连接负载。
1.44*10^5，此时m_ratio＝inte_size/m_size＝(1.44*10^5)/10^6＝14.4％。算法9‑11行
判断当前预测参数值的误差是否小于最大允许误差e和当前迭代次数是否达到上限k，确定
是否退出算法并返回实例化的参数值。若算法没有退出，算法12行根据二分搜索的思想重
置参数p的值。在上述示例中，因为14.4％大于11.11％，并且参数p前的逻辑运算符为≥，因
此重置p＝(55+110)/2＝82.5，继续迭代直至退出算法。由于算法1关于解(符号参数值)的
搜索是指数收敛的，解的精度可以得到有效的保证，并且算法1可处理含有任意连接谓词的
非等值连接负载。
[0085] 算法1的复杂度可由迭代次数与数值积分的代价相乘表示。因为算法1采用了二分搜索的思想，迭代次数是logN的，N为符号参数的值域。而数值积分的代价一般与涉及的变
量数目和被积分表达式的复杂度相关，由于非等值连接谓词中往往仅包含一些线性运算，
并且NejGen采用了高效的数学计算工具Mathematica支持数值积分运算，因此数值积分的
代价可看作是一个常量。综上，算法1是高效的。
量数目和被积分表达式的复杂度相关，由于非等值连接谓词中往往仅包含一些线性运算，
并且NejGen采用了高效的数学计算工具Mathematica支持数值积分运算，因此数值积分的
代价可看作是一个常量。综上，算法1是高效的。
[0086] 数据生成
[0087] 在图2中，查询实例化模块将基于用户指定数据特征而构建的属性随机生成函数传递给数据生成模块，数据生成模块主要负责多节点并行的模拟数据库生成。由于具有每
个属性的生成函数，数据生成是相对容易的，仅需考虑如何做到充分的并行以及数据生成
任务的划分。数据生成主要分为两个步骤：(1)首先根据机器配置，将所有的数据生成任务
均匀划分到每个节点的每个数据生成线程上。每个节点上开启的数据生成线程数为当前节
点CPU的最大并行度，并对所有节点上的线程编号。例如，有三个节点，每个节点的最大并行
度为10，那么可以在每个节点上开启10个数据生成线程，针对所有数据生成线程依次编号
为：0,1,2,…,29。(2)然后在数据生成的过程中，针对每个数据表的主键值，每个数据生成
线程都有一个相应的起始id，并设置为当前线程编号，每生成一条记录，该id的值加上总线
程数。例如，在上面的示例中，0号线程生成的记录主键值为：0,30,60,…；1号线程生成的记
录主键值为：1,31,61,…。在数据生成过程中，每个数据生成线程的输出文件相互独立，并
采用缓存异步刷盘的方式提高性能。生成的数据文件可利用相应的导入工具导入到待测试
数据库中。
个属性的生成函数，数据生成是相对容易的，仅需考虑如何做到充分的并行以及数据生成
任务的划分。数据生成主要分为两个步骤：(1)首先根据机器配置，将所有的数据生成任务
均匀划分到每个节点的每个数据生成线程上。每个节点上开启的数据生成线程数为当前节
点CPU的最大并行度，并对所有节点上的线程编号。例如，有三个节点，每个节点的最大并行
度为10，那么可以在每个节点上开启10个数据生成线程，针对所有数据生成线程依次编号
为：0,1,2,…,29。(2)然后在数据生成的过程中，针对每个数据表的主键值，每个数据生成
线程都有一个相应的起始id，并设置为当前线程编号，每生成一条记录，该id的值加上总线
程数。例如，在上面的示例中，0号线程生成的记录主键值为：0,30,60,…；1号线程生成的记
录主键值为：1,31,61,…。在数据生成过程中，每个数据生成线程的输出文件相互独立，并
采用缓存异步刷盘的方式提高性能。生成的数据文件可利用相应的导入工具导入到待测试
数据库中。
[0088] 实验结论
[0089] 实验环境
[0090] 实验硬件配置：5个物理节点，每个节点含有2个CPU，型号为Intel Xeon E5‑2620@2.0GHz；内存为64GB；存储为3TB，RAID‑5，7200转的HDD磁盘。物理节点之间使用千兆以太网
通信。
通信。
[0091] 性能评测
[0092] 实验一：输入如图1，但是数据表R，S，T的大小分别为10^8，2*10^8和5*10^8，其他不变。数据生成节点由1个不断增加到5个，观察数据生成时间和基数约束最大误差。
[0093]
[0094]
[0095] 实验二：输入如图1，但是数据表R，S，T的大小分别为10^n，2*10^n和5*10^n，n＝5,6,7,8,9，其他不变。数据生成节点为5个，观察数据生成时间和基数约束最大误差。
[0096]n的大小 5 6 7 8 9
数据生成时间 0.821s 1.280s 4.433s 36.236s 359.642s
基数约束最大误差 0.0078 0.0015 0.00042 0.00021 0.00007
数据生成时间 0.821s 1.280s 4.433s 36.236s 359.642s
基数约束最大误差 0.0078 0.0015 0.00042 0.00021 0.00007
[0097] 通过实验数据可知，NejGen对于数据生成节点数和生成数据库实例的数据量大小都是线性可扩展的；NejGen的数据生成吞吐量在5个节点时大约为每秒2*10^7条记录；并且
基数约束的误差也随着生成数据量的增大而逐渐减小。
基数约束的误差也随着生成数据量的增大而逐渐减小。
[0098] 本发明的保护内容不局限于以上实施例。在不背离发明构思的精神和范围下，本领域技术人员能够想到的变化和优点都被包括在本发明中，并且以所附的权利要求书为保
护范围。
护范围。