-
摘要: 现有的索引选择方法存在诸多局限性. 首先, 大多数方法考虑场景较为单一, 不能针对特定数据模态选择合适的索引结构, 进而无法有效应对海量多模态数据; 其次, 现有方法未考虑索引选择时索引构建的代价, 无法有效应对动态的工作负载. 针对上述问题, 提出一种面向多模态数据的智能高效索引选择模型 APE-X DQN (Distributed prioritized experience replay in deep Q-network), 称为 AP-IS (APE-X DQN for index selection). AP-IS 设计了新型索引集编码和 SQL 语句编码方法, 该方法使 AP-IS 在感知多模态数据的同时兼顾索引结构本身的特性, 极大地降低了索引的存储代价. AP-IS 集成新型索引效益评估方法, 在优化强化学习奖励机制的同时, 监控数据库工作负载的执行状态, 保证动态工作负载下 AP-IS 在时间和空间上的优化效果. 在真实多模态数据集上进行大量实验, 验证了 AP-IS 在工作负载的延迟、存储代价和训练效率等方面的性能, 结果均明显优于最新索引选择方法.Abstract: Existing index selection methods have several limitations. Firstly, most methods only consider a single scenario and cannot select an appropriate index structure for a specific data modal, thus being unable to effectively cope with massive multimodal data; Secondly, these methods do not take into consideration the cost of constructing indexes when selecting indexes, making them be unable to effectively handle dynamic workloads. Aiming to cope with these issues, an intelligent and efficient index selection model for multimodal data based on the APE-X DQN (distributed prioritized experience replay in deep Q-network) model, called AP-IS (APE-X DQN for index selection). AP-IS designs a new index set encoding and a new SQL statement encoding method, allowing AP-IS to perceive multimodal data while considering the characteristics of the index structure itself, significantly reducing the storage cost of indexes. AP-IS integrates a novel index benefit evaluation method. While optimizing the reward mechanism of reinforcement learning, it can monitor the execution state of database workloads, guaranteeing the effect of time and space optimization of AP-IS under dynamic workloads. Extensive experiments are conducted on real multimodal datasets to evaluate the performance of AP-IS under workloads including latency, storage cost, training efficiency, and the results of AP-IS significantly outperforms the state-of-the-art index selection methods.
-
Key words:
- Intelligent database /
- multimodal data /
- index selection /
- reinforcement learning /
- execution plan
-
在当今的信息社会, 各行各业数据量呈现爆炸式增长, 数据的模态也越来越多样化[1], 如非结构化文本、时序数据、半结构化JSON、空间数据等. 多模态数据库[2]能够存储、查询及管理当前多种行业相关的多模态数据, 然而, 多模态数据库尚未普及, 大多数场景和需求仍使用成熟而稳定的关系型数据库存储多模态数据. 当采用关系型数据库存储多模态数据时, 往往由于跨模态数据关联, 引发查询复杂性过高、针对多模态数据的索引优化等问题, 导致查询和管理性能较差. 因此, 如何高效地查询和管理多模态数据成为一个重要研究问题.
索引是一类用于提高数据库查询效率的数据结构, 良好执行计划的生成和选择很大程度上取决于数据表是否存在合适的索引. 数据库索引是提高多模态数据查询效率的重要手段之一, 它可以根据查询条件快速访问数据库表中的特定信息. 一个索引可以在一个数据表的一个字段或多个字段上创建, 每个表上可以同时存在多个索引. 同时, 存在多种基于不同方法实现的索引类型. 例如, 在PostgreSQL数据库中共存在6种索引类型, 包括B-tree、Hash、GiST (Generalized search tree)、SP-GiST (Space-partitioned generalized search tree)、GIN (Generalized inverted index)和BRIN (Block range index).
在没有索引的情况下, 数据库必须执行全表扫描来查找特定的数据. 这意味着数据库将查看表中的每条数据, 直到找到所需的数据, 导致执行查询、排序、聚合等操作时效率极低, 消耗大量的时间和内存资源. 在建立索引后(以B + 树索引为例), 数据库通过维护一个多级树状结构, 其中每个节点包含了数据项的键值和指向数据存储位置的指针, 使得数据的查找、插入和删除操作能够在对数时间复杂度内完成. 然而, 索引本身也需要占用硬盘空间, 同时需要在数据更新(插入、删除、修改)时进行维护, 消耗一定时间和资源. 因此, 创建索引需要综合考虑数据模态、存储开销、工作负载变化、数据库中的数据分布等因素. 不同的索引类型适用于不同的应用场景和数据模态. 如图1所示, 在时序数据模态下, 采用BRIN索引在多个方面的性能评估均优于B-tree索引.
图 1 时序数据模态下BRIN索引和B-tree索引的性能对比Fig. 1 Performance comparison of BRIN index and B-tree index in temporal data modal创建索引在优化查询效率的同时, 也会造成一些负面影响, 例如: 1)索引会大量占用磁盘空间; 2)数据库中数据更新的同时, 需要对索引进行维护, 影响数据的更新效率; 3)创建索引的过程需要花费较长时间, 且占用大量磁盘的读写资源. 因此, 需要在一定的索引存储空间约束下, 根据具体的需求和数据特征来选择合适的索引类型和字段组合, 使数据库中工作负载的执行效率最高. 此类问题被定义为索引选择问题[3−4], 其难点还体现在: 1) PostgreSQL中的B-tree、GiST、GIN和BRIN索引支持将几个字段排列起来形成一个索引, 被称为复合索引. 其中, 最常用的B-tree复合索引遵循最左前缀原则, 即查询条件需从左到右进行匹配, 否则会造成索引失效. 复合索引具有减少磁盘开销、防止回表、效率高等优势, 但大大增加了索引选择问题的复杂度. 2)数据库中的工作负载是不断变化的[5], 包括数据的更新以及业务模式的变化, 例如某索引字段从大量查询的工作负载转变为大量插入的工作负载, 这会使执行效率大大降低. 在这种情况下需要对索引进行适当更新来维持索引的优化效果. 3) PostgreSQL数据库默认的索引类型为B-tree, 其无法适应多模态数据的应用场景. 若能为特定的数据字段选择合适的索引类型, 可以大幅度增加索引的效率, 并减少磁盘占用, 但会增加索引选择问题的复杂性.
当前, 学者开始研究数据库索引选择方法, 通过强化学习算法[6−9], 提高索引质量进而优化数据库效率. 然而, 现有的索引选择方法存在诸多局限性, 如当前流行的AutoIndex方法[10] 具有以下局限性: 该方法未根据不同模态数据选择不同的索引类型, 无法使索引优化效果达到最优; 该方法未考虑索引结构本身的特性进行复合索引选择, 可能造成索引失效. 在当前大数据背景下, 索引选择方法更需要适应海量的多模态数据, 选择合适的索引结构, 适应索引结构特性, 使数据库提高运行效率, 减少存储代价[11].
针对现有方法存在的不足, 本文提出一种面向多模态数据的索引选择框架, 可以显著提高数据库效率并降低索引规模. 本文的主要贡献包括:
1)针对现有方法无法适应动态工作负载的问题, 提出一种基于APE-X DQN模型[12]的索引选择框架, 通过异步更新和优先经验回放机制, 优化多模态数据场景下智能体的探索策略和与环境交互能力. 异步更新机制可以显著提高训练效率, 使得算法更快地学习到优秀的策略.
2)针对当前方法不能适应多模态数据场景的问题, 提出一种新型的SQL语句编码方法, 从中提取可索引列并感知其数据模态, 选择最优的索引类型, 避免索引缺失; 针对已有方法无法创建复合索引的问题, 提出一种新型的索引集编码方法, 能够精确编码多种属性的索引集, 适应联合索引特性, 能有效避免索引冗余.
3)为进一步提升推荐索引质量、更加直观地证明所提方法的性能优势, 提出一种索引效益评估方法, 综合考虑索引体积、索引创建时间、索引命中率等性能指标, 使AP-IS在动态的工作负载下, 适时更新索引集, 保持索引的优化效果.
4)针对当前模型训练效率较低的问题, 提出一种混合训练机制: 先通过建立虚拟索引, 利用代价估计值进行训练; 再建立真实索引, 利用执行时间训练. 通过该方法提高训练效率, 缩短收敛时间.
5)在真实的多模态数据集、TPC-H[13]以及TPC-DS数据集[14] 上进行大量实验, 证明AP-IS相较于其他方法能为多模态数据选择更合适的索引集.
本文第1节介绍当前代表性索引选择技术, 包括传统方法和基于学习的方法, 总结各种方法的优点以及存在的局限性; 第2节对多种索引结构进行概述, 介绍索引结构与多模态数据的适用关系; 第3节对AP-IS进行详细介绍, 包括面向多模态数据的索引编码方法和SQL语句编码方法、索引效益评估方法以及基于APE-X DQN的索引选择模型; 第4节采用多种方法进行实验并分析实验结果; 第5节总结全文并展望未来工作.
1. 相关工作
传统索引选择技术一般采用贪心、动态规划、暴力枚举等方法, 最早的研究可追溯到1970年. 近年来随着机器学习技术的发展, 一些基于学习的索引选择方法[15−18]被提出, 索引选择方法相关工作总结如表1所示. 本节将对上述方法进行对比和分析.
表 1 索引选择方法对比分析Table 1 Comparison analysis of index selection methods方法策略 方法名称 优点 不足 传统的数据库索引选择方法 Drop[19] 通过启发式方法, 针对工作负载创建索引, 减轻DBA的工作负担 没有充分利用DBA经验, 无法适应动态的工作负载, 无法创建复合索引 AutoAdmin[20] 每轮迭代通过增加索引宽度支持多列索引选择 无法处理动态变化的工作负载, 加重DBA的负担 DB2Advis[21] 采用随机替换法适应动态的工作负载 随机的索引替换造成大量磁盘开销, 索引方案的不断变化影响系统的稳定性 基于学习的
数据库索引
选择方法NoDBA[22] 首次采用深度强化学习进行数据库索引自动选择, 降低工作负载的执行延迟 无法适应动态的工作负载, 也无法创建复合索引 ITLCS[23] 将遗传算法和强化学习相结合, 能够适应动态的工作负载和表结构较复杂的场景 依赖遗传算法索引选择策略, 未将基于学习的方法应用到问题的求解过程中 AutoIndex[10] 利用蒙特卡罗树搜索根据候选索引优化现有索引, 支持复合索引和动态的工作负载 无法适应多模态数据场景, 不支持多种索引类型的选择 1.1 传统的数据库索引选择方法
文献 [19] 提出一种下降启发式的索引选择方法. 首先, 初始化一个包含所有潜在候选单列索引的索引集$ S_{|I|} $, 之后经过多个下降阶段, 每个阶段均将每一个候选索引从当前索引集中移除. 在第$ n $个阶段剩余的索引候选者$ w \in S_n $在给定工作负载下的成本可表示为$ C(S_n / \{w\}) $, 成本最低的候选者将被永久移除, 不进入下一阶段. 重复上述步骤直至成本不再降低. 该方法能在一定程度上优化给定工作负载的执行效率, 但无法适应动态的工作负载, 也无法选择复合索引. Chaudhuri等[15]提出一种针对Microsoft SQL Server数据库的自动索引选择方法AutoAdmin. 该方法首先从查询日志中选择一些频繁的查询作为查询集合, 并从中提取所有可索引的字段; 其次使用枚举方法计算每种索引组合的优化效果; 最后, 在优化效果较好的索引集上采用贪心算法添加可索引列, 直到索引数量达到阈值. 该方法通过每次迭代时增加索引宽度支持了多列索引, 但工作负载发生变化时, 需要数据库管理员(Database administrator, DBA)重新分析可索引列, 并重复上述步骤, 否则无法保持索引集的优化效果. Valentin等[16]提出一种针对IBM DB2数据库的索引优化方法DB2Advis. 该方法首先列举工作负载中每个查询$ q $的所有可索引字段作为假设索引, 其中包括单列索引和复合索引; 其次, 为每个查询$ q $选择最优索引, 并将其添加到候选索引集$ I $中; 最后, 递减排列$ I $中候选索引的空间收益比, 例如, 索引$ w_1 $的空间收益大于$ w_2 $, 则将$ w_1 $与$ w_2 $合并. 在存储预算允许的情况下, 将这些索引添加到最终索引配置中. 此外, DB2Advis会随机交换候选索引集与最终索引配置中的索引, 避免由于存储约束而错过最佳索引配置. 该方法采用随机替换的方法, 在一定程度上可以适应动态的工作负载, 但索引方案的不断变化会严重影响数据库管理系统(Database management system, DBMS)的稳定性, 造成大量磁盘开销.
上述传统的数据库索引选择方法存在一些共性问题: 1)未考虑多模态数据本身的特性去选择合适的索引结构; 2)采用枚举方法列举所有可索引字段, 搜索范围较大, 对于数据量较大的工作负载进行索引选择的时间和磁盘开销过大; 3)无法从历史的索引选择策略中学习经验, 从而无法良好应对动态的工作负载. 针对上述问题, 学者们提出基于学习的数据库索引选择方法.
1.2 基于学习的数据库索引选择方法
Sharma等[22]首次采用深度强化学习(Deep reinforcement learning, DRL)[24]中的深度Q网络(Deep Q-network, DQN)[25]进行数据库索引自动选择, 通过动作、奖励函数、智能体、神经网络的输入等DRL组件与数据库索引选择的关联进行介绍. 该方法将每条查询的执行代价作为优化目标, 设置最大的索引数量$ k=3 $, 并在TPC-H数据集的一个表上进行了实验. 该研究无法选择复合索引, 也无法适应动态的工作负载.
Pedrozo等[23]提出一种基于学习分类器系统的索引选择方法ITLCS (Index tuning with learning classifier system), 该方法结合了遗传算法[26]和强化学习, 建立了一个基于规则的索引选择机制. 首先, ITLCS通过监督学习方法训练多个分类器, 每个分类器被遗传算法视为一个单独的个体, 分类器的输入为查询语句, 输出为索引选择动作; 其次, 对于每个查询, 选择满足条件的分类器在环境中相互竞争, 由优先级最高的分类器采取索引选择动作; 最后, 根据数据库性能变化, 对所选分类器进行奖惩, 采用遗传算法淘汰较差的分类器, 生成后代分类器. ITLCS能适应动态的工作负载, 但依赖遗传算法索引选择策略, 未将基于学习的方法深入问题的求解过程中. 该方法在面对海量多模态数据且表结构较复杂的数据库场景时, 很难得到较优策略.
Zhou等[10]提出一个增量索引管理系统AutoIndex. 首先, AutoIndex采集工作负载性能, 若存在索引导致数据库性能下降, 则发出索引更新请求; 其次, AutoIndex集成了一种增量索引管理方法, 该方法将工作负载与提取的查询模板相匹配, 从模板中选择候选索引, 并利用蒙特卡罗树搜索(Monte carlo tree search, MCTS)[27]根据候选索引优化现有索引. 在MCTS中, 为了有效估计不同索引的收益, AutoIndex应用了一个索引收益估计模型, 采用深度回归模型来估计索引集的收益. 该方法具有选择复合索引的能力, 且支持动态的工作负载, 但仍无法适应多模态数据场景, 不支持多种索引类型的选择.
2. 背景知识及问题描述
2.1 多模态数据与索引类型选择
PostgreSQL数据库提供了6种索引类型, 每一种索引类型都采用了不同的算法以适应不同的数据模态或查询场景. CREATE INDEX命令默认用于创建B-tree索引, 这使得以往的索引选择方法无法达到最佳的优化效果. 表2总结了不同索引类型在多模态数据场景的适用性和局限性.
表 2 不同索引类型在多模态数据场景的适用性和局限性Table 2 Applicability and limitations of different index types in multimodal data scenarios索引类型 适用数据模态及场景 不适用数据模态及场景 B-tree 整型、浮点型的等值、范围查询、排序等 文本类型的全文搜索, JSON等半结构化数据 Hash 等值查询 数据分布不均匀或更新频繁的场景 GiST 空间数据、文本数据的全文搜索、模糊查询 精确匹配、排序、去重等场景 SP-GiST 空间数据、文本数据的全文搜索 去重、排序, 不支持复合索引 GIN JSON等半结构化数据更新频繁的场景 大型二进制对象数据, 精确匹配等场景 BRIN 时序数据, 顺序访问模式 随机访问、精确匹配等场景 B-tree索引是PostgreSQL中最常用的索引类型之一, 它是一种平衡的树状数据结构, 由一系列的节点组成, 每个节点可以包含多个键值对. B-tree索引可用于等值查找、范围查询、排序等不同的场景, 在整型、浮点型数据上能取得较好的优化效果. 但它在面对文本类型、JSON、几何类型、时序数据等数据模态时, 并非最佳的选择.
Hash索引用于快速查找和匹配具有固定长度的键值对, 它使用散列函数将键值对中的键转换成一个固定长度的散列值, 并将键值映射到索引存储结构的槽位或存储桶. Hash索引适用于等值查询、完全匹配查询、唯一性约束及内存密集型工作负载的场景, 但它不支持范围查询、模糊查询、排序操作及多列查询. 此外, Hash索引在数据分布不均匀或更新频繁的场景有一定的局限性. 分布不均匀的数据会产生大量Hash冲突, 导致额外的比较操作和链式查找, 降低查询效率; 更新频繁的数据会导致Hash表的重建或重散列, 影响数据库性能.
GiST是一种基于多叉树的通用索引结构, 它的每个节点包含一个或多个索引项, 每个索引项由一个谓词和一个指针组成. 通过定义适当的分割函数和谓词函数, GiST索引特别适用于处理空间数据, 如几何对象、地理数据等. 例如, 可以使用GiST索引进行高效的地理位置范围查询、距离查询和交叉查询等操作. 同理, 它还支持文本类型数据的全文搜索和模糊查询等场景. 但当GiST索引面对需要精确匹配或排序的查询时, 其效率可能不如B-tree索引, 因为GiST索引的数据结构不保证顺序, 而且可能存在重叠的范围.
SP-GiST索引是对GiST索引的改进和扩展, 其中包含了四叉树(Quad-tree)、K维树(K-d tree)和基数树(Radix tree)三种不同的索引结构. SP-GiST索引将值域递归地划分为不相交的子域, 优化了索引性能, 减少了I/O操作和索引膨胀. 但SP-GiST不支持复合索引, 不能用于排序和唯一约束.
GIN索引采用了倒排列表(Inverted list)数据结构, 对于每个索引键值, 倒排列表保存了所有包含该键值的文档或数据行的引用. 它同GiST均支持全文检索, GIN索引的精度和查询效率高于GiST, 但GiST索引在数据更新频繁的场景下整体效率优于GIN索引. 此外, GIN索引在面对数组、JSON等多值类型数据时, 可以有效地减少存储空间和提高查询效率.
BRIN索引将数据按照某种方式分成多个数据块. 每个数据块包含一连串的数据行, 通常是物理存储上相邻的数据. 分块的目的是将数据行按照物理顺序组织, 以提高索引的压缩和查询性能. BRIN索引适用于具有顺序访问模式的数据, 例如时间序列数据或有序的范围数据. 它通过数据块的范围信息和摘要来实现高效的索引访问和查询优化. 然而, 对于具有随机访问模式或需要精确匹配的查询, BRIN索引不是最佳选择.
2.2 深度强化学习
在深度强化学习中, 智能体从环境中观察到状态(State), 并通过选择动作(Action)来影响环境. 环境根据智能体的动作和当前状态, 给出奖励(Reward)信号, 并转移到下一个状态, 从而学习到一个优秀的策略. 面向多模态数据的索引选择问题可以用深度强化学习来解决. 为了实现这一目标, 将上述要素与深度强化学习相结合, 给出如下定义:
定义1 (环境). 环境可视为一个外部系统, 可基于智能体作出的决策给出相应的反馈. 在索引选择问题中可将DBMS视为环境, 用于智能体获取工作负载执行的代价估计值以及延迟.
定义2 (动作空间). 动作空间$ A $是智能体基于当前观测状态$ s_t $能够做出的索引选择动作$ a $集合, 例如, 在表$ L $的$ (p,\; q) $字段创建B-tree索引. 其中$ s_t \in S,\; t $为观测时间.
定义3 (状态). 状态$ S $是智能体对DBMS中的关键信息进行观测后获得的状态, 在索引选择问题中, 状态包括当前工作负载$ W $、索引集$ ISet $、以及$ W $的执行时间等.
定义4 (奖励). 奖励$ r $是环境对智能体基于当前观测状态$ s_t $选择相应动作$ a_t $后给出的反馈, 在AP-IS中, 由索引效益评估方法根据DBMS的状态给出.
定义5 (智能体). 智能体是DRL的算法模型. 智能体主要负责观测当前状态$ s_t $从索引选择动作空间$ A $中选择某个动作$ a \in A $.
定义6 (多模态数据索引选择问题). 在有限的存储空间下, 为基于多模态数据的工作负载$ W $选择适当的索引集合$ ISet $, 使得$ W $有最好的执行效率, 即为多模态数据索引选择问题.
通过上述定义, 将索引选择问题与深度强化方法相结合, 使索引选择方法具有自学习能力和泛化能力, 能从经验中学习并改进索引选择策略, 逐步提升执行工作负载的性能.
3. AP-IS的架构和关键技术
3.1 AP-IS的整体架构和工作机制
如图2所示, AP-IS索引选择模型框架包括三个主要组成部分: 1)基于AP-IS索引选择模型, 智能体根据当前工作负载状态、经验以及现有索引集, 执行添加索引或删除索引的动作, 进一步优化工作负载的执行效率. 2)编码方法, 包括对SQL语句和对索引集的编码. 其中, SQL语句编码包含SQL语句类型、查询谓词所对应的数据字段以及该字段对应的数据模态, 为APE-X DQN模型提供准确且高效的状态表示; 索引集编码包括数据库中每个索引的类型以及所包含字段的集合. 3)索引效益评估方法, 将工作负载的实际执行延迟、代价估计、磁盘占用、索引创建时间、索引命中率等作为评判指标, 判断索引集在多种方面的优化效果, 为APE-X DQN提供奖励.
APE-X DQN包含两部分: 执行者(Actor)和学习者(Learner), 执行者在环境中执行动作并生成经验, 而学习者则从执行者生成的经验中学习; 执行者和学习者的定义如下所示:
定义7 (执行者). 执行者使用当前的策略$ \pi (a|s;\theta) $进行决策, 其中$ \theta $是当前策略的参数. 执行者在环境中执行动作$ a $, 观察到新的状态$ s' $和奖励$ r $, 然后将经验$ (s,\; a,\; r,\; s') $存储到经验回放缓冲区.
定义8 (学习者). 学习者的主要职责是学习和更新策略. 学习者从优先级经验回放缓冲区中取出存储的经验$ (s,\; a,\; r,\; s') $, 然后使用这些经验来更新网络的参数$ \theta $. 学习者通过优化损失函数来进行学习, 定期将更新的策略参数发送给执行者, 使执行者可以根据最新的策略$ \theta' $进行决策.
如图3所示, AP-IS模型的工作机制分为训练阶段和运行阶段. 在训练阶段, 基于数据库中已存在的数据及历史的工作负载, 首先, AP-IS创建多个执行者线程, 每个线程独立地与环境进行交互, 执行动作并观察环境的反馈; 其次, 创建一个共享的经验回放缓冲区, 智能体线程将其收集到的经验存储到缓冲区中, 以实现多智能体之间的经验共享; 最后, 周期性地创建学习者线程, 从经验回放缓冲区中采样一批经验样本进行策略网络的更新和优化. 在全局学习过程中, 需要将学习得到的参数传播给每个智能体线程, 以更新它们的策略网络. 在训练阶段, AP-IS的奖励由如下参数共同决定: 1)创建虚拟索引后工作负载的代价估计值; 2)创建真实索引后工作负载的代价估计值; 3)工作负载实际执行延迟; 4)索引占用的存储空间; 5)创建索引所消耗的时间; 6)索引的命中率. 索引效益评估方法会根据当前数据库环境、索引选择情况进行训练, 拟合索引的奖励值.
在训练阶段前期, AP-IS模型首先创建虚拟索引, 将代价估计值作为训练的指标之一; 在后续的训练中, 创建真实索引并将实际的SQL执行延迟和索引体积等参数作为训练指标, 该方法可以在很大程度上提高训练速度, 防止执行者在训练前期盲目创建大量无用索引.
在运行阶段, AP-IS模型继续收集数据库中的工作负载、执行代价、索引命中率等信息, 更新智能体的参数及经验评估当前的索引集是否需要被更新. 当动态的工作负载的变化导致数据库效率下降时, AP-IS会周期性地更新索引配置.
3.2 AP-IS的编码方法
AP-IS的编码方法涵盖了SQL语句编码和索引集编码两个方面. 通过丰富的SQL语句编码, AP-IS能够更好地发现候选索引、感知索引选择与多模态工作负载的关联, 选择最优的索引类型, 避免索引缺失. 同时, 高效的索引集编码方法可以适应联合索引的特性, 精确编码多种属性的索引集, 有效避免索引冗余.
3.2.1 SQL语句编码
SQL语句编码包含5个重要组成部分:
1) SQL语句类型编码. 索引主要影响SQL语句中的数据查询语言和数据操纵语言的执行效率, 包括INSERT、DELETE、UPDATE、SELECT子句类型. 因此, AP-IS采用四位one-hot编码表示这4类SQL语句, 例如, INSERT语句的编码为{0 1 0 0}.
2)子句类型编码. 一个SQL语句中可包含多种子句类型, 包括JOIN、ORDER BY、HAVING等. 在众多子句对应的字段上建立索引能提高相应操作的执行效率. 因此, AP-IS采用多组one-hot编码表示SQL中的子句类型.
3)谓词类型编码. 查询语句分为众多类型, 包括比较谓词、范围谓词、逻辑谓词等, 这些类型可通过SQL中的众多谓词体现. AP-IS采用多组one-hot编码对查询中的谓词进行编码, 为索引类型选择提供依据.
4)可索引字段编码. SQL中谓词对应的数据字段为可索引字段. AP-IS对数据库中所有的字段进行multi-hot编码, 查询中涉及到目标字段的编码为1, 未涉及的字段为0.
5)字段类型编码. AP-IS将PostgreSQL中的多种数据类型进行one-hot编码, 使AP-IS支持多模态数据的索引选择.
例1 (SQL语句编码举例). AP-IS的SQL树状编码方法如图4所示, 树的根节点为SQL语句类型编码, 语句中包含的JOIN、ORDER BY、WHERE查询子句被分为多棵子树, 子树中可包含LIKE、AND等谓词作为中间节点, 谓词所对应的字段以及其数据模态可视为叶子结点. 该SQL查询编码树将作为Tree-LSTM (Tree-long short-term memory)的输入.
AP-IS利用Tree-LSTM[28]将上述SQL查询编码树进行状态表示, 具体方法将在第3.3节中详细介绍.
3.2.2 索引集编码
例2 (索引集编码举例). 索引集编码方法原则为: 已知一个包含字段(a, b, c)的联合索引, 当查询条件使用WHERE子句并涵盖(a, b, c)、(a, b)或(a)字段时, 可以利用该索引提升执行效率. 然而, 当查询条件只包含(b, c)时, 由于缺少最左侧的字段(a), 无法采用该联合索引优化查询. 同样地, 若查询条件为(c)或(a, c), 也无法命中该索引. 上述过程称为索引的最左优先原则.
B-tree索引具有最左前缀原则, 在建立复合索引时, 数据库会根据复合索引最左的字段来构建B-tree, 叶子节点存储其余字段数据. 因此, 查询条件需要尽量从左至右包含复合索引中的字段以优化执行计划. 基于前缀树编码的索引添加操作如算法1所示.
算法1. 基于前缀树编码的索引添加算法
输入. 现有索引集编码树根节点$ root $, 待创建索引$ Index $.
输出. 添加索引后的编码树根节点$ root' $.
1) $ cur\_node = root; $
2) for $ I $ in $ Index $ do
3) if $ I.type\;{in}\;cur\_node\;\rightarrow\;child.type\;{and} $
$ I.field\; {in}\; cur\_node\;\rightarrow\;child.field $ then
4) $ cur\_node\;=\;cur\_node\;\rightarrow next; $
5) else
6) $ new\_node\;=\;Create(I); $
7) $ cur\_node\;\rightarrow\;next\;=\;new\_node; $
8) end if
9) end for
10) $ {return}\;root' $
算法1的输入为现有索引集编码树根节点$ root $, 待创建索引$ Index $. 首先将前缀树的根节点设为当前节点$ cur\_node $, 并遍历待创建索引的每个字段(算法1 ~ 2行); 若当前节点的子节点与待创建索引的字段名称及索引类型均相同, 则将该节点作为当前节点(算法3 ~ 4行); 若字段名称或索引类型不同, 则在前缀树上创建一个新的节点, 节点编码为待创建索引字段名及索引类型(算法5 ~ 9行); 最后, 返回完成索引创建的前缀树根节点(算法第10行).
如图5所示, 某数据表上已存在字段(a, b)、(a, e)上的联合B-tree索引和字段(b, e)、(b, d)上的联合GIN索引.
案例 1: 当智能体做出在(a, b, c)上添加B-tree索引的动作, 查询前缀树发现已存在(a, b)上的B-tree索引, 因此删除索引(a, b), 并创建索引(a, b, c);
案例 2: 智能体做出在字段(a, b)上添加B-tree索引的动作, 但索引前缀树中已包含(a, b, c)上的B-tree索引, 因此不创建任何索引;
案例 3: 智能体做出在字段(b)上创建Hash索引的动作, 由于没有以(b)为前缀的Hash索引, 因此在该字段创建Hash索引;
案例 4: 智能体做出删除字段(b, d)上GIN索引的动作, 则删除索引并在前缀树上删除节点d (GIN)即可.
3.3 AP-IS的状态表示模型
准确的状态表示能够提升AP-IS的性能. 因此, 采用图4中的SQL编码, AP-IS设计了一种基于Tree-LSTM的状态表示模型. 树状结构的编码具有良好的灵活性和扩展性, 可以处理不确定数量的子节点, 并捕捉树的上下文信息, 能有效处理复杂的SQL编码; 明确的层级关系能有效避免信息丢失或歧义, 为AP-IS提供准确高效的索引选择依据.
图6为Tree-LSTM的结构图, Tree-LSTM通过递归计算子节点的隐藏状态来计算当前节点的隐藏状态. 每个节点的隐藏状态是基于其子节点的隐藏状态和当前节点的输入表示计算得出的, 该结构有助于AP-IS捕捉到树结构中的上下文信息, 感知多模态数据特征. 不同于LSTM (Long short-term memory)[29]中的时间步, Tree-LSTM中的每个节点可能包含不同数量的子节点, 且共享相同的参数, 这样可以有效地处理SQL编码树的可变结构. Tree-LSTM中的关键设计在于计算节点的隐藏状态和细胞状态的递归更新规则. 给定一个树节点的输入表示和其子节点的隐藏状态和细胞状态, 可以使用以下公式计算节点的新的隐藏状态和细胞状态, 式(1) ~ (4)分别表示输入门、遗忘门、细胞状态以及细胞状态更新状态.
$$ \begin{aligned} i_j = \sigma(W^{(i)}x_j + U^{(i)}h_1 +\cdots+ U^{(i)}h_n + b^{(i)}) \end{aligned} $$ (1) $$ \begin{aligned} f_{jk} = \sigma(W^{(f)}x_j + U^{(f)}h_k +b^{(f)}) \end{aligned} $$ (2) $$ \begin{aligned} o_j = \sigma(W^{(o)}x_j + U^{(o)}h_1 +\cdots+ U^{(o)}h_k + b^{(o)}) \end{aligned} $$ (3) $$ \begin{aligned} u_j = \mathrm{tanh}(W^{(u)}x_j + U^{(u)}h_1 +\cdots+ U^{(u)}h_n + b^{(u)}) \end{aligned} $$ (4) $$ \begin{aligned} c_j = \sum\limits_{k = 1}^n {f_{jk} \odot c_k + i_j \odot u_j} \end{aligned} $$ (5) $$ \begin{aligned} h_j = o_{j} \odot \mathrm{tanh}(c_j) \end{aligned} $$ (6) 其中, $ i_j $表示节点$ j $的输入门向量; $ x_j $是节点$ j $的输入表示; $ h_1,\ h_2,\ \cdots \ ,\ h_n $是节点$ j $的子节点的隐藏状态向量; $ W^{(\cdot)},\; U^{(\cdot)},\; b^{(\cdot)} $为可学习参数; $ f_{jk} $是节点$ j $的遗忘门向量, 用于控制是否保留子节点$ k $的记忆; $ o_j $是节点$ j $的输出门向量; $ u_j $表示节点$ j $的细胞状态向量; $ c_j $是节点$ j $的新细胞状态; $ c_k $是节点$ j $的子节点$ k $的细胞状态; $ h_j $是隐藏状态; $\odot $为点乘运算; $ \sigma(\cdot) $和tanh$ (\cdot) $分别表示sigmoid函数和双曲正切函数.
当进行索引选择动作时, AP-IS将Tree-LSTM状态表示的输出作为6种索引类型选择的依据.
根据SQL的状态表示, 将工作负载的实际执行延迟或代价估计值作为训练指标, 采用softmax分类器预测最优的索引结构. Tree-LSTM的隐藏状态$ h_j $作为该分类器的输入, 如式(7)所示:
$$ \begin{aligned} \hat{p}_\theta(T|WL_j) = \mathrm{softmax}(W^{(m)}\times h_j + b^{(m)}) \end{aligned} $$ (7) 其中, $ \hat{p}_\theta(T|WL_j) $表示在工作负载$ WL_j $下选择索引类型$ T $的预测概率分布; softmax$ (\cdot) $为softmax分类器; $ \theta $为模型参数; $ W^{(m)} $和$ b^{(m)} $为softmax层的权重和偏置. 然后, 选择具有最高预测概率的索引类型为索引选择提供依据, 如式(8)所示:
$$ \begin{aligned} \hat{T}_j ={\mathrm{arg}} \mathop{\mathrm{max}}\limits_{T} \hat{p}_\theta(T|WL_j) \end{aligned} $$ (8) 其中, $ \hat{T}_j $表示具有最高预测概率的索引类型, 即为AP-IS最终选择的索引类型, $ \mathrm{arg\ max} $函数用于提取具有最高预测概率的索引类型$ T $. 该softmax层的损失函数记为$ J(\theta) $, 其定义如式(9)所示, 用于更新模型参数$ \theta $. 该损失函数采用每轮训练的实际执行延迟作为依据, 执行延迟越长, 损失值越大.
$$ \begin{aligned} J(\theta) = \frac{{1}}{m}\sum\limits_{k = 1}^m \sqrt{\frac{{Latency(T^{(k)}|WL^{(k)})-Latency_{\min}}}{Latency_{\max}-Latency_{\min}}} \end{aligned} $$ (9) 其中, $ m $表示工作负载的SQL语句数量, $ Latency (T^{(k)}| WL^{(k)}) $表示工作负载$ WL $中语句$ k $在选择索引类型 $ T $ 时的实际执行延迟, $ Latency\mathrm{_{max}} $和$ Latency\mathrm{_{min}} $分别表示在训练中的最大和最小执行延迟.
3.4 基于APE-X DQN的索引选择方法
APE-X DQN采用异步更新机制来改进DQN, 如图7所示, 允许多个执行者同时进行经验采集. 执行者拥有各自的探索策略和与环境交互的能力, 将经验存储到经验回放缓冲区中. 异步更新机制可以显著地提高训练效率, 使得算法更快地学习到优秀的策略. APE-X DQN由智能体、经验回放缓冲区、学习者和全局参数服务器构成.
执行者的目标网络状态$ s $作为输入, 以$ Q $值作为输出. 其中, $ s $由SQL的状态表示模型和索引集编码组成, $ Q $值用于确定需要执行的索引选择动作$ a $. 在索引选择动作执行后, 智能体不会立即得到奖励, 而需要经过多条SQL语句执行后, 由索引效益评估方法输出奖励值, 在此期间, 智能体不会做出索引选择动作. 计算$ Q $值的公式如下所示:
$$ \begin{aligned} Q(s,\; a) = E(s(q_1,\; \cdots,\; q_k))+\gamma\; \mathrm{max}\{Q(s',\; a')\} \end{aligned} $$ (10) $ Q(s,\; a) $表示在 $ s $ 状态下选择动作 $ a $ 的 $ Q $ 值; $ E(\cdot) $为索引效益评估方法的输出值; $ q_1,\; \cdots ,\; q_k $为智能体完成动作后执行 $ k $ 条SQL语句; $ \gamma $为折扣因子, 表示当前状态对未来奖励的影响程度, $ \gamma \in [0,\; 1] $, $ \gamma $越接近1, 智能体越重视未来奖励; $ \max\{Q(s',\; a')\} $表示在新状态 $ s' $ 下所有可能动作的$ Q $ 值中的最大值.
APE-X DQN采用损失函数衡量DQN预测的$ Q $值和目标$ Q $值之间的差异. AP-IS的工作机制分为训练阶段和运行阶段, 两个阶段的损失函数分别定义为:
$$ \begin{split} L_{train} =\;& (Q(s,\; a)-(E(s(q_1,\; \cdots,\; q_k))\;+\\ &\gamma\; \mathrm{max}\{Q(s',\; a')\}))^2 \end{split} $$ (11) $$ \begin{aligned}L_{run}=\left(Q(s,\; a)-\frac{1}{w/k}\sum\limits_{i=1}^{w/k}E(s'_i(q_1,\; \cdots,\; q_k))\right)^2\end{aligned} $$ (12) 其中, $ L_{train} $表示训练阶段中$ s $状态下选择动作$ a $的损失值; $ L_{run} $表示运行阶段的损失值; $ w $为完成一次索引选择动作后执行的SQL语句的条数; $ s'_i $为每执行$ k $条SQL语句后的状态.
APE-X DQN并行开启多个执行者线程, 并在各自的环境中进行探索, 生成经验(状态、动作、奖励), 经验被发送到一个中央经验回放缓冲区, 按照其优先级进行排序和存储. 一个单独的学习者从经验回放缓冲区中按优先级抽样, 进行学习并更新神经网络参数. 更新后的神经网络参数被发送到所有的执行者, 用于生成新的经验. 在APE-X DQN中, 学习者和执行者是分开的. 执行者在环境中执行操作并收集经验, 将这些经验发送到中央经验回放缓冲区; 学习者则专注于从缓冲区中采样经验并更新Q-network参数. 学习者的算法步骤如算法2所示.
算法2. APE-X DQN学习者算法
输入. 经验回放缓冲区$ D $.
输出. 目标Q-network Q$ (s,\; a; \theta') $的参数$ \theta' $; 缓冲区中的经验优先级$ p $.
1) 初始化一个Q-network Q$ (s,\; a; \theta) $与目标Q-network Q$ (s,\; a; \theta') $的参数$ \theta $和$ \theta' $;
2) for each episode do
3) $ B = (s,\; a,\; r,\; s')\leftarrow D.sample(\cdot); $
4) for each experience do
5) $ Q'\leftarrow r + \gamma\; \mathrm{max}(Q(s',\; a'; \theta')); $
6) $ L(\theta)\leftarrow {\mathrm{E}}_{(s,\; a,\; r,\; s')\sim B}[(Q'-Q(s,\; a; \theta))^2]; $
7) $ \delta\leftarrow r+\gamma\; \mathrm{max}(Q(s',\; a'; \theta'))-Q(s,\; a; \theta); $
8) $ p\leftarrow|\delta|+\varepsilon; $
9) end for
10) $ \theta'\leftarrow\theta; $
11) end for
3.4.1 算法工作原理
从经验回放缓冲区$ D $中, 根据优先级采样样本集的经验$ B $ (算法第1 ~ 3行); 对于样本集中的每一条经验$ (s,\; a,\; r,\; s') $, 计算目标$ Q $值, 计算损失函数$ L(\theta) $, 并使用梯度下降法更新Q-network的参数$ \theta $以最小化损失(算法5 ~ 6行); 对于每条经验, 计算其TD (Temporal difference)误差$ \delta $, 并更新经验回放缓冲区中对应经验的优先级$ p $ (算法7 ~ 8行). 每隔一定数量的更新步骤, 将Q-network的参数复制到目标Q-network, 即$ \theta'\leftarrow\theta $.
3.4.2 算法复杂性分析
算法2的复杂度与训练的episode数量$ N $和每次采样的经验条数$ K $相关, 通过分析可以发现, 算法的时间复杂度为$ \mathrm{O}(N\times K) $. 与传统的DQN相比, 高效的并行化能大大提高数据吞吐量和学习速度, 能良好感知执行动作对多模态数据场景下状态的影响. 通过将经验存储在回放缓冲区中, 并按照优先级进行抽样, 能够减少样本间的相关性, 提高学习的稳定性. 其分布式架构使得AP-IS能够很好地扩展到大规模的计算环境中, 如多核CPU和GPU集群. 其在线的学习过程也能适应环境的动态变化, 对于非静态环境有很好的适应性.
3.5 索引效益评估方法
在AP-IS模型中, 索引效益评估方法为APE-X DQN提供奖励值. 奖励是智能体与环境之间的交互过程中反馈给智能体的信号, 用于指导索引选择的决策和行为. 因此, 索引效益评估的准确性对高效的索引选择起着至关重要的作用. 评价索引效益可以使用很多指标, 而现有方法大多只依赖于数据库中的代价估计值, 未考虑索引体积和构建索引的代价. 为了使AP-IS能更好地适应动态的工作负载, 索引效益评估方法通过从工作负载$ q $的执行成本和索引$ I $的构建成本两方面评估索引的代价.
工作负载的执行成本由数据库的代价估计、工作负载实际执行延迟、磁盘I/O共同组成, 记作$ Cost(q) $, 具体表示为:
$$ \begin{split}Cost(q)=\; & \alpha\; (w_1\times C_{cost}^q)\; + \\ & \beta\; \Bigg(w_2\; C_{latency}^q+w_3\; \left(\frac{1}{C_{IO}^q}\right)\Bigg)\end{split} $$ (13) 其中, $ C^q_{cost} $为执行工作负载$ q $时的数据库代价估计值; $ C^q_{latency} $为工作负载实际的执行延迟, 单位为ms; $ C^q_{IO} $为磁盘I/O值, 该值可由PostgreSQL中的pg_stat_statements扩展获得; $ w_1 $、$ w_2 $和$ w_3 $为平衡各指标重要性的权重; $ \alpha $和$ \beta $代表标志位, 为了加快训练速度, AP-IS会先采用虚拟索引和代价估计值作为训练依据, 此时没有真实的执行延迟和I/O值, 因此该阶段$ \alpha=1 $, $ \beta=0 $; 后续训练采用真实的索引和实际的执行参数作为训练依据, 此时标志位$ \alpha=0 $, $ \beta=1 $.
索引的构建成本由构建索引的耗时、索引体积和索引的命中率共同组成, 记作$ Cost(I) $, 如下所示:
$$ \begin{aligned} Cost(I) = w_4\; C^I_{time}+w_5\; C^I_{size}+w_6 \left(\frac{1}{R^I_{hit}}\right) \end{aligned} $$ (14) 其中, $ C^I_{time} $为构建索引$ I $时的执行延迟; $ C^I_{size} $为索引的体积值, 单位为MB; $ R^I_{hit} $为索引的命中率; $ w_4 $、$ w_5 $和$ w_6 $为平衡各指标重要性的权重. 上述权重通过一个单层神经网络, 从历史的数据中动态学习得到, 以获得更精确的成本估计.
最后, 索引效益评估方法采用$ \mathrm{Reward} $奖励值, 其基于上述工作负载的执行成本(见式(13))和索引的构建成本(见式(14)), 用于指导索引选择的决策和行为, 具体定义为:
$$ \begin{aligned} {\mathrm{Reward}} = -\sqrt{\frac{1}{k}Cost(q)+Cost(I)} \end{aligned} $$ (15) 其中, $ k $为工作负载$ q $中执行的SQL数量. AP-IS的目的为选择代价尽量小的索引集, 因此索引效益评估方法给出的奖励值为负值.
4. 实验与分析
4.1 实验设置
实验数据集为TPC-H、TPC-DS和真实的多模态场景数据Real-D, TPC-H和TPC-DS是由事务处理性能委员会(Transaction Processing Performance Council)制定的标准数据库性能测试基准. TPC-H旨在模拟数据仓库的工作环境, 包含8张表, 22条SQL查询, 这些查询涉及到复杂的JOIN操作、数据聚合以及深层次的嵌套子查询等. 这些查询被设计成复杂度不同、涵盖了各种可能的应用场景. TPC-DS模拟了一个包括多种渠道的销售、库存、促销等数据的大型跨国零售公司的业务场景, 包含7张事实表、17张维度表、23张辅助表及99个复杂的SQL查询. Real-D为真实系统日志数据库, 其中包含35 GB数据, 62个数据表以及300组查询模板, 数据集包含大量时序数据、JSON数据、网络地址数据、文本数据以及数值数据. Real-D数据集在工作负载的大小和查询复杂性方面远大于TPC-DS, Real-D数据集和TPC-H、TPC-DS数据集的构成信息如表3、表4所示.
表 3 Real-D数据集描述Table 3 Description of Real-D dataset数据类型 数据来源 数据规模(GB) 时序数据 滴滴轨迹日志数据 22.1 JSON数据 HTTP请求数据 5.4 字符串数据 图片特征数据 6.8 数值数据 Kaggle 0.7 表 4 TPC-H、TPC-DS数据集描述Table 4 Description of TPC-H and TPC-DS datasets数据集名称 数据类型 数据规模(GB) TPC-H 数值、字符串等 1 TPC-DS 数值、字符串等 10 实验环境配置为16核32线程的CPU、2 TB硬盘、256 GB内存, DBMS为PostgreSQL, 操作系统为Ubuntu 20.04, 深度强化学习环境采用RLlib实现. RLlib是一个开源的强化学习库, 支持TensorFlow, 能够为不同的应用程序提供高度可伸缩的接口. 实验中设置学习率$ lr $= 0.01; 折扣因子$ \gamma $的值设置过大将导致模型过于关注长期奖励而忽视短期奖励, 反之则会导致模型过于关注短期奖励, 故设置$ \gamma $的值为0.95; 经验回放缓冲区大小$ S_D $的值设置为
30000 , $ S_D $值设置过小则经验存储数量不足, 不利于多周期训练, 过度增加$ S_D $值会导致缓冲区中存储冗余经验, 可能会导致训练效果的下降; 当单次采样经验条数$ K $的取值较大时, 会导致神经网络参数更新频率变低, 模型将无法及时从采样经验中学习到新信息, 使模型收敛速度变慢, 降低了模型对非静态环境的适应性, 具体参数设置如表5所示.表 5 实验超参数设置Table 5 Experimental setup of hyperparameters参数名 参数值 参数说明 $ N $ 10000 训练中episode数量 $ K $ 64 单次采样经验条数 $ lr $ 0.01 学习率 $ \gamma $ 0.95 折扣因子 $ S_D $ 30000 经验回放缓冲区大小 实验对比算法为当前主流的索引选择方法, 包括: 1) NoDBA: 采用DQN实现索引的自动选择; 2) AutoIndex: 利用蒙特卡罗树搜索, 根据候选索引优化现有索引; 3) Greedy: 采用一种启发式方法进行索引选择; 4) ITLCS: 一种基于规则的索引选择方法, 结合了遗传算法和强化学习.
在AP-IS的训练阶段, 对于前30% 的数据会创建虚拟索引, 将代价估计值作为训练的指标, 在后70% 的训练中, 创建真实索引并将实际的SQL执行延迟和索引体积等参数作为训练指标.
4.2 实验评估指标
AP-IS采用多种评价指标与其他方法进行对比分析, 包括平均相对代价、平均相对延迟、索引体积.
平均相对代价$ E^{cost} $旨在描述索引集$ ISet $在某工作负载下对执行代价的优化效果. 其公式如下所示:
$$ \begin{aligned} E^{cost} = \frac{\sum\limits_{i = 1}^{n}\frac{Cost(Q_i,\; ISet)}{Cost(Q_i)}}{n} \end{aligned} $$ (16) 其中, $ Q_i $表示第$ i $条SQL语句; $ n $为工作负载中SQL语句的数量; $ Cost(Q_i,\; ISet) $表示在索引集$ ISet $优化下执行语句$ Q_i $的执行代价; $ Cost(Q_i) $表示未添加索引时执行语句$ Q_i $获取的代价值. 当$ E^{cost}<1 $时, 代表在索引集$ ISet $下的平均相对代价低于未添加索引的平均相对代价.
平均相对延迟$ E^{latency} $的计算公式为:
$$ \begin{aligned} E^{latency} = \frac{\sum\limits_{i = 1}^{n}\frac{Latency(Q_i,\; ISet)}{Latency(Q_i)}}{n} \end{aligned} $$ (17) 其中, $ Latency (Q_i,\; ISet) $表示在索引集$ ISet $优化下执行语句$ Q_i $的执行延迟; $ Latency(Q_i) $表示未添加索引时执行语句$ Q_i $获取的时间.
4.3 AP-IS的代价评估
在AP-IS的平均相对代价评估中, 首先采用只读的工作负载进行实验, 即数据插入完成后仅进行查询操作. 如图8(a)所示, 在TPC-H数据集上, AP-IS平均相对代价均低于其他方法, 其中, 基于强化学习的AP-IS、AutoIndex、NoDBA和ITLCS方法均低于传统的Greedy方法. 主要原因在于: TPC-DS中大多数的字段为数值类型和字符串类型, 在字符串类型数据上建立B-tree索引可能无法优化查询效率, 而AP-IS具有建立全文索引的优势和更先进的搜索策略, 因此优于其他方法. TPC-DS数据集的数据模态与TPC-H类似, 而工作负载更加复杂, 因此, 如图8(b)所示, 各方法的平均相对代价均高于TPC-H中的评估结果. 如图8(c)所示, 在多模态数据集Real-D上, AP-IS的性能仍优于其他方法, 且AP-IS的优势更加明显. 其原因在于, AP-IS能为大量多模态数据选择合适的索引类型, 在文本数据、半结构化数据、时序数据等字段上的查询代价远低于其他方法.
4.4 AP-IS的执行延迟评估
如图9所示, 在只读工作负载的延迟评估中, AP-IS的平均相对延迟均低于其他方法. 在TPC-DS数据集上, Greedy方法的$ E^{latency} $比AP-IS高出0.244, AutoIndex方法的$ E^{latency} $比AP-IS高出0.139, NoDBA方法的$ E^{latency} $比AP-IS高出0.263, ITLCS方法的$ E^{latency} $比AP-IS高出0.216.
由于NoDBA方法只以数据库代价估计作为DQN的奖励值, 且无法创建复合索引, 因此在执行延迟评估中表现较差.
在Real-D数据集上, AP-IS仍具有最低平均相对延迟, 因为AP-IS采用多个执行者和一个学习者的架构, 能充分考虑多模态数据场景下多个索引的优化效果, 为不同数据模态选择不同索引类型, 大幅度优化了只读工作负载下的查询效率.
在AP-IS动态工作负载的执行延迟评估中, 分别采用频繁读和频繁写两种工作模式. 频繁读指80% 的数据读取操作及20% 的数据写入操作, 频繁写指80% 的数据写入操作及20% 的数据读取操作. 在TPC-DS数据集中, 采用查询(SELECT)和插入(INSERT)语句模拟动态工作负载的读写过程, 在Real-D数据集中, 写入操作包括插入、修改和删除. TPC-H与TPC-DS数据集上的实验结果相似, 这里不再赘述.
如图10所示, 在频繁读场景的工作负载下, AP-IS在Real-D数据集上的$ E^{latency} $值比Greedy、AutoIndex、NoDBA以及ITLCS分别低0.468、0.357、0.437、0.463, 取得了最佳的性能, 其主要原因在于: AP-IS的SQL编码方法能够在高效编码SQL的同时, 保留SQL中所含有的丰富信息(操作类型、所含子句、对应谓词、可索引字段、模态等), 然后利用Tree-LSTM准确捕捉树形状态信息, 保证了数据读取的准确性及效率; AP-IS的分布式机制允许多个执行者分别与环境进行交互, 进而高效感知动态工作负载中多种SQL语句类型以及数据模态, 再由学习者采用优先级从经验回放缓冲区内的大量信息中学习, 从而选择具有更高效益的索引, 在频繁读状态下相较于其他方法具有更好的性能.
在频繁写场景下, AP-IS在Real-D数据集上的$ E^{latency} $比Greedy、AutoIndex、NoDBA、ITLCS分别低0.579、0.365、0.612、0.443, 主要原因在于: AP-IS采用的高效索引集编码方法能够有效避免冗余的复合索引, 能在一定程度上减少索引对插入操作的负面效果. 此外, AP-IS在TPC-DS数据集上的综合表现弱于在Real-D数据集上的表现, 具体原因为: 在基于TPC-DS数据集评估中, 虽然TPC-DS具有较Real-D更简单的表结构, 但其在频繁写工作负载中包含大量插入操作, 对实验效果造成了一定负面影响. 在TPC-DS中的频繁写场景下, NoDBA方法因未考虑动态工作负载导致性能不佳. 进一步地, 由于Greedy方法和NoDBA方法均不支持动态工作负载下的索引更新, 因此在频繁写工作负载下, 数据更新的效率降低, 产生了较差的优化效果.
图11展示了在Real-D数据集的动态工作负载情况下, AP-IS结合不同强化学习算法的执行延迟对比, 其中AP-IS为所提方法, 采用APE-X DQN作为强化学习骨架. 由实验结果可知, AP-IS具有最优的执行延迟, 这是由于APE-X DQN可利用多线程机制并行化多个学习者来加速学习过程, 可以提高样本利用率, 并且可以较好地平衡策略步长, 使其针对动态工作负载的综合稳定性较强. 在频繁读和频繁写工作负载下, DDQN (Double deep Q-network)[30]算法的执行延迟略优于DQN算法, 原因在于DDQN使用两个独立的神经网络来估计$ Q $值, 一定程度上减少了选择动作和评估动作效果之间可能存在的偏差, 进而提升了推荐索引质量. PPO (Proximal policy optimization)[31]算法在连续空间中具有较好的表现, 但其更加适用于策略更新步长比较小的情况, 所以在动态的工作负载场景下适应性不足.
图 11 动态工作负载下不同强化学习算法延迟Fig. 11 Latency of different reinforcement learning algorithms under dynamic workloads4.5 AP-IS的状态表示模型评估
AP-IS采用Tree-LSTM对SQL语句进行状态表示, 同时将其作为索引类型的选择依据. 为了验证Tree-LSTM在AP-IS中的有效性, 如表6所示, 分别将其替换为RNN (Recurrent neural network)[32]方法、BiRNN (Bidirectional recurrent neural network)[33]方法、LSTM方法、BiLSTM (Bidirectional long short-term memory)[34]方法以及GRU (Gated recurrent unit)[35]方法为AP-IS提供状态表示.
表 6 AP-IS不同状态表示方法的延迟对比Table 6 Latency comparison of different state representation methods of AP-IS方法 频繁读 频繁写 只读 TPC-H TPC-DS Real-D TPC-H TPC-DS Real-D TPC-H TPC-DS Real-D RNN 0.550 0.604 0.548 0.616 0.695 0.599 0.569 0.618 0.657 BiRNN 0.549 0.591 0.522 0.546 0.633 0.534 0.576 0.570 0.599 LSTM 0.506 0.563 0.496 0.523 0.629 0.513 0.513 0.537 0.539 BiLSTM 0.452 0.549 0.430 0.472 0.603 0.530 0.468 0.459 0.456 GRU 0.459 0.552 0.427 0.486 0.593 0.429 0.436 0.447 0.428 Tree-LSTM 0.433 0.519 0.364 0.460 0.589 0.396 0.423 0.447 0.398 传统的RNN模型通过循环连接处理工作负载, 在处理长期依赖问题时容易出现梯度爆炸或梯度消失问题, 不适合处理较长SQL序列. 而LSTM、GRU等模型通过其门控机制和细胞状态可以让网络决定丢弃和保留信息, 能避免在处理较大工作负载时的梯度消失, 但其仅允许严格按顺序进行信息传播, 不利于处理SQL语句中的树状结构. 采用上述方法指导索引选择时容易使AP-IS选择包含较多列的联合索引, 造成索引冗余.
Tree-LSTM具有复杂的树状结构, 每个单元包括多个遗忘门, 使门控向量和记忆单元的更新依赖于更多子单元状态. AP-IS能够拆分或合并SQL语句中的可索引列信息, 选择更适合的字段创建索引, 避免索引冗余. 实验中分别对比上述方法在不同工作负载下的平均相对延迟, 结果证明采用Tree-LSTM能为AP-IS提供更好的状态表示, 使工作负载的执行延迟更低, 效果最佳.
4.6 AP-IS的多线程机制评估
AP-IS的多线程机制具有加快训练速度、提高样本利用率、增加算法的稳定性等优势, 能有效改善探索与利用两个阶段的平衡, 提高AP-IS在复杂多模态数据场景的优化效果. 为了证明AP-IS的多线程机制的有效性, 在频繁读的工作负载中, 采用不同执行者数量的环境对AP-IS进行评估. 如图12所示, 随着执行者数量的增加, 工作负载的平均相对延迟逐步降低. 在TPC-H数据集上, 64个执行者环境下的平均相对延迟比单线程环境下低17.9%, 在TPC-DS数据集下低19.1%, 在Real-D数据集下低35.9%. 在基于TPC-H和TPC-DS数据集的评估中, 执行者线程数超过8个后的数据库效率改善幅度较小, 而基于Real-D数据集的评估随着执行者数量增加仍有改善空间. 其原因在于, TPC-DS的数据模态数量较少, 其数据复杂程度也远低于Real-D, 因此AP-IS增加线程数量也无法获取更多的经验.
4.7 AP-IS的混合训练机制评估
AP-IS的混合训练机制包含基于虚拟索引的代价估计训练以及基于真实索引的执行延迟训练. 为了验证AP-IS的混合训练机制的有效性, 引入对照方法AP-IS-with-only-latency, 该方法仅采用真实索引和执行延迟作为训练指标. 如图13所示, 该评估中采用TPC-DS数据集的频繁读工作负载, 前
3 000 个episode采用虚拟索引, 基于代价估计值进行训练; 后7 000 个episode采用真实索引, 基于工作负载的实际执行延迟进行训练.在AP-IS的混合训练机制下, 经过500个episode的训练之后, 平均相对延迟逐渐低于1, 由于创建虚拟索引以及代价估计的效率较高, 使智能体能够快速学习索引选择策略, 感知数据模态和复杂的动态工作负载. 在
2500 到3000 个episode训练期间, 平均相对延迟没有明显下降, 且波动较大. 在后续的真实执行延迟训练中(第3000 个episode后), 平均相对延迟进一步降低, 且训练曲线趋于平稳, 在7500 个episode后逐渐收敛.对于AP-IS-with-only-latency, 前期智能体盲目地选择索引, 在索引创建上消耗大量时间, 训练速度较慢, 学习到的策略不能及时更新. 训练进行到2 000个episode后平均相对延迟才小于1, 后续训练曲线存在较大波动, 收敛速度较慢.
4.8 AP-IS的编码方法评估
为证明AP-IS的编码有效性, 引入4个对照方法: 1) All-Encoding: 保留AP-IS完整的编码方法; 2) No-SQL-Encoding: 该方法的SQL编码仅对可索引列采用简单的one-hot编码, 不使用树形结构编码及基于Tree-LSTM的状态表示模型; 3) No-Index-Encoding: 该方法的索引集采用简单的one-hot编码方法, 不适用基于前缀树的编码方法; 4) No-Encoding表示SQL编码和索引集编码均采用one-hot编码.
如图14所示, AP-IS放弃任一种编码方法均会造成数据库性能下降. 其主要原因在于, 仅采用one-hot的SQL语句编码无法使AP-IS感知不同的数据模态以及SQL语句类型, 执行者无法学习数据模态与索引类型之间的对应关系, 使执行者盲目进行索引类型选择, 无法利用不同的索引类型优化多模态数据的查询性能. 而仅采用one-hot编码索引集无法考虑B-tree索引本身的特性, 仅采用可索引列作为索引选择依据, 容易造成索引冗余或索引失效, 无法有效优化工作负载的执行.
图 14 AP-IS在动态工作负载下的编码方法评估Fig. 14 Evaluation of encoding methods for AP-IS under dynamic workloads4.9 AP-IS的索引存储空间评估
AP-IS的索引选择方法能泛化到各种存储空间限制中, 如图15所示, 在Real-D数据集的动态工作负载下, 当索引存储空间限制从5 GB提升到20 GB时, AP-IS的平均相对延迟从0.663降低到了0.396. 在10 GB和20 GB的存储空间限制中, AP-IS共构建了37个和53个索引, 每个索引类型的选择数量如表7所示. 由于索引体积是AP-IS的奖励参数之一, 因此更趋向于选择空间收益比更高的索引. Hash索引与BRIN索引和B-tree索引相比有更小的索引体积和索引创建时间, 因此, 与其他方法相比, AP-IS能在相同的存储空间下选择更多的索引数量, 进而使平均相对延迟低于其他方法. 此外, 在不支持动态工作负载的Greedy方法和NoDBA方法中, 选择更多的索引在某些情况下并不会使工作负载的执行效率提高, 其原因在于, 大量冗余的B-tree索引会对数据更新产生负面影响.
表 7 AP-IS在Real-D数据集上不同索引类型的选择数量Table 7 Selection number of different index types on the Real-D dataset of AP-IS索引类型 选择数量(10 GB) 选择数量(20 GB) B-tree 13 19 Hash 7 9 GiST 5 4 SP-GiST 3 7 GIN 1 4 BRIN 8 10 5. 结束语
本文提出一种新型索引选择框架, 支持多种索引类型的选择, 显著提高了数据库执行效率. 通过异步更新和优先经验回放机制, 优化多模态数据场景下智能体的探索策略和与环境交互能力. 提出一种新型的SQL语句和索引集编码方法, 能够感知数据模态, 定位索引候选属性, 精确表达索引集和索引类型, 避免索引冗余或缺失. 此外, 提出一种索引效益评估方法, 综合多种指标, 使AP-IS适时更新索引集, 保持索引的优化效果. 最后, 在TPC-DS数据集和真实多模态数据集上, 证明了AP-IS的有效性.
现有索引选择方法仍然存在一些不足, 例如: 需考虑到更多的索引参数, 在算法中实现更严谨的状态表示方法、搜索策略以及更复杂的动作集, 以进一步增加索引推荐的质量; 其次, AP-IS当前无法支持动态更新的表结构, 模型训练时已对数据库中的索引字段进行编码, 无法在后续增量训练或索引选择执行过程中动态改变字段编码, 若某个数据表添加新的字段, 已完成训练的模型将无法对其进行索引优化, 需重新对数据库进行状态表达并训练新的模型进而优化变更的字段.
为改进上述不足之处, 未来工作应考虑更多的索引参数、解决动态的表结构问题、优化学习型索引结构以及结合学习型连接优化器.
-
图 1 时序数据模态下BRIN索引和B-tree索引的性能对比
Fig. 1 Performance comparison of BRIN index and B-tree index in temporal data modal
图 11 动态工作负载下不同强化学习算法延迟
Fig. 11 Latency of different reinforcement learning algorithms under dynamic workloads
图 14 AP-IS在动态工作负载下的编码方法评估
Fig. 14 Evaluation of encoding methods for AP-IS under dynamic workloads
表 1 索引选择方法对比分析
Table 1 Comparison analysis of index selection methods
方法策略 方法名称 优点 不足 传统的数据库索引选择方法 Drop[19] 通过启发式方法, 针对工作负载创建索引, 减轻DBA的工作负担 没有充分利用DBA经验, 无法适应动态的工作负载, 无法创建复合索引 AutoAdmin[20] 每轮迭代通过增加索引宽度支持多列索引选择 无法处理动态变化的工作负载, 加重DBA的负担 DB2Advis[21] 采用随机替换法适应动态的工作负载 随机的索引替换造成大量磁盘开销, 索引方案的不断变化影响系统的稳定性 基于学习的
数据库索引
选择方法NoDBA[22] 首次采用深度强化学习进行数据库索引自动选择, 降低工作负载的执行延迟 无法适应动态的工作负载, 也无法创建复合索引 ITLCS[23] 将遗传算法和强化学习相结合, 能够适应动态的工作负载和表结构较复杂的场景 依赖遗传算法索引选择策略, 未将基于学习的方法应用到问题的求解过程中 AutoIndex[10] 利用蒙特卡罗树搜索根据候选索引优化现有索引, 支持复合索引和动态的工作负载 无法适应多模态数据场景, 不支持多种索引类型的选择 
下载: 导出CSV
表 2 不同索引类型在多模态数据场景的适用性和局限性
Table 2 Applicability and limitations of different index types in multimodal data scenarios
索引类型 适用数据模态及场景 不适用数据模态及场景 B-tree 整型、浮点型的等值、范围查询、排序等 文本类型的全文搜索, JSON等半结构化数据 Hash 等值查询 数据分布不均匀或更新频繁的场景 GiST 空间数据、文本数据的全文搜索、模糊查询 精确匹配、排序、去重等场景 SP-GiST 空间数据、文本数据的全文搜索 去重、排序, 不支持复合索引 GIN JSON等半结构化数据更新频繁的场景 大型二进制对象数据, 精确匹配等场景 BRIN 时序数据, 顺序访问模式 随机访问、精确匹配等场景
下载: 导出CSV
表 3 Real-D数据集描述
Table 3 Description of Real-D dataset
数据类型 数据来源 数据规模(GB) 时序数据 滴滴轨迹日志数据 22.1 JSON数据 HTTP请求数据 5.4 字符串数据 图片特征数据 6.8 数值数据 Kaggle 0.7
下载: 导出CSV
表 4 TPC-H、TPC-DS数据集描述
Table 4 Description of TPC-H and TPC-DS datasets
数据集名称 数据类型 数据规模(GB) TPC-H 数值、字符串等 1 TPC-DS 数值、字符串等 10
下载: 导出CSV
表 5 实验超参数设置
Table 5 Experimental setup of hyperparameters
参数名 参数值 参数说明 $ N $ 10000 训练中episode数量 $ K $ 64 单次采样经验条数 $ lr $ 0.01 学习率 $ \gamma $ 0.95 折扣因子 $ S_D $ 30000 经验回放缓冲区大小
下载: 导出CSV
表 6 AP-IS不同状态表示方法的延迟对比
Table 6 Latency comparison of different state representation methods of AP-IS
方法 频繁读 频繁写 只读 TPC-H TPC-DS Real-D TPC-H TPC-DS Real-D TPC-H TPC-DS Real-D RNN 0.550 0.604 0.548 0.616 0.695 0.599 0.569 0.618 0.657 BiRNN 0.549 0.591 0.522 0.546 0.633 0.534 0.576 0.570 0.599 LSTM 0.506 0.563 0.496 0.523 0.629 0.513 0.513 0.537 0.539 BiLSTM 0.452 0.549 0.430 0.472 0.603 0.530 0.468 0.459 0.456 GRU 0.459 0.552 0.427 0.486 0.593 0.429 0.436 0.447 0.428 Tree-LSTM 0.433 0.519 0.364 0.460 0.589 0.396 0.423 0.447 0.398
下载: 导出CSV
表 7 AP-IS在Real-D数据集上不同索引类型的选择数量
Table 7 Selection number of different index types on the Real-D dataset of AP-IS
索引类型 选择数量(10 GB) 选择数量(20 GB) B-tree 13 19 Hash 7 9 GiST 5 4 SP-GiST 3 7 GIN 1 4 BRIN 8 10
下载: 导出CSV
-
[1] Zhang C, Yang Z, He X, Deng L. Multimodal intelligence: Representation learning, information fusion, and applications. IEEE Journal of Selected Topics in Signal Processing, 2020, 14(3): 478−493 doi: 10.1109/JSTSP.2020.2987728 [2] Lu J, Holubová I. Multi-model databases: A new journey to handle the variety of data. ACM Computing Surveys, 2019, 52(3): 1−38 [3] Li G, Zhou X, Cao L. AI meets database: AI4DB and DB4AI. In: Proceedings of the 2021 ACM SIGMOD International Conference on Management of Data. New York, USA: ACM, 2021. 2859−2866 [4] Chaudhuri S, Datar M, Narasayya V. Index selection for databases: A hardness study and a principled heuristic solution. IEEE Transactions on Knowledge and Data Engineering, 2004, 16(11): 1313−1323 doi: 10.1109/TKDE.2004.75 [5] Sun Z, Zhou X, Li G. Learned index: A comprehensive experimental evaluation. Proceedings of the VLDB Endowment, 2023, 16(8): 1992−2004 doi: 10.14778/3594512.3594528 [6] AlMahamid F, Grolinger K. Reinforcement learning algorithms: An overview and classification. In: Proceedings of the 2021 IEEE Canadian Conference on Electrical and Computer Engineering. Washington, USA: IEEE, 2021. 1−7 [7] Huang S, Wang Y, Li G. ACR-Tree: Constructing r-trees using deep reinforcement learning. In: Proceedings of the 28th International Conference of Database Systems for Advanced Applications. Berlin, Germany: Springer, 2023. 80−96 [8] 孙长银, 穆朝絮. 多智能体深度强化学习的若干关键科学问题. 自动化学报, 2020, 46(7): 1301−1312Sun Chang-Yin, Mu Chao-Xu. Important scientific problems of multi-agent deep reinforcement learning. Acta Automatica Sinica, 2020, 46(7): 1301−1312 [9] 胡子剑, 高晓光, 万开方, 张乐天, 汪强龙, Neretin Evgeny. 异策略深度强化学习中的经验回放研究综述. 自动化学报, 2023, 49(11): 2237−2256Hu Zi-Jian, Gao Xiao-Guang, Wan Kai-Fang, Zhang Le-Tian, Wang Qiang-Long, Neretin Evgeny. Research on experience replay of off-policy deep reinforcement learning: A review. Acta Automatica Sinica, 2023, 49(11): 2237−2256 [10] Zhou X, Liu L, Li W, Jin L, Li S, Wang T. AutoIndex: An incremental index management system for dynamic workloads. In: Proceedings of the 2022 IEEE 38th International Conference on Data Engineering. Washington, USA: IEEE, 2022. 2196−2208 [11] 蒲志强, 易建强, 刘振, 丘腾海, 孙金林, 李非墨. 知识和数据协同驱动的群体智能决策方法研究综述. 自动化学报, 2022, 48(3): 627−643Pu Zhi-Qiang, Yi Jian-Qiang, Liu Zhen, Qiu Teng-Hai, Sun Jin-Lin, Li Fei-Mo. Knowledge-based and data-driven integrating methodologies for collective intelligence decision making: A survey. Acta Automatica Sinica, 2022, 48(3): 627−643 [12] Horgan D, Quan J, Budden D, Barth-Maron G, Hessel M, Hasselt H. Distributed prioritized experience replay. In: Proceedings of the 6th International Conference on Learning Representations. Appleton, USA: ICLR Press, 2018. 1−19 [13] Boncz P, Neumann T, Erling O. TPC-H analyzed: Hidden messages and lessons learned from an influential benchmark. In: Proceedings of the Performance Characterization and Benchmarking. Berlin, Germany: Springer, 2014. 61−76 [14] Tardío R, Maté A, Trujillo J. Beyond TPC-DS, a benchmark for big data OLAP systems (BDOLAP-Bench). Future Generation Computer Systems, 2022, 132(5): 136−151 [15] Chaudhuri S, Narasayya V R. AutoAdmin “what-if” index analysis utility. In: Proceedings of the 1998 ACM SIGMOD International Conference on Management of Data. New York, USA: ACM, 1998. 367−378 [16] Valentin G, Zuliani M, Zilio D C, Lohman G M, Skelley A. DB2 advisor: An optimizer smart enough to recommend its own indexes. In: Proceedings of the 16th International Conference on Data Engineering. Washington, USA: IEEE, 2000. 101−110 [17] Sharma V, Dyreson C, Flann N. MANTIS: Multiple type and attribute index selection using deep reinforcement learning. In: Proceedings of the 25th International Database Engineering & Applications Symposium. New York, USA: ACM, 2021. 56−64 [18] Perera R, Oetomo B, Rubinstein B, Borovica-Gajic R. DBA bandits: Self-driving index tuning under ad-hoc, analytical workloads with safety guarantees. In: Proceedings of the IEEE 37th International Conference on Data Engineering. Washington, USA: IEEE, 2021. 600−611 [19] Kossmann J, Halfpap S, Jankrift M, Schlosser R. Magic mirror in my hand, which is the best in the land? An experimental evaluation of index selection algorithms. Proceedings of the VLDB Endowment, 2020, 13(12): 2382−2395 doi: 10.14778/3407790.3407832 [20] Chaudhuri S, Narasayya V. An efficient cost-driven index selection tool for microsoft SQL server. In: Proceedings of the 23rd International Conference on Very Large Data Bases. San Francisco, USA: Morgan Kaufmann Publishers Inc., 1997. 146−155 [21] Valentin G, Zuliani M, Zilio D, Lohman G, Skelley A. DB2 advisor: An optimizer smart enough to recommend its own indexes. In: Proceedings of the 16th International Conference on Data Engineering. Washington, USA: IEEE, 2000. 101−110 [22] Sharma A, Schuhknecht F M, Dittrich J. The case for automatic database administration using deep reinforcement learning. arXiv preprint arXiv: 1801.05643, 2018. [23] Pedrozo W, Nievola J, Carvalho D. An adaptive approach for index tuning with learning classifier systems on hybrid storage environments. In: Proceedings of the Hybrid Artificial Intelligent Systems. Berlin, Germany: Springer, 2018. 716−729 [24] Wang X, Wang S, Liang X, Zhao D, Huang J, Xu X. Deep reinforcement learning: A survey. IEEE Transactions on Neural Networks and Learning Systems, 2024, 35(4): 5064−5078 doi: 10.1109/TNNLS.2022.3207346 [25] Mnih V, Kavukcuoglu K, Silver D, Rusu A, Veness J, Bellemare M. Human-level control through deep reinforcement learning. Nature, 2015, 518(7540): 529−533 doi: 10.1038/nature14236 [26] Katoch S, Chauhan S, Kumar V. A review on genetic algorithm: Past, present, and future. Multimedia Tools and Applications, 2021, 80(5): 8091−8126 doi: 10.1007/s11042-020-10139-6 [27] Swiechowski M, Godlewski K, Sawicki B, Mandziuk J. Monte carlo tree search: A review of recent modifications and applications. Artificial Intelligence Review, 2023, 56(3): 2497−2562 doi: 10.1007/s10462-022-10228-y [28] Tai K, Socher R, Manning C. Improved semantic representations from tree-structured long short-term memory networks. In: Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing. Stroudsburg, USA: Association for Computational Linguistics, 2015. 1556−1566 [29] Lindemann B, Müller T, Vietz H, Jazdi N, Weyrich M. A survey on long short-term memory networks for time series prediction. In: Proceedings of the 14th CIRP Conference on Intelligent Computation in Manufacturing Engineering. Amsterdam, Netherlands: Elsevier, 2021. 650−655 [30] Yao Y, He J, Li T, Wang Y, Lan X, Li Y. An automatic xss attack vector generation method based on the improved dueling DDQN algorithm. IEEE Transactions on Dependable and Secure Computing, 2024, 21(4): 2852−2868 doi: 10.1109/TDSC.2023.3319352 [31] Chen Y, Shih W, Lai H, Chang H, Huang J. Pairs trading strategy optimization using proximal policy optimization algorithms. In: Proceedings of the International Conference on Big Data and Smart Computing. Washington, USA: IEEE, 2023. 40−47 [32] Han Y, Li G, Yuan H, Sun J. AutoView: An autonomous materialized view management system with encoder-reducer. IEEE Transactions on Knowledge and Data Engineering, 2023, 35(6): 5626−5639 [33] Holzer S, Stockinger K. Detecting errors in databases with bidirectional recurrent neural networks. In: Proceedings of the 25th International Conference on Extending Database Technology. Edinburgh, UK: EDBT Association, 2022. 364−367 [34] Zheng Y, Gao Z, Shen J, Zhai X. Optimizing automatic text classification approach in adaptive online collaborative discussion——A perspective of attention mechanism-based Bi-LSTM. IEEE Transactions on Learning Technologies, 2023, 16(5): 591−602 doi: 10.1109/TLT.2022.3192116 [35] Yao D, Cong G, Zhang C, Meng X, Duan R, Bi J. A linear time approach to computing time series similarity based on deep metric learning. IEEE Transactions on Knowledge Data Engineering, 2022, 34(10): 4554−4571 doi: 10.1109/TKDE.2020.3047070 -
下载:
计量
- 文章访问数: 229
- HTML全文浏览量: 100
- PDF下载量: 45
- 被引次数: 0
