Published in Data Science and Engineering in January 2026, the study addresses the critical performance bottleneck caused by shuffle operations, which involve extensive network transfers and remote input/output when joining large tables. The authors demonstrate that their hierarchical approach reduces query latency by up to 45.7% and improves system throughput by up to two times compared to state-of-the-art layout techniques, particularly for workloads dominated by complex multi-table joins.
The core challenge in modern analytical systems is that join operators frequently require redistributing data across nodes to co-locate tuples with identical join keys. This redistribution, known as shuffling, incurs substantial overhead due to network serialization, deserialization, and remote disk access. Existing data layout techniques often struggle with complex join patterns because they rely on inflexible distribution key assignments and suboptimal cluster key choices that require significant manual tuning. PAC-Tree aims to resolve these limitations by integrating data statistics with query execution plans to optimize the entire end-to-end query processing pipeline.
PAC-Tree features a two-level hierarchical structure that distinguishes it from traditional partitioning methods. The upper level of the tree replicates fact tables using diverse distribution keys to improve data co-location across various join patterns. By leveraging data replication, this design alleviates resource contention that arises when a single fixed distribution key cannot accommodate all potential join relationships. The lower level applies advanced multidimensional partitioning with predicate-aware splits, enabling fine-grained intra-shard data skipping. This dual-layer approach allows the system to optimize both the placement of data across machines and the organization of data within each machine.
The construction of the PAC-Tree involves a three-stage offline process that begins with the selection of optimal join keys. The system employs a greedy strategy to identify representative join keys for each table, guided by a lightweight evaluation function that estimates the benefit of a candidate key based on the size of the join result. This selection is subject to a predefined replication factor, which determines how many different distribution keys are used for replicas of the same table. The algorithm filters out low-cardinality columns that could cause data skew, ensuring that the selected keys provide balanced distribution across compute nodes.
Following key selection, the system constructs the top part of the tree based on the distribution of these join keys. The number of top-level leaf nodes is chosen as an integer multiple of the available worker count to ensure balanced utilization during join processing. The bottom part of the tree is then constructed using query-driven techniques that maximize data skipping by exploiting frequently filtered columns. The authors adopt the MTO method as the basis for this bottom-layer construction, extending it with a novel bounding split mechanism. This bounding split merges multiple single-step splits into a single operation, which is particularly advantageous for small leaf nodes where traditional single-step splits may fail to find optimal boundaries.
To leverage the optimized layout during query execution, the researchers propose a block-grouping algorithm and a join reordering policy. The block-grouping algorithm, termed Queue-Driven Grouping or QDG, constructs co-partitions under memory constraints to minimize data shuffling. It uses a priority queue to repeatedly merge pairs of blocks or block groups that maximize the locality of their required join blocks. This approach ensures that blocks from one table are grouped with the specific blocks from the other table that they need to join with, reducing the amount of data that must be transferred across the network.
The join reordering policy uses the PRIM algorithm to optimize the overall execution plan for multi-table joins. By modeling the join relationships as a weighted graph, the system identifies a join order that maximizes the use of local hyper joins while minimizing the number of expensive shuffle joins. This reordering is informed by the PAC-Tree’s view of data distribution, allowing the query optimizer to make more accurate cost estimates. The result is a query plan that reduces the total input/output cost by avoiding unnecessary data movements between compute nodes.
The experimental evaluation was conducted on a three-node Apache Spark cluster, using standard OLAP workloads including TPC-H, TPC-DS, and the Join Order Benchmark. The datasets were scaled to various sizes, up to 100 GB, to test the robustness of the layout under different data volumes. The researchers compared PAC-Tree against two baseline methods: PAW, which constructs predicate-based binary trees without distinguishing join-related columns, and AD-MTO, a hybrid approach that combines elements of AdaptDB, BaW, and MTO. These baselines represent current state-of-the-art techniques for query-aware data partitioning.
The results demonstrate that PAC-Tree achieves strong cross-database generalization, with up to a 67% reduction in scanned data compared to PAW and up to a 45% reduction compared to AD-MTO. In end-to-end system performance evaluations, PAC-Tree consistently achieved the lowest query latency across all benchmarks. The reduction in latency was accompanied by substantial decreases in read bytes, with a 49% reduction compared to PAW and a 25% reduction compared to AD-MTO. These improvements in data skipping efficiency directly translate to better system throughput, with PAC-Tree improving throughput by factors of 3.2 times and 2 times over the respective baselines.
Sensitivity analyses revealed that the performance of PAC-Tree is influenced by the replication factor and block size. Increasing the replication factor generally improves performance up to an optimal point, typically around three replicas, after which the benefits diminish. The system also maintains its performance advantage across various minimum block sizes, although larger partitions can reduce the flexibility in distinguishing data groups by query access patterns. The study also examined the impact of the number of joined tables, finding that the advantages of PAC-Tree grow significantly as join complexity increases, highlighting its broader applicability to complex analytical workloads.
Ablation studies confirmed the effectiveness of individual components of the PAC-Tree approach. The weight-based join key selection strategy was shown to outperform random key assignment, with larger replication factors offering greater potential for performance gains. The join order optimization driven by the QDG algorithm consistently outperformed the default query optimizer order, especially for queries involving complex join graphs.
The study acknowledges certain limitations in the current implementation. PAC-Tree is not always optimal for every individual query, with suboptimal outcomes observed in some cases where tables feature a large number of join keys or where the cost of shuffle edges is misestimated. The MST-based join ordering may overvalue certain hyperedges, which can restrict join orders and raise overall join costs in specific scenarios. Additionally, the offline model runtime for PAC-Tree is longer than that of some baseline methods, although this overhead is negligible relative to the total time required for processing benchmark datasets.
Future work will focus on developing adaptive mechanisms that allow PAC-Tree to dynamically respond to workload shifts. This involves aggregating and filtering collected features to ensure the robustness of static partitions and detecting recurring filter patterns to better inform the design of distribution and clustering keys. The researchers also aim to reduce the reliance on manually tuned hyperparameters within the algorithm, thereby minimizing intervention during deployment and enhancing the generality of PAC-Tree for diverse analytical environments.
Subject of Research: Beyond Shuffling: PAC-Tree for Efficient Distributed Joins via Hierarchical Data Placement
Article Title: Beyond Shuffling: PAC-Tree for Efficient Distributed Joins via Hierarchical Data Placement
Article References: Liu, P., Li, C., & Chen, H. (2026). Beyond Shuffling: PAC-Tree for Efficient Distributed Joins via Hierarchical Data Placement. Data Science and Engineering, 11(1), 155-176. https://doi.org/10.1007/s41019-025-00324-8
Image Credits: AI Generated
DOI: 10.1007/s41019-025-00324-8
Keywords: Beyond, Shuffling, PAC-Tree, Efficient, Distributed, Joins, Hierarchical, Data, Placement, scientific research
News Source: Denise Maddox. (November 10, 2026). PAC-Tree Cuts Distributed Join Latency by 45.7% via Hierarchical Layout. Scienmag.
