Learning Multi-dimensional Indexes

Abstract

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.

Cited by in corpus (12)

• ALEX: An Updatable Adaptive Learned Index
• Qd-tree: Learning Data Layouts for Big Data Analytics
• Are Updatable Learned Indexes Ready?
• APEX: A High-Performance Learned Index on Persistent Memory
• LMSFC: A Novel Multidimensional Index based on Learned Monotonic Space Filling Curves
• Updatable Learned Indexes Meet Disk-Resident DBMS -- From Evaluations to Design Choices
• Accelerating String-Key Learned Index Structures via Memoization-based Incremental Training
• LeaFi: Data Series Indexes on Steroids with Learned Filters
• Blueprinting the Cloud: Unifying and Automatically Optimizing Cloud Data Infrastructures with BRAD -- Extended Version
• A Learning-Based Caching Mechanism for Edge Content Delivery
• DeepMapping: Learned Data Mapping for Lossless Compression and Efficient Lookup
• LES3: Learning-based Exact Set Similarity Search