# Tsunami: A Learned Multi-dimensional Index for Correlated Data and Skewed Workloads

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

## Key facts

- Cited by 25 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Jun 2020.

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

- [A Unified Transferable Model for ML-Enhanced DBMS](https://mlsanity.com/paper/2105.02418/) (2021)
- [One Model to Rule them All: Towards Zero-Shot Learning for Databases](https://mlsanity.com/paper/2105.00642/) (2021)
- [CARMI: A Cache-Aware Learned Index with a Cost-based Construction Algorithm](https://mlsanity.com/paper/2103.00858/) (2021)
- [Detect, Distill and Update: Learned DB Systems Facing Out of Distribution Data](https://mlsanity.com/paper/2210.05508/) (2022)
- [WISK: A Workload-aware Learned Index for Spatial Keyword Queries](https://mlsanity.com/paper/2302.14287/) (2023)
- [A Learned Index for Exact Similarity Search in Metric Spaces](https://mlsanity.com/paper/2204.10028/) (2022)
- [A Survey of Learned Indexes for the Multi-dimensional Space](https://mlsanity.com/paper/2403.06456/) (2024)
- [Accelerating String-Key Learned Index Structures via Memoization-based Incremental Training](https://mlsanity.com/paper/2403.11472/) (2024)
- [Towards Practical Learned Indexing](https://mlsanity.com/paper/2108.05117/) (2021)
- [NFL: Robust Learned Index via Distribution Transformation](https://mlsanity.com/paper/2205.11807/) (2022)
- [A Reinforcement Learning Based R-Tree for Spatial Data Indexing in Dynamic Environments](https://mlsanity.com/paper/2103.04541/) (2021)
- [Learned-Database Systems Security](https://mlsanity.com/paper/2212.10318/) (2022)
- [A Pluggable Learned Index Method via Sampling and Gap Insertion](https://mlsanity.com/paper/2101.00808/) (2021)
- [The "AI+R"-tree: An Instance-optimized R-tree](https://mlsanity.com/paper/2207.00550/) (2022)
- [Compressing (Multidimensional) Learned Bloom Filters](https://mlsanity.com/paper/2208.03029/) (2022)
- [LotusFilter: Fast Diverse Nearest Neighbor Search via a Learned Cutoff Table](https://mlsanity.com/paper/2506.04790/) (2025)
- [Mathematical Foundations of Poisoning Attacks on Linear Regression over Cumulative Distribution Functions](https://mlsanity.com/paper/2603.00537/) (2026)
- [Testing the Robustness of Learned Index Structures](https://mlsanity.com/paper/2207.11575/) (2022)
- [Learned k-NN Distance Estimation](https://mlsanity.com/paper/2208.14210/) (2022)
- [Learned spatial data partitioning](https://mlsanity.com/paper/2306.04846/) (2023)
- [Sig2Model: A Boosting-Driven Model for Updatable Learned Indexes](https://mlsanity.com/paper/2509.20781/) (2025)
- [Optimized Learned Count-Min Sketch](https://mlsanity.com/paper/2512.12252/) (2025)
- [Lower Bounds for the Algorithmic Complexity of Learned Indexes](https://mlsanity.com/paper/2601.06629/) (2026)
- [Piece of CAKE: Adaptive Execution Engines via Microsecond-Scale Learning](https://mlsanity.com/paper/2602.04181/) (2026)
- [M-CTX: Exact and Scalable Spatial Context Retrieval for Trajectory Analytics](https://mlsanity.com/paper/2606.15244/) (2026)

## Abstract (arXiv)

Filtering data based on predicates is one of the most fundamental operations for any modern data warehouse. Techniques to accelerate the execution of filter expressions include clustered indexes, specialized sort orders (e.g., Z-order), multi-dimensional indexes, and, for high selectivity queries, secondary indexes. However, these schemes are hard to tune and their performance is inconsistent. Recent work on learned multi-dimensional indexes has introduced the idea of automatically optimizing an index for a particular dataset and workload. However, the performance of that work suffers in the presence of correlated data and skewed query workloads, both of which are common in real applications. In this paper, we introduce Tsunami, which addresses these limitations to achieve up to 6X faster query performance and up to 8X smaller index size than existing learned multi-dimensional indexes, in addition to up to 11X faster query performance and 170X smaller index size than optimally-tuned traditional indexes.