>From Shahrzad Shirazi <[email protected]>:
Shahrzad Shirazi has uploaded this change for review. (
https://asterix-gerrit.ics.uci.edu/c/asterixdb/+/20961?usp=email )
Change subject: WIP:Index not used with redundant range predicates
......................................................................
WIP:Index not used with redundant range predicates
Change-Id: I77ff55c70a3f2b54154162120260c373d51ba77c
---
M
asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/am/BTreeAccessMethod.java
1 file changed, 122 insertions(+), 56 deletions(-)
git pull ssh://asterix-gerrit.ics.uci.edu:29418/asterixdb
refs/changes/61/20961/1
diff --git
a/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/am/BTreeAccessMethod.java
b/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/am/BTreeAccessMethod.java
index b7e2a28..d3a2d3d 100644
---
a/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/am/BTreeAccessMethod.java
+++
b/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/am/BTreeAccessMethod.java
@@ -47,6 +47,7 @@
import org.apache.asterix.metadata.utils.TypeUtil;
import org.apache.asterix.om.base.ADouble;
import org.apache.asterix.om.base.IAObject;
+import org.apache.asterix.om.constants.AsterixConstantValue;
import org.apache.asterix.om.functions.BuiltinFunctions;
import org.apache.asterix.om.typecomputer.base.TypeCastUtils;
import org.apache.asterix.om.typecomputer.impl.TypeComputeUtils;
@@ -69,6 +70,7 @@
import org.apache.hyracks.algebricks.core.algebra.base.LogicalOperatorTag;
import org.apache.hyracks.algebricks.core.algebra.base.LogicalVariable;
import
org.apache.hyracks.algebricks.core.algebra.expressions.AbstractFunctionCallExpression;
+import
org.apache.hyracks.algebricks.core.algebra.expressions.ConstantExpression;
import
org.apache.hyracks.algebricks.core.algebra.expressions.IAlgebricksConstantValue;
import
org.apache.hyracks.algebricks.core.algebra.expressions.IVariableTypeEnvironment;
import
org.apache.hyracks.algebricks.core.algebra.expressions.ScalarFunctionCallExpression;
@@ -127,8 +129,8 @@
@Override
public boolean
analyzeFuncExprArgsAndUpdateAnalysisCtx(AbstractFunctionCallExpression funcExpr,
- List<AbstractLogicalOperator> assignsAndUnnests,
AccessMethodAnalysisContext analysisCtx,
- IOptimizationContext context, IVariableTypeEnvironment
typeEnvironment) throws AlgebricksException {
+
List<AbstractLogicalOperator> assignsAndUnnests, AccessMethodAnalysisContext
analysisCtx,
+
IOptimizationContext context, IVariableTypeEnvironment typeEnvironment) throws
AlgebricksException {
boolean matches =
AccessMethodUtils.analyzeFuncExprArgsForOneConstAndVarAndUpdateAnalysisCtx(funcExpr,
analysisCtx, context, typeEnvironment,
allowFunctionExpressionArg());
if (!matches) {
@@ -153,8 +155,8 @@
@Override
public boolean
applySelectPlanTransformation(List<Mutable<ILogicalOperator>> afterSelectRefs,
- Mutable<ILogicalOperator> selectRef, OptimizableOperatorSubTree
subTree, Index chosenIndex,
- AccessMethodAnalysisContext analysisCtx, IOptimizationContext
context) throws AlgebricksException {
+ Mutable<ILogicalOperator>
selectRef, OptimizableOperatorSubTree subTree, Index chosenIndex,
+ AccessMethodAnalysisContext
analysisCtx, IOptimizationContext context) throws AlgebricksException {
SelectOperator selectOp = (SelectOperator) selectRef.getValue();
Mutable<ILogicalExpression> conditionRef = selectOp.getCondition();
AbstractFunctionCallExpression funcExpr =
(AbstractFunctionCallExpression) conditionRef.getValue();
@@ -257,10 +259,10 @@
@Override
public boolean applyJoinPlanTransformation(List<Mutable<ILogicalOperator>>
afterJoinRefs,
- Mutable<ILogicalOperator> joinRef, OptimizableOperatorSubTree
leftSubTree,
- OptimizableOperatorSubTree rightSubTree, Index chosenIndex,
AccessMethodAnalysisContext analysisCtx,
- IOptimizationContext context, boolean isLeftOuterJoin, boolean
isLeftOuterJoinWithSpecialGroupBy,
- IAlgebricksConstantValue leftOuterMissingValue) throws
AlgebricksException {
+ Mutable<ILogicalOperator>
joinRef, OptimizableOperatorSubTree leftSubTree,
+ OptimizableOperatorSubTree
rightSubTree, Index chosenIndex, AccessMethodAnalysisContext analysisCtx,
+ IOptimizationContext context,
boolean isLeftOuterJoin, boolean isLeftOuterJoinWithSpecialGroupBy,
+ IAlgebricksConstantValue
leftOuterMissingValue) throws AlgebricksException {
AbstractBinaryJoinOperator joinOp = (AbstractBinaryJoinOperator)
joinRef.getValue();
Mutable<ILogicalExpression> conditionRef = joinOp.getCondition();
@@ -318,11 +320,11 @@
*/
@Override
public ILogicalOperator
createIndexSearchPlan(List<Mutable<ILogicalOperator>> afterTopOpRefs,
- Mutable<ILogicalOperator> topOpRef, Mutable<ILogicalExpression>
conditionRef,
- List<Mutable<ILogicalOperator>> assignBeforeTheOpRefs,
OptimizableOperatorSubTree indexSubTree,
- OptimizableOperatorSubTree probeSubTree, Index chosenIndex,
AccessMethodAnalysisContext analysisCtx,
- boolean retainInput, boolean retainMissing, boolean
requiresBroadcast, IOptimizationContext context,
- LogicalVariable newMissingNullPlaceHolderForLOJ,
IAlgebricksConstantValue leftOuterMissingValue)
+ Mutable<ILogicalOperator>
topOpRef, Mutable<ILogicalExpression> conditionRef,
+
List<Mutable<ILogicalOperator>> assignBeforeTheOpRefs,
OptimizableOperatorSubTree indexSubTree,
+ OptimizableOperatorSubTree
probeSubTree, Index chosenIndex, AccessMethodAnalysisContext analysisCtx,
+ boolean retainInput, boolean
retainMissing, boolean requiresBroadcast, IOptimizationContext context,
+ LogicalVariable
newMissingNullPlaceHolderForLOJ, IAlgebricksConstantValue leftOuterMissingValue)
throws AlgebricksException {
Index.ValueIndexDetails chosenIndexDetails = (Index.ValueIndexDetails)
chosenIndex.getIndexDetails();
@@ -337,13 +339,13 @@
}
protected ILogicalOperator
createBTreeIndexSearchPlan(List<Mutable<ILogicalOperator>> afterTopOpRefs,
- Mutable<ILogicalOperator> topOpRef, Mutable<ILogicalExpression>
conditionRef,
- List<Mutable<ILogicalOperator>> assignBeforeTheOpRefs,
OptimizableOperatorSubTree indexSubTree,
- OptimizableOperatorSubTree probeSubTree, Index chosenIndex,
AccessMethodAnalysisContext analysisCtx,
- boolean retainInput, boolean retainMissing, boolean
requiresBroadcast, IOptimizationContext context,
- LogicalVariable newMissingNullPlaceHolderForLOJ,
IAlgebricksConstantValue leftOuterMissingValue,
- List<List<String>> chosenIndexKeyFieldNames, List<IAType>
chosenIndexKeyFieldTypes,
- List<Integer> chosenIndexKeyFieldSourceIndicators) throws
AlgebricksException {
+
Mutable<ILogicalOperator> topOpRef, Mutable<ILogicalExpression> conditionRef,
+
List<Mutable<ILogicalOperator>> assignBeforeTheOpRefs,
OptimizableOperatorSubTree indexSubTree,
+
OptimizableOperatorSubTree probeSubTree, Index chosenIndex,
AccessMethodAnalysisContext analysisCtx,
+ boolean retainInput,
boolean retainMissing, boolean requiresBroadcast, IOptimizationContext context,
+ LogicalVariable
newMissingNullPlaceHolderForLOJ, IAlgebricksConstantValue leftOuterMissingValue,
+ List<List<String>>
chosenIndexKeyFieldNames, List<IAType> chosenIndexKeyFieldTypes,
+ List<Integer>
chosenIndexKeyFieldSourceIndicators) throws AlgebricksException {
Dataset dataset = indexSubTree.getDataset();
ARecordType recordType = indexSubTree.getRecordType();
ARecordType metaRecordType = indexSubTree.getMetaRecordType();
@@ -497,15 +499,23 @@
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;
+ // Multiple upper-bound predicates on the same key
(e.g., a < 3 AND a < 5).
+ // Pick the tighter (smaller) bound if both are
constants.
+ int cmp = compareConstants(searchKeyExpr,
highKeyExprs[keyPos]);
+ if (cmp != 0) {
+ if (cmp < 0) {
+ highKeyLimits[keyPos] = limit;
+ highKeyExprs[keyPos] = searchKeyExpr;
+ highKeyInclusive[keyPos] = false;
+ }
+ } else {
+ couldntFigureOut = true;
+ doneWithExprs = true;
+ }
}
break;
}
@@ -515,15 +525,23 @@
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;
+ // Multiple upper-bound predicates on the same key
(e.g., a <= 3 AND a <= 5).
+ // Pick the tighter (smaller) bound if both are
constants.
+ int cmp = compareConstants(searchKeyExpr,
highKeyExprs[keyPos]);
+ if (cmp != 0) {
+ if (cmp < 0) {
+ highKeyLimits[keyPos] = limit;
+ highKeyExprs[keyPos] = searchKeyExpr;
+ highKeyInclusive[keyPos] = true;
+ }
+ } else {
+ couldntFigureOut = true;
+ doneWithExprs = true;
+ }
}
break;
}
@@ -533,15 +551,23 @@
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;
+ // Multiple lower-bound predicates on the same key
(e.g., a > 3 AND a > 5).
+ // Pick the tighter (larger) bound if both are
constants.
+ int cmp = compareConstants(searchKeyExpr,
lowKeyExprs[keyPos]);
+ if (cmp != 0) {
+ if (cmp > 0) {
+ lowKeyLimits[keyPos] = limit;
+ lowKeyExprs[keyPos] = searchKeyExpr;
+ lowKeyInclusive[keyPos] = false;
+ }
+ } else {
+ couldntFigureOut = true;
+ doneWithExprs = true;
+ }
}
break;
}
@@ -551,15 +577,23 @@
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;
+ // Multiple lower-bound predicates on the same key
(e.g., a >= 3 AND a >= 5).
+ // Pick the tighter (larger) bound if both are
constants.
+ int cmp = compareConstants(searchKeyExpr,
lowKeyExprs[keyPos]);
+ if (cmp != 0) {
+ if (cmp > 0) {
+ lowKeyLimits[keyPos] = limit;
+ lowKeyExprs[keyPos] = searchKeyExpr;
+ lowKeyInclusive[keyPos] = true;
+ }
+ } else {
+ couldntFigureOut = true;
+ doneWithExprs = true;
+ }
}
break;
}
@@ -578,7 +612,6 @@
if (couldntFigureOut) {
return null;
}
-
// if we have composite search keys, we should always need a
post-processing to ensure the correctness
// of search results because of the way a BTree is searched, unless
only the last key is a range search.
// During a BTree search, we iterate from the start index
@@ -819,7 +852,7 @@
}
private static ILogicalOperator addCastAssignOp(IOptimizationContext ctx,
List<IAType> indexKeysTypes,
- BTreeJobGenParams jobGenParams, ILogicalOperator inputOp,
SourceLocation srcLoc)
+ BTreeJobGenParams
jobGenParams, ILogicalOperator inputOp, SourceLocation srcLoc)
throws AlgebricksException {
// cast the input values (low/high vars) if needed and update the
jobGenParams
List<LogicalVariable> lowKeyVars = jobGenParams.getLowKeyVarList();
@@ -839,8 +872,8 @@
}
private static void castInputValues(IOptimizationContext ctx, List<IAType>
indexKeyTypes,
- List<LogicalVariable> inputVars, ILogicalOperator inputOp,
List<LogicalVariable> castAssignVars,
- List<Mutable<ILogicalExpression>> castAssignExprs, SourceLocation
srcLoc) throws AlgebricksException {
+ List<LogicalVariable> inputVars,
ILogicalOperator inputOp, List<LogicalVariable> castAssignVars,
+ List<Mutable<ILogicalExpression>>
castAssignExprs, SourceLocation srcLoc) throws AlgebricksException {
for (int i = 0; i < inputVars.size(); i++) {
LogicalVariable inputVar = inputVars.get(i);
IVariableTypeEnvironment typeEnv =
ctx.getOutputTypeEnvironment(inputOp);
@@ -864,9 +897,9 @@
}
private int createKeyVarsAndExprs(int numKeys, LimitType[] keyLimits,
ILogicalExpression[] searchKeyExprs,
- ArrayList<LogicalVariable> assignKeyVarList,
ArrayList<Mutable<ILogicalExpression>> assignKeyExprList,
- ArrayList<LogicalVariable> keyVarList, IOptimizationContext
context, ILogicalExpression[] constExpressions,
- LogicalVariable[] constExprVars) {
+ ArrayList<LogicalVariable>
assignKeyVarList, ArrayList<Mutable<ILogicalExpression>> assignKeyExprList,
+ ArrayList<LogicalVariable> keyVarList,
IOptimizationContext context, ILogicalExpression[] constExpressions,
+ LogicalVariable[] constExprVars) {
if (keyLimits[0] == null) {
return 0;
}
@@ -894,7 +927,7 @@
}
private void getNewConditionExprs(Mutable<ILogicalExpression> conditionRef,
- Set<ILogicalExpression> replacedFuncExprs,
List<Mutable<ILogicalExpression>> remainingFuncExprs)
+ Set<ILogicalExpression>
replacedFuncExprs, List<Mutable<ILogicalExpression>> remainingFuncExprs)
throws CompilationException {
remainingFuncExprs.clear();
if (replacedFuncExprs.isEmpty()) {
@@ -931,7 +964,7 @@
}
private static int indexOf(List<String> fieldName, int fieldSource,
List<List<String>> keyNames,
- List<Integer> keySources) {
+ List<Integer> keySources) {
int i = 0;
for (List<String> keyName : keyNames) {
if (keyName.equals(fieldName) && keyMatches(keySources, i,
fieldSource)) {
@@ -995,19 +1028,19 @@
@Override
public ATypeHierarchy.TypeCastingMathFunctionType
getRoundingFunction(ComparisonKind cKind, Index chosenIndex,
- IAType indexedFieldType, IAObject constantValue, boolean
realTypeConvertedToIntegerType)
+
IAType indexedFieldType, IAObject constantValue, boolean
realTypeConvertedToIntegerType)
throws CompilationException {
switch (cKind) {
case GE:
return relaxLimitTypeToInclusive(chosenIndex,
indexedFieldType, realTypeConvertedToIntegerType)
&& DOUBLE_CMPR.compare(ZERO, constantValue) ==
ILogicalBinaryComparator.Result.LT
- ?
ATypeHierarchy.TypeCastingMathFunctionType.FLOOR
- :
ATypeHierarchy.TypeCastingMathFunctionType.CEIL;
+ ? ATypeHierarchy.TypeCastingMathFunctionType.FLOOR
+ : ATypeHierarchy.TypeCastingMathFunctionType.CEIL;
case LE:
return relaxLimitTypeToInclusive(chosenIndex,
indexedFieldType, realTypeConvertedToIntegerType)
&& DOUBLE_CMPR.compare(ZERO, constantValue) ==
ILogicalBinaryComparator.Result.GT
- ?
ATypeHierarchy.TypeCastingMathFunctionType.CEIL
- :
ATypeHierarchy.TypeCastingMathFunctionType.FLOOR;
+ ? ATypeHierarchy.TypeCastingMathFunctionType.CEIL
+ : ATypeHierarchy.TypeCastingMathFunctionType.FLOOR;
default:
return super.getRoundingFunction(cKind, chosenIndex,
indexedFieldType, constantValue,
realTypeConvertedToIntegerType);
@@ -1016,7 +1049,7 @@
}
private static boolean relaxLimitTypeToInclusive(Index chosenIndex, IAType
indexedFieldType,
- boolean realTypeConvertedToIntegerType) {
+ boolean
realTypeConvertedToIntegerType) {
// For a non-enforced index or an enforced index that stores a casted
value on the given index,
// we need to apply the following transformation.
// For an index on a closed field, this transformation is not
necessary since the value between
@@ -1142,7 +1175,7 @@
@Override
public boolean acceptsFunction(AbstractFunctionCallExpression
functionExpr, Index index, IAType indexedFieldType,
- boolean defaultNull, boolean finalStep) throws
CompilationException {
+ boolean defaultNull, boolean finalStep)
throws CompilationException {
FunctionIdentifier funId = functionExpr.getFunctionIdentifier();
if (!finalStep) {
return AccessMethodUtils.isFieldAccess(funId);
@@ -1169,4 +1202,37 @@
return this.getName().compareTo(o.getName());
}
+ /**
+ * Compares two constant search key expressions.
+ * Returns negative if expr1 < expr2, positive if expr1 > expr2, 0 if
comparison is not possible
+ * (e.g., non-constant expressions or incomparable types).
+ */
+ private static int compareConstants(ILogicalExpression expr1,
ILogicalExpression expr2) {
+ if (expr1.getExpressionTag() != LogicalExpressionTag.CONSTANT
+ || expr2.getExpressionTag() != LogicalExpressionTag.CONSTANT) {
+ return 0;
+ }
+ IAObject val1 = ((AsterixConstantValue) ((ConstantExpression)
expr1).getValue()).getObject();
+ IAObject val2 = ((AsterixConstantValue) ((ConstantExpression)
expr2).getValue()).getObject();
+ IAType type1 = val1.getType();
+ IAType type2 = val2.getType();
+ if (type1.getTypeTag() != type2.getTypeTag()) {
+ return 0;
+ }
+ try {
+ ILogicalBinaryComparator comparator =
ComparatorUtil.createLogicalComparator(type1, type2, false);
+ ILogicalBinaryComparator.Result result = comparator.compare(val1,
val2);
+ switch (result) {
+ case LT:
+ return -1;
+ case GT:
+ return 1;
+ default:
+ return 0;
+ }
+ } catch (Exception e) {
+ return 0;
+ }
+ }
+
}
--
To view, visit https://asterix-gerrit.ics.uci.edu/c/asterixdb/+/20961?usp=email
To unsubscribe, or for help writing mail filters, visit
https://asterix-gerrit.ics.uci.edu/settings?usp=email
Gerrit-MessageType: newchange
Gerrit-Project: asterixdb
Gerrit-Branch: master
Gerrit-Change-Id: I77ff55c70a3f2b54154162120260c373d51ba77c
Gerrit-Change-Number: 20961
Gerrit-PatchSet: 1
Gerrit-Owner: Shahrzad Shirazi <[email protected]>
