DTLI: Distribution transformation-based lightweight learned indexing for data lakehouse query optimization

Area of Science:

• Data Science
• Database Systems
• Machine Learning

Background:

• Modern analytical platforms like data lakehouses experience query performance bottlenecks due to massive data growth.
• Traditional and existing learned indexes struggle to balance query efficiency with lightweight structures.

Purpose of the Study:

• To propose DTLI, a novel lightweight learned index architecture based on distribution transformation.
• To address the limitations of existing indexing methods in large-scale data environments.

Main Methods:

• Systematic evaluation of generative models (VAE, Normalizing Flow, Diffusion Model) for distribution transformation.
• Selection of Block Neural Autoregressive Flow (B-NAF) to map complex data distributions to near-uniform ones.
• Development of a changepoint-based piecewise fitting algorithm for cumulative distribution functions, creating a minimal binary tree index.
• Design of local and global indexing strategies tailored for data lakehouse partitioning and integration with Apache Hudi.

Main Results:

• DTLI significantly outperforms native indexes (B+Tree) and learned indexes (RMI, PGM, NFL) across various datasets.
• DTLI achieves an average throughput increase of 72.55% over B+Tree and reduces 99th percentile tail latency by 57.52%.
• Distribution transformation alone improves existing index throughput by over 38%.

Conclusions:

• DTLI offers a lightweight and efficient solution for indexing in data lakehouses, improving query performance.
• The proposed distribution transformation technique shows promise for enhancing existing indexing methods.
• Future work includes extending DTLI to multi-dimensional/non-numerical data and developing incremental update mechanisms.