com.lucidera.lcs
Class LcsIndexOptimizer

java.lang.Object
  com.lucidera.lcs.LcsIndexOptimizer

public class LcsIndexOptimizer
extends Object

LcsIndexOptimizer optimizes the access path to use index based on cost.

Version:

$Id: //open/dev/farrago/src/com/lucidera/lcs/LcsIndexOptimizer.java#23 $

Author:

Rushan Chen

Nested Class Summary

static class	LcsIndexOptimizer.CandidateIndex
private static class	LcsIndexOptimizer.Filter2IndexMapping
class	LcsIndexOptimizer.IndexFilterTuple
static class	LcsIndexOptimizer.IndexLengthComparator
private static class	LcsIndexOptimizer.IndexPageCountComparator
private static class	LcsIndexOptimizer.MappedFilterSelectivityComparator
private static class	LcsIndexOptimizer.RowCountComparator RowCountComparator is used to sort RelNodes based on their rowcounts, provided the counts are known.
static class	LcsIndexOptimizer.SargColumnFilter
static class	LcsIndexOptimizer.SargColumnFilterSelectivityComparator

Field Summary

private Double	avgColumnLength
private Double	bestCost
private LcsIndexOptimizer.Filter2IndexMapping	bestMapping
private static int	ByteLength
private static Double	ColumnCorrelationFactor
private int	dbBlockSize
private Double	deletionIndexScanCost
private Double	estimatedBitmapBlockCount
private Double	estimatedBitmapRowCount
private static Double	IndexSearchSeletivityThreshold
private static Double	IOCostPerBlock
private Timestamp	labelTimestamp
private static Double	ResidualFilterEvalCostPerMillionRow
private LcsRowScanRel	rowScanRel
private Double	rowScanRelRowCount
private static Double	SetOpCostPerBlock
private static int	SmallTableRowCount
private static Double	SortCostConstant
private Double	tableBlockCount
private int	tableColumnCount
private Double	tableRowCount
(package private) RelStatSource	tableStats
private Map<FemLocalIndex,LcsIndexOptimizer.SargColumnFilter>	tmpIndex2LastFilterMap
private Set<LcsIndexOptimizer.SargColumnFilter>	tmpResidualFilterSet
(package private) Logger	tracer
private List<FemLocalIndex>	usableIndexes
private boolean	useCost

Constructor Summary

LcsIndexOptimizer(LcsRowScanRel rowScanRel)

Method Summary

