Piece of CAKE: Adaptive Execution Engines via Microsecond-Scale Learning
This addresses performance inefficiencies in database systems for users dealing with dynamic data workloads, representing a novel method rather than an incremental improvement.
The paper tackles the problem of selecting optimal low-level database kernels for varying data distributions, which static heuristics often miss, by proposing CAKE, a system that uses microsecond-scale contextual multi-armed bandits to learn kernel selection, reducing end-to-end workload latency by up to 2x compared to state-of-the-art static heuristics.
Low-level database operators often admit multiple physical implementations ("kernels") that are semantically equivalent but have vastly different performance characteristics depending on the input data distribution. Existing database systems typically rely on static heuristics or worst-case optimal defaults to select these kernels, often missing significant performance opportunities. In this work, we propose CAKE (Counterfactual Adaptive Kernel Execution), a system that learns to select the optimal kernel for each data "morsel" using a microsecond-scale contextual multi-armed bandit. CAKE circumvents the high latency of traditional reinforcement learning by exploiting the cheapness of counterfactuals -- selectively running multiple kernels to obtain full feedback -- and compiling policies into low-latency regret trees. Experimentally, we show that CAKE can reduce end-to-end workload latency by up to 2x compared to state-of-the-art static heuristics.