Merging and Partition for SPARQL Query Optimization

Abstract

Characteristic sets (CS) are used for storage and indexing, as the same CS tends to have a similar schema. While many methods based on CSs can improve query performance, especially for star queries, query performance will be seriously afected when the workload is complicated and produces many CSs. In this paper, we present CoPMP, merging CSs based on the correlations between predicates within the CSs and partitioning predicates. Our method captures the predicate correlation and merges CSs to reduce the number of CSs. The merging operation is driven by the cost model considering the predicate correlation and null values. In merging CSs, each predicate belongs to only a property set, i.e., predicate partitioning. Thus, CoPMP has the advantages of both property table and vertical partitioning for query optimization. We allocate merged tables into data blocks based on subject hash partitioning, considering that CS is from the same subject. Our extensive evaluation demonstrates the eficiency and scalability of our system.

Keywords

• Optimization

1. Introduction

Traditional RDF data storage schemes include triples store, vertical partitioning, and property table. But these methods are not eficient enough when workloads are complicated. Recently works show that Characteristic sets (CS) [ 1 ] can capture the implicit schema of RDF data and improve optimization. The CS for a subject is the set of predicates on the outgoing edges from that subject. For the complicated datasets, Papastefanatos et al. [ 4 ] point out that merging CSs based on the hierarchical structure reduces the number of CSs. But it only works in subset inclusion relations between property sets. In this paper, we introduce CoPMP, a distributed query engine based on Spark, which combines predicate correlation with partitioning and allocates tables to data partitions by subject. [ 7 ] also considers predicate partition. But it is not the same as the focus of this paper. Firstly, [ 7 ] artificially sets a co-occurrence threshold and uses a similarity coeficient similar to Jaccard to represent the degree of co-occurrence between two predicates. Only when co-occurrence is greater than the threshold are two predicates considered co-occurrence. In this paper, Two predicates are considered related as long as they have the same subject. Secondly, When dividing predicates, [ 7 ] stores all predicates that cooccur with predicates, that is predicates with a degree of co-occurrence greater than a threshold, into a set. However, based on CSs, this paper selects the CS with the greatest benefit as the basic data table and tries to add all the predicates with the same subject as the predicates in the selected CS. If the benefit of the table increases, then add the predicate. Finally, To obtain a better predicate partitioning pattern, [ 7 ] enumerates diferent co-occurrence thresholds. In this paper, CSs are merged based on the heuristic cost function to obtain the optimal relation pattern, which is the same idea as [ 4 ], but the method is diferent.

Figure 1 illustrates an overview of CoPMP architecture. Our contributions are as follows: - We propose a new heuristic algorithm for merging CSs, which considers the correlation of predicates and null values of the merged table. - We ensure predicate partition in merging CSs, allowing CoPMP to benefit from vertical partitioning and property tables without additional storage structures. - Extensive experiments on synthetic and real-world RDF graphs have been conducted to verify the eficiency and scalability of our method.

RDF Data

SPARQL

Storage Builder

Query Planner

Characteristic sets

Extractor

Heuristic Merging Table Generator

HDFS

Query Parse

Query Decompose

Join Optimizer

2. CoPMP

Algorithm 1: CSsMerge Output: schemaSet for each schema ∈CSs do

pts.add(schema); end while !pts.isEmpty() do Consider two extremes, (i) a CS corresponds to a property table, and (ii) all CSs are merged into a property table.

One leads to many tables and joins, and the other to excessive NULLs.

Thus, we need to find a Pareto equilibrium between fewer tables and null values when we merge CSs based on predicate correlation. Input: Characteristic Sets CSs, , , a property table set ← ∅ ; compute the cost of the schema; schema remove predicate p, if p is marked; select a schema with the lowest cost

; select a predicate pmax with max Predicate Frequency; pts.remove(schema); for each predicate p and PC(p, pmax) = true do if end let schemaTmp = schema.add(p); compute the

of schemaTmp; <

then schema = shemaTmp; mark predicate p;

= ; end schemaSet.add(schema); end return schemaSet; However, enumerating the combination of all related predicates is computationally hard. For this reason, we rely on a heuristic algorithm for approximating the problem. We introduce a function to find the current minimum cost in the merging process. Predicate frequency ( the number of sets(CSs) in which appear. Predicate co-occurrence ( , ) is the number of diferent sets in which predicate , that appear together. We design a cost model to measure the data table . The column field of the table is the set of predicates. And is predicate ) is with max , and

are functions measuring the null values and correlation. cost( ) = ( ) ( ) =

∑ ( ) + ( max) −

( , max) ∑ ∑

