TL;DR
This paper introduces SaGe, a novel preemptive SPARQL query engine designed for public Semantic Web endpoints. By allowing queries to be interrupted and resumed, SaGe significantly improves data availability and query throughput, addressing a key challenge in building robust Semantic Web applications.
What Problem Does This Paper Address?
The Semantic Web aims to be a global, interconnected data space where applications can query vast amounts of RDF data. However, accessing this data through public SPARQL endpoints presents significant challenges. These endpoints often face unpredictable loads from arbitrary queries, leading to performance issues and limited data availability. To protect themselves, many endpoints impose strict quotas on query execution time and result size, forcing developers to resort to downloading entire datasets locally, which is often impractical. Existing alternatives like Triple Pattern Fragments (TPF) distribute query processing but shift the burden of complex operations like joins to the client, leading to poor performance. The core problem is finding a way to provide both high data availability and efficient, reliable SPARQL query execution on public servers without overwhelming them.
Methods
SaGe tackles this problem by introducing a preemptive query execution model. The key innovation lies in its preemptable physical query execution plan and preemptable physical operators. When a query arrives, the SaGe server executes its plan for a fixed time slice (the "time quota"). If the query isn't finished within this quota, SaGe stops the execution, saves the current state of the execution plan, and returns the partial results along with this saved state to the client. The client can then resubmit the saved plan to continue the query execution from where it left off, effectively resuming the interrupted process. This approach is inspired by preemptive scheduling in operating systems and aims to provide proportional fairness, ensuring that long-running queries don't block shorter ones. The server itself remains stateless, as the execution state is managed by the client.
Datasets
The paper uses the WatDiv benchmark for experimental evaluation. This benchmark is designed to generate diverse Basic Graph Pattern (BGP) queries that stress RDF data management systems, including queries with varying complexity and selectivity.
Key Insights and Ideas
- Preemption as a Solution for Availability: The core insight is that preempting queries, rather than simply timing them out or rejecting them, allows for a more graceful handling of long-running operations on public endpoints. This directly addresses the data availability problem.
- Client-Side State Management for Stateless Servers: By offloading the saved query state to the client, SaGe achieves a stateless server architecture. This simplifies server management and allows clients to resume queries even if the server restarts or experiences temporary issues.
- Proportional Fairness for Better Throughput: The preemptive, time-sharing approach ensures that no single query monopolizes server resources, leading to improved overall query throughput, especially under high load. This is a significant advantage over traditional approaches that might suffer from starvation.
- BGP Execution on the Server: Unlike TPF, SaGe processes Basic Graph Patterns (BGPs) on the server side. This means intermediate results are not transmitted to the client, reducing data transfer overhead and improving performance.
Key Results
Experimental results demonstrate that SaGe significantly outperforms existing approaches like Virtuoso (with and without quotas), TPF, and BrTPF in terms of:
- Query Throughput: SaGe achieved higher query throughput, especially under increasing client loads.
- Query Timeout Ratio: SaGe drastically reduced the percentage of timed-out queries, indicating better handling of complex queries.
- Answer Completeness: SaGe was able to deliver complete results for a much larger portion of the workload compared to other methods, particularly Virtuoso with quotas.
For instance, in experiments with 100 clients, SaGe delivered complete results for up to 60 clients, dropping to 98% at 100 clients, whereas Virtuoso with quotas only delivered 20% of results.
Limitations and Future Work
The authors acknowledge several limitations and suggest future research directions:
- Focus on BGPs: The current implementation of SaGe focuses on Basic Graph Patterns (conjunctive queries of triple patterns). Future work aims to extend SaGe to support full SPARQL queries.
- Preemptable Operator Choices: The choice of preemptable join operators is limited, which can constrain the types of query execution plans that can be generated. Exploring more efficient preemptable operators is a key area for improvement.
- Scheduling Strategy: While Round-Robin scheduling was used for its simplicity, the authors plan to explore more sophisticated scheduling strategies to potentially further enhance performance.
- Dynamic Time Quota: The time quota was determined statically based on workload analysis. Future work will investigate computing this quota dynamically on the server side.
- Federated Query Processing: Extending SaGe to support federated SPARQL query processing is another promising avenue to address broader Semantic Web challenges.
Summary updated