com.lucidera.opt
Class LoptMultiJoin

java.lang.Object
  com.lucidera.opt.LoptMultiJoin

public class LoptMultiJoin
extends Object

LoptMultiJoin is a utility class used to keep track of the join factors that make up a MultiJoinRel.

Version:

$Id: //open/dev/farrago/src/com/lucidera/opt/LoptMultiJoin.java#14 $

Author:

Zelaine Fong

Nested Class Summary

private class

LoptMultiJoin.RemovableSelfJoin Utility class used to keep track of the factors in a removable self-join.

Field Summary

private List<RexNode>	allJoinFilters All join filters associated with the MultiJoinRel, decomposed into a list.
(package private) BitSet[]	factorsRefByFactor Bitmap indicating which factors each factor references in join filters that correspond to comparisons
private Map<RexNode,BitSet>	factorsRefByJoinFilter For each join filter, associates a bitmap indicating all factors referenced by the filter
(package private) int[][]	factorWeights Weights of each factor combination
(package private) RelDataTypeFactory	factory Type factory
private Map<RexNode,BitSet>	fieldsRefByJoinFilter For each join filter, associates a bitmap indicating all fields referenced by the filter
private RelNode[]	joinFactors Original inputs into the MultiJoinRel
private Map<Integer,int[]>	joinFieldRefCountsMap Map containing reference counts of the fields referenced in join conditions for each join factor.
private List<RexNode>	joinFilters Join filters associated with the MultiJoinRel, decomposed into a list.
(package private) Integer[]	joinRemovalFactors Indicates for each factor whether its join can be removed because it is the dimension table in a semijoin.
(package private) SemiJoinRel[]	joinRemovalSemiJoins The semijoins that allow the join of a dimension table to be removed
(package private) int[]	joinStart Starting RexInputRef index corresponding to each join factor
private JoinRelType[]	joinTypes If a join factor is null generating in a left or right outer join, joinTypes indicates the join type corresponding to the factor.
(package private) MultiJoinRel	multiJoin The MultiJoinRel being optimized
(package private) int[]	nFieldsInJoinFactor Number of fields in each join factor
private int	nJoinFactors Number of factors into the MultiJoinRel
private int	nTotalFields Total number of fields in the MultiJoinRel
private BitSet[]	outerJoinFactors If a join factor is null generating in a left or right outer join, the bitmap contains the non-null generating factors that the null generating factor is dependent upon
private BitSet[]	projFields Bitmap corresponding to the fields projected from each join factor, after row scan processing has completed.
(package private) Set<Integer>	removableOuterJoinFactors Set of null-generating factors whose corresponding outer join can be removed from the query plan
(package private) Map<Integer,LoptMultiJoin.RemovableSelfJoin>	removableSelfJoinPairs Map consisting of all pairs of self-joins where the self-join can be removed because the join between the identical factors is an equality join on the same set of unique keys.

Constructor Summary

LoptMultiJoin(MultiJoinRel multiJoin)

Method Summary

void	addRemovableOuterJoinFactor(int factIdx) Adds a join factor to the set of factors that can be removed because the factor is the null generating factor in an outer join, its join keys are unique, and the factor is not projected in the query
void	addRemovableSelfJoinPair(int factor1, int factor2) Adds to a map that keeps track of removable self-join pairs.
int	findRef(int rexInputRef) Determines the join factor corresponding to a RexInputRef
void	getChildFactors(LoptJoinTree joinTree, BitSet childFactors) Sets a bitmap indicating all child RelNodes in a join tree
BitSet	getFactorsRefByFactor(int factIdx)
BitSet	getFactorsRefByJoinFilter(RexNode joinFilter)
int[][]	getFactorWeights()
BitSet	getFieldsRefByJoinFilter(RexNode joinFilter)
RelNode	getJoinFactor(int factIdx)
int[]	getJoinFieldRefCounts(int factIdx)
RelDataTypeField[]	getJoinFields(LoptJoinTree left, LoptJoinTree right) Retrieves the fields corresponding to a join between a left and right tree
private BitSet	getJoinFilterFactorBitmap(RexNode joinFilter, boolean setFields) Returns a bitmap representing the factors referenced in a join filter
List<RexNode>	getJoinFilters()
Integer	getJoinRemovalFactor(int dimIdx)
SemiJoinRel	getJoinRemovalSemiJoin(int dimIdx)
int	getJoinStart(int factIdx)
RelDataTypeField[]	getMultiJoinFields()
MultiJoinRel	getMultiJoinRel()
int	getNumFieldsInJoinFactor(int factIdx)
int	getNumJoinFactors()
int	getNumTotalFields()
Integer	getOtherSelfJoinFactor(int factIdx)
RexNode	getOuterJoinCond(int factIdx)
BitSet	getOuterJoinFactors(int factIdx)
BitSet	getProjFields(int factIdx)
Integer	getRightColumnMapping(int rightFactor, int rightOffset) Determines whether there is a mapping from a column in the right factor of a self-join to a column from the left factor.
boolean	hasAllFactors(LoptJoinTree joinTree, BitSet factorsNeeded) Returns true if a join tree contains all factors required
boolean	isLeftFactorInRemovableSelfJoin(int factIdx)
boolean	isNullGenerating(int factIdx)
boolean	isRemovableOuterJoinFactor(int factIdx)
boolean	isRightFactorInRemovableSelfJoin(int factIdx)
private void	setFactorBitmap(BitSet factorRefBitmap, BitSet fieldRefBitmap) Sets the bitmap indicating which factors a filter references based on which fields it references
private void	setFactorWeight(int weight, int leftFactor, int rightFactor) Sets an individual weight if the new weight is better than the current one
void	setFactorWeights() Sets weighting for each combination of factors, depending on which join filters reference which factors.
void	setFieldBitmap(LoptJoinTree rel, BitSet fields) Sets a bitmap representing all fields corresponding to a RelNode
private void	setJoinFilterRefs() Sets bitmaps indicating which factors and fields each join filter references
void	setJoinRemovalFactor(int dimIdx, int factIdx) Indicates that a dimension factor's join can be removed because of a semijoin with a fact table.
void	setJoinRemovalSemiJoin(int dimIdx, SemiJoinRel semiJoin) Indicates the semijoin that allows the join of a dimension table to be removed
private void	setOuterJoinInfo() Extracts outer join information from the join factors, including the type of outer join and the factors that a null-generating factor is dependent upon.

Methods inherited from class java.lang.Object

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

Field Detail

multiJoin

MultiJoinRel multiJoin

The MultiJoinRel being optimized

joinFilters

private List<RexNode> joinFilters

Join filters associated with the MultiJoinRel, decomposed into a list. Excludes left/right outer join filters.

allJoinFilters

private List<RexNode> allJoinFilters

All join filters associated with the MultiJoinRel, decomposed into a list. Includes left/right outer join filters.

nJoinFactors

private int nJoinFactors

Number of factors into the MultiJoinRel

nTotalFields

private int nTotalFields

Total number of fields in the MultiJoinRel

joinFactors

private RelNode[] joinFactors

Original inputs into the MultiJoinRel

joinTypes

private JoinRelType[] joinTypes

If a join factor is null generating in a left or right outer join, joinTypes indicates the join type corresponding to the factor. Otherwise, it is set to INNER.

outerJoinFactors

private BitSet[] outerJoinFactors

If a join factor is null generating in a left or right outer join, the bitmap contains the non-null generating factors that the null generating factor is dependent upon

projFields

private BitSet[] projFields

Bitmap corresponding to the fields projected from each join factor, after row scan processing has completed. This excludes fields referenced in join conditions, unless the field appears in the final projection list.

joinFieldRefCountsMap

private Map<Integer,int[]> joinFieldRefCountsMap

Map containing reference counts of the fields referenced in join conditions for each join factor. If a field is only required for a semijoin, then it is removed from the reference count. (Hence the need for reference counts instead of simply a bitmap.) The map is indexed by the factor number.

factorsRefByJoinFilter

private Map<RexNode,BitSet> factorsRefByJoinFilter

For each join filter, associates a bitmap indicating all factors referenced by the filter

fieldsRefByJoinFilter

private Map<RexNode,BitSet> fieldsRefByJoinFilter

For each join filter, associates a bitmap indicating all fields referenced by the filter

joinStart

int[] joinStart

Starting RexInputRef index corresponding to each join factor

nFieldsInJoinFactor

int[] nFieldsInJoinFactor

Number of fields in each join factor

factorsRefByFactor

BitSet[] factorsRefByFactor

Bitmap indicating which factors each factor references in join filters that correspond to comparisons

factorWeights

int[][] factorWeights

Weights of each factor combination

factory

RelDataTypeFactory factory

Type factory

joinRemovalFactors

Integer[] joinRemovalFactors

Indicates for each factor whether its join can be removed because it is the dimension table in a semijoin. If it can be, the entry indicates the factor id of the fact table (corresponding to the dimension table) in the semijoin that allows the factor to be removed. If the factor cannot be removed, the entry corresponding to the factor is null.

joinRemovalSemiJoins

SemiJoinRel[] joinRemovalSemiJoins

The semijoins that allow the join of a dimension table to be removed

removableOuterJoinFactors

Set<Integer> removableOuterJoinFactors

Set of null-generating factors whose corresponding outer join can be removed from the query plan

removableSelfJoinPairs

Map<Integer,LoptMultiJoin.RemovableSelfJoin> removableSelfJoinPairs

Map consisting of all pairs of self-joins where the self-join can be removed because the join between the identical factors is an equality join on the same set of unique keys. The map is keyed by either factor in the self join.

Constructor Detail

LoptMultiJoin

public LoptMultiJoin(MultiJoinRel multiJoin)

Method Detail

getMultiJoinRel

public MultiJoinRel getMultiJoinRel()

Returns:

the MultiJoinRel corresponding to this multijoin

getNumJoinFactors

public int getNumJoinFactors()

Returns:

number of factors in this multijoin

getJoinFactor

public RelNode getJoinFactor(int factIdx)

Parameters:

factIdx - factor to be returned

Returns:

factor corresponding to the factor index passed in

getNumTotalFields

public int getNumTotalFields()

Returns:

total number of fields in the multijoin

getNumFieldsInJoinFactor

public int getNumFieldsInJoinFactor(int factIdx)

Parameters:

factIdx - desired factor

Returns:

number of fields in the specified factor

getJoinFilters

public List<RexNode> getJoinFilters()

Returns:

all non-outer join filters in this multijoin

getFactorsRefByJoinFilter

public BitSet getFactorsRefByJoinFilter(RexNode joinFilter)

Parameters:

joinFilter - filter for which information will be returned

Returns:

bitmap corresponding to the factors referenced within the specified join filter

getMultiJoinFields

public RelDataTypeField[] getMultiJoinFields()

Returns:

array of fields contained within the multijoin

getFieldsRefByJoinFilter

public BitSet getFieldsRefByJoinFilter(RexNode joinFilter)

Parameters:

joinFilter - the filter for which information will be returned

Returns:

bitmap corresponding to the fields referenced by a join filter

getFactorWeights

public int[][] getFactorWeights()

Returns:

weights of the different factors relative to one another

getFactorsRefByFactor

public BitSet getFactorsRefByFactor(int factIdx)

Parameters:

factIdx - factor for which information will be returned

Returns:

bitmap corresponding to the factors referenced by the specified factor in the various join filters that correspond to comparisons

getJoinStart

public int getJoinStart(int factIdx)

Parameters:

factIdx - factor for which information will be returned

Returns:

starting offset within the multijoin for the specified factor

isNullGenerating

public boolean isNullGenerating(int factIdx)

Parameters:

factIdx - factor for which information will be returned

Returns:

whether or not the factor corresponds to a null-generating factor in a left or right outer join

getOuterJoinFactors

public BitSet getOuterJoinFactors(int factIdx)

Parameters:

factIdx - factor for which information will be returned

Returns:

bitmap containing the factors that a null generating factor is dependent upon, if the factor is null generating in a left or right outer join; otherwise null is returned

getOuterJoinCond

public RexNode getOuterJoinCond(int factIdx)

Parameters:

factIdx - factor for which information will be returned

Returns:

outer join conditions associated with the specified null generating factor

getProjFields

public BitSet getProjFields(int factIdx)

Parameters:

factIdx - factor for which information will be returned

Returns:

bitmap containing the fields that are projected from a factor

getJoinFieldRefCounts

public int[] getJoinFieldRefCounts(int factIdx)

Parameters:

factIdx - factor for which information will be returned

Returns:

the join field reference counts for a factor

getJoinRemovalFactor

public Integer getJoinRemovalFactor(int dimIdx)

Parameters:

dimIdx - the dimension factor for which information will be returned

Returns:

the factor id of the fact table corresponding to a dimension table in a semijoin, in the case where the join with the dimension table can be removed

getJoinRemovalSemiJoin

public SemiJoinRel getJoinRemovalSemiJoin(int dimIdx)

Parameters:

dimIdx - the dimension factor for which information will be returned

Returns:

the semijoin that allows the join of a dimension table to be removed

setJoinRemovalFactor

public void setJoinRemovalFactor(int dimIdx,
                                 int factIdx)

Indicates that a dimension factor's join can be removed because of a semijoin with a fact table.

Parameters:

dimIdx - id of the dimension factor

factIdx - id of the fact factor

setJoinRemovalSemiJoin

public void setJoinRemovalSemiJoin(int dimIdx,
                                   SemiJoinRel semiJoin)

Indicates the semijoin that allows the join of a dimension table to be removed

Parameters:

dimIdx - id of the dimension factor

semiJoin - the semijoin

setOuterJoinInfo

private void setOuterJoinInfo()

Extracts outer join information from the join factors, including the type of outer join and the factors that a null-generating factor is dependent upon.

getJoinFilterFactorBitmap

private BitSet getJoinFilterFactorBitmap(RexNode joinFilter,
                                         boolean setFields)

Returns a bitmap representing the factors referenced in a join filter

Parameters:

joinFilter - the join filter

setFields - if true, add the fields referenced by the join filter into a map

Returns:

the bitmap containing the factor references

setJoinFilterRefs

private void setJoinFilterRefs()

Sets bitmaps indicating which factors and fields each join filter references

setFactorBitmap

private void setFactorBitmap(BitSet factorRefBitmap,
                             BitSet fieldRefBitmap)

Sets the bitmap indicating which factors a filter references based on which fields it references

Parameters:

factorRefBitmap - bitmap representing factors referenced that will be set by this method

fieldRefBitmap - bitmap representing fields referenced

findRef

public int findRef(int rexInputRef)

Determines the join factor corresponding to a RexInputRef

Parameters:

rexInputRef - rexInputRef index

Returns:

index corresponding to join factor

setFactorWeights

public void setFactorWeights()

Sets weighting for each combination of factors, depending on which join filters reference which factors. Greater weight is given to equality conditions. Also, sets bitmaps indicating which factors are referenced by each factor within join filters that are comparisons.

setFactorWeight

private void setFactorWeight(int weight,
                             int leftFactor,
                             int rightFactor)

Sets an individual weight if the new weight is better than the current one

Parameters:

weight - weight to be set

leftFactor - index of left factor

rightFactor - index of right factor

hasAllFactors

public boolean hasAllFactors(LoptJoinTree joinTree,
                             BitSet factorsNeeded)

Returns true if a join tree contains all factors required

Parameters:

joinTree - join tree to be examined

factorsNeeded - bitmap of factors required

Returns:

true if join tree contains all required factors

setFieldBitmap

public void setFieldBitmap(LoptJoinTree rel,
                           BitSet fields)

Sets a bitmap representing all fields corresponding to a RelNode

Parameters:

rel - relnode for which fields will be set

fields - bitmap containing set bits for each field in a RelNode

getChildFactors

public void getChildFactors(LoptJoinTree joinTree,
                            BitSet childFactors)

Sets a bitmap indicating all child RelNodes in a join tree

Parameters:

joinTree - join tree to be examined

childFactors - bitmap to be set

getJoinFields

public RelDataTypeField[] getJoinFields(LoptJoinTree left,
                                        LoptJoinTree right)

Retrieves the fields corresponding to a join between a left and right tree

Parameters:

left - left hand side of the join

right - right hand side of the join

Returns:

fields of the join

addRemovableOuterJoinFactor

public void addRemovableOuterJoinFactor(int factIdx)

Adds a join factor to the set of factors that can be removed because the factor is the null generating factor in an outer join, its join keys are unique, and the factor is not projected in the query

Parameters:

factIdx - join factor

isRemovableOuterJoinFactor

public boolean isRemovableOuterJoinFactor(int factIdx)

Parameters:

factIdx - factor in question

Returns:

true if the factor corresponds to the null generating factor in an outer join that can be removed

addRemovableSelfJoinPair

public void addRemovableSelfJoinPair(int factor1,
                                     int factor2)

Adds to a map that keeps track of removable self-join pairs.

Parameters:

factor1 - one of the factors in the self-join

factor2 - the second factor in the self-join

getOtherSelfJoinFactor

public Integer getOtherSelfJoinFactor(int factIdx)

isLeftFactorInRemovableSelfJoin

public boolean isLeftFactorInRemovableSelfJoin(int factIdx)

Parameters:

factIdx - factor in a self-join

Returns:

true if the factor is the left factor in a self-join

isRightFactorInRemovableSelfJoin

public boolean isRightFactorInRemovableSelfJoin(int factIdx)

Parameters:

factIdx - factor in a self-join

Returns:

true if the factor is the right factor in a self-join

getRightColumnMapping

public Integer getRightColumnMapping(int rightFactor,
                                     int rightOffset)

Determines whether there is a mapping from a column in the right factor of a self-join to a column from the left factor. Assumes that the right factor is a part of a self-join.

Parameters:

rightFactor - the index of the right factor

rightOffset - the column offset of the right factor

Returns:

the offset of the corresponding column in the left factor, if such a column mapping exists; otherwise, null is returned