# Fine-Tuning Data Structures for Analytical Query Processing

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 15 of its 91 references that are in the map.
- First posted on arXiv 24 Dec 2021.

## Builds on (most cited first, 15 of 15)

- [A Survey on Compiler Autotuning using Machine Learning](https://mlsanity.com/paper/1801.04405/) (2018)
- [Deep Unsupervised Cardinality Estimation](https://mlsanity.com/paper/1905.04278/) (2019)
- [FAQ: Questions Asked Frequently](https://mlsanity.com/paper/1504.04044/) (2015)
- [Towards Linear Algebra over Normalized Data](https://mlsanity.com/paper/1612.07448/) (2016)
- [A Layered Aggregate Engine for Analytics Workloads](https://mlsanity.com/paper/1906.08687/) (2019)
- [HoTTSQL: Proving Query Rewrites with Univalent SQL Semantics](https://mlsanity.com/paper/1607.04822/) (2016)
- [Building Efficient Query Engines in a High-Level Language](https://mlsanity.com/paper/1612.05566/) (2016)
- [AC/DC: In-Database Learning Thunderstruck](https://mlsanity.com/paper/1803.07480/) (2018)
- [Functional Collection Programming with Semi-Ring Dictionaries](https://mlsanity.com/paper/2103.06376/) (2021)
- [Multi-layer Optimizations for End-to-End Data Analytics](https://mlsanity.com/paper/2001.03541/) (2020)
- [Solving the Join Ordering Problem via Mixed Integer Linear Programming](https://mlsanity.com/paper/1511.02071/) (2015)
- [Stream Fusion, to Completeness](https://mlsanity.com/paper/1612.06668/) (2016)
- [Push vs. Pull-Based Loop Fusion in Query Engines](https://mlsanity.com/paper/1610.09166/) (2016)
- [Towards Automatic Resource Bound Analysis for OCaml](https://mlsanity.com/paper/1611.00692/) (2016)
- [The Case for Deep Query Optimisation](https://mlsanity.com/paper/1908.08341/) (2019)

## Abstract (arXiv)

We introduce a framework for automatically choosing data structures to support efficient computation of analytical workloads. Our contributions are twofold. First, we introduce a novel low-level intermediate language that can express the algorithms behind various query processing paradigms such as classical joins, groupjoin, and in-database machine learning engines. This language is designed around the notion of dictionaries, and allows for a more fine-grained choice of its low-level implementation. Second, the cost model for alternative implementations is automatically inferred by combining machine learning and program reasoning. The dictionary cost model is learned using a regression model trained over the profiling dataset of dictionary operations on a given hardware architecture. The program cost model is inferred using static program analysis. Our experimental results show the effectiveness of the trained cost model on micro benchmarks. Furthermore, we show that the performance of the code generated by our framework either outperforms or is on par with the state-of-the-art analytical query engines and a recent in-database machine learning framework.