Query cardinal number estimation method based on grouping mask autoregression model

技术领域

本发明属于数据库查询技术领域，具体涉及一种查询基数估计方法。

背景技术

伴随着信息时代的高速发展，数据库中的数据存量增长迅速，数据库关系模式也日趋复杂，想要在这种情况下进行查询优化，查询优化器需要能在复杂模式下具有更高准确性和稳定性的基数估计模型。传统基数估计方法大致包含直方图、数据画像与采样三种方法，但是在如今的复杂条件下它们的准确性都难以满足的查询优化的需求。

由上，基于机器学习的基数估计方法逐渐走进了人们的视野，针对训练对象的不同，现有的基于机器学习的基数估计方法大致可分为由查询驱动的机器学习基数估计方法和数据驱动的机器学习基数估计方法。查询驱动的方式利用神经网络模型去学习查询条件与对应基数的映射关系，数据驱动的方式使用和积网络、自回归模型等模型学习数据的联合概率分布。这些方法相比于传统基数估计防范都具有更高的准确性。

目前，基于自回归模型的数据驱动方法能适应更多的负载场景，且具有更高的准确性。但是，自回归模型难以拟合某些数据列的联合概率分布，导致涉及这些列的查询出现较大误差，进一步导致查询优化器选择错误的计划；同时，也有方案利用查询条件与其基数结果和数据去优化自回归模型，使得该方法同时由数据和查询驱动，具有更高的准确性，但是代价是大幅增加的训练时间，由此导致模型实时性降低，难以满足数据库查询优化需求。

发明内容

本发明的目的在于提供一种具有高准确性，又满足数据库查询优化需求的基于分组掩码自回归模型的查询基数估计方法。

本发明提出的基于分组掩码自回归模型的查询基数估计方法，具体步骤包含：列数据分组预处理、分组掩码神经网络基数估计模型的训练。

步骤(一)列数据分组预处理；

具体是将单表数据以列为单位，按照信息熵从小到大进行分组；分组后在组内按列间相关性与相对熵(KL散度)的加权平均进行组内排序。排序后的数据按照分组附加不同顺序的掩码输入分组掩码神经网络基数估计模型，并进行训练。经过分组预处理的单表数据更有利于使用自回归模型进行预测，降低自回归模型的预测误差，且之后的神经网络按分组对数据附加掩码进行训练。

进一步地：

所述数据列分组阶段，计算所有数据列的信息熵，按信息熵从小到大进行排序，排序前列为{X₁，X₂...X_n}，排序后为{X₁′，X₂′...X_n′}，这一过程表示为：

{X₁′，X₂′...X_n′}＝Sort(H(X₁)，H(X₂)...H(X_n))，  (1)

排序完成后，按照信息熵对数据列进行聚类，聚类方法可以使用K-means等聚类方法，μ_j为聚类过程中第j类的聚类中心，聚类的目标函数可以表示为：

完成数据列分组后进行组内排序，设组内存在k列，排序前列为{X₁，X₂...X_k}，排序后为{X₁′，X₂′...X_k′}，每列数据i计算其与组内其他列j的关系值R(i，j)，R(i，j)可以由相关性r(i，j)与相对熵(KL散度)D_KL(i，j)进行加权平均产生：

R(i，j)＝w₁*r(X_i，X_j)-w₂*D_KL(X_i，X_j)，  (3)

列间相关性计算可以使用成对数据最小方法、皮尔逊积矩相关系数等。以原先的组内第一列作为开始，后续选取未参与排序且与已经完成排序的前一列之间关系值R(i，j)最大的列作为组内排序的下一个列，列选取为：

X′_i+1＝X_j＝max_j∈{i}[]{j}R(i，j)，  (⁴)

其中，第一列为X₁′＝X₁。

(二)分组掩码神经网络基数估计模型的训练；

所述分组掩码神经网络基数估计模型采用自回归神经网络模型，以下简称模型，包括使用原始数据与在原始数据上的查询与查询结果，对自回归神经网络模型进行训练学习，获取原始数据中不同列不同取值的联合概率分布，且可以使用掩码机制针对(一)中生成的数据分组与重点查询的概率分布进行优化学习。本发明可以使用多种自回归神经网络模型，当前所使用的是由Mathieu Germain在2015年ICML上发表论文《MADE：MaskedAutoencoder for Distribution Estimation》中的掩码自回归模型，结构可见图1。

模型训练分为数据训练、混合掩码训练、直接查询训练三个训练阶段。在使用数据进行训练时，首先对数据进行编码，对于不同值数量大于64的列可以采用独热编码，对于不同值数量大于64的列可以使用词向量编码。同时需要在每条数据前附加当前预测位置的编码。

三个训练阶段总体如下：

数据训练阶段，将长度为n数据序列扩展为n×n的矩阵数据，对相同的数据矩阵按照分组附加不同的掩码矩阵以进行不同顺序的训练学习，其中一数据中顺序对应一种n×n大小的掩码矩阵，掩码按分组为单位进行施加，掩码矩阵与数据矩阵相乘得到训练数据，将训练数据输入神经网络进行训练；

混合掩码训练阶段，选取测试查询中误差大于设定阈值η₁的查询，根据查询所涉及的列条件顺序生成对应掩码矩阵，掩码矩阵与数据矩阵相乘得到训练数据，训练数据输入神经网络进行训练；

直接查询训练阶段，需要选择经过前两步训练后误差大于定阈值η₂的查询，将其加入数据集中，利用重参数技巧，或者拆分为子查询，直接对模型进行训练，这些查询可以来自预先设置的测试集，也可以来自在实际使用中日志记录查询。

具体训练过程如下：

(1)对于一组长度为n的存储数据，首先按照列数据分组预处理方法分组后得到k组数据，k的值视列数量与聚类情况确定，通常可以取[2-4]。按组为单位生成种随机排列。

(2)数据训练阶段，对于第一步中生成的随机排列，根据排列顺序生成对应的掩码矩阵M₁与位置序列P₁。将掩码矩阵M₁与m个数据序列扩展n*n数据矩阵进行相乘，得到掩码后的数据矩阵，数据矩阵左方附加位置序列。如果排序数量，可以根据训练集或验证集的查询条件选择部分次序进行保留。随后将数据矩阵输入神经网络模型，神经网络输出在当前序列下需要预测变量的条件概率分布。将该分布与输入数据计算交叉熵作为模型损失loss₁，并进行反向传播训练神经网络模型，设定epoch₀次训练周期进行训练。

以6列数据为例，按分组[(1，2)，(3，4)，(5，6)]分为3组，产生一种组间顺序为：Sq＝(3，4)-(5，6)-(1，2)，该序列的掩码矩阵M₁为：

该序列产生的位置序列P₁为：

将数据单条数据扩展为n*n大小的数据矩阵D₁，将掩码矩阵乘以数据矩阵并拼接位置序列得到该次训练数据D₁′：

此时产生的掩码矩阵附加与对应训练的条件概率分布见图2所示，图中实线位置代表掩码矩阵值为1模型可见该位置值；虚线位置代表附加遮蔽，掩码值为0模型不可见此处数据值。

当分组数量超过4导致排序数量超过6时，或者后两阶段的训练数据集增长至严重影响模型训练时间时，可以根据训练集或验证集的查询条件选择部分次序进行保留，以减少这一阶段的模型训练时间。统计训练集或验证集的联合列条件分布情况，例如同时涉及{4，6}两列的查询较多时，可以保留Sq＝(3，4)-(5，6)-(1，2)这一次序使得模型可以跳过部分列而学习{4，6}两列的联合概率分布。

(3)混合掩码训练阶段，设定误差阈值η₁，阈值通常设置为1.5，也可以根据模型的实际精度需求自行确定。选择经过数据训练阶段后误差q_error大于η₁的查询条件生成掩码样本，这些查询可以来自预先设定好的训练集与实际使用时的查询日志之中，阈值越接近1时会收集更多的查询，模型会更加精确。设查询Q＝{X₁∈R₁，X₂∈R₂...X_n∈R_n}，设X_i值域为R_i′，如果R_i≠R_i′，则认为查询Q在i列上存在条件。根据查询是否在i列上存在条件，可以从查询中生成如下序列S＝{f₁，f₂...f_n}，掩码矩阵长度L＝sum(S)，其中：

根据序列S生成掩码矩阵与位置序列，矩阵大小为n*L，以6列数据为例，设Q＝{X₁∈R₁，X₃∈R₃，X₄∈R₄}为例，可以得到S＝{1，0，1，1，0，0}，掩码矩阵M₂为：

位置序列P₂为：

将数据单条数据扩展为对应L*n大小的数据矩阵D₂，将掩码矩阵乘以数据矩阵并拼接位置序列得到该次训练数据D₂′：

将该数据与第一阶段的训练数据一起输入模型进行训练，计算模型输出，与原始数据对应位置分布的交叉熵作为损失loss₂，并于第一阶段的loss₁一同进行反向传播对模型进行训练。

(4)直接查询训练阶段，挑选出经过前两阶段训练后误差值大于设定阈值η₂的查询Q，使用查询条件与其基数值对模型进行训练，阈值η₂通常设置为1.8，也可以根据模型的实际精度需求自行确定，通常需要大于η₁。这些查询可以来自预先设置的测试集，也可以来自在实际使用中日志记录查询。直接查询阶段可以使用重参数技巧直接对所有类型的查询进行训练，也可以将范围查询分解为多个对应的点查询重新执行。对于范围查询，利用重参数技巧对模型输出结果与实际的label计算q_error作为损失loss₃，结合前两个阶段的loss₁与loss₂对神经网络模型进行反向传播训练。对于只包含等于条件的查询q，可以将符合查询的序列直接输入模型得到估计值sel(q)′，与查询q的选择率sel(q)计算q_error作为损失进行对分组掩码神经网络基数估计模型反向传播。

由上可见，本发明关于基数估计模型的三个阶段的训练采用混合训练的方式，即首先使用经过预处理后的数据对模型进行数据训练阶段的训练，属于初始化训练；随后统计训练集查询与实际查询的查询信息与结果，用于混合掩码训练与直接查询训练阶段，当对应阶段的超过误差阈值的查询出现次数大于预先设定的阈值时，会触发对应训练阶段完成对(二)中神经网络模型的训练。

基数估计模型混合训练中，需设定误差阈值η₁与η₂，设定查询数量统计阈值N_η1与N_η2，两阶段训练轮次epoch₁与epoch₂，记录在测试阶段与实际使用阶段误差分别大于阈值的查询Q与对应的出现次数N_Q1与N_Q2，当对应阶段的超过误差阈值的查询出现次数N_Q大于N_η时，该训练器会触发对应的混合掩码训练或直接查询训练，对模型进行轮次为epoch_1or2的训练。

该基数估计模型混合训练，在使用与测试时，将误差超过η₂的查询Q拆分为只包含点查询的子查询q并在系统空余时刻自动执行得到选择率sel(Q)。子查询结果会记录在日志中，训练器将其中产生的误差大于η₂(可以默认η₂＝1.8)的子查询加入直接查询训练阶段的训练数据中。

拆分查询可以表达为：

split(Q)＝[q₁，q₂，...q_n]，

设Q＝{X₁∈R₁，X₃∈R₃，X₄∈R₄}，

则有：split(Q)＝[q₁＝{X₁＝x₁}，Q₃＝{X₁＝x₁，X₃＝x₃}，Q₄＝{X₁＝x₁，X₃＝x₃，X₄＝x₄}]，

其中，x_i∈R_i，x_i为R_i范围内的随机取值。该查询总共可以拆分为R₁*R₃*R₄个子查询，从查询中进行随机取值，取其中产生较大误差的子查询加入数据集中。

本发明的基于分组掩码自回归模型的查询基数估计方法具有以下优势：

本发明的模型与其训练方法混合了数据驱动与查询驱动对模型进行学习，可以适应不同类型的训练数据组合情况。同时本发明提出的通过掩码由查询指导数据方面的训练方法可以减少训练时间，同时可以使模型相比于传统自回归方法可以更好地获取数据之间的联合概率分布，以提高基数估计的准确性帮助数据库生成更良好的查询计划。

基数估计模型混合训练的流程参见图3所示。