org.apache.derby.impl.sql.compile
Class HalfOuterJoinNode

java.lang.Object
  extended by org.apache.derby.impl.sql.compile.QueryTreeNode
      extended by org.apache.derby.impl.sql.compile.ResultSetNode
          extended by org.apache.derby.impl.sql.compile.FromTable
              extended by org.apache.derby.impl.sql.compile.TableOperatorNode
                  extended by org.apache.derby.impl.sql.compile.JoinNode
                      extended by org.apache.derby.impl.sql.compile.HalfOuterJoinNode
All Implemented Interfaces:
Optimizable, Visitable

public class HalfOuterJoinNode
extends JoinNode

An HalfOuterJoinNode represents a left or a right outer join result set. Right outer joins are always transformed into left outer joins during preprocessing for simplicity.


Field Summary
private  boolean rightOuterJoin
           
private  boolean transformed
           
 
Fields inherited from class org.apache.derby.impl.sql.compile.JoinNode
aggregateVector, CROSSJOIN, flattenableJoin, FULLOUTERJOIN, INNERJOIN, joinClause, joinClauseNormalized, joinOrderStrategyProperties, joinPredicates, LEFTOUTERJOIN, RIGHTOUTERJOIN, subqueryList, UNIONJOIN, usingClause
 
Fields inherited from class org.apache.derby.impl.sql.compile.TableOperatorNode
leftOptimizer, leftResultSet, rightOptimizer, rightResultSet
 
Fields inherited from class org.apache.derby.impl.sql.compile.FromTable
ADD_PLAN, bestAccessPath, bestCostEstimate, bestSortAvoidancePath, correlationName, corrTableName, currentAccessPath, hashKeyColumns, initialCapacity, level, LOAD_PLAN, loadFactor, maxCapacity, origTableName, REMOVE_PLAN, tableNumber, tableProperties, trulyTheBestAccessPath, userSpecifiedJoinStrategy
 
Fields inherited from class org.apache.derby.impl.sql.compile.ResultSetNode
costEstimate, cursorTargetTable, finalCostEstimate, insertSource, optimizer, referencedTableMap, resultColumns, resultSetNumber, scratchCostEstimate, statementResultSet
 
Fields inherited from class org.apache.derby.impl.sql.compile.QueryTreeNode
AUTOINCREMENT_CREATE_MODIFY, AUTOINCREMENT_INC_INDEX, AUTOINCREMENT_IS_AUTOINCREMENT_INDEX, AUTOINCREMENT_START_INDEX, isPrivilegeCollectionRequired
 
Constructor Summary
HalfOuterJoinNode()
           
 
Method Summary
protected  int addOuterJoinArguments(ActivationClassBuilder acb, MethodBuilder mb)
          Generate and add any arguments specifict to outer joins.
protected  void adjustNumberOfRowsReturned(CostEstimate costEstimate)
          Some types of joins (e.g. outer joins) will return a different number of rows than is predicted by optimizeIt() in JoinNode.
 void generate(ActivationClassBuilder acb, MethodBuilder mb)
          Generate the code for an inner join node.
(package private)  ResultSetNode getLogicalLeftResultSet()
          Return the logical left result set for this qualified join node.
(package private)  ResultSetNode getLogicalRightResultSet()
          Return the logical right result set for this qualified join node.
protected  int getNumJoinArguments()
          Return the number of arguments to the join result set.
 void init(java.lang.Object leftResult, java.lang.Object rightResult, java.lang.Object onClause, java.lang.Object usingClause, java.lang.Object rightOuterJoin, java.lang.Object tableProperties)
          Initializer for a HalfOuterJoinNode.
private  boolean isNullRejecting(ValueNode joinClause, JBitSet leftTableMap, JBitSet rightTableMap)
          Tests pRiRj in the sense of Galindo-Legaria et al: Outerjoin Simplification and Reordering for Query Optimization, ACM Transactions on Database Systems, Vol. 22, No. 1, March 1997, Pages 43-74: "The set of attributes referenced by a predicate p is called the schema of p, and denoted sch(p).
 boolean isRightOuterJoin()
          Return true if right outer join or false if left outer join Used to set Nullability correctly in JoinNode
 boolean LOJ_bindResultColumns(boolean anyChange)
           
 boolean LOJ_reorderable(int numTables)
          This method recursively: determines if this part of the query tree is a compound OJ of the shape required for reordering and if so, does a reordering.
 JBitSet LOJgetNPReferencedTables(int numTables)
           
 JBitSet LOJgetRPReferencedTables(int numTables)
           
protected  void oneRowRightSide(ActivationClassBuilder acb, MethodBuilder mb)
           
 ResultSetNode preprocess(int numTables, GroupByList gbl, FromList fromList)
          Put a ProjectRestrictNode on top of each FromTable in the FromList.
 void pushExpressions(PredicateList outerPredicateList)
          Push expressions down to the first ResultSetNode which can do expression evaluation and has the same referenced table map.
 boolean pushOptPredicate(OptimizablePredicate optimizablePredicate)
          Push an OptimizablePredicate down, if this node accepts it.
 java.lang.String toString()
          Convert this object to a String.
 FromTable transformOuterJoins(ValueNode predicateTree, int numTables)
          Transform any Outer Join into an Inner Join where applicable.
 
Methods inherited from class org.apache.derby.impl.sql.compile.JoinNode
acceptChildren, bindExpressions, bindResultColumns, bindResultColumns, flatten, generateCore, generateCore, getAllResultColumns, getFinalCostEstimate, getLeftPredicateList, getMatchingColumn, getRightPredicateList, init, isFlattenableJoinNode, isOrderedOn, joinTypeToString, LOJgetReferencedTables, modifyAccessPath, normExpressions, notFlattenableJoin, optimizeIt, printSubNodes, projectResultColumns, pushExpressionsToLeft, setAggregateVector, setNaturalJoin, setSubqueryList, updateTargetLockMode
 
Methods inherited from class org.apache.derby.impl.sql.compile.TableOperatorNode
adjustForSortElimination, adjustForSortElimination, bindExpressionsWithTables, bindNonVTITables, bindUntypedNullsToResultColumns, bindVTITables, decrementLevel, getExposedName, getFromTableByName, getLeftmostResultSet, getLeftResultSet, getRightResultSet, init, modifyAccessPaths, needsSpecialRCLBinding, optimize, optimizeSource, referencesSessionSchema, referencesTarget, rejectParameters, setLeftmostResultSet, setLevel, setNestedInParens, setReferencedColumns, updateBestPlanMap, verifyProperties
 
Methods inherited from class org.apache.derby.impl.sql.compile.FromTable
assignCostEstimate, canBeOrdered, considerSortAvoidancePath, convertAbsoluteToRelativeColumnPosition, cursorTargetTable, estimateCost, feasibleJoinStrategy, fillInReferencedTableMap, forUpdate, getBaseTableName, getBestAccessPath, getBestSortAvoidancePath, getCorrelationName, getCostEstimate, getCurrentAccessPath, getLevel, getName, getNumColumnsReturned, getOrigTableName, getProperties, getResultColumnsForList, getSchemaDescriptor, getSchemaDescriptor, getScratchCostEstimate, getTableDescriptor, getTableName, getTableNumber, getTrulyTheBestAccessPath, getUserSpecifiedJoinStrategy, hashKeyColumns, hasTableNumber, init, initAccessPaths, initialCapacity, isBaseTable, isCoveringIndex, isMaterializable, isOneRowScan, isTargetTable, legalJoinOrder, loadFactor, markUpdatableByCursor, maxCapacity, memoryUsageOK, nextAccessPath, optimizeSubqueries, pullOptPredicates, rememberAsBest, rememberJoinStrategyAsBest, rememberSortAvoidancePath, resetJoinStrategies, setCostEstimate, setHashKeyColumns, setOrigTableName, setProperties, setTableNumber, startOptimizing, supportsMultipleInstantiations, tellRowOrderingAboutConstantColumns, uniqueJoin
 
Methods inherited from class org.apache.derby.impl.sql.compile.ResultSetNode
addNewPredicate, assignResultSetNumber, bindTargetExpressions, changeAccessPath, columnTypesAndLengthsMatch, considerMaterialization, disablePrivilegeCollection, enhanceRCLForInsert, ensurePredicateList, flattenableInFromSubquery, generateNormalizationResultSet, generateResultSet, genProjectRestrict, genProjectRestrict, genProjectRestrictForReordering, getCostEstimate, getCursorTargetTable, getFromList, getNewCostEstimate, getOptimizer, getOptimizerImpl, getRCLForInsert, getReferencedTableMap, getResultColumns, getResultSetNumber, isNotExists, isOneRowResultSet, isPossibleDistinctScan, isUpdatableCursor, makeResultDescription, makeResultDescriptors, markAsCursorTargetTable, markForDistinctScan, markStatementResultSet, modifyAccessPaths, notCursorTargetTable, numDistinctAggregates, parseDefault, performMaterialization, pushOffsetFetchFirst, pushOrderByList, rejectXMLValues, renameGeneratedResultNames, replaceOrForbidDefaults, returnsAtMostOneRow, setInsertSource, setReferencedTableMap, setResultColumns, setResultToBooleanTrueNode, setTableConstructorTypes, subqueryReferencesTarget, verifySelectStarSubquery
 
Methods inherited from class org.apache.derby.impl.sql.compile.QueryTreeNode
accept, bindOffsetFetch, bindRowMultiSet, bindUserType, checkReliability, checkReliability, convertDefaultNode, createTypeDependency, debugFlush, debugPrint, formatNodeString, foundString, generateAuthorizeCheck, getBeginOffset, getClassFactory, getCompilerContext, getContextManager, getCursorInfo, getDataDictionary, getDependencyManager, getEndOffset, getExecutionFactory, getGenericConstantActionFactory, getIntProperty, getLanguageConnectionContext, getNodeFactory, getNodeType, getNullNode, getParameterTypes, getRowEstimate, getSchemaDescriptor, getSchemaDescriptor, getStatementType, getTableDescriptor, getTypeCompiler, init, init, init, init, init, init, init, init, init, init, isAtomic, isInstanceOf, isPrivilegeCollectionRequired, isSessionSchema, isSessionSchema, makeConstantAction, makeTableName, makeTableName, nodeHeader, orReliability, parseStatement, printLabel, resolveTableToSynonym, setBeginOffset, setContextManager, setEndOffset, setNodeType, setRefActionInfo, stackPrint, treePrint, treePrint, verifyClassExist
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 
Methods inherited from interface org.apache.derby.iapi.sql.compile.Optimizable
getDataDictionary, getReferencedTableMap, getResultSetNumber
 

Field Detail

rightOuterJoin

private boolean rightOuterJoin

transformed

private boolean transformed
Constructor Detail

HalfOuterJoinNode

public HalfOuterJoinNode()
Method Detail

init

public void init(java.lang.Object leftResult,
                 java.lang.Object rightResult,
                 java.lang.Object onClause,
                 java.lang.Object usingClause,
                 java.lang.Object rightOuterJoin,
                 java.lang.Object tableProperties)
          throws StandardException
Initializer for a HalfOuterJoinNode.

Overrides:
init in class QueryTreeNode
Parameters:
leftResult - The ResultSetNode on the left side of this join
rightResult - The ResultSetNode on the right side of this join
onClause - The ON clause
usingClause - The USING clause
rightOuterJoin - Whether or not this node represents a user specified right outer join
tableProperties - Properties list associated with the table
Throws:
StandardException - Thrown on error

pushOptPredicate

public boolean pushOptPredicate(OptimizablePredicate optimizablePredicate)
                         throws StandardException
Description copied from interface: Optimizable
Push an OptimizablePredicate down, if this node accepts it.

Specified by:
pushOptPredicate in interface Optimizable
Overrides:
pushOptPredicate in class JoinNode
Parameters:
optimizablePredicate - OptimizablePredicate to push down.
Returns:
Whether or not the predicate was pushed down.
Throws:
StandardException - Thrown on error
See Also:
Optimizable.pushOptPredicate(org.apache.derby.iapi.sql.compile.OptimizablePredicate)

toString

public java.lang.String toString()
Convert this object to a String. See comments in QueryTreeNode.java for how this should be done for tree printing.

Overrides:
toString in class TableOperatorNode
Returns:
This object as a String

preprocess

public ResultSetNode preprocess(int numTables,
                                GroupByList gbl,
                                FromList fromList)
                         throws StandardException
Put a ProjectRestrictNode on top of each FromTable in the FromList. ColumnReferences must continue to point to the same ResultColumn, so that ResultColumn must percolate up to the new PRN. However, that ResultColumn will point to a new expression, a VirtualColumnNode, which points to the FromTable and the ResultColumn that is the source for the ColumnReference. (The new PRN will have the original of the ResultColumnList and the ResultColumns from that list. The FromTable will get shallow copies of the ResultColumnList and its ResultColumns. ResultColumn.expression will remain at the FromTable, with the PRN getting a new VirtualColumnNode for each ResultColumn.expression.) We then project out the non-referenced columns. If there are no referenced columns, then the PRN's ResultColumnList will consist of a single ResultColumn whose expression is 1.

Overrides:
preprocess in class JoinNode
Parameters:
numTables - Number of tables in the DML Statement
gbl - The group by list, if any
fromList - The from list, if any
Returns:
The generated ProjectRestrictNode atop the original FromTable.
Throws:
StandardException - Thrown on error

pushExpressions

public void pushExpressions(PredicateList outerPredicateList)
                     throws StandardException
Push expressions down to the first ResultSetNode which can do expression evaluation and has the same referenced table map. RESOLVE - This means only pushing down single table expressions to DistinctNodes today. Once we have a better understanding of how the optimizer will work, we can push down join clauses.

Overrides:
pushExpressions in class JoinNode
Parameters:
outerPredicateList - The PredicateList from the outer RS.
Throws:
StandardException - Thrown on error

LOJ_reorderable

public boolean LOJ_reorderable(int numTables)
                        throws StandardException
This method recursively:

    OJ1  pT1T2                      OJ1  pT2T3
   /  \                             / \
  /    \                 can       /   t3
 t1    OJ2 pT2T3       reorder    /
       /  \              to      OJ2  pT1T2
      /    \                    /   \
     t2    t3                  /     \
                             t1     t2

 where pR1R2 is a null-rejecting predicate which references the schema
 of joinee R1 and R2, cf. terminology explanation in #isNullRejecting.
 

OJ1 represents this before and after the reordering.

The join predicates are assumed to be in CNF form.

Note: Present implementation limitations

Overrides:
LOJ_reorderable in class JoinNode
Parameters:
numTables - number of tables involved (needed to right size the bitmaps)
Returns:
boolean true if any reordering took place at this level or deeper so caller can know whether rebinding may be necessary
Throws:
StandardException - standard error policy

isNullRejecting

private boolean isNullRejecting(ValueNode joinClause,
                                JBitSet leftTableMap,
                                JBitSet rightTableMap)
                         throws StandardException
Tests pRiRj in the sense of Galindo-Legaria et al: Outerjoin Simplification and Reordering for Query Optimization, ACM Transactions on Database Systems, Vol. 22, No. 1, March 1997, Pages 43-74: "The set of attributes referenced by a predicate p is called the schema of p, and denoted sch(p). As a notational convention, we annotate predicates to reflect their schema. If sch(p) includes attributes of both Ri, Rj and only those relations, we can write the predicate as pRiRj. If a null-valued column is compared in a predicate that contains no OR connectives, the predicate evaluates to undefined, and the tuple is rejected. The relops satisfy this criterion.

To simplify analysis, we only accept predicates of the form:

 X relop Y [and .. and X-n relop Y-n]
 
At least one of the relops should reference both leftTableMap and rightTableMap, so that we know that sch(p) includes attributes of both Ri, Rj. I.e.

X should be a table in leftTableMap, and Y should be a table in rightTableMap.

or X should be a table in rightTableMap, and Y should be a table in leftTableMap.

Parameters:
joinClause - The join clause (i.e. predicate) we want to check
leftTableMap - a bit map representing the tables expected for the predicate (logical left)
rightTableMap - a bit map representing the tables expected for the predicate (logical right)
Returns:
true if the joinClause has at least one relop that references both leftTableMap and rightTableMap
Throws:
StandardException - standard exception policy

LOJ_bindResultColumns

public boolean LOJ_bindResultColumns(boolean anyChange)
                              throws StandardException
Throws:
StandardException

transformOuterJoins

public FromTable transformOuterJoins(ValueNode predicateTree,
                                     int numTables)
                              throws StandardException
Transform any Outer Join into an Inner Join where applicable. (Based on the existence of a null intolerant predicate on the inner table.)

Overrides:
transformOuterJoins in class JoinNode
Parameters:
predicateTree - The predicate tree for the query block
Returns:
The new tree top (OuterJoin or InnerJoin).
Throws:
StandardException - Thrown on error

adjustNumberOfRowsReturned

protected void adjustNumberOfRowsReturned(CostEstimate costEstimate)
Description copied from class: JoinNode
Some types of joins (e.g. outer joins) will return a different number of rows than is predicted by optimizeIt() in JoinNode. So, adjust this value now. This method does nothing for most join types.

Overrides:
adjustNumberOfRowsReturned in class JoinNode
See Also:
JoinNode.adjustNumberOfRowsReturned(org.apache.derby.iapi.sql.compile.CostEstimate)

generate

public void generate(ActivationClassBuilder acb,
                     MethodBuilder mb)
              throws StandardException
Generate the code for an inner join node.

Overrides:
generate in class JoinNode
Parameters:
acb - The ActivationClassBuilder for the class being built
mb - The method for the generated code to go into
Throws:
StandardException - Thrown on error

addOuterJoinArguments

protected int addOuterJoinArguments(ActivationClassBuilder acb,
                                    MethodBuilder mb)
                             throws StandardException
Generate and add any arguments specifict to outer joins. Generate the methods (and add them as parameters) for returning an empty row from 1 or more sides of an outer join, if required. Pass whether or not this was originally a right outer join.

Overrides:
addOuterJoinArguments in class JoinNode
Parameters:
acb - The ActivationClassBuilder
mb - the method the generate code is to go into return The args that have been added
Throws:
StandardException - Thrown on error

getNumJoinArguments

protected int getNumJoinArguments()
Return the number of arguments to the join result set.

Overrides:
getNumJoinArguments in class JoinNode

oneRowRightSide

protected void oneRowRightSide(ActivationClassBuilder acb,
                               MethodBuilder mb)
Overrides:
oneRowRightSide in class JoinNode

getLogicalLeftResultSet

ResultSetNode getLogicalLeftResultSet()
Return the logical left result set for this qualified join node. (For RIGHT OUTER JOIN, the left is the right and the right is the left and the JOIN is the NIOJ).

Overrides:
getLogicalLeftResultSet in class JoinNode

getLogicalRightResultSet

ResultSetNode getLogicalRightResultSet()
Return the logical right result set for this qualified join node. (For RIGHT OUTER JOIN, the left is the right and the right is the left and the JOIN is the NIOJ).

Overrides:
getLogicalRightResultSet in class JoinNode

isRightOuterJoin

public boolean isRightOuterJoin()
Return true if right outer join or false if left outer join Used to set Nullability correctly in JoinNode


LOJgetNPReferencedTables

public JBitSet LOJgetNPReferencedTables(int numTables)
                                 throws StandardException
Throws:
StandardException

LOJgetRPReferencedTables

public JBitSet LOJgetRPReferencedTables(int numTables)
                                 throws StandardException
Throws:
StandardException

Built on Thu 2012-03-29 21:53:33+0000, from revision ???

Apache Derby V10.6 Internals - Copyright © 2004,2007 The Apache Software Foundation. All Rights Reserved.