SkinnerDB: Regret-bounded Query Evaluation via Reinforcement Learning

作者：Immanuel Trummer, Junxiong Wang, Ziyun Wei, Deepak Maram, Samuel H. Moseley, Saehan Jo, Joseph Antonakakis, Ankush Rayabhari · 发表于：ACM Transactions on Database Systems · 年份：2021 · DOI：10.1145/3464389 · 被引用次数：53 · 研究领域：Data Management and Algorithms、Data Stream Mining Techniques、Advanced Database Systems and Queries

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, P...