Join Processing for Graph Patterns: An Old Dog with New Tricks
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 (opens in a new tab)
Related Posts
Leapfrog Triejoin: A Simple, Worst-Case Optimal Join Algorithm
In 2012, Ngo, Porat, R«e and Rudra (henceforth NPRR) devised a join algorithm with worst-case running time proportional to the AGM bound [8]. Our commercial database system LogicBlox employs a novel join algorithm, leapfrog triejoin, which compared conspicuously well to the NPRR algorithm in preliminary benchmarks.
Hybrid Context-Sensitivity for Points-To Analysis
Context sensitive points-to analysis is valuable for achieving high precision with good performance.The standard flavors of context sensitivity are call site-sensitivity (kCFA) and object-sensitivity. Combining both flavors of context-sensitivity increases precision but at an infeasibly high cost.