关键词:
数据库管理系统
索引推荐
蒙特卡洛树搜索
索引收益估计
图神经网络
摘要:
随着移动互联网的兴起,数据呈爆发式增长,愈加庞大的数据规模对数据库的快速响应能力提出了要求,同时,计算机技术越来越自动化、智能化,导致开发软件的门槛被逐步降低,越来越多的网站和应用出现,但是许多应用开发者缺乏必要的数据库知识,导致数据库的响应速度被限制。建立索引是加速数据库查询的最有效、最常见的方式之一,如何根据数据库内容和查询负载自动创建合适的索引,是数据库查询优化领域的一个重要课题。近年来,机器学习、深度学习等人工智能技术的发展给索引推荐带来了新的机遇。
本文提出了一种索引推荐算法以推荐合适的索引,和一种代价估计模型以更加准确地评估查询语句的运行成本:1)针对当前索引推荐算法存在的问题,本文提出了一种基于蒙特卡洛树搜索的索引推荐算法,蒙特卡洛树搜索具有兼顾探索和利用的特点,能避免像贪心算法那样容易陷入局部最优,同时,将树节点的动作空间定义为选择某个表字段作为单列索引,或者附加在现有的索引后面以扩展索引,使得算法不需要提前使用预设规则对潜在索引集进行筛选并且时间复杂度也相对较低;2)针对数据库代价估计器准确率较低,从而影响索引推荐算法效果的问题,本文在Zero Shot代价估计模型的基础上,提出使用图神经网络学习物理执行计划中的索引信息,设计索引列节点类型,聚合多个索引列的信息来表示一个多列索引,修改扫描类算子和连接类算子中涉及到索引的建模方式,使得模型能够在索引推荐的任务场景下更加准确地估计执行计划的运行时间;3)将本文提出的索引推荐算法和代价估计模型相结合,索引推荐算法评估查询语句的开销时,将从查询优化器得到的执行计划传递给代价估计模型,代价估计模型输出查询的预估运行时间,索引推荐算法以此作为查询的运行开销。
论文对提出的索引推荐算法和代价估计模型进行了实验测试,实验结果表明,本文提出的索引推荐算法能有效降低查询负载的运行开销至原来的68%;相比于原始的Zero Shot模型,本文提出的代价估计模型的平均值的准确率提升了39.2%;将本文提出的索引推荐算法和代价估计模型联合使用,能降低查询负载的运行时间至原来的61.1%。