SkinnerDB: Regret Bounded Query Evaluation using RL

Опубликовано 12 августа 2020, 17:41

Query plans are typically selected based on coarse-grained data statistics and simplifying cost and cardinality models. This approach is brittle and the most common cause of highly suboptimal performance in practice. SkinnerDB eschews statistics and models in favor of "intra-query learning": a principled "learning by doing" approach, based on reinforcement learning.

SkinnerDB does not learn from past queries to optimize the next (inter-query learning). Instead, it divides the execution of one single query into hundreds of thousands of micro-episodes. By trying different plans in different episodes, SkinnerDB learns optimal, query-specific plans from scratch. By selecting plans based on sound statistical principles, balancing exploration and exploitation, SkinnerDB guarantees near-optimal expected execution time. Execution ends once result fragments can be combined into a complete result.
Intra-query learning requires a specialized execution engine. We need to facilitate fast plan switches, avoid plan-specific intermediate results, and obtain unbiased quality estimates after executing plans only for a few steps. In this talk, I will introduce the basic principles behind intra-query learning, discuss SkinnerDB and our specialized execution engine, and present experimental results for our latest prototype.

See more at microsoft.com/en-us/research/v...