  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.
