# Comprehensive and Efficient Workload Compression

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Nov 2020.

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

- [Real-time Workload Pattern Analysis for Large-scale Cloud Databases](https://mlsanity.com/paper/2307.02626/) (2023)
- ["What makes my queries slow?": Subgroup Discovery for SQL Workload Analysis](https://mlsanity.com/paper/2108.03906/) (2021)
- [ML-Powered Index Tuning: An Overview of Recent Progress and Open Challenges](https://mlsanity.com/paper/2308.13641/) (2023)
- [Budget-aware Query Tuning: An AutoML Perspective](https://mlsanity.com/paper/2404.00137/) (2024)
- [Can Uncertainty Quantification Improve Learned Index Benefit Estimation?](https://mlsanity.com/paper/2410.17748/) (2024)
- [AutoIndexer: A Reinforcement Learning-Enhanced Index Advisor Towards Scaling Workloads](https://mlsanity.com/paper/2507.23084/) (2025)

## Abstract (arXiv)

This work studies the problem of constructing a representative workload from a given input analytical query workload where the former serves as an approximation with guarantees of the latter. We discuss our work in the context of workload analysis and monitoring. As an example, evolving system usage patterns in a database system can cause load imbalance and performance regressions which can be controlled by monitoring system usage patterns, i.e.,~a representative workload, over time. To construct such a workload in a principled manner, we formalize the notions of workload em representativity and em coverage. These metrics capture the intuition that the distribution of features in a compressed workload should match a target distribution, increasing representativity, and include common queries as well as outliers, increasing coverage. We show that solving this problem optimally is NP-hard and present a novel greedy algorithm that provides approximation guarantees. We compare our techniques to established algorithms in this problem space such as sampling and clustering, and demonstrate advantages and key trade-offs of our techniques.