The existing web of linked data inherently has distributed data sources. A federated SPARQL query system, which queries RDF data via multiple SPARQL endpoints, is expected to process queries on the basis of these distributed data sources. During a federated query, each data source may consist of a search space of nontrivial size. Therefore, nding the optimal join order to minimize the size of intermediate results from di erent sources is key to optimizing the performance of such federated queries. In this study, we present a dynamic optimization approach to determining join order, which can nd more optimized join plans than static optimization approaches. Our experimental results show that our proposed approach stably improves the performance of a federated query as the query becomes increasingly complex.
Linked data technology has substantially contributed to the freeing of data conned in individual silos; however, searching over such data is still performed within a single SPARQL endpoint, making it di cult to truly a rm that data are truly freed from their respective silos even in the linked data space.
A number of federated query systems have been developed to enable search across multiple endpoints. Although it is di cult to assert that the performance of these query systems is close to production level, the research community is continuously trying to improve such performance [2,3,5,6,8,10]. In this paper, we propose a novel technique, i.e., dynamic join order optimization, to signi cantly improve the performance of federated search.
A federated query inherently has to explore multiple endpoints, and while traversing these endpoints, results from one endpoint must be joined with results from the next endpoint and so on. Here each endpoints may consist of a search space of nontrivial size. To e ciently perform the search across these multiple search spaces, determining the optimal join order is key to good performance.
Join order optimization has been a research topic for a number of years [4,11{ 13]; however, in these studies, the common approach is to somehow try to nd the optimal join order before beginning actual exploration into the endpoints. We therefore call this static join optimization. Considering the importance of join order on the performance of a SPARQL query, we argue that join order cannot be su ciently optimized at the onset of the query; further, by utilizing intermediate results obtained during search, join order can be signi cantly improved. We present a simple algorithm for dynamic join order optimization as well as an implementation in the form of an extension to FedX.
Our experimental results show that dynamic join order optimization is e ective in controlling the search space size, thereby avoiding explosions in size. We also developed a new benchmark for evaluating the join optimization of federated query performance. This benchmark is developed to include more complex join operations than those introduced in FedBench [8]. Our experimental results here show that our dynamic join order approach stably improves the performance of federated search. 2
In relational databases, associated data entries are maintained in tables consisting of any number of columns; in RDF, data pieces are maintained in triples, the smallest unit of representation for typed binary relationships. Therefore, join operations generally occur much more frequently when processing a SPARQL query than when processing a corresponding SQL query.
(a) Static approach (b) Dynamic approach (c) Final results for two approaches
Suppose we have a query that can be decomposed into three subqueries, Qa,
Qb, and Qc, which have answers Ra, Rb, and Rc, respectively, from three
different endpoints. Then, nal answers are to be those that satisfy the constraints
set by the three subqueries. In Figure 1(c), the three circles Ra, Rb, and Rc
represent the sets of results of the three subqueries, with the gray area
representing the nal results. To reach the set of nal results, there are six distinct
join orders, i.e., (
If the size of the intermediate results is known or can be estimated in advance, the join order may be optimized. For example, the result size of the individual subqueries may be estimated in advance as jRaj < jRbj < jRcj. Based on this information, the join order may be optimized as A ! B ! C. Below are the necessary operations that must occur in the given order: 1. Receive result set Ra. 2. Bind variables in query Qb using result set Ra and then submit intermediate results to Eb. 3. Receive result set Ra \ Rb. 4. Bind variables in query Qc using result set Ra \ Rb and then submit intermediate results to Ec. 5. Receive nal result Ra \ Rb \ Rc.
With the given join order, the size of the intermediate result sets that must be handled is jRaj + jRa \ Rbj. This is more or less the scenario in which most federated search systems have been developed in terms of join order optimization, i.e., to better optimize the join order, attempt to estimate the result set sizes of individual subqueries with heuristics or statistical information.
In this paper, we argue that even if the initial estimation is performed
perfectly, there is still large room for further optimization. Note that after Qa is rst
executed, there are two choices for the next execution, i.e., Qb and Qc. Although
jRbj is estimated to be smaller than jRcj, choosing Qc for the next execution
is in fact a more optimal choice because jRa \ Rcj (i.e., Figure 1(b)) is smaller
than jRa \ Rbj (i.e., Figure 1(a)). To select the optimal choice in this case, we
propose a dynamic join order optimization approach that evaluates queries as
follows: (
To date, research regarding join order optimization, both in relational database and RDF data management systems, has been centered on static optimization in which optimization is performed only once before queries are actually executed. As an example, FedX builds a subquery for a group of triple patterns in which each triple exclusively shares a single relevant source. FedX assumes this type of exclusive subquery, and the subquery with fewer free variables has a high selectivity ranking. The assumed selectivity ranking and variable counting technologies are not suitable for all situations as queries become complex. DARQ [6], SPLENDID [3], ADERIS [5], Avalanche [2], and other similar systems use pre-computed information, such as service description or VoID, to estimate selectivity and optimize join order; however, none of these can overcome the fragility of static optimization techniques. More speci cally, the search space changes as the query is processed. Based on this and the frequency of join operations in a SPARQL query, we argue that join order should be optimized by utilizing intermediate results with a dynamic approach. 3 3.1
To best introduce our dynamic join order optimization algorithm, we rst show a simple algorithm that uses the static join order strategy. Here we assume the existence of a sortSubQueries operation to sort subqueries by some measure and an evaluateQuery operation to output a set preResults of results for variables appearing in a given SPARQL query.
Algorithm 1 Query execution with static join order optimization 1: function StaticJoin(setSubQueries: a set of subqueries) 2: listSubQueries sortSubQueries(setSubQueries) 3: preResult ; 4: while listSubQueries is not empty do 5: curSubQuery pop(listSubQueries) 6: preResult evaluateQuery(preResult; curSubQuery) 7: end while 8: return preResult 9: end function Algorithm 1 shows the ow of query execution when a static join order optimization scheme is applied. Given the setSubQueries set of subqueries, the algorithm rst sorts the subqueries on the basis of estimations of their result sizes and then executes the subqueries in the given order. In other words, the optimal join order is determined before the execution of any subqueries, and the join order does not change during execution, which is why we call it a "static" optimization strategy. 3.2
Dynamic join order optimization Algorithm 2 shows the ow of query execution with dynamic join order optimization. Unlike the static optimization strategy described above, the optimal subquery to be executed next is determined at each step of query execution by considering the intermediate results obtained thus far. We therefore call this approach a "dynamic" optimization strategy.
In the algorithm, ndOptimalSubQuery nds the subquery with the highest selectivity among all subqueries (line 4). On line 6, the executed subquery is removed from the subquery set, and then this process repeats until all subqueries nish.
Finding the optimal subquery In Algorithm 3, we apply a greedy strategy at each step to nd the subquery that has the smallest result size. Algorithm 3 Finding the optimal subquery 1: function findOptimalSubQuery(setSubQueries, preResult) 2: optimalSubQuery setSubQueries[0] 3: minSize M AX V ALU E 4: for each subQuery in setSubQueries do 5: if jsetSubQueriesj equals 1 then 6: break 7: end if 8: size estimateResultSize(subQuery; preResult) 9: if size < minSize then 10: optimalSubQuery subQuery 11: minSize size 12: end if 13: end for 14: return optimalSubQuery 15: end function Estimating result size There are many approaches for estimating the result size of a subquery, for example, using pre-computed statistical information. In this paper, our implementation uses COUNT queries that do not need any precomputed information. More speci cally, we bind previous subquery results to each remaining subquery, construct a COUNT query, and send it on the y to the relevant sources to determine under the current conditions how many intermediate results they will produce.
Note that a COUNT query is a SPARQL query with the form \select count(*)..."
that evaluates the result size of a subquery. We construct COUNT queries for all
subqueries as follows: (
SELECT count(*) WHERE{ {?enzyme kegg :substrate <http://bio2rdf.org/kegg:D06880> . ?enzyme rdf:type kegg:Enzyme>. ?reaction kegg:enzyme ?enzyme . } UNION … UNION {?enzyme kegg :substrate <http://bio2rdf.org/kegg:C11613> . ?enzyme rdf:type kegg:Enzyme>. ?reaction kegg:enzyme ?enzyme . } } (c) COUNT query: bound with the values of ?cpd from the previous subquery
For dynamic join order optimization, the system must apply all previous query results to the candidate subqueries; however, when there are a large number of values in the intermediate results, it is costly to bind all values to the remaining subqueries and execute the large query. Note that for join order optimization, we need only a rough estimate of the size of the query results on which the subqueries may be ordered. This estimation does not need to be very precise because a small di erence in the size of results will not signi cantly impact the overall performance.
Thus, rather than exhaustively consider the entire set of intermediate results, we take a small sample of size n and order the subqueries by the size of the results after binding relevant variables with the sample values. In this work, we simply set the size of n to be 3. While it may be necessary to estimate the optimal sample size, at this point, we assume that it is not a critical factor for the reason noted above.
Instead of estimating the cost of expressions with VoID as SPLENDID, the
estimateResultsSize function actually sends the COUNT query to its relevant
data sources. Here, we note two important observations: (
We investigated how dynamic join optimization in uences the query performance in comparison with the static join. As we noted above, FedX is the fastest engine among the current federated SPARQL endpoint query systems according to recent benchmarks. We therefore implemented all the functions, including source selection, on the basis of the FedX system, and compared the di erences before and after using dynamic join optimization in conjunction with the FedX system. Further, we evaluated SPLENDID, which is expected to produce a good join order plan using statistical information and optimizing plans on the basis of dynamic programming techniques.
FedBench is a comprehensive benchmark suite for federated semantic data that considers the evaluation of UNION, FILTER, and OPTIONAL clauses; however, we note that almost all queries in this benchmark have a common characteristic, i.e., they include a single triple pattern with two bound variables and only one free variable, as shown in the query below from Cross Domain evaluation CD6.
SELECT ?name ?location ?news
WHERE {
?artist <http://xmlns.com/foaf/0.1/name> ?name . (
Benchmark setup For our benchmarks, we used ve real biological SPARQL endpoints from the Bio2RDF project [1], which is a di erent setup than FedBench [8], SP2Bench [9], and the ne-grained evaluation of SPARQL endpoint federation systems [7], all of which use a simulated federated environment and synthetic data or a subset of real data. For the life science eld, FedBench uses three biological datasets, namely KEGG, ChEBI, and Drugbank. Because the SPARQL endpoint for CHEBI in the Bio2RDF project [1] is still under construction, we selected KEGG, Drugbank, SIDER, OMIM, and PharmGKB.
These datasets connect to one another closely by relationships between gene, drug, disease, reaction, side e ect, and others. Table 1 presents the details of each dataset. The data are far more complicated than the FedBench life science data. The largest biological dataset in FedBench is a subset of ChEBI that includes 7.33 million triples, 28 predicates, and a single type. In the Bio2RDF project, the server of each endpoint is set to return a maximum of 10,000 results at a time, regardless of the real result size. This restriction is commonplace to lessen the burden on the server. Note that all settings in the Bio2RDF servers are beyond our control.
This benchmark focuses on testing the join operation in the SPARQL
endpoint federation. We consider the following points in designing the queries: (
In addition, the query set considers the numbers of variables in a triple pattern. RDF data could connect to each other via di erent paths, which brings about more free variables. The fewer bound variables, the more di cult it is to estimate selectivity. Here Q2 and Q3 include one triple pattern in which all variables are free, Q3 changes the position of the triple pattern, and Q4 increases another such triple pattern. The rest of the queries consider the in uence of the triple pattern with two bound variables. In this case, Q5, Q7, and Q8 have only one triple pattern with two bound variables, whereas Q6 has two such triple patterns. Next, Q7 is a variation of LS4 from FedBench, with Q7 obtained by slightly modifying the bound variables, thereby increasing the result size. Further, Q5 is a variation of Q7 obtained by changing the connected dataset and constructing a more complicated star Q8 subquery. Here Q6 tests a query with complicated star subqueries, evaluating the query connecting three datasets. Finally, Q1 is designed to evaluate the extreme case with only two join triple patterns.
We sequentially executed each query ve times, removing the largest and smallest values, calculating the mean value of the three remaining values. Query performance Figure 3 summarizes query performance, and Table 3 shows how intermediate results changed. Dynamic join optimization outperformed the original static FedX system during all queries, except for Q5. As for the time cost, for Q1, Q2, Q6, and Q8, the dynamic approach was faster than the original FedX system. FedX failed on Q4, which has two triple patterns in which all variables are free 1. With regard to the result completeness, the dynamic approach returned all results for all queries, whereas Fedx returned incomplete results for Q2, Q3, Q6, and Q7. Finally, SPLENDID returned all results for Q1, Q2, and Q4, in which Q2 and Q4 were slower than the dynamic join and Q1 was slightly faster; note that SPLENDID failed all other queries by reaching the one-hour timeout limitation.
Intermediate results shown in Table 3 detail the query performance of both FedX and our dynamic join approach. Intermediate results for the rst step, namely the results of the rst subquery, show the selectivity of the rst subquery. In the table, the number outside the bracket shows the real intermediate result size that the subquery should return, whereas the number inside the bracket shows the actual intermediate size returned within the 10,000-result limitation of the server.
The real intermediate result sizes of Q1, Q2, Q3, Q4, Q6, Q7, and Q8 of FedX were far larger than those of the dynamic join optimization; therefore, FedX was much slower for queries Q1, Q2, Q6, and Q8. For Q7, because of the restrictions on the returned size, the returned intermediate results size was 10,000 (though it should be 80,460), which was less than that of the dynamic join; therefore, the query seemed faster; however, Fedx returned incomplete results, while our dynamic approach returned all results. For Q3, Fedx failed in the second step because this step returned zero results, while our dynamic join approach successfully nished the query in the third step. For Q5, FedX and our dynamic approach produced the same number of intermediate results and the same join plan. In this case, the dynamic approach needed an additional join order optimization cost and was therefore a little slower. We did not measure the details of the intermediate results for SPLENDID. 1 A SPARQL compiler error occurs when FedX joins a certain intermediate result with another subquery. The dynamic join avoids this problem because the number of intermediate results is much less than that of FedX. 0.1
FedX SPLENDID DynaJoin r e s u l tz e r o r e s u l tz e r o time out time out r e s u l tz e r o time rout e s u lti n c o m p l e t e
We investigated why Fedx returned no results for Q2. Figure 4(a) and 4(b) illustrate the produced join plan of Q2. In the gures, the number inside the bracket shows the intermediate result after executing the operation. The rst evaluation produced by FedX was the exclusive group. With the limitation of the OMIM server, the evaluation returned 10,000 intermediate results that contributed no nal results; here the actually produced intermediate result size was 95,443. The dynamic join approach sends COUNT queries; thus, determining the fourth triple pattern has the highest selectivity, thereby returning only one result. It then binds the results of variable ?o2 to the other triple patterns, constructs the COUNT queries, and sends them to the relevant endpoints. In this case, the dynamic approach judged the third triple pattern to have fewer results and nally joined the exclusive group. The reason why Q3 and Q6 returned no results is similar to that of Q2.
For Q7 and Q8, it was more di cult to make a join order plan. There is a single triple pattern with two bound variables, which seemingly has higher selectivity. For Q7, FedX rst produced a larger initial search space of 80,406, which partially contributed to the nal results and therefore returned only part of the results. The dynamic join rst evaluated the group (i.e., 4323 results from the fourth and sixth triple patterns), with the search space size being far less than that of Fedx. Consequently, FedX returned only part of the results, whereas the dynamic join returned all results. (?gene rdf:type omim:Gene) (0) ⋈
For Q8, 111,962 results were returned-the largest size in this group of queries. The query was evaluated across three endpoints, as shown in Figure 5. Both FedX and our dynamic join rst evaluated the exclusive group (i.e., the rst three triple patterns) at the Drugbank endpoint. Next, FedX evaluated the second exclusive group (i.e., the fourth and fth triple patterns); how(6e⋈03v62e)r, the dynamic join approach judged the second exclusive group to h a(3v6) e more results∑than the third exclusive group (i.e., the seventh and eighth triple p∑atterns).(s?idderur:gs idae‐elfufect sider:pubchem‐flat‐ Ev a(?tdirung g the trhesirudltse,xtchluesrievbeygarcocueplereaatrilniegr tshuebqstuaenrtyi.ally(ad?nrsrut1sgd)ebraudngkb:uaAnnktc:iccaoetnevdguolrsy t(?a?afhsffe1fec dtecertueddg‐ob)sragniaknz:isem (?a?afosffe1fec fdtcertueddgt‐ob)rhagn?aksnei:disem)i ntercmompeoudndi‐ida?tcped) (a) FedX and SPLENDID for Q8(the first two steps) (36) ∑ (?s2 kegg:x‐ ∑(?s2 kegg:pathway
pubchem.comp ?pathway) (?s1Fdruogbrank:Qcate5go,ry F(?se1 ddruXgbanka:n(d?s1 dorugubarnk: douynd n?cpad)mic approach produced the same join plan. The dyadnrnutsg)baanmk:Anitciconavuplsp?aafrffefecotcetaedd‐o)crghanismn ?aeafffefeectcdetedd‐eo)rdganisam n additional join order optimization cost; therefore, FedX was sligh(bt)l DyynafJoainsfotr eQ8r(t.heT firsat tbwol setep4s) shows the additional overhead and their corresponding percentages accounting for the total query time in detail. The largest overhead here was 3.74 seconds for Q5. Consequently, the size increased and the query became heavier, thereby causing the optimization cost to no longer seem insigni cant.
In addition, our evaluation shows that SPLENDID cannot produce a better join plan than our dynamic approach despite using pre-computed statistical information. More speci cally, we checked the join plan produced by SPLENDID. For Q7 and Q8, SPLENDID produced the same join order as FedX, which generated far larger intermediate results than our dynamic approach. For other queries, SPLENDID produced the same join order plan as our dynamic join approach. The additional cost of the dynamic approach for Q1 resulted from the two COUNT queries, while SPLENDID used pre-computed information to evaluate the selectivity of the two triple patterns.
We also checked the di erence when using an index cache; however, we do not provide details here because the cache was not used in the dynamic join order procedure. Here source selection was implemented in the same way as that in case of FedX, which does not impact performance; therefore, the aforementioned conclusions still hold. As mentioned in the above section, the FedBench benchmark cannot measure the performance of join optimization in the federated query well because of its simplicity in producing a join plan; however, in this section, we still provide evaluation results with the Fedbench benchmark as a reference.
Our experiments were conducted on the AWS platform, with ve m3.2xlarge instances for the Cross Domain dataset and four instances for life science data. These instances were con gured with Intel(R) Xeon(R) CPU E5-2670 v2 2.50 GHz 4 Core CPU with 30 GB RAM and high network performance property (AWS standards) with a 64-bit GNU/Linux operating system and the 64-bit Java VM 1.7.0 75. All datasets were stored with an 8 GiB general purpose SSD EBS, except for the Geonames dataset, which used a 100 GiB one. Endpoints used open-source Virtuoso 07.00.3203.
Table 5 summarizes the FedBench dataset, while Table 6 presents query characteristics. #Tp., #Src, and #Res represent the number of triple patterns, data sources, and results, respectively. Figure 6 presents our experimental results.
Except for query LS6, FedX was slightly faster than our approach, with a maximum di erence of less than 0.5 seconds. Our proposed dynamic join eventually generated the same join plan as FedX. Therefore, the cost di erence mainly came from the additional optimization cost of our proposed dynamic optimization algorithm. Overall, the additional cost is not substantial. Further, as the queries in the life science eld become heavier than queries in the cross domain, the additional cost will decrease.
CD1 shows an extreme case in which only two triple patterns were joined. In this query, Fedx simply identi ed the triple pattern with higher selectivity. Our dynamic join approach seemed to experience a large cost (0.5 seconds) for optimization; however, the evaluation of Q1 in our designed benchmark, which also joined two triple patterns, showed our dynamic join approach to be much faster than FedX. In such cases, they applied di erent join order plans. LS6 illustrated a special case in which our dynamic join outperformed FedX. The results of this query are di erent from what was described in the FedX paper; the FedX team has con rmed these results with our current dataset and settings. We are jointly investigating the reasons why these inconsistencies exist. 0.01 dynamic approach engine can stably present an optimal join plan and therefore improve the performance of a federated query, with the degree of improvement becoming clearer as the query becomes more complex. Our dynamic approach does introduce additional overhead with its multiple updates of the join plan, with the overhead being signi cant in queries that return a small number of results and therefore have join orders that are not complex; however, as queries become more complex and result sizes increase, the optimization cost becomes increasingly insigni cant.
Note that the overhead of the COUNT queries could be further controlled by parallelizing the COUNT queries and setting timeout limitations. For the rst returned COUNT query, we could assume that it has less of a join cost because the amount of data, the scale of server computational ability, or the degree of network cost is better than others. We plan to implement this in the future to gain a better understanding here. In addition, although we implemented selectivity estimation via COUNT queries in this paper, other approaches are available. With ne-grained metadata, selectivity estimation could be estimated with less cost, although previous results provide concrete instances.
This work was supported by the National Bioscience Database Center (NBDC) of the Japan Science and Technology Agency (JST). We also thank the continued support from the FedX team for evaluating FedBench.