After five years of blood, sweat, and tears, TreeTracker Join ((\mathsf{TTJ})) has finally been published. The research itself is very interesting and kept me hooked for five years. As a postmortem, I reflect on some of what I learned during the process. I’m hoping this post can be useful to my fellow PhD students who are currently struggling to make progress or finding their work a proper home.
-
When talking about empirical study, what should we implement?
-
Considerations on the design and implementation of prototype
Short background on (\mathsf{TTJ})
This research concerns query processing, specifically the evaluation of queries that involve multiple joins, e.g., (R \Join S \Join T) for relations (R), (S), and (T). Those queries are known as conjunctive queries. It has been long known from database theory that evaluation of an important subclass of conjunctive queries called acyclic conjunctive queries 2 can be done very efficiently using an algorithm called Yannakakis’s algorithm ((\mathsf{YA})) 1. (There are many expositions on Yannakakis’s algorithm such as wikipedia, blog post, slides, and video.) However, the issue with this algorithm is that it is somewhat galactic (theoretically optimal but empirically impractical) due to its poor empirical performance and awkward algorithm structure. On the empirical performance front, the core issue of (\mathsf{YA}) is that it uses semijoin to preprocess the input relations of a query so that the follow-up joins only generate the tuples that can be part of the final query result. There are two problems with semijoins:
Semijoin is really a heavy operation from empirical perspective: If one implements hash-based semijoin, building hash table and probing tuples against it can be quite expensive. 1.
(\mathsf{YA}) just uses too many semijoins; if your query has (k) relations for a positive integer (k), (\mathsf{YA}) uses (2k-2) semijoins.