Exploiting the query structure for efficient join ordering in SPARQL queries
Andrey Gubichev, Thomas Neumann · 2014
The join ordering problem is a fundamental challenge that has to be solved by any query optimizer. Since the high-performance RDF systems are often implemented as triple stores (i.e., they represent RDF data as a single table with three attributes, at least conceptu-ally), the query optimization strategies employed by such systems are often adopted from relational query optimization. In this paper we show that the techniques borrowed from traditional SQL query optimization (such as Dynamic Programming algorithm or greedy heuristics) are not immediately capable of handling large SPARQL queries. We introduce a new join ordering algorithm that performs a SPARQL-tailored query simplification. Furthermore, we present a novel RDF statistical synopsis that accurately estimates cardinal-ities in large SPARQL queries. Our experiments show that this algorithm is highly superior to the state-of-the-art SPARQL opti-mization approaches, including the RDF-3X’s original Dynamic Programming strategy.