面向时空数据场景的数据库索引选择框架.pdf

2023年第49卷第4期无线电通信技术665 doi:10.3969/j.issn.1003-3114.2023.04.010引用格式:徐康镭,乔少杰,陈金勇,等.面向时空数据场景的数据库索引选择框架J.无线电通信技术,2023,49(4):665-673.XU Kanglei,QIAO Shaojie,CHEN Jinyong,et al.A Framework for Database Index Selection over Spatio-temporal Data Scenarios J.Radio Communications Technology,2023,49(4):665-673.面向时空数据场景的数据库索引选择框架徐康镭1,乔少杰1,陈金勇2,张 桃3,高 林2,冉黎琼1,谢添丞1,于 泳1,彭钰寒1,焦育威4(1.成都信息工程大学 软件工程学院,四川 成都 610225;2.中国电子科技集团公司第五十四研究所,河北 石家庄 050081;3.宜宾学院 人工智能与大数据学部,四川 宜宾 644000;4.四川数字交通科技股份有限公司,四川 成都 610225)摘 要:索引是一种用于提高数据库查询效率的数据结构,良好执行计划的生成和选择很大程度上取决于数据表上是否存在合适的索引。然而,面对复杂的时空数据场景,现有的索引选择方法存在很多不足,如无法高效处理大量范围查询、容易造成索引冗余、无法有效应对动态的工作负载等问题。针对上述问题,提出一种新型基于深度确定策略梯度(Deep Deterministic Policy Gradient,DDPG)模型和索引效益评估网络的索引选择框架:ST-IS(Index Selection method tailored for Spatio-Temporal data scenarios)。ST-IS 集成了对 SQL 语句和索引集的新型编码方法,有效避免索引冗余或索引缺失。ST-IS 使用索引效益评估网络来优化强化学习的奖励机制,同时支持动态的工作负载。大量实验结果表明,在真实时空数据集和 TPC-DS 标准数据集上,ST-IS 的性能优于现有的索引选择方法。关键词:时空数据;强化学习;索引选择;查询优化;移动数据挖掘中图分类号:TP311 文献标志码:A 开放科学(资源服务)标识码(OSID):文章编号:1003-3114(2023)04-0665-09A Framework for Database Index Selection over Spatio-temporal Data ScenariosXU Kanglei1,QIAO Shaojie1,CHEN Jinyong2,ZHANG Tao3,GAO Lin2,RAN Liqiong1,XIE Tiancheng1,YU Yong1,PENG Yuhan1,JIAO Yuwei4(1.School of Software Engineering,Chengdu University of Information Technology,Chengdu 610225,China;2.The 54th Research Institute of CETC,Shijiazhuang 050081,China;3.Faculty of Artificial Intelligence and Big Data,Yibin University,Yibin 644000,China;4.Sichuan Digital Transportation Technolgy Co.,Ltd.,Chengdu 610225,China)收稿日期:2023-03-04基金项目:国家自然科学基金(62272066,61962006);四川省科技计划(2021JDJQ0021,2022YFG0186,2022NSFSC0511,2023YFG0027,2022YFG0325,2021YFG0029);教育部人文社会科学研究规划基金(22YJAZH088);宜宾市引进高层次人才项目(2022YG02);成都市“揭榜挂帅”科技项目(2022-JB00-00002-GX,2021-JB00-00025-GX);成都市重大科技创新项目(2021-YF08-00156-GX);中国电子科技集团公司第五十四研究所高校合作课题(SKX212010057);四川省教育厅人文社科重点研究基地四川网络文化研究中心资助科研项目(WLWH22-1);成都信息工程大学科技创新能力提升计划(KYTD202222);成都海关科研项目(2022CK008)Foundation Item:National Natural Science Foundation of China(62272066,61962006);Sichuan Science and Technology Program(2021JDJQ0021,2022YFG0186,2022NSFSC0511,2023YFG0027,2022YFG0325,2021YFG0029);Planning Foundation for Humanities and Social Sciences of Ministry of Education of China(22YJAZH088);High-level Talent Introduction Project of Yibin(2022YG02);Chengdu“Take the lead”Science and Technology Pro-ject(2022-JB00-00002-GX,2021-JB00-00025-GX);Chengdu Major Science and Technology Innovation Project(2021-YF08-00156-GX);The 54th Re-search Institute of China Electronics Technology Group Corporation-University Cooperation Project(SKX212010057);Web Culture Project Sponsored by the Humanities and Social Science Research Base of the Sichuan Provincial Education Department(WLWH22-1);Science and Technology Innovation Capability Improvement Project of Chengdu University of Information Technology(KYTD202222);Chengdu Customs Scientific Research Project(2022CK008)666 Radio Communications TechnologyVol.49 No.4 2023Abstract:The index is a data structure used to improve the efficiency of database queries,and the generation and selection of a good execution plan depends much on the presence of appropriate indexes on data tables.However,existing index selection methods have many shortcomings when facing with complex spatio-temporal data scenarios,such as inefficient handling of a great number of range queries,potential index redundancy,and inability to effectively handle dynamic workloads.Aiming to cope with these problems,a new index selection framework called ST-IS(Index Selection method tailored for Spatio-Temporal data scenarios)is proposed,which is based on the Deep Deterministic Policy Gradient(DDPG)and an index utility evaluation network.ST-IS integrates a novel encoding method for SQL statements and index sets,effectively avoiding index redundancy or missing indexes.ST-IS uses an index utility evalua-tion network to optimize the reinforcement learning reward mechanism,while supporting dynamic workloads.Extensive experiments are conducted and the results show that ST-IS outperforms existing index selection methods on real spatio-temporal datasets and the TPC-DS benchmark dataset.Keywords:spatio-temporal data;reinforcement learning;index selection;query optimization;mobile data mining0 引言近年来,随着移动传感器、物联网、全球定位系统等技术的发展,时空数据的产生和应用越来越广泛1。时空数据是指具有时间和空间属性的数据,如轨迹数据2-3、遥感影像数据、地理位置数据等,常用于交通管理4-5、疾病监控、环境监测、犯罪分析等领域。时空数据具有多源异构、动态变化、复杂关联等特性。因此,如何高效地管理和查询时空数据成为数据库领域的一个重要研究问题。数据库索引是提高时空数据查询效率的一个重要手段之一,它可以根据不同的查询条件快速定位到所需的数据记录,但也会增加存储空间和更新开销6。索引选择的目的是适当地创建和删除索引,以确保索引的大小在约束范围内且工作负载的性能得到优化,过多无用或冗余的索引会浪费存储空间和更新时间,甚至可能影响数据库优化器选择最佳执行计划。传统的索引选择主要采用启发式方法7-10,它利用问题的启发信息(如属性的数据分布、查询频率、更新频率等),根据代价估计信息来指导索引的创建、删除和调整。然而,在面对时空数据场景时,传统的索引选择方法往往无法满足多样化、高效率、低延迟等需求,因此需要针对时空数据场景设计新型索引选择框架。基于以上问题,本文提出一种针对时空数据场景的索引选择框架(Index Selection method tailored for Spatio-Temporal data scenarios,ST-IS)。ST-IS 的主要贡献如下:提出一种基于深度确定策略梯度模型11的索引选择模型,能有效处理大规模时空数据下的连续索引选择动作。提出新型的 SQL 语句编码方法,能够准确地对复杂的嵌套 SQL 语句编码,定位索引候选属性,防止索引缺失。提出新型的索引集编码方法,能全面而精简地表达每个表上的索引集,大大简化索引选择动作,避免索引冗余。提出一种基于多头注意力机制12和门控循环单元(Gate Recurrent Unit,GRU)模型13的索引效益评估方法,使模型能在动态的工作负载14下保持索引的优化效果。在真实出租车数据集15以及 TPC-DS 通用模拟数据集16上进行大量对比实验,证明了本文所提方法的实用性和有效性。1 相关工作1.1 索引选择框架索引选择问题(Index Selection Problem,ISP)17是指在一定约束条件内(如存储空间限制、索引中包含的最大属性个数等),为给定工作负载选择最佳的索引集,使得该工作负载获得最佳的运行效率。ISP 问题已被证明为 NP-Hard 问题18-19,其难点包括:索引的选择不仅是在单个属性上进行,还需要考虑在多个属性上建立的联合索引,以及多表连接查询的复杂情况,这使得 ISP 问题的搜索空间大大增加。现实中的工作负载是动态变化的(如数据库的读写比、业务类型、表结构等),因此要实时更新索引,以避免数据倾斜造成优化效果变差。增加索引会造成数据的插入和更新变慢,因此要避免冗余的索引。目前,已有一些基于启发式算法的索引选择方法,将索引选择问题描述为背包问题。这些方法的搜索空间较大,且无法适用动态的工作负载。当发2023年第49卷第4期无线电通信技术667 生数据库相关业务变化时,需要重新考虑所有可能情况,不具有学习能力。1.2 深度强化学习深度强化学习是一种结合了深度学习和强化学习的机器学习方法,它能够让智能体在复杂的环境中通过与环境的交互来自主地学习最优的行为策略。Sharma 等人20提出一种基于 DQN21模型的索引选择方法:NoDBA;Zhou 等人22提出一种基于蒙特卡洛树23的索引选择框架。但它们仍存在一些不足:需用户指定索引的最大个数或单个索引中的最大属性个数,若选择不当会造成过度索引或欠缺索引。未考虑多表连接情况的索引选择,多表连接查询时的优化效果较差。推广到动态工作负载的能力较差,当数据及查询发生较大变化时,需要重新训练模型。未考虑索引过多导致数据更新效率变慢的问题,虽然查询效率得到提升,但整体工作负载的效率下降。2 问题表述与模型2.1 主要概念定定义义 1 1索引选择空间。在索引选择方法中,智能体可以创建多个索引,每个索引中可以包含多个属性。索引选择空间为某个数据库中所有可能的索引构成的集合。使用 ISet 表示整个索引集,使用ISeti表示单个索引。定定义义 2 2索引优化效果。Cost 和 Latency 是常用于数据库 SQL 语句效率评估的两个重要指标。其中,Cost 为 SQL 语句的代价估计值,获取 Cost 值不需要实际执行该语句;而 Latency 为 SQL 语句执行的实际时间。Ec(Qi)和 El(Qi)分别表示索引集ISet 对于每条 SQL 语句在两个指标上的优化效果。Ec(Qi)的具体计算公式如式(1)所示:Ec(Qi)=Cost(Qi,ISet)Cost(Qi),(1)式中:Cost(Qi)表示未添加索引时执行语句 Qi获取的 Cost 值,Cost(Qi,ISet)表示添加索引集 ISet 后执行语句 Qi获取的 Cost 值。El(Qi)的计算公式为:El(Qi)=Latency(Qi,ISet)Latency(Qi),(2)式中:Latency(Qi)表示未添加索引时执行语句 Qi的实际执行时间,Latency(Qi,ISet)表示添加索引集ISet 后执行语句 Qi的实际执行时间。2.2 基于深度强化学习的索引选择框架如图 1 所示,ST-IS 包含三个重要的组成部分:编码方法,包括对索引集的编码以及对 SQL语句的编码,为 DDPG 提供既准确又丰富的状态表示。索引效率评估模型,通过 Cost、实际执行时间、索引命中率等指标判断当前索引集的优化效果。效益评估模型包括多头注意力机制,用于处理 SQL语句编码;以及一个 GRU 模型,用于处理索引集编码。基于 DDPG 的索引选择模型,根据当前索引集的优化效果,做出添加索引、添加属性或删除索引的动作以进一步优化当前索引集。图 1 ST-IS 的整体架构Fig.1 Architecture of ST-IS索引选择框架分为训练阶段和运行阶段。在训练阶段,DDPG 通过选择各种索引集进行探索,使用已有的工作负载与数据库进行交互,获得 Cost、Latency 等信息。这些信息将被输入到索引效率评估模型,作为 DDPG 的奖励值。DDPG 将根据该奖励更新参数,并将结果保存到经验回放缓冲区中。在运行阶段,索引效率评估模块会继续收集数据库的工作负载、Cost、实际执行时间以及执行计划,从中分析索引的命中率以及数据库效率的变化情况,通过效益评估网络评估当前索引集是否需要被更新。2.3 编码方法索引选择模型的编码方法包括 SQL 语句编码和索引集编码。丰富的 SQL 语句编码有助于 ST-IS发现候选索引集,避免 DDPG 中智能体大量无意义的探索;高效的索引集编码能有效避免索引冗余或668 Radio Communications TechnologyVol.49 No.4 2023索引欠缺。2.3.1 SQL 语句编码索引可优化的 SQL 语句包括 INSERT、UP-DATE、SELECT、DELETE 语句,因此分别对其编码,并考虑其中受索引影响的条件,如 GROUP BY、OR-DER BY、JOIN 等子句类型。具体编码方法如下:使用 4 位 one-hot 编码表示 SQL 语句类型,其中,INSERT 语句编码为1 0 0 0,UPDATE 语句编码为0 1 0 0,SELECT 语句编码为0 0 1 0,DELETE 语句编码为0 0 0 1。采用 multi-hot 编码表示数据库中所有的列,编码的维度为列的数量,涉及到的目标列的编码为1,其余为 0。采用 5 位 one-hot 编码对查询子句类型进行编 码,其 中 WHERE 子 句 编 码 为 1 0 0 0 0,GROUP BY 子句编码为0 1 0 0 0,HAVING 子句编码为0 0 1 0 0,ORDER BY 子句编码为0 0 0 1 0,JOIN 相关的子句编码为0 0 0 0 1。每个子句编码之后跟随步骤中所述的数据库列编码。如图 2 所示,示例用于说明 SQL 语句的编码。示例包含 A、B 两个数据表,表 A 中包含 a、b 两个列,表 B 中包含 c、d 两个列。其中,SQL 语句类型为SELECT 语句,其编码为0 0 1 0,其目标列为 A.b和 B.d,因此编码为0 1 0 1;其中包含 JOIN 查询子句,JOIN 的子句编码为0 0 0 0 1,其目标列为A.a 和 B.c,因此在其编码后追加列编码1 0 1 0;其中包含 ORDER BY 查询子句,ORDER BY 的子句编码为0 0 0 1 0,其目标列为 A.a,因此在其编码后追加列编码1 0 0 0。将上述编码拼接,即为该SQL 语句完整的编码。图 2 SQL 语句编码示例Fig.2 Example of SQL-encoding2.3.2 索引选择编码B+树索引具有最左前缀原则。在建立复合索引时,数据库会根据复合索引最左的字段来构建 B+树,而叶子节点存储的是多个字段的数据。查询条件需要从左至右包含复合索引中的列才可以利用索引进行检索。例如,有一个复合索引(a,b,c,d),当使用WHERE 子句在(a),(a,b),(a,b,c),(a,b,c,d)上进行查询时,可利用该索引优化查询效率。但使用(a,c,d)三列作为查询条件时,由于 b 列没有被使用到,便无法使用该索引。同理,将(b),(b,c,d),(c,d)等查询条件同样无法命中该索引,只能建立新的索引对其优化。基于上述特性,ST-IS 采用一种基于字典树的编码方式,每个表的索引集即为一棵字典树。当智能体需要添加一个索引时,首先在已有的树上查询是否已存在该索引。若当前索引不存在或存在当前索引的子集,便建立新的节点。最后,索引选择框架将遍历每个表对应的字典树创建相应的索引集。如图 3 所示,给出一个示例来表示某个表上的索引选择编码。其中,图 3(a)表示在该表上已存在两个索引,分别为(a,b)和(e,d)。如图 3(b)所示,模型执行添加索引(a,b,c)的动作,查询字典树发现已存在索引(a,b),因此只需要在其上添加 c 列即可。对于图 3(c),模型执行添加索引(b)的动作,查询字典树发现没有以列 b 为起点的索引,因此在根节点上添加索引(b)。对于图 3(d),模型发现索引(e,d)对工作负载产生了负优化效果,模型执行删除索引(e,d)的动作。对于图 3(e),模型执行添加索引(a,b)的动作,查询字典树发现树上已存在以列 a、b 为起点的索引,因此不执行任何操作。对于图 3(f),模型执行添加索引(a,b,e)的动作,查询字典树发现不存在以列 a、b、e 作为起点的索引,因此在根节点上添加索引(a,b,e)。图 3 索引集编码示例Fig.3 Example of index benefit evaluation network2023年第49卷第4期无线电通信技术669 2.4 索引效益评估网络索引效益评估网络由多头注意力机制和 GRU模型组成。如图 4 所示,多头注意力机制用于处理SQL 语句编码,GRU 模型用于处理索引选择编码。将多头注意力解码器的输出与 GRU 模型的输出进行联结,经过 Sigmod 函数层输出该索引对于该 SQL语句的优化效果预测。该预测包括 SQL 语句的Cost、Latency 以及当前索引集是否会被命中。在将 SQL 语句编码输入到多头注意力机制前,评估网络会先将 SQL 语句中不同的查询子句类型进行拆分,每个查询子句的编码将被输入到多头注意力机制的一个头中。多头注意力机制的公式如下:Qi=QWiQ,Ki=KWiK,Vi=VWiV,i=1,2,h,(3)headi=Attention(Qi,Ki,Vi),i=1,2,h,(4)Multihead(Q,K,V)=Concact(head1,head2,headh)WO,(5)式中:Q、K、V 分别表示查询、键和值矩阵,WiQ,WiK、WiV、WO分别表示可学习的权重矩阵,h 表示头的数量,Attention 表示缩放点积注意力函数。图 4 索引效益评估网络Fig.4 Index benefit evaluation network在将索引选择编码输入到 GRU 模型前,评估网络会先将每个表对应的字典树进行遍历,将索引集中的每个索引进行 one-hot 编码,如图 5 所示。最后,将编码序列集输入到 GRU 模型中。GRU 处理每个表的索引集编码的计算公式如下:zk=Sigmod(WzXk+Uzhk-1+bz),(6)rk=Sigmod(WrXk+Ur hk-1+br),(7)hk=tanh(Wh Xk+Uh(rkhk-1)+bh),(8)hk=(1-zk)hk-1+zkhk,(9)式中:k 代表数据库中表的编号,用于遍历每棵字典树编码;z 代表更新门,Sigmod()代表激活函数,Wz、Uz、bz用于计算更新门 zt的权重矩阵和偏置向量,X 为索引编码向量,r 代表重置门,Wr、Ur、br用于计算重置门 rt的权重矩阵和偏置向量,h代表候选隐状态,Wh、Uh、bh用于计算候选隐状态 h的权重矩阵和偏置向量,代表逐元素相乘。图 5 字典树 one-hot 编码Fig.5 One-hot encoding of trie2.5 DDPG 索引选择模型传统的强化学习模型存在诸多问题,例如:通常需要大量的训练数据和时间才能学习到一个好的策略;在训练过程中容易出现不稳定的情况;难以直接应用于连续动作空间。为了更好地生成时空数据场景的数据库索引,将 DDPG 算法作为索引选择模型。面对大量的数据库工作负载,每条语句中可能包含大量子查询,DDPG 算法需要处理连续的索引选择动作。同时 DDPG 算法可以通过引入深度学习技术和经验回放缓存来提高学习效率,并且能够在相对较短的时间内学习到一个好的策略。此外,使用经验回放缓存、目标网络和软更新策略等技术,可以改善算法的稳定性,从而提高算法的收敛性和训练效果。DDPG 算法步骤如算法 1 所示。670 Radio Communications TechnologyVol.49 No.4 2023算算法法 1 1 D DD DP PG G 算算法法输输入入:Actor 网络的初始参数,Value-Critic 网络的初始参数 Q。输输出出:最优策略。1.初始化 Actor 网络参数 和 Critic 网络参数 Q;2.初始化目标策略网络参数 和目标动作值函数网络参数 Q,并将其设置为 Q和 的初始值;3.初始化经验回放缓存 D,其最大容量为 N;4.FOR each episode DO5.使用 Actor 网络(st|)选择动作 at;6.执行动作 at,得到新状态 st+1和回报 rt;7.将转移(st,at,rt,st+1)存储到经验值回放缓存 D 中;8.计算目标 Q 值 yt=rt+Q(st+1,(st+1|),Q);9.使用 Critic 网络的均方误差 L(Q)来更新参数 Q:QQ-QQ1NNi=1yi-Q si,ai Q()()210.使用 Actor 网络的梯度 Q(s,a|Q)更新参数 Q:Q(s,a|Q);11.使用软更新策略更新目标动作值函数网络参数 Q和目标策略网络参数:Q rQQ+(1-rQ)Q;12.END FOR 在算法 1 中,设 的参数个数为 n,Q的参数个数为 m,每次训练 k 个 episodes,则算法的整体时间复杂度为 O(k(n+m)。在训练开始时,首先采用 Cost 作为指标进行训练,索引选择模型在数据库上进行添加索引和在某个索引中添加属性操作,用于优化查询效率。然后,采用 Latency 对模型进行微调,算法可在现有索引集的基础上删除索引,用于优化插入和更新操作。3 实验结果与分析3.1 实验设置实验数据集采用滴滴出租车数据集和 TPC-DS标准数据集。滴滴数据集包括出租车轨迹数据、道路信息、订单数据等。TPC-DS 数据集用于评测数据仓库系统的标准 SQL 测试集,它模拟了一个大型跨国零售公司的业务场景,包括多种渠道的销售、库存、促销等数据。TPC-DS 采用星型、雪花型等多维数据模式,它包含 7 张事实表,17 张维度表,平均每张表含有 18 列。TPC-DS 的工作负载包含 99 个SQL 查询,测试流程包括加载数据、单线程处理查询、并行处理查询和数据维护。实验硬件环境为NVIDIA 3080GTX 显卡、具有8 核16 线程的 CPU、64GB 内存。操作系统为 Ubuntu 20.04。实验的软件环境为 Python3.9,强化学习库采用RLib。实验评估中的对比方法分别为基于拉格朗日分解的启发式方法、AutoIndex、NoDBA、Bao24与不添加任何索引的 Default 方法。其中,Bao 通过为数据库查询选择物理算子来达到优化查询的目的,与NoDBA 与 AutoIndex 相同,采用了强化学习方法。3.2 实验评估指标实验评估指标为相对平均代价和相对平均延迟。相对平均代价 RAC的计算公式为:RAC=ni=1Ec(Qi)n,(10)式中:Qi表示第 i 条 SQL 语句,n 为工作负载中 SQL语句的数量。当 RAC 1 时,代表目标索引选择方法的相对平均代价低于未添加索引的相对平均代价。相对平均延迟 RAL的计算公式为:RAL=nni=1El(Qi)。(11)当 RAL 1 时,表示目标索引选择方法的相对平均延迟低于未添加索引的相对平均延迟。3.3 ST-IS 的代价评估如图 6 所示,在出租车数据集上,SP-IS 的相对平均代价比不添加任何索引的 Default 方法低 44.8%,启发式方法比 Default 方法低 20.7%。基于强化学习的 AutoIndex 方法比 Default 方法低 25.6%。基于深度强 化 学 习 的 NoDBA 方 法 比 Default 方 法 低10.7%。图 6 出租车数据集上不同方法的代价评估Fig.6 Cost evaluation of different methods on taxi datasets2023年第49卷第4期无线电通信技术671 主要原因在于,轨迹数据集大多为连续的空间数据,而多头注意力机制和 GRU 都能较好地处理连续 SQL 数据,DDPG 也善于处理连续的索引选择动作。相对于其他方法,ST-IS 更能有效地优化时空数据场景数据库,产生较好的执行计划。对于 Bao,其优化方式为通过修改数据库物理算子,间接影响执行计划。当遇到时空场景大量的连续范围查询时,很容易造成全表扫描。因此,Bao 的优化耗时超过了其优化效果,使其相对平均延迟大于 1。TPC-DS 数据集模拟的是一个大型跨国零售公司,如图 7 所示,虽然其中并没有时空数据工作负载,但 ST-IS 算法在代价评估上依旧优于其他算法,其平均代价低于无索引情况的 65.3%,进而说明ST-IS 方法具有较好的鲁棒性,在其他类型的工作负载上依旧能选择良好的索引集。图 7 TPC-DS 数据集上不同方法的代价评估Fig.7 Cost evaluation of different methods on TPC-DS datasets3.4 ST-IS 的执行时间评估在数据库工作负载执行过程中,不带有查询子句的插入语句代价估计值被设为 0.01,不能全面评估整个工作负载。因此,在实际执行时间上进行了实验,证明 ST-IS 在完整工作负载上的效果。如图 8 所示,在出租车数据集上,相对于启发式方法(ST-IS 的平均相 对 延 迟 比 启 发 式 方 法 低51.7%)、AutoIndex(ST-IS 的平均相对延迟比 Au-toIndex 低 28.2%)、NoDBA(ST-IS 的平均相对延迟比 NoDBA 低 28.2%)和 Bao(ST-IS 的平均相对延迟比 Bao 低 40.0%),ST-IS 框架能生成较好的索引集。其原因主要在于,ST-IS 在训练后期采用真实Latency 作为评价指标,删除冗余的索引以保证数据插入与更新的效率。图 8 出租车数据集上不同方法的执行时间评估Fig.8 Latency evaluation of different methods on taxi datasets如图 9 所示,在 TPC-DS 上,ST-IS 依然具有良好的优化效果。对于启发式方法,它无法适应于动态的工作负载。当工作负载发生变化时,需要及时更新索引以保证优化效果,削弱数据倾斜对优化效果的负面影响。图 9 TPC-DS 数据集上不同方法的执行时间评估Fig.9 Latency evaluation of different methods on TPC-DS datasets4 结束语ST-IS 采用深度强化学习作为索引选择方法,集成了精确高效的 SQL 语句与索引选择编码方法,使索引选择框架能够选出准确而精简的索引集,避免了索引缺失或索引冗余。同时,提出基于多头注意力机制和 GRU 模型混合的索引效率评估网络,能完整地表示 SQL 语句和索引编码的状态,使效益评估更加精准。实验证明,ST-IS 在处理时空数据场景的数据库索引选择问题时,在 Cost 和 Latency 上的表现均优于现有方法。在未来的工作中,将基于 ST-IS 进一步研究更复杂场景的索引选择问题,包括并发查询、分布式数据库优化等。此外,研究外部因素对数据库优化器的影响,如缓存机制、文件系统、CPU 架构等。672 Radio Communications TechnologyVol.49 No.4 2023参 考 文 献1 WANG S Z,CAO J N,YU P S,et al.Deep Learning for Spatio-Temporal Data Mining:A SurveyJ.IEEE Trans-actions on Knowledge and Data Engineering,2022,34(8):3681-3700.2 郑磊.时域交互网络中动态嵌入轨迹预测方法J.重庆理工大学学报(自然科学),2022,36(8):161-170.3 张玉虎,郑皎凌,蒲良,等.卡口数据驱动的车辆轨迹重构方法研究J.重庆理工大学学报(自然科学),2022,36(8):193-202.4 魏盛杰,王鑫,戴劲,等.融合信任圈和移动模式的位置预测框架J.重庆理工大学学报(自然科学),2022,36(8):182-192.5 冯嘉松,杨国平,徐启禄,等.城市道路交通瓶颈识别算法研究J.重庆理工大学学报(自然科学),2022,36(8):171-181.6 GRAEFE G.B-tree Indexes for High Update RatesJ.ACM SIGMOD Record,2006,35(1):39-44.7 CAPRARA A,FISCHETTI M,MAIO D.Exact and Ap-proximate Algorithms for the Index Selection Problem in Physical Database Design J.IEEE Transactions on Knowledge and Data Engineering,1995,7(6):955-967.8 CAPRARA A,GONZLEZ J.A Branch-and-cut Algorithm for a Generalization of the Uncapacitated Facility Location ProblemJ.Top,1996,4(1):135-163.9 DEBABRATA D,NEOKLIS P,ANASTASIA A.CoPhy:A Scalable,Portable,and Interactive Index Advisor for Large Workloads J.Proceedings of the VLDB Endowment,2011,4(6):362-372.10 HIDEAKI K,GEORGE H,ALEXANDERR,et al.CO-RADD:Correlation Aware Database Designer for Material-ized Views and IndexesJ.Proceedings of the VLDB En-dowment,2010,3(1):1103-1113.11 LILLICRAP T P,HUNT J J,PRITZEL A,et al.Continu-ous Control with Deep Reinforcement LearningC Pro-ceedings of 4th International Conference on Learning Rep-resentations.San Juan:ICLR,2016:136-149.12 VASWANI A,SHAZEER N,PARMAR N,et al.Attention is All You NeedC NIPS17:Proceedings of the 31st International Conference on Neural Information Processing Systems.Long Beach:Curran Associates Inc.,2017:6000-6010.13 KYUNGHYUN C,BART M,CAGLAR G,et al.Learning Phrase Representations using RNN EncoderDecoder for Statistical Machine TranslationC P