Source-linked AI summary
Learning Multi-dimensional Indexes
Vikram Nathan, Jialin Ding, Mohammad Alizadeh, Tim Kraska
TL;DR
Analytical systems need efficient scans and filters over multi-dimensional tables, but existing indexes and sort orders are difficult to tune across datasets and workloads. Flood learns a workload-specific multi-dimensional in-memory layout and index jointly, achieving up to three orders of magnitude faster performance than state-of-the-art alternatives. The paper positions this learned primary index as a building block for larger in-memory database systems.
Problem
Existing multi-dimensional indexes and sort orders are difficult to tune and have inconsistent performance across datasets and query workloads.
Method
Flood automatically co-optimizes an in-memory multi-dimensional index and data layout using the dataset and a sample query workload.
Results
Flood achieves up to three orders of magnitude faster performance than state-of-the-art alternatives, with conclusion-level gains of 30−400× over existing clustered indexes.
Takeaways & Limitations
Learned primary multi-dimensional indexes can substantially improve analytical query performance while using a fraction of the space of optimally tuned spatial indexes.
Takeaways & Limitations
Flood is optimized for reads at the expense of writes and is therefore most suitable for relatively static analytical workloads.
Abstract
from arXiv · showhide
Scanning and filtering over multi-dimensional tables are key operations in modern analytical database engines. To optimize the performance of these operations, databases often create clustered indexes over a single dimension or multi-dimensional indexes such as R-trees, or use complex sort orders (e.g., Z-ordering). However, these schemes are often hard to tune and their performance is inconsistent across different datasets and queries. In this paper, we introduce Flood, a multi-dimensional in-memory index that automatically adapts itself to a particular dataset and workload by jointly optimizing the index structure and data storage. Flood achieves up to three orders of magnitude faster performance for range scans with predicates than state-of-the-art multi-dimensional indexes or sort orders on real-world datasets and workloads. Our work serves as a building block towards an end-to-end learned database system.
1 INTRODUCTION
Multi-dimensional filtering is difficult to optimize because existing indexes and sort orders are workload-sensitive and hard to tune. Flood addresses this by jointly adapting data layout and index structure to the dataset and query distribution, achieving strong performance across evaluated workloads.
- Motivation: Existing clustered column indexes efficiently narrow scans along one filtered attribute, but multi-attribute predicates require broader approaches.Clustered B-Trees and single-attribute sort orders organize data around one attribute; secondary indexes can impose storage and pointer-chasing costs.
- Motivation: Multi-dimensional indexes and sort orders are hard to tune, and no single technique dominates across data distributions and query workloads.The best choice depends on which columns are accessed together and their selectivity.
- Flood: Flood automatically co-optimizes its data layout and index structure for a particular dataset and query distribution.It learns dimension usage, co-usage, and selectivity from sample predicates, then customizes the layout.
- Flood: Flood uses empirical CDF models to flatten skewed multi-dimensional distributions, limiting the number of points searched.Each attribute is modeled with an RMI that maps values to cumulative fractions, enabling efficient grid projection.
- Results: Up to three orders of magnitude faster performance was achieved against state-of-the-art alternatives, often with smaller storage overhead.On a sales dataset, Flood was 3× faster than a tuned clustered column index and 72× faster than Redshift’s Z-encoding; on a TPC-H workload, it was 61× and 3× faster, respectively.
- Results: Flood was evaluated on synthetic and real-world datasets and workloads, with competitive index creation time and speedups across predicates and data sizes.The evaluation included an actual sales workload from a major analytical database company.
2 RELATED WORK
Prior work spans spatial indexes, space-filling sort orders, adaptive indexing, automatic index selection, and learned data structures. Flood differs by learning a multi-dimensional layout from both workload and data distribution rather than adapting only queries or selecting secondary indexes.
- Multi-dimensional indexes: Multi-dimensional indexing includes Z-ordering, R-Trees, k-d trees, octrees, R∗-trees, UB trees, and Grid Files.Commercial systems use several of these alternatives, including Redshift’s Z-order and Informix’s R-Tree.
- Multi-dimensional indexes: Grid Files resemble Flood’s underlying structure but do not automatically adjust to query workload and can grow superlinearly in index size.The cited comparison reports this growth even for uniformly distributed data.
- Adaptive indexing: Database cracking incrementally builds query-adaptive single-dimensional clustered indexes but does not jointly optimize multiple attributes or account for data distribution.These limitations reduce its usefulness for multi-dimensional filters.
- Index selection: Automatic index selection mainly creates secondary indexes, whereas Flood optimizes the storage and index itself for a workload and data distribution.Flood’s distinction is the joint optimization target, not merely choosing among secondary indexes.
- Learned indexes: Flood extends learned indexing to multiple dimensions, where there is no natural sort order for points.Its design is tailored specifically to multi-dimensional data.
3 INDEX OVERVIEW
Flood is a multi-dimensional clustered index that lays out data into grid cells, orders points within cells, and processes range predicates through projection, refinement, and scanning.
- Flood supports relational range queries over one or more attributes joined by ANDs.
- Flood uses an offline preprocessing step to choose an optimal layout and an online component to execute incoming queries.
- Data Layout: Flood overlays a (d−1)-dimensional grid on the first d−1 ranked dimensions, while the remaining dimension orders points within each cell.
- Data Layout: Points are sorted by a depth-first traversal of cells and then by the sort dimension within each cell.
- Query Processing: Queries identify intersecting cells, refine their physical ranges when possible, and scan the resulting ranges to process matching records.
4 OPTIMIZING THE GRID
Flood optimizes grid parameters and sort-dimension choice with a learned cost model that captures workload, layout, and data-dependent scan behavior.
- Layout Optimization: Flood tunes column counts and the sort dimension because their optimal values depend on workload selectivities, dimensional correlations, and data layout.
- Layout Optimization: More columns reduce unnecessary scanned points but increase visited cells and projection and refinement costs, creating a layout trade-off.
- Cost Model: Flood models query time as projection, refinement, and scan costs weighted by data-, query-, and layout-dependent parameters.
- Cost Model: The layout objective minimizes average modeled query time across the workload, using statistics such as cells and scanned points as model features.
- Cost Model: Query time is difficult to model analytically because its variables interact nonlinearly; the machine-learning cost model has 9× and 4× smaller average error than the stated alternatives.
- Layout Optimization: Flood optimizes candidate layouts using sampled data and workload statistics without rebuilding layouts, sorting the dataset, or running queries at every gradient-descent iteration.
5 LEARNING FROM THE DATA
Flood learns data-aware layouts by flattening skewed dimensions and refining cells with learned CDF models, while acknowledging limitations from cross-dimensional correlations.
- Learning from the Data: Flood learns attribute distributions to space columns more effectively and models data within cells to accelerate refinement.
- Flattening: Recursive Model Indexes estimate each attribute’s CDF so columns contain approximately equal numbers of points in the transformed space.
- Flattening: Flattening provides a 20−30× performance boost over a non-flattened layout on two evaluation datasets.
- Limitations: Independent flattening does not guarantee uniform final-grid cells when dimensions are correlated, although additional columns and cell pruning can mitigate overhead.
- Cell Refinement: Flood refines each cell’s physical range with a piecewise linear CDF model and corrects prediction errors through local search.
- Cell Refinement: The piecewise linear model lower-bounds true CDF positions and limits each segment’s average absolute error to a threshold δ.
6 DISCUSSION
Flood’s discussion contrasts its adaptive grid design with alternative indexes, emphasizing low space and lookup overhead while identifying excluded query types and unresolved correlation modeling.
- Alternatives to grids: Flood’s grid uses less than 1kB, compared with 10MB to 1GB for other multidimensional indexes.The small grid leaves room for per-cell models.
- Alternatives to grids: On TPC-H, Flood with flattening identifies relevant grid cells in 0.46ms, versus 8.9ms for k-d trees and 1.8ms for hyperoctrees.These correspond to 20× and 4× longer lookup times, respectively.
- Nearest Neighbor Queries: Flood excludes k-nearest-neighbor queries because the paper focuses on non-geospatial analytics.Its grid can locate adjacent cells, allowing a similar kNN algorithm.
- Multi-dimensional CDFs: Flood does not use multidimensional CDFs because monotonic partitioning is difficult and conditional CDFs increased index size without significant benchmark gains.Efficiently modeling correlations across more dimensions remains an active research area.
7 EVALUATION
The evaluation compares Flood with multiple indexing and scanning approaches across real-world and synthetic datasets using range and equality workloads. Flood is faster than or comparable to every tested index, often uses less space, and adapts quickly, while evaluation remains focused on range filters rather than full database workloads.
- Results: Flood is faster than or on par with every other tested index, although the next-best index varies by dataset.The evaluation covers several indexing methods across varied datasets and workloads.
- Results: Flood is up to 187× faster than a clustered single-dimensional index, 62× faster than GridFile, and 72× faster than Z-order.It is also up to 250× faster than UB-tree, 43× faster than hyperoctree, and 48× faster than k-d tree or R-tree.
- Results: Flood’s index can use up to 50× less space than the next fastest index.This is reported as an overall evaluation result.
- Results: Flood can retrain its layout and reorganize records for a new query distribution, typically in under a minute for 300 million records.The system was not optimized specifically for dynamic workloads.
- Results: Flood’s performance advantage over baseline indexes increases with larger datasets and higher-selectivity queries.The evaluation includes three real-world and one synthetic dataset, with range and equality filters.
- Scope: The study evaluates Flood as a range-filter index component, excluding joins, group-bys, and other complex query operators.The authors note that broader full-query evaluation would require major changes to open-source column stores.
7.4 Results
Flood consistently outperforms tuned baseline indexes across datasets and workloads, while adapting its layout automatically to changing query characteristics. Its gains come primarily from learning the workload and, for skewed data, flattening the layout.
- Flood achieves between 2.4× and 3.3× query-time speedup over the next closest index on three datasets and is never slower than that baseline.
- Flood beats the Pareto frontier of other multi-dimensional indexes on every dataset, including a more than 20× smaller index than the hyperoctree on OSM.
- Flood achieves more than 20× speedup on half the TPC-H workloads, while its median improvement on OSM is 2.2×.
- Dynamic Query Workload Changes: Flood’s automatic workload adaptation yields a median improvement above 5× over the closest competitor, with 30% of queries exceeding 10× speedup.
- Dynamic Query Workload Changes: Relearning the layout after workload transitions restores query time below competing indexes, showing that query-workload learning is crucial to Flood’s gains.
- Performance Breakdown: Flood lowers scan overhead on three of four datasets and usually reduces time per scanned point, offsetting its higher index time.
- Performance Breakdown: Flattening and workload learning provide the largest component-level improvements, while flattening helps most on heavily skewed datasets.
7.5 Scalability
Flood scales across dataset sizes, query selectivities, and dimensions, while its cost model balances scan overhead against index-processing cost. Sampling data or queries reduces learning effort while preserving low query times.
- Dataset Size: Flood’s query time grows sub-linearly as dataset size increases because additional cells reduce scan overhead more than they increase cell-processing cost.
- Query Selectivity: Flood performs well from 0.001% to 10% query selectivity, although its advantage is less apparent at 10% because all indexes scan more efficiently.
- Number of Dimensions: Flood continues to outperform baseline indexes at higher dimensions, prioritizing frequently filtered dimensions rather than indexing every dimension.
- Finding the Optimum: Flood’s cost model selects the grid size minimizing total query time by balancing lower scan overhead against higher index time.
- Robustness of the model: Cost-model weights transfer across datasets, producing similar query times and often less than 10% variation without retraining for every dataset.
- Index Creation and Sampling: Flood’s total index creation time is competitive with baseline indexes, while sampling 0.01–1% of records or 5% of queries preserves low query times.
- CDF Models: The piecewise-linear model and RMI outperform binary search by up to 4×, and Flood uses the piecewise-linear model because it has a single tuning parameter.
8 FUTURE WORK
Future work targets workload-change detection, incremental layout adjustment, insertions, and parallel execution. These extensions address current boundaries in adaptation, mutability, and execution model.
- Shifting Workloads: Flood adapts quickly to workload changes but cannot currently detect when a new layout is warranted.
- Shifting Workloads: Flood completely rebuilds its index for each new workload, motivating incremental adjustments such as splitting or coalescing columns.
- Insertions: Flood currently supports only read-only workloads, with insertion support proposed through cell gaps or a buffered delta index.
- Concurrency and parallelism: Flood is currently single-threaded, although cells, records, and dense column arrays could support parallelism and SIMD.
9 CONCLUSION
Flood is a learned primary multi-dimensional index that jointly optimizes storage order and index structure using data and query workloads. It substantially outperforms clustered and spatial indexes while using less space.
- Flood serves as the primary index and storage order for the underlying data, jointly optimized using the data and query workloads.
- Flood outperforms existing clustered indexes by 30−400× and beats optimally tuned spatial indexes while using a fraction of their space.
- The results position learned primary multi-dimensional indexes as building blocks for larger in-memory database systems.
A INDEX IMPLEMENTATION DETAILS
The implemented indexes accept per-dimension filter ranges and a Visitor for aggregation statistics, then scan only dimension columns. Their layouts differ in how they partition, order, and store points.
- Queries provide start and end values for every dimension, using negative and positive infinity when a dimension is unfiltered.
- Experiments use aggregation queries, with a Visitor object accumulating the aggregation statistic.
- Clustered Single-Dimensional Index: The clustered single-dimensional index uses a three-layer linear-model RMI, with 1, √n, and n experts across the layers.The leaf layer uses linear regressions, while non-leaf layers use linear spline models to preserve monotonicity.
- Grid File: Grid File buckets store points contiguously but unsorted, so accessing one record requires scanning its entire bucket.The grid starts as one block and splits buckets when they reach a user-defined page size.
- Z-order: Z-order pages are skipped by comparing each page’s minimum Z-order value with the target Z-order value.
- Hyperoctree and k-d tree: Hyperoctrees recursively split d-dimensional hyperoctants until pages contain fewer than the page-size point limit, storing pages contiguously in tree order.The described k-d-tree layout similarly stores contiguous pages ordered by an in-order traversal, with round-robin splits prioritized by decreasing selectivity.
B OPTIMIZATION PSEUDOCODE
Algorithm 1 searches for a low-cost data layout using a calibrated query-time model. It evaluates dimension orders and optimizes grid-column counts before returning the best layout found.
- The procedure takes a d-dimensional dataset, query workload, and cost model, and returns a layout containing dimension order and grid-column counts.The cost model maps the dataset, query, and layout to query time.
- Samples of the dataset and workload are flattened by replacing each dimension value with its corresponding CDF value from an RMI.
- Dimensions are ordered by decreasing average query selectivity on the sampled dataset.
- The algorithm considers each dimension as the sort dimension while preserving the remaining dimensions’ relative order.
- For each fixed dimension order, gradient descent searches for grid-column counts minimizing average modeled cost over sampled queries.
- The procedure retains the layout with the lowest found cost and returns it after evaluating all candidate sort dimensions.