| package edu.uci.ics.asterix.optimizer.rules.am; |
| |
| import java.util.ArrayList; |
| import java.util.BitSet; |
| import java.util.HashSet; |
| import java.util.Iterator; |
| import java.util.List; |
| import java.util.Set; |
| |
| import org.apache.commons.lang3.mutable.Mutable; |
| import org.apache.commons.lang3.mutable.MutableObject; |
| |
| import edu.uci.ics.asterix.common.config.DatasetConfig.IndexType; |
| import edu.uci.ics.asterix.metadata.entities.Dataset; |
| import edu.uci.ics.asterix.metadata.entities.Index; |
| import edu.uci.ics.asterix.om.functions.AsterixBuiltinFunctions; |
| import edu.uci.ics.asterix.om.types.ARecordType; |
| import edu.uci.ics.hyracks.algebricks.common.exceptions.AlgebricksException; |
| import edu.uci.ics.hyracks.algebricks.core.algebra.base.ILogicalExpression; |
| import edu.uci.ics.hyracks.algebricks.core.algebra.base.ILogicalOperator; |
| import edu.uci.ics.hyracks.algebricks.core.algebra.base.IOptimizationContext; |
| import edu.uci.ics.hyracks.algebricks.core.algebra.base.LogicalExpressionTag; |
| import edu.uci.ics.hyracks.algebricks.core.algebra.base.LogicalVariable; |
| import edu.uci.ics.hyracks.algebricks.core.algebra.expressions.AbstractFunctionCallExpression; |
| import edu.uci.ics.hyracks.algebricks.core.algebra.expressions.IndexedNLJoinExpressionAnnotation; |
| import edu.uci.ics.hyracks.algebricks.core.algebra.expressions.ScalarFunctionCallExpression; |
| import edu.uci.ics.hyracks.algebricks.core.algebra.expressions.VariableReferenceExpression; |
| import edu.uci.ics.hyracks.algebricks.core.algebra.functions.AlgebricksBuiltinFunctions; |
| import edu.uci.ics.hyracks.algebricks.core.algebra.functions.AlgebricksBuiltinFunctions.ComparisonKind; |
| import edu.uci.ics.hyracks.algebricks.core.algebra.functions.FunctionIdentifier; |
| import edu.uci.ics.hyracks.algebricks.core.algebra.functions.IFunctionInfo; |
| import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.AbstractBinaryJoinOperator; |
| import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.AbstractLogicalOperator; |
| import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.AbstractLogicalOperator.ExecutionMode; |
| import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.AssignOperator; |
| import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.DataSourceScanOperator; |
| import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.SelectOperator; |
| import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.UnnestMapOperator; |
| |
| /** |
| * Class for helping rewrite rules to choose and apply BTree indexes. |
| */ |
| public class BTreeAccessMethod implements IAccessMethod { |
| |
| // Describes whether a search predicate is an open/closed interval. |
| private enum LimitType { |
| LOW_INCLUSIVE, |
| LOW_EXCLUSIVE, |
| HIGH_INCLUSIVE, |
| HIGH_EXCLUSIVE, |
| EQUAL |
| } |
| |
| // TODO: There is some redundancy here, since these are listed in AlgebricksBuiltinFunctions as well. |
| private static List<FunctionIdentifier> funcIdents = new ArrayList<FunctionIdentifier>(); |
| static { |
| funcIdents.add(AlgebricksBuiltinFunctions.EQ); |
| funcIdents.add(AlgebricksBuiltinFunctions.LE); |
| funcIdents.add(AlgebricksBuiltinFunctions.GE); |
| funcIdents.add(AlgebricksBuiltinFunctions.LT); |
| funcIdents.add(AlgebricksBuiltinFunctions.GT); |
| } |
| |
| public static BTreeAccessMethod INSTANCE = new BTreeAccessMethod(); |
| |
| @Override |
| public List<FunctionIdentifier> getOptimizableFunctions() { |
| return funcIdents; |
| } |
| |
| @Override |
| public boolean analyzeFuncExprArgs(AbstractFunctionCallExpression funcExpr, List<AssignOperator> assigns, |
| AccessMethodAnalysisContext analysisCtx) { |
| boolean matches = AccessMethodUtils.analyzeFuncExprArgsForOneConstAndVar(funcExpr, analysisCtx); |
| if (!matches) { |
| matches = AccessMethodUtils.analyzeFuncExprArgsForTwoVars(funcExpr, analysisCtx); |
| } |
| return matches; |
| } |
| |
| @Override |
| public boolean matchAllIndexExprs() { |
| return true; |
| } |
| |
| @Override |
| public boolean matchPrefixIndexExprs() { |
| // TODO: The BTree can support prefix searches. Enable this later and add tests. |
| return false; |
| } |
| |
| @Override |
| public boolean applySelectPlanTransformation(Mutable<ILogicalOperator> selectRef, |
| OptimizableOperatorSubTree subTree, Index chosenIndex, AccessMethodAnalysisContext analysisCtx, |
| IOptimizationContext context) throws AlgebricksException { |
| SelectOperator select = (SelectOperator) selectRef.getValue(); |
| Mutable<ILogicalExpression> conditionRef = select.getCondition(); |
| ILogicalOperator primaryIndexUnnestOp = createSecondaryToPrimaryPlan(selectRef, conditionRef, subTree, null, |
| chosenIndex, analysisCtx, false, false, context); |
| if (primaryIndexUnnestOp == null) { |
| return false; |
| } |
| Mutable<ILogicalOperator> assignRef = (subTree.assignRefs.isEmpty()) ? null : subTree.assignRefs.get(0); |
| AssignOperator assign = null; |
| if (assignRef != null) { |
| assign = (AssignOperator) assignRef.getValue(); |
| } |
| // Generate new select using the new condition. |
| if (conditionRef.getValue() != null) { |
| select.getInputs().clear(); |
| if (assign != null) { |
| subTree.dataSourceScanRef.setValue(primaryIndexUnnestOp); |
| select.getInputs().add(new MutableObject<ILogicalOperator>(assign)); |
| } else { |
| select.getInputs().add(new MutableObject<ILogicalOperator>(primaryIndexUnnestOp)); |
| } |
| } else { |
| ((AbstractLogicalOperator) primaryIndexUnnestOp).setExecutionMode(ExecutionMode.PARTITIONED); |
| if (assign != null) { |
| subTree.dataSourceScanRef.setValue(primaryIndexUnnestOp); |
| selectRef.setValue(assign); |
| } else { |
| selectRef.setValue(primaryIndexUnnestOp); |
| } |
| } |
| return true; |
| } |
| |
| @Override |
| public boolean applyJoinPlanTransformation(Mutable<ILogicalOperator> joinRef, |
| OptimizableOperatorSubTree leftSubTree, OptimizableOperatorSubTree rightSubTree, Index chosenIndex, |
| AccessMethodAnalysisContext analysisCtx, IOptimizationContext context) throws AlgebricksException { |
| AbstractBinaryJoinOperator joinOp = (AbstractBinaryJoinOperator) joinRef.getValue(); |
| Mutable<ILogicalExpression> conditionRef = joinOp.getCondition(); |
| // Determine if the index is applicable on the left or right side (if both, we arbitrarily prefer the left side). |
| Dataset dataset = analysisCtx.indexDatasetMap.get(chosenIndex); |
| // Determine probe and index subtrees based on chosen index. |
| OptimizableOperatorSubTree indexSubTree = null; |
| OptimizableOperatorSubTree probeSubTree = null; |
| if (leftSubTree.dataset != null && dataset.getDatasetName().equals(leftSubTree.dataset.getDatasetName())) { |
| indexSubTree = leftSubTree; |
| probeSubTree = rightSubTree; |
| } else if (rightSubTree.dataset != null |
| && dataset.getDatasetName().equals(rightSubTree.dataset.getDatasetName())) { |
| indexSubTree = rightSubTree; |
| probeSubTree = leftSubTree; |
| } |
| ILogicalOperator primaryIndexUnnestOp = createSecondaryToPrimaryPlan(joinRef, conditionRef, indexSubTree, |
| probeSubTree, chosenIndex, analysisCtx, true, true, context); |
| if (primaryIndexUnnestOp == null) { |
| return false; |
| } |
| // If there are conditions left, add a new select operator on top. |
| indexSubTree.dataSourceScanRef.setValue(primaryIndexUnnestOp); |
| if (conditionRef.getValue() != null) { |
| SelectOperator topSelect = new SelectOperator(conditionRef); |
| topSelect.getInputs().add(indexSubTree.rootRef); |
| topSelect.setExecutionMode(ExecutionMode.LOCAL); |
| context.computeAndSetTypeEnvironmentForOperator(topSelect); |
| // Replace the original join with the new subtree rooted at the select op. |
| joinRef.setValue(topSelect); |
| } else { |
| joinRef.setValue(indexSubTree.rootRef.getValue()); |
| } |
| return true; |
| } |
| |
| private ILogicalOperator createSecondaryToPrimaryPlan(Mutable<ILogicalOperator> topOpRef, |
| Mutable<ILogicalExpression> conditionRef, OptimizableOperatorSubTree indexSubTree, |
| OptimizableOperatorSubTree probeSubTree, Index chosenIndex, AccessMethodAnalysisContext analysisCtx, |
| boolean retainInput, boolean requiresBroadcast, IOptimizationContext context) throws AlgebricksException { |
| Dataset dataset = indexSubTree.dataset; |
| ARecordType recordType = indexSubTree.recordType; |
| DataSourceScanOperator dataSourceScan = indexSubTree.dataSourceScan; |
| int numSecondaryKeys = chosenIndex.getKeyFieldNames().size(); |
| |
| // Info on high and low keys for the BTree search predicate. |
| ILogicalExpression[] lowKeyExprs = new ILogicalExpression[numSecondaryKeys]; |
| ILogicalExpression[] highKeyExprs = new ILogicalExpression[numSecondaryKeys]; |
| LimitType[] lowKeyLimits = new LimitType[numSecondaryKeys]; |
| LimitType[] highKeyLimits = new LimitType[numSecondaryKeys]; |
| boolean[] lowKeyInclusive = new boolean[numSecondaryKeys]; |
| boolean[] highKeyInclusive = new boolean[numSecondaryKeys]; |
| |
| List<Integer> exprList = analysisCtx.indexExprs.get(chosenIndex); |
| List<IOptimizableFuncExpr> matchedFuncExprs = analysisCtx.matchedFuncExprs; |
| // List of function expressions that will be replaced by the secondary-index search. |
| // These func exprs will be removed from the select condition at the very end of this method. |
| Set<ILogicalExpression> replacedFuncExprs = new HashSet<ILogicalExpression>(); |
| // TODO: For now we don't do any sophisticated analysis of the func exprs to come up with "the best" range predicate. |
| // If we can't figure out how to integrate a certain funcExpr into the current predicate, we just bail by setting this flag. |
| boolean couldntFigureOut = false; |
| boolean doneWithExprs = false; |
| boolean isEqCondition = false; |
| // TODO: For now don't consider prefix searches. |
| BitSet setLowKeys = new BitSet(numSecondaryKeys); |
| BitSet setHighKeys = new BitSet(numSecondaryKeys); |
| // Go through the func exprs listed as optimizable by the chosen index, |
| // and formulate a range predicate on the secondary-index keys. |
| for (Integer exprIndex : exprList) { |
| // Position of the field of matchedFuncExprs.get(exprIndex) in the chosen index's indexed exprs. |
| IOptimizableFuncExpr optFuncExpr = matchedFuncExprs.get(exprIndex); |
| int keyPos = indexOf(optFuncExpr.getFieldName(0), chosenIndex.getKeyFieldNames()); |
| if (keyPos < 0) { |
| if (optFuncExpr.getNumLogicalVars() > 1) { |
| // If we are optimizing a join, the matching field may be the second field name. |
| keyPos = indexOf(optFuncExpr.getFieldName(1), chosenIndex.getKeyFieldNames()); |
| } |
| } |
| if (keyPos < 0) { |
| throw new AlgebricksException( |
| "Could not match optimizable function expression to any index field name."); |
| } |
| ILogicalExpression searchKeyExpr = AccessMethodUtils.createSearchKeyExpr(optFuncExpr, indexSubTree, |
| probeSubTree); |
| LimitType limit = getLimitType(optFuncExpr, probeSubTree); |
| switch (limit) { |
| case EQUAL: { |
| if (lowKeyLimits[keyPos] == null && highKeyLimits[keyPos] == null) { |
| lowKeyLimits[keyPos] = highKeyLimits[keyPos] = limit; |
| lowKeyInclusive[keyPos] = highKeyInclusive[keyPos] = true; |
| lowKeyExprs[keyPos] = highKeyExprs[keyPos] = searchKeyExpr; |
| setLowKeys.set(keyPos); |
| setHighKeys.set(keyPos); |
| isEqCondition = true; |
| } else { |
| // Has already been set to the identical values. When optimizing join we may encounter the same optimizable expression twice |
| // (once from analyzing each side of the join) |
| if (lowKeyLimits[keyPos] == limit && lowKeyInclusive[keyPos] == true |
| && lowKeyExprs[keyPos].equals(searchKeyExpr) && highKeyLimits[keyPos] == limit |
| && highKeyInclusive[keyPos] == true && highKeyExprs[keyPos].equals(searchKeyExpr)) { |
| isEqCondition = true; |
| break; |
| } |
| couldntFigureOut = true; |
| } |
| // TODO: For now don't consider prefix searches. |
| // If high and low keys are set, we exit for now. |
| if (setLowKeys.cardinality() == numSecondaryKeys && setHighKeys.cardinality() == numSecondaryKeys) { |
| doneWithExprs = true; |
| } |
| break; |
| } |
| case HIGH_EXCLUSIVE: { |
| if (highKeyLimits[keyPos] == null || (highKeyLimits[keyPos] != null && highKeyInclusive[keyPos])) { |
| highKeyLimits[keyPos] = limit; |
| highKeyExprs[keyPos] = searchKeyExpr; |
| highKeyInclusive[keyPos] = false; |
| } else { |
| // Has already been set to the identical values. When optimizing join we may encounter the same optimizable expression twice |
| // (once from analyzing each side of the join) |
| if (highKeyLimits[keyPos] == limit && highKeyInclusive[keyPos] == false |
| && highKeyExprs[keyPos].equals(searchKeyExpr)) { |
| break; |
| } |
| couldntFigureOut = true; |
| doneWithExprs = true; |
| } |
| break; |
| } |
| case HIGH_INCLUSIVE: { |
| if (highKeyLimits[keyPos] == null) { |
| highKeyLimits[keyPos] = limit; |
| highKeyExprs[keyPos] = searchKeyExpr; |
| highKeyInclusive[keyPos] = true; |
| } else { |
| // Has already been set to the identical values. When optimizing join we may encounter the same optimizable expression twice |
| // (once from analyzing each side of the join) |
| if (highKeyLimits[keyPos] == limit && highKeyInclusive[keyPos] == true |
| && highKeyExprs[keyPos].equals(searchKeyExpr)) { |
| break; |
| } |
| couldntFigureOut = true; |
| doneWithExprs = true; |
| } |
| break; |
| } |
| case LOW_EXCLUSIVE: { |
| if (lowKeyLimits[keyPos] == null || (lowKeyLimits[keyPos] != null && lowKeyInclusive[keyPos])) { |
| lowKeyLimits[keyPos] = limit; |
| lowKeyExprs[keyPos] = searchKeyExpr; |
| lowKeyInclusive[keyPos] = false; |
| } else { |
| // Has already been set to the identical values. When optimizing join we may encounter the same optimizable expression twice |
| // (once from analyzing each side of the join) |
| if (lowKeyLimits[keyPos] == limit && lowKeyInclusive[keyPos] == false |
| && lowKeyExprs[keyPos].equals(searchKeyExpr)) { |
| break; |
| } |
| couldntFigureOut = true; |
| doneWithExprs = true; |
| } |
| break; |
| } |
| case LOW_INCLUSIVE: { |
| if (lowKeyLimits[keyPos] == null) { |
| lowKeyLimits[keyPos] = limit; |
| lowKeyExprs[keyPos] = searchKeyExpr; |
| lowKeyInclusive[keyPos] = true; |
| } else { |
| // Has already been set to the identical values. When optimizing join we may encounter the same optimizable expression twice |
| // (once from analyzing each side of the join) |
| if (lowKeyLimits[keyPos] == limit && lowKeyInclusive[keyPos] == true |
| && lowKeyExprs[keyPos].equals(searchKeyExpr)) { |
| break; |
| } |
| couldntFigureOut = true; |
| doneWithExprs = true; |
| } |
| break; |
| } |
| default: { |
| throw new IllegalStateException(); |
| } |
| } |
| if (!couldntFigureOut) { |
| // Remember to remove this funcExpr later. |
| replacedFuncExprs.add(matchedFuncExprs.get(exprIndex).getFuncExpr()); |
| } |
| if (doneWithExprs) { |
| break; |
| } |
| } |
| if (couldntFigureOut) { |
| return null; |
| } |
| |
| // Rule out the cases unsupported by the current btree search |
| // implementation. |
| for (int i = 1; i < numSecondaryKeys; i++) { |
| if (lowKeyInclusive[i] != lowKeyInclusive[0] || highKeyInclusive[i] != highKeyInclusive[0]) { |
| return null; |
| } |
| if (lowKeyLimits[0] == null && lowKeyLimits[i] != null || lowKeyLimits[0] != null |
| && lowKeyLimits[i] == null) { |
| return null; |
| } |
| if (highKeyLimits[0] == null && highKeyLimits[i] != null || highKeyLimits[0] != null |
| && highKeyLimits[i] == null) { |
| return null; |
| } |
| } |
| if (lowKeyLimits[0] == null) { |
| lowKeyInclusive[0] = true; |
| } |
| if (highKeyLimits[0] == null) { |
| highKeyInclusive[0] = true; |
| } |
| |
| // Here we generate vars and funcs for assigning the secondary-index keys to be fed into the secondary-index search. |
| // List of variables for the assign. |
| ArrayList<LogicalVariable> keyVarList = new ArrayList<LogicalVariable>(); |
| // List of variables and expressions for the assign. |
| ArrayList<LogicalVariable> assignKeyVarList = new ArrayList<LogicalVariable>(); |
| ArrayList<Mutable<ILogicalExpression>> assignKeyExprList = new ArrayList<Mutable<ILogicalExpression>>(); |
| int numLowKeys = createKeyVarsAndExprs(lowKeyLimits, lowKeyExprs, assignKeyVarList, assignKeyExprList, |
| keyVarList, context); |
| int numHighKeys = createKeyVarsAndExprs(highKeyLimits, highKeyExprs, assignKeyVarList, assignKeyExprList, |
| keyVarList, context); |
| |
| BTreeJobGenParams jobGenParams = new BTreeJobGenParams(chosenIndex.getIndexName(), IndexType.BTREE, |
| dataset.getDataverseName(), dataset.getDatasetName(), retainInput, requiresBroadcast); |
| jobGenParams.setLowKeyInclusive(lowKeyInclusive[0]); |
| jobGenParams.setHighKeyInclusive(highKeyInclusive[0]); |
| jobGenParams.setIsEqCondition(isEqCondition); |
| jobGenParams.setLowKeyVarList(keyVarList, 0, numLowKeys); |
| jobGenParams.setHighKeyVarList(keyVarList, numLowKeys, numHighKeys); |
| |
| ILogicalOperator inputOp = null; |
| if (!assignKeyVarList.isEmpty()) { |
| // Assign operator that sets the constant secondary-index search-key fields if necessary. |
| AssignOperator assignConstantSearchKeys = new AssignOperator(assignKeyVarList, assignKeyExprList); |
| // Input to this assign is the EmptyTupleSource (which the dataSourceScan also must have had as input). |
| assignConstantSearchKeys.getInputs().add(dataSourceScan.getInputs().get(0)); |
| assignConstantSearchKeys.setExecutionMode(dataSourceScan.getExecutionMode()); |
| inputOp = assignConstantSearchKeys; |
| } else { |
| // All index search keys are variables. |
| inputOp = probeSubTree.root; |
| } |
| |
| UnnestMapOperator secondaryIndexUnnestOp = AccessMethodUtils.createSecondaryIndexUnnestMap(dataset, recordType, |
| chosenIndex, inputOp, jobGenParams, context, false, retainInput); |
| |
| // Generate the rest of the upstream plan which feeds the search results into the primary index. |
| UnnestMapOperator primaryIndexUnnestOp; |
| boolean isPrimaryIndex = chosenIndex.getIndexName().equals(dataset.getDatasetName()); |
| if (!isPrimaryIndex) { |
| primaryIndexUnnestOp = AccessMethodUtils.createPrimaryIndexUnnestMap(dataSourceScan, dataset, recordType, |
| secondaryIndexUnnestOp, context, true, retainInput, false); |
| } else { |
| List<Object> primaryIndexOutputTypes = new ArrayList<Object>(); |
| AccessMethodUtils.appendPrimaryIndexTypes(dataset, recordType, primaryIndexOutputTypes); |
| primaryIndexUnnestOp = new UnnestMapOperator(dataSourceScan.getVariables(), |
| secondaryIndexUnnestOp.getExpressionRef(), primaryIndexOutputTypes, retainInput); |
| primaryIndexUnnestOp.getInputs().add(new MutableObject<ILogicalOperator>(inputOp)); |
| } |
| |
| List<Mutable<ILogicalExpression>> remainingFuncExprs = new ArrayList<Mutable<ILogicalExpression>>(); |
| getNewConditionExprs(conditionRef, replacedFuncExprs, remainingFuncExprs); |
| // Generate new condition. |
| if (!remainingFuncExprs.isEmpty()) { |
| ILogicalExpression pulledCond = createSelectCondition(remainingFuncExprs); |
| conditionRef.setValue(pulledCond); |
| } else { |
| conditionRef.setValue(null); |
| } |
| return primaryIndexUnnestOp; |
| } |
| |
| private int createKeyVarsAndExprs(LimitType[] keyLimits, ILogicalExpression[] searchKeyExprs, |
| ArrayList<LogicalVariable> assignKeyVarList, ArrayList<Mutable<ILogicalExpression>> assignKeyExprList, |
| ArrayList<LogicalVariable> keyVarList, IOptimizationContext context) { |
| if (keyLimits[0] == null) { |
| return 0; |
| } |
| int numKeys = keyLimits.length; |
| for (int i = 0; i < numKeys; i++) { |
| ILogicalExpression searchKeyExpr = searchKeyExprs[i]; |
| LogicalVariable keyVar = null; |
| if (searchKeyExpr.getExpressionTag() == LogicalExpressionTag.CONSTANT) { |
| keyVar = context.newVar(); |
| assignKeyExprList.add(new MutableObject<ILogicalExpression>(searchKeyExpr)); |
| assignKeyVarList.add(keyVar); |
| } else { |
| keyVar = ((VariableReferenceExpression) searchKeyExpr).getVariableReference(); |
| } |
| keyVarList.add(keyVar); |
| } |
| return numKeys; |
| } |
| |
| private void getNewConditionExprs(Mutable<ILogicalExpression> conditionRef, |
| Set<ILogicalExpression> replacedFuncExprs, List<Mutable<ILogicalExpression>> remainingFuncExprs) { |
| remainingFuncExprs.clear(); |
| if (replacedFuncExprs.isEmpty()) { |
| return; |
| } |
| AbstractFunctionCallExpression funcExpr = (AbstractFunctionCallExpression) conditionRef.getValue(); |
| if (replacedFuncExprs.size() == 1) { |
| Iterator<ILogicalExpression> it = replacedFuncExprs.iterator(); |
| if (!it.hasNext()) { |
| return; |
| } |
| if (funcExpr == it.next()) { |
| // There are no remaining function exprs. |
| return; |
| } |
| } |
| // The original select cond must be an AND. Check it just to be sure. |
| if (funcExpr.getFunctionIdentifier() != AlgebricksBuiltinFunctions.AND) { |
| throw new IllegalStateException(); |
| } |
| // Clean the conjuncts. |
| for (Mutable<ILogicalExpression> arg : funcExpr.getArguments()) { |
| ILogicalExpression argExpr = arg.getValue(); |
| if (argExpr.getExpressionTag() != LogicalExpressionTag.FUNCTION_CALL) { |
| continue; |
| } |
| // If the function expression was not replaced by the new index |
| // plan, then add it to the list of remaining function expressions. |
| if (!replacedFuncExprs.contains(argExpr)) { |
| remainingFuncExprs.add(arg); |
| } |
| } |
| } |
| |
| private <T> int indexOf(T value, List<T> coll) { |
| int i = 0; |
| for (T member : coll) { |
| if (member.equals(value)) { |
| return i; |
| } |
| i++; |
| } |
| return -1; |
| } |
| |
| private LimitType getLimitType(IOptimizableFuncExpr optFuncExpr, OptimizableOperatorSubTree probeSubTree) { |
| ComparisonKind ck = AlgebricksBuiltinFunctions.getComparisonType(optFuncExpr.getFuncExpr() |
| .getFunctionIdentifier()); |
| LimitType limit = null; |
| switch (ck) { |
| case EQ: { |
| limit = LimitType.EQUAL; |
| break; |
| } |
| case GE: { |
| limit = probeIsOnLhs(optFuncExpr, probeSubTree) ? LimitType.HIGH_INCLUSIVE : LimitType.LOW_INCLUSIVE; |
| break; |
| } |
| case GT: { |
| limit = probeIsOnLhs(optFuncExpr, probeSubTree) ? LimitType.HIGH_EXCLUSIVE : LimitType.LOW_EXCLUSIVE; |
| break; |
| } |
| case LE: { |
| limit = probeIsOnLhs(optFuncExpr, probeSubTree) ? LimitType.LOW_INCLUSIVE : LimitType.HIGH_INCLUSIVE; |
| break; |
| } |
| case LT: { |
| limit = probeIsOnLhs(optFuncExpr, probeSubTree) ? LimitType.LOW_EXCLUSIVE : LimitType.HIGH_EXCLUSIVE; |
| break; |
| } |
| case NEQ: { |
| limit = null; |
| break; |
| } |
| default: { |
| throw new IllegalStateException(); |
| } |
| } |
| return limit; |
| } |
| |
| private boolean probeIsOnLhs(IOptimizableFuncExpr optFuncExpr, OptimizableOperatorSubTree probeSubTree) { |
| if (probeSubTree == null) { |
| // We are optimizing a selection query. Search key is a constant. Return true if constant is on lhs. |
| return optFuncExpr.getFuncExpr().getArguments().get(0) == optFuncExpr.getConstantVal(0); |
| } else { |
| // We are optimizing a join query. Determine whether the feeding variable is on the lhs. |
| return (optFuncExpr.getOperatorSubTree(0) == null || optFuncExpr.getOperatorSubTree(0) == probeSubTree); |
| } |
| } |
| |
| private ILogicalExpression createSelectCondition(List<Mutable<ILogicalExpression>> predList) { |
| if (predList.size() > 1) { |
| IFunctionInfo finfo = AsterixBuiltinFunctions.getAsterixFunctionInfo(AlgebricksBuiltinFunctions.AND); |
| return new ScalarFunctionCallExpression(finfo, predList); |
| } |
| return predList.get(0).getValue(); |
| } |
| |
| @Override |
| public boolean exprIsOptimizable(Index index, IOptimizableFuncExpr optFuncExpr) { |
| // If we are optimizing a join, check for the indexed nested-loop join hint. |
| if (optFuncExpr.getNumLogicalVars() == 2) { |
| if (!optFuncExpr.getFuncExpr().getAnnotations().containsKey(IndexedNLJoinExpressionAnnotation.INSTANCE)) { |
| return false; |
| } |
| } |
| // No additional analysis required for BTrees. |
| return true; |
| } |
| } |
