# Cuttlefish: A Lightweight Primitive for Adaptive Query Processing

arXiv: https://arxiv.org/abs/1802.09180 · HTML: https://mlsanity.com/paper/1802.09180/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Feb 2018.

## Built on by (most cited first, 4 of 4)

- [No DBA? No regret! Multi-armed bandits for index tuning of analytical and HTAP workloads with provable guarantees](https://mlsanity.com/paper/2108.10130/) (2021)
- [Supporting Dynamic Agentic Workloads: How Data and Agents Interact](https://mlsanity.com/paper/2512.09548/) (2025)
- [Implementing Semantic Join Operators Efficiently](https://mlsanity.com/paper/2510.08489/) (2025)
- [Piece of CAKE: Adaptive Execution Engines via Microsecond-Scale Learning](https://mlsanity.com/paper/2602.04181/) (2026)

## Abstract (arXiv)

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.