com.bigdata.rdf.sparql.ast.optimizers

Class ASTSimpleGroupByAndCountOptimizer

java.lang.Object

com.bigdata.rdf.sparql.ast.optimizers.ASTSimpleGroupByAndCountOptimizer

All Implemented Interfaces:

IASTOptimizer

public class ASTSimpleGroupByAndCountOptimizer
extends Object
implements IASTOptimizer

Optimizes SELECT (COUNT(*) as ?count) ?z WHERE { ?x rdf:type ?z } GROUP BY ?z and similar patterns using an O(N) algorithm, where N is the number of distinct solutions.

The optimizer aims at establishing an execution plan that applies a combination of distinct term scan pattern (to efficiently compute the distinct values for the group variable) and fast range count pattern to efficiently calculate the COUNT, without materialization of the variables on which the COUNT operation is performed. The basic idea is to (i) replace the GROUP BY pattern through a SELECT DISTINCT subquery to calculate the distinct bindings for variable ?z first, and (ii) use a fast range count operator to efficiently calculate the COUNT. Note that the sub query in step (i) may (where possible) be optimized by the ASTDistinctTermScanOptimizer, i.e. if possible the subquery producing the ?z bindings will be replaced by a distinct term scan in a later optimization step.

Author:

Michael Schmidt

See Also:

GROUP BY optimization using distinct-term-scan and fast-range-count

Constructor Summary

Constructors

Constructor and Description
ASTSimpleGroupByAndCountOptimizer()

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

ASTSimpleGroupByAndCountOptimizer

public ASTSimpleGroupByAndCountOptimizer()

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.