Title: Towards a Worst-Case I/O-Optimal Algorithm for Acyclic Joins

Speaker: Xiao Hu, HKUST

Time/Date: Friday, Jun 3, 11-12

Location: 3501

Abstract:

Nested-loop join is a worst-case I/O-optimal algorithm for 2
relations. Recently, a lot of efforts have been devoted to the
"triangle query", for which an I/O-optimal algorithm is known. We
extend these results to a fairly large class of acyclic joins. Acyclic
joins can be computed optimally in internal memory using Yannakakis'
algorithm from 1981, which simply performs a series of pairwise
joins. However, no pairwise join algorithm can be I/O-optimal beyond 2
relations. To achieve I/O-optimality, the algorithm has to handle all
the intermediate results carefully without writing them to
disk. Unlike the optimal internal memory join algorithm which has a
nice tight bound (the AGM bound), the I/O-complexity of joins turns
out to be quite complex or even unknown. Yet, we are able to prove
that our algorithm is I/O-optimal for certain classes of acyclic joins
without deriving its bound explicitly.