private static LcsIndexIntersectRel	addIntersect(RelNode oldIndexAccessRel, RelOptRuleCall call, int rowScanRelPosInCall, FemLocalIndex index, RelNode keyInput, Integer[] inputKeyProj, Integer[] inputDirectiveProj, FennelRelParamId startRidParamId, FennelRelParamId rowLimitParamId, boolean requireMerge, Double indexSelectivity) Add new index access rel and intersect that with the oldIndexAccessRel.
static RelNode	addNewIndexAccessRel(RelNode oldIndexAccessRel, RelOptRuleCall call, int rowScanRelPosInCall, FemLocalIndex index, RelNode keyInput, Integer[] inputKeyProj, Integer[] inputDirectiveProj, boolean requireMerge, Double indexSelectivity) Add new index access rel using a given index to the input of the row scan rel matched by the call.
private Double	costIndexAccess(List<LcsIndexOptimizer.SargColumnFilter> pointList, List<LcsIndexOptimizer.SargColumnFilter> intervalList, LcsIndexOptimizer.Filter2IndexMapping candidateMapping) Calculate the cost of using index access and residual filtering with a row scan.
private Double	costIndexAccessWithInputRel(RelNode dimRel, List<Integer> factKeyList, List<Integer> dimKeyList, FemLocalIndex index, int matchedPos) Calculate the cost of using index access, driven by an input rel, on a row scan.
static Integer[]	findIndexOnlyProjection(LcsRowScanRel rowScan, FemLocalIndex index) Search for a projection of a bitmap index that satisfies the row scan.
private LcsIndexOptimizer.SargColumnFilter	findSargFilterForColumn(LcsRowScanRel rowScanRel, Set<LcsIndexOptimizer.SargColumnFilter> filterSet, FemAbstractColumn col) From a list of filters on distinct columns, find the one on a given column.
FemLocalIndex	findSemiJoinIndexByCost(RelNode dimRel, List<Integer> factKeyList, List<Integer> dimKeyList, List<Integer> bestFactKeyOrder) Find the index with the best cost to filter the LHS of a join that originates from a single LcsRowScanRel.
private void	getBestIndex(List<LcsIndexOptimizer.SargColumnFilter> pointList, List<LcsIndexOptimizer.SargColumnFilter> intervalList) Find the set of indexes that gives the lowest access time for the query.
static Map<CwmColumn,SargIntervalSequence>	getCol2SeqMap(LcsRowScanRel rowScan, List<SargBinding> sargBindingList) Converts a list of SargBidning to a map of column to sarg sequence.
private Double	getCombinedSelectivity(Set<LcsIndexOptimizer.SargColumnFilter> filterSet) Calculate the combined selectivity of a set of sargable filters.
private static Double	getCombinedSelectivity(Set<LcsIndexOptimizer.SargColumnFilter> filterSet, RelStatSource tabStat) Calculate the combined selectivity of a set of sargable filters.
private Map<FemLocalIndex,Integer>	getIndex2MatchedPos(List<List<LcsIndexOptimizer.SargColumnFilter>> colFilterLists) This is the algorithm that maps indexes to search key columns.
Map<FemLocalIndex,Integer>	getIndex2MatchedPosByCost(List<List<LcsIndexOptimizer.SargColumnFilter>> filterLists) Find the best filter to index mapping based on cost.
private Double	getIndexBitmapBitOpCost(int numIndexesUsed) Calculates the cost of performing bitmap operations for a bitmapped index.
private Double	getIndexBitmapCount(FemLocalIndex index, int mappedPos, LcsIndexOptimizer.SargColumnFilter lastFilter) Calculate the number of bitmaps(distinct key values) satisfying the index search keys.
private Double	getIndexBitmapScanCost(FemLocalIndex index) Calculate the cost of scanning an entire bitmap index.
private Double	getIndexBitmapScanCost(FemLocalIndex index, Double scannedBitmapCount) Calculate the cost of scanning part of a bitmap index.
private Double	getIndexBitmapSortCost(Double scannedBitmapCount) Calculate the cost of sorting the bitmap entries in an index.
static FemAbstractColumn	getIndexColumn(FemLocalIndex index, int position) Get the column at a given index key position.
private Double	getIndexSearchCost(Map<FemLocalIndex,Integer> index2MatchedPosMap, Map<FemLocalIndex,LcsIndexOptimizer.SargColumnFilter> index2LastFilterMap) Calculate the cost of an index search.
static FemLocalIndex	getIndexWithMinDiskPages(LcsRowScanRelBase rowScan) Selects from the clustered indexes on a table the one with the fewest number of pages.
private Double	getLcsTableBlockCount(LcsTable lcsTable) Calculate the total number of disk blocks used by a lcs table.
private Double	getTableScanCostWithIndexSearch(Double indexSearchSelectivity) Calculate the cost of scanning a table with index search applied.
private Double	getTableScanCostWithResidual(Set<LcsIndexOptimizer.SargColumnFilter> indexSearchFilterSet, Set<LcsIndexOptimizer.SargColumnFilter> residualFilterSet) Calculate the cost of scanning a table with residual filters applied.
static List<FemLocalIndex>	getUnclusteredIndexes(LcsRowScanRel rowScan) Get a list of all unclustered indexes on the table scanned by a LcsRowScanRel
private boolean	mapIndexToFilter(List<FemLocalIndex> usableIndexes, List<LcsIndexOptimizer.SargColumnFilter> pointList, List<LcsIndexOptimizer.SargColumnFilter> intervalList, Set<LcsIndexOptimizer.SargColumnFilter> mappedIndexSet, TreeSet<LcsIndexOptimizer.IndexFilterTuple> indexFilterSet) maps each index in the list of usable indexes to filters satisfiable by the index and populates the indexFilterSet with tuples (index, satisfiable filters).
static FennelSingleRel	newIndexRel(FennelRelImplementor relImplementor, RelOptCluster cluster, LcsTable lcsTable, FemLocalIndex index, RelNode keyInput, Integer[] inputKeyProj, Integer[] inputDirectiveProj, FennelRelParamId startRidParamId, FennelRelParamId rowLimitParamId, boolean requireMerge, Double indexSelectivity) Create a new index search rel using an given index.
private void	rebuildTreeSet(TreeSet<LcsIndexOptimizer.IndexFilterTuple> indexFilterSet, Set<LcsIndexOptimizer.SargColumnFilter> mappedFilters) recalculate effective selectivity and rebuild the tree set effective selectivity of an index may be changed if some other indexes has satisfied some of the filters

Methods inherited from class java.lang.Object

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

Field Detail

IOCostPerBlock

private static Double IOCostPerBlock

SetOpCostPerBlock

private static Double SetOpCostPerBlock

ResidualFilterEvalCostPerMillionRow

private static Double ResidualFilterEvalCostPerMillionRow

SortCostConstant

private static Double SortCostConstant

ColumnCorrelationFactor

private static Double ColumnCorrelationFactor

ByteLength

private static int ByteLength

SmallTableRowCount

private static int SmallTableRowCount

IndexSearchSeletivityThreshold

private static Double IndexSearchSeletivityThreshold

rowScanRel

private LcsRowScanRel rowScanRel

usableIndexes

private List<FemLocalIndex> usableIndexes

tableColumnCount

private int tableColumnCount

dbBlockSize

private int dbBlockSize

tableStats

RelStatSource tableStats

tableBlockCount

private Double tableBlockCount

tableRowCount

private Double tableRowCount

rowScanRelRowCount

private Double rowScanRelRowCount

deletionIndexScanCost

private Double deletionIndexScanCost

useCost

private boolean useCost

avgColumnLength

private Double avgColumnLength

estimatedBitmapBlockCount

private Double estimatedBitmapBlockCount

estimatedBitmapRowCount

private Double estimatedBitmapRowCount

tmpResidualFilterSet

private Set<LcsIndexOptimizer.SargColumnFilter> tmpResidualFilterSet

tmpIndex2LastFilterMap

private Map<FemLocalIndex,LcsIndexOptimizer.SargColumnFilter> tmpIndex2LastFilterMap

bestMapping

private LcsIndexOptimizer.Filter2IndexMapping bestMapping

bestCost

private Double bestCost

labelTimestamp

private Timestamp labelTimestamp

tracer

Logger tracer

Constructor Detail

LcsIndexOptimizer

public LcsIndexOptimizer(LcsRowScanRel rowScanRel)

Method Detail

getUnclusteredIndexes

public static List<FemLocalIndex> getUnclusteredIndexes(LcsRowScanRel rowScan)

Get a list of all unclustered indexes on the table scanned by a LcsRowScanRel

Parameters:

rowScan -

Returns:

list of all unclustered indexes

getIndexColumn

public static FemAbstractColumn getIndexColumn(FemLocalIndex index,
                                               int position)

Get the column at a given index key position.

Parameters:

index - the index whose key contains the column

position - the index key position for the column

Returns:

null if the position specified is invalid

findSargFilterForColumn

private LcsIndexOptimizer.SargColumnFilter findSargFilterForColumn(LcsRowScanRel rowScanRel,
                                                                   Set<LcsIndexOptimizer.SargColumnFilter> filterSet,
                                                                   FemAbstractColumn col)

From a list of filters on distinct columns, find the one on a given column.

Parameters:

rowScanRel -

filterSet -

col -

Returns:

the filter on the given column

findIndexOnlyProjection

public static Integer[] findIndexOnlyProjection(LcsRowScanRel rowScan,
                                                FemLocalIndex index)

Search for a projection of a bitmap index that satisfies the row scan. If such a projection exists, return the projection, with bitmap columns appended.

Parameters:

index - the index which is to be projected

Returns:

a projection on the index that satisfies the columns of the row scan and includes bitmap data, or null if a satisfying projection could not be found

getIndex2MatchedPos

private Map<FemLocalIndex,Integer> getIndex2MatchedPos(List<List<LcsIndexOptimizer.SargColumnFilter>> colFilterLists)

This is the algorithm that maps indexes to search key columns. It does so by finding the shortest (in terms of key length) index to map to the longest list of columns(in the case of composite key idnexes). The index selection is expressed using a map where all selected indexes and the matched key positions are remembered.

Parameters:

colFilterLists - two SargColumnFilter lists: the first one contains the "point" column filters, the second one contains the "interval" column filters.

Returns:

a map from selected index to its associated matched key position.

getIndex2MatchedPosByCost

public final Map<FemLocalIndex,Integer> getIndex2MatchedPosByCost(List<List<LcsIndexOptimizer.SargColumnFilter>> filterLists)

Find the best filter to index mapping based on cost. If cost information is not available, pick indexes with the longest matching keys.

Parameters:

filterLists - two lists of sarg column filters: one for point filters, and one for interval filters.

Returns:

a map which contains the indexes picked for index access path and the respective leading key postitions for each index.

getBestIndex

private void getBestIndex(List<LcsIndexOptimizer.SargColumnFilter> pointList,
                          List<LcsIndexOptimizer.SargColumnFilter> intervalList)

Find the set of indexes that gives the lowest access time for the query. This method greedily searchs for local optimum; it may end up picking a sub-optimal set of indexes.

Parameters:

pointList - list of point filters

intervalList - list of interval filters

mapIndexToFilter

private boolean mapIndexToFilter(List<FemLocalIndex> usableIndexes,
                                 List<LcsIndexOptimizer.SargColumnFilter> pointList,
                                 List<LcsIndexOptimizer.SargColumnFilter> intervalList,
                                 Set<LcsIndexOptimizer.SargColumnFilter> mappedIndexSet,
                                 TreeSet<LcsIndexOptimizer.IndexFilterTuple> indexFilterSet)

maps each index in the list of usable indexes to filters satisfiable by the index and populates the indexFilterSet with tuples (index, satisfiable filters). The set is ordered by effective selectivity of the index.

Parameters:

usableIndexes - list of indexes to be mapped

pointList - list of point filters

intervalList - list of interval filters

mappedIndexSet -

indexFilterSet - the tree set to be populated

Returns:

true if the sets of satisfiable filters are disjoint

rebuildTreeSet

private void rebuildTreeSet(TreeSet<LcsIndexOptimizer.IndexFilterTuple> indexFilterSet,
                            Set<LcsIndexOptimizer.SargColumnFilter> mappedFilters)

recalculate effective selectivity and rebuild the tree set effective selectivity of an index may be changed if some other indexes has satisfied some of the filters

Parameters:

indexFilterSet -

mappedFilters -

costIndexAccess

private Double costIndexAccess(List<LcsIndexOptimizer.SargColumnFilter> pointList,
                               List<LcsIndexOptimizer.SargColumnFilter> intervalList,
                               LcsIndexOptimizer.Filter2IndexMapping candidateMapping)

Calculate the cost of using index access and residual filtering with a row scan.

Parameters:

pointList - list of point filters

intervalList - list of interval filters

candidateMapping - the candidate mapping from filter to index

Returns:

cost of index access

costIndexAccessWithInputRel

private Double costIndexAccessWithInputRel(RelNode dimRel,
                                           List<Integer> factKeyList,
                                           List<Integer> dimKeyList,
                                           FemLocalIndex index,
                                           int matchedPos)

Calculate the cost of using index access, driven by an input rel, on a row scan.

Parameters:

dimRel - input rel that drives the index search

factKeyList - keys on which the row scan is filtered

dimKeyList - keys which the input rel produces to drive the index search

index - index to be used in the index search

matchedPos - leading key positions of this index

Returns:

the cost of scanning factRowScanRel with the proposed index.

getCol2SeqMap

public static Map<CwmColumn,SargIntervalSequence> getCol2SeqMap(LcsRowScanRel rowScan,
                                                                List<SargBinding> sargBindingList)

Converts a list of SargBidning to a map of column to sarg sequence.

Parameters:

sargBindingList - list of sarg binding.

Returns:

converted map

findSemiJoinIndexByCost

public final FemLocalIndex findSemiJoinIndexByCost(RelNode dimRel,
                                                   List<Integer> factKeyList,
                                                   List<Integer> dimKeyList,
                                                   List<Integer> bestFactKeyOrder)

Find the index with the best cost to filter the LHS of a join that originates from a single LcsRowScanRel. Typical usage is to filter the fact table joining to a dimension table.

Parameters:

dimRel - RHS of a join, e.g. scanning the dimension table.

factKeyList - LHS join key positions

dimKeyList - RHS join key positions

bestFactKeyOrder - join keys that can be filtered by the index

Returns:

the best index to filter the join LHS

getIndexSearchCost

private Double getIndexSearchCost(Map<FemLocalIndex,Integer> index2MatchedPosMap,
                                  Map<FemLocalIndex,LcsIndexOptimizer.SargColumnFilter> index2LastFilterMap)

Calculate the cost of an index search.

Parameters:

index2MatchedPosMap - map from index to searched position

index2LastFilterMap - map from index to last filter satisfied by this index.

Returns:

the cost of performing index search.

getIndexBitmapScanCost

private Double getIndexBitmapScanCost(FemLocalIndex index)

Calculate the cost of scanning an entire bitmap index.

Parameters:

index - index to be scanned.

Returns:

the cost of performing index search.

getIndexBitmapScanCost

private Double getIndexBitmapScanCost(FemLocalIndex index,
                                      Double scannedBitmapCount)

Calculate the cost of scanning part of a bitmap index.

Parameters:

index - index to be scanned.

scannedBitmapCount - number of bitmaps scanned

Returns:

the cost of performing index search.

getIndexBitmapBitOpCost

private Double getIndexBitmapBitOpCost(int numIndexesUsed)

Calculates the cost of performing bitmap operations for a bitmapped index.

Parameters:

numIndexesUsed - number of indexes used in the index access path.

Returns:

cost of AND'ing the bitmaps from difference indexes.

getIndexBitmapSortCost

private Double getIndexBitmapSortCost(Double scannedBitmapCount)

Calculate the cost of sorting the bitmap entries in an index.

Parameters:

scannedBitmapCount - number of bitmaps scaned

Returns:

cost of sorting the bitmap entries.

getIndexBitmapCount

private Double getIndexBitmapCount(FemLocalIndex index,
                                   int mappedPos,
                                   LcsIndexOptimizer.SargColumnFilter lastFilter)

Calculate the number of bitmaps(distinct key values) satisfying the index search keys.

Parameters:

index - index to be scanned.

mappedPos - key postitions mapped to this index.

lastFilter - the last filter satisfied by this index

Returns:

number of bitmaps matching the index search keys.

getLcsTableBlockCount

private Double getLcsTableBlockCount(LcsTable lcsTable)

Calculate the total number of disk blocks used by a lcs table.

Parameters:

lcsTable -

Returns:

disk blocks used o null if the clustered indexes are not analyzed.

getCombinedSelectivity

private static Double getCombinedSelectivity(Set<LcsIndexOptimizer.SargColumnFilter> filterSet,
                                             RelStatSource tabStat)

Calculate the combined selectivity of a set of sargable filters.

Parameters:

filterSet - set of filters

tabStat - stat for underlying table these filters are based on

Returns:

combined selectivity or null if selectivity stat is not available

getCombinedSelectivity

private Double getCombinedSelectivity(Set<LcsIndexOptimizer.SargColumnFilter> filterSet)

Calculate the combined selectivity of a set of sargable filters.

Parameters:

filterSet - set of filters

Returns:

combined selectivity or null if selectivity stat is not available

getTableScanCostWithResidual

private Double getTableScanCostWithResidual(Set<LcsIndexOptimizer.SargColumnFilter> indexSearchFilterSet,
                                            Set<LcsIndexOptimizer.SargColumnFilter> residualFilterSet)

Calculate the cost of scanning a table with residual filters applied.

Parameters:

indexSearchFilterSet - index search filters

residualFilterSet - residual column filters

Returns:

the cost of row scan with residuals

getTableScanCostWithIndexSearch

private Double getTableScanCostWithIndexSearch(Double indexSearchSelectivity)

Calculate the cost of scanning a table with index search applied.

Parameters:

indexSearchSelectivity -

Returns:

the cost of row scan with index search.

getIndexWithMinDiskPages

public static FemLocalIndex getIndexWithMinDiskPages(LcsRowScanRelBase rowScan)

Selects from the clustered indexes on a table the one with the fewest number of pages. If more than one has the fewest pages, pick based on the one that sorts alphabetically earliest, based on the index names.

Parameters:

rowScan - the table

Returns:

the best index

newIndexRel

public static FennelSingleRel newIndexRel(FennelRelImplementor relImplementor,
                                          RelOptCluster cluster,
                                          LcsTable lcsTable,
                                          FemLocalIndex index,
                                          RelNode keyInput,
                                          Integer[] inputKeyProj,
                                          Integer[] inputDirectiveProj,
                                          FennelRelParamId startRidParamId,
                                          FennelRelParamId rowLimitParamId,
                                          boolean requireMerge,
                                          Double indexSelectivity)

Create a new index search rel using an given index. Add merge rel if required. Merge rels are always added if search rel is driven by an input other than FennelValuesRel.

Parameters:

cluster - Cluster

relImplementor - Implementor

lcsTable - table filtered by the index access path

index - the index to search on

keyInput - input rel containing index key values to search on.

inputKeyProj - key locations from the input.

inputDirectiveProj - key directives for each key value

startRidParamId -

rowLimitParamId -

requireMerge -

indexSelectivity - the selectivity of the index scan; null if unknown

Returns:

the new index access rel created

addIntersect

private static LcsIndexIntersectRel addIntersect(RelNode oldIndexAccessRel,
                                                 RelOptRuleCall call,
                                                 int rowScanRelPosInCall,
                                                 FemLocalIndex index,
                                                 RelNode keyInput,
                                                 Integer[] inputKeyProj,
                                                 Integer[] inputDirectiveProj,
                                                 FennelRelParamId startRidParamId,
                                                 FennelRelParamId rowLimitParamId,
                                                 boolean requireMerge,
                                                 Double indexSelectivity)

Add new index access rel and intersect that with the oldIndexAccessRel. This method is only called from RelOptRule class, as it requires the the rule call as a parameter. Additionally, this rule has to match LcsRowScanRel as part of the pattern.

Parameters:

oldIndexAccessRel - existing index access rel

call - call matched by a rule

rowScanRelPosInCall - position of LcsRowScanRel in the sequence of rels matched by the rule

index - index to add to the access path

keyInput - input rel to the index search

inputKeyProj - key projection from index search input

inputDirectiveProj - directive projection from index search input

startRidParamId - parameter ID for RID skipping optimization

rowLimitParamId - parameter ID for

requireMerge - whether a LcsIndexMergeRel should be added on top of the newly created LcsIndexSearchRel. If the input to LcsIndexSearchRel is known to search to just one bitmap, then no merge is required. All other cases, for example, when the input comes from a sort, a merge is required.

indexSelectivity - the selectivity of the index being added; null if unknown

Returns:

the new index intersect rel created

addNewIndexAccessRel

public static RelNode addNewIndexAccessRel(RelNode oldIndexAccessRel,
                                           RelOptRuleCall call,
                                           int rowScanRelPosInCall,
                                           FemLocalIndex index,
                                           RelNode keyInput,
                                           Integer[] inputKeyProj,
                                           Integer[] inputDirectiveProj,
                                           boolean requireMerge,
                                           Double indexSelectivity)

Add new index access rel using a given index to the input of the row scan rel matched by the call. This method is only called from RelOptRule class, as it requires the the rule call as a parameter. Additionally, this rule has to match LcsRowScanRel as part of the pattern.

Parameters:

oldIndexAccessRel - existing index access rel

call - call matched by a rule

rowScanRelPosInCall - position of LcsRowScanRel in the sequence of rels matched by the rule

index - index to add to the access path

keyInput - input rel to the index search

inputKeyProj - key projection from index search input

inputDirectiveProj - directive projection from index search input

requireMerge - whether a LcsIndexMergeRel should be added on top of the newly created LcsIndexSearchRel. If the input to LcsIndexSearchRel is known to search to just one bitmap, then no merge is required. All other cases, for example, when the input comes from a sort, a merge is required.

indexSelectivity - selectivity of the new index being added; null if unknown

Returns:

the new index access rel created