# Qd-tree: Learning Data Layouts for Big Data Analytics

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

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Apr 2020.

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

- [DB-BERT: a Database Tuning Tool that "Reads the Manual"](https://mlsanity.com/paper/2112.10925/) (2021)
- [High-Throughput Vector Similarity Search in Knowledge Graphs](https://mlsanity.com/paper/2304.01926/) (2023)
- [A Survey on Deep Reinforcement Learning for Data Processing and Analytics](https://mlsanity.com/paper/2108.04526/) (2021)
- [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)
- [Towards Effective Next POI Prediction: Spatial and Semantic Augmentation with Remote Sensing Data](https://mlsanity.com/paper/2404.04271/) (2024)
- [HONEYBEE: Efficient Role-based Access Control for Vector Databases via Dynamic Partitioning[Technical Report]](https://mlsanity.com/paper/2505.01538/) (2025)
- [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)
- [ML-Powered Index Tuning: An Overview of Recent Progress and Open Challenges](https://mlsanity.com/paper/2308.13641/) (2023)
- [Benchmarking Filtered Approximate Nearest Neighbor Search Algorithms on Transformer-based Embedding Vectors](https://mlsanity.com/paper/2507.21989/) (2025)
- [The "AI+R"-tree: An Instance-optimized R-tree](https://mlsanity.com/paper/2207.00550/) (2022)
- [Dynamic Data Layout Optimization with Worst-case Guarantees](https://mlsanity.com/paper/2405.04984/) (2024)
- [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)
- [M-CTX: Exact and Scalable Spatial Context Retrieval for Trajectory Analytics](https://mlsanity.com/paper/2606.15244/) (2026)
- [Smart Compaction: Predicting Compaction Utility from Lakehouse Table Metadata](https://mlsanity.com/paper/2608.08639/) (2026)

## Abstract (arXiv)

Corporations today collect data at an unprecedented and accelerating scale, making the need to run queries on large datasets increasingly important. Technologies such as columnar block-based data organization and compression have become standard practice in most commercial database systems. However, the problem of best assigning records to data blocks on storage is still open. For example, today's systems usually partition data by arrival time into row groups, or range/hash partition the data based on selected fields. For a given workload, however, such techniques are unable to optimize for the important metric of the number of blocks accessed by a query. This metric directly relates to the I/O cost, and therefore performance, of most analytical queries. Further, they are unable to exploit additional available storage to drive this metric down further. In this paper, we propose a new framework called a query-data routing tree, or qd-tree, to address this problem, and propose two algorithms for their construction based on greedy and deep reinforcement learning techniques. Experiments over benchmark and real workloads show that a qd-tree can provide physical speedups of more than an order of magnitude compared to current blocking schemes, and can reach within 2X of the lower bound for data skipping based on selectivity, while providing complete semantic descriptions of created blocks.