( , ) min( ( ), ( )) / 2 (1) The main idea behind the heuristic merging in algorithm 1 is to iterate over the predicates co-occurring with the

in the lowest cost CS. If adding these predicates comes with a smaller cost, merge them, and update the cost and property set. We choose instead of enumerating all predicates because predicate combinations are too large.

Query Planner Query Planner generates an optimal query plan for a given SPARQL query to be further executed. Query Decompose module decomposes the query into star subqueries. Moreover, we can search candidate triples by indexing the constant predicate based on predicate partitioning. Finally, we join the subqueries to get the result of the query.

3. Evaluation

We implement the experiment on a cluster with five machines. Each machine is equipped with 24G RAM, 2TB disk, and a 6 core Intel Xeon E5-2420 processor. The cluster runs Cloudera 5.13.3 with Spark 2.4.4 on Ubuntu 16.04 LTS. We compare CoPMP with S2RDF [ 2 ] and Sempala [ 3 ]. S2RDF uses ExtVP, which is based on vertical partitioning, and Sempala is based on the property table. We choose S2RDF and Sempala as the comparison system to show that CoPMP has the advantages of property table and vertical partition at the same time. The tests were run using the synthetic dataset WatDiv [ 5 ] and real-world dataset DBpedia [ 6 ]. For the Watdiv benchmark, we generate datasets with Watdiv100M, Watdiv300M, and Watdiv500M to test the system’s scalability and employ four types of queries snowflake(S), linear(L), star(S), and complex(C). Due to DBpedia’s absence of query templates, we designed four queries that combine query types. Figure 2 ∼ 4 show the average query time obtained on the Watdiv and Figure 1 shows the response time on the DBpedia. The results show that CoPMP proved more eficient than Sempala and S2RDF. Sempala needs to scan a big table each time since it stores triples with a unified property table, which results in a slow response. S2RDF precompute semi-join tables to reduce data shufling. However, if the query does not appear in a semi-join table, the query can be expensive with VP tables. CoPMP merges CSs based on predicate correlation and predicate partitioning. Based on predicate partitioning, CoPMP can quickly find candidate triples since each predicate exists in only one table, similar to S2RDF. Also, CoPMP decomposes the query into star subqueries, thereby reducing joins with the benefits of property tables, but without scanning a single table containing all the data like Sempala. The results show that CoPMP benefits vertical partitioning and property tables.

S2RDF Sempala CoPMP

S2RDF Sempala CoPMP 1.E+05 C

F

L

S

4. Conclusion and Future Work

In this paper, we present a distributed query engine CoPMP that merges characteristic sets based on predicate correlation and predicate partitioning. Moreover, we allocate the merged table to the data partition based on the subject hash partition, which is the advantage of the CS with the same subject in distributed storage. Also, our extensive experimental results show the efectiveness of the CoPMP. In the future, we are planning to continue to extend the work to Well-designed SPARQL and conduct a comprehensive experiment to validate the eficiency of CoPMP.

References

[1] Neumann , T. , Moerkotte , G.: Characteristic sets: Accurate cardinality estimation for RDF queries with multiple joins . In: ICDE . pp. 984 - 994 ( 2011 )

[2] Schätzle , A. , Przyjaciel-Zablocki , M. , Skilevic , S. , Lausen , G.: S2RDF: RDF querying with SPARQL on spark . In: VLDB . pp. 804 - 815 ( 2016 )

[3] Schätzle , A. , Przyjaciel-Zablocki , M. , Neu , A. , Lausen , G.: Sempala: Interactive sparql query processing on hadoop . In: ISWC . pp. 164 - 179 ( 2014 )

[4] Papastefanatos , G. , Meimaris , M. , Vassiliadis , P. : Relational schema optimization for RDFbased knowledge graphs . In: Information Systems . pp. 735 - 754 ( 2022 )

[5] Aluç , G. , Hartig , O. , Özsu , M.T. , Daudjee , K. : Diversified stress testing of RDF data management systems . In: ISWC . pp. 197 - 212 ( 2014 )

[6] Jens , L. , Robert , I. , Max , J. , Anja , J. , Dimitris , K. , Pablo , M. , Sebastian , H. , Mohamed , M. , Patrick , V. , Sören , A. , Christian , B. : DBpedia - A Large-scale, Multilingual Knowledge Base Extracted from Wikipedia . In: Semantic Web . pp. 167 - 195 ( 2015 )

[7] Guangxi , J. : Optimizing Well-designed SPARQL Query Based on Constrained Pattern Tree[Master Thesis] , Tianjin University, 2022 .