Source-linked AI summary
Tsunami: A Learned Multi-dimensional Index for Correlated Data and Skewed Workloads
Jialin Ding, Vikram Nathan, Mohammad Alizadeh, Tim Kraska
TL;DR
Existing multi-dimensional indexes are difficult to tune and can perform inconsistently, while learned indexes struggle with correlated data and skewed workloads. Tsunami addresses these limitations with workload-aware data organization and two modular structures, achieving up to 6× higher query throughput and 8× lower space than existing learned multi-dimensional indexes.
Problem
Multi-dimensional indexes require repeated manual tuning, and learned multi-dimensional indexes struggle with correlated datasets and skewed query workloads.
Method
Tsunami is an in-memory read-optimized learned multi-dimensional index using Grid Tree partitioning for query skew and Augmented Grids with functional mappings or conditional CDFs for correlations.
Results
Up to 6× higher query throughput and 8× lower space than existing learned multi-dimensional indexes are reported for Tsunami.
Takeaways & Limitations
Tsunami moves toward a robust learned multi-dimensional index that can serve as a building block in larger in-memory database systems.
Takeaways & Limitations
Flood, the prior system addressed by Tsunami, degrades on non-uniform queries because its uniform grid cannot optimize independently for skewed query regions.
Abstract
from arXiv · showhide
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.
1 INTRODUCTION
Traditional multi-dimensional indexes are difficult to tune and can perform inconsistently, while Flood's learned approach struggles with correlated data and skewed workloads. Tsunami addresses these limitations with workload-optimized structures and reports substantial performance gains over learned and traditional indexes.
- Motivation: Multi-dimensional indexes require manual choices about indexed dimensions and ordering, and no single approach dominates across workloads.These decisions must be revisited when data or workloads change.
- Limitations of prior work: Flood automatically optimizes its layout for a dataset and workload, but its grid cannot efficiently adapt to skewed queries or correlated dimensions.Correlations can prevent uniformly sized cells, degrading performance and memory usage.
- Tsunami: Tsunami combines a Grid Tree for reducing query skew with an Augmented Grid that captures correlations using functional mappings and conditional CDFs.The index also automatically optimizes data storage organization and index structure based on the data and workload.
- Scope: Tsunami is designed as an in-memory, read-optimized clustered index for analytics workloads that increasingly favor incremental merges over in-place updates.The paper positions it as a possible building block for larger in-memory database systems.
- Results: 6× faster query performance is achieved by Tsunami than Flood, while Tsunami also adapts to workload shift and scales across data size, selectivity, and dimensionality.The evaluation uses real datasets and varied workloads, including traditional non-learned indexes.
2 BACKGROUND
Traditional multi-dimensional indexes are workload-independent and difficult to tune, while Flood learns a compact workload-aware grid but struggles with skewed workloads and correlated data. Tsunami aims to retain Flood’s compact, adaptive indexing while addressing those limitations.
- Tsunami targets range-predicate filtering for analytical queries using an in-memory clustered multi-dimensional index.The index is designed for a single table and read-optimized analytics.
- Traditional indexes construct partitions from data distribution rather than query workload, so their structure does not adapt to query frequency or selectivity.The k-d tree uses recursive median-based splits and stores points in each leaf region contiguously.
- Flood automatically tunes a grid for a workload and uses compact CDF models to locate intersecting cells with lower space and traversal overhead than tree indexes.Its query workflow identifies intersecting partitions, maps cells to physical ranges, and scans those ranges.
- Up to three orders of magnitude higher performance and 50× smaller index size are reported for Flood versus non-learned indexes.
- Flood’s uniform grid underperforms on skewed workloads because optimizing the average query cannot independently prioritize distinct query regions.Query skew is common when recent data or extreme metric values are queried more frequently.
- Correlated dimensions can create unequally sized Flood cells, degrading performance and space usage despite equal marginal partition sizes.Examples include correlations between taxi-ride price and distance and between package shipping and receipt dates.
- Tsunami seeks to preserve workload optimization and compact model-based indexing while addressing correlation and query-skew limitations.
3 TSUNAMI DESIGN OVERVIEW
Tsunami combines a Grid Tree for query-skewed space partitioning with region-specific Augmented Grids for correlated data. Its offline optimizer tunes both structures using the dataset and workload, while queries traverse regions, locate cells, and scan physical ranges.
- Tsunami is a learned multi-dimensional index designed to be robust to data correlation and query skew.
- The Grid Tree partitions data space into non-overlapping regions, while each selected region receives an Augmented Grid.Regions without intersecting queries need not receive an Augmented Grid.
- Augmented Grids extend Flood’s structure with functional mappings and conditional CDFs to capture correlations.
- Tsunami processes each query by traversing the Grid Tree, finding intersecting Augmented Grid cells, mapping them to physical ranges, and scanning matching points.
- Offline optimization first tunes the Grid Tree on the full dataset and workload, then tunes each regional Augmented Grid on its intersecting points and queries.
- The Grid Tree and Augmented Grid separately address query skew and data correlation, respectively.
- A single grid cannot efficiently index the running skewed workload, whereas non-overlapping regional grids can tailor indexing to different query regions.
4 GRID TREE
Tsunami’s Grid Tree addresses query skew by partitioning data space into non-overlapping regions whose local workloads are less skewed. It defines skew from query distributions, clusters query types, and greedily selects split dimensions and values before indexing regions separately.
- Motivation: Query skew occurs when query frequency or selectivity varies across different parts of the data space.The Grid Tree targets this variation so regions can use indexing schemes suited to their local workloads.
- Definition of Query Skew: Query skew is measured independently for each query type as the Earth Mover’s Distance between empirical and uniform query distributions.Each query contributes unit mass spread across its filter range in a dimension; histograms approximate the resulting distribution in practice.
- Grid Tree Design: The Grid Tree partitions space into non-overlapping regions so each region has little query skew, while remaining lightweight and allowing any intra-region index.Its nodes can split on multiple values, producing multiple children; queries traverse intersecting regions, and unindexed regions are scanned.
- Optimizing the Grid Tree: The optimizer greedily chooses the dimension and split values that maximize skew reduction, stopping when skew or data/query coverage falls below thresholds.It evaluates the largest reduction independently for each dimension, then selects the dimension with the greatest reduction; the default skew threshold is 5% of |Q|.
- Clustering Query Types: Queries are clustered into types using filtered dimensions and selectivity characteristics because aggregate skew can cancel across different query types.Queries filtering different dimension sets are separated automatically, while DBSCAN clusters embeddings of selectivities for shared dimension sets.
- Selecting Split Values: A skew tree uses dynamic programming to find a covering set with minimum combined skew, whose boundaries provide candidate split values.A later merge step removes superfluous splits when combined skew rises by no more than the default 10% factor.
5 AUGMENTED GRID
The Augmented Grid addresses correlated data by partitioning dimensions dependently, using functional mappings for tight monotonic correlations and conditional CDFs for generic correlations. Tsunami optimizes the resulting grid’s skeleton and partition counts for workload query time.
- Correlated dimensions create uneven grid cells when partitioned independently, causing queries to scan excess points.
- Tsunami partitions dimensions dependently to preserve the time and space advantages of grids under correlation.
- An Augmented Grid combines a partitioning skeleton with per-dimension partition counts to define a concrete index.
- Functional mappings remove a mapped dimension by transforming its predicates into semantically equivalent filters on another dimension.
- Conditional CDFs partition dependent dimensions using CDF(X |Y), producing equally-sized cells for loose monotonic or generic correlations.
- Adaptive gradient descent jointly optimizes the skeleton and partition counts for the lowest predicted average query time.
6 EVALUATION
Across tested datasets and workloads, Tsunami was the fastest index and used less space than Flood and optimally tuned non-learned indexes. It also adapted to workload changes and retained advantages across scale, selectivity, and dimensionality.
- Tsunami was consistently the fastest index across the evaluated datasets and workloads.
- 6× higher query throughput than Flood and 11× higher query throughput than the fastest optimally-tuned non-learned index were achieved.
- Tsunami had up to 8× smaller index size than Flood and up to 170× smaller index size than the fastest non-learned index.
- Tsunami quickly re-optimized its layout and reorganized records after query-workload changes, with total index creation remaining below 4 minutes on the largest datasets.
- On correlated datasets, Tsunami achieved performance comparable to an uncorrelated dataset with four fewer dimensions.
- Tsunami’s performance advantage persisted across dataset sizes and query selectivities, although aggregation became a bottleneck at 10% selectivity.
- Grid Tree contributed most to performance, while Augmented Grid also significantly improved performance over Flood.
- The cost model’s average prediction error across optimized configurations was 15%.
7 RELATED WORK
Related work spans traditional multi-dimensional indexes, learned indexes, correlation-aware techniques, and workload-skew methods. Tsunami differs by jointly learning from data and query workloads while cooptimizing index structure and data storage.
- Traditional systems use structures such as Z-order indexes, k-d trees, octrees, R-trees, UB trees, and Grid Files.
- Prior learned indexes mainly extend learned-model ideas to spatial and multi-dimensional data, including Flood, Qd-tree, and LISA.
- ZM-index and ML-index learn from data distributions but do not learn from query workloads.
- Correlation-focused systems discover dependencies or reduce secondary-index size, whereas Tsunami applies correlation to clustered multi-dimensional indexing.
- Tsunami automatically partitions data space with a Grid Tree to account for query skew instead of relying on caches for frequently accessed keys.
8 FUTURE WORK
Future work extends Tsunami’s handling of correlations, categorical dimensions, workload shifts, updates, and persistent storage. Key directions include stronger correlation-aware partitioning, adaptive re-optimization, buffered updates, and disk- or SSD-resident indexes.
- Complex Correlations: Functional mappings are not robust to outliers, while Augmented Grid may miss temporal, periodic, and higher-dimensional functional-dependency correlations.Proposed directions include buffering outliers separately and introducing new correlation-aware partitioning strategies.
- Categorical dimensions: Categorical values can be sorted by co-access frequency so commonly queried values share grid partitions and require fewer scans.
- Data and Workload Shift: Tsunami lacks automatic detection of workload changes that would trigger re-optimization and currently re-optimizes the entire workload.Future approaches could detect changing query types or regional skew and incrementally re-optimize the most affected Augmented Grids.
- Updates: Tsunami supports only read-only workloads; sibling delta indexes could buffer updates before periodically merging them into the main nodes.
- Persistence: Tsunami’s skew-reduction and correlation-handling techniques could be incorporated into indexes for data stored on disk or SSD.Potential integrations include ideas from qd-tree or LISA.
9 CONCLUSION
Tsunami is an in-memory learned multi-dimensional index designed to adapt automatically to data correlations and query skew. Its Grid Tree and Augmented Grid improve query throughput and space usage relative to existing learned indexes.
- Tsunami automatically adapts a learned multi-dimensional index to data correlations and query skew.
- Grid Tree and Augmented Grid are modular data structures that support Tsunami’s performance improvements.
- Up to 6× higher query throughput and 8× lower space usage are reported compared with existing learned multi-dimensional indexes.