Beyond Shuffling: PAC-Tree for Efficient Distributed Joins via Hierarchical Data Placement

Efficiently execution of join operations over large-scale distributed data is critical in modern analytical engines, yet costly shuffle operations involving extensive network transfer and remote I/O often hinder performance. Existing data layout techniques struggle with complex multi-table joins due to inflexible distribution key assignments, suboptimal cluster key choices that require significant manual tuning, and weak co-optimization with downstream join strategy selection. This paper introduces PAC-Tree (Partition-Aligned Co-Join Tree), a novel query-aware data layout designed to comprehensively address these limitations in an end-to-end manner. PAC-Tree features a two-level hierarchical structure: the upper level replicates fact tables with diverse distribution keys to improve co-location across join patterns, while the lower level applies advanced multidimensional partitioning with predicate-aware splits for fine-grained intra-shard data skipping. Leveraging PAC-Tree’s statistics, we further propose a block-grouping algorithm to construct co-partitions under memory constraints and a PRIM-based reordering policy for multi-table joins, together significantly reducing shuffle overhead. Experiments on a real Spark cluster demonstrate that PAC-Tree reduces query latency by up to 45.7% and improves throughput by up to 2$$\times$$ compared with state-of-the-art layouts, especially for join-heavy workloads.