Ilmu Komputer & AI editorial
Open AccessOA2026
TreeRedux: Separating Concerns in Spark's Distributed Tree Aggregation
A terminal finalize operation that keeps large aggregation state off the driver, enabling exact quantiles and heavy-hitter sketches at unprecedented scale
David A. G. Harrison; Ivan Cao· 2026· DOI 10.48550/arXiv.2609.06982
The core problem
Apache Spark's tree aggregation primitives are a cornerstone of distributed data processing, but their default design places the tree root on the driver. This forces the driver to participate in the same aggregation computation over intermediate aggregation state as executor nodes. For large aggregates, the single coordinator can face substantial computation and memory requirements. Recent Spark versions optionally move the root to an executor, yet the completed aggregate must still be returned to and materialized on the driver. The authors demonstrate this limitation using exact quantile computation and heavy-hitter identification, where the intermediate aggregation state can be substantially larger than the desired final result. They propose TreeRedux, a minimal extension that adds a terminal finalize operation executed on an executor, mapping the aggregation state to a compact result , so that rather than the potentially large is materialized on the driver.
Innovation
The authors conducted experiments to evaluate TreeRedux against baseline implementations. The default GK Select implementation encountered a driver out-of-memory error at 2.5 billion elements. Spark's executor-side final aggregation option extended this limit to approximately 16-18 billion elements but still required the final aggregation state to be materialized on the driver. In contrast, Redux Select, the TreeRedux-enhanced version, completed through 28 billion elements without a driver out-of-memory error. Furthermore, TreeRedux allowed Space-Saving sketches with up to 32x the capacity of the largest configuration that materializes a full sketch on the driver. These results demonstrate significant improvements in scalability and memory efficiency.
Apache Spark's tree aggregation primitives are a cornerstone of distributed data processing, but their default design places the tree root on the driver. This forces the driver to participate in the same aggregation computation over intermediate aggregation state as executor nodes. For large aggregates, the single coordinator can face substantial computation and memory requirements. Recent Spark versions optionally move the root to an executor, yet the completed aggregate must still be returned to and materialized on the driver. The authors demonstrate this limitation using exact quantile computation and heavy-hitter identification, where the intermediate aggregation state can be substantially larger than the desired final result. They propose TreeRedux, a minimal extension that adds a terminal finalize operation executed on an executor, mapping the aggregation state to a compact result , so that rather than the potentially large is materialized on the driver.
TreeRedux introduces a terminal finalize operation that runs on an executor after the tree aggregation completes. Formally, let denote the intermediate aggregation state and the final compact result. The finalize function is applied on an executor, ensuring that only is transferred to and materialized on the driver. This separation of concerns decouples the aggregation computation from the final result materialization.
Why it matters
The results highlight the effectiveness of separating the finalization step from the aggregation computation. By moving the finalize operation to an executor, TreeRedux eliminates the driver's epsilon-n memory term for exact quantile computation, reducing driver memory requirements to the same asymptotic order as Spark's GK Sketch. This is particularly important for large-scale data processing where the intermediate aggregation state can be orders of magnitude larger than the final result. The ability to use Space-Saving sketches with 32x capacity further underscores the practical benefits. TreeRedux is a minimal extension, making it easy to adopt in existing Spark applications. The authors note that while recent Spark versions optionally move the root to an executor, the completed aggregate must still be returned to and materialized on the driver; TreeRedux addresses this remaining bottleneck. Future work could explore applying TreeRedux to other aggregation primitives and optimizing the finalize function for various data types.
Who should read this
CS practitioners and researchers
Opening member content…