Traveling Light — A Low-Overhead Approach for SPARQL Query Optimization

SPARQL query processing in triplestores has to deal with many of the same problems as query processing in relational databases, and additional problems due to the schema relaxed nature of RDF. The flexible pattern matching capabilities of SPARQL queries entail performance challenges for complex queries. Most modern query optimizers produce a significant overhead as they use an exhaustive statistics generation and storage approach. Currently, there is no pure online cost-based optimizer for SPARQL queries. In this paper, we explore the hypothesis that just storing selectivity statistics for predicates enables effective optimization of typical queries. Based on this, we introduce a pure online optimizer for triplestores, the Online Join Order Optimizer (OJOO), which learns from query executions. OJOO's overhead in creating and persisting statistics is very low, and it provides an easily extendable storage architecture for statistics. We implemented the OJOO in a main-memory triplestore, PDStore (Parsimonious Data Store), and evaluated its performance experimentally using the Lehigh University Benchmark (LUBM). Our experimental results revealed that the OJOO is competitive, efficient, scalable, and has a negligible runtime overhead.