RelJoin: Relative-cost-based selection of distributed join methods for query plan optimization

Feng Liang, Francis C.M. Lau, Heming Cui, Yupeng Li, Bing Lin, Chengming Li, Xiping Hu*

*Corresponding author for this work

Research output: Contribution to journalJournal articlepeer-review


Selecting appropriate distributed join methods for logical join operations in a query plan is crucial for the performance of data-intensive scalable computing (DISC). Different network communication patterns in the data exchange phase generate varying network communication workloads and significantly affect the distributed join performance. However, most cost-based query optimizers focus on the local computing cost and do not precisely model the network communication cost. We propose a cost model for various distributed join methods to optimize join queries in DISC platforms. Our method precisely measures the network and local computing workloads in different execution phases, using information on the size and cardinality statistics of datasets and cluster join parallelism. Our cost model reveals the importance of the relative size of the joining datasets. We implement an efficient distributed join selection strategy, known as RelJoin in SparkSQL, which is an industry-prevalent distributed data processing framework. RelJoin uses runtime adaptive statistics for accurate cost estimation and selects optimal distributed join methods for logical joins to optimize the physical query plan. The evaluation results on the TPC-DS benchmark show that RelJoin performs best in 62 of the 97 queries and can reduce the average query time by 21% compared with other strategies.

Original languageEnglish
Article number120022
JournalInformation Sciences
Early online date20 Dec 2023
Publication statusPublished - Feb 2024

Scopus Subject Areas

  • Software
  • Control and Systems Engineering
  • Theoretical Computer Science
  • Computer Science Applications
  • Information Systems and Management
  • Artificial Intelligence

User-Defined Keywords

  • Adaptive statistics
  • Cost-based
  • Distributed join
  • Query plan optimization


Dive into the research topics of 'RelJoin: Relative-cost-based selection of distributed join methods for query plan optimization'. Together they form a unique fingerprint.

Cite this