TL;DR
This paper tackles the challenge of efficiently executing SPARQL queries that involve "property path queries" (PPQs), which are common in knowledge graphs like Wikidata. They introduce a novel query optimizer that uses a combination of "reachability-pattern relaxation" and a "sampling-based cardinality estimator" to significantly speed up query execution, outperforming existing engines.
What Problem Does This Paper Address?
SPARQL 1.1 introduced property paths, allowing users to express complex navigational queries over RDF data. These are incredibly popular, especially in knowledge graphs like Wikidata, where they account for a significant portion of queries. However, evaluating these property path queries, particularly those involving transitive closures (paths of arbitrary length), is computationally expensive. Many such queries time out or fail to complete within reasonable limits. Existing query optimization techniques, which work well for traditional conjunctive queries, struggle with property paths because the cost of evaluating a path pattern can depend heavily on how it's used within the overall query plan, not just its inherent cardinality. This paper aims to bridge this gap by developing an optimizer that can accurately estimate and minimize the cost of property path queries.
Methods
The core of the paper's contribution lies in its novel query optimizer, which integrates two key techniques:
- Reachability-Pattern Relaxation: Property path patterns can behave differently depending on the join order. They can be treated as "transitive-patterns" (where cost is related to cardinality) or "reachability-patterns" (where cost is more complex and not directly tied to cardinality). The optimizer identifies these reachability-patterns and "relaxes" them by transforming them into equivalent patterns that can be evaluated using traditional cost models. This relaxation involves generating forward and backward filter patterns to explore different evaluation strategies.
- Sampling-Based Cardinality Estimator: To accurately estimate the cost of these relaxed patterns, the optimizer employs a cardinality estimator based on "random walks." This approach, inspired by techniques for conjunctive queries, uses random walks over the RDF graph to estimate the number of results. For property path queries, it rewrites them into equivalent queries without property paths and then uses random walks to estimate their cardinality, even handling UNION clauses that arise from rewriting.
The optimizer uses a dynamic programming approach to explore different join orders, incorporating the relaxation and cardinality estimation steps to find the most efficient plan.
Datasets
The experiments were conducted using the Wikidata Graph Query Benchmark (WDBench). This benchmark is derived from real-world SPARQL queries from the Wikidata query logs and uses a corresponding RDF dataset. The authors filtered out non-property path queries and queries with cross-products to create their specific workload.
Key Insights and Ideas
- The "reachability-pattern" problem: The paper highlights that traditional cardinality-based cost models fail for property path queries because some patterns, when evaluated in certain join orders, become "reachability-patterns" whose evaluation cost is not simply proportional to their cardinality.
- Relaxation as a solution: By transforming reachability-patterns into a form that can be evaluated using standard cost models (like transitive-patterns), the optimizer can more accurately estimate query costs.
- Random walks for cardinality: The use of random walks as a cardinality estimator is a powerful technique that avoids the need for expensive statistics or specialized indexes, making it adaptable to existing SPARQL engines.
- Join order is crucial: The paper strongly demonstrates that the order in which query components are joined has a dramatic impact on the performance of property path queries, often leading to timeouts or significant slowdowns.
Key Results
The proposed approach significantly improves query execution times:
- BlazeGraph: The workload execution time was divided by at least 14 compared to BlazeGraph's default optimizer.
- Virtuoso: A 14% improvement in execution time was observed compared to Virtuoso.
- Timeouts and Errors: The proposed optimizer drastically reduced timeouts and errors, with BlazeGraph's default optimizer experiencing numerous timeouts and errors, while the proposed method achieved near-zero.
- Parameter Impact: Increasing the budget of random walks (k) generally leads to better performance, while the depth limit (dMax) needs careful tuning; a larger dMax can improve accuracy but also increase optimization time.
Limitations and Future Work
- Distinct Modifier: The paper acknowledges that for simplicity, the
DISTINCTmodifier in queries is ignored during cardinality estimation. This can lead to overestimation on dense graphs, potentially impacting join order quality. The authors assume this won't prevent finding good join orders in practice. - Nested Stars: The current approach does not consider nested star expressions in property paths, which is identified as a direction for future work.
- Other Operators: Extending the random walk-based cardinality estimation to handle
MINUS,OPTIONAL, andFILTER NOT EXISTSoperators is also suggested for future research. - Budget Model: Further improvements in optimization time could be achieved with a better budget model for random walks, potentially adapting the budget per join order.
Summary updated