| |
| Currently, relational databases are wildly adopted in RDF (Resource Description Framework) data management, but they show problematic performance in SPARQL query evaluation. One important factor is how to tackle the suboptimal query plan caused by error-prone cardinaltiy estimation. Consider the schema-free nature of RDF data and the extsc{Join}-intensive characteristic of SPARQL query, determine an optimal query plan is costly or even infeasible, especially for complex queries on large-scale data. In this paper, we propose ROSIE, a underline{R}untime underline{O}ptimization framework that iteratively re-optimize the underline{S}PARQL query plan accroding to the actual cardinality derived from underline{I}ncremental partial query underline{E}valuation. By introducing a heuristic-based plan generation approach, as well as a mechanism to detect cardinaltiy estimation error at runtime, ROSIE relieves the problem of biased cardinality propagation, and thus is more resilient to complex query evaluation. Extensive experiments on real and benchmark data show that compared to the state-of-the-arts, ROSIE can improve query performance by orders of magnitude. |
|
| Keywords:Computer Software and Theory, SPARQL query optimization, cardinality estimation, runtime optimization |
|
