net.sf.farrago.fennel.rel
Class FennelNestedLoopJoinRule

java.lang.Object
  org.eigenbase.relopt.RelOptRule
      net.sf.farrago.fennel.rel.FennelNestedLoopJoinRule

public class FennelNestedLoopJoinRule
extends RelOptRule

FennelNestedLoopJoinRule is a rule for converting a JoinRel with a join condition into a FennelNestedLoopJoinRel. The nested loop join is executed by creating a temporary index on the right join input and using join keys from the left input to do lookups against that index.

Any sargable join predicates that aren't part of the index lookup are processed by a FennelReshapeRel. And then finally, any remaining join predicates are processed by a Calc node.

Version:

$Id: //open/dev/farrago/src/net/sf/farrago/fennel/rel/FennelNestedLoopJoinRule.java#3 $

Author:

Zelaine Fong

Field Summary

static FennelNestedLoopJoinRule

instance

Fields inherited from class org.eigenbase.relopt.RelOptRule

ANY, description, operands

Constructor Summary

private

FennelNestedLoopJoinRule() Creates a FennelNestedLoopJoinRule.

Method Summary

private RelNode	convertInput(RelTraitSet origTraits, RelNode inputRel) Converts an input so its traits include FENNEL_EXEC_CONVENTION
private void	createJoinKeyParameters(FennelRelImplementor implementor, List<Integer> joinKeys, Map<Integer,FennelRelParamId> joinKeyParamMap) Creates a new dynamic parameter for each new join key encountered
private RelNode	createNestedLoopRel(JoinRel origJoinRel, RelNode leftRel, RelNode rightRel, boolean swapped, List<Integer> outputProj, JoinRelType joinType, List<Integer> indexCols, List<Integer> indexOperands, CompOperatorEnum indexOp, List<Integer> filterCol, List<Integer> filterOperand, CompOperatorEnum filterOp, RexNode residualCondition) Creates a nested loop join tree with the appropriate inputs.
private FennelReshapeRel	createReshapeRel(RelNode leftRel, RelNode reshapeInput, Map<Integer,FennelRelParamId> joinKeyParamMap, List<Integer> filterCols, List<Integer> filterOperands, CompOperatorEnum filterOp, List<Integer> residualRefs, RexNode residualCondition, Map<Integer,Integer> residualRefMap) Creates a FennelReshapeRel for applying simple join filters that can't be applied as part of the temp index lookup
private RelNode	createResidualFilter(RelDataTypeField[] joinFields, int nLeftFields, RelNode filterInput, RexNode residualCondition, RelNode rightRel, Map<Integer,Integer> residualRefMap) Creates RelNodes to apply remaining filters
private RelNode	createSecondInput(RelNode leftRel, RelNode rightRel, List<Integer> indexCols, List<Integer> indexOperands, CompOperatorEnum indexOp, Map<Integer,FennelRelParamId> joinKeyParamMap, FennelRelParamId rootPageIdParamId, List<Integer> filterCol, List<Integer> filterOperand, CompOperatorEnum filterOp, List<Integer> residualRefs, RexNode residualCondition) Creates the second input into the nested loop join tree that processes the RHS input.
private FennelTempIdxSearchRel	createTempIdxLookup(RelNode rightRel, List<Integer> indexCols, List<Integer> indexOperands, CompOperatorEnum indexOp, Map<Integer,FennelRelParamId> joinKeyParamMap, FennelRelParamId rootPageIdParamId) Creates a temporary index lookup RelNode
private RelNode	createThirdInput(RelNode rightRel, List<Integer> indexCols, FennelRelParamId rootPageIdParamId) Creates the third input into the nested loop join, which builds the temporary index on the right join input
private void	findLeftInputRefs(RexNode residualCondition, int nLeftFields, List<Integer> leftInputRefs) Locates all references to the left input in an expression representing the portion of the join condition that must be processed by a Calc node
CallingConvention	getOutConvention() Returns the calling convention of the result of firing this rule, null if not known.
private RexNode	getPredicates(RelNode[] joinInputs, RexNode joinCondition, List<Integer> indexCols, List<Integer> indexOperands, List<CompOperatorEnum> indexOp, List<Integer> filterCol, List<Integer> filterOperand, List<CompOperatorEnum> filterOp, List<Integer> outputProj) Locates from the join condition all equi-join predicates and a single range predicate for use with a temporary index and then if possible, an additional range predicate for a FennelReshapeRel
private void	mapSqlOpToCompOp(List<SqlOperator> sqlOpList, List<CompOperatorEnum> compOpList)
void	onMatch(RelOptRuleCall call) Receives notification about a rule match.

Methods inherited from class org.eigenbase.relopt.RelOptRule

convert, equals, equals, getOperand, getOperands, getOutTrait, hashCode, matches, mergeTraitsAndConvert, mergeTraitsAndConvert, toString

Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, wait, wait, wait

Field Detail

instance

public static final FennelNestedLoopJoinRule instance

Constructor Detail

FennelNestedLoopJoinRule

private FennelNestedLoopJoinRule()

Creates a FennelNestedLoopJoinRule.

Method Detail

getOutConvention

public CallingConvention getOutConvention()

Description copied from class: RelOptRule

Returns the calling convention of the result of firing this rule, null if not known.

Overrides:

getOutConvention in class RelOptRule

onMatch

public void onMatch(RelOptRuleCall call)

Description copied from class: RelOptRule

Receives notification about a rule match. At the time that this method is called, call.rels holds the set of relational expressions which match the operands to the rule; call.rels[0] is the root expression.

Typically a rule would check that the nodes are valid matches, creates a new expression, then calls back RelOptRuleCall.transformTo(org.eigenbase.rel.RelNode) to register the expression.

Specified by:

onMatch in class RelOptRule

Parameters:

call - Rule call

See Also:

RelOptRule.matches(RelOptRuleCall)

createNestedLoopRel

private RelNode createNestedLoopRel(JoinRel origJoinRel,
                                    RelNode leftRel,
                                    RelNode rightRel,
                                    boolean swapped,
                                    List<Integer> outputProj,
                                    JoinRelType joinType,
                                    List<Integer> indexCols,
                                    List<Integer> indexOperands,
                                    CompOperatorEnum indexOp,
                                    List<Integer> filterCol,
                                    List<Integer> filterOperand,
                                    CompOperatorEnum filterOp,
                                    RexNode residualCondition)

Creates a nested loop join tree with the appropriate inputs.

In the new tree, the first input is the left join input. The left join input is assumed to have been casted, as needed, to match the right join input.

The right input does all the necessary lookups and filtering on the right input by reading dynamic parameters corresponding to the left input.

An optional third input creates the temporary index used in join lookups if a temporary index is to be used

Parameters:

origJoinRel - original join tree

leftRel - left input into the new join

rightRel - right input into the new join

swapped - true if the original inputs were swapped

outputProj - required projection of join result (post-swap, if inputs have been swapped)

joinType - join type

indexCols - list of column offsets from the RHS input that are to be indexed

indexOperands - list of column offsets from the LHS input that will be used as index lookup keys

indexOp - the operator to be used in the index lookup

filterCol - the column offset from the RHS input that can be applied in FennelReshapeRel

filterOperand - the LHS input that filterCol is compared against

filterOp - comparison operator that will be applied in FennelReshapeRel

residualCondition - remaining filter that must be applied in a Calc node

Returns:

created nested loop join tree

getPredicates

private RexNode getPredicates(RelNode[] joinInputs,
                              RexNode joinCondition,
                              List<Integer> indexCols,
                              List<Integer> indexOperands,
                              List<CompOperatorEnum> indexOp,
                              List<Integer> filterCol,
                              List<Integer> filterOperand,
                              List<CompOperatorEnum> filterOp,
                              List<Integer> outputProj)

Locates from the join condition all equi-join predicates and a single range predicate for use with a temporary index and then if possible, an additional range predicate for a FennelReshapeRel

Parameters:

joinInputs - join inputs

joinCondition - the join condition

indexCols - returns list of column offsets from the right join input that are to be indexed

indexOperands - returns list of column offsets from the left join input that will be used as index lookup keys

indexOp - returns the operator to be used in the index lookup

filterCol - returns the column offset corresponding to RHS input that can be filtered in FennelReshapeRel

filterOperand - returns the column offset corresponding to LHS input that filterCol is compared against

filterOp - returns the comparison operator that will be applied in FennelReshapeRel

Returns:

excess predicates that cannot be processed by the index or FennelReshapeRel

mapSqlOpToCompOp

private void mapSqlOpToCompOp(List<SqlOperator> sqlOpList,
                              List<CompOperatorEnum> compOpList)

convertInput

private RelNode convertInput(RelTraitSet origTraits,
                             RelNode inputRel)

Converts an input so its traits include FENNEL_EXEC_CONVENTION

Parameters:

origTraits - traits of the original input

inputRel - the input

Returns:

a new RelNode with the merged traits

createJoinKeyParameters

private void createJoinKeyParameters(FennelRelImplementor implementor,
                                     List<Integer> joinKeys,
                                     Map<Integer,FennelRelParamId> joinKeyParamMap)

Creates a new dynamic parameter for each new join key encountered

Parameters:

implementor - FennelRelImplementor

joinKeys - list of join keys for which we want to create dynamic parameters; if a dynamic parameter has already been created for a key, don't create another one

joinKeyParamMap - mapping from join keys to dynamic parameters; used to keep track of which keys already have corresponding dynamic parameters

findLeftInputRefs

private void findLeftInputRefs(RexNode residualCondition,
                               int nLeftFields,
                               List<Integer> leftInputRefs)

Locates all references to the left input in an expression representing the portion of the join condition that must be processed by a Calc node

Parameters:

residualCondition - remaining join condition to be processed by Calc node

nLeftFields - number of fields in the left join input

leftInputRefs - list of column offsets corresponding to left input references

createSecondInput

private RelNode createSecondInput(RelNode leftRel,
                                  RelNode rightRel,
                                  List<Integer> indexCols,
                                  List<Integer> indexOperands,
                                  CompOperatorEnum indexOp,
                                  Map<Integer,FennelRelParamId> joinKeyParamMap,
                                  FennelRelParamId rootPageIdParamId,
                                  List<Integer> filterCol,
                                  List<Integer> filterOperand,
                                  CompOperatorEnum filterOp,
                                  List<Integer> residualRefs,
                                  RexNode residualCondition)

Creates the second input into the nested loop join tree that processes the RHS input. If a temporary index is used in the join lookup, create an index lookup RelNode. The output from either that (or the RHS input, if no temp index lookup is required) is then optionally fed into a FennelReshapeRel and/or a Calc node for additional join filtering.

Parameters:

leftRel - left input into the new join

rightRel - right input into the new join

indexCols - list of column offsets from the RHS input that are to be indexed

indexOperands - list of column offsets from the LHS input that will be used as index lookup keys

indexOp - the operator to be used in the index lookup

joinKeyParamMap - mapping from LHS inputs to dynamic parameters

rootPageIdParamId - dynamic parameter corresponding to the rootPageId of the temp index

filterCol - the column offset from the RHS input that can be applied in FennelReshapeRel

filterOperand - the LHS input that filterCol is compared against

filterOp - comparison operator that will be applied in FennelReshapeRel

residualRefs - LHS inputs that must be processed in the Calc node

residualCondition - remaining filter that must be applied in a Calc node

Returns:

RelNode tree corresponding to the nested loop join's second input or null if traits couldn't be converted

createTempIdxLookup

private FennelTempIdxSearchRel createTempIdxLookup(RelNode rightRel,
                                                   List<Integer> indexCols,
                                                   List<Integer> indexOperands,
                                                   CompOperatorEnum indexOp,
                                                   Map<Integer,FennelRelParamId> joinKeyParamMap,
                                                   FennelRelParamId rootPageIdParamId)

Creates a temporary index lookup RelNode

Parameters:

rightRel - right input into the new join

indexCols - list of column offsets from the RHS input that are to be indexed

indexOperands - list of column offsets from the LHS input that will be used as index lookup keys

indexOp - the operator to be used in the index lookup

joinKeyParamMap - mapping from LHS inputs to dynamic parameters

rootPageIdParamId - dynamic parameter corresponding to the rootPageId of the temp index

Returns:

temporary index lookup RelNode

createReshapeRel

private FennelReshapeRel createReshapeRel(RelNode leftRel,
                                          RelNode reshapeInput,
                                          Map<Integer,FennelRelParamId> joinKeyParamMap,
                                          List<Integer> filterCols,
                                          List<Integer> filterOperands,
                                          CompOperatorEnum filterOp,
                                          List<Integer> residualRefs,
                                          RexNode residualCondition,
                                          Map<Integer,Integer> residualRefMap)

Creates a FennelReshapeRel for applying simple join filters that can't be applied as part of the temp index lookup

Parameters:

leftRel - left join input

reshapeInput - input into FennelReshapeRel

joinKeyParamMap - mapping from LHS inputs to dynamic parameters

filterCols - the column offset from the RHS input that can be applied in FennelReshapeRel

filterOperands - the LHS input that filterCol is compared against

filterOp - comparison operator that will be applied in FennelReshapeRel

residualRefs - LHS inputs that must be processed in Calc node

residualCondition - remaining filter that must be applied in a Calc node

residualRefMap - map used to keep track of where each residual reference will appear in the output for the ReshapeRel; the map is populated within this method

Returns:

FennelReshapeRel

createResidualFilter

private RelNode createResidualFilter(RelDataTypeField[] joinFields,
                                     int nLeftFields,
                                     RelNode filterInput,
                                     RexNode residualCondition,
                                     RelNode rightRel,
                                     Map<Integer,Integer> residualRefMap)

Creates RelNodes to apply remaining filters

Parameters:

joinFields - fields from join of the left and right inputs

nLeftFields - number of fields in the left input

filterInput - input to be filtered

residualCondition - filter to be applied

rightRel - right join input

residualRefMap - map used to keep track of where each residual reference will appear in the output for the ReshapeRel

Returns:

filtering RelNodes

createThirdInput

private RelNode createThirdInput(RelNode rightRel,
                                 List<Integer> indexCols,
                                 FennelRelParamId rootPageIdParamId)

Creates the third input into the nested loop join, which builds the temporary index on the right join input

Parameters:

rightRel - right join input

indexCols - columns to be indexed

rootPageIdParamId - dynamic parameter corresponding to the root of the temporary index

Returns:

RelNodes corresponding to the third input