一种基于深度强化学习的索引选择方法

瞿 中,吴哲一

(重庆邮电大学 计算机科学与技术学院,重庆 400065)

1 引 言

数据库系统已经在行业中成熟而稳定地运行,而大数据时代为数据库系统提出了更高的要求.随着数据量的增大,也要求数据库系统能够具备更快的查询速度、更高的系统吞吐量.数据的类型模式不断增多,使得工作负载具有快速而又多样化的特点,要求数据库系统能够具备快速、准确地响应查询负载动态变化的能力[1].随着数据规模的不断增大,数据库性能的调优对研究人员、企业和数据库管理员(Database Administrator,DBA)也变得越来越重要.数据库性能调优的一个重要的方面是选择合适的索引.索引选择问题(Index Selection Problem,ISP)是数据库性能调优中的重要问题之一.在系统中设置适当的索引可以加快数据的访问过程,使用不合适的索引不仅浪费资源,而且还会对系统造成不必要的磁盘开销与索引维护代价[2].

强化学习[3](Reinforcement Learning,RL)是机器学习的一个分支,是与人类学习最接近的一种形式,可以通过探索和利用未知环境来学习经验.环境(Environment)传递给智能体(Agent)环境状态信息,智能体执行相应的动作(Action),环境反馈给智能体一定的奖励(Reward);智能体的目的是最大化累计的奖励,通过反复的交互,智能体可以做出最优的动作.深度学习[4](Deep Learning,DL)的优势在于感知能力,可以让智能体提取到外界环境状态的有效特征.DeepMind将深度学习的感知能力和强化学习的决策能力相结合,提出了深度强化学习[5](Deep Reinforcement Learning,DRL),并创造出AlphaGo.

传统索引选择方法如AutoAdmin[6]、DB2Advis[7]使用不同的启发式规则生成候选索引,来减少配置搜索空间,在通过贪心算法找到最优的索引选择.但索引之间是可以相互影响的,即一个索引的优化效果会因为另一个索引的的存在而受到影响[8].因此,要找到最佳的索引组合就必须考虑索引间的交互,不能仅仅考虑单个索引的优化效果,因为每个索引可能会影响所有其他索引,所以从一大堆候选索引中找到最佳索引非常具有挑战性,索引交互极大地增加了索引选择的复杂性.传统的索引选择方法先生成候选索引,再利用动态规划等算法从候选索引中选择在限制条件最优的索引组合,但都没有考虑到不同索引间的影响.近年来,将机器学习应用于索引选择问题成为了热门的研究方向.Sharma等人提出的NoDBA[9]系统提供了一个用强化学习进行索引选择的思路,将工作负载和候选索引表示为强化学习中的环境,将在某列上创建索引表示为动作,其证明了将强化学习应用于索引选择是可行的.文献[10,11]提出了基于深度强化学习的索引推荐方案,但大多数也只能选择单列索引,就会错过类似于覆盖索引这样可以大幅度提升查询性能的多列索引,并且上述方法没有考虑到索引交互的影响.文献[12]考虑到索引交互的影响,其将已创建索引之间的交互建模为神经元之间的交互,但没有将不同索引配置下的数据库查询性能进行比较,不能充分考虑到索引交互对索引选择带来的影响.

针对上述问题,本文将索引选择过程建模为马尔可夫决策模型,首先通过对数据库的工作负载进行分析生成候选索引,然后利用深度强化学习算法训练智能体进行索引选择.相对于目前的索引选择方法,本文提出的方法具有以下优点:

1)将索引选择问题定义为一个马尔可夫决策过程,提出一个基于深度强化学习的索引选择方法,并通过制定索引评价规则生成候选索引,实现了单列索引和多列索引的同时选择.

2)通过定义深度强化学习过程中数据库环境的状态表示、智能体的动作和奖励函数,充分考虑了索引之间可能的交互,能够选择最优索引组合.

2 模型算法与理论

2.1 强化学习

强化学习的目标是最大化智能体的累积奖励,使用强化学习的智能体可以通过与环境的反复交互,学会选择近似最优的行为以实现其目标,最终学习得到一个环境状态到动作的映射关系.其原理如图1所示.

图1 强化学习原理Fig.1 Principle of reinforcement learning

强化学习过程属于马尔科夫决策过程(Markov Decision Process,MDP).通常,将MDP定义为一个四元组:

(S,A,R,P)

(1)

其中,S表示环境的状态信息,st∈S表示智能体在t时刻的环境状态;A为智能体可执行的动作,at∈A表示智能体在t时刻执行的动作;R是奖励函数,rt∈R表示智能体在t时刻获得的奖励值;P为状态转移概率分布函数,表示智能体执行动作at,从状态转移到下一状态st+1的概率.

P(st+1,rt+1|s1,a1,r1,…,st,at,rt)=P(st+1,rt+1|st,at)

(2)

公式(2)表明,状态st+1仅与当前状态st相关,与之前状态无关.在强化学习中,智能体以获得最大累积奖励为目标,t时刻的累积奖励可表示为:

(3)

其中,γ∈[0,1]是折扣系数,代表智能体对未来奖励的重视程度.

2.2 DQN算法

强化学习根据是否需要价值函数分为基于价值(Value-based)的和基于策略(Policy-based)的,Q-Learning是基于价值中的代表性算法.状态-动作函数Q(s,a)指在某一时刻的s状态下,采取动作a能够获得奖励的期望,该算法将所有状态s与动作a关联起来组成一张Q表,来存储状态动作对(s,a)的Q值,通过在每个状态下选择具有最高Q值的动作来形成策略,Q值的更新如式(4)所示:

(4)

Q-Learning算法通过表格来存储Q值,当状态-动作空间很大时,表格的维度也会增大,导致在表格中的搜索效率降低.深度强化学习是强化学习与深度学习相结合的全新算法,能够有效地对任务中的高维状态与数据特征进行提取,可以有效地解决Q表的维度过大的问题.

Mnih等提出了深度Q网络[5](Deep Q Network,DQN).DQN采用神经网络来代替Q表,解决了Q-Learning算法的Q表的维度过大的问题.DQN中有两个结构相同但参数不同的神经网络,分别为评估网络和目标网络,为了提高了算法的稳定性,首先让评估网络在执行动作后都会进行参数更新,目标网络隔一段时间将评估网络参数硬拷贝过来,实现目标网络的更新,其次使用经验回放机制打乱了样本之间的相关性.目标值网络Q值的计算公式如公式(5)所示:

(5)

(6)

为缓解DQN中动作值函数容易产生Q值过估计的问题,Van等提出了双重深度Q网络模型[13](Double Deep Q Network,DDQN).DDQN的网络结构与DQN类似,主要是将动作选取和值评估解耦,首先根据公式(7)利用当前Q网络选择Q值最大的动作.

(7)

再通过公式(8)选出的动作在目标Q网络中计算目标Q值.

(8)

通过以上步骤有效缓解了DQN中存在的Q值过估计问题.

3 索引选择问题描述

索引选择问题是在特定限制条件下,如存储限制,索引数量限制,调优时间限制等,为给定工作负载找到一组索引组合,能最大限度提升数据库系统的查询性能.

数据库D中包含n张表{T1,T2,…,Tn},其中Ti为数据库中的表.工作负载W(大小为m)是一组工作负载W={Q1,Q2,…,Qm},Qi是第i条查询语句.索引配置I为一组索引{i1,i2,…,ik},可能包含来自不同表的单列索引或多列索引.C为当前的限制,如索引的内存限制或数量限制.Cost(Qi,I)表示在索引配置I下查询语句Qi的查询成本.因此,工作负载W在索引设置I下的查询成本如公式(9)所示:

(9)

本文对索引选择问题的优化目标是,在一个包含n张表的数据库D上,针对一组工作负载W,在限制条件为C的情况下生成一组候选索引Ic,并从候选索引Ic选择一组索引I*并使得公式(10)成立:

(10)

4 基于深度强化学习的索引选择方法

本节主要阐述将深度强化学习应用于索引选择算法的相关定义,包括通过索引评价规则生成候选索引和分别对深度强化学习算法所需的数据库环境状态、索引选择智能体的动作、奖励等信息进行定义.

4.1 候选索引的生成

如果在有一张含有n列的表建立一个维度为i(1≤i≤n)的索引,索引的第1列有n种选择,第2列有n-1种选择,以此类推这张表可能索引数量如公式(11)所示:

(11)

如果一张表有10列,就有10种不同的可能性单列索引,有90种2个属性的索引,若索引包含5个属性,则可能的索引有30240种[14].如果要实现多列索引的选择,通过穷举所有可能的索引作为候选索引是不现实的.因此,本文通过使用索引评价规则对工作负载进行分析,进而生成高质量地候选索引,限制候选索引的数量.本文提出的索引选择方法只对二级索引进行操作,所以创建的索引都是B+树结构.

本文根据文献[15]提出的观点,在一条查询语句中,对在谓词条件、连接条件、GROUP-BY条件、ORDER-BY条件关联的属性创建索引能最大程度提升查询效率.因此文中设计5条索引评价规则,能最大程度提供高质量的候选索引.规则如下:

规则1.将查询语句中WHERE后面所有出现的属性设为单列索引.

规则2.将WHERE后面的等值查询和范围查询关联的属性作为多列索引,且索引中的顺序和查询语句中的排列顺序一致.

规则3.若出现ORDER-BY和GROUP-BY,多列索引需要包含对应关联的属性,且保持顺序一致.

规则4.若有具体要查询的属性,多列索引需包含全部要查询的属性,即为覆盖索引.

规则5.若出现多表连接查询,将连接查询处的每个表的连接属性分别设为单列索引.

规则1将在查询语句中所有WHERE后面出现的属性都设置为单列索引,虽然这些单列索引有可能不会给对查询语句带来优化,但是单列索引数量的有限,并不会带来维度爆炸的问题,同时能给索引选择智能体更多动作选项.因为本文创建的B+树索引是一种有序的数据机构,所以对于一个查询语句,一个索引只要按照前缀顺序包含该查询语句的WHERE条件中属性,该索引就可以对此查询语句进行优化,由此引出规则2.当查询语句包含ORDER-BY和GROUP-BY等排序操作时,通过规则3可以在创建索引时就进行排序,这样在进行查询时就无需多余的排序操作.

当查询语句为SELECT×FROM … WHERE…时,首先要通过二级索引查询到符合WHERE后条件记录的主键ID,再根据主键ID通过聚集索引访问数据表找到对应的记录,这个过程叫做回表查询.但如果有具体要查询的属性,就可以通过规则4创建覆盖索引,这样就避免再次访问表的操作.

连接查询的执行相对比较复杂,在执行连接查询时在主要由嵌套循环连接、哈希连接和合并扫描连接这3种方式对表进行连接,不同的连接方式对索引的设置有着不同的要求.在使用嵌套循环连接时,表的访问顺序会对索引的设置有着重大的影响,主要取决于那一张表是驱动表.而哈希连接和合并扫描连接都是先通过连接字段进行扫描,保存在一个临时表中,再通过扫描其他的表满足本地谓词条件的记录和临时表中对应记录进行匹配,所以在连接属性上创建索引都有可能对查询语句进行优化.因此,本文提出规则5,将每个表的连接属性设为单列索引.

4.2 基于DDQNPER的索引选择智能体

优先级经验重放[16]被证明是对传统经验重放的一种非常有效的改进,因为优先级经验重放不是均匀抽样,而是对样本进行加权,使得产生高误差的样本在训练中更容易被抽取,有助于降低总体偏差.DDQN算法有效缓解了DQN中存在的Q值过估计问题.本文将它们的优势结合,提出基于DDQNPER的索引选择方法.

本文中基于DDQNPER的索引选择方法中的Q-Learning算法基本要素可表示为:

1)环境(environment):基于PostgreSQL数据库的TPC-H实例.

2)智能体(agent):智能体是索引选择调优,它接收来自环境的状态和奖励,并在每一步更新策略以选择合适的索引.

3)动作(action):在索引选择过程中,动作at可表示为在步骤t时,在候选索引I中选择一个索引i,其中i∈I.

4)状态(state):状态st由一个向量表示,初始化都为0,每个位置表示当前候选索引的选择与否,当选择某个索引时,将其对应位置设置为1,表示已经选择,状态空间维度等于动作空间维度,也就是候选索引的数量.

5)策略(policy):策略是从状态映射到动作的函数,策略π从s0开始,在每个时间步下选择一个索引,进入下一个状态st+1,这个过程重复进行,直到达到索引数量限制.执行完策略的结果是选择过的索引集合.

6)奖励(reward):在强化学习中,奖励是智能体不断完善自己,使自己能够自主实现目标的直接经验来源.智能体在进行索引选择时,每次选择新索引indexnew创建之后,所有索引整体的优化效果会出现变化,这可能是创建indexnew带来的优化效果或者indexnew与indexesold中某些索引交互产生的,因此,本文将这两种情形都考虑在内.因此本文在设计奖励函数时将索引交互对索引选择的影响考虑在内,将当前索引配置下Cost(W,It)与初始化下索引配置下Cost(W,I0)以及上一次索引选择配置下Cost(W,It-1)进行比较,其奖励函数如公式(12)所示:

(12)

α和β为两个取值范围为[0,1]的因子,用于调节索引交互对于奖励的影响,α/β越大,说明智能体越重视当前索引配置相对于上一次索引配置的带来查询性能的变化,也就是索引交互可能带来的影响,而不是考虑当前索引配置相对于初始状态下查询性能的变化.

4.3 改进的ε-greedy探索策略

动作的选取在强化学习中十分重要,ε-greedy策略是经常被使用的选择策略.在传统强化学习算法中,探索因子ε的值是固定的,如果ε的值太小会导致智能体在训练前期无法对环境进行充分探索,导致智能体陷入局部最优.若其太大,会导致训练后期智能体虽然已经对环境进行了充分探索,但仍然以较大概率随机选取动作,而非通过当前策略选择最优动作,出现过度探索而利用不足,这样和寻找最优策略的原则不相符合.

在索引选择问题场景下,DRL的状态空间和动作空间都是非常大的,如果在智能体训练前期不进行充分的探索,很难学习到最优的策略,但是如果在训练后期智能体还在过度探索,则可能导致神经网络很难收敛,所以根据索引选择问题的实际情况,本文基于ε-greedy策略提出一种改进的动态探索策略,ε值的变化如公式(13)所示:

(13)

其中x为训练步数,μ为偏移量.图2展示了不同偏移量下对应ε值的变化.

图2 ε 值变化曲线Fig.2 Variation curve of ε value

如图2所示,随着μ值的增大会ε值变化的曲线向右偏移,所以智能体训练中前期的探索的机会越多,随着训练过程的深入,ε值始终会收敛到一个较小的水平,保证了智能体更大概率地利用当前最优策略.

4.4 索引选择智能体的训练

索引选择算法的核心在于训练神经网络,为了使DDQNPER网络模型适用于索引选择场景,需要创建真实的数据库实例场景,并根据随机生成的工作负载对智能体进行训练,通过迭代求解不断更新网络参数,使得神经网络的训练收敛,最终得到完成训练的智能体.

基于DDQNPER的索引选择方法分为候选索引的生成和训练两个阶段,训练过程如图3所示.

图3 基于DDQNPER的索引选择方法学习过程Fig.3 Learning process of ISP based on DDQNPER

算法1.基于DDQNPER的索引选择算法

输入：训练回合数V,每回合训练步数T,目标网络更新频率C,折扣率λ,ε中的偏移量μ;

输出：训练完成的索引选择智能体

1.随机初始化评估网络参数θ和目标网络参θ′

2.初始化经验单元,容量为N

3.生成工作负载,通过索引评价规则生成候选索引;

4.For episode=1 toVdo:

5. 初始化数据库系统;

6. For episode=1 toTdo:

7. 在状态st下,通过公式(13)计ε,利用概率ε随机选取动作;

9. 执行动作at,测试数据库系统查询性能,并以此计算rt,状态转换为st+1;

10.将(st,at,st+1,rt)组成训练样本存入经验回放单元;

11. 从经验回放单元随机抽取训练样本,并对抽取的样本进行排序;

14. 每训练C轮后,用评估网络的参数更新目标网络的参数,即θ′=θ;

15. End For

16.End For 参数θ,θ′收敛

本文利用算法1训练智能体.训练开始前,对数据库系统和深度强化学习的神经网络参数进行初始化,然后随机生成工作负载,并根据本文提出的索引评价规则生成候选索引.每执行完一次训练回合,对数据库系统进行初始化,删除所有本回合创建的索引.

智能体在选择动作前,首先通过公式(13)先计算ε值,再根据ε决定随机选择还是选取Q值最高的动作执行,执行完动作后获得奖励,同时转换到下一个环境状态.由于需要训练神经网络模型,所以将训练数据以(st,at,st+1,rt)的形式存储到经验回放单元.经历C次迭代训练后,从经验回放单元抽取批量训练数据对评估网络进行训练更新.根据目标网络更新频率,用评估网络的参数替换目标网络的参数;执行完所有的训练回合后,得到训练完成的索引选择智能体.

算法1的时间复杂度为O(V×(Ti+Ta+Tnn)),其中V为训练回合数,Ti是本次训练回合开始前数据库状态初始化的时间,Ta是在数据库系统中创建索引的时间,Tnn是神经网络进行训练更新的时间.

本文中神经网络模型训练相关参数设置如表1所示.

表1 超参数列表Table 1 Hyperparameter list

索引选择智能体的网络模型由3个全连接层组成,(输入为数据库系统当前候选索引的配置,所以网络模型的状态维度和动作维度也与候选索引数量相同,输出为每个候选索引的Q值.智能体的网络模型结构如图4所示.

图4 模型结构Fig.4 Model architecture

5 实 验

5.1 实验环境

本文在PostgreSQL数据库系统上进行了实验测试,并使用PostgreSQL的HypoPG(1)http://github.com/hypopg扩展来创建虚拟索引,避免实际的查询执行和索引创建的开销.本次实验在Intel Xeon 3160 CPU,NVIDIA GeForce RTX 2080 GPU,RAM:16GB的服务器上进行,操作系统为Ubuntu 20.04.本次实验所有的代码都使用Python和PyTorch实现,公式(12)中的参数α与β的值都为0.5.

5.2 工作负载的生成

TPC(2)http://www.tpc.org是业界广泛使用的一套数据库基准测试,其中TPC-H用于评测数据库的分析查询能力,主要用于对数据库系统进行基准测试.但是,TPC-H不是索引选择方法的基准测试.TPC-H测试的工作负载非常复杂,不仅包含大量函数操作,还存在许多子查询以及分组查询,并不符合实际场景下的数据库操作,所以本文采用自定义生成的工作负载.

为了验证本文提出的基于DDQNPER改进的索引选择方法(简称为DDQN-MC)的有效性,本文使用了两种类型的工作负载来验证.工作负载A中的查询语句对所有表进行SELECT T_A.C_B或者SELECT COUNT(*)查询,在WHERE后通过谓词[AND,OR,JOIN]连接最多3个随机创建的查询条件,WHERE子句查询条件为等值查询(例如L_TAX=0.02)或者范围查询(例如L_SHIPDATE<′1994-01-01′),查询语句最后可能包含聚合[GROUP-BY,ORDER-BY],T_A和C_B的值随机地从数据库中选择真实存在的值.工作负载A由5组不同类型的查询语句组成,每组各生成4条查询语句,类型示例如表2所示.分别生成训练工作负载和测试工作负载各20条查询语句.工作负载的多样性有助于验证索引选择方法的有效性.

表2 查询语句示例表Table 2 Query statement sample table

工作负载B中的每条查询语句都是对LINEITEM表进行SELECT COUNT(*)查询,在WHERE后通过AND连接最多7个随机创建的查询条件,WHERE子句查询条件为等值查询或者范围查询.分别生成训练工作负载和测试工作负载各10条查询语句.

5.3 实验评估与结果分析

本次实验通过TPC-H生成大小为1GB的数据库实例,索引数量限制为3,使用工作负载B.将基于动态探索策略的DDQN-MC和传统DDQN算法进行分别执行100次迭代训练,对两种算法每一步的平均奖励值进行比较.平均奖励值的数据如图5所示.

图5 DDQN算法和DDQN-MC算法平均奖赏值对比图Fig.5 Comparison of the average rewards values between DDQN and DDQN-MC in simple environment

NoDBA同样是一个基于DRL的索引选择智能体,其将当前索引配置和工作负载作为DRL中的环境,可执行的动作为在某列上创建索引,所以其无法推荐多列索引.为了能与DDQN-MC进行比较,本次实验的使用工作负载B,且基于DDQN的索引选择方法和DDQN-MC都没有使用本文提出的索引评价规则生成候选索引,候选索引都为工作负载B中出现过的属性,皆为单列索引.

由图6和图7的实验结果可以得知,在创建相同数量索引的情况下,DDQN-MC选择的索引组合相对于NoDBA和DDQN能更多地提升数据库系统的查询性能.NoDBA在设计奖励函数没有将索引交互考虑在内,只比较当前索引配置相对于初始状态下数据库系统查询性能的变化,所以出现随着索引数量的增加查询性能提升率增加缓慢甚至退化的情况.而基于DDQN的索引选择方法和DDQN-MC都可以随着索引数量的增加使得查询性能提升率有所提升.

图6 数据库实例大小为1G时不同方法查询性能提升率对比Fig.6 Comparison of performance improvement rate of different methods when the database instance size is 1GB

图7 数据库实例大小为10G时不同方法查询性能提升率对比Fig.7 Comparison of performance improvement rate of different methods when the database instance size is 10 GB

由图7可以看出,在数据库实例大小为10G时,基于DDQN的索引选择方法和DDQN-MC的性能都有所下降.随着数据规模的增加,在硬件的不同状态下,相同工作负载的执行时间变化较大,而工作负载的执行时间对智能体的训练迭代有着关键的作用,所以导致智能体无法学习到最优的策略,但仍可以看出DDQN-MC的性能要明显优于基于DDQN的索引选择方法和NoDBA.

为了验证本文提出的提出索引评价规则和DDQN-MC的有效性,本文将其与能同样推荐多列索引的AutoAdmin、POWA(The PostgresSQL Workload Analyzer)以及基于索引评价规则和DDQN的索引选择方法分别在大小为1G和10G的数据库实例上进行对比实验,执行工作负载A.

AutoAdmin是Microsoft公司研究的数据库系统自动化管理和调优的技术,并将其应用于Microsoft SQL Server,其能根据工作负载同时选择单列索引和多列索引,为了能与DDQN-MC进行比较,本文使用Jan[17]等针对PostgreSQL重新实现的AutoAdmin方法.

POWA是一个分析PostgresSQL工作负载的工具.POWA对数据库中各种数据进行统计,其组件pg_qualstats能够根据工作负载提出建议索引.

通过图8和图9实验结果可以发现,DDQN-MC在每个阶段选择索引的优化效果都要强于其他3种方法,随着索引数量的增加,工作负载的执行时间也逐渐减少.DDQN在数据库实例大小为1G的所有阶段和数据库大小为10G时绝大部分阶段选择索引的优化效果也是优于AutoAdmin和POWA.

图8 数据库实例大小为1G时不同方法查询时间对比Fig.8 Comparison of query time between different methods when the database instance size is 1GB

图9 数据库实例大小为10G时不同方法查询时间对比Fig.9 Comparison of query time between different methods when the database instance size is 10 GB

通过在不同场景下进行对比,DDQN-MC都能选择出更优的索引组合,有效地提升了数据库的查询性能.

6 结 语

本文提出一种基于深度强化学习的索引选择方法.相比于传统的索引选择方法,本文提出的方法能更好地考虑索引交互的影响.与典型的基于深度强化学习的索引选择方法相比,其不仅考虑索引交互的影响,还能够选择单列索引和多列索引,且相对于这两种方法,其能够选择出更优的索引组合.

但是本文提出的方法存在一定的局限性,例如未考虑索引创建带来的时空开销以及索引的删除等方面.在未来的工作中,可以用全面的指标来评价索引选择方法,把智能体和数据库环境的交互以及奖励的设计作为重点,同时将更多深度强化学习算法应用于索引选择也是未来的发展方向之一.