Dynamic Data Layout Optimization with Worst-case Guarantees
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.
Code (1)
Similar Papers 제목 키워드 기반
Monotonic Robust Policy Optimization with Model Discrepancy
State-of-the-art deep reinforcement learning (DRL) algorithms tend to overfit in some specific environments due to the lack of data diversity in training. To mitigate the model discrepancy between training and target (te…
Deep Reinforcement LearningDiversitymodelWarehouse Layout Method Based on Ant Colony and Backtracking Algorithm
Warehouse is one of the important aspects of a company. Therefore, it is necessary to improve Warehouse Management System (WMS) to have a simple function that can determine the layout of the storage goods. In this paper …
ManagementFinite Horizon Worst-Case Analysis of Linear Time-Varying Systems Applied to Launch Vehicle
This paper presents an approach to compute the worst-case gain of the interconnection of a finite time horizon linear time-variant system and a perturbation. The input/output behavior of the uncertainty is described by i…
Real-Time Dynamic Layout Optimization for Floating Offshore Wind Farm Control
Downstream wind turbines operating behind upstream turbines face significant performance challenges due to reduced wind speeds and increased turbulence. This leads to decreased wind energy production and higher dynamic l…
Model Predictive ControlPoint TrackingPEPit: computer-assisted worst-case analyses of first-order optimization methods in Python
PEPit is a Python package aiming at simplifying the access to worst-case analyses of a large family of first-order optimization methods possibly involving gradient, projection, proximal, or linear optimization oracles, a…