Shaikhha, Amir

Barbalace, Antonio

Kaboli, Amirali

RelationalAI

2025-05-28T12:13:11Z

2025-05-28T12:13:11Z

2025-05-28

Join processing is a fundamental operation in database management systems; however, traditional join algorithms often encounter efficiency challenges when dealing with complex queries that produce intermediate results much larger than the final query output. The emergence of worst-case optimal join (WCOJ) algorithms represents a significant advancement, offering asymptotically better performance by avoiding the enumeration of potentially exploding intermediate results. In this thesis, we propose a unified architecture that efficiently supports both traditional binary joins and WCOJ processing. As opposed to the state-of-the-art, which only focuses on either hash-based or sort-based join implementations, our system accommodates both physical implementations of binary joins and WCOJ algorithms. Experimental evaluations demonstrate that our system achieves performance gains of up to 3.1× (on average 1.5×) and 4.8× (on average 1.4×) over the state-of-the-art implementation of Generic Join and Free Join methods, respectively, across acyclic and cyclic queries in standard query benchmarks.

https://hdl.handle.net/1842/43503

http://dx.doi.org/10.7488/era/6039

en

The University of Edinburgh

Unified Architecture

Binary Joins

Worst-case Optimal Join (WCOJ)

Efficiency

Performance Gains

Unified architecture for efficient binary and worst-case optimal join processing

A unified architecture for efficient binary and worst-case optimal join processing

Thesis or Dissertation

Doctoral

MSc(R) Master of Science by Research