收藏切换
Beyond Shuffling: PAC-Tree for Efficient Distributed Joins via Hierarchical Data Placement
收藏切换
PDF
Pengju Liu1, 2, Cuiping Li1, 2, Hong Chen1, 2
Data Science and Engineering | 2026, 11(1) : 155 - 176
Less
收藏切换
Data Science and Engineering | 2026, 11(1): 155-176
RESEARCH PAPERS
Beyond Shuffling: PAC-Tree for Efficient Distributed Joins via Hierarchical Data Placement
Full
Pengju Liu1, 2, Cuiping Li1, 2, Hong Chen1, 2
Affiliations
  • 1Engineering Research Center of Database and Business Intelligence, Ministry of Education, Haidian Huangzhuang, Haidian District Beijing 100872, People's Republic of China
  • 2School of Information, Renmin University of China, No. 59 Zhongguancun Street, Haidian District Beijing 100872, People's Republic of China
  • Cuiping Li 

    Hong Chen 

Published: 2026-03-01 doi: 10.1007/s41019-025-00324-8
Outline
收藏切换

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× compared with state-of-the-art layouts, especially for join-heavy workloads.

Data layout  /  Distributed joins  /  Hierarchical partitioning tree  /  Data skipping  /  Data shuffling reduction
Pengju Liu, Cuiping Li, Hong Chen. Beyond Shuffling: PAC-Tree for Efficient Distributed Joins via Hierarchical Data Placement[J]. Data Science and Engineering, 2026 , 11 (1) : 155 -176 . DOI: 10.1007/s41019-025-00324-8
  • National Key Research and Development Program of China(2023YFB4503600)
  • National Natural Science Foundation of China(U23A20299; 62072460; 62172424; 62276270; 62322214)
Year 2026 volume 11 Issue 1
PDF
39
10
Cite this Article
BibTeX
Article Info
doi: 10.1007/s41019-025-00324-8
  • Receive Date:2025-06-05
  • Online Date:2026-08-06
  • Published:2026-03-01
Article Data
Affiliations
History
  • Received:2025-06-05
  • Revised:2025-09-05
  • Accepted:2025-10-28
Funding
National Key Research and Development Program of China(2023YFB4503600)
National Natural Science Foundation of China(U23A20299; 62072460; 62172424; 62276270; 62322214)
Affiliations
    1Engineering Research Center of Database and Business Intelligence, Ministry of Education, Haidian Huangzhuang, Haidian District Beijing 100872, People's Republic of China
    2School of Information, Renmin University of China, No. 59 Zhongguancun Street, Haidian District Beijing 100872, People's Republic of China

Corresponding:

Pengju Liu 
References
Share
https://castjournals.cast.org.cn/joweb/dse/EN/10.1007/s41019-025-00324-8
Share to
QR

Scan QR to access full text

Cite this article
BibTeX
Citations
表12种不同金属材料的力学参数

Family
属数
Number of
genus
种数
Number of
species
占总种数比例
Percentage of
total species (%)

Genus
种数
Number of
species
占总种数比例
Percentage of total
species (%)
鹅膏菌科Amanitaceae 2 11 5.26 鹅膏菌属 Amanita 10 4.78
小菇科 Mycenaceae 2 12 5.74 丝盖伞属 Inocybe 5 2.39
多孔菌科 Polyporaceae 8 14 6.70 蜡蘑属 Laccaria 5 2.39
红菇科 Russulaceae 3 23 11.00 小皮伞属 Marasmius 6 2.87
小菇属 Mycena 11 5.26
光柄菇属 Pluteus 5 2.39
红菇属 Russula 17 8.13
栓菌属 Trametes 5 2.39
关闭全屏
  • BibTeX
  • EndNote
  • RefWorks
  • TxT