com.bigdata.rdf.sparql.ast.optimizers

Class ASTComplexOptionalOptimizer

java.lang.Object

com.bigdata.rdf.sparql.ast.optimizers.ASTComplexOptionalOptimizer

All Implemented Interfaces:

IASTOptimizer

Deprecated.

@Deprecated
public class ASTComplexOptionalOptimizer
extends Object
implements IASTOptimizer

NOTE: this optimizer was not sound from a correctness perspective in previous versions (cf. http://trac.blazegraph.com/ticket/1071); the rewritten form should be fine from a correctness perspective, but does not really optimize queries from a performance perspective, so it has been (temporarily) disabled in the DefaultOptimizerList. The description below describes the original idea, the actual implementation slightly differs in (i) that it passes around intermediate solutions (rather than computing all joins over the original outer mapping set) and (ii) does not compute a final join over all intermediate solutions but simply returns the last computed result (which is now possible due to (i)). Also note that the AST2BOpUtility has been refactored (as part of ticket #1071 and #1118) and now implements intelligent pushing of projection variables into OPTIONAL blocks, so there's probably no more need for this optimizer. Rewrite a join group using two or more complex OPTIONAL groups using a hash join pattern.

Note: this optimization is not required if there is only one complex optional in the join group. It is only when there are multiple complex optional groups that we need to lift those groups out as named subqueries (since they need to feed each other). If there is only one complex optional group, then we can run it as a sub-group instead.

NOte: This optimization presumes that simple optional groups were already translated into optional StatementPatternNodes.

Queries with multiple complex optional groups can be rewritten into the hash join of solution sets as follows.

1. First, create a hash index from the required joins and any simple optional joins. Given the modeling abilities of the AST, this is most easily achieved by converting the required joins into a named subquery. The join variable(s) for that named subquery will the subset of variable(s) which are shared by each of the complex OPTIONAL groups. The ASTNamedSubqueryOptimizer already handles the assignment of join variables, so we do not need to consider it further here.
2. For each complex optional group, use the solution step generated in (1) and run the optional group as a named subquery producing a new solution set. The WHERE clause of the named subquery should look like:

    {INCLUDE %set . OPTIONAL {...}}
    

3. Join all of the named solution sets in (2) back together. For example, if there were two complex optional groups and the required joins resulted in known bound variables for var1 and var2, then those result sets might be combined as follows in the main WHERE clause of the rewritten query.

    INCLUDE %set1 .
    INCLUDE %set2 JOIN ON (?var1, ?var2) .
    

   Note: The join variables for those INCLUDEs MUST be identified through static analysis. Failure to use available join variables will result in an extremely inefficient query plan as the full cross product of the solutions will be compared to identify solutions which join.

TODO The rewrite into named subquery includes means that we wind up building more hash indices than we strictly require as a hash index will also be built at the start of each optional group. However, since the hash index at the start of the optional group has exactly the same data as the named subquery include's hash index, we should elide the step which builds the extra hash index. TODO This optimzer should not be strictly necessary at all. The same behavior should arise from running the complex optionals as sub-groups. Based on a few govtrack CI queries, it looks like we do better when the complex optional groups are lifted out as named subqueries. We need to go back and investigate whether or not this is true and why.

Author:

Bryan Thompson, Michael Schmidt

See Also:

https://sourceforge.net/apps/trac/bigdata/ticket/397

Constructor Summary

Constructors

Constructor and Description
ASTComplexOptionalOptimizer() Deprecated.

Method Summary

Methods

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

Methods inherited from class java.lang.Object

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

Constructor Detail

ASTComplexOptionalOptimizer

public ASTComplexOptionalOptimizer()

Deprecated.

Method Detail

optimize

public QueryNodeWithBindingSet optimize(AST2BOpContext context,
                               QueryNodeWithBindingSet input)

Deprecated.

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.