org.modeshape.graph.query.plan
Class CanonicalPlanner

java.lang.Object
  org.modeshape.graph.query.plan.CanonicalPlanner

All Implemented Interfaces:

Planner

public class CanonicalPlanner
extends Object
implements Planner

The planner that produces a canonical query plan given a query command.

A canonical plan always has the same structure:

       LIMIT       if row limit or offset are used
         |
      SORTING      if 'ORDER BY' is used
         |
     DUP_REMOVE    if 'SELECT DISTINCT' is used
         |
      PROJECT      with the list of columns being SELECTed
         |
       GROUP       if 'GROUP BY' is used
         |
      SELECT1
         |         One or more SELECT plan nodes that each have
      SELECT2      a single non-join constraint that are then all AND-ed
         |         together (see separateAndConstraints(Constraint, List))
      SELECTn
         |
    SOURCE or JOIN     A single SOURCE or JOIN node, depending upon the query
              /  \
             /    \
           SOJ    SOJ    A SOURCE or JOIN node for the left and right side of the JOIN
 

There leaves of the tree are always SOURCE nodes, so conceptually data always flows through this plan from the bottom SOURCE nodes, is adjusted/filtered as it trickles up through the plan, and is then ready to be used by the caller as it emerges from the top node of the plan.

This canonical plan, however, is later optimized and rearranged so that it performs faster.

Constructor Summary

CanonicalPlanner()

Method Summary

protected void	allColumnsFor(Schemata.Table table, SelectorName tableName, List<Column> columns, List<String> columnTypes)
protected PlanNode	attachCriteria(QueryContext context, PlanNode plan, Constraint constraint, List<? extends Column> columns, Map<String,Subquery> subqueriesByVariableName) Attach all criteria above the join nodes.
protected PlanNode	attachDuplicateRemoval(QueryContext context, PlanNode plan) Attach DUP_REMOVE node at top of tree.
protected PlanNode	attachLimits(QueryContext context, PlanNode plan, Limit limit) Attach a LIMIT node at the top of the plan tree.
protected PlanNode	attachProject(QueryContext context, PlanNode plan, List<? extends Column> columns, Map<SelectorName,Schemata.Table> selectors) Attach a PROJECT node at the top of the plan tree.
protected PlanNode	attachSorting(QueryContext context, PlanNode plan, List<? extends Ordering> orderings) Attach SORT node at top of tree.
protected PlanNode	attachSubqueries(QueryContext context, PlanNode plan, Map<String,Subquery> subqueriesByVariableName) Attach plan nodes for each subquery, resulting with the first subquery at the top of the plan tree.
protected PlanNode	createCanonicalPlan(QueryContext context, Query query) Create a canonical query plan for the given query.
protected PlanNode	createCanonicalPlan(QueryContext context, SetQuery query) Create a canonical query plan for the given set query.
PlanNode	createPlan(QueryContext context, QueryCommand query) Create a canonical query plan for the given command.
protected PlanNode	createPlanNode(QueryContext context, Source source, Map<SelectorName,Schemata.Table> usedSelectors) Create a JOIN or SOURCE node that contain the source information.
protected void	separateAndConstraints(Constraint constraint, List<Constraint> andableConstraints) Walk the supplied constraint to extract a list of the constraints that can be AND-ed together.
protected void	setSubqueryVariableName(PlanNode subqueryPlan, String varName)
protected void	validate(QueryContext context, QueryCommand query, Map<SelectorName,Schemata.Table> usedSelectors) Validate the supplied query.

Methods inherited from class java.lang.Object

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

Constructor Detail

CanonicalPlanner

public CanonicalPlanner()

Method Detail

createPlan

public PlanNode createPlan(QueryContext context,
                           QueryCommand query)

Create a canonical query plan for the given command.

Specified by:

createPlan in interface Planner

Parameters:

context - the context in which the query is being planned

query - the query command to be planned

Returns:

the root node of the plan tree representing the canonical plan

See Also:

Planner.createPlan(org.modeshape.graph.query.QueryContext, org.modeshape.graph.query.model.QueryCommand)

createCanonicalPlan

protected PlanNode createCanonicalPlan(QueryContext context,
                                       Query query)

Create a canonical query plan for the given query.

Parameters:

context - the context in which the query is being planned

query - the query to be planned

Returns:

the root node of the plan tree representing the canonical plan

validate

protected void validate(QueryContext context,
                        QueryCommand query,
                        Map<SelectorName,Schemata.Table> usedSelectors)

Validate the supplied query.

Parameters:

context - the context in which the query is being planned

query - the set query to be planned

usedSelectors - the map of SelectorNames (aliases or names) used in the query.

createCanonicalPlan

protected PlanNode createCanonicalPlan(QueryContext context,
                                       SetQuery query)

Create a canonical query plan for the given set query.

Parameters:

context - the context in which the query is being planned

query - the set query to be planned

Returns:

the root node of the plan tree representing the canonical plan

createPlanNode

protected PlanNode createPlanNode(QueryContext context,
                                  Source source,
                                  Map<SelectorName,Schemata.Table> usedSelectors)

Create a JOIN or SOURCE node that contain the source information.

Parameters:

context - the execution context

source - the source to be processed; may not be null

usedSelectors - the map of SelectorNames (aliases or names) used in the query.

Returns:

the new plan; never null

attachCriteria

protected PlanNode attachCriteria(QueryContext context,
                                  PlanNode plan,
                                  Constraint constraint,
                                  List<? extends Column> columns,
                                  Map<String,Subquery> subqueriesByVariableName)

Attach all criteria above the join nodes. The optimizer will push these criteria down to the appropriate source.

Parameters:

context - the context in which the query is being planned

plan - the existing plan, which joins all source groups

constraint - the criteria or constraint from the query

columns - the columns in the select (that may have aliases)

subqueriesByVariableName - the subqueries by variable name

Returns:

the updated plan, or the existing plan if there were no constraints; never null

separateAndConstraints

protected void separateAndConstraints(Constraint constraint,
                                      List<Constraint> andableConstraints)

Walk the supplied constraint to extract a list of the constraints that can be AND-ed together. For example, given the constraint tree ((C1 AND C2) AND (C3 OR C4)), this method would result in a list of three separate criteria: [C1,C2,(C3 OR C4)]. The resulting andConstraints list will contain Constraint objects that all must be true.

Parameters:

constraint - the input constraint

andableConstraints - the collection into which all non-AND constraints should be placed

attachSorting

protected PlanNode attachSorting(QueryContext context,
                                 PlanNode plan,
                                 List<? extends Ordering> orderings)

Attach SORT node at top of tree. The SORT may be pushed down to a source (or sources) if possible by the optimizer.

Parameters:

context - the context in which the query is being planned

plan - the existing plan

orderings - list of orderings from the query

Returns:

the updated plan, or the existing plan if there were no orderings; never null

attachLimits

protected PlanNode attachLimits(QueryContext context,
                                PlanNode plan,
                                Limit limit)

Attach a LIMIT node at the top of the plan tree.

Parameters:

context - the context in which the query is being planned

plan - the existing plan

limit - the limit definition; may be null

Returns:

the updated plan, or the existing plan if there were no limits

attachProject

protected PlanNode attachProject(QueryContext context,
                                 PlanNode plan,
                                 List<? extends Column> columns,
                                 Map<SelectorName,Schemata.Table> selectors)

Attach a PROJECT node at the top of the plan tree.

Parameters:

context - the context in which the query is being planned

plan - the existing plan

columns - the columns being projected; may be null

selectors - the selectors keyed by their alias or name

Returns:

the updated plan

allColumnsFor

protected void allColumnsFor(Schemata.Table table,
                             SelectorName tableName,
                             List<Column> columns,
                             List<String> columnTypes)

attachDuplicateRemoval

protected PlanNode attachDuplicateRemoval(QueryContext context,
                                          PlanNode plan)

Attach DUP_REMOVE node at top of tree. The DUP_REMOVE may be pushed down to a source (or sources) if possible by the optimizer.

Parameters:

context - the context in which the query is being planned

plan - the existing plan

Returns:

the updated plan

attachSubqueries

protected PlanNode attachSubqueries(QueryContext context,
                                    PlanNode plan,
                                    Map<String,Subquery> subqueriesByVariableName)

Attach plan nodes for each subquery, resulting with the first subquery at the top of the plan tree.

Parameters:

context - the context in which the query is being planned

plan - the existing plan

subqueriesByVariableName - the queries by the variable name used in substitution

Returns:

the updated plan, or the existing plan if there were no limits

setSubqueryVariableName

protected void setSubqueryVariableName(PlanNode subqueryPlan,
                                       String varName)