  Query optimization remains one of the most challenging problems in data
management systems. Recent efforts to apply machine learning techniques to
query optimization challenges have been promising, but have shown few practical
gains due to substantive training overhead, inability to adapt to changes, and
poor tail performance. Motivated by these difficulties and drawing upon a long
history of research in multi-armed bandits, we introduce Bao (the BAndit
Optimizer). Bao takes advantage of the wisdom built into existing query
optimizers by providing per-query optimization hints. Bao combines modern tree
convolutional neural networks with Thompson sampling, a decades-old and
well-studied reinforcement learning algorithm. As a result, Bao automatically
learns from its mistakes and adapts to changes in query workloads, data, and
schema. Experimentally, we demonstrate that Bao can quickly (an order of
magnitude faster than previous approaches) learn strategies that improve
end-to-end query execution performance, including tail latency. In cloud
environments, we show that Bao can offer both reduced costs and better
performance compared with a sophisticated commercial system.
