Scholarlink

<p>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 (<b>P</b>artition-<b>A</b>ligned <b>C</b>o-Join <b>Tree</b>), 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<InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(\times\)</EquationSource> </InlineEquation> compared with state-of-the-art layouts, especially for join-heavy workloads.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

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

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2026年1月7日

查看全文
  • Pengju Liu,
  • Cuiping Li,
  • Hong Chen

摘要

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.