Since the proposal of RDF as a standard for representing statements about entities, diverse interfaces to publish and strategies to query RDF data have been proposed. Although some recent proposals are aware of the advantages and disadvantages of state-of-the-art approaches, no work has yet tried to integrate them into a hybrid system that exploits their, in many cases, complementary strengths to process queries more e ciently than each of these approaches could do individually. In this paper, we present hybridSE, an approach that exploits the diverse characteristics of queryable RDF interfaces to e ciently process SPARQL queries. We present a brief study of the characteristics of some of the most popular RDF interfaces (brTPF and SPARQL endpoints), a method to estimate the impact of using a particular interface on query evaluation, and a method to use multiple interfaces to e ciently process a query. Our experiments, using a well-known benchmark dataset and a large number of queries, with result sizes varying from 1 up to 1 million, show that hybridSE processes queries up to three orders of magnitude faster and transfers up to four orders of magnitude less data.
E ciently evaluating SPARQL queries over heterogeneous RDF interfaces, such
as SPARQL endpoints and Triple Pattern Fragments (TPFs) [
In this paper, we examine and show how the advantages of available queryable RDF interfaces can be exploited to nd an execution plan that makes the best use of the strengths of available interfaces. We propose hybridSE (hybrid SPARQL Engine), a smart client that is aware of alternative interfaces for the same dataset, exploits their strengths to evaluate di erent parts of a query and combines partial answers to produce the nal result.
In summary, this paper makes the following contributions: Characterization of existing queryable RDF interfaces: SPARQL endpoints, triple pattern fragments, and bindings-restricted triple pattern fragments Estimation of the impact of di erent RDF interfaces on query execution Method to compute good execution plans exploiting advantages of di erent RDF interfaces
Extensive evaluation using the well-known WatDiv benchmark [
The basic idea of exploiting multiple data sources and interfaces has been
considered in the database community in the context of multistore systems or
polystores [
As with other data models, SPARQL queries can be evaluated using
different interfaces, such as SPARQL endpoints, link traversal over RDF
documents [
Recently, Hartig et al. [
E ciently querying multiple homogeneous interfaces that provide access to
di erent datasets, i.e., processing federated SPARQL queries, has been
extensively studied, in the context of SPARQL endpoints [1,3,7,11,12,17{19,22,23,25]
and LDF [
In this section, we brie y discuss the main characteristics of some of the most popular queryable RDF interfaces.
SPARQL endpoints are speci cally designed to e ciently query RDF datasets. Having access to the whole dataset in advance allows for computing indexes and enables the use of tailored physical operators according to the characteristics of the data. Therefore, SPARQL endpoints can, for instance, rely on cost functions to determine whether a symmetric hash join is more suitable than a bound join to evaluate a join in a given query.
However, being able to evaluate any (or almost any) SPARQL query comes
at a cost. Query optimization in consideration of all available alternatives
(indexes, auxiliary structures, join order, join algorithm, etc.) can represent an
unnecessary overhead for relatively simple queries, for which a straightforward
optimization without considering alternatives would result in a su ciently good
query execution plan. Moreover, in some cases cost functions rely on low
quality cardinality estimations and lead to produce execution plans with very large
execution times [
Verborgh et al. [
Even if the costs of providing access to RDF data is considerably reduced by
using TPF interfaces, the paradigm used by TPF leads to less e cient query
executions [
Table 1 shows an overview of the studied interfaces. For powerful servers and
low numbers of clients, SPARQL endpoints represent the best option to e
ciently process queries as they transfer the lowest amount of data and have no
requirement on the client side resources. For very high numbers of clients with
no requirements regarding answer time and some local resources available for
query processing, the TPF interface o ers the best option. A server can respond
to a very large number of simple queries while the clients take over most of
the query processing tasks. Lastly, if clients and servers have resources available
for query processing, brTPF is the best option. As computational power spent
by brTPF servers to process requests is between SPARQL endpoints' and TPF
servers', brTPF servers can answer more requests. Moreover, as these requests
reduce the network tra c, query results are obtained faster.
In this paper, we assume that the most expressive interface, i.e., SPARQL
endpoints, takes advantage of having access to server-side resources to e ciently
process queries by relying on indexes. We further assume that the less expressive
interfaces, i.e., TPF [
Query processing time mainly depends on three aspects: (i) query processing time at the server, (ii) transfer time of (intermediate) results from servers to clients, and (iii) query processing time at the client. While all aspects are in uenced by the size of intermediate results, aspects (i) and (iii) are also in uenced by the data structures used to store intermediate results during query processing, e.g., available indexes and the complexity of the algorithms used to process the query.
A restricted interface, such as TPF, has very low query processing time at the server, transfer time depends on the sizes of intermediate results, and query processing time at the client can be signi cantly high depending on the selectivity of the triple patterns in the query. Moreover, queries with high numbers of intermediate results lead to a high number of requests to the TPF server during query processing, which can signi cantly slow down execution.
A SPARQL endpoint has a signi cantly higher query processing time at the server, transfer time depends on the query result size, and query processing time at the client is very low (and usually negligible).
If the SPARQL endpoint had enough query processing power to instantly answer the queries of all users, then the best possible approach to e ciently process queries would be to use the SPARQL endpoint in all cases. However, the available query processing power of SPARQL endpoints is limited and this processing power should be used mainly in cases when using other interfaces would incur in signi cantly higher query processing times in order to improve the overall e ciency of query processing for all clients.
Knowing the sizes of intermediate and query results could help deciding which
interface to use to execute the queries. While computing this knowledge before
execution time has been addressed in diverse works [
To illustrate the impact of the interfaces on query e ciency and resource
usage, we use queries generated using the WatDiv benchmark [
Query A (Listing 1.1) has one small fragment, tp1, and joins on di erent
variables. Thus, Query A is evaluated more e ciently by brTPF, which results in
a relatively low amount of data transfer in comparison to the number of results,
while the endpoint relies on cardinality estimations that are deteriorated by
the di erent object-subject joins and the unsatis ed assumption of query triple
pattern independence [
Query B (Listing1.2) involves only fragments with relatively large estimated cardinalities and many subject-subject joins on the same variables. Then, using brTPF results in relatively high amounts of data transfer in comparison to the number of results. Virtuoso is able to exploit existing indexes to e ciently process Query B outperforming brTPF for this particular query.
As the number of calls to the servers increases with the number of clients issuing queries, the servers represent bottlenecks, which can result in higher response times. 1 In these setups, described in Section 6, each client executes around 200 di erent queries. Queries A and B are two example queries executed by one of the clients.
Algorithm 1 Evaluate BGP
Input: sorted triple patterns tps in the BGP; set of initial mappings ms; threshold that guides the choice of interface
Output: A set of answer mappings (ms) to BGP tps 1: function evaluateBGP (tps,ms,threshold) 2: if size(tps)=0 then 3: return ms 4: end if 5: if estimatedFragmentCardinality( rst(tps)) > threshold ^ size(tps) > 1 then 6: ms' evaluateBGPAtSPARQLEndpoint(tps, ms) 7: ms ms' ./ ms 8: else 9: rst rst(tps) 10: tps removeFirst(tps) 11: ms' evaluateTPAtBrTPFServer( rst, ms) 12: ms ms' ./ ms 13: ms evaluateBGP(tps, ms,threshold) 14: end if 15: return ms 16: end function
The goal of hybridSE is to use a combination of multiple interfaces to reduce the overall query execution time. The simpler interface should be used for relatively simple computations, and if we already know there are not many intermediate results, then an interface like brTPF is the best. However, in some cases applying the simpler query execution approach and using the simpler interface leads to very expensive query execution times. In such cases, we should make use of more costly interfaces that are able to exploit knowledge about the data to produce better execution plans.
Algorithm 1 sketches how hybridSE implements the aforementioned heuristics. The list of triple patterns and their order is described in tps. Hence, to achieve e cient query processing, tps should be sorted according to selectivity and this can be based on several heuristics. The order used in this paper is as follows: The rst triple pattern is the one with the lowest estimated fragment cardinality. The second triple pattern is the one with the greater number of bound variables, when considering the bound variables after the evaluation of the rst triple pattern, and so on. As such, it is more likely that fragment cardinalities will be reduced as the number of bound variables increases. Note that it is possible to use any other execution order for triple patterns, e.g., updating the order of the triple patterns after the evaluation of each triple pattern query at the brTPF server.
For Query A (Listing1.1), the rst triple pattern is tp1 with an estimated fragment cardinality of 47. The next one to execute is tp2 because after evaluation of tp1, we know the bindings for variable ?v1 and can use them to obtain a smaller fragment for triple pattern tp2.
The estimated fragment cardinality of the triple pattern with higher selectivity is used to determine whether brTPF should be used or if it is necessary to use a more expressive interface, i.e., the SPARQL endpoint (Line 5), as we consider that the triple patterns in tps are sorted according their selectivity this is the rst triple pattern in tps. In any case, the previously obtained mappings are passed on to the function evaluating the graph pattern (BGP or TP), line 6 or 11, and only the mapping values that are relevant for the pattern evaluation are included in the request sent to the server. Listing 1.3: Query C: Find the purchases of friends of the reviewers of a set of products SELECT * WHERE {
VALUES (? v2 ) { ( wsdbm : P r o d u c t 2 4 9 5 7 ) ( wsdbm : P r o d u c t 2 0 0 0 3 ) ( wsdbm : P r o d u c t 1 4 3 9 1 ) ( wsdbm : P r o d u c t 1 8 0 3 9 ) ( wsdbm : P r o d u c t 1 9 3 3 3 ) ( wsdbm : P r o d u c t 1 8 6 8 7 ) ( wsdbm : P r o d u c t 1 0 4 1 5 ) ( wsdbm : P r o d u c t 1 3 6 8 3 ) ( wsdbm : P r o d u c t 1 5 5 0 5 ) ( wsdbm : P r o d u c t 2 0 2 ) ( wsdbm : P r o d u c t 1 2 6 2 ) } } ? v2 rev : ha sR ev ie w ? v3 . ? v3 rev : reviewer ? v4 . ? v4 wsdbm : friendOf ? v5 . ? v5 wsdbm : m a k e s P u r c h a s e ? v6 .
For Query A (Listing1.1) the rst triple pattern (tp1 ) is evaluated rst and the 46 values of ?v1 are used to evaluate tp2 using the brTPF interface; the 46 values are used to build two brTPF requests, one with 30 bindings and another one with 16 bindings, considering a maximum of 30 bindings per request. As the resulting fragments have estimated cardinalities of 26 and 15, the evaluation continues using brTPF. The 41 values obtained for ?v2 are used to build two brTPF requests to evaluate tp3. As the retrieved fragments have estimated fragment cardinalities of 489 and 113, thresholds of up to 112 result in evaluating the triple patterns f tp3 . tp4 . tp5 . tp6 g using the Virtuoso endpoint. As such, the values for ?v2 are passed on to the Virtuoso endpoint in a VALUES clause, as shown in Listing 1.3, rather than to the brTPF server. Notice that the di erence between the estimated fragment cardinality, 15, and the actual fragment cardinality, 11, used to generated Query C, cf. Listing 1.3, is relatively low. Likewise, the obtained 30 bindings from the other brTPF request, also close to the estimated fragment cardinality of 26, are used to build a similar request for the Virtuoso endpoint.
Table 3 shows the evaluation metrics for hybridSE obtained when executing queries A and B (Listings 1.1 and 1.2) in the setups with 4 and 16 clients introduced in Section 4, and used to evaluate brTPF and endpoint (values in Table 2b). While Query A has been evaluated as described above exploiting the advantages of both brTPF and endpoint, the execution of Query B relies exclusively on the endpoint. Using hybridSE, Query A is executed considerably more e cient, at least two times faster for the setup with 4 clients and 6 times faster for the setup with 16 clients, and achieves a similar performance as a SPARQL endpoint for Query B. To evidence the potential of hybridSE, we have implemented a prototype to evaluate BGP queries using a combination of SPARQL endpoints and brTPF servers. The prototype uses Algorithm 1 described in Section 5 to exploit the advantages of each RDF interface.
Dataset and queries: We use the WatDiv benchmark [
Hardware con guration: For our experiments we used virtual machines (VMs) running Ubuntu Linux 4.4.0 64bit x86 with eight cores and CPU 2294.250 MHz with a network speed of up to 10,000Mb/s. A dedicated VM was used to deploy the servers. A Virtuoso 7.2.4.2 endpoint was set up to use up to 7GB of RAM, 1 million result set rows, 6,000s estimated execution time, and 600s execution time. A brTPF server was set up to use up to 8GB of RAM. Up to four VMs, with 16GB of RAM, were used to run clients for the experiments. Each (client) VM ran up to eight clients simultaneously.
Evaluation metrics: 1. Execution Time (ET) is the time elapsed since the query is issued until the complete answer is produced (with a timeout of 300,000 ms), 2. Number of Transferred Bytes (NTB) is the amount of data transferred from the brTPF server or the SPARQL endpoint to the query engine during query evaluation. It includes the Total Number of Transferred Triples from the brTPF server (TNTTTPF) and the Number of (sub)query Results obtained from the SPARQL Endpoint (NRSE). NTB is computed as the sum of bytes in the string representations of TNTTTPF and NRSE. 3. Number of Calls to the brTPF server (NCTPF) is the number of (sub)queries sent to the brTPF server. 4. Number of Calls to the SPARQL Endpoint (NCSE) is the number of (sub)queries sent to the SPARQL endpoint. 5. Throughput (T): is the number of queries executed by all the clients in one time unit. It is computed as the number of queries executed by the clients divided by the total execution time. 6.1
To evaluate the performance of hybridSE, we compare its results to the SPARQL endpoint and the brTPF client. We compare the performance of the WatDiv queries based on the aforementioned metrics. hybridSE has as input a threshold value representing the turning point where the least expressive interface should be switch to the most expressive one. In Algorithm 1, a threshold is used to choose which interface should be used to avoid ine cient processing of 4 As available at http://olafhartig.de/brTPF-ODBASE2016/ on January 2018. These implementations have some limitations, as pointed out by Hartig in his review of our work https://openreview.net/forum?id=BJeDc51elX, the client is purposely simple and lacks adaptive query optimization techniques to exploit metadata obtained during query processing and the cardinality estimations provided by the server can be totally inaccurate. the queries from all the clients. We tested the WatDiv queries with three di erent thresholds: 25, 50, and 75. We also performed the WatDiv experiments with di erent numbers of clients: 1, 4, 8, 16 and 32. However, due to space limitations, we will only show results for 4 and 16 clients. After a comparison of hybridSE's performance for the di erent thresholds, we will consider only threshold=50 for the rest of the paper. Timed out queries are omitted from the plots5. ) s (m2e+05 e m i T n o itu1e+05 c e x E (a) Detailed runtime per query Because our evaluation comprises a large number of queries and to ease the readability of the results, we present the average values of the metrics for groups of queries with similar amounts of transferred bytes (NTB). As each approach might exhibit di erent NTB, we have considered for each query the average NTB, ANTB, over the three approaches, and divided the queries into clusters 5 Fewer queries timed out using hybridSE, e.g., in the 16 clients setup, only 134 out of 3,245 queries timed out, while 812 and 350 timed out using brTPF and endpoint. according to ANTB, such that the results obtained for the three approaches for each query are considered in the same cluster. Therefore, the comparison over these clusters corresponds to comparing the approaches for the same set of queries and eases the readability, i.e, in Figure 1b, instead of showing around 3,200 points per approach (one for each query), as in Figure 1a, we depict only 15 points (one per cluster), where each point represents the average value for queries with ANTB in the interval [x*106,y*106) for the label [x,y) in the x-axis of Figure 1b. Detailed results for all the setups and metrics are available at our website http://qweb.cs.aau.dk/hybridse.
Impact of the threshold on hybridSE's performance Figure 1b shows the average execution time obtained when using di erent values of threshold in the setup with 16 clients. We observe that as the threshold increases, the performance of hybridSE improves in average. The di erence is quite small, having a very close average over all the queries with just slightly worse performance for rare queries when the threshold is 25. Scalability of hybridSE Figure 2 shows the average execution time obtained when using di erent values for the threshold in a setup with 4 clients, where around 800 queries were executed. In comparison to Figure 1b, where around 3,200 queries were executed, we observe that even if the workload is multiplied by four, the execution time increases only sub-linearly.
Execution time Figure 3 shows the average execution time obtained for hybridSE, brTPF and endpoint in the setup with 16 clients. Even if brTPF and Endpoint faced challenging queries that have considerably degraded their execution time for some groups of queries, hybridSE has exploited the advantages of each of these approaches, i.e., relying on brTPF only for very simple subqueries with one triple pattern or accessing relatively small triple pattern fragments that contribute to reducing the di culty of the queries that are later sent to the Fig. 4: Total Number of Transferred Bytes from the TPF server and the SPARQL Endpoint (NTB), 16 clients setup for BrTPF, Endpoint and hybridSE approaches (x-axis, *105) Number of Transferred Bytes Figure 4 shows the average number of transferred bytes for hybridSE and the brTPF and endpoint baselines in the setup with 16 clients. Clearly the endpoint baseline transfers the lowest number of bytes by transferring only the query results, and the brTPF baseline transfers higher numbers of bytes because the used interface only evaluates triple pattern queries with some binding values. hybridSE remains very close to the data transfer incurred by the more e
cient approach in this metric (endpoint), therefore using hybridSE does not result in any considerable increase of the network tra c with respect to the best possible alternative.
● brTPF hybridSE ● ● ● ● ● ● ● ● [0,2) [2,4) [4,6) [6,8) [8,10)[10,12)[12,14)[14,16)[16,18)[18,20)[20,22)[22,24)[24,26)[26,28)[28,30)[30,32)[32,34)
Avg. Calls to the TPF server Range (a) Total Number of Calls to the brTPF server
endpoint hybridSE r e rve104 s F P T the102 ● o t s ll aC100 . g v A t 5 n i o p 4 d n E 3 e h t 2 o t lls 1 a .C 0 g v A−1 [0.5,0.[60).6,0.[70).7,0.[80).8,0.9)[0.9,1)[1,1.[11).1,1.[21).2,1.[31).3,1.[41).4,1.[51).5,1.[61).6,1.[71).7,1.[81).8,1.9)[1.9,2)[2,2.[12).1,2.[22).2,2.[32).3,2.[42).4,2.[52).5,2.6)
Avg. Calls to the Endpoint Range (b) Number of Calls to the SPARQL Endpoint
System Throughput Figure 6 shows system throughput for hybridSE and the brTPF and endpoint baselines in the setup with 16 clients. The throughput of hybridSE is considerably higher than the other approaches. hybridSE is at least ve times faster and up to 40 times faster than the baselines. Therefore, the improvement is not only due to having more resources available (two interfaces instead of one) but also due to making better use of these resources. 7
In this paper, we have presented )30 hybridSE, an approach for exploit- m / ing the di erent capabilities of avail- q able LDF interfaces to process queries t(#20 as e ciently as possible but with- phu out unnecessary usage of resources. ug10 hybridSE uses available information, roh such as the number of triples per frag- T 0 ment, to determine when it is more brTPF endpoint hybridSE e cient to use the brTPF client or send a (sub)query to the SPARQL Fig. 6: System throughput, 16 clients endpoint. Our experimental evaluation shows that hybridSE produces query execution plans that are better in terms of data transfer and execution time than the available implementation for the brTPF interface.
As future work, it would be interesting to assess if the limitations of the
available brTPF implementation had a signi cant impact on our experimental
results and to extend hybridSE for more complex fragments of the SPARQL
query language. Additionally, we would like to combine hybridSE with other
interfaces, such as other TPF clients, e.g., [
Acknowledgments. This research was partially funded by the Danish Council for Independent Research (DFF) under grant agreement no. DFF-4093-00301 and Aalborg University's Talent Management Programme.