Technical Perspective: Output-Optimal Evaluation ofConjunctive Queries

The best asymptotic runtime that we can hope for a query evaluation algorithm is O(N + OUT), where N is the size of the input database and OUT is the size of the query's output. Indeed, any algorithm must read the input, and must write the output, hence one cannot do better asymptotically. It is not immediately obvious how to evaluate a query in this time. The standard approach taken by all query engines is to compute one join at a time, but in that case the intermediate results may become much larger than both the input and the final output. Yannakakis' algorithm from the early 80's achieves a runtime of O(N +OUT) on all full, acyclic queries, by first removing all dangling tuples from all relations using a sequence of semijoins, then performing the joins.