ARQ - Optimizer

Overview

The ARQ-Optimizer is a cost based Basic Graph Pattern (BGP) optimizer for ARQ and Jena in-memory models. The optimizer fits into the query execution process and is executed during BGP stage generation. Hence, BGPs defined in the input query are analysed and optimized using heuristics for cost estimation of joined triple patterns.

Optimization is achieved by reordering the triple patterns of a BGP in a way that the intermediate result set sizes are minimized. The ARQ-Optimizer implements an algorithm which identifies the optimized execution order of the BGP triple patterns based on different heuristics which estimate the execution cost of joined triple patterns.

Usage

The ARQ-Optimizer is turned on by default in ARQ. Hence, for Jena in-memory models, BGPs are automatically optimized. Depending on the query execution context, the optimizer automatically identifies the best heuristic to use for cost estimation. Hence, in a generic setting, users should not be required to interact with the optimizer.

The optimizer code is organized in the following Java namespace

com.hp.hpl.jena.sparql.engine.optimizer

and provides the class

com.hp.hpl.jena.sparql.engine.optimizer.Optimizer

with static methods to enable and disable the optimizer. The optimizer can be disabled at any time in user applications by calling

Optimizer.disable()

either with or without the ARQ context. Disabling the optimizer will reset the context to the one specified and essentially override the BGP stage generator used by the optimizer in order that the optimizer is not executed any longer during BGP stage generation. The optimizer can, of course, be enabled by calling

Optimizer.enable()

either with or without the ARQ context. Note that providing the context to the methods allows to globally or locally enable or disable the optimizer, i.e. globally for every query executed by ARQ in an application or locally only for the query executed within a query execution.

Acknowledgments

The following people greatly influenced the development of ARQo

• Markus Stocker, who developed in his MSc thesis The Fundamentals of iSPARQL at the Department of Informatics, University of Zurich together with Prof. Abraham Bernstein and his assistant Christoph Kiefer the approach of selectivity estimation for static SPARQL query optimization. This work is partially published as technical report by Bernstein et al.
• Andy Seaborne, who constantly assisted the author with useful discussions and advices
• The author, Markus Stocker, for the implementation

ARQ Documentation Page