Optimizing graph queries with graph joins and Sprinkle SPARQL
Eric L. Goodman, Edward S. Jimenez, Cliff Joslyn, David J. Haglin, Sinan al-Saffar, Dirk C. Grunwald · 2014
Big data problems are often more akin to sparse graphs rather than relational tables. As such we argue that graph-based physical representations provide advantages in terms of both size and speed for executing queries. Drawing from research in sparse matrices, we use a compressed sparse row (CSR) format to model graph-oriented data. We also present two novel mechanisms for exploiting the CSR format that both find optimal join strategies and also prune variable bindings before expensive join operations occur. The first tactic we call Sprinkle SPARQL, which takes triple patterns of SPARQL queries and performs low-cost, linear-time set intersections to produce a constrained list of variable bindings for each variable in a query. Besides constrained lists of variable bindings, Sprinkle SPARQL also produces metrics that are consumed by the join algorithm to select an optimal execution path. The second tactic, graph joins, utilizes the CSR data structure as an index to efficiently join two variables expressed in a triple pattern together. We evaluate our approach on two data sets with over a billion edges: LUBM(8000) and an R-MAT graph generated with Graph5001parameters and extended to have edge labels.