com.bigdata.rdf.sparql.ast.optimizers

Class ASTStaticBindingsOptimizer

java.lang.Object

com.bigdata.rdf.sparql.ast.optimizers.ASTStaticBindingsOptimizer

All Implemented Interfaces:

IASTOptimizer

public class ASTStaticBindingsOptimizer
extends Object
implements IASTOptimizer

Optimizer that aims at the optimization of SPARQL 1.1 pattern detecting static (i.e., non runtime dependent) binding for variables, moving them to the top-level of the query where possible, and attaching them with occurrences of the variable.

The optimizer may apply to the following construct: (A) BIND + VALUES clauses with constant values; (B) FILTER IN clauses with URIs; (C) FILTERs with sameTerm(?x,) and ?x= clauses

It proceeds as follows:

1. Identify the constructs mentioned above in the query and record identified static bindings. We distinguish between produced static bindings, namely constructs that introduce bindings (case A above) and enforced static bindings (cases B and C) above. Produced bindings are recorded in class ASTStaticBindingsOptimizer.StaticBindingInfo, and for them we also remove the construct producing the bindings, as they will later be added to as static bindings to the query top level (see step 3a below). See step 3b below for the treatment of enforced bindings

2. Along the way, we record usages of all variables, see class ASTStaticBindingsOptimizer.VariableUsageInfo. These usages (i) may be used for inlining in a later step, whenever we detected static bindings and (b) are used to decide whether static bindings can be considered global. There are some pitfalls here, in particular with FILTER expressions, see the code for in-depth comments.

3. Having extracted the static bindings and the associated variable usages, we proceed as follows: 3a. Produced bindings are moved to the top-level. For the main query this means inserting them into the set of exogeneous bindings, for subqueries we construct a VALUES clause. 3b. Both the produced and enforced bindings are "inlined" to identified usages of the variable. This essentially means replacing occurrences of the variable through a hybrid of Variable+Constant. This info can then later be used in further optimization steps and at runtime.

4. As a side effect, the optimizer re-initializes the StaticAnalysis class with the statically known bindings for the top-level query, which againg may be valuable input for further optimization.

Note: This optimizer generalizes the ASTSimpleBindingsOptimizer, the ASTValuesOptimizer, and the ASTBindingAssigner, which have been disabled and marked deprecated

The following extensions are not considered crucial for now, but might be subject to future work on this optimizer: (i) we may want to decompose FILTERs prior to running this optimizer, which may be useful to identify; (ii) in some cases it is also valid to propagate static bindings to optional patterns; implementing this might increase the benefit of the optimizer; (iii) we could implement some special handling for the variables reported by IEvaluationContext.getGloballyScopedVariables(): currently, they're just treated as "normal" variables and hence only inlined at top-level, but it would be possible to inline them into subqueries and in any nested scope as well, giving us a (in general) a better evaluation plan.

Version:

$Id$

Author:

Michael Schmidt

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	ASTStaticBindingsOptimizer.InlineTasks Task specifying the inlining opportunities for a given variable in the form of a list of query nodes in which a statically derived value for the given variable can be inlined.
static class	ASTStaticBindingsOptimizer.StaticBindingInfo Class that helps to keep track of static bindings that have been spotted during query analysis.
static class	ASTStaticBindingsOptimizer.VariableUsageInfo Helper class used to record usage of a given variable, i.e.

Constructor Summary

Constructors

Constructor and Description
ASTStaticBindingsOptimizer()

Method Summary

Methods

Modifier and Type	Method and Description
QueryNodeWithBindingSet	optimize(AST2BOpContext context, QueryNodeWithBindingSet input) Optimize the AST.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

ASTStaticBindingsOptimizer

public ASTStaticBindingsOptimizer()

Method Detail

optimize

public QueryNodeWithBindingSet optimize(AST2BOpContext context,
                               QueryNodeWithBindingSet input)

Description copied from interface: IASTOptimizer

Optimize the AST.

Specified by:

optimize in interface IASTOptimizer

Parameters:

context - The evaluation context.

input - The input to the optimizer, consisting of a queryNode and input binding set.

Returns:

An instance of type QueryNodeWithBindingSet.