Fragment Allocations for Partially Replicated Databases Considering Data Modifications and Changing Workloads

Columnar database systems can process complex mixed workloads on a single node. In case of increasing and peak analytical processing demand, we can offload read-only queries to replicas. Partial replication, i.e., duplicating only data subsets to additional nodes, is more cost-efficient than full replication for two primary reasons: (i) Partial replicas require less storage and can be set up faster. (ii) Partial replicas must synchronize only stored data subsets, allowing better scalability. However, determining which queries to offload is challenging for larger workloads because queries access overlapping data subsets and cause synchronization costs. This paper shows how to calculate optimized replica configurations that consider reallocation and data modification costs using integer linear programming (ILP) techniques. While ILP is effective for solving assignment problems, it does not scale well. For larger problems, users often fall back to simple heuristics, which can lose optimization potential. This paper demonstrates that scalable heuristics can be built on ILP, preserving its strengths. The three proposed approaches for reducing the calculation time allow trading solution quality flexibly. Our evaluations using TPC-H, TPC-DS, and a large real-world accounting workload show that our approach outperforms state-of-the-art solutions, often reducing reallocated data by more than 80% and halving modification costs. At the same time, the new allocations reduce the storage consumption by over 30%, with solutions computed in just a few seconds.