Translating SPARQL to Spark SQL has been proposed to achieve better scalability in query evaluation. Recent investigations show that the database design for storing the RDF-graph plays a signi cant role in the performance, due to intrinsic characteristics of Spark's computation model. The analysis points to the interesting fact that a Wide Property Table (WPT), a single-table design with one row for each subject and one column for each property, has very nice properties for storing RDF-graphs. In addition to WPT's simplicity, SPARQL queries, in particular those with many joins on subjects, are translated to an e cient Spark execution plan. We aim to extend the WPT with inverse properties to broaden this bene t to other kinds of queries. Thus, in this paper we propose a framework which can leverage one or a combination of WPTs extensions. Our experiments on a widely used benchmark reveal that a combination of three di erent kinds of WPT together leads to the best performance for almost all query types but the linear-shaped ones.
Translation from SPARQL to Spark SQL is widely researched because it makes it
possible to bene t from the robustness and scalability of cloud computing
infrastructure. In Spark, a database design involves a collection of DataSets, which
are at the physical level divided into partitions (set of rows), and distributed
and replicated among cluster nodes. An example of such a design is the Wide
Property Table (WPT), a very sparse single-table design with one row for each
subject and as many columns as the number of distinct properties. Some notable
examples of systems on top of Spark are: S2RDF [
We propose a framework capable of using multiple WPT extensions from the same RDF-graph to evaluate SPARQL queries. We achieve this by generating an intermediate abstract tree of operation nodes to represent a given SPARQL query. The central criterion to build it is the minimization of the number of join operations. In this tree each node can independently use an available WPT design. The leaves contain a graph pattern (a single or conjunction of triple patterns), that can be evaluated without a Spark SQL join operation in a given database. Intermediate nodes represent join operations on the common variables of their children nodes. Thus, to minimize the number of join operations necessary for the query evaluation the algorithm takes all available designs given as input into account. Given that WPT works well for on-subject joins, we consider here also its object counterpart, the Inverse Wide Property Table (iWPT). An iWPT contains one distinct column for each property of the RDF-graph and each row contains the information about an object. Therefore, graph patterns with a common object resource can be processed with a single scan of the iWPT. These two tables, WPT and iWPT, can be joined to have in a single row all information connected one-hop away from a resource, regardless of the predicate direction. Therefore, we consider here two variations, one obtained through a full outer join (jWPT-outer) and an inner join (jWPT-inner) between the WPT and iWPT. The schema of the WPT, iWPT, and jWPT, given an RDF-graph with n distinct properties, is shown in Table 1.
WPT iWPT jWPT s p0 ... pn pn 1 ... p0 1 o pn 1 ... p0 1 r p0 ... pn
Table 1: Schema of a WPT, iWPT, and jWPT.
An example of how the abstract tree is generated on top of some of these
WPT extensions is provided in Figure 1. Input to our algorithm is the SPARQL
query (A) which results in the graph pattern illustrated in (B), and the set of
database designs where the operations can be executed. As the gure shows,
when only WPT is available (C) all on-subject patterns are grouped together,
while others are executed independently on the same table. When also the iWPT
is available, the same occurs with on-object joins, which are now grouped in one
leaf (D). Finally, the complete graph pattern is placed in a single leaf when the
jWPT is available (E).
We performed our tests on a small cluster of 10 machines, 1 master and 9
workers, connected via Gigabit Ethernet connection. Each machine is equipped with
32GB of memory, 4TB of disk space and with a 6 Core Intel Xeon E5-2420
processor. The cluster runs Cloudera CDH 5.10.0 with Spark 2.2 on Ubuntu 14.04.
Yarn, the resource manager, in total uses 198 GB and 108 virtual cores. The
tests were run with using a WatDiv dataset [
The graph (A) in Figure 2 shows the average time when considering the entire Watdiv benchmark query set. Since Watdiv is strongly biased towards queries which only contain on-subject joins, we show in the graph (B) the performance evaluation on a reduced Watdiv query set whose queries contain at least two joins, one on a subject and one on an object, and excluding completely linearshaped ones. This allows us to closely analyse the bene t of jWPT, which reduces the number of Spark SQL join operations the most. We can observe from the graphs that the combination of WPT and iWPT in C2 performs slightly worse than WPT only (C1), except for complex queries, but the di erence is not very signi cant. In the case of C3, jWPT-outer only, when considering the reduced query set, there is an improvement over C1 and C2 for all query shapes but the complex ones. Interestingly, the same does not occur when considering the full query set. This can be attributed to the higher number of rows present in the jWPT-outer. Finally, C4, the combination of WPT, iWPT and jWPT-inner, resulted in the best performance for all query shapes, but the linear-shaped ones, showing that further improvements can be made for the e cient evaluation of this speci c type of query.
Data model Size Tuples WPT 1.1GB 5.2M iWPT 1.2GB 9.7M jWPT-outer 2.3GB 10.2M jWPT-inner 1.8GB 4.7M Table 2: Tables statistics.
C1 C2 C3 C4 (A) full
C1 C2 C3 C4
(B) reduced Wat-C Wat-F Wat-L Wat-S at-C W at-F W at-S W
In this paper we show the bene t of extending WPTs with inverse properties.
Similar ideas can be found in a commercial system [