This paper asks if new join algorithms allow relational engines to close the
performance gap with graph engines?

Dung Nguyen, Molham Aref, Martin Bravenboer, George Kollias, Hung Q. Ngo,
Christopher Re´, Atri Rudra. 2015.

In Proceedings of the GRADES ‘15 (GRADES ‘15).

Join optimization has been dominated by Selinger-style, pairwise optimizers for
decades. But, Selinger-style algorithms are asymptotically suboptimal for
applications in graphic analytics. This suboptimality is one of the reasons that
many have advocated supplementing relational engines with specialized graph
processing engines. Recently, new join algorithms have been discovered that
achieve optimal worst-case run times for any join or even so-called beyond
worst-case (or instance optimal) run time guarantees for specialized classes of
joins. These new algorithms match or improve on those used in specialized
graph-processing systems. This paper asks can these new join algorithms allow
relational engines to close the performance gap with graph engines?

Read the PDF:
Join Processing for Graph Patterns: An Old Dog with New Tricks