Cuttlefish: A Lightweight Primitive for Adaptive Query Processing
arXiv:1802.09180
Abstract
Modern data processing applications execute increasingly sophisticated analysis that requires operations beyond traditional relational algebra. As a result, operators in query plans grow in diversity and complexity. Designing query optimizer rules and cost models to choose physical operators for all of these novel logical operators is impractical. To address this challenge, we develop Cuttlefish, a new primitive for adaptively processing online query plans that explores candidate physical operator instances during query execution and exploits the fastest ones using multi-armed bandit reinforcement learning techniques. We prototype Cuttlefish in Apache Spark and adaptively choose operators for image convolution, regular expression matching, and relational joins. Our experiments show Cuttlefish-based adaptive convolution and regular expression operators can reach 72-99% of the throughput of an all-knowing oracle that always selects the optimal algorithm, even when individual physical operators are up to 105x slower than the optimal. Additionally, Cuttlefish achieves join throughput improvements of up to 7.5x compared with Spark SQL's query optimizer.
References in corpus (9)
- Show, Attend and Tell: Neural Image Caption Generation with Visual Attention
- Analysis of Thompson Sampling for the multi-armed bandit problem
- Thompson Sampling for Contextual Bandits with Linear Payoffs
- Further Optimal Regret Bounds for Thompson Sampling
- Fast Training of Convolutional Networks through FFTs
- Distributed Clustering of Linear Bandits in Peer to Peer Networks
- Thompson Sampling for 1-Dimensional Exponential Family Bandits
- A Survey of Online Experiment Design with the Stochastic Multi-Armed Bandit
- Optimality of Thompson Sampling for Gaussian Bandits Depends on Priors