com.bigdata.rdf.sparql.ast.optimizers

Class ASTExistsOptimizer

java.lang.Object

com.bigdata.rdf.sparql.ast.optimizers.ASTExistsOptimizer

All Implemented Interfaces:

IASTOptimizer

public class ASTExistsOptimizer
extends Object
implements IASTOptimizer

Optimizer identifies value expressions using EXISTS or NOT EXISTS and rewrites them in a form suitable for evaluation by the query engine. The main problem with (NOT) EXIST is that the query engine is not written to evaluate graph patterns within value expressions. Therefore the graph pattern is extracted into a subquery which must be evaluated before the FILTER may be evaluated.

Like the FILTER in which the (NOT EXISTS) appears (and like MINUS) the order in which graph pattern must be evaluated is determined by the same general principles which govern the attachment of FILTERs to joins. That is, when a variable on which the filter depends is bound by a required join they must not run before that required join. And, when a variable on which the filter depends is only bound by an optional join, then they must not run until after that optional join.

For (NOT) EXISTS evaluation we need to bind the outcome of the graph pattern (that is, whether or not the graph pattern is satisified) onto an anonymous variable (assigned by the SPARQL parser). It is the truth state of that anonymous variable which is tested by the filter. This is handled by special handshaking with the join in which we declare the anonymous variable to the join (this is the "ASK_VAR") and project only that anonymous variable out of the join.

All variables which are in scope when the (NOT) EXISTS graph pattern is evaluated must be projected into the subquery (since they must be visible to it), but the bindings produced by the subquery (other than the anonymous variable indicating whether or not the graph pattern "exists") must be discarded. Again, this is handled by projecting out only the "anonymous" variable and the join variables (which are bound on entry to the join and are used within the (NOT) EXISTS graph pattern). Other bindings are discarded.

The interpretation of the truth state of the variable by the FILTER provides the "exists" or "not exists" semantics. The hash index containing the ASK VAR bindings must remain visible until the corresponding FILTER has been evaluated.

Note: This rewrite must run relatively early to ensure that other optimizers are able to run against the graph pattern once it has been lifted out of the (NOT) EXISTS onto a subquery.

Version:

$Id$

Author:

Bryan Thompson

See Also:

ExistsNode, NotExistsNode

Constructor Summary

Constructors

Constructor and Description
ASTExistsOptimizer()

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

ASTExistsOptimizer

public ASTExistsOptimizer()

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.