TL;DR
This paper tackles the challenge of processing "TOP-k" queries (e.g., finding the 10 oldest people) on public SPARQL endpoints, which often time out due to fair-use policies and inefficient "materialize-and-sort" strategies. The authors introduce a novel "preemptable partial TOP-k operator" that significantly reduces data transfer and query execution time by allowing queries to be suspended and resumed without recomputing everything, and by enabling early pruning of irrelevant results.
What Problem Does This Paper Address?
Public SPARQL endpoints, like those for knowledge graphs (e.g., Wikidata), are crucial for accessing vast amounts of data. However, a common issue arises when users try to retrieve the "top k" results for a query (e.g., the 10 tallest buildings, the 5 most recent scientific papers). These queries, often involving ORDER BY and LIMIT clauses, typically require the SPARQL engine to first retrieve all possible results, then sort them, and finally select the top k. This "materialize-and-sort" approach is highly inefficient, especially for queries that might return millions of results before the top 10 are identified. Public endpoints often impose quotas (like time limits) to prevent abuse, leading to these TOP-k queries being abruptly terminated before completion. While some restricted SPARQL servers offer better guarantees, they still often rely on the inefficient materialize-and-sort method on the client side, leading to massive data transfers and slow performance. The core problem is how to efficiently process TOP-k queries on public endpoints while respecting their fair-use policies and ensuring timely completion.
Methods
The paper proposes extending the "Web preemption" model with a new "preemptable partial TOP-k operator." Web preemption allows a server to suspend a query, save its state, and resume it later, preventing it from exceeding time limits. However, traditional Web preemption still requires transferring all intermediate results to the client for sorting.
The authors' key innovation is the preemptable partial TOP-k operator. This operator works in two main ways:
- Partial TOP-k: Instead of materializing all results, the server maintains only the top k results seen so far within a given quantum (a time slice of execution). This partial list is managed efficiently, with its overhead not depending on the total number of results, but rather on k (or a predefined maximum K). When a query is suspended, only this partial list and the query state are sent to the client.
- Early Pruning: The system also incorporates early pruning. By knowing the current "threshold" (the rank of the worst result currently in the top-k list), the server can discard any new results that are guaranteed to be worse than this threshold, further reducing data transfer.
The implementation involves extending the SAGE query engine with these new operators.
Datasets
The paper uses two main sources for data and queries:
- Waterloo SPARQL Diversity Benchmark (WatDiv): This benchmark was used for evaluating the performance of the proposed approach. The authors re-used the RDF graph and SPARQL queries from a previous SAGE study. The RDF graph contains 107 million triples, and the workload includes 193 queries. For their experiments, they randomly selected 20 SPARQL conjunctive queries with varying shapes and up to 10 joins, and then randomly generated
ORDER BYandLIMITclauses. - Wikidata Query Logs: To test the approach on real-world queries, the authors extracted 20 queries from Wikidata logs. These queries had 1 to 10 joins, a single-variable
ORDER BYclause, and aLIMIT koperator with k ranging from 1 to 10000. These queries were executed on a 2017-03-13 dump of Wikidata (2262 million triples).
Key Insights and Ideas
- The "materialize-and-sort" bottleneck: The paper clearly illustrates why the standard approach to TOP-k queries is fundamentally flawed for public endpoints, leading to timeouts and massive data transfer.
- Web Preemption + Partial TOP-k = Efficiency: The core insight is that by combining Web preemption with a server-side partial TOP-k computation, the system can avoid transferring all results to the client, drastically reducing data transfer and improving execution time.
- Overhead independence from total results: A crucial aspect is that the proposed partial TOP-k operator's overhead is bounded by k (or K), not the total number of results. This makes it scalable even when the underlying query would produce millions of intermediate mappings.
- Early pruning's impact: While partial TOP-k significantly helps, early pruning further boosts performance, especially for queries where the ranking criteria are evaluated early in the query execution plan.
- Trade-offs in Web Preemption: The paper highlights that while Web preemption is key, the duration of a quantum and the maximum limit K for partial results need careful configuration to balance performance and overhead.
Key Results
The experimental results demonstrate significant improvements:
- Data Transfer Reduction: The proposed approach reduces data transfer by a factor of up to 100 compared to the baseline SAGE approach (which transfers all results).
- Execution Time Improvement: Query execution time is reduced by up to 39% on Wikidata queries and up to 60% on WatDiv queries when early pruning is enabled.
- Reduced HTTP Calls: The number of HTTP calls is significantly reduced because fewer intermediate results need to be sent to the client.
- Preemptable Operator Efficiency: The preemptable partial TOP-k iterator's overhead for saving and resuming does not depend on the total number of results, only on k (or K), making it robust.
- Early Pruning Effectiveness: Early pruning shows a substantial impact, reducing execution time by up to 60% for smaller k values, though its effectiveness diminishes for larger k.
Limitations and Future Work
- Maximum Limit K: The preemptable TOP-k iterator (Algorithm 1) imposes a maximum value K on the number of results. If a user requests k > K, they must fall back to the client-side solution. The partial TOP-k iterator (Algorithm 2) also has performance implications if K is reached frequently.
- Join Order Dependency: The effectiveness of early pruning is noted to be highly dependent on the query's join order.
- Future Work: The authors plan to explore supporting early termination of TOP-k queries within the Web preemption context. They also aim to investigate how their partial TOP-k iterator can be applied to aggregate queries, which currently rely on similar preemptable iterator concepts.
Summary updated