We present a join optimization method for federated linked geospatial data. This optimization targets within-distancequeries in cases where the shapes that are compared are served from diferent sources of the federation. This operation is computationally expensive, because it cannot be answered from the spatial index of any of the individual data sources in the federation. Our optimization augments the subqueries prepared for each source with additional restrictions on topological relations that must be satisfied and that (a) can be answered from the spatial index of the individual data sources; (b) do not change the semantics of the query. We evaluate our optimization on data and queries derived from a real-world workflow over land usage data. Evaluation shows that our optimization substantially improves query processing time. Federated and distributed query processing, linked geospatial data, GeoSPARQL query processing GeoLD 2022: 5th International Workshop on Geospatial Linked Data co-located with ESWC, May 30 2022, Hersonissos, (N. Prokopaki-Kostopoulou)
Linked geospatial data brings into the scope of the Semantic Web and its technologies a wealth of datasets that combine semantically-rich descriptions of resources with these resources’ geo-location. There are, however, various Semantic Web technologies where technical work is needed in order to achieve the full integration of geospatial data, and federated query processing is one of these technologies.
Indexing and query optimizationare key features of all database management systems, both geospatial and relational. For instance, consider the query that r“eatlrliervesetsaurants within 1km from Syntagma Square, Athens, Greece.”A centralized geospatial database relies on its geospatial index to exclude instances that cannot possibly be within 1km from Syntagma Square, so that the distance only needs to be computed for a small number of candidates. A query optimizer is aware that it is much more eficient to first retrieve the location of Syntagma Square Greece and then filter for restaurants, than it would be to first retrieve the location of all restaurants in the world. So query optimization ensures that query execution is organized optimally and not following the ordering of the sub-queries in the original query.
Although both indexing and query optimization are based on mature technologies, it is not always straightforward to port these technologies to linked geospatial data and, even more so, to federated query processing of linked geospatial data. Suppose that we are federating a database that knows points of interest such as “Syntagma Square” with a database that knows commercial points of interest, including restaurants. There is no single geospatial index that can restrict the restaurants sub-query to the instances can potentially be solutions.
In the remainder of this paper, we present some background information (Se2c)t, iaonnd we describe our optimization for federated within-distance queries in detail (3S)e.cWtieonimplement this technique inSemagrowand we compare the optimized version with the unoptimized one (Section4). Finally, we discuss relevant work (Sect5io)nand conclude (Section6).
The GeoSPARQL specification [
Naturally, inference abogueto:wktLiteral values falls outside RDF graph entailment and can only be performed by specialized geospatial databases. Such entailment is accessed via iflter expressions that contain geospatial functions. For example: SELECT ?r1 ?r2 WHERE { ?r1 geo:hasGeometry ?g1 . ?r2 geo:hasGeometry ?g2 . ?g1 geo:asWKT ?w1 . ?g2 geo:asWKT ?w2 . FILTER(geof:sfIntersects(?w1,?w2)) } uses thegeof:sfIntersects function3 to access the geospatial operator that computes if the WKT values?w1 and ?w2 retrieved from the graph pattern intersect; such a query fetches all features that have intersecting geometries. Notice that a geospatial join is essentially a cross product that is being filtered by a geospatial condition comparing values from both expressions.
Bind join [
2Two alternative serializations are foreseGeneobSyPARQL, geo:wktLiteral and geo:gmlLiteral, and two datatype propertiegse,o:hasWKT and geo:hasGML. We restrict the discussion in this paper to the WTK serialization, and it is straightforward to transfer this discussion to GML or any other serialization.
3We use geof: forhttp://www.opengis.net/def/function/geosparql/ The idea, similar to thneested loop joi,nis that if we have a very selective outer relation of a join, we can pass the results as bindings to the inner relation in order to filter out a large number of tuples. The diference is that bind join can also work for remote queries since it substitutes the results of the outer relation as bindings to the query of the inner relation.
A naive implementation of bind join3,[
Filter pushdown[
Let and be two spatial objects, that can be points, lines and/or polygonal areas. We say that and intersectif they share any portion of space. Moreover, we say thactontains if no points of lie in the exterior o,fand at least one point of the interi orlioefs in the interior of . Let be a length measurement. Then, thbeufer of size around is a spatial object that contains all points whose distances fr oamre less or equal t.oFinally, theminimum bounding box of is a rectangle whose sides are parallel t o tahned axises and minimally enclose; it is formed by the minimum and maximum p, q coordinates of.
Let us now focus onGeoSPARQL queries. Avariable bindingis a pair { , where is a variable and is an RDF value. Each element of the result setGoefoaSPARQL query is aquery binding, which is a set of variable bindings. L etbe a query binding. We say tha tis a bound variable w.r. t.if contains a variable bindi ng{ . In this case, we writep q to denote the RDF value . Moreover, we say th atis a freevariable w.r. t.if is not bound w.r.t .. Finally, let be a set of query bindings an dbe a variable. We say tha tis a free (resp. bound) variable w.r.t. if it is a free (resp. bound) w.r.t. to all query bin di∈ngs. For the rest of the paper, when we will refer to a binding we will mean a query binding.
A federated within-distance querisya query that involves fetching pairs of shapes that are served from diferent federated sources and their distance is less or equal than a given length measurement. Since theGeoSPARQL specification does not ofer any specialized function for the within-distance operator (contrary to e.g., PostGIS) such queries contain filters of the form: FILTER( geof:distance(?x, ?y, uom) < d ) . whereuom is a unit of measure URdI, is a numeric literal, and the bindings?oxfand ?y are retrieved from diferent sources of the federation.
We design our optimization technique under the general assumption that the federation engine evaluates all federated joins in a bind join fashion with a filter pushdown optimization (cf. Subsection2.2 for details). In this case, the federator operates by fetching “left-hand” WKTs to partially bind two-variable functions and then it pushes the filter to the “right-hand” endpoint. Notice that the filter pushed in “right-hand” endpoint contains a single free variable, because the other variable is bound with WKTs that have been already retrieved.
Recall that in the naive implementation of bind join, for each binding of the left part of the join, the federator issues one query to the endpoint of the right part of the join. Assume, without loss of generality, that the binding?sxoafre retrieved from the left part of the join. Thus, a query issued by the federator to the right-hand endpoint should contain a filter of the form: FILTER( geof:distance(WKT_LITERAL, ?y, uom) < d ) . whereWKT_LITERAL is obtained by the bindings of the left part of the join. Such queries are usually slow, because the evaluation of this filter cannot use the spatial index of the source.
The evaluation of the source query in the remote endpoint can be sped-up if the federator adds an additional geospatial filter for filtering out all irrelevant candidate sh?ayp: es for FILTER( geof:sfIntersects(?y, BBOX_BUF_LITERAL) ) . where BBOX_BUF_LITERAL is the minimum bounding box of the bufer of size around WKT_LITERAL. This additional filter is evaluated by the geospatial source using its spatial index, thus giving fast access to a subset of shapes, in which the exact distance filter is then applied to. Notice that this optimization can be performed during query execution time (and not before evaluating the query), becauseWtKTh_eLITERAL is not known at the planning time.
In the following, we will extend this approach so as to apply in more elaborate implementations of bind join, where multiple bindings can be passed in a single query.
We assume the existence of some helper routines that their implementations are not included here as separate algorithms. Given a WKT lit e,raanlumeric liter aland a unit of measur e, the routinBeufferp, , q returns a WKT literal that represents the bufer o fasrizoeund measured in units of typ e. Given a WKT liter al, the routinMebbp q returns a WKT literal that represents the minimum bounding box o.fGiven an endpoint , a query and a set of bindings , the routineEvaluateRemoteQueryp, , q implements the behavior of the query executor (cf. Subsectio2n.2) and returns a set of bindings obtained from the source. Our Algorithm 1 EvaluateRemoteQueryOpt Input: a GeoSPARQL endpoint , a GeoSPARQL query , and a set of bindings .
Output: a set of bindings 1: if contains a filter of the forFmILTER( geof:distance(?w1,?w2, ) < ) where is a unit of measure URI, is a numeric literal, one of?w1, ?w2 is a free variable w.r.t(denoted as ), and one of?w1, ?w2 is a bound variable w.r .t(denoted as ) then 2: ≔ a fresh variable 3: Obtain ′ by augmenting with the filterFILTER( geof:sfIntersects( , ) ) 4: ′ ≔ t ∪ t {MbbpBufferp p q, , qqu ∶ ∈ u 5: ′ ≔ EvaluateRemoteQueryp, ′, ′q , ≔ t ´ t { u ∶ ∈ ′u 6: return 7: else 8: return EvaluateRemoteQueryp, , q 9: end if goal is to extenEdvaluateRemoteQuery with the optimization sketched in Subsecti3o.2n, adapted for the eficient bind join implementation that groups multiple query bindings from the left-hand endpoint in a single query for the right-hand endpoint. Thus, in Algor1i,twhme define EvaluateRemoteQueryOpt, which behaves as a wrapper for the original executor.
The first step (line 1) is to identify whether the input query is in the form of our interest. We considerwithin-distancejoins (i.e., a filter of the formgeof:distance(?w1,?w2, ) < ), and the join is afederatedone (i.e., only one of the argumen?tws1, ?w2 is bound from the bindings that came from the left part of the join). When the optimization is not applicable, EvaluateRemoteQueryOpt falls back to the originEavlaluateRemoteQuery behavior.
The next step (lines 2-4) is to rewrite the query. After we identify that the free variable is the variabl e and the bound variable is the varia b(lleine 1), we add an additional filter that forces to intersect with the minimum bounding box of the bufer of s izaeround (line 3). Notice though that unlike Subsect3io.2n, we have several bindings for the varia b,ltehus we cannot hard-code the bounding box directly in the query. Instead, the additional filter is geof:sfIntersects( , ), and we provide additional bindings for the new fresh varia(blilnee 2) by extending each binding from with the binding { , where is obtained by calculating the minimum bounding box of the bufer of size around the value th aatssigns in (line 4).
The final step (line 5) is to use the originaElvaluateRemoteQuery with the rewritten query and the extended bindings to obtain the result set of the query. Since the original query did not contain the newly constructed vari a,bwle need to remove through a post-processing all variable bindings that refe r tforom the result set.
Lemma 1. Let, be WKT literals and be a length measurement. If the distance betweeannd is less than , then intersects with the minimum bounding box of the bufer of sizearound . Proof.Let. be geometric literals, such that the distance bet waenend is less than . Then, by definition, intersects with the bufer of si zearound . Since all points of a sha pebelong also to the minimum bounding box o f,we can conclude tha talso intersects with the minimum bounding box of the bufer of siz e around .
Following Pérez et a[l8.] we denote byv⋅w theevaluationof a SPARQL query over a dataset . If a query is a SELECT query, thenv w is a set of bindings, which are the solutions that satisfy over . Moreover, given a query and a query binding , we write to denote the query obtained by substituting each bound variaoblfe in with p q. We assume set semantics of GeoSPARQL.
Lemma 2. Let be a binding, be a free variable w.r.t,. be a bound variable w.r.t,. be a unit of measure URI, and be a numeric literal. We define 1 “ (geof:distance(, , ) < ), 2 “ geof:sfIntersects( , ), where “ MbbpBufferp p q, , q. Let 1, 2 be twoGeoSPARQL queries, s.t. 2 contains 1 and 1 is obtained by augmentin g 2 with 2. Then, v 1 w “ v 2 w . Proof.Suppose that the lemma does not hold. Si nc1eis essentially 2 augmented with an additional filter, it must bve 1 w ⊆ v 2 w , i.e., there must exist some binding˚ such that ˚ ∉ v 1 w and ˚ ∈ v 2 w . According to the meaning o f1, 2, this means that (a) the distance between˚p q and p q is less tha n and (b) ˚p q does not intersect with the minimum bounding box of a bufer of size around p q. Contradiction (Lemma1).
Theorem 1. Let be a GeoSPARQLendpoint, be a GeoSPARQLquery, and be a set of bindings. Then, EvaluateRemoteQueryOptp, , q “ EvaluateRemoteQueryp, , q.
Proof.If is not of the form of the query in Line 1 of Algori1t,htmhen the equation holds (cf. Line 8). Otherwise, notice that it hoℰldsp, , ∅ q “ ℰp, , ∅ q for all ∈ (Lemma 2) (for brevity, we writℰe and ℰ instead ofEvaluateRemoteQueryOpt and EvaluateRemoteQuery), respectively). Therefore, notice that for∈a ll it holds ℰ p, , t uq “ ℰ p, , ∅ q “ ℰp, , ∅ q “ ℰp, , t uq, and thusℰ p, , q “ ⋃∈ ℰ p, , t uq “ ⋃∈ ℰp, , t uq “ ℰp, , q.
We provide an implementation of our geospatial join optimization integratedSeinmtahgerow SPARQL federation engin4e.Our implementation extends the existing query execution mechanism with a GeoSPARQL query executor that uses this optimization.
We evaluate our technique using datasets and queries from the GeoFedBench bench9m],ark [ which was derived from practical use cases in the agro-environmental domain; that is, linking land usage data with ground observations for the purpose of estimating crop type accuracy.
4Cf. https://github.com/semagrow/semagrow Datasets For the experimental evaluation, we use the following publicly available data sources: 1. The Austrian Land Parcel Identification System (INVEKO5,Sw)hich contains the geolocations of all crop parcels in Austria and the owners’ self-declaration about the crops grown in each parcel. 2. The EUROSTAT’s Land Use and Cover Area frame Survey (LUC A6,Sw)hich contains agro-environmental and soil data by field observation of geographically referenced points. Table1 gives more details about these datasets. Each dataset is loaded on a diferent SPARQL endpoint; we use the Strabon geospatial RDF st1o0r]ef[or serving the data. Strabon encapsulates PostGIS for performing spatial operations, and uses a spatial index to optimize query time. Federations We use two federations of the above datasets; one Semagrow federation in which the execution engine uses technique discussed in Secti3on(semagrow-opt) and one that does not use its(emagrow-std). Regarding the evaluation of federated geospatial joins, each Semagrow federation uses a bind join evaluation strategy with a filter push-down optimization. Queries In Table2 we summarize the queries of the experiment. Each row of the table corresponds with a query template with a specific parameter. Q1-3 are used to estimate the croptype reliability of the INVEKOS dataset. For each LUCAS instance URI, we check if it provides a positive validation (Q1), a negative validation (Q2), or it is irrelevant for the analysis (Q3). In order to get more information about the instances, each query either returns a single result (if the LUCAS URI has the desired property) or an empty result set (otherwise). These queries have several characteristics apart from federated within-distance geospatial 9jo]ifnosr(caf. [ discussion on the complexity of the query set). In order to focus on the behavior of the withindistance geospatial join, we have also included Q4. This query returns all INVEKOS instances that are within a given distance from a specific LUCAS instance. The query is parameterized with various distances ranging fro10mmeters to100 kilometers. As for the LUCAS instance, we used the one that is closest to the center of the minimum bounding box of Austria. Experiment deployment and execution We use a Kubernetes 1.14 cluster with 1 master node and 8 worker nodes with a total of 120 cores and 264GB RAM. All queries are executed three times; the execution times reported are the average of the second and third run. Experiment deployment and execution is done through the KOBE benchmarking engi1n1e],[and the KOBE configurations for reproducing the experiments are publicly avail7able.
5cf.http://www.data.gv.at/katalog/dataset/f7691988-e57c-4ee9-bbd0-e361d3811641 6cf.https://esdac.jrc.ec.europa.eu/projects/lucas 7The experiment specifications can be found inhttps://github.com/semagrow/benchmark-geofedben.ch
In the first part of the experimental study, we compare the optimiszeemda(grow-opt) version ofSemagrowover the unoptimized onese(magrow-std) using the query load obtained by the data validation task. Ta3blceontains the experimental results. For every query template, we illustrate: the number of queries for each template (#queries), the number of queries that return result (#results), and the query processing time. For each federation, we display the total time to evaluate the query load and the average time for each query of the query load.
We notice that the queries are much faster if we use the optimized verSsieomnaogfrow. The unoptimized version would require several days for the evaluation, while with our optimization technique the task reduces to several hours.
Even though the query set contains several complex characteristics, the bottleneck for the query evaluation is the calculation of the within-distance operation. This can be verified if we analyze the execution plan of each query. For Q1 andSQem2,agrowretrieves the WKT of the given point from LUCAS (which is a fast operation since it requires fetching information from a single instance), and then it retrieves all parcels that are within 10 meters from this WKT (together with their distance and crop type) from INVEKOS. TSheemna, growsorts the INVEKOS parcels according to their distance and takes the first one. Since the distance is only 10 meters, the parcels are very small in number, therefore the sorting operation is very fast as well. Then,Semagrowretrieves the point crop type from LUCAS and compares it with the crop type of the parcels. Again, this operation is fast because it requires retrieving information from a single instance. Similarly, for QS3e,magrowretrieves the crop type and WKT of the given point from LUCAS (a fast retrieval of information from a single instance), and checks if there is any point within 10 meters from this WKT from INVEKOS.
The previous discussion suggests that the operation “retrieve all WKTs from INVEKOS within 10m distance from a specific WKT (obtained from LUCAS)” is the costliest operation in the data validation task. As a result, it is safe to conclude that our optimization technique which targets such queries is the reason for the extreme speed-up of the INVEKOS validation task.
In the second part of the experimental study, we compare the optimsiezmedag(row-opt) over the unoptimized s(emagrow-std) version of Semagrow using a query of fetching all INVEKOS parcels that are found within increasing distances from a specific LUCAS point. T4acbolnetains the experimental results. For every instance of the query template Q4, we illustrate: the distance parameter of the within-distance operation, the query processing time and the number of results forsemagrow-std and semagrow-opt. Moreover, we display the number and percentage of shapes that are pruned from INVEKOS by the additional filter that the optimization process places in the source query that corresponds to the right part of the federated join.
First, we notice that in both casSeesm,agrow returns the same number of results. This validates that the implementation of the optimization is correct, i.e., the bounding box in the additional filter is constructed correctly, thus the filter does not prune any correct shapes.
Regardingsemagrow-std, which issues the unoptimized query in INVEKOS, we notice that every query requires at least 57 seconds. For a parameterized distance between 10 meters and 10 kilometers, the query time is 57 – 58 seconds, even if the result is either very small (2 results) or moderate (4,700 results). Only for distances greater than 50 kilometers, where we have a very large result set (greater than 140,000 results), the query time seems to increase as we increase the distance parameter. This behavior can be explained if we consider that the unoptimized query cannot be answered using the spatial index of the source, and the source has to check for every shape in INVEKOS if it is within a specific distance. Thus, the experimental results can be explained as follows; the time needed to check potential candidates within a given distance is around 1 minute, and the remaining time is used for passing the results back to the clients. Notice that in our case, the transfer cost can be relatively high (e.g., 50 seconds for 500,000 results), because the result set includes WKT values which are in general long strings.
Regardingsemagrow-opt, which issues the optimized query in INVEKOS, we notice that the query processing time is analogous to the size of the distance parameter, i.e., for smaller distances we have a faster query processing time. Recall that the optimized source query has an additional filter expression, which is used to prune all shapes that are too far away from the given LUCAS WKT. Indeed, we observe that there exists a connection between the amount of the pruning of the additional filter and the query processing time. Unlike previously, where the source had to consider all shapes from INVEKOS, the source here computes the distance for a reduced set of candidate shapes, which is relevant to the distance parameter. Moreover, since thegeof:sfIntersects function of the additional filter can be evaluated using the spatial index, this filter does not introduce any time overhead in the evaluation of the query.
Comparing the two approaches, we observe that the optimized version reduces the query processing time by 3 orders of magnitude for distances less than 1 km and by 2 orders of magnitude for distances around 10 km. For larger distances, the time diference is less pronounced, but in any case, we can safely conclude that the optimization technique can be efective for federated within-distance queries for any distance length.
The literature on federated geospatial query processing is very sparse, in either the Semantic Web community, the geographical information systems community, or the wider databases community. Recent studies1[2, Section 5] find that there is no mature federated GeoSPARQL query processing system. Recent work on data integration methods cites systems that collect and integrate distributed geospatial data into a single store as well dynamic federation of nongeospatial data sources, but also does not include systems that are both federated and support geospatial operation1s3[, Sect. 2].
PostGISalready has a build-in function calculating the geometries that are within a given
distance, calleSdT_DWithin [
Similarly, this is kind of how PostGIS proposes to handle the nearest neighbour s1e5a]r.ch [ Traditionally, the naive way to find the nearest neighbour is to force the database to calculate the distance between the query geometry and every candidate geometry and then sort them all. For a large table of candidate geometries, it is not an eficient approach. One way to improve performance is to add an index constraint to the search; first find which candidate geometries overlap or touch with an arbitrary box around the query geometry and only calculate the actual distance with them. The above introduces the problem of somehow choosing the smallest box, and that is whyPostGISintroduces KNN, a pure index based nearest neighbour searPcohs.tGIS uses an R-Tree index implemented on top of GiST (Generalized Search Tree) to index GIS data. The KNN system evaluates distances between bounding boxes insidePtohsetGISGiST index. So, in the case of within-distance queries the computations will be between the bounding boxes of geometries; they will not be precise on the exact geometries.
Another optimization can be performed by creating on-the-fly spatial indexing for spatial
objects [
We presented a geospatial join optimization method for federated within-distance queries. In this optimization, the query execution module of a federation engine can be extended, so that it rewrites the query to be issued to the geospatial source endpoint by adding an extra filter to the within-distance filter. This can help the federated source to calculate faster the result set since the additional filter can make use of the spatial index of the source, without changing the semantics of the original query. The implementation of our method is provided as open source, integrated with the Semagrow federated GeoSPARQL processor.
In the experimental setup, we showed that the optimization substantially speeds up query execution, especially for restrictive within-distance limits. This can prove useful for many real-world applications, as it is reasonable to expect that within-distance restrictions are used to limit results to a local scope. In other words, the value of the proposed method might be smaller for within-distance limits of thousands of kilometers, but it is hard to imagine use cases where such queries would be useful.
As future work, we plan to develop a GeoSPARQL extension where within-distance restrictions are expressed with a single function. This will allow the scope of application of our optimization to be made explicit, and not depend on statically analysing the query in order to identify queries where the optimization is applicable. Another direction for future work is to develop similar rewriting techniques for optimizing federated queries with other GeoSPARQL functions (such asgeof:sfCrosses orgeof:sfTouches). Finally, an interesting open question is whether (and to what extend) our approach can be efective for triple stores that do not provide a complete implementation of the GeoSPARQL standard.
Acknowledgements The work described here has received funding from the European Union’s Horizon 2020 research and innovation programme under grant agreement No 825258. For more details, please vishittp://earthanalytics..eTuhe authors also acknowledge that the work was supported by SKEL, NCSR ‘Demokritohs’ttps://www.iit.demokritos.gr/labs/sk. el/