Highly Parallel SPARQL Engine for RDF

Fan Feng, Weikang Zhou, Ding Zhang, Jinhui PangCommunications 2020 · DOI · OpenAlex

Abstract

In this paper, a highly parallel batch processing engine is designed for SPARQL queries. Machine learning algorithms were applied to make time predictions of queries and reasonably group them, and further make reasonable estimates of the memory footprint of the queries to arrange the order of each group of queries. Finally, the query is processed in parallel by introducing pthreads. Based on the above three points, a spall time prediction algorithm was proposed, including data processing, to better deal with batch SPARQL queries, and the introduction of pthread can make our query processing faster. Since data processing was added to query time prediction, the method can be implemented in any set of data-queries. Experiments show that the engine can optimize time and maximize the use of memory when processing batch SPARQL queries.

Introduction

As Resource Description Framework (RDF) data explodes in volume, the need for efficient SPARQL querying has become critical. Most existing RDF engines, such as RDF3X or gStore, excel at serial execution but struggle to leverage modern multi-core hardware for batch processing.

The traditional approach to handling multiple queries simultaneously is Multi-Query Optimization (MQO), which attempts to find and share common sub-expressions between queries. However, MQO is an NP-hard problem; the computational overhead of finding the "perfect" optimized plan often outweighs the benefits. This research shifts the focus from complex algebraic rewriting to intelligent parallel scheduling.

Methodology

The proposed engine utilizes a three-stage pipeline to handle batches of SPARQL queries efficiently.

1. Time Prediction via Machine Learning

The system employs Support Vector Regression (SVR) to predict query execution time. Unlike models that rely solely on query structure, this approach extracts a multi-faceted feature set:

  • Algebraic Features: Captures the hierarchy and frequency of operators like UNION and OPTIONAL.
  • BGP Features: Basic Graph Patterns (BGPs) are mapped to structural graphs. The "distance" between a query and known templates is calculated using Graph Edit Distance (GED).
  • Data Features: Accounts for the "width" (class hierarchy) and "depth" (instance attributes) of the underlying RDF dataset, acknowledging that data shape significantly impacts performance.
Mapping Basic Graph Patterns (BGPs) to structural graphs for feature extraction.

2. Memory Estimation

To prevent system instability, the engine estimates the memory footprint of each query. It utilizes a cardinality estimation algorithm based on B-tree indexes (SPO, POS, and OSP patterns) to predict the size of intermediate result sets.

3. Pthread Allocation and Scheduling

The engine uses pthreads (POSIX threads) for parallel execution due to their low overhead and shared address space. Queries are grouped by their predicted execution time into $m$ groups (where $m$ is the number of threads) to ensure an even temporal load. Within each group, queries are sorted by memory usage to balance resource consumption.

Evaluation

The engine was evaluated using the DBpedia 3.9 dataset and real-world query logs from the USEWOD 2014 dataset. The test suite consisted of 10,000 queries.

On a system with 16 CPU cores and 32GB of RAM, the proposed engine demonstrated superior performance compared to traditional methods when processing a batch of 1,000 queries:

Method Execution Time (s)
No Optimization 67
Standard MQO 47
Optimized MQO (MQO-S) 42
Proposed Pthread Engine 38

The system achieved a nearly 43% speedup over unoptimized execution and outperformed traditional algebraic multi-query optimization.

Discussion and Conclusion

The core insight of this work is that for batch processing, a "good enough" parallel schedule is often superior to a "perfectly optimized" serial plan. By incorporating data-aware features into the prediction model, the engine accounts for the "shape" of the graph, which is often more critical than the query syntax itself. Furthermore, using pthreads reduces context-switching costs by roughly 30x compared to separate processes.

Future work will address the engine's reliance on specific B-tree indexing for memory estimation and explore dynamic scheduling for streaming query environments.

Summary updated

Abstract

Abstract In this paper, a highly parallel batch processing engine is designed for SPARQL queries. Machine learning algorithms were applied to make time predictions of queries and reasonably group them, and further make reasonable estimates of the memory footprint of the queries to arrange the order of each group of queries. Finally, the query is processed in parallel by introducing pthreads. Based on the above three points, a spall time prediction algorithm was proposed, including data processing, to better deal with batch SPARQL queries, and the introduction of pthread can make our query processing faster. Since data processing was added to query time prediction, the method can be implemented in any set of data-queries. Experiments show that the engine can optimize time and maximize the use of memory when processing batch SPARQL queries.
BibTeX
@inproceedings{feng2020highly,
  author = {Fan Feng and Weikang Zhou and Ding Zhang and Jinhui Pang},
  title = {{Highly Parallel SPARQL Engine for RDF}},
  booktitle = {Communications},
  year = {2020},
  doi = {10.1007/978-981-15-7981-3\_5},
}
Figure