A Unified Architecture for Efficient Binary and Worst-Case Optimal Join Processing
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916759577034752 |
|---|---|
| author | Kaboli, Amirali Mascolo, Alex Shaikhha, Amir |
| author_facet | Kaboli, Amirali Mascolo, Alex Shaikhha, Amir |
| contents | 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 paper, 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.1x (on average 1.5x) and 4.8x (on average 1.4x) over the state-of-the-art implementation of Generic Join and Free Join methods, respectively, across acyclic and cyclic queries in standard query benchmarks. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_19918 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Unified Architecture for Efficient Binary and Worst-Case Optimal Join Processing Kaboli, Amirali Mascolo, Alex Shaikhha, Amir Databases 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 paper, 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.1x (on average 1.5x) and 4.8x (on average 1.4x) over the state-of-the-art implementation of Generic Join and Free Join methods, respectively, across acyclic and cyclic queries in standard query benchmarks. |
| title | A Unified Architecture for Efficient Binary and Worst-Case Optimal Join Processing |
| topic | Databases |
| url | https://arxiv.org/abs/2505.19918 |