Access Pattern Validation - ensures that all access patterns have been satisfied

Apply Security - applies row and column level security

Assign Output Symbol - this rule walks top down through every node and calculates the output columns for each node.  Columns that are not needed are dropped at every node, which is known as projection minimization.  This is done by keeping track of both the columns needed to feed the parent node and also keeping track of columns that are "created" at a certain node.

Calculate Cost - adds costing information to the plan

Choose Dependent - this rule looks at each join node and determines whether the join should be made dependent and in which direction.  Cardinality, the number of distinct values, and primary key information are used in several formulas to determine whether a dependent join is likely to be worthwhile.  The dependent join differs in performance ideally because a fewer number of values will be returned from the dependent side.  Also, we must consider the number of values passed from independent to dependent side.  If that set is larger than the max number of values in an IN criteria on the dependent side, then we must break the query into a set of queries and combine their results. Executing each query in the connector has some overhead and that is taken into account.  Without costing information a lot of common cases where the only criteria specified is on a non-unique (but strongly limiting) field are missed.  A join is eligible to be dependent if:

there is at least one equi-join criterion, i.e. tablea.col = tableb.col

the join is not a full outer join and the dependent side of the join is on the inner side of the join

There is an unsatisfied access pattern that can be satisfied with the dependent join criteria

The potential dependent side of the join is marked with an option makedep

(4.3.2) if costing was enabled, the estimated cost for the dependent join (5.0+ possibly in each direction in the case of inner joins) is computed and compared to not performing the dependent join.  If the costs were all determined (which requires all relevant table cardinality, column ndv, and possibly nnv values to be populated) the lowest is chosen.

If key metadata information indicates that the potential dependent side is not "small" and the other side is "not small" or (5.0.1) the potential dependent side is the inner side of a left outer join.

Choose Join Strategy - choose the join strategy based upon the cost and attributes of the join.

Clean Criteria - removes phantom criteria

Collapse Source - takes all of the nodes below an access node and creates a SQL query representation

Copy Criteria - this rule copies criteria over an equality criteria that is present in the criteria of a join.  Since the equality defines an equivalence, this is a valid way to create a new criteria that may limit results on the other side of the join (especially in the case of a multi-source join).

Decompose Join - this rule perfomrs a partition-wise join optimization on joins of Federated Optimizations#Partitioned Union. The decision to decompose is based upon detecting that each side of the join is a partitioned union (note that non-ansi joins of more than 2 tables may cause the optimization to not detect the appropriate join). The rule currently only looks for situations where at most 1 partition matches from each side.

Implement Join Strategy - adds necessary sort and other nodes to process the chosen join strategy

Merge Criteria - combines select nodes and can convert subqueries to semi-joins

Merge Virtual - removes view and inline view layers

Place Access - places access nodes under source nodes. An access node represents the point at which everything below the access node gets pushed to the source or is a plan invocation.  Later rules focus on either pushing under the access or pulling the access node up the tree to move more work down to the sources.  This rule is also responsible for placing Federated Optimizations#Access Patterns.

Plan Joins - this rule attempts to find an optimal ordering of the joins performed in the plan, while ensuring that Federated Optimizations#Access Patterns dependencies are met.  This rule has three main steps.  First it must determine an ordering of joins that satisfy the access patterns present.  Second it will heuristically create joins that can be pushed to the source (if a set of joins are pushed to the source, we will not attempt to create an optimal ordering within that set.  More than likely it will be sent to the source in the non-ANSI multi-join syntax and will be optimized by the database). Third it will use costing information to determine the best left-linear ordering of joins performed in the processing engine.  This third step will do an exhaustive search for 7 or less join sources and is heuristically driven by join selectivity for 8 or more sources.

Plan Outer Joins - reorders outer joins as permitted to improve push down.

Plan Procedures - plans procedures that appear in procedural relational queries

Plan Sorts - optimizations around sorting, such as combining sort operations or moving projection

Plan Unions - reorders union children for more pushdown

Plan Aggregates - performs aggregate decomposition over a join or union

Push Limit - pushes the affect of a limit node further into the plan

Push Non-Join Criteria - this rule will push predicates out of an on clause if it is not necessary for the correctness of the join.

Push Select Criteria - push select nodes as far as possible through unions, joins, and views layers toward the access nodes.  In most cases movement down the tree is good as this will filter rows earlier in the plan.  We currently do not undo the decisions made by Push Select Criteria.  However in situations where criteria cannot be evaluated by the source, this can lead to sub optimal plans.

Push Large IN - push IN predicates that are larger than directly supported by the translator to be processed as a dependent set.

Raise Access - this rule attempts to raise the Access nodes as far up the plan as possible.  This is mostly done by looking at the source’s capabilities and determining whether the operations can be achieved in the source or not.

Raise Null - raises null nodes. Raising a null node removes the need to consider any part of the old plan that was below the null node.

Remove Optional Joins - removes joins that are marked as or determined to be optional

Substitute Expressions - used only when a function based index is present

Validate Where All - ensures criteria is used when required by the source

Document selection - determine which tags of the virtual document should be excluded from the output document.  This is done based on a combination of the model (which marks parts of the document excluded) and the query (which may specify a subset of columns to include in the SELECT clause).

Criteria evaluation - breaks apart the user’s criteria, determine which result set the criteria should be applied to, and add that criteria to that result set query.

Result set ordering - the query’s ORDER BY clause is broken up and the ORDER BY is applied to each result set as necessary

Result set planning - ultimately, each result set is planned using the relational planner and taking into account all the impacts from the user’s query. The planner will also look to automatically create staging tables and dependent joins based upon the mapping class hierarchy.

Program generation - a set of instructions to produce the desired output document is produced, taking into account the final result set queries and the excluded parts of the document.  Generally, this involves walking through the virtual document in document order, executing queries as necessary and emitting elements and attributes.