A Worst-Case Optimal Join Algorithm for SPARQL

Abstract

Worst-case optimal multiway join algorithms have recently gained a lot of attention in the database literature. These algorithms not only offer strong theoretical guarantees of efficiency, but have also been empirically demonstrated to significantly improve query runtimes for relational and graph databases. Despite these promising theoretical and practical results, however, the Semantic Web community has yet to adopt such techniques; to the best of our knowledge, no native RDF database currently supports such join algorithms, where in this paper we demonstrate that this should change. We propose a novel procedure for evaluating SPARQL queries based on an existing worst-case join algorithm called Leapfrog Triejoin. We propose an adaptation of this algorithm for evaluating SPARQL queries, and implement it in Apache Jena. We then present experiments over the Berlin and WatDiv SPARQL benchmarks, and a novel benchmark that we propose based on Wikidata that is designed to provide insights into join performance for a more diverse set of basic graph patterns. Our results show that with this new join algorithm, Apache Jena often runs orders of magnitude faster than the base version and two other SPARQL engines: Virtuoso and Blazegraph.

A Proof of Theorem 1

Fix a basic graph pattern P, an RDF graph G, and $\mathtt {?x}_1, \ldots , \mathtt {?x}_n$ the chosen variable order. Further assume that the computation of ${\text {LF}}_G(P',\mathtt {?x})$ takes time at most $\min _{t \in P' : \mathtt {?x}\in {\text {var}}(t)} |\pi _{\mathtt {?x}}(\llbracket t \rrbracket _G)| \, \cdot \, \log (|G|)$ for every basic graph pattern $P'$ (for simplicity, we will omit the trivial empty case where there exists $t \in P'$ such that $\mathtt {?x}\in {\text {var}}(t)$ and $|\pi _{\mathtt {?x}}(\llbracket t \rrbracket _G)| = 0$ since the time taken will be simply $\log (|G|)$). Finally, for every RDF graph $G'$ we will say that $G'$ is of size less than G whenever $|\llbracket t \rrbracket _{G_i}| \le |\llbracket t \rrbracket _{G}|$ for all $t \in P$ (recall that P is fixed).

The proof of Theorem 1 goes in two steps. First, we will bound the time of Leapfrog Join by bounding the time $T_i$ of each for-loop $\mathtt {?x}_i$ of Algorithm 1. Then for each level $\mathtt {?x}_i$ we define a new RDF graph $G_{i}$ of size less than G such that $T_i = |\llbracket P \rrbracket _{G_i}| \le 2^{\text {MIN}(P, G)}$. The proof will follow by taking the sum over all $T_i$.

Fix a variable $\mathtt {?x}_i$ and denote by $\bar{x}_{i-1} = \mathtt {?x}_1, \ldots , \mathtt {?x}_{i-1}$ the order of variables before $\mathtt {?x}_i$ (for the sake of simplification, in the sequel we consider $\bar{x}_i$ also as a set). We start by bounding the time of the for-loop in Algorithm 1 corresponding to $\mathtt {?x}_i$. For this, consider the following extension of ${\text {LF}}_G$ over $\bar{x}_{i-1}$:

$$ {\text {LF}}_G(P,\bar{x}_{i-1}) \ = \ \{\mu \mid {\text {dom}}(\mu ) = \bar{x}_{i-1} \text { and } \llbracket \mu (t) \rrbracket _G \ne \varnothing \text { for all } t \in P\} $$

Clearly, the number of times that the for-loop of $\mathtt {?x}_i$ will be called is given by $|{\text {LF}}_G(P,\bar{x}_{i-1})|$. Then for each $\mu \in {\text {LF}}_G(P,\bar{x}_{i-1})$ the Leapfrog procedure ${\text {LF}}_G(\mu (P),\mathtt {?x}_i)$ is called taking time at most $\min _{t \in \mu (P) : \mathtt {?x}_i \in {\text {var}}(t)} |\pi _{\mathtt {?x}_i}(\llbracket t \rrbracket _G)|$ (omitting the $\log (|G|)$ factor for the moment). If we call $T_i$ the number of steps that Algorithm 1 spends in the for-loop of $\mathtt {?x}_i$, we have that:

$$ T_i \ = \ \sum _{\mu \in {\text {LF}}_G(P,\bar{x}_{i-1})} \min _{t \in \mu (P) : \mathtt {?x}_i \in {\text {var}}(t)} |\pi _{\mathtt {?x}_i}(\llbracket t \rrbracket _G)| $$

One can easily check that the total time of Algorithm 1 is given by $(\sum _{i=1}^n T_i)\cdot \log (G)$. Therefore, if we bound $T_i$ by the AGM bound of P and G, then the worst case optimality of Leapfrog Join will be proven (recall that our analysis is in data complexity, omitting factors that depend on the size of P).

To bound the size of $T_i$, we build an RDF graph $G_i$ such that $T_i = |\llbracket P \rrbracket _{G_i}|$ and the size of $G_i$ is less that the size of G. Let $\bot$ be a dummy value. To build $G_i$ define the set of mappings $U_i$ such that $\mu \in U_i$ if and only if there exists $\mu ' \in {\text {LF}}_G(P,\bar{x}_{i-1})$ such that:

• 1. ep2mm

• 1. $\mu (\mathtt {?x}) = \mu '(\mathtt {?x})$ for every $\mathtt {?x}\in \bar{x}_{i-1}$,

• 2. $1 \le \mu (\mathtt {?x}_i) \le \min _{t \in \mu '(P) : \mathtt {?x}_i \in {\text {var}}(t)} |\pi _{\mathtt {?x}_i}(\llbracket t \rrbracket _G)|$, and

• 3. $\mu (\mathtt {?x}) = \bot$ for every $\mathtt {?x}\in \{\mathtt {?x}_{i+1}, \ldots , \mathtt {?x}_{n}\}$.

In other words, $U_i$ contains all mappings built from mappings of ${\text {LF}}_G(P,\bar{x}_{i-1})$ and extended by assigning to $\mathtt {?x}_i$ any value less than the time for computing ${\text {LF}}_G(\mu '(P),\mathtt {?x}_i)$. From $U_i$ we can build the RDF graph $G_i$ as follows:

$$ G_i \ = \ \bigcup _{\mu \in U_i} \mu (P). $$

By construction, note that the size of $G_i$ is less than the size of G. Furthermore, we have that $T_i = |\llbracket P \rrbracket _{G_i}|$. Indeed, for each $\mu ' \in {\text {LF}}_G(P,\bar{x}_{i-1})$ we will have $\big (\min _{t \in \mu '(P) : \mathtt {?x}_i \in {\text {var}}(t)} |\pi _{\mathtt {?x}_i}(\llbracket t \rrbracket _G)|\big )$ different mappings in $\llbracket P \rrbracket _{G_i}$ and vice versa.

To finish the proof, recall the linear program associated to P and G, and its minimum value $\text {MIN}(P,G)$. Consider also the same linear program but now for P and $G_i$. Given that $G_i$ is of size less than G, then the minimization function associated to the linear program of P and $G_i$ always satisfies:

$$ \sum _{t\in P} x_t \cdot \log (|\llbracket t \rrbracket _{G_i}|) \le \sum _{t\in P} x_t \cdot \log (|\llbracket t \rrbracket _{G}|). $$

Therefore, we can conclude that $\text {MIN}(P,G_i) \le \text {MIN}(P,G)$ and thus:

$$ T_i \ = \ |\llbracket P \rrbracket _{G_i}| \ \le \ 2^{\text {MIN}(P,G_i)} \ \le \ 2^{\text {MIN}(P,G)} $$

where the second inequality follows by the AGM bound. Given that each $T_i$ is bounded by $2^{\text {MIN}(P,G)}$ we conclude that the overall time is bounded by $n\cdot 2^{\text {MIN}(P,G)} \cdot \log (G)$ and that Leapfrog Join is worst-case optimal.