Dynamic Data Layout Optimization with Worst-case Guarantees
Preprint
Abstract
Many data analytics systems store and process large datasets in partitions containing millions of rows. By mapping rows to partitions in an optimized way, it is possible to improve query performance by skipping over large numbers of irrelevant partitions during query processing. This mapping is referred to as a data layout. Recent works have shown that customizing the data layout to the anticipated query workload greatly improves query performance, but the performance benefits may disappear if the workload changes. Reorganizing data layouts to accommodate workload drift can resolve this issue, but reorganization costs could exceed query savings if not done carefully. In this paper, we present an algorithmic framework OReO that makes online reorganization decisions to balance the benefits of improved query performance with the costs of reorganization. Our framework extends results from Metrical Task Systems to provide a tight bound on the worst-case performance guarantee for online reorganization, without prior knowledge of the query workload. Through evaluation on real-world datasets and query workloads, our experiments demonstrate that online reorganization with OReO can lead to an up to 32% improvement in combined query and reorganization time compared to using a single, optimized data layout for the entire workload.Keywords
All Related Versions
This publication has 14 references indexed in Scilit:
- SAT: sampling acceleration tree for adaptive database repartitionWorld Wide Web, 2023
- PAW: Data Partitioning Meets Workload Variance2022
- Metrical Task Systems on Trees via Mirror Descent and Unfair GluingSIAM Journal on Computing, 2021
- Learning a Partitioning Advisor for Cloud Databases2020
- Spark SQL2015
- Learning-based Query Performance Modeling and Prediction2012
- A tight bound on approximating arbitrary metrics by tree metricsJournal of Computer and System Sciences, 2004
- Better Algorithms for Unfair Metrical Task Systems and ApplicationsSIAM Journal on Computing, 2003
- Randomized algorithms for metrical task systemsTheoretical Computer Science, 1998
- An optimal on-line algorithm for metrical task systemJournal of the ACM, 1992