13 - Multi-Way / Worst-Case Optimal Join Algorithms (CMU Advanced Databases / Spring 2023)

15-721 Advanced Database Systems (Spring 2023)
Carnegie Mellon University

[kendallwillets]

This seems to be a version of what people now call the MergeSkip algorithm (it seems to get rediscovered periodically), which can be used for n-way ordered set intersection or other problems.

With MergeSkip, when merging n ordered sequences (in this case table tuples), it's possible to skip values which occur in less than all of them, if each sequence has a "skip" operation which seeks to the next sequence value >= a target value. WCOJ appears to do the skip with tries, but other methods or data structures will also work.