AlphaQO_鲁棒的学习型查询优化器-余翔，柴成亮，张辛宁，汤南，孙佶，李国良.pdf

上善若水

244

18页

0次

2022-05-19

免费下载

软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn

Journal of Software, 2022,33(3):814−831 [doi: 10.13328/j.cnki.jos.006452] http://www.jos.org.cn

AlphaQO: 鲁棒的学习型查询优化器

∗

余

翔

柴成亮

张辛宁

汤

南

孙

佶

李国良

(清华大学计算机科学与技术系, 北京 100084)

(浙江大学计算机科学与技术学院, 浙江杭州 310027)

(Qatar Computing Research Institute, Hamad Bin Khalifa University, Doha, Qatar)

通信作者: 李国良, E-mail: liguoliang@tsinghua.edu.cn

摘要: 由深度学习驱动的学习型查询优化器正在越来越广泛地受到研究者的关注, 这些优化器往往能够取得近

似甚至超过传统商业优化器的性能. 与传统优化器不同的是, 一个成功的学习型优化器往往依赖于足够多的高质

量的负载查询作为训练数据. 低质量的训练查询会导致学习型优化器在未来的查询上失效. 提出了基于强化学习

的鲁棒的学习型查询优化器训练框架 AlphaQO, 提前找到学习型优化器做不好的查询, 以提高学习型优化器的鲁

棒性. AlphaQO 中存在两个重要部分: 查询生成器和学习型优化器. 查询生成器的目标是生成“难”的查询(传统优

化器做得好, 但是学习型优化器反而做得不好的查询). 学习型优化器利用这些生成的查询进行测试和训练,并提

供反馈让查询生成器进行更新. 系统迭代交替的运行上述两个部分, 分别进行训练. 目的在于在提供尽量少的信

息和消耗足够小的时间下找到足够多“难”的并且未见的查询给优化器训练, 以提高学习型优化器的鲁棒性. 实验

结果显示: 该生成器会提供越来越难的训练查询给学习型优化器; 同时, 这些查询能够提升学习型优化器的性能.

关键词: 学习型优化器; 鲁棒性; AI4DB; 数据库; 强化学习; 查询生成

中图法分类号: TP311

中文引用格式: 余翔, 柴成亮, 张辛宁, 汤南, 孙佶, 李国良. AlphaQO: 鲁棒的学习型查询优化器. 软件学报, 2022, 33(3):

814–831. http://www.jos.org.cn/1000-9825/6452.ht m

英文引用格式: Yu X, Chai CL, Zhang XN, Tang N, Sun J, Li GL. AlphaQO: Robust Learned Query Optimizer. Ruan Jian Xue Bao/

Journal of Software, 2022, 33(3): 814−831 (in Chinese). http://www.jos.org.cn/1000-9825/6452.htm

AlphaQO: Rob ust Learne d Query Optimi zer

YU Xiang

, CHAI Cheng-Liang

, ZHANG Xin-Ning

, TANG Nan

, SUN Ji

, LI Guo-Liang

(Department of Computer Science and Technology, Tsinghua University, Beijing 100084, China)

(College of Computer Science and Technology, Zhejiang University, Hangzhou 310027, China)

(Qatar Co mputi ng Res ear ch In sti tut e, Hamad Bin Khal if a Univ ers it y, Doha , Qata r)

Abstra ct : Learned database query optimizers, which are typically empowered by (deep) learning models, have attracted significant

attention recently, because they can offer similar or even better performance than the state-of-the-art commercial optimizers that require

hundreds of expert-hours to tune. A crucial factor of successfully training learned optimizers is training queries. Unfortunately, a good

query workload that is sufficient for training learned optimizers is not always available. This study proposes a framework, called

AlphaQO, on generating queries for learned optimi zers with reinforcement learning (RL). AlphaQO is a loop s yst em that consists of two

main components, query generator and learned optimizer. Query generator aims at generating “hard” queries (i.e., those queries that the

learned optimizer provides poo r estimates). The learned opti mizer will be trained using g enerated queries, as well as providing feedb acks

(in terms of numerical rewards) to the query generator. If the generated queries are good, the query generator will get a high reward;

∗ 基金项目: 国家自然科学基金(61925205, 61632016); 华为和好未来资助项目

本文由“数据库系统新型技术”专题特约编辑李国良教授、于戈教授、杨俊教授和范举教授推荐.

收稿时间: 2021-06-30; 修改时间: 2021-07-31; 采用时间: 2021-09-13; jos 在线出版时间: 2021-10-21

余翔等: AlphaQO: 鲁棒的学习型查询优化器

815

otherwise, the query generator will get a low reward. The above process is performed iteratively, with the main goal that within a small

budget, the learned optimizer can be trained and generalized well to a wide range of unseen queries. Extensive experiments show that

AlphaQO can generate a relatively small number of queries and train a learned optimizer to outperform commercial optimizers. Moreover,

learned optimizers need much l ess queries fro m AlphaQO than randomly generated queries, in order to well train the l earned optimi zer.

Key words: learned optimizer; robust ness; AI4 DB; database; r einfor cement learning; qu ery generation

查询优化器决定着数据库引擎执行一条查询时所采用的具体方案, 是决定数据库系统成功与否的核心部

件

[1−3]

. 传统的查询优化器

[4−7]

主要使用的是基于代价的方法: 给定一个 SQL 查询, 优化器会尝试枚举不同的

可能的执行方案, 然后交给估计器估计每个方案的执行代价, 从中选出最小代价的那个方案. 传统的方法往

往受限于两个问题.

• L1: 枚举代价过高. 可能的方案空间往往是指数级的, 基于动态规划的方法需要大量的计算, 而启发

式的方法不一定能取得较好的结果.

• L2: 代价估计模型难以维护. 维护一个好的估计器是非常难的, 不同的系统环境、存储结构、数据集

需要不同的代价模型参数; 同时, 基数估计的准确性也显著影响着估计器的效果.

近段时间, 一些研究者开始使用基于学习的方法对传统优化器进行改进

[8−11]

, 并在 L1 和 L2 上取得了不

错的效果. 他们研究发现, 对比目前已有的数据库管理系统, 学习型优化器可以提供相近甚至更高的性能. 然

而学习型优化器往往使用的是深度学习模型, 效果往往依赖于模型训练的情况. 一般来讲有两个难点.

• L3: 冷启动问题. 如果学习型优化器依赖于大量的真实查询来训练, 一直在线上收集查询并训练, 比

如 NEO

[8]

, 我们会需要很久的时间让学习型优化器收集数据、训练, 以产生较好的效果.

• L4: 鲁棒性问题. 基于学习的优化器的质量往往取决于训练集的质量, 在收集数据的质量不高, 或者

使用随机生成的查询来训练的情况下, 学习型的优化器不一定能够对未来的真实查询取得一个较好

的结果, 从而导致系统的失效.

因此, 我们这篇文章主要解决一个问题: 不仅仅依赖于线上收集大量真实的负载, 我们能否提前发现学

习型优化器做得不好的查询, 交给学习型优化器训练, 提高其鲁棒性?

一个自然而然的想法是生成大量的随机查询, 尽可能地覆盖所有的情况. 然而, 这个做法会十分消耗时

间而并不实用: 首先, 可能的查询数量是十分巨大的, 不同的连接、不同的谓词选择, 会产生指数级别的查询

搜索空间; 同时, 学习型优化器训练一条查询的代价也是非常高的, 需要使用不同的方案在数据库管理系统

上执行该查询得到足够的训练数据. 这些都导致了单纯的随机生成无法解决我们的问题.

我们需要尽量减小生成查询的数量, 提高生成查询的质量, 选择有效的查询交给学习型优化器作为训练

数据. 考虑到学习型优化器一般从那些已经做得好的查询上学不到太多信息, 我们希望查询生成器能够识别

学习型优化器目前做得不好的查询(质量高). 我们使用迭代的方式, 首先由查询生成器生成查询提供给学习

型优化器测试, 然后得到反馈并改进查询生成器的生成方向.

• 贡献

在这篇文章中, 我们提出了一个通用的鲁棒优化器训练框架 AlphaQO, 目的是基于深度强化学习(deep

reinforment learning, DRL)发现学习型优化器做得不好的查询, 并以此提高学习型优化器的鲁棒性. 图 1 总结

了我们 Al

phaQO 的系统架构, 这是一个循环的结构, 主要包含了一个查询生成器(主体, agent)和一个学习型优

化器(环境, environment). 查询生成器迭代地生成查询, 交给学习型优化器. 学习型优化器将测试这些查询,

并给出对应的奖励值(reward), 用于指导查询生成器的生成方向; 之后, 用这些查询训练自己提高性能. 更具

体地来讲, 在第 i 个迭代过程中, 查询生成器会根据策略函数生成查询集合 Q

, 交给学习型优化器. 学习型优

化器拿到这个查询集合 Q

以后, 会与后端的数据库管理系统(DBMS)交互, 来对比看是否超过了传统优化器

的性能, 并根据对比情况返回奖励值集合 R

给查询生成器. 最后, 学习优化器利用这些查询 Q

作为训练数据

进行训练, 并更新系统的状态为 S

. 这些奖励值 R

会被用于生成器的策略函数, 指导查询生成器下一次迭代

过程中的结果.

of 18

免费下载

软件学报计算机技术

关注

评论