菜菜的秘密花园SWIRL: Selection of Workload-aware Indexes using Reinforcement Learning
本文为论文 SWIRL: Selection of Workload-aware Indexes using Reinforcement Learning 的阅读笔记。
1 简介
🔴 我们提出了一种基于RL的索引选择方法，与最好的竞争者的性能相匹配。
🟡 我们的解决方案采用了一个复杂的工作负载模型，以推广到具有未见过的查询的工作负载，并依靠无效动作屏蔽来减少训练时间。
🔵 我们包括了基于RL的索引选择的首次调查和性能研究，并通过PostgreSQL上复杂的分析性数据库基准评估我们的方法。
2 背景
2.1 索引选择问题
大的解决方案空间。 相关候选索引的数量取决于工作负载查询访问的属性数量、每个索引的最大属性数量。评估所有候选组合通常是不切实际的，因为它们的数量超过了属性的数量级。
索引交互。 一个索引的存在会影响其他索引的性能。因此，在索引选择的每个步骤中，必须要考虑到当前存在的索引，经常需要重新计算候选索引的收益。
量化索引影响。 漫长的创建和执行时间使得物理上创建索引并不可行。索引选择方法通常依赖于估计而不是实际测量。（假设索引）
2.2 问题定义
假设有 N 个查询，K 个属性，每个查询 n 的属性表示为 $q_n⊆{1,…,K},n=1,…,K$ 。 W为每个索引包含的属性个数（索引宽度），$m_i$ 为需要的存储空间。索引的选择由子集 $I^*⊆I$ 表示，其执行成本为 $c_n(I^*)$ ，出现频率为 $f_n$ 。总的工作负载成本为：
目标是确定 $I^*$ 使 $C(I^*)$ 最小，并且不超过给定预算 B。
2.3 强化学习
强化学习（RL）包括一组算法，用于解决决策问题。
这些问题的特点是，在给定状态 $s_t∈S$ ，反复允许一个代理执行行动 $a_t$ ，其中 $a_t∈A$ 。在执行了所选择的行动后，达到新的状态 $s_{t+1}$ ，重复该过程。为了向代理人提供关于行动是否选择得当的反馈，他们会收到反馈信号，即每次决策后的奖励 $r_t$ 。
问题是要找到一个最佳决策，它将状态映射为行动，涉及到以时间 t 为开始状态的未来长期报酬：
Q-value 是给定状态 $s_t$ 和动作 $a_t$ 时，$G_t$ 的期望值： $Q(s,a)=E[G_t|s_t=s,a_t=a]$ 。η 为学习率，通过迭代可得：
不是所有 A 内的行动都适用，例如预算的限制。这种无效的行动可以通过分配大量负面奖励来建模。我们将引入另一种反馈机制： 行动屏蔽。
3 相关工作
大多数技术要么迭代地将索引从零添加索引，要么从满状态一步步减少。
建议的解决方案应该接受存储预算作为停止标准，因为与限制索引数量相比，它们允许更多的细粒度解决方案。
4 SWIRL
4.1 概述
图2概述了基于RL的索引选择过程中涉及的实体以及它们如何交互。该过程分为三个阶段：
🔴 预处理：生成训练和测试工作负载，确定候选指标，并准备工作负载表示模型；
🟡 训练：代理学习哪些索引对所提供的查询有价值，以及这些索引如何交互；
🔵 应用：代理应用训练后的模型来确定某些工作负载的索引。
【预处理】
① 用户指定一组具有代表性的查询。
② 基于输入模式的属性和代表性查询集生成索引候选。
③ 基于具有代表性的查询，生成随机工作负载，分为训练集和测试集。
④ 工作负载模型负责创建工作负载表示，即将关于当前工作负载的查询的信息转换为可以传递给神经网络的数字表示。
【训练】
RL过程的核心组件是索引选择环境和索引选择代理。
⑤ 环境为每个训练事件检索一个新的工作负载
⑥ 在给定当前索引配置的情况下，向假设优化器传送当前工作负载的查询成本和计划。
⑦ 代理的操作空间被限制为仅包含对当前状态有效的操作，尽快收敛候选索引。
⑧ 环境的当前状态，如剩余预算、当前成本和活动索引，被转换为数字特征，以便将其传递给代理。
⑨ 从工作负载模型中检索工作负载表示。
⑩ 环境的状态和奖励被传递给代理。
⑪ 代理返回有效操作。
⑫ 在环境通过假设程序创建索引来实现代理的操作之后，该过程在步骤6继续，直到没有剩余的有效操作为止。
【应用】
⑤ 在这里接收实际工作负载
⑪ 从空的索引集开始，代理重复评估ANN并选择行动（通过在 ⑩ 得到的最高回报）
4.2 模型
4.2.1 状态表示
【工作负载】
① N个长度为R的数值向量表示查询的内容 ② 一个长度为N的向量表示每个查询的频率 ③ 一个长度为N的向量表示每个查询的估计执行成本。
虽然神经网络结构是固定的，一个用工作负载大小N训练的模型总是可以用来确定索引配置，即使当工作负载大小不是N时。
【元信息】
包含4个标量特征：① 当前指定的存储预算 ② 当前存储消耗（基于假设优化器的索引大小预测）③ 初始成本 ④ 当前成本。
【当前索引配置】
我们分别对每个可索引属性的当前索引配置信息进行编码，以避免大的特征空间。
【连接和规范化】
在呈现的状态信息被传递到神经网络之前，向量被连接起来，并进行均值为0、方差为1的归一化。
【特征数量】
F为特征数量，N为工作负载的查询数量，R为工作负载的指定宽度，MI为元信息，K为属性数量，则有：$F=N·R+N+N+MI+K$ 。
4.2.2 工作负载建模&查询表示
🔴 利用假设优化器和候选索引，从一组代表性查询中构建代表性计划。
🟡 与索引选择相关的每个计划的操作符都转换为文本表示形式。
🟢 所有代表性计划的文本表示都存储在操作符字典中，该字典为每个不同的操作符文本表示分配一个ID。这些ID将在下一步中用于构造操作符袋(BOO)，即查询操作符的数字表示。
🔵 使用BOO而不进行进一步处理将导致每个查询产生大量稀疏特征。基于所有代表性计划的BOO表示，我们建立了一个潜在语义索引模型来减少特征数量。（随机预测、主成分分析等，也可用于降低维数）
4.2.3 行动
我们利用【无效操作】屏蔽给定当前状态的操作，从而使代理只考虑所有可用操作的子集。有效的操作必须在每一步之前更新，并且有4个原因可以导致操作被标记为无效，如图5所示。
① 候选索引与工作负载无关。即是否所有索引的属性都出现在工作负载中。
② 索引将超出预算。
③ 索引已经存在。
④ 前提条件无效。在第一步之前，所有多属性索引都被屏蔽为无效。只有当agent选择了一个索引(A)之后，所有以A为第一属性的多属性索引(如(A, B)， (A, C))才会生效。
4.2.4 奖励
为了一致地优化每个步骤中的存储使用，我们将索引选择 $I^*_t$ 额外使用的存储视为奖励：
5 实验
5.1 表现
测试的工作负载和训练的工作负载在以下方面有所不同：① 查询模板的确切组合 ② 在训练期间没有看到确切的频率-模板-组合 ③ 测试的工作负载包含训练时保留的未知模板。
SWIRL与最先进的方法相比具有竞争力，并且优于DRLinda：就成本而言，它的性能大致与表现最好的算法相当；在选择运行时方面，它在所有情况下都优于所有竞争对手。
AutoAdmin和Extend在之前的性能研究中是最好的，但它们通常要慢几个数量级。
5.2 训练时间&工作量
【训练时间】
训练持续时间是指在没有进一步改进之前收敛所需的时间。包含计算状态表示、应用动作掩蔽、创建假设索引、更新神经网络权重以及在训练期间使用神经网络进行预测所需的时间。
以下几个方面影响了问题的复杂性，从而影响训练时间：① 工作负载大小 ② 查询的复杂性 ③ 索引候选数。
【动作屏蔽的有效性】
图8显示，在开始时，只有8%的操作是有效的；随着剩余预算的减少，越来越多的索引因为太大而失效。此外，大多数有效操作引用宽度为1和2的索引。可见无效操作屏蔽是限制操作空间的一种有效技术。
这种技术也减少了收敛所需的训练时间。在没有动作掩蔽的情况下，即使延长训练时间，整体性能也可能更差。