The federated query extension of SPARQL 1.1 allows executing queries distributed over different SPARQL endpoints. SPARQL-LD is a recent extension of SPARQL 1.1 which enables to directly query any HTTP web source containing RDF data, like web pages embedded with RDFa, JSON-LD or Microformats, without requiring the declaration of named graphs. This makes possible to query a large number of data sources (including SPARQL endpoints, online resources, or even Web APIs returning RDF data) through a single one concise query. However, not optimal formulation of SPARQL 1.1 and SPARQL-LD queries can lead to a large number of calls to remote resources which in turn can lead to extremely high query execution times. In this paper, we address this problem and propose a set of query reordering methods which make use of heuristics to reorder a set of service graph patterns based on their restrictiveness, without requiring the gathering and use of statistics from the remote sources. Such a query optimization approach is widely applicable since it can be exploited on top of existing SPARQL 1.1 and SPARQL-LD implementations. Evaluation results show that query reordering can highly decrease the query-execution time, while a method that considers the number and type of unbound variables and joins achieves the optimal query plan in 88% of the cases.
A constantly increasing number of data providers publish their data on the Web
following the Linked Data principles and adopting standard RDF formats.
According to the Web Data Commons project [
SPARQL [
However, not optimal query writing in both SPARQL 1.1 and SPARQL-LD can lead to a very large number of service calls to remote resources, which in turn can lead to an extremely high query execution time. Thus, there arises the need for an effective query optimization method than can find a near-optimal query execution plan. In addition, given the dynamic nature of Linked Data and the capability offered by SPARQL-LD to query any remote HTTP resource containing RDF data, we need a widely-applicable method that does not require the use of statistics or metadata from the remote sources and that can operate on top of existing SPARQL 1.1 and SPARQL-LD implementations.
To this end, in this paper we propose and evaluate a set of query reordering methods for SPARQL 1.1 and SPARQL-LD. We focus on fully heuristics-based methods that reorder a query’s service graph patterns based on their restrictiveness (selectivity), without requiring the gathering and use of statistics from the remote sources. The objective is to decrease the number of intermediate results and thus the number of calls to remote resources. We also propose the use of a greedy algorithm for computing a near-optimal query execution plan for cases of large number of service patterns.
In a nutshell, in this paper we make the following contributions: – We propose a set of heuristics-based query reordering methods for SPARQL 1.1 and SPARQL-LD, which can also exploit a greedy algorithm for choosing a near-optimal query execution plan. The query optimizer is publicly available as open source.5 – We report the results of an experimental evaluation which show that a method that considers the number and type of unbound variables and the number and type of joins achieves the optimal query plan in 88% of the examined queries, while the greedy algorithm has an accuracy of 94% in finding the reordering with the lowest cost.
The rest of this paper is organized as follows: Section 2 presents the required background and related works. Section 3 describes the proposed query reordering
methods. Section 4 reports experimental results. Finally, Section 5 concludes the paper and discusses interesting directions for future work. 2 2.1
SPARQL-LD
The service operator of SPARQL 1.1 (service a P ) is defined as a graph
pattern P evaluated in the SPARQL endpoint specified by the URI a, while
(service ?X P ) is defined by assigning to the variable ?X all the URIs (of
endpoints) coming from partial results, i.e. that get bound after executing an initial
query fragment [
SPARQL-LD is a generalization of SPARQL 1.1 in the sense that every query
that can be answered by SPARQL 1.1 can be also answered by SPARQL-LD.
Specifically, if the URI given to the service operator corresponds to a SPARQL
endpoint, then it works exactly as the original SPARQL 1.1 (the remote endpoint
evaluates the query and returns the result). Otherwise, instead of returning an
error (and no bindings), it tries to fetch and query the triples that may exist in
the given resource. SPARQL-LD has been implemented using Apache Jena [
Listing 1 shows a query that can be answered by SPARQL-LD. The query returns all co-authors of Pavlos Fafalios together with the number of their publications and the number of distinct conferences in which they have a publication. The query first accesses the RDFa-embedded web page of Pavlos Fafalios to collect his co-authors, then queries a SPARQL endpoint over DBLP to retrieve the conferences, and finally accesses the URI of all co-authors to gather their publications. Notice that the co-author URIs derive at query-execution time. In the same query, one could further integrate data from any other web resource, or from a web API which can return results in a standard RDF format.
The query in Listing 1 is answered within a few seconds. However, if we change the order of the first two service patterns, then its execution time is dramatically increased to many minutes. To cope with this problem, in this paper we propose methods to reorder the query’s service patterns and thus improve the query execution time in case of non optimal query formulation.
1 SELECT DISTINCT ?authorURI (count(distinct ?paper) AS ?numOfPapers) 2 (count(distinct ?series) AS ?numOfDiffConfs) WHERE { 3 SERVICE <http://l3s.de/~fafalios/> { ?p <http://purl.org/dc/terms/creator> ?authorURI } 4 SERVICE <http://dblp.l3s.de/d2r/sparql> { 5 ?p2 <http://purl.org/dc/elements/1.1/creator> ?authorURI . 6 ?p2 <http://swrc.ontoware.org/ontology#series> ?series } 7 SERVICE ?authorURI { ?paper <http://purl.org/dc/elements/1.1/creator> ?authorURI } 8 } GROUP BY ?authorURI ORDER BY DESC(?numOfPapers)
Listing 1. Example SPARQL query that can be answered by SPARQL-LD. 2.2
Related Works
SPARQL Endpoint Federation
The idea of query federation is to provide integrated access to distributed sources
on the Web. DARQ [
There is also a plethora of query federation engines to support efficient
SPARQL query processing to multiple endpoints. The work in [
The ANAPSID system [
The work in [
SPLENDID [
programming strategy is exploited to optimize the join order of SPARQL basic graph patterns.
ADERIS [
The FedX framework [
Regarding more recent works, SemaGrow [
Finally, Odyssey [
The work in [
heuristics for deciding which triple patterns of a SPARQL query are more
selective and thus it is in the benefit of the planner to evaluate them first. The
planner tries to maximize the number of merge joins and reduce intermediate
results by choosing triples patterns most likely to have high selectivity. [
In [
We first model query reordering as a cost minimization problem (Section 3.1). Then we describe four heuristics-based methods for computing the cost of a service graph pattern (Section 3.2). We also discuss how we handle some special query cases (Section 3.3). At the end we motivate the need for a greedy algorithm for computing a near-optimal reordering for cases of large number of service graph patterns (Section 3.4). 3.1
Problem Modeling Let Q be a SPARQL query and let S = (s1, s2, . . . , sn) be a sequence of n service patterns contained in Q. For a service pattern si, let gi be its nested graph pattern and Bi be the list of bindings of Q before the execution of si. Our objective is to compute a reordering S0 of S that minimizes its execution cost. Formally:
R∗ = argmin cost(S0) (1)
S0
In our case, the execution cost of a sequence of service patterns S0 corresponds to its total execution time. However, the execution time of a service pattern si ∈ S0 highly depends on the query patterns that precede si, while the bindings produced by si affect the execution time of the succeeding service patterns. Considering the above, we can estimate cost(S0) as the weighted sum of the cost of each service pattern si ∈ S0 given Bi. Formally: cost(S0) = n X (cost(si|Bi) · wi) i=1 (2)
where cost(si|Bi) expresses the cost of service pattern si given Bi (i.e., given the already-bound variables before executing si), and wi is the weight of service pattern si which expresses the degree up to which it influences the execution time of the sequence S0. We define wi = n−i+1 . In this case, for a sequence of n four service patterns S0 = (s1, s2, s3, s4), the weights are: w1 = 1.0 (since s1 influences the execution time of 3 service patterns), w2 = 0.75 (s2 affects 2 service patterns), w3 = 0.5 (s3 affects 1 service pattern), and w4 = 0.25 (s4 does not affect any other service pattern).
Now, the cost of each service pattern si can be estimated based on the selectivity/restrictiveness of its graph pattern gi given Bi. Formally: cost(si|Bi) = unrestrictiveness(gi|Bi) (3)
A service graph pattern that is very unrestrictive will return a large number of intermediate results (large number of bindings), which in turn will increase the number of calls to succeeding service patterns, resulting in higher total execution time. In the query of Listing 1 for example, a large number of bindings of the variables in the first service pattern will result in many calls of the second service. Thus, our objective is to first execute the more restrictive service patterns that will probably return small result sets.
As proposed in [
Methods for Estimating Unrestrictiveness We examine four methods for computing the unrestrictiveness cost (Equation 3) of a service graph pattern: – I. Variable Count (VC) – II. Unbound Variable Count (UVC) – III. Weighted Unbound Variable Count (WUVC) – IV. Joins-aware Weighted Unbound Variable Count (JWUVC) I. Variable Count (VC). The first unrestrictiveness measure simply considers the number of graph pattern variables without considering whether they are bound or not. For a given graph pattern gi, let V (gi) be the set of variables of
gi. The unrestrictiveness of gi can be now defined as:
unrestrictiveness(gi|Bi) = |V (gi)| With the above formula, more variables in a graph pattern means higher unrestrictiveness score. Consider for example the query in Listing 2. The second service pattern contains one variable and is more likely to retrieve a smaller number of results than the first one which contains three variables. Thus the second service pattern is more restrictive and should be executed first. 1 SELECT * WHERE { 2 SERVICE <http://resource1> { ?s ?p ?o } 3 SERVICE <http://resource2> { ?s a :fish } }
Listing 2. Example SPARQL query for VC reordering.
II. Unbound Variable Count (UVC). A service pattern containing many new unbound variables is more likely to retrieve a higher number of results compared to a service pattern with less unbound variables. Thereby, we can also consider the set of binding Bi before the execution of a service pattern si. Let first V u(gi, Bi) be the set of new (unbound) variables of gi given Bi. The unrestrictiveness of gi can be now defined as:
unrestrictiveness(gi|Bi) = |V u(gi, Bi)| Listing 3 shows an example for this case. After the execution of the first service pattern, we should better run the third one since all its variables are already bound. The second service pattern contains one unbound variable, although its total number of variables is less than those of the third service pattern. 1 SELECT * WHERE { 2 SERVICE <http://resource1> { 3 <http://entity1> :birthPlace ?place1 ; :friend ?entity2 ; :workPlace ?place2 } 4 SERVICE <http://resource2> { ?entity2 a ?type } 5 SERVICE <http://resource3> { ?entity2 :birthPlace ?place1 ; :workPlace ?place2 } }
Listing 3. Example SPARQL query for UVC reordering.
III. Weighted Unbound Variable Count (WUVC). The above formulas do not consider the type of the unbound variables in the graph pattern, i.e., whether they are in the subject, predicate or object position in the triple pattern. For a graph pattern gi and a set of bindings Bi, let Vsu(gi, Bi), Vpu(gi, Bi) and Vou(gi, Bi) be the set of subject, predicate and object unbound variables in gi, respectively. Let also ws, wp and wo be the weights for subject, predicate and object variables, respectively. The unrestrictiveness of gi can be now defined as: unrestrictiveness(gi|Bi) = |Vsu(gi, Bi)| · ws + |Vpu(gi, Bi)| · wp + |Vou(gi, Bi)| · wo (6)
According to [
(5)
matching a predicate than an object, and more triples matching an object than
a subject. When considering variables, selectivity is opposite: a subject variable
may return more bindings than an object variable and an object variable more
bindings than a predicate variable. Consider for example the query in Listing 4.
The subjects having Greece as the birth place (1st service pattern) are expected
to be more than the friends of George (2nd service pattern), while the friends
of George are expected to be more than the different properties that connect
George with Nick (3rd service pattern). Thus, one can define weights so that
ws > wo > wp. Based on the distribution of subjects, predicates and objects
in a large Linked Data dataset of more than 28 billion triples (gathered from
more than 650 thousand sources) [
Listing 4. Example SPARQL query for WUVC reordering.
IV. Joins-aware Weighted Unbound Variable Count (JWUVC). When
a graph pattern contains joins, its restrictiveness is usually increased depending
on the number and type of joins (star, chain, or unusual join) [
Listing 5 shows an example for this case. The first service pattern contains a star join, the second a chain join, and the third an unusual join. The unusual join will probably return fewer results than the star and chain joins. 1 SELECT * WHERE { 2 SERVICE <http://resource1> { ?ent1 :birthPlace :Greece ; :workPlace :Germany } 3 SERVICE <http://resource2> { <http://George> :friend ?ent1 . ?ent1 :friend <http://Nick> } 4 SERVICE <http://resource3> { <http://George> ?p <http://Nick> . ?p :label "best friend" } }
Listing 5. Example SPARQL query for JWUVC reordering.
In Section 4 we evaluate the effectiveness of the above four methods on finding the optimal, in terms of query execution time, query reordering. 3.3
Handling of Special Cases
Query plans with same cost. In case the lowest unrestrictiveness cost is the
same for two or more query reorderings, we consider the number of literals and
filter operators contained in the graph patterns. Literals are generally considered
more selective than URIs [
SERVICE within OPTIONAL. In case a service call is within an optional pattern, then we separately reorder the service patterns that exist before and after it. An optional pattern requires a left outer join and thus changing its order can distort the query result.
Variable in SERVICE clause. If a service clause contains a variable instead of a URI, we should ensure that this variable gets bound before the execution of the service pattern. Thereby, during reordering we ensure that all other services containing this variable in their graph patterns are placed before the service pattern having the variable in its clause.
Projection variables. The set of variables that appear in the SELECT clause of a service pattern are called the projection variables. Since these are part of the answer and affect the size of the bindings, we only consider these variables in all the proposed formulas.
UNION operator, nested patterns, combination of triple and SERVICE patterns. In this work we do not study the case of queries containing the UNION operator as well as nested patterns. Such queries require the reordering of groups of service patterns which is not currently supported by our implementation. In addition, our implementation does not yet support the case of queries containing both triple patterns (that query the “local” endpoint) and service patterns. We leave the handling of these cases as part of our future work. 3.4
Computing a near-optimal query-execution plan Computing the unrestrictiveness score for all the different query reorderings may be prohibitive for large number of service patterns, since the complexity is n! (where n is the query’s number of service patterns). This applies in all the proposed optimization methods apart from VC where no all permutations are needed to be computed. For example, for queries with 5 service patterns there are 5! (=720) different permutations, however for 10 service patterns this
number is increased to more than 3.6 million permutations and for 15 to around 1.3 trillion.
Table 1 shows the time required for computing the reordering with the lowest cost for different number of service patterns using the JWUVC method (the time is almost the same for also UVC and WUVC). Our implementation (cf. Footnote 5) is in Java and uses Apache Jena for decomposing the SPARQL query, while we run the experiments in an ordinary computer with processor Intel Core i5 @ 3.2Ghz CPU, 8GB RAM and running Windows 10 (64 bit).
We see that the time is very high for queries with many service patterns. For example, more than 1 hour is required for just finding the reordering with the lowest cost for a query with 12 service patterns. This illustrates the need for a cost-effective approach which can find a near-optimal query execution plan without needing to check all the different permutations. We adopt a greedy algorithm starting with the service pattern with the smaller unrestrictiveness score (local optimal choice) and continuing with the next service pattern with the smaller score, considering at each stage the already bound variables of the previous stages. To find the local optimal choice, we can use any of the proposed unrestrictiveness formulas. Considering the UVC formula for example, in the query of Listing 6 the greedy algorithm first selects the 2nd service pattern since it contains only 1 variable. In the next stage, it selects the 3rd service pattern which contains 2 unbound variables, fewer than those of the 1st service pattern. 1 SELECT * WHERE { 2 SERVICE <http://resource1> { ?ent1 :birthPlace ?place1 ; :workPlace ?place2 ; :friend ?ent2 } 3 SERVICE <http://resource2> { ?ent2 a :Actor } 4 SERVICE <http://resource3> { ?ent2 :birthPlace ?place1 ; :workPlace ?place2 } }
Listing 6. Example SPARQL query for choosing a near-optimal query plan.
4
We evaluated the effectiveness of the proposed query reordering methods using
real federated queries from the LargeRDFBench [
SELECT * WHERE { SERVICE <ex1> {..} OPTIONAL { SERVICE <ex2> {..} } } to the query:
SELECT * WHERE { SERVICE <ex1> {..} SERVICE <ex2> {..} }
The final evaluation dataset contains 17 queries of varying complexity (each one containing at least two service patterns), while their service patterns require access to totally 7 remote SPARQL endpoints. Note that there is no benchmark for SPARQL-LD, however this does not affect the objective of our evaluation since the proposed methods do not distinguish between SPARQL 1.1 and SPARQL-LD queries (a SPARQL endpoint can be considered an HTTP resource containing all the endpoint’s triples).
For each query, we found the optimal reordering by computing the execution time of all possible permutations (average of 5 runs). Then, we examined the effectiveness of the proposed optimization methods (VC, UVC, WUVC, and JUWVC, as described in Section 3.2) on finding the optimal query execution plan. Figure 1 shows the results. VC finds the optimal query plan in 8/17 queries (47%), UVC in 10/17 queries (59%), WUVC in 9/17 queries (53%), and JUWVC in 15/17 queries (88%). We notice that the JUWVC method, which considers the number and type of joins, achieves a very good performance. Given the infrastructure used to host the SPARQL endpoints in our experiments9, query reordering using JUWVC achieves a very large decrease of the query execution time for many of the queries (for example, from minutes to some seconds for the queries S4, S10, S12, C7, C10).
JUWVC fails to find the optimal query plan for the queries S13 and C6, which both contain 2 service patterns. The first service pattern of S13 contains 1 star join and the second 2 star joins. As regards C6, its first service pattern contains 1 star join and 1 chain join, and its second 5 star joins. In both queries, although the second service pattern contains more joins than the first service pattern, it returns larger number of bindings and this increases the number of calls to the first remote endpoint and thus the overall query execution time. Note that, without exploiting dataset statistics, such cases are very difficult to be caught by an unrestrictiveness formula.
8 Although this transformation changes the query results, it does not affect the objective of our evaluation. 9 2x Intel Xeon CPU E5-2630 @ 2.30GHz, 6-core, 384GB RAM.
1.E+07 1.E+06 1.E+05 e l a c s l-g1.E+04 o ) s (m1.E+03 e m i T1.E+02 1.E+01 1.E+00 OPTIMAL VC UVC WUVC JWUVC
S2 S3 S4 S5 S10 S11 S12 S13 S14 C1 C2 C5 C6 C7 C8 C9 C10
Query
As regards the effectiveness of the greedy algorithm which avoids computing the cost of all possible permutations (cf. Section 3.4), it manages to find the reordering with the lowest cost using JUWVC in 16/17 queries (94%). It fails for the query C2, however the returned reordering is very close to the optimal (the difference is only a few milliseconds).
One of the limitations of such a fully heuristics-based method is that it is
practically impossible to always find the optimal query plan. However, this is
the case also for methods that pre-compute and exploit metadata and statistics
from the remote resources, or which make use of caching. The reason is that
the Web of Data is a huge and constantly evolving information space, meaning
that we may always need to query a new, unknown resource discovered during
query execution. A solution to this problem is the exploitation of VoID [
We have proposed and evaluated a set of fully heuristics-based query reordering methods for federating queries in SPARQL 1.1 and SPARQL-LD. The proposed methods reorder a set of service graph patterns based on their selectivity (restrictiveness) and do not require the gathering and use of statistics or metadata 10 https://www.w3.org/TR/void/#void-file
from the remote resources. Such an approach is widely-applicable and can be exploited on top of existing SPARQL 1.1 and SPARQL-LD implementations.
Since the new query functionality offered by SPARQL-LD (allowing to query any HTTP resource containing RDF data) can lead to queries with large number of service patterns which in turn can dramatically increase the time to find the optimal reordering, we proposed the use of a simple greedy algorithm for finding a near-optimal query execution plan without checking all possible query reorderings. The results of an experimental evaluation using an existing benchmark showed that a query reordering method which considers the number and type of unbound variables and the number and type of joins achieves the optimal query plan in 88% of the examined queries, resulting in a large decrease of the overall query execution time (from minutes to a few seconds in many cases). Regarding the greedy algorithm, it has an accuracy of 94% in finding the reordering with the lowest cost.
As part of our future work, we plan to offer a holistic query reordering approach which will cover any type of federated queries. This involves the handling of queries containing UNION and nested graph patterns, as well as queries which combine triple and service patterns. We also plan to offer this query reordering functionality as a web service, allowing for on-the-fly query optimization. Acknowledgements The work was partially funded by the European Commission for the ERC Advanced Grant ALEXANDRIA under grant No. 339233.