【论文阅读 SIGMOD18】Query-based Workload Forecasting for Self-Driving

Query-based Workload Forecasting for Self-Driving Database Management Systems

• My Summary

ABSTRACT

Autonomous DBMS的第一步就是能够建模并预测工作负载，以前的预测技术对查询的资源利用率进行建模。然而，当数据库的物理设计和硬件资源发生变化时，这些指标会发生变化，从而使以前的预测模型无用。

提出了QueryBot 5000的具有鲁棒性的预测框架，它允许DBMS根据历史数据预测未来查询的预期到达率。为了更好地支持高度动态的环境，本文的方法使用工作负载中查询的逻辑组合，而不是用于查询执行的物理资源的数量。提供了短期和长期的预测。本文还提出了一种基于聚类的技术来减少要维护的预测模型的总数。在三个数据库进行测试，在MySQL和PG的external controller上实现了本文的模型进行了测试（选择索引）。

1 INTRODUCTION

两个原因关于为什么要再次努力开发self-driving dbms：

• 现代存储和计算硬件的改进能力使DBMS能够收集足够的关于其行为的数据，然后使用它来训练比以前可能更复杂的机器学习(ML)模型。
• 第二个原因是 ML 的最新进展，尤其是在深度神经网络和强化学习中，将允许 DBMS 随着时间的推移不断改进其模型，因为它更多地了解应用程序的工作负载。

要完全autonomous，一个是可以预测未来负载变化做出相应的action，另外一个是能够在低峰期间自动进行action，不然高峰就出现争用了。

以前的工作已经研究了不同上下文中的数据库工作负载建模。

• 一种方法是对系统资源需求进行建模，而不是直接表示工作负载本身
• 其他方法通过回答有关 OLTP 工作负载变化的“what-if”问题来模拟 DBMS 的性能。将工作负载建模为具有固定比率的不同类型事务的混合。（足够多的分类，然后如果作出修改，性能会怎么改变来模拟最佳配置）
• 也有研究使用隐马尔可夫模型或回归来预测工作负载如何随时间移动
• 早期的工作还使用更正式的方法对数据库工作负载进行建模，这些方法具有预定义的事务类型和到达率

所有这些方法都存在缺陷，这使得它们不适合自治系统。

• 有些使用有损压缩方案，该方案只维护高级统计信息，如平均查询延迟和资源利用率。
• 其他工作假设只有静态工作负载，或者当工作负载发生变化时，它们只生成新的模型，从而无法捕获查询的数量和工作负载趋势如何随时间变化。
• 一些模型是硬件和/或数据库设计相关的，这意味着DBMS必须在配置发生变化时重新训练它们。

本文提出了一个简洁的self-driving的工作负载的预测方法。根据查询到达率来对查询进行建模，无缝处理不同负载模式和切换，构建模型来预测查询聚类的未来到达模式(类别)，这样的预测是必要的，使自主DBMS的planner模块能够识别哪些优化actions可以提高系统的性能，并主动应用它们。与以前的预测方法相比，本文的方法的主要优点是用来训练的模型的数据独立于硬件和数据库设计。因此，如果DBMS的硬件或配置设置发生变化，则不需要重建模型。

为了评估预测模型，将该框架集成到 MySQL [1] 和 PostgreSQL [5] 中，并测量其建模和优化三个数据库应用程序的能力。结果表明，本文的框架可以有效地预测预期的未来工作负载，而精度损失很小。他们还展示了如何使用这个框架来提高系统的性能。

2 BACKGROUND

Autonomous DBMS中的工作负载预测的目标是使系统能够预测未来应用程序的工作量。因为现实世界应用程序的工作负载永远不会是静态的，系统可以选择优化以基于此预测准备。

负载预测主要是两个挑战，一个是应用程序的查询可能具有非常不同的到达率。因此，一个有效的预测模型必须能够识别和描述这些到达率模式中的每一个。第二个是workload的查询的组合和数量会随着时间进行变化，如果工作负载和过去偏差很大，就得重新弄一个model。

下面是调研3个实际数据库，workload的共同特征和模式，讨论有效的预测模型要克服的challenge。

2.1 Sample Workloads

我们现在对从真实世界的数据库application·收集的三个样本工作负载跟踪进行简要描述：

• Admissions：大学研究生招生网站大学研究生招生网站学生将申请材料提交给不同院系的项目。院系在截止日期后审核申请并做出决定。是Growth and Spikes
• BusTracker：一个实时跟踪公共交通公交系统的手机应用程序。它定期从公交系统获取公交位置信息，然后帮助用户找到附近的公交站点并获取路线信息。所以在一天之内是有周期性的Cycles
• MOOC：为想要学习或教学的人提供在线课程的web应用程序[3]。教师可以上传他们的课程材料，学生可以查看课程内容并提交他们的课程作业。有new release之后，类似于增量式，Workload Evolution。

2.2 Workload Patterns

三种常见工作负载模式，前两种模式是数据库应用程序中的查询可能具有的不同到达率的示例。第三种模式展示了工作负载中查询的组合如何随时间变化。

• Cycles：一些应用程序在一天中的特定时间段执行的查询比在其他时间段执行的查询更多
• Growth and Spikes:另一个常见的工作负载模式是查询量随着时间的推移而增加。这种模式在具有越来越受欢迎的应用程序的初创企业和具有特定到期日期的事件的应用程序中很常见。招生申请有这种模式。图1b显示了在应用程序截止日期前一周内每分钟执行的查询数。查询的到达率随着日期的临近而增加:它在一周开始时增长缓慢，但在截止日期前的最后两天迅速增加。
• Workload Evolution:数据库工作负载随着时间的推移而演变。位于不同时区的新用户开始使用某个应用程序、新的应用程序特性之后增长。

2.3 Discussion

要使预测框架在实际的DBMS部署中工作，必须解决三个挑战。

• 第一个，最重要的：为了利用工作负载中的各种到达率模式进行优化规划，需要良好的到达率预测模型。不仅不同的工作负载有不同的模式，而且单个工作负载也可以有不同的查询子组模式。因此，一个有效的预测模型必须能够识别和描述在同一工作量内同时发生的模式。
• 第二个：由于应用程序每天执行数百万个查询，因此为工作负载中的每个查询构建预测模型是不可行的。这意味着框架必须在不严重降低预测准确性的前提下，降低其分析工作负载的复杂性。
• 第三个，framework必须处理工作负载模式以及查询混合的变化。所有这些都必须在没有任何人为干预的情况下完成。也就是说，框架不能要求DBA调优其内部参数或提供有关应用程序工作负载是什么以及何时发生变化的提示。

3 QUERYBOT 5000 OVERVIEW

QueryBot 5000 (QB5000)是一个工作负载预测框架，既可以作为外部控制器运行，也可以作为嵌入式模块运行。

目标DBMS连接到该framework，然后转发query，当QB5000接收到这些查询时，它将它们存储在其内部数据库中。然后，它训练模型来预测哪些类型的查询，以及DBMS在未来预计执行多少查询。然后，self-driving DBMS可以使用这些信息来部署优化，以提高其目标目标(例如，延迟，吞吐量).

查询转发到QB5000的时候，先进入pre-processor和clusterer，将查询映射到之前见过的查询里面去，这使QB5000能够在不牺牲准确性的情况下减少跟踪SQL查询的计算和存储开销。preprocessor通过从SQL字符串中提取常量参数，将原始查询转换为通用模板，记录每个模板的到达率历史。

为了进一步减少计算资源压力，QB5000然后根据其语义(例如，它访问的表)将模板映射到最相似的先前查询组。然后，Clusterer使用在线聚类技术进一步压缩工作负载，将具有相似到达率模式的模板分组在一起。它能够处理不断变化的工作负载，新查询出现，旧查询消失。

在最后阶段，Forecaster选择最大的模板集群(即查询量最高的聚类)，然后根据每个聚簇中templates的平均到达率训练预测模型。模型预测了每个template cluster将在未来执行多少query 一小时后或者一天后，DBMS将根据它对应用程序未来的期望来决定如何优化自己，而不是根据过去发生的情况。QB5000还会随着工作负载的变化自动调整这些集群。每次template的cluster分配发生变化时，QB5000都会重新训练它的模型。

当DBMS运行时，Pre-Processor总是提取新的查询，并在后台实时更新每个template的历史到达率。clusterer和forecaster定期更新聚类分配和预测模型。当QB5000预测未来的预期工作负载时，它使用最新的数据作为模型的输入。

4 PRE-PROCESSOR

对于OLTP工作负载，应用程序调用具有不同输入参数的相同查询。对于OLAP工作负载，用户经常与仪表板或报告工具进行交互，这些工具提供了使用不同谓词和输入参数构造查询的接口。

这类类似的查询以相同的频率执行，并且通常在系统中具有相同的资源利用率。因此，可以把具有相同template的查询，减少了需要跟踪的查询的数量，因为它只需要维护每个模板的到达率信息，而不是每个单独的查询。QB5000的PRE-PROCESSOR是如何收集和组合它从DBMS接收到的查询呢？

PreProcesssor主要是两步：

• 首先从查询的SQL字符串中提取所有常量，并用值占位符替换它们。常量主要包括
  • WHERE子句谓词中的值。
  • UPDATE语句中的SET字段。I
  • NSERT语句中的VALUES字段。对于批处理insert, QB5000还跟踪元组的数量。
• PreProcessor执行额外的格式化来规范空格、大小写和括号/括号的位置，output一个query template，

QB5000跟踪在给定时间间隔内到达每个模板的查询数量，然后在每个时间间隔结束时将最终计数存储到internal catalog table中。系统将过期的到达率记录以更大的间隔进行汇总，以节省存储空间。

QB5000为每个模板维护一组查询的原始参数样例。我们使用reservoir抽样从包含大量或未知数量项目的列表中选择固定数量的低方差items，方便autonomous DBMS的planning 模块在cost/benefit的时候会使用。Preprocessor执行最后一步，聚合具有等效语义特征的模板，以进一步减少QB5000跟踪的唯一模板的数量。评估语义等价性是一项非常重要的工作，关于这一主题已经有了广泛的研究。QB5000使用启发式方法来近似模板的等价性。如果两个模板访问相同的表、使用相同的谓词并返回相同的投影，则认为它们是等价的。人们可以使用更正式的方法来充分利用语义等价。

启发式足够了，在不降低准确性的情况下提供了合理的性能。将研究更复杂的方法作为未来的工作。

表2显示，对于示例工作负载，QB5000的Pre-Processor能够将查询数量从数百万个减少到最多数千个模板。

5 CLUSTERER

训练一个模型可能需要三分钟以上的时间，所以对每个template都构建模型是不行的，还得聚类。Clusterer将具有相似模式的模板的历史到达率聚合，这个过程通过把template映射到高维向量然后计算相似度实现。为了支持在动态环境（工作负载、DBMS物理设计、配置都会发生改变）对负载进行建模，聚类算法必须使用不依赖于数据库当前状态的特征生成稳定的映射。

QB5000聚类过程主要有三个行文阶段，第一是从每个template提取特征，第二是描述如何确定她属于哪个cluster，第三是介绍QB5000的聚类算法，该算法支持随着应用程序工作负载的发展而进行增量更新，以及框架如何快速确定是否重建其集群。

5.1 Clustering Features

从template提取三种特征，physical、logical、arrival rate history。

• 物理特性是DBMS在执行查询时使用的资源量和其他运行时指标，例如读/写元组的数量或查询延迟。使用物理特性选择查询计划、性能建模、workload压缩，好处是物理特性提供了单个查询细粒度信息，但是它们依赖于DBMS的配置和硬件、数据库的内容以及同时运行的其他查询。如果其中任何一个发生了变化，那么之前收集的特征都是无用的，框架必须重新构建它的模型。这种不稳定性使得DBMS的规划模块很难了解它的决策是在帮助还是在损害性能。
• template logical features，比如它访问的表/列和查询语法树的属性。逻辑特性不依赖于DBMS的配置，也不依赖于工作负载的特征(例如，哪个查询比其他查询执行得更频繁)，但是信息有限可能生成不那么足以分别的聚簇，预测模型很差。
• 历史到达率：聚簇是簇内模板的平均到达率，为什么呢？尽管每个模板在给定时间数量都不同，但是他们的循环模式是相同的，因为这几个查询可能被封装在同一个事务里面。由于同一聚簇中的模板表现出相似的到达率模式，系统可以为每个簇构建一个预测模型，以捕获它们的查询行为。

计算历史到达率的相似度：QB5000首先随机采样当前时间点之前的时间戳，QB5000取这些时间戳处的值子集，形成一个向量。两个特征之间的相似度定义为两个向量的余弦相似度。如果模板是新的，我们将其可用时间戳与其他模板向量中的相应子集进行比较。当前实现是使用10k 时间戳采样点来构建一个特征向量vector。

逻辑特征和到达率历史特征表达了查询的不同特征。基于到达率特性的聚类可以为实际应用程序生成更好的模型，因为它们捕获了查询如何影响系统性能。。尽管使用模板的到达率可以避免在DBMS更改时重新构建聚类，缺点是容易受到工作负载变化的影响。

5.2 On-line Clustering

聚类算法使用的是DBSCAN，是基于密度的聚类算法：给定某个空间中的一组点，它将有许多邻近点(称为core objects)的点分组在一起，并将单独位于低密度区域的点标记为离群点(即最近的邻居也很远的点)，与K-means不同，该算法不受小簇数量或簇密度的影响。

原始的DBSCAN算法通过检查对象与集群的任何core objects之间的最小距离来评估objects是否属于集群。调整成距离聚簇中心的距离来衡量，这是因为QB5000使用集群的中心来表示作为该集群成员的模板，并使用该中心构建预测模型。

DBSCAN算法的on-line extension在更新集群时有很高的开销，本文的online DBSCAN变体使用阈值ρ(0≤ρ≤1)来决定模板的到达率必须有多相似才能属于同一簇。ρ值越高，聚类内模板的到达率越相似，建模结果越准确。但是，如果生成的集群数量更多，计算开销也会更高。在附录a中对该值的设置进行了敏感性分析。

聚类过程三个步骤

• Step 1：对new template，检查历史到达率是否有相似度得分大于ρ的，如果有就分配给相似度最大的簇。使用kd-tree使得QB5000在高维空间中快速找到离模板最近的现有聚簇中心。QB5000将更新该集群的中心，该中心是该集群中所有模板到达率历史的算术平均值。如果没有现有的集群(这是第一个查询)，或者没有集群的中心离模板足够近，QB5000将创建一个新的集群，并将该模板作为其唯一的成员。
• Step 2：QB5000检查先前模板与其所属集群中心的相似性。如果模板的相似度不再大于ρ， QB5000将其从当前聚类中移除，然后重复步骤(1)以找到新的聚类位置。有时，将模板从一个集群移动到另一个集群会导致两个集群的中心发生变化，并递归地迫使这两个集群中的其他模板进行移动。QB5000将修改集群推迟到下一个更新周期。如果QB5000在很长一段时间内没有收到它的一个查询，就会删除模板。
• Step 3：QB5000计算集群中心之间的相似性，并合并得分大于ρ的两个集群。

除了定期执行这三个步骤外，QB5000还监视工作负载中的新模板。如果以前未见过的模板的百分比高于阈值，则会触发这些步骤以适应工作负载变化。正确设置这个阈值取决于目标DBMS的性能属性。

评价一下这个算法的话：1. 增量算法能够自适应调整来适应负载变化，不需要预热或者提前了解负载。2. 复杂度是O nlogn。3. step2终止了递归所以不一定收敛，但是不影响有效性。

5.3 Cluster Pruning

聚簇修剪（剪枝）。即使在使用聚簇技术减少QB5000需要建模的查询总数之后，由于到达率模式的长尾分布，实际应用程序仍然倾向于拥有大量簇。只有少数大型聚簇表现出主要的工作负载的模式，但有几个小型簇更像是干扰的噪声，QB5000不为它们构建模型。

6 FORECASTER

实验表明：对于我三个示例工作负载，五个最大的聚簇就覆盖了高达95%的查询量。最后一个阶段是构建预测模型来预测集群查询的到达率模式。这些模型允许DBMS的planning module估计应用程序将来将执行的查询数量，并选择适当的优化来满足SLA。下面描述QB5000如何构建和使用其预测模型，首先解释它的底层数据结构和训练方法，然后讨论了QB5000如何在多个模型上支持同一簇的不同预测范围和间隔。

6.1 Forecasting Models

六种模型，三个属性linear、memory：一个模型可以保留记忆允许它使用输入数据和从过去观察中“记住”的信息来预测未来。kernel：为非线性关系建模提供另一种方法

线性模型通常在近期(例如，一小时)做出预测方面表现更好，而非线性模型在更长的时间(例如，超过一天)做出预测方面表现更好。但是，确定在不同的时间范围和不同的工作负载上使用哪种类型的模型是非常重要的。

另一个方法是ENSEMBLE集成方法，该方法将多个模型组合在一起以进行平均预测。集成方法用于预测任务，将几种机器学习技术结合到一个预测模型中，以减少方差或偏差(例如，boosting)。

Linear Regression (LR):

在QB5000中，框架基于过去指定时间段内查询的到达率，对集群中查询的未来到达率进行回归。

Recurrent Neural Network (RNN):QB5000使用LSTM

平均LR和RNN模型的预测结果来应用集成方法，尽管集成方法获得了良好的平均预测精度，但我们发现它无法预测远离每次发生的工作负载中的周期性峰值，比如年度pattern。但是这种是DBMS常见的workload。所以用到下面的预测模型

Kernel Regression (KR):LR模型的非线性变体，它使用Nadaraya-Watson estimator，给定输入的预测是训练输出的加权平均值，其中权重随着给定输入与相应训练输入之间的距离而减小。

KR并不能很好地利用以前没有见过的数据进行推断，就平均预测精度而言，它的性能比ENSEMBLE差。但这是唯一一种能够应对每年招生人数激增的研究模式。

QB5000使用HYBIRD 预测模型，来自动确定何时使用来自ENSEMBLE的预测而不是来自KR的预测。由于KR擅长用少量观测值预测峰值，如果KR预测的workload量高于ENSEMBLE的超过了阈值γ使用KR的预测，在QB5000中，我们将γ设置为150%，考虑到测试的所有应用程序工作负载提供了最准确的预测。在附录C中提供了γ的敏感性分析。

6.2 Prediction Horizons & Intervals

预测模型的范围是根据其水平和间隔来定义的。

prediction horizon：指的是预测到多远的未来，prediction interval模型可以预测的时间粒度，例如，模型可以预测每隔一分钟或一小时将执行的查询数量。

QB5000将记录查询到达率的间隔设置为一分钟，这是QB5000能够提供给DBMS的最佳预测级别。为了预测峰值，使用一小时为间隔训练KR来预测。

7 EXPERIMENTAL ANALYSIS

1. 首先分析clusterer的压缩效果
2. 评估forecaster模型的准确性
3. 研究QB5000的计算时间和存储占用
4. 演示QB5000对self-drving DB的作用

7.1 Number of Clusters

第一个实验的目标是证明QB5000可以使用少量最高容量的聚簇对大部分数据库工作负载进行建模。

我们首先计算在整个工作负载执行过程中，每天最大聚簇的容量与总工作负载容量之间的平均比率。将给定聚簇的volume除以当天所有聚簇的总volume来计算的。下面图5结果显示，容量最大的聚簇覆盖了工作负载中的大部分查询

下面测试了 这个聚簇的稳定性，测试连续两天内聚簇发生改变的workload的占比，就是100天内有多少次发生了更改。对于Admissions和BusTracker来说，90%范围内，五个最大的聚簇中最多有一个变化。所以对workload的表征是有效且稳定的。

mooc工作负载比其他两个有更多的集群变化，因为随着教师创建和启动新课程，会出现新的查询。这表明QB5000的增量聚类算法可以捕捉应用程序工作负载随时间变化时的变化。

7.2 Prediction Accuracy Evaluation

QB5000对覆盖工作负载中总查询95%以上的最高容量聚簇进行建模。QB5000训练一个单一的预测模型，这个模型预测所有clusters的query arrival rates，这允许跨集群共享信息，从而提高预测的准确性，MSE越小，预测精度越高。

另一个考虑是，因为对于self-driving db来说预测模型一个特点就是对超参不敏感，所以实验中不管workload or horizons 都fix了超参。

对比了和其他模型的预测效果，包括ARMA、FNN、PSRNN。

1. 随着horizon的变化，精度下降。
2. 对于较短的视界，LR模型的表现与更复杂的RNN模型一样好，甚至更好。
3. 当视界大于或等于一天时，RNN优于LR。
4. ARMA的精度在不同视界上并不稳定。对于图7中的所有试验，它只有10%的时间达到最佳性能，但38%的时间性能最差。这是因为模型对它的超参数很敏感。ARMA的最佳超参数设置高度依赖于数据的统计特性，如平稳性和自相关结构。
5. FNN模型不能像rnn那样记住工作负载的状态。它们也缺乏LR的简单性来防止过拟合。
6. KR在19%的实验中表现最好，但在24%的实验中表现最差。该模型能够对非线性函数进行建模，但是当它在训练中没有看到与进行预测的输入接近的输入时，它很容易出错。
7. ENSEMBLE提供了最好的整体预测精度。在61%的实验中，它比所有的独立模型表现得更好，而且从来没有最差的表现。集成方法通常比其基础模型具有更低的方差，并且当其模型具有互补特征时产生更好的结果，LR和RNN具有不同的特性:LR在进行线性预测时仅使用有限数量的过去观测值，而RNN是非线性的，并保持状态以记忆来自所有先前观测值的信息。由于LR在短于一天的时间内具有与ENSEMBLE相当的性能，因此对于缺乏计算资源的DBMS来说，在这些短时间内使用LR也是可取的。
8. 尽管ENSEMBLE效果很好，但是它不能预测工作负载中不经常重复的峰值。HYBRID利用KR的预测修正了ENSEMBLE的结果，解决了这个问题。并且修正前后影响很小。

演示QB5000如何使用其HYBRID模型来预测每个集群的查询到达率。BusTracker的一小时的水平预测比一周的水平预测更准确。效果都很好。

7.3 Spike Prediction Evaluation

峰值预测。评估QB5000预测增长和峰值工作负载模式的能力。

上图结果显示，ENSEMBLE及其两个基本模型无法预测工作负载中的峰值。KR是唯一成功预测峰值的模型。这是因为它的预测是基于测试点和训练数据之间的距离，其中每个训练数据点的影响随其与测试点的距离呈指数递减。

7.4 Prediction Interval Evaluation

接下来，本文用不同的预测间隔来评估本文的ENSEMBLE预测模型的预测精度和训练时间。

10.a就是以不同的horizon，基本上随着horizon的边长，准确率变低，相同horizon里面随着间隔的变短准确率变高，较短的时间间隔对较长的视界尤其有利，因为未来和过去的到达率之间的关系更为复杂。但是较短的间隔增加了数据中的噪声，并且需要更多的间隔来包含相同的时间范围。

10.b显示了每个模型在不同间隔下的训练时间，在较长的时间间隔上训练模型所需的时间更少，这是符合预期的，

这里面一个trade-off是 设置间隔 和 self-driving DB自己的planning capabilities。

7.5 Computation & Storage Overhead

检车QB5000的计算和存储开销，记录它的四个组件花费的时间和空间量。

• Preprocessor：用于将查询模板化以及更新历史到达率的时间，以及每天生成的历史记录。
• Clusterer：根据最新的历史记录和结果数据的大小，每天更新一次聚类结果的时间。
• LR模型：训练一个LR模型的时间，以及学习到的权重的大小。
• KR Model:使用KR模型预测一个测试点的时间以及为模型维护的历史数据的大小。
• RNN模型:训练一个RNN模型的时间，以及PyTorch序列化的模型对象的大小，其中包含模型参数和网络结构。

表4显示了QB5000的所有组件都有合理的存储开销。结果还表明，训练rnn模型是计算成本最高的任务。

7.6 Automatic Index Selection

演示self-driving dbms如何使用QB5000的工作负载预测进行主动优化，从而提高系统性能。将QB5000与MySQL和PostgreSQL集成，以处理、集群和预测SQL工作负载，并为预测的工作负载自动构建index。PostgreSQL (BusTracker)和MySQL (Admissions)。

使用基于AutoAdmin引入的索引选择技术来生成要构建的索引集，AutoAdmin首先为样例工作负载中的每个查询选择最佳索引，以形成候选索引集。然后，它使用启发式搜索算法在候选索引中查找最佳有界索引子集。本文没有使用示例工作负载来生成候选索引，而是使用Clusterer生成的三个最大集群的预测工作负载。此评估的目的是演示QB5000动态建模和预测工作负载的能力，而不是索引选择算法的有效性。将自动索引选择(AUTO)的性能与静态索引选择方法进行比较（所以可能是效果不咋样），静态索引选择方法使用相同的索引选择算法，但将其应用于整个查询历史中的一个固定工作负载样本，该查询历史是在实验开始之前手动准备的(static)。

在实验期间AUTO总共构建20个索引，因此我们设置STATIC在实验开始前也构建20个索引。

垂直的绿色虚线表示DBMS何时构建新索引。

AUTO最初的性能比STATIC差，因为它还没有创建任何二级索引，但在实验结束时实现了28%的吞吐量和23%的延迟改善。这是因为AUTO利用QB5000的预测，选择了STATIC没有选择的四个索引。在pg里面，AUTO只选择一个与STATIC不同的索引，性能相似。

7.7 Logical vs. Arrival Rate History Feature

比较了QB5000的Clusterer使用的到达率历史特征与逻辑特征(AUTO-LOGICAL)的有效性。根据SQL字符串逻辑结构的相似性对模板进行分组。更具体地说，模板的逻辑特征向量由查询类型(例如，INSERT、SELECT、UPDATE或DELETE)、访问的表、引用的列、子句的数量(例如，JOIN、HAVING或GROUP BY)和聚合的数量(例如，SUM或AVG)组成。

结果显示AUTO- logical的dbms吞吐量比AUTO慢20%左右。

逻辑特性导致更糟糕的索引选择有两个原因：首先，SQL查询不足以确定两个模板是否会对系统产生类似的影响。第二个原因是同一逻辑特性聚簇中的模板可能有多个到达率模式，包括一次性查询等异常情况，这使得forecaster更难识别这些模式并难以根据聚簇中心预测趋势。

8 RELATED WORK

将以前在系统工作负载建模方面的工作分为几类：资源估计和自动伸缩resource estimation and auto-scaling、性能诊断和建模performance diagnosis and modeling、, shift detection、workload characterization for system design、metrics prediction for queries。

• 自动识别工作负载的变化以及资源伸缩，[Automated Demand-driven Resource Scaling in Relational Database-as-a-Service]使用手动构建的规则层次结构提出了一种数据库服务DasS的自动扩展解决方案，资源需求估计器从DBMS的内部延迟、资源利用率和等待统计数据中获取信号，以确定对资源的需求是高还是低。他们的工作侧重于短期趋势，并单独估计对每种资源的需求。
• 其他研究研究了在云平台中主动扩展资源。所有这些方法都估计在不久的将来是否会有对每种资源的需求。相反，本文对短期和长期的查询到达率进行建模，以支持复杂的优化规划决策。
• 数据库管理系统性能的建模和诊断方面已有较好的研究：DBSeer预测给定工作负载变化的“WHAT-IF”问题的答案，例如估计未来工作负载波动的磁盘I/O。该模型根据事务类型对工作负载进行聚类，并根据事务mixtures预测系统的资源利用率。缺点是一种离线模型，假定了事务的types。本文的工作不仅着眼于当前的工作负载组合，而且还预测了未来的工作负载。
• DBSherlock是一个事务性数据库的诊断工具，它使用因果模型来识别异常性能行为的潜在原因，并提供可视化，这一方面的工作建模主要是旨在帮助dba理解他们的系统并识别瓶颈。
• 使用分析模型来持续监控系统吞吐量、响应时间和缓冲池大小之间的关系。
• 其他人已经使用马尔可夫模型来预测用户将根据DBMS当前执行的语句来执行的下一个SQL语句，还有的扩展了该模型以检测工作负载变化，将这些技术与工作负载分类方法结合起来，对工作负载的周期性和重复模式进行建模，这些方法捕获工作负载中的某些模式，但是它们都不能预测未来工作负载的数量、持续时间和变化。
• Workload 压缩，与本文的目标相似，通过使用特定于应用程序的距离函数D(qi, qj)对任意一对SQL查询qi和qj搜索要从工作负载中删除的查询，可以压缩一组SQL DML语句。该技术不为查询的时间模式建模。
• 其他工作研究了如何预测特定查询的运行时指标。PQR使用决策树的一种变体来确定查询的延迟属于哪个桶，使用查询计划和系统负载指标作为输入特征。

9 CONCLUSION

本文提出了一个预测框架，允许DBMS根据历史数据预测未来查询的预期到达率。使用查询的逻辑组合来减少需要监控的查询数量，使用在线聚类方法将具有相似模式的查询模板分组在一起，使用混合学习方法来预测查询到达率。结果表明，QB5000在帮助DBMS实时选择目标工作负载的最佳索引方面是有效的。