Database systems must map queries, describing data to generate, into plans, describing how to generate it. Traditionally, database systems rely on coarse-grained data statistics and simplifying cost and cardinality models to select query plans. This approach is known to be unreliable, resulting all too often in plans with catastrophic execution times. SkinnerDB is designed from the ground up for reliable performance. It uses reinforcement learning to learn optimal query plans from scratch without assuming any prior knowledge about the incoming query or the data it executes on.
SkinnerDB applies intra-query learning to learn optimal plans. This means that we divide the execution of a query into micro-episodes, each episode only lasts for a few tens of microseconds. At the beginning of each episode, a plan is selected and executed for a fixed number of steps. This generates query result fragments that are finally combined into a complete query result. It also yields information about the quality of alternative plans which we leverage to improve plan selections for the coming episodes. We use reinforcement learning to select plans at the beginning of each episode, optimally balancing the need to advance query execution by selecting promising plans (exploitation) and to explore the plan space (exploration). We translate formal guarantees offered by reinforcement learning methods into guarantees on near-optimal expected execution cost. This is only possible due to a specialized execution engine that is tailored to the needs of intra-query learning (such as early quality feedback and low-overhead plan switching).
SkinnerDB was recently presented at SIGMOD 2019 and demoed at VLDB 2018. An early prototype of an ongoing re-implementation effort can be accessed on GitHub.
SkinnerDB: Regret-bounded query evaluation via reinforcement learning. SIGMOD 2019. Immanuel Trummer, Junxiong Wang, Deepak Maram, Samuel Moseley, Saehan Jo, Joseph Antonakakis.
Invited for Best of SIGMOD 2019 (TODS)
Demo: SkinnerDB: Regret-bounded query evaluation via reinforcement learning. VLDB 2018. Immanuel Trummer, Samuel Moseley, Deepak Maram, Saehan Jo, Joseph Antonakakis.
NSF proposal 1910830: Regret-Bounded Query Evaluation via Reinforcement Learning.