SkinnerDB: Regret-bounded Query Evaluation via Reinforcement Learning
SkinnerDB: Regret-bounded Query Evaluation via Reinforcement Learning
复制标题
DOI：
10.1145/3464389
复制
发表时间：
2021-09
期刊：
影响因子：
--
通讯作者：
Immanuel Trummer;Junxiong Wang;Ziyun Wei;Deepak Maram;Samuel Moseley;Saehan Jo;Joseph Antonakakis;Ankush Rayabhari
中科院分区：
文献类型：
--
作者：
Immanuel Trummer;Junxiong Wang;Ziyun Wei;Deepak Maram;Samuel Moseley;Saehan Jo;Joseph Antonakakis;Ankush Rayabhari
SkinnerDB使用强化学习来实现可靠的连接排序，利用具有专门连接算法和数据结构的自适应处理引擎。它不维护数据统计，也不使用成本或基数模型。此外，它不使用训练工作负载，也不尝试将当前查询链接到过去看似相似的查询。相反，它使用强化学习在当前查询的执行过程中从头开始学习最佳连接顺序。为此，它将查询的执行划分为许多小的时间片。在不同的时间片中尝试不同的连接顺序。SkinnerDB合并根据不同连接顺序生成的结果元组，直到获得完整的查询结果。通过测量每个时间片的执行进度，它可以在执行过程中识别有希望的连接顺序。沿着SkinnerDB，我们引入了一个新的查询执行策略的质量标准。我们上限期望执行成本遗憾，即，由于次优连接顺序选择而浪费的预期执行成本量。SkinnerDB具有针对该标准进行优化的多个执行策略。其中一些可以在现有的数据库系统上执行。为了最大限度地提高性能，我们引入了一个自定义的执行引擎，通过专门的多路连接算法和元组表示促进快速连接顺序切换。我们通过实验将SkinnerDB的性能与各种基线进行了比较，包括MonetDB，Postgres和自适应处理方法。我们考虑了各种基准测试，包括连接顺序基准测试、TPC-H和JCC-H，以及带有用户定义函数的基准测试变体。总的来说，与偶尔的灾难性连接顺序选择的性能影响相比，可靠连接顺序的开销可以忽略不计。
SkinnerDB uses reinforcement learning for reliable join ordering, exploiting an adaptive processing engine with specialized join algorithms and data structures. It maintains no data statistics and uses no cost or cardinality models. Also, it uses no training workloads nor does it try to link the current query to seemingly similar queries in the past. Instead, it uses reinforcement learning to learn optimal join orders from scratch during the execution of the current query. To that purpose, it divides the execution of a query into many small time slices. Different join orders are tried in different time slices. SkinnerDB merges result tuples generated according to different join orders until a complete query result is obtained. By measuring execution progress per time slice, it identifies promising join orders as execution proceeds. Along with SkinnerDB, we introduce a new quality criterion for query execution strategies. We upper-bound expected execution cost regret, i.e., the expected amount of execution cost wasted due to sub-optimal join order choices. SkinnerDB features multiple execution strategies that are optimized for that criterion. Some of them can be executed on top of existing database systems. For maximal performance, we introduce a customized execution engine, facilitating fast join order switching via specialized multi-way join algorithms and tuple representations. We experimentally compare SkinnerDB’s performance against various baselines, including MonetDB, Postgres, and adaptive processing methods. We consider various benchmarks, including the join order benchmark, TPC-H, and JCC-H, as well as benchmark variants with user-defined functions. Overall, the overheads of reliable join ordering are negligible compared to the performance impact of the occasional, catastrophic join order choice.