2018, Vol. 29
2. 浙江省大数据智能计算重点实验室(浙江大学), 浙江 杭州 310027;
3. 浙江大学 计算机辅助设计与图形学国家重点实验室, 浙江 杭州 310027
2. Key Laboratory of Big Data Intelligent Computing of Zhejiang Province(Zhejiang University), Hangzhou 310027, China;
3. State Key Laboratory of CAD & CG, Zhejiang University, Hangzhou 310027, China
随着数据库中数据量的与日俱增和查询的日益复杂, 数据库负载管理、查询调度面临极大的挑战.负载管理要解决的核心问题就是查询执行时间的预测.对于用户提交的查询任务, 管理系统要判断是否执行; 若执行就要确定任务执行顺序; 如果一个任务执行很久没有结束, 需要判断是否继续执行或者强制结束.无法预计时间的长时查询, 是计算机资源耗尽的根源所在.如果在查询执行之前能够确定其运行时间, 就可以取消执行无法在期望时间内完成的查询, 或者在不影响其他查询的情况下执行.但是, 由于数据库系统的复杂性和计算机资源的竞争, 很难精确地估计不同数据库操作的开销.因此, 查询开销预测成为一个重要的研究问题.
除此以外, 预测查询执行时间对于数据库管理领域的其他方面也有重要意义[1], 如权限控制[2, 3]、进度监控[4]和系统规模定制[5].
针对查询开销的预测问题, 研究人员提出了许多面向关系型数据库的查询开销预测方案.其中, 有些研究没有预测出真实的运行时间, 而是估计了查询完成的百分比或者输出了一个任意单位的值来代表查询开销, 类似于查询优化器的开销预测; 有些研究需要运行时性能统计, 而这又需要额外的开销去产生统计数据[6].
虽然上述研究方案在一定程度上解决了查询开销预测的问题, 但是都有各自的局限性:第一, 开销预估的结果是任意单位, 很难映射到时间单位, 无法支持负载管理中的一些决策; 第二, 预测需要查询执行中的信息, 无法在查询执行前就给出预测.
为了解决以上问题, 本文提出了一种基于循环神经网络的查询开销预测方法, 该方法不仅能够预测查询计划的执行时间, 而且在查询执行前就可以得到预测结果.模型主要分为编码和预测两个模块:编码模块能够接受一个JSON格式的查询计划并产生与它等价的特征向量; 预测模块用于预测该查询计划的开销.
本文的主要贡献如下:
(1) 设计了一种编码方法, 将树形结构的查询计划转换成特征向量, 并尽可能保留其影响开销的信息;
(2) 提出了一种基于循环神经网络的查询开销预测模型.给定一个查询计划, 在计划实际执行前, 模型就能够产生该查询计划实际运行时间的预测;
(3) 通过实验验证, 不管是短时间运行的查询还是长时间运行的查询, 模型的预测结果都较为准确.模型的正确率高于71%, 在一定程度上证明了本文模型的可行性.
本文第1节介绍相关的研究成果.第2节描述模型要解决的问题.第3节介绍模型的设计和实现.第4节通过分析实验的结果, 验证模型的可行性.第5节总结全文并提出未来工作的展望.
1 相关工作 1.1 查询开销预测数据库查询优化器根据开销模型产生的开销预估比较不同计划的好坏.使用PostgreSQL提供的explain操作, 可以输出查询计划的开销预估.但是这个开销模型并不擅长预测开销具体的执行时间, 因为它只反映了优化器所关心的部分, 而忽略了一些影响开销的重要因素.例如, 开销模型没有考虑结果行传递给客户端所花费的时间, 优化器忽略了它的原因是对于不同的计划, 它的值不会产生变化.但是对于负载管理, 这个重要因素不能被忽略.其次, 这个开销模型依赖于直方图或者应用采样技术.由于空间有限, 直方图间隔尺寸不能太细, 因此开销预测就会不准确.最后, 大多数优化器使用的单位是任意单位, 无法轻易地映射到时间单位[6].
与查询优化器不同的是, 查询进度指示器能够给出时间单位的预测, 而且它使用了基于操作行为和运行信息的一个更为精细的模型.本文中的模型也是基于操作层面的信息建立的.但是查询进度指示器不能在查询执行前进行开销预测, 它预测的是运行中的查询完成进度[6].
文献[6]提出使用机器学习的方法预测查询开销, 与本文最大的区别在于其处理特征向量的方法丢失了查询计划的结构信息.文献[7]提出一种能够对数据库系统工作负载类型分类的模型, 试图去解决性能调优问题, 但并没有直接给出查询开销的预测.文献[8]使用统计机器学习技术建立了查询计划层面信息和操作层面信息的模型以及混合两者的模型来预测查询性能, 但没有直接预测查询执行时间.同样使用统计机器学习技术来预测开销的还有文献[9, 10].
文献[11]首次提出了应用循环神经网络(recurrent neural network, 简称RNN)到数据库查询优化领域的思想概括, 而本文运用LSTM解决了具体问题并实现验证了方法的可行性.现在, 越来越多的研究尝试使用深度学习方法来解决数据库领域的问题.例如, 文献[12]运用LSTM预测一段时间内将要执行查询的数量, 解决了负载管理领域的另一个问题.
1.2 神经网络前馈神经网络(feedforward neural network, 简称FNN)是最基础的神经网络, 网络拓扑结构上不存在环或者回路.图 1展示了FNN的结构, 包括一个输入层、一个或多个隐藏层和一个输出层.输入层接收一个向量:x=(a0, a1, …, an-1).即, 输入层有n个神经元并且每一个神经元都有特定的值ai.uj是第1个隐藏层的第j个神经元.uj可以按照公式(1)计算:
| $ {u_j} = f\left( {\sum\limits_{i = 0}^{n - 1} {{w_{ij}}{a_i}} + {b_j}} \right) $ | (1) |
|
Fig. 1 FNN model structure 图 1 FNN模型结构 |
f是激活函数, 例如典型的激活函数有ReLU和tanh.wij是从输入层的第i个神经元到隐藏层的第j个神经元之间的权重, 而bj是偏移量.
通常, 为了简化表达, 可以使用向量U、向量B和矩阵W来重写公式(1), 见公式(2):
| $ U = f\left( {Wx + B} \right) $ | (2) |
每一个隐藏层都会调用上述的计算过程, 该计算过程被称为正向传播.最终, 最后一个隐藏层计算得到输出向量o=(l0, l1, …, lm-1).输出向量会与真实的结果进行比较, 并计算出预测误差, 反向传播至隐藏层来调整层与层之间的权重矩阵.反向传播可以使用随机梯度下降方法(stochastic gradient descent, 简称SGD).
FNN很难对随时间状态变化的过程建模, 例如股票价格预测和语音识别.其原因是:FNN主要利用窗处理来做时序预测, 但模型受限于窗的大小(帧数).
而RNN比FNN多了时间步(time step)的概念, 当前时刻的预测同时取决于当前输入和上一时刻的状态.因此, RNN特别适用于处理声音、时间序列数据或自然语言等序列数据.图 2是RNN随时间展开后的结构.
|
Fig. 2 The expanding RNN model structure 图 2 展开的RNN模型结构 |
通过图 1和图 2中FNN和RNN模型结构的比较不难发现, RNN本质上是FNN在时间维度上的扩展.将图 2简化一下, RNN的模型结构如图 3所示.
|
Fig. 3 RNN model structure 图 3 RNN模型结构 |
在时间状态t, 神经模块收到输入xt=(a0, a1, …, an-1), 隐藏层按照公式(3)计算:
| $ {h_t} = f(W{x_t} + \bar W{h_{t - 1}} + B) $ | (3) |
f, W和B都与之前定义的一致.
LSTM有3个门:输入门、遗忘门和输出门.本文采用了LSTM的一种变种——peephole connection[14].这个变种在LSTM的3个门的计算中加入了细胞状态.第3.2节将详细阐述这种特殊LSTM的结构.
2 问题与方法图 4展现了传统查询优化器的基本结构[15], 包括两个最重要的模块:查询生成器和搜索算法.查询生成器应用转换规则产生可能的逻辑和物理计划, 而搜索算法依据开销模型指导查询生成器产生高质量的候选计划.最终, 优化器产生了较好的查询计划并用于执行.计划的实际运行统计会反馈给查询优化器并对其进行调节.
|
Fig. 4 Process of query optimization 图 4 查询优化过程 |
开销模型预测的准确性直接影响了查询优化器的性能.为了估计不同数据库操作的开销, 现有的方法是建立直方图[16, 17]或者是应用采样技术[18].因此, 开销模型可以估计需要执行多少顺序或随机I/O.估计的精确程度依赖于数据分布, 但是由于空间限制, 不能建立过多直方图或者保存过多样本.因此, 开销估计常常是不准确的, 导致优化器产生了性能极差的查询计划.另一方面, 查询计划的搜索空间可能会过大, 对于n个表连接的查询来说, 有(2n-2)!/(n-1)!种连接计划.查询优化器不可能遍历所有的计划.
数据库中的负载管理离不开准确的开销模型, 而查询优化器中开销模型无法满足需求, 第1.1节详细阐述了原因.因此, 本文提出了基于神经网络的开销模型, 功能类似于查询优化器的开销模型, 用于负载管理场景, 模型框架如图 5所示:首先, 从数据库历史查询记录中抽取出查询计划和运行时间构成原始数据, 按照查询计划的运行时间长短将原始数据分类, 使得数据集中每类包含的查询计划的数量相等; 其次, 将查询计划编码成操作向量, 获得训练集.最后训练并得到模型.针对待测的查询计划, 编码得到其对应的操作向量, 再输入神经网络模型中, 输出与操作序列对应的运行时间序列, 完成数据库查询时间的预测.
|
Fig. 5 General idea of the model 图 5 模型框架 |
一个查询语句对应多个查询计划.查询计划的结构是一棵多叉树, 直观上看并不是序列数据.但显然:查询计划树的子树开销会影响父节点的开销; 同一个节点的子树之间相互独立, 互不影响.因此, 本文采用后序编码来保留这种结构信息, 将查询计划树转换成序列.序列前面的数据会影响后面的数据, 抽象来说, 就是一个时间序列.但序列中有些数据前后独立, 即:同一个节点的子树在序列中虽然有先后关系, 但彼此之间却是独立的.这与机器翻译问题非常相似, 因此, 本文模型遵循了神经网络机器翻译的思路[19-21].
后序编码后的查询计划作为神经网络的输入.网络逐个地学习查询计划中每个操作的开销, 那么查询计划的第1个操作开销将会帮助网络决定第2个操作的开销预测结果.最后, 网络输出该查询计划的开销序列.
3 模型建立 3.1 特征提取应用深度学习算法需要特征向量与预测标签.预测标签, 即模型的输出, 有两种设计方案.
● 第1个方案是试图解决回归问题, 也就是直接预测时间.由于不同查询计划可能导致大量不同的开销, 不利于模型的训练.本文的相关实验验证了以上的观点.再次分析问题的应用场景, 其实预测时间本质目的是区分短时间查询和长时间查询, 即并不关心非常精确的时间, 重要的是确定查询开销处于哪个数量级;
● 第2个方案是解决分类问题, 将时间范围划分成c个区间, 预测开销落在那个区间.实验结果表明, 第2个设计方案比第1种设计方案更合适.
注意:区间的划分并不是数值均匀的, 而是保持每个区间内的数据量均匀.假设有m条数据和c个区间, 那么每个区间内的数据量应该是m/c条.可以将所有数据排序, 根据每个区间内的数据量来划分区间范围.若数据量较大, 可采用抽样方法来确定区间范围.
相比预测标签, 定义特征向量就比较复杂.图 6是下面查询语句的一个查询计划树.
|
Fig. 6 A typical query plan 图 6 查询计划树 |
SELECT T1.k
FROM T1, T2, T3
WHERE T1.k=T2.fk AND T1.fk=T3.k AND T1.k < 100
GROUP BY T1.k
其中, T1, T2, T3分别表示了数据库中的源表, 即查询计划的各个操作可能用到的源表; T1.k表示T1表的主键, 同理, T3.k表示T3表的主键; T1.fk表示了T1表的外键, 同理, T2.fk表示了T2表的外键.
查询优化器产生一个查询计划只要毫秒到秒级别的时间, 因此, 这些信息不难获取.查询计划本质上是一棵以各种类型的操作为节点的多叉树, 每个节点上都有操作的相关信息.例如, 图 6中左侧Hash Join节点代表的是连接类型下的一种操作, 其连接的条件是T1.k=T2.fk.
在将查询计划编码成LSTM能接收的格式时, 为了保留查询计划树的结构信息, 本文采用后序编码, 将其编码成一个操作序列Sop={op0, op1, …, opm-1}, opi是操作序列Sop中第i个操作, m表示查询计划中操作的个数.图 6中查询计划树的后续遍历可以表示成:
| $ {S_{op}} = \{ {T_2}, \sigma {T_1}.k < 100, Hash, \bar T = {T_1} \triangleright \triangleleft {T_2}, {T_3}, Materialize, \bar T \triangleright \triangleleft {T_3}, Sort, Group\} $ |
σ表示选择操作, ▷◁表示表的连接操作,
对于一个查询计划中的各个操作, 经过后序遍历生成操作序列, 遍历生成操作序列时, 对于查询计划中的各个操作提取关键特征, 将每个操作转换成向量v.v包含5个部分:
(1) n0代表操作的类型, 例如Hash Join, Nested Loop等.PostgreSQL中共有34种操作类型, 表 1给出了操作清单.因此, n0是一个34位的向量, 该操作类型对应的位设置为1, 其他位设置为0;
|
Table 1 Operation list 表 1 操作清单 |
(2) n1代表操作在数据库中对应的源表.假设数据库有k个表, 那n1就有k位.计划树的叶子节点带有源表信息.例如, 图 6中左边叶子节点的源表是T2, 因此, 该叶子节点操作的n1中T2对应的位设置为1, 其他位设置为0.子节点的源表信息会传递给父节点.例如, 图 6中Hash Join操作的源表是T1和T2, 分别来自它的两棵子树;
(3) n2代表操作在数据库中对应源表中涉及的列.假设数据库中所有表共m列, 那n2就有m位.例如, 图 6中Hash Join涉及表T1中主键和表T2中的外键, 那么这两列对应的位就会被设置为1, 其余的位设置为0;
(4) n3代表操作对应结果行的平均宽度, 即每行所占字节数.假设操作的输出仅包含一列且该列的类型是integer, 那么结果行的平均宽度是4字节.将宽度的范围划分成c个区间, 宽度落在哪个区间内, 该区间对应的位就设置为1, 其余位设置为0;
(5) n4代表操作对数据的选择率, 即结果数据量占总量的百分比.这部分考虑了数据分布对于开销的影响.由于TPC-H的数据集分布是均匀的, 因此本文实验部分不包含n4, 但实际数据库中的数据分布很有可能是不均匀的.可以使用等宽直方图或等高直方图来计算选择率.等高直方图更加准确, 因为频度较高的属性值, 所处的桶范围就小, 因此更为近似; 相反, 频度较低的属性值, 等高直方图的近似相对不准确, 但对于估算结果来说, 频度高的属性值更重要.多列条件筛选时, 选择率可以是多列选择率的乘积, 也可以收集多列统计信息.前者的实现方式更为简单, 后者估算结果更为准确, 但需要维护统计信息.
向量v的前3个部分描述了查询的结构, 后2个部分跟踪了查询过程中包含的数据规模.因此, 当数据库系统中数据量动态变化时, 模型的输入的一部分也会产生变化, 因此模型的输出也会受到影响.同时, 用户在此期间产生的历史查询会作为新的训练集继续训练模型, 因而模型会随着数据库数据量的变化而变化.现在用一个向量来表示一个特定的操作, 即Sv={v0, v1, …, vm-1}表示一个特定的计划, vi是后序编码中第i个操作.在这节的其余部分里, 将展示如何使用Sv来训练LSTM模型.
3.2 LSTM模型LSTM有3个门:输入门、遗忘门和输出门, 它可以自适应地记住过去的状态来加强它的学习过程.本文应用了LSTM的一个变种——peephole connections[14], 如图 7所示.
|
Fig. 7 LSTM memory block with peephole connections from the CEC to the gates[14] 图 7 使用peephole connections的LSTM结构[14] |
peephole连接起了门与CEC(constant error carousel), 可以理解为3个门的输入信息增加了Cell的状态.这个变种可以在没有任何短训练样本的帮助下学习间隔50个或49个时间步的序列之间的细微差别, 比普通LSTM学习长序列的能力要强[12].而查询计划形成的序列也很长, 因而选用了这种网络.
peephole connections有多个实现的版本, 只在细节上有所差异.本文所采用的peephole connections是DL4J中的版本, 见公式(4)~公式(8).
定义I是输入的个数, K是输出的个数, H是隐藏层中细胞的个数, C是块(block)中细胞的个数.wij是i单元~j单元之间的权重.在t时间, j单元的值经过激励函数输出的值定义为
公式(4)、公式(5)、公式(7)表示了3个门前向传播的计算方式, 公式(6)、公式(8)表示cell的状态和cell的输出.关于反向传播的公式见文献[23].
| $ y_\iota ^t = f\left( {\sum\limits_{i = 1}^I {{w_{i\iota }}x_i^t + \sum\limits_{h = 1}^H {{w_{h\iota }}y_h^{t - 1} + \sum\limits_{c = 1}^C {{w_{c\iota }}s_c^{t - 1}} } } {\rm{ + }}{b_\iota }} \right) $ | (4) |
| $ y_\phi ^t = f\left( {\sum\limits_{i = 1}^I {{w_{i\phi }}x_i^t + \sum\limits_{h = 1}^H {{w_{h\phi }}y_h^{t - 1} + \sum\limits_{c = 1}^C {{w_{c\phi }}s_c^{t - 1}} } } {\rm{ + }}{b_\phi }} \right) $ | (5) |
| $ s_c^t = y_\phi ^ts_c^{t - 1} + y_\iota ^tg\left( {\sum\limits_{i = 1}^I {{w_{ic}}x_i^t + \sum\limits_{h = 1}^H {{w_{hc}}y_h^{t - 1} + {b_c}} } } \right) $ | (6) |
| $ y_\omega ^t = f\left( {\sum\limits_{i = 1}^I {{w_{i\omega }}x_i^t + \sum\limits_{h = 1}^H {{w_{h\omega }}y_h^{t - 1} + \sum\limits_{c = 1}^C {{w_{c\omega }}s_c^t} } } {\rm{ + }}{b_\omega }} \right) $ | (7) |
| $ y_c^t = y_\omega ^t{g_{out}}(s_c^t) $ | (8) |
由公式(4)~公式(8)可推导出LSTM隐藏层的参数个数为
| $ Nu{m_{parameters}} = [(I + H + C + 1) \times 3 + I + H + 1)] \times H $ | (9) |
使用第3.1节介绍的Sv作为模型的输入.模型试图去预测查询计划每一步的运行开销, 再与真实的结果比较计算出误差来调节网络.
St代表子计划在时间t已经被执行了.对于计划Sv={v0, v1, …, vm-1}来说, St={v0, v1, …, vt-1}(t < m)是它的一个子计划.将时间范围划分为n个区间, 记为{c0, c1, …, cn-1}.
定义St的开销为δ(St), δ(St)落入某区间ci的概率表示为
| $ C({S_t}) = MAX({P_{{S_t}, {c_i}}})(i = 0, 1, ..., n - 1) $ | (10) |
例1:对于图 6中展示的查询计划, 在预测了它的子计划S2={T2, σT1.k < 100, Hash}后, 有了扫描表T2和选择T1特定元组的开销预测.假设S2的开销是δ(S2).
接下来, 模型要预测子计划
网络设计要确定层数、每个隐藏层的节点数和激活函数、输出层的激活函数和代价函数, 以及一些重要参数, 如优化算法、初始学习率等.本文设计的网络结构如图 8所示:第1层是输入层, 中间两层是隐藏层, 最后一层是输出层.隐藏层所用的激活函数是sigmoid, 输出层的激活函数是softmax.两个隐藏层都是100节点.输入层的节点数取决于特征向量的长度, 见表 3、表 4.
|
Fig. 8 Network structure 图 8 网络结构 |
优化算法采用了随机梯度下降方法, 初始学习率设为0.05.
代价函数是交叉熵代价函数, 见公式(11)(损失越小, 表示预测效果越好.训练过程就是不断减小损失的
过程):
| $ J = - \sum\limits_{k = 1}^n {\sum\limits_{i = 1}^c {{y_{ki}}\log ({{\hat y}_{ki}})} } $ | (11) |
公式(11)中, 样本数量为n, 类别数量是c, yki是样本k属于类别i的概率,
为了评估模型的性能, 本文使用DL4J实现了基于LSTM的开销预测模型.训练数据和测试数据来源于TPC-H决策支持基准[22], 采用了PostgreSQL数据库.
本文做了两组实验:一组使用查询优化器产生的cost进行训练, 一组收集查询真实的运行时间作为训练集.分别称为模拟数据和真实数据.
原型系统采用Java语言开发, 系统环境为Ubuntu 14.04.2 LTS, Linux 3.13.0-99-generic (x86_64), 2x Intel(R) Xeon(R) CPU E5-2650 v2@2.60GHz, 内存96GB, 硬盘SEAGATE ST9300603SS SAS 10K, 300GB.
4.2 训练集收集大部分DBMS(如PostgreSQL和SQLServer)都支持explain命令, 可以得到建议的执行计划和查询优化器估计的I/O开销.为了使用实际运行数据作为训练数据集, 可以使用explain analyze命令去运行和收集计划中每一个操作真实的运行时间.
|
|
Table 2 The experimental data range 表 2 实验数据范围 |
大部分由TPC-H模板产生的查询语句执行开销较小, 并不满足均匀覆盖短时间查询和长时间查询的条件.为了产生长时间查询, 实验根据数据库中的8张表自定义了查询模板.通过改变数据库配置和表的连接顺序, 利用模板生成了数万条的查询计划.更改数据库配置, 是为了引导查询优化器产生不同的查询计划.实验中随机更改PostgreSQL提供的28项设置, 以引导查询优化器同时产生“好”和“不好”的计划.
特别注意的是:在收集每一条查询计划的运行时间时, 都需要在执行该条计划前清理缓存, 以确保数据的准确性.在Linux上, 可以通过关闭PostgreSQL数据库, 使用drop_caches清理系统层面的缓存, 再重启PostgreSQL的方法清理缓存.另外, 训练集在训练前要随机打乱, 避免训练数据之间的相关性很大影响训练结果.
4.3 模型评估本节介绍了两组实验中对模型的评估.表 3、表 4总结描述了两次实验中网络各层的详细信息.表 3中输入大小为120, 代表第3.1节中被转换成向量v的操作长度.实验中的向量v有4个部分:n0有34位, 代表了PostgreSQL数据库中34种操作类型; n1有8位, 代表了TPC-H中的8张表; n2有61位, 代表了表中的所有列; n3有17位, 表示结果行的平均宽度范围被划分成17个区间.4部分总共120位.
|
|
Table 3 Network layer information of the first experiment 表 3 实验1网络层级信息 |
|
|
Table 4 Network layer information of the second experiment 表 4 实验2网络层级信息 |
实验使用80%的数据作为训练集, 20%的数据作为测试集.表 5中第1组实验使用了12万条查询计划进行训练, 3万条独立的查询计划测试; 第2组实验采用了真实运行时间数据, 8 000条查询计划用于训练, 2 000条独立的查询计划用于测试.
|
|
Table 5 Model evaluation results 表 5 模型评估结果 |
公式(12)用于评估模型预测的正确率, Numtotal指的是预测的总次数, Numhit指预测开销所在的区间与真实开销所在区间一致的预测次数.Accuracy并不代表查询时间值的差异, 而是代表了时间开销间隔类别的差异.
| $ Accuracy = Nu{m_{hit}}/Nu{m_{total}} $ | (12) |
实验结果见表 5:两组实验的正确率都高于71%, 模拟数据训练下模型的正确率高于78%.分析预测结果发现:不正确的预测结果误差范围较小, 对实际应用场景的执行影响很小.模型的训练时间代价见表 6, 在本文系统环境下, 实验2模型的训练代价仅为1小时, 达到了71%的正确率.
|
|
Table 6 Model training time cost 表 6 模型训练时间代价 |
实验中模型终止迭代评分为3.78.终止迭代次数见表 6中, 各为2 000次.
图 9和图 10是两次实验对于每个子计划预测的命中率, 第1类的时间区间是(-∞, 0], 负数的时间实际是没有意义的, 因此这个区间只包含0.为了让每一个计划向量的长度相同, 采用最大字长, 不足最大长度的计划向量在前面补0, 这样的做法使得训练集和测试集都存在一定数量开销为0的操作.例如实验2中, 2 000条计划有2000×6个操作, 其中, 开销为0的个数为5 005, 命中的数量是4 977, 模型预测的准确率是99.441%, 但由于其数量之大影响了图 10中其他数据的显示, 因此图中没有给出.图 9同理.
|
Fig. 9 The hit condition of the first experiment 图 9 实验1的命中情况 |
|
Fig. 10 The hit condition of the second experiment 图 10 实验2的命中情况 |
实验还比较了查询优化器与本文模型的预测速度.第2组实验中, 对于2 000条测试数据, 查询优化器用时846ms, 本文模型用时6 372ms.本文模型的应用场景是负载管理, 与查询优化器的代价模型有所不同, 本文第2节给出了详细的说明.因此两者的速度要求并不相同.实验中本文模型用时是查询优化器的8倍.但随着深度学习算法的优化, 和硬件的提升, 未来模型时间性能的提升是必然的.
5 结束语本文提出一种基于循环神经网络的查询开销预测模型.给出一个特定的查询计划, 在计划实际执行前, 模型就能够产生该查询计划实际运行时间区间的预测, 不管是短时间查询还是长时间查询, 模型的预测结果都较为准确.特别地, 本文设计了一种编码方法, 能够将具有复杂结构的查询计划转换成特征向量.通过实验验证, 模型的正确率高于71%, 说明了本文模型的可行性.后续工作将继续研究模型在PostgreSQL以外的关系型数据库上的性能表现以及如何将模型扩展应用到关系型数据库以外的数据库上, 例如MongoDB、HBase等.
| [1] |
Wu W, Chi Y, Zhu S, Tatemura J, Hacigümüs H, Naughton JF. Predicting query execution time: Are optimizer cost models really unusable? In: Proc. of the 2013 IEEE 29th Int'l Conf. on Data Engineering (ICDE). New York: IEEE, 2013. 1081-1092. [doi: 10.1109/ICDE.2013.6544899] |
| [2] |
Tozer S, Brecht T, Aboulnaga A. Q-Cop: Avoiding bad query mixes to minimize client timeouts under heavy loads. In: Proc. of the 2010 IEEE 26th Int'l Conf. on Data Engineering (ICDE). New York: IEEE, 2010. 397-408. [doi: 10.1109/ICDE.2010.5447850] |
| [3] |
Xiong P, Chi Y, Zhu S, Tatemura J, Pu C, HacigümüŞ H. ActiveSLA: A profit-oriented admission control framework for databaseas-a-service providers. In: Proc. of the 2nd ACM Symp. on Cloud Computing. New York: ACM Press, 2011. 15. [doi: 10.1145/2038916.2038931] |
| [4] |
Mishra C, Koudas N. The design of a query monitoring system. ACM Trans. on Database Systems (TODS), 2009, 34(1): 1–51.
[doi:10.1145/1508857.1508858] |
| [5] |
Wasserman TJ, Martin P, Skillicorn DB, Rizvi H. Developing a characterization of business intelligence workloads for sizing new database systems. In: Proc. of the 7th ACM Int'l Workshop on Data Warehousing and OLAP. New York: ACM Press, 2004. 7-13. [doi: 10.1145/1031763.1031766] |
| [6] |
Ganapathi A, Kuno H, Dayal U, Wiener JL, Fox A, Jordan M, Patterson D. Predicting multiple metrics for queries: Better decisions enabled by machine learning. In: Proc. of the 2009 IEEE Int'l Conf. on Data Engineering (ICDE 2009). New York: IEEE, 2009. 592-603. [doi: 10.1109/ICDE.2009.130] |
| [7] |
Elnaffar S, Martin P, Horman R. Automatically classifying database workloads. In: Proc. of the 11th Int'l Conf. on Information and Knowledge Management (CIKM 2002). New York: ACM Press, 2002. 622-624. [doi: 10.1145/584792.584898] |
| [8] |
Akdere M, Çetintemel U, Riondato M, Upfal E, Zdonik SB. Learning-Based query performance modeling and prediction. In: Proc. of the 2012 IEEE 28th Int'l Conf. on Data Engineering. New York: IEEE, 2012. 390-401. [doi: 10.1109/ICDE.2012.64] |
| [9] |
Ahmad M, Aboulnaga A, Babu S, Munagala K. Interaction-Aware scheduling of report-generation workloads. The VLDB Journal -The Int'l Journal on Very Large Data Bases, 2011, 20(4): 589–615.
[doi:10.1007/s00778-011-0217-y] |
| [10] |
Duggan J, Cetintemel U, Papaemmanouil O, Upfal E. Performance prediction for concurrent database workloads. In: Proc. of the 2011 ACM SIGMOD Int'l Conf. on Management of Data. New York: ACM Press, 2011. 337-348. [doi: 10.1145/1989323.1989359] |
| [11] |
Wang W, Zhang M, Chen G, Jagadish HV, Ooi BC, Tan KL. Database meets deep learning:Challenges and opportunities. ACM SIGMOD Record, 2016, 45(2): 17–22.
[doi:10.1145/3003665.3003669] |
| [12] |
Pavlo A, Angulo G, Arulraj J, Lin H, Lin J, Ma L, Santurkar S. Self-Driving database management systems. In: Proc. of the 8th Biennial Conf. on Innovative Data Systems Research (CIDR). 2017. |
| [13] |
Gers FA, Schmidhuber J, Cummins F. Learning to forget:Continual prediction with LSTM. Neural Computation, 2000, 12(10): 2451–2471.
[doi:10.1162/089976600300015015] |
| [14] |
Gers FA, Schraudolph NN, Schmidhuber J. Learning precise timing with LSTM recurrent networks. Journal of Machine Learning Research, 2003, 3(1): 115–143.
[doi:10.1162/153244303768966139] |
| [15] |
Ioannidis YE. Query optimization. ACM Computing Surveys (CSUR), 1996, 28(1): 121–123.
[doi:10.1145/234313.234367] |
| [16] |
Scott DW. On optimal and data-based histograms. Biometrika, 1979, 66(3): 605–610.
[doi:10.1093/biomet/66.3.605] |
| [17] |
Ioannidis YE, Poosala V. Balancing histogram optimality and practicality for query result size estimation. ACM SIGMOD Record, 1995, 24(2): 233–244.
[doi:10.1145/568271.223841] |
| [18] |
Haas PJ, Naughton JF, Seshadri S, Stokes L. Sampling-Based estimation of the number of distinct values of an attribute. In: Carey M, ed. Proc. of the 21th Int'l Conf. on Very Large Data Bases (VLDB'95). New York: ACM Press, 1995. 311-322. [doi: 10.1145/223784.223841] |
| [19] |
Bahdanau D, Cho K, Bengio Y. Neural machine translation by jointly learning to align and translate. arXiv preprint arXiv: 1409. 0473, 2014. |
| [20] |
Cho K, Van Merriënboer B, Gulcehre C, Bahdanau D, Bougares F, Schwenk H, Bengio Y. Learning phrase representations using RNN encoder-decoder for statistical machine translation. arXiv preprint arXiv: 1406. 1078, 2014. |
| [21] |
Sutskever I, Vinyals O, Le QV. Sequence to sequence learning with neural networks. In: Ghahramani Z, ed. Proc. of the 27th Int'l Conf. on Neural Information Processing Systems (NIPS 2014). Massachusetts: MIT Press Cambridge, 2014. 3104-3112. |
| [22] |
TPC-H benchmarks. http://www.tpc.org |
| [23] |
Graves A, Schmidhuber J. Framewise phoneme classification with bidirectional LSTM and other neural network architectures. Neural Networks, 2005, 18(5): 602–610.
http://www.cs.toronto.edu/~graves/nn_2005.pdf |