You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@asterixdb.apache.org by wa...@apache.org on 2018/02/16 19:04:21 UTC
[15/16] asterixdb git commit: [ASTERIXDB-1972][COMP][RT][TX]
index-only plan
http://git-wip-us.apache.org/repos/asf/asterixdb/blob/c3c23574/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/am/AccessMethodUtils.java
----------------------------------------------------------------------
diff --git a/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/am/AccessMethodUtils.java b/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/am/AccessMethodUtils.java
index 10630a5..9950e37 100644
--- a/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/am/AccessMethodUtils.java
+++ b/asterixdb/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/am/AccessMethodUtils.java
@@ -20,8 +20,12 @@
package org.apache.asterix.optimizer.rules.am;
import java.util.ArrayList;
+import java.util.Collections;
import java.util.HashSet;
+import java.util.Iterator;
+import java.util.LinkedHashMap;
import java.util.List;
+import java.util.Map;
import java.util.Set;
import org.apache.asterix.algebra.operators.physical.ExternalDataLookupPOperator;
@@ -50,11 +54,14 @@ import org.apache.asterix.om.types.ATypeTag;
import org.apache.asterix.om.types.BuiltinType;
import org.apache.asterix.om.types.IAType;
import org.apache.asterix.om.types.hierachy.ATypeHierarchy;
+import org.apache.asterix.om.types.hierachy.ATypeHierarchy.TypeCastingMathFunctionType;
import org.apache.asterix.om.utils.ConstantExpressionUtil;
import org.apache.commons.lang3.mutable.Mutable;
import org.apache.commons.lang3.mutable.MutableObject;
import org.apache.hyracks.algebricks.common.exceptions.AlgebricksException;
import org.apache.hyracks.algebricks.common.utils.Pair;
+import org.apache.hyracks.algebricks.common.utils.Quadruple;
+import org.apache.hyracks.algebricks.common.utils.Triple;
import org.apache.hyracks.algebricks.core.algebra.base.ILogicalExpression;
import org.apache.hyracks.algebricks.core.algebra.base.ILogicalOperator;
import org.apache.hyracks.algebricks.core.algebra.base.IOptimizationContext;
@@ -68,15 +75,21 @@ import org.apache.hyracks.algebricks.core.algebra.expressions.ScalarFunctionCall
import org.apache.hyracks.algebricks.core.algebra.expressions.UnnestingFunctionCallExpression;
import org.apache.hyracks.algebricks.core.algebra.expressions.VariableReferenceExpression;
import org.apache.hyracks.algebricks.core.algebra.functions.AlgebricksBuiltinFunctions;
+import org.apache.hyracks.algebricks.core.algebra.functions.AlgebricksBuiltinFunctions.ComparisonKind;
+import org.apache.hyracks.algebricks.core.algebra.functions.FunctionIdentifier;
import org.apache.hyracks.algebricks.core.algebra.functions.IFunctionInfo;
import org.apache.hyracks.algebricks.core.algebra.operators.logical.AbstractDataSourceOperator;
import org.apache.hyracks.algebricks.core.algebra.operators.logical.AbstractLogicalOperator;
import org.apache.hyracks.algebricks.core.algebra.operators.logical.AbstractLogicalOperator.ExecutionMode;
import org.apache.hyracks.algebricks.core.algebra.operators.logical.AbstractUnnestMapOperator;
+import org.apache.hyracks.algebricks.core.algebra.operators.logical.AggregateOperator;
+import org.apache.hyracks.algebricks.core.algebra.operators.logical.AssignOperator;
import org.apache.hyracks.algebricks.core.algebra.operators.logical.GroupByOperator;
import org.apache.hyracks.algebricks.core.algebra.operators.logical.LeftOuterUnnestMapOperator;
import org.apache.hyracks.algebricks.core.algebra.operators.logical.OrderOperator;
import org.apache.hyracks.algebricks.core.algebra.operators.logical.SelectOperator;
+import org.apache.hyracks.algebricks.core.algebra.operators.logical.SplitOperator;
+import org.apache.hyracks.algebricks.core.algebra.operators.logical.UnionAllOperator;
import org.apache.hyracks.algebricks.core.algebra.operators.logical.UnnestMapOperator;
import org.apache.hyracks.algebricks.core.algebra.operators.logical.visitors.VariableUtilities;
import org.apache.hyracks.algebricks.core.algebra.plan.ALogicalPlanImpl;
@@ -89,6 +102,13 @@ import org.apache.hyracks.storage.am.lsm.invertedindex.tokenizers.DelimitedUTF8S
*/
public class AccessMethodUtils {
+ // Output variable type from a secondary unnest-map
+ enum SecondaryUnnestMapOutputVarType {
+ PRIMARY_KEY,
+ SECONDARY_KEY,
+ CONDITIONAL_SPLIT_VAR
+ }
+
public static void appendPrimaryIndexTypes(Dataset dataset, IAType itemType, IAType metaItemType,
List<Object> target) throws AlgebricksException {
ARecordType recordType = (ARecordType) itemType;
@@ -292,7 +312,9 @@ public class AccessMethodUtils {
* Appends the types of the fields produced by the given secondary index to dest.
*/
public static void appendSecondaryIndexTypes(Dataset dataset, ARecordType recordType, ARecordType metaRecordType,
- Index index, boolean primaryKeysOnly, List<Object> dest) throws AlgebricksException {
+ Index index, List<Object> dest, boolean requireResultOfInstantTryLock) throws AlgebricksException {
+ // In case of an inverted-index search, secondary keys will not be generated.
+ boolean primaryKeysOnly = isInvertedIndex(index);
if (!primaryKeysOnly) {
switch (index.getIndexType()) {
case BTREE:
@@ -301,10 +323,6 @@ public class AccessMethodUtils {
case RTREE:
dest.addAll(KeyFieldTypeUtil.getRTreeIndexKeyTypes(index, recordType, metaRecordType));
break;
- case SINGLE_PARTITION_WORD_INVIX:
- case SINGLE_PARTITION_NGRAM_INVIX:
- case LENGTH_PARTITIONED_NGRAM_INVIX:
- case LENGTH_PARTITIONED_WORD_INVIX:
default:
break;
}
@@ -316,12 +334,25 @@ public class AccessMethodUtils {
} else {
dest.addAll(KeyFieldTypeUtil.getPartitoningKeyTypes(dataset, recordType, metaRecordType));
}
+
+ // Adds one more type to apply an index-only plan optimization.
+ // Currently, we use AINT32 to decode result values for this.
+ // Refer to appendSecondaryIndexOutputVars() for more details.
+ if (requireResultOfInstantTryLock) {
+ dest.add(BuiltinType.AINT32);
+ }
+
}
+ /**
+ * Creates output variables for the given unnest-map or left-outer-unnestmap operator
+ * that does a secondary index lookup.
+ * The order: SK, PK, [Optional: the result of a instantTryLock on PK]
+ */
public static void appendSecondaryIndexOutputVars(Dataset dataset, ARecordType recordType,
- ARecordType metaRecordType, Index index, boolean primaryKeysOnly, IOptimizationContext context,
- List<LogicalVariable> dest) throws AlgebricksException {
- int numPrimaryKeys = 0;
+ ARecordType metaRecordType, Index index, IOptimizationContext context, List<LogicalVariable> dest,
+ boolean requireResultOfInstantTryLock) throws AlgebricksException {
+ int numPrimaryKeys;
if (dataset.getDatasetType() == DatasetType.EXTERNAL) {
numPrimaryKeys = IndexingConstants
.getRIDSize(((ExternalDatasetDetails) dataset.getDatasetDetails()).getProperties());
@@ -329,33 +360,80 @@ public class AccessMethodUtils {
numPrimaryKeys = dataset.getPrimaryKeys().size();
}
int numSecondaryKeys = KeyFieldTypeUtil.getNumSecondaryKeys(index, recordType, metaRecordType);
- int numVars = (primaryKeysOnly) ? numPrimaryKeys : numPrimaryKeys + numSecondaryKeys;
+ // In case of an inverted-index search, secondary keys will not be generated.
+ int numVars = isInvertedIndex(index) ? numPrimaryKeys : numPrimaryKeys + numSecondaryKeys;
+
+ // If it's an index-only plan, add one more variable to put the result of instantTryLock on PK -
+ // whether this lock can be granted on a primary key.
+ // If it is granted, then we don't need to do a post verification (select).
+ // If it is not granted, then we need to do a secondary index lookup, do a primary index lookup, and select.
+ if (requireResultOfInstantTryLock) {
+ numVars += 1;
+ }
+
for (int i = 0; i < numVars; i++) {
dest.add(context.newVar());
}
}
- public static List<LogicalVariable> getPrimaryKeyVarsFromSecondaryUnnestMap(Dataset dataset,
- ILogicalOperator unnestMapOp) {
+ /**
+ * Gets the primary key variables from the unnest-map or left-outer-unnest-map operator
+ * that does a secondary index lookup.
+ * The order: SK, PK, [Optional: the result of a TryLock on PK]
+ */
+ public static List<LogicalVariable> getKeyVarsFromSecondaryUnnestMap(Dataset dataset, ARecordType recordType,
+ ARecordType metaRecordType, ILogicalOperator unnestMapOp, Index index,
+ SecondaryUnnestMapOutputVarType keyVarType) throws AlgebricksException {
int numPrimaryKeys;
+ int numSecondaryKeys = KeyFieldTypeUtil.getNumSecondaryKeys(index, recordType, metaRecordType);
if (dataset.getDatasetType() == DatasetType.EXTERNAL) {
numPrimaryKeys = IndexingConstants
.getRIDSize(((ExternalDatasetDetails) dataset.getDatasetDetails()).getProperties());
} else {
numPrimaryKeys = dataset.getPrimaryKeys().size();
}
- List<LogicalVariable> primaryKeyVars = new ArrayList<>();
- List<LogicalVariable> sourceVars = null;
-
- sourceVars = ((AbstractUnnestMapOperator) unnestMapOp).getVariables();
+ List<LogicalVariable> keyVars = new ArrayList<>();
+ AbstractUnnestMapOperator abstractUnnestMapOp = (AbstractUnnestMapOperator) unnestMapOp;
+ List<LogicalVariable> sourceVars = abstractUnnestMapOp.getVariables();
+ // Assumption: the primary keys are located after the secondary key.
+ int start;
+ int stop;
+
+ // If a secondary-index search didn't generate SKs, set it to zero.
+ // Currently, only an inverted-index search doesn't generate any SKs.
+ boolean isNgramOrKeywordIndex = isInvertedIndex(index);
+ if (isNgramOrKeywordIndex) {
+ numSecondaryKeys = 0;
+ }
- // Assumes the primary keys are located at the end.
- int start = sourceVars.size() - numPrimaryKeys;
- int stop = sourceVars.size();
+ // Fetches keys: type 0 - PK, type 1 - SK, type 2 - the result of instantTryLock() on PK
+ switch (keyVarType) {
+ case PRIMARY_KEY:
+ // Fetches primary keys - the second position
+ start = numSecondaryKeys;
+ stop = numSecondaryKeys + numPrimaryKeys;
+ break;
+ case SECONDARY_KEY:
+ // Fetches secondary keys - the first position
+ start = 0;
+ stop = numSecondaryKeys;
+ break;
+ case CONDITIONAL_SPLIT_VAR:
+ // Sanity check - the given unnest map should generate this variable.
+ if (!abstractUnnestMapOp.getGenerateCallBackProceedResultVar()) {
+ throw CompilationException.create(ErrorCode.CANNOT_GET_CONDITIONAL_SPLIT_KEY_VARIABLE);
+ }
+ // Fetches conditional splitter - the last position
+ start = numSecondaryKeys + numPrimaryKeys;
+ stop = start + 1;
+ break;
+ default:
+ return Collections.emptyList();
+ }
for (int i = start; i < stop; i++) {
- primaryKeyVars.add(sourceVars.get(i));
+ keyVars.add(sourceVars.get(i));
}
- return primaryKeyVars;
+ return keyVars;
}
public static List<LogicalVariable> getPrimaryKeyVarsFromPrimaryUnnestMap(Dataset dataset,
@@ -384,10 +462,9 @@ public class AccessMethodUtils {
*
* @throws AlgebricksException
*/
- public static Pair<ILogicalExpression, Boolean> createSearchKeyExpr(Index index, IOptimizableFuncExpr optFuncExpr,
- IAType indexedFieldType, OptimizableOperatorSubTree indexSubTree, OptimizableOperatorSubTree probeSubTree)
+ public static Triple<ILogicalExpression, ILogicalExpression, Boolean> createSearchKeyExpr(Index index,
+ IOptimizableFuncExpr optFuncExpr, IAType indexedFieldType, OptimizableOperatorSubTree probeSubTree)
throws AlgebricksException {
-
if (probeSubTree == null) {
// We are optimizing a selection query. Search key is a constant.
// Type Checking and type promotion is done here
@@ -396,7 +473,7 @@ public class AccessMethodUtils {
//We are looking at a selection case, but using two variables
//This means that the second variable comes from a nonPure function call
//TODO: Right now we miss on type promotion for nonpure functions
- return new Pair<>(new VariableReferenceExpression(optFuncExpr.getLogicalVar(1)), false);
+ return new Triple<>(new VariableReferenceExpression(optFuncExpr.getLogicalVar(1)), null, false);
}
ILogicalExpression constantAtRuntimeExpression = optFuncExpr.getConstantExpr(0);
@@ -408,25 +485,103 @@ public class AccessMethodUtils {
ATypeTag constantValueTag = optFuncExpr.getConstantType(0).getTypeTag();
ATypeTag indexedFieldTypeTag = TypeComputeUtils.getActualType(indexedFieldType).getTypeTag();
- // if the constant type and target type does not match, we do a type conversion
- AsterixConstantValue replacedConstantValue = null;
// type casting happened from real (FLOAT, DOUBLE) value -> INT value?
boolean realTypeConvertedToIntegerType = false;
+ // constant value after type-casting is applied.
+ AsterixConstantValue replacedConstantValue = null;
+ // constant value after type-casting is applied - this value is used only for equality case.
+ // Refer to the following switch case for more details.
+ AsterixConstantValue replacedConstantValueForEQCase = null;
+ // If the constant type and target type does not match, we may need to do a type conversion.
if (constantValueTag != indexedFieldTypeTag && constantValue != null) {
- try {
- replacedConstantValue = ATypeHierarchy.getAsterixConstantValueFromNumericTypeObject(
- constantValue.getObject(), indexedFieldTypeTag, index.isEnforced());
- realTypeConvertedToIntegerType =
- isRealTypeConvertedToIntegerType(constantValueTag, indexedFieldTypeTag);
- } catch (HyracksDataException e) {
- throw new AlgebricksException(e);
+ // To check whether the constant is REAL values, and target field is an INT type field.
+ // In this case, we need to change the search parameter. Refer to the caller section for the detail.
+ realTypeConvertedToIntegerType =
+ isRealTypeConvertedToIntegerType(constantValueTag, indexedFieldTypeTag);
+ if (realTypeConvertedToIntegerType && !index.isEnforced() && !index.isOverridingKeyFieldTypes()) {
+ // For the index on a closed-type field,
+ // if a DOUBLE or FLOAT constant is converted to an INT type value,
+ // we need to check a corner case where two real values are located
+ // between an INT value. For example, the following query,
+ //
+ // for $emp in dataset empDataset
+ // where $emp.age > double("2.3") and $emp.age < double("3.3")
+ // return $emp.id;
+ //
+ // It should generate a result if there is a tuple that satisfies the condition,
+ // which is 3. However, it does not generate the desired result since finding
+ // candidates fails after truncating the fraction part
+ // (there is no INT whose value is greater than 2 and less than 3.)
+ //
+ // Thus,
+ // when converting FLOAT or DOUBLE values, we need to apply ceil() or floor().
+ // The following transformation will generate the final result, not a superset of it.
+ //
+ // LT
+ // IntVar < 4.9 ==> round-up: IntVar < 5
+ //
+ // LE
+ // IntVar <= 4.9 ==> round-down: IntVar <= 4
+ //
+ // GT
+ // IntVar > 4.9 ==> round-down: IntVar > 4
+ //
+ // GE
+ // IntVar >= 4.9 ==> round-up: IntVar >= 5
+ //
+ // EQ: two values are required to do a correct type-casting.
+ // IntVar = 4.3 ==> round-down and round-up: IntVar = 4 and IntVar = 5 : false
+ // IntVar = 4.0 ==> round-down and round-up: IntVar = 4 and IntVar = 4 : true
+ FunctionIdentifier functionID = optFuncExpr.getFuncExpr().getFunctionIdentifier();
+ ComparisonKind cKind = AlgebricksBuiltinFunctions.getComparisonType(functionID);
+
+ switch (cKind) {
+ case LT:
+ case GE:
+ // round-up
+ replacedConstantValue =
+ getReplacedConstantValue(constantValue.getObject(), constantValueTag,
+ indexedFieldTypeTag, index.isEnforced(), TypeCastingMathFunctionType.CEIL);
+ break;
+ case LE:
+ case GT:
+ // round-down
+ replacedConstantValue =
+ getReplacedConstantValue(constantValue.getObject(), constantValueTag,
+ indexedFieldTypeTag, index.isEnforced(), TypeCastingMathFunctionType.FLOOR);
+ break;
+ case EQ:
+ // equality case - both CEIL and FLOOR need to be applied.
+ replacedConstantValue =
+ getReplacedConstantValue(constantValue.getObject(), constantValueTag,
+ indexedFieldTypeTag, index.isEnforced(), TypeCastingMathFunctionType.FLOOR);
+ replacedConstantValueForEQCase =
+ getReplacedConstantValue(constantValue.getObject(), constantValueTag,
+ indexedFieldTypeTag, index.isEnforced(), TypeCastingMathFunctionType.CEIL);
+ break;
+ default:
+ // NEQ should not be a case.
+ throw new IllegalStateException();
+ }
+ } else if (!realTypeConvertedToIntegerType) {
+ // Type conversion only case: (e.g., INT -> BIGINT)
+ replacedConstantValue = getReplacedConstantValue(constantValue.getObject(), constantValueTag,
+ indexedFieldTypeTag, index.isEnforced(), TypeCastingMathFunctionType.NONE);
}
}
-
- return replacedConstantValue != null
- ? new Pair<>(new ConstantExpression(replacedConstantValue), realTypeConvertedToIntegerType)
- : new Pair<>(constantAtRuntimeExpression, false);
+ // No type-casting at all
+ if (replacedConstantValue == null) {
+ return new Triple<>(constantAtRuntimeExpression, null, false);
+ }
+ // A type-casting happened, but not EQ case
+ if (replacedConstantValueForEQCase == null) {
+ return new Triple<>(new ConstantExpression(replacedConstantValue), null,
+ realTypeConvertedToIntegerType);
+ }
+ // A type-casting happened and it's an EQ case.
+ return new Triple<>(new ConstantExpression(replacedConstantValue),
+ new ConstantExpression(replacedConstantValueForEQCase), realTypeConvertedToIntegerType);
} else {
// We are optimizing a join query. Determine which variable feeds the secondary index.
OptimizableOperatorSubTree opSubTree0 = optFuncExpr.getOperatorSubTree(0);
@@ -445,11 +600,22 @@ public class AccessMethodUtils {
TypeCastUtils.setRequiredAndInputTypes(castFunc, indexedFieldType, probeType);
boolean realTypeConvertedToIntegerType =
isRealTypeConvertedToIntegerType(probeTypeTypeTag, indexedFieldTypeTag);
- return new Pair<>(castFunc, realTypeConvertedToIntegerType);
+ return new Triple<>(castFunc, null, realTypeConvertedToIntegerType);
}
}
+ return new Triple<>(probeExpr, null, false);
+ }
+ }
- return new Pair<>(probeExpr, false);
+ private static AsterixConstantValue getReplacedConstantValue(IAObject sourceObject, ATypeTag sourceTypeTag,
+ ATypeTag targetTypeTag, boolean strictDemote, TypeCastingMathFunctionType mathFunction)
+ throws CompilationException {
+ try {
+ return ATypeHierarchy.getAsterixConstantValueFromNumericTypeObject(sourceObject, targetTypeTag,
+ strictDemote, mathFunction);
+ } catch (HyracksDataException e) {
+ throw new CompilationException(ErrorCode.ERROR_OCCURRED_BETWEEN_TWO_TYPES_CONVERSION, e, sourceTypeTag,
+ targetTypeTag);
}
}
@@ -490,10 +656,119 @@ public class AccessMethodUtils {
return indexExprs.get(0).second;
}
+ /**
+ * Checks whether the given function expression can utilize the given index.
+ * If so, checks the given join plan is an index-only plan or not.
+ */
+ public static boolean setIndexOnlyPlanInfo(List<Mutable<ILogicalOperator>> afterJoinRefs,
+ Mutable<ILogicalOperator> joinRef, OptimizableOperatorSubTree probeSubTree,
+ OptimizableOperatorSubTree indexSubTree, Index chosenIndex, AccessMethodAnalysisContext analysisCtx,
+ IOptimizationContext context, AbstractFunctionCallExpression funcExpr,
+ List<Pair<FunctionIdentifier, Boolean>> funcIdentifiers) throws AlgebricksException {
+ // index-only plan possible?
+ boolean isIndexOnlyPlan = false;
+
+ // Whether a verification (especially for R-Tree case) is required after the secondary index search
+ // In other words, can the chosen method generate any false positive results?
+ // Currently, for the B+ Tree index, there cannot be any false positive results except the composite index case.
+ boolean requireVerificationAfterSIdxSearch = false;
+
+ // Does the given index can cover all search predicates?
+ boolean doesSIdxSearchCoverAllPredicates = false;
+
+ Pair<Boolean, Boolean> functionFalsePositiveCheck =
+ AccessMethodUtils.canFunctionGenerateFalsePositiveResultsUsingIndex(funcExpr, funcIdentifiers);
+
+ if (functionFalsePositiveCheck.first) {
+ requireVerificationAfterSIdxSearch = functionFalsePositiveCheck.second;
+ } else {
+ // Function not found?
+ return false;
+ }
+
+ Quadruple<Boolean, Boolean, Boolean, Boolean> indexOnlyPlanInfo = new Quadruple<>(isIndexOnlyPlan, false,
+ requireVerificationAfterSIdxSearch, doesSIdxSearchCoverAllPredicates);
+
+ if (analysisCtx.getIndexDatasetMap().get(chosenIndex).getDatasetType() == DatasetType.INTERNAL) {
+ AccessMethodUtils.indexOnlyPlanCheck(afterJoinRefs, joinRef, indexSubTree, probeSubTree, chosenIndex,
+ analysisCtx, context, indexOnlyPlanInfo);
+ } else {
+ // We don't consider an index on an external dataset to be an index-only plan.
+ isIndexOnlyPlan = false;
+ indexOnlyPlanInfo.setFirst(isIndexOnlyPlan);
+ }
+
+ analysisCtx.setIndexOnlyPlanInfo(indexOnlyPlanInfo);
+
+ return true;
+ }
+
+ /**
+ * Finalizes the index-nested-loop join plan transformation.
+ */
+ public static boolean finalizeJoinPlanTransformation(List<Mutable<ILogicalOperator>> afterJoinRefs,
+ Mutable<ILogicalOperator> joinRef, OptimizableOperatorSubTree indexSubTree,
+ AccessMethodAnalysisContext analysisCtx, IOptimizationContext context, boolean isLeftOuterJoin,
+ boolean hasGroupBy, ILogicalOperator indexSearchOp, LogicalVariable newNullPlaceHolderVar,
+ Mutable<ILogicalExpression> conditionRef, Dataset dataset) throws AlgebricksException {
+ ILogicalOperator finalIndexSearchOp = indexSearchOp;
+ if (isLeftOuterJoin && hasGroupBy) {
+ ScalarFunctionCallExpression lojFuncExprs = analysisCtx.getLOJIsMissingFuncInGroupBy();
+ List<LogicalVariable> lojMissingVariables = new ArrayList<>();
+ lojFuncExprs.getUsedVariables(lojMissingVariables);
+ boolean lojMissingVarExist = false;
+ if (!lojMissingVariables.isEmpty()) {
+ lojMissingVarExist = true;
+ }
+
+ // Resets the missing place holder variable.
+ AccessMethodUtils.resetLOJMissingPlaceholderVarInGroupByOp(analysisCtx, newNullPlaceHolderVar, context);
+
+ // For the index-only plan, if newNullPlaceHolderVar is not in the variable map of the union operator
+ // or if the variable is removed during the above method, we need to refresh the variable mapping in UNION.
+ finalIndexSearchOp = AccessMethodUtils.resetVariableMappingInUnionOpInIndexOnlyPlan(lojMissingVarExist,
+ lojMissingVariables, indexSearchOp, afterJoinRefs, context);
+ }
+
+ boolean isIndexOnlyPlan = analysisCtx.getIndexOnlyPlanInfo().getFirst();
+ // If there are any left conditions, add a new select operator on top.
+ indexSubTree.getDataSourceRef().setValue(finalIndexSearchOp);
+ if (conditionRef.getValue() != null) {
+ // If an index-only plan is possible, the whole plan is now changed.
+ // Replaces the current path with the new index-only plan.
+ if (isIndexOnlyPlan && dataset.getDatasetType() == DatasetType.INTERNAL) {
+ // Gets the revised dataSourceRef operator from the secondary index-search.
+ ILogicalOperator dataSourceRefOp =
+ AccessMethodUtils.findDataSourceFromIndexUtilizationPlan(finalIndexSearchOp);
+ if (dataSourceRefOp != null && (dataSourceRefOp.getOperatorTag() == LogicalOperatorTag.UNNEST_MAP
+ || dataSourceRefOp.getOperatorTag() == LogicalOperatorTag.LEFT_OUTER_UNNEST_MAP)) {
+ indexSubTree.getDataSourceRef().setValue(dataSourceRefOp);
+ }
+ // Replaces the current operator with the newly created UNIONALL operator.
+ joinRef.setValue(finalIndexSearchOp);
+ } else {
+ // Non-index only plan case
+ indexSubTree.getDataSourceRef().setValue(finalIndexSearchOp);
+ SelectOperator topSelectOp = new SelectOperator(conditionRef, isLeftOuterJoin, newNullPlaceHolderVar);
+ topSelectOp.getInputs().add(indexSubTree.getRootRef());
+ topSelectOp.setExecutionMode(ExecutionMode.LOCAL);
+ context.computeAndSetTypeEnvironmentForOperator(topSelectOp);
+ joinRef.setValue(topSelectOp);
+ }
+ } else {
+ if (finalIndexSearchOp.getOperatorTag() == LogicalOperatorTag.UNIONALL) {
+ joinRef.setValue(finalIndexSearchOp);
+ } else {
+ joinRef.setValue(indexSubTree.getRootRef().getValue());
+ }
+ }
+ return true;
+ }
+
public static ILogicalOperator createSecondaryIndexUnnestMap(Dataset dataset, ARecordType recordType,
ARecordType metaRecordType, Index index, ILogicalOperator inputOp, AccessMethodJobGenParams jobGenParams,
- IOptimizationContext context, boolean outputPrimaryKeysOnly, boolean retainInput, boolean retainNull)
- throws AlgebricksException {
+ IOptimizationContext context, boolean retainInput, boolean retainNull,
+ boolean generateInstantTrylockResultFromIndexSearch) throws AlgebricksException {
// The job gen parameters are transferred to the actual job gen via the UnnestMapOperator's function arguments.
ArrayList<Mutable<ILogicalExpression>> secondaryIndexFuncArgs = new ArrayList<>();
jobGenParams.writeToFuncArgs(secondaryIndexFuncArgs);
@@ -501,17 +776,19 @@ public class AccessMethodUtils {
List<LogicalVariable> secondaryIndexUnnestVars = new ArrayList<>();
List<Object> secondaryIndexOutputTypes = new ArrayList<>();
// Append output variables/types generated by the secondary-index search (not forwarded from input).
- appendSecondaryIndexOutputVars(dataset, recordType, metaRecordType, index, outputPrimaryKeysOnly, context,
- secondaryIndexUnnestVars);
- appendSecondaryIndexTypes(dataset, recordType, metaRecordType, index, outputPrimaryKeysOnly,
- secondaryIndexOutputTypes);
+ // Output: SK, PK, [Optional: the result of instantTryLock]
+ appendSecondaryIndexOutputVars(dataset, recordType, metaRecordType, index, context, secondaryIndexUnnestVars,
+ generateInstantTrylockResultFromIndexSearch);
+ appendSecondaryIndexTypes(dataset, recordType, metaRecordType, index, secondaryIndexOutputTypes,
+ generateInstantTrylockResultFromIndexSearch);
// An index search is expressed as an unnest over an index-search function.
IFunctionInfo secondaryIndexSearch = FunctionUtil.getFunctionInfo(BuiltinFunctions.INDEX_SEARCH);
UnnestingFunctionCallExpression secondaryIndexSearchFunc =
new UnnestingFunctionCallExpression(secondaryIndexSearch, secondaryIndexFuncArgs);
secondaryIndexSearchFunc.setReturnsUniqueValues(true);
- // This is the operator that jobgen will be looking for. It contains an unnest function that has all necessary arguments to determine
- // which index to use, which variables contain the index-search keys, what is the original dataset, etc.
+ // This is the operator that jobgen will be looking for. It contains an unnest function that has all
+ // necessary arguments to determine which index to use, which variables contain the index-search keys,
+ // what is the original dataset, etc.
// Left-outer-join (retainInput and retainNull) case?
// Then, we use the LEFT-OUTER-UNNEST-MAP operator instead of unnest-map operator.
@@ -520,6 +797,8 @@ public class AccessMethodUtils {
LeftOuterUnnestMapOperator secondaryIndexLeftOuterUnnestOp = new LeftOuterUnnestMapOperator(
secondaryIndexUnnestVars, new MutableObject<ILogicalExpression>(secondaryIndexSearchFunc),
secondaryIndexOutputTypes, true);
+ secondaryIndexLeftOuterUnnestOp
+ .setGenerateCallBackProceedResultVar(generateInstantTrylockResultFromIndexSearch);
secondaryIndexLeftOuterUnnestOp.getInputs().add(new MutableObject<>(inputOp));
context.computeAndSetTypeEnvironmentForOperator(secondaryIndexLeftOuterUnnestOp);
secondaryIndexLeftOuterUnnestOp.setExecutionMode(ExecutionMode.PARTITIONED);
@@ -533,6 +812,7 @@ public class AccessMethodUtils {
UnnestMapOperator secondaryIndexUnnestOp = new UnnestMapOperator(secondaryIndexUnnestVars,
new MutableObject<ILogicalExpression>(secondaryIndexSearchFunc), secondaryIndexOutputTypes,
retainInput);
+ secondaryIndexUnnestOp.setGenerateCallBackProceedResultVar(generateInstantTrylockResultFromIndexSearch);
secondaryIndexUnnestOp.getInputs().add(new MutableObject<>(inputOp));
context.computeAndSetTypeEnvironmentForOperator(secondaryIndexUnnestOp);
secondaryIndexUnnestOp.setExecutionMode(ExecutionMode.PARTITIONED);
@@ -540,12 +820,11 @@ public class AccessMethodUtils {
}
}
- public static AbstractUnnestMapOperator createPrimaryIndexUnnestMap(AbstractDataSourceOperator dataSourceOp,
- Dataset dataset, ARecordType recordType, ARecordType metaRecordType, ILogicalOperator inputOp,
- IOptimizationContext context, boolean sortPrimaryKeys, boolean retainInput, boolean retainNull,
- boolean requiresBroadcast) throws AlgebricksException {
- List<LogicalVariable> primaryKeyVars =
- AccessMethodUtils.getPrimaryKeyVarsFromSecondaryUnnestMap(dataset, inputOp);
+ private static AbstractUnnestMapOperator createFinalNonIndexOnlySearchPlan(Dataset dataset,
+ ILogicalOperator inputOp, IOptimizationContext context, boolean sortPrimaryKeys, boolean retainInput,
+ boolean retainMissing, boolean requiresBroadcast, List<LogicalVariable> primaryKeyVars,
+ List<LogicalVariable> primaryIndexUnnestVars, List<Object> primaryIndexOutputTypes)
+ throws AlgebricksException {
// Optionally add a sort on the primary-index keys before searching the primary index.
OrderOperator order = null;
if (sortPrimaryKeys) {
@@ -559,6 +838,493 @@ public class AccessMethodUtils {
order.setExecutionMode(ExecutionMode.LOCAL);
context.computeAndSetTypeEnvironmentForOperator(order);
}
+ // Creates the primary-index search unnest-map operator.
+ AbstractUnnestMapOperator primaryIndexUnnestMapOp = createPrimaryIndexUnnestMapOp(dataset, retainInput,
+ retainMissing, requiresBroadcast, primaryKeyVars, primaryIndexUnnestVars, primaryIndexOutputTypes);
+ if (sortPrimaryKeys) {
+ primaryIndexUnnestMapOp.getInputs().add(new MutableObject<ILogicalOperator>(order));
+ } else {
+ primaryIndexUnnestMapOp.getInputs().add(new MutableObject<>(inputOp));
+ }
+ context.computeAndSetTypeEnvironmentForOperator(primaryIndexUnnestMapOp);
+ primaryIndexUnnestMapOp.setExecutionMode(ExecutionMode.PARTITIONED);
+ return primaryIndexUnnestMapOp;
+ }
+
+ private static ILogicalOperator createFinalIndexOnlySearchPlan(List<Mutable<ILogicalOperator>> afterTopOpRefs,
+ Mutable<ILogicalOperator> topOpRef, Mutable<ILogicalExpression> conditionRef,
+ List<Mutable<ILogicalOperator>> assignsBeforeTopOpRef, Dataset dataset, ARecordType recordType,
+ ARecordType metaRecordType, ILogicalOperator inputOp, IOptimizationContext context, boolean retainInput,
+ boolean retainMissing, boolean requiresBroadcast, Index secondaryIndex,
+ AccessMethodAnalysisContext analysisCtx, OptimizableOperatorSubTree subTree,
+ LogicalVariable newMissingPlaceHolderForLOJ, List<LogicalVariable> pkVarsFromSIdxUnnestMapOp,
+ List<LogicalVariable> primaryIndexUnnestVars, List<Object> primaryIndexOutputTypes)
+ throws AlgebricksException {
+ Quadruple<Boolean, Boolean, Boolean, Boolean> indexOnlyPlanInfo = analysisCtx.getIndexOnlyPlanInfo();
+ // From now on, we deal with the index-only plan.
+ // Initializes the information required for the index-only plan optimization.
+ // Fetches SK variable(s) from the secondary-index search operator.
+ List<LogicalVariable> skVarsFromSIdxUnnestMap = AccessMethodUtils.getKeyVarsFromSecondaryUnnestMap(dataset,
+ recordType, metaRecordType, inputOp, secondaryIndex, SecondaryUnnestMapOutputVarType.SECONDARY_KEY);
+ boolean skFieldUsedAfterTopOp = indexOnlyPlanInfo.getSecond();
+ boolean requireVerificationAfterSIdxSearch = indexOnlyPlanInfo.getThird();
+ ILogicalOperator assignBeforeTopOp;
+ UnionAllOperator unionAllOp;
+ SelectOperator newSelectOpInLeftPath;
+ SelectOperator newSelectOpInRightPath;
+ SplitOperator splitOp = null;
+ // This variable map will be used as input to UNIONALL operator. The form is <left, right, output>.
+ // In our case, left: instantTryLock fail path, right: instantTryLock success path
+ List<Triple<LogicalVariable, LogicalVariable, LogicalVariable>> unionVarMap = new ArrayList<>();
+ List<LogicalVariable> condSplitVars;
+ List<LogicalVariable> liveVarsAfterTopOp = new ArrayList<>();
+
+ // Constructs the variable mapping between newly constructed secondary
+ // key search (SK, PK) and those in the original plan (datasource scan).
+ LinkedHashMap<LogicalVariable, LogicalVariable> origVarToSIdxUnnestMapOpVarMap = new LinkedHashMap<>();
+
+ List<List<String>> chosenIndexFieldNames = secondaryIndex.getKeyFieldNames();
+ IndexType idxType = secondaryIndex.getIndexType();
+
+ // variables used in SELECT or JOIN operator
+ List<LogicalVariable> usedVarsInTopOp = new ArrayList<>();
+ List<LogicalVariable> uniqueUsedVarsInTopOp = new ArrayList<>();
+
+ // variables used in ASSIGN before SELECT operator
+ List<LogicalVariable> producedVarsInAssignsBeforeTopOp = new ArrayList<>();
+
+ // For the index-nested-loop join case, we need to exclude the variables from the left (outer) branch
+ // when deciding which variables should be propagated via UNIONALL operator.
+ // This is because these variables are already generated and is not related to the decision
+ // whether the plan is an index-only plan or not. Only the right (inner) branch matters.
+ List<LogicalVariable> liveVarsInSubTreeRootOp = new ArrayList<>();
+
+ // variables used after SELECT or JOIN operator
+ List<LogicalVariable> usedVarsAfterTopOp = new ArrayList<>();
+ List<LogicalVariable> varsTmpList = new ArrayList<>();
+
+ // If the secondary key field is used after SELECT or JOIN operator (e.g., returning the field value),
+ // then we need to keep these secondary keys. In case of R-tree index, the result of an R-tree
+ // index search is an MBR. So, we need to reconstruct original field values from the result if that index
+ // is on a rectangle or point.
+ AssignOperator skVarAssignOpInRightPath = null;
+ List<LogicalVariable> restoredSKVarFromRTree = null;
+ // Original SK field variable to restored SK field variable in the right path mapping
+ LinkedHashMap<LogicalVariable, LogicalVariable> origSKFieldVarToNewSKFieldVarMap = new LinkedHashMap<>();
+ // Index-only plan consideration for the R-Tree index only:
+ // Constructs an additional ASSIGN to restore the original secondary key field(s) from
+ // the results of the secondary index search in case the field is used after SELECT or JOIN operator or
+ // a verification is required since the given query shape is not RECTANGLE or POINT even though the type of
+ // index is RECTANGLE or POINT (in this case only, removing false-positive is possible.).
+ if (idxType == IndexType.RTREE && (skFieldUsedAfterTopOp || requireVerificationAfterSIdxSearch)) {
+ IOptimizableFuncExpr optFuncExpr = AccessMethodUtils.chooseFirstOptFuncExpr(secondaryIndex, analysisCtx);
+ int optFieldIdx = AccessMethodUtils.chooseFirstOptFuncVar(secondaryIndex, analysisCtx);
+ Pair<IAType, Boolean> keyPairType = Index.getNonNullableOpenFieldType(optFuncExpr.getFieldType(optFieldIdx),
+ optFuncExpr.getFieldName(optFieldIdx), recordType);
+ if (keyPairType == null) {
+ return null;
+ }
+ // Gets the number of dimensions corresponding to the field indexed by chosenIndex.
+ IAType spatialType = keyPairType.first;
+ ArrayList<Mutable<ILogicalExpression>> restoredSKFromRTreeExprs = new ArrayList<>();
+ restoredSKVarFromRTree = new ArrayList<>();
+ switch (spatialType.getTypeTag()) {
+ case POINT:
+ // Reconstructs a POINT value.
+ AbstractFunctionCallExpression createPointExpr = createPointExpression(skVarsFromSIdxUnnestMap);
+ restoredSKVarFromRTree.add(context.newVar());
+ restoredSKFromRTreeExprs.add(new MutableObject<ILogicalExpression>(createPointExpr));
+ skVarAssignOpInRightPath = new AssignOperator(restoredSKVarFromRTree, restoredSKFromRTreeExprs);
+ break;
+ case RECTANGLE:
+ // Reconstructs a RECTANGLE value.
+ AbstractFunctionCallExpression expr1 = createPointExpression(skVarsFromSIdxUnnestMap.subList(0, 2));
+ AbstractFunctionCallExpression expr2 = createPointExpression(skVarsFromSIdxUnnestMap.subList(2, 4));
+ AbstractFunctionCallExpression createRectangleExpr = createRectangleExpression(expr1, expr2);
+ restoredSKVarFromRTree.add(context.newVar());
+ restoredSKFromRTreeExprs.add(new MutableObject<ILogicalExpression>(createRectangleExpr));
+ skVarAssignOpInRightPath = new AssignOperator(restoredSKVarFromRTree, restoredSKFromRTreeExprs);
+ break;
+ default:
+ break;
+ }
+ }
+
+ // Gets all variables from the right (inner) branch.
+ VariableUtilities.getLiveVariables((ILogicalOperator) subTree.getRootRef().getValue(), liveVarsInSubTreeRootOp);
+ // Gets the used variables from the SELECT or JOIN operator.
+ VariableUtilities.getUsedVariables((ILogicalOperator) topOpRef.getValue(), usedVarsInTopOp);
+ // Excludes the variables in the condition from the outer branch - in join case.
+ for (Iterator<LogicalVariable> iterator = usedVarsInTopOp.iterator(); iterator.hasNext();) {
+ LogicalVariable v = iterator.next();
+ if (!liveVarsInSubTreeRootOp.contains(v)) {
+ iterator.remove();
+ }
+ }
+ // Keeps the unique used variables in the SELECT or JOIN operator.
+ copyVarsToAnotherList(usedVarsInTopOp, uniqueUsedVarsInTopOp);
+
+ // If there are ASSIGN operators (usually secondary key field) before the given SELECT or JOIN operator,
+ // we may need to propagate these produced variables via the UNIONALL operator if they are used afterwards.
+ if (assignsBeforeTopOpRef != null && !assignsBeforeTopOpRef.isEmpty()) {
+ for (int i = 0; i < assignsBeforeTopOpRef.size(); i++) {
+ assignBeforeTopOp = assignsBeforeTopOpRef.get(i).getValue();
+ varsTmpList.clear();
+ VariableUtilities.getProducedVariables(assignBeforeTopOp, varsTmpList);
+ copyVarsToAnotherList(varsTmpList, producedVarsInAssignsBeforeTopOp);
+ }
+ }
+
+ // Adds an optional ASSIGN operator that sits right after the SELECT or JOIN operator.
+ // This assign operator keeps any constant expression(s) extracted from the original ASSIGN operators
+ // in the subtree and are used after the SELECT or JOIN operator. In usual case,
+ // this constant value would be used in a group-by after a left-outer-join and will be removed by the optimizer.
+ // We need to conduct this since this variable does not have to be in the both branch of an index-only plan.
+ AssignOperator constAssignOp = null;
+ ILogicalOperator currentOpAfterTopOp = null;
+ List<LogicalVariable> constAssignVars = new ArrayList<>();
+ List<Mutable<ILogicalExpression>> constAssignExprs = new ArrayList<>();
+ ILogicalOperator currentOp = inputOp;
+
+ boolean constantAssignVarUsedInTopOp = false;
+ if (assignsBeforeTopOpRef != null) {
+ // From the first ASSIGN (earliest in the plan) to the last ASSGIN (latest)
+ for (int i = assignsBeforeTopOpRef.size() - 1; i >= 0; i--) {
+ AssignOperator tmpOp = (AssignOperator) assignsBeforeTopOpRef.get(i).getValue();
+ List<LogicalVariable> tmpAssignVars = tmpOp.getVariables();
+ List<Mutable<ILogicalExpression>> tmpAsssignExprs = tmpOp.getExpressions();
+ Iterator<LogicalVariable> varIt = tmpAssignVars.iterator();
+ Iterator<Mutable<ILogicalExpression>> exprIt = tmpAsssignExprs.iterator();
+ boolean changed = false;
+ while (exprIt.hasNext()) {
+ Mutable<ILogicalExpression> tmpExpr = exprIt.next();
+ LogicalVariable tmpVar = varIt.next();
+ if (tmpExpr.getValue().getExpressionTag() == LogicalExpressionTag.CONSTANT) {
+ constAssignVars.add(tmpVar);
+ constAssignExprs.add(tmpExpr);
+ varIt.remove();
+ exprIt.remove();
+ changed = true;
+ }
+ }
+ if (changed) {
+ context.computeAndSetTypeEnvironmentForOperator(tmpOp);
+ }
+ }
+
+ if (!constAssignVars.isEmpty()) {
+ // These constants should not be used in the SELECT or JOIN operator.
+ for (LogicalVariable v : constAssignVars) {
+ if (usedVarsInTopOp.contains(v)) {
+ constantAssignVarUsedInTopOp = true;
+ break;
+ }
+ }
+ // If this assign operator is not used in the SELECT or JOIN operator,
+ // we will add this operator after creating UNION operator in the last part of this method.
+ constAssignOp = new AssignOperator(constAssignVars, constAssignExprs);
+ if (constantAssignVarUsedInTopOp) {
+ // Places this assign after the secondary index-search op.
+ constAssignOp.getInputs().add(new MutableObject<ILogicalOperator>(inputOp));
+ constAssignOp.setExecutionMode(ExecutionMode.PARTITIONED);
+ context.computeAndSetTypeEnvironmentForOperator(constAssignOp);
+ currentOp = constAssignOp;
+ }
+ }
+ }
+
+ // variables used after SELECT or JOIN operator
+ HashSet<LogicalVariable> varsTmpSet = new HashSet<>();
+ if (afterTopOpRefs != null) {
+ for (Mutable<ILogicalOperator> afterTopOpRef : afterTopOpRefs) {
+ varsTmpSet.clear();
+ OperatorPropertiesUtil.getFreeVariablesInOp((ILogicalOperator) afterTopOpRef.getValue(), varsTmpSet);
+ copyVarsToAnotherList(varsTmpSet, usedVarsAfterTopOp);
+ }
+ }
+
+ // Now, adds a SPLIT operator to propagate <SK, PK> pair from the secondary-index search to the two paths.
+ // And constructs the path from the secondary index search to the SPLIT operator.
+
+ // Fetches the conditional split variable from the secondary-index search
+ condSplitVars = AccessMethodUtils.getKeyVarsFromSecondaryUnnestMap(dataset, recordType, metaRecordType, inputOp,
+ secondaryIndex, SecondaryUnnestMapOutputVarType.CONDITIONAL_SPLIT_VAR);
+
+ // Adds a SPLIT operator after the given secondary index-search unnest-map operator.
+ splitOp = new SplitOperator(2,
+ new MutableObject<ILogicalExpression>(new VariableReferenceExpression(condSplitVars.get(0))));
+ splitOp.getInputs().add(new MutableObject<ILogicalOperator>(currentOp));
+ splitOp.setExecutionMode(ExecutionMode.PARTITIONED);
+ context.computeAndSetTypeEnvironmentForOperator(splitOp);
+
+ // To maintain SSA, we assign new variables for the incoming variables in the left branch
+ // since the most tuples go to the right branch (instantTryLock success path). Also, the output of
+ // UNIONALL should be a new variable. (it cannot be the same to the left or right variable.)
+
+ // Original variables (before SPLIT) to the variables in the left path mapping
+ LinkedHashMap<LogicalVariable, LogicalVariable> liveVarAfterSplitToLeftPathMap = new LinkedHashMap<>();
+ // output variables to the variables generated in the left branch mapping
+ LinkedHashMap<LogicalVariable, LogicalVariable> origPKRecAndSKVarToleftPathMap = new LinkedHashMap<>();
+ // Original variables (before SPLIT) to the output variables mapping (mainly for join case)
+ LinkedHashMap<LogicalVariable, LogicalVariable> origVarToOutputVarMap = new LinkedHashMap<>();
+ List<LogicalVariable> liveVarsAfterSplitOp = new ArrayList<>();
+ VariableUtilities.getLiveVariables(splitOp, liveVarsAfterSplitOp);
+
+ ArrayList<LogicalVariable> assignVars = new ArrayList<>();
+ ArrayList<Mutable<ILogicalExpression>> assignExprs = new ArrayList<>();
+ for (LogicalVariable v : liveVarsAfterSplitOp) {
+ LogicalVariable newVar = context.newVar();
+ liveVarAfterSplitToLeftPathMap.put(v, newVar);
+ assignVars.add(newVar);
+ assignExprs.add(new MutableObject<ILogicalExpression>(new VariableReferenceExpression(v)));
+ }
+ AssignOperator origVarsToLeftPathVarsAssignOp = new AssignOperator(assignVars, assignExprs);
+ origVarsToLeftPathVarsAssignOp.getInputs().add(new MutableObject<ILogicalOperator>(splitOp));
+ context.computeAndSetTypeEnvironmentForOperator(origVarsToLeftPathVarsAssignOp);
+ origVarsToLeftPathVarsAssignOp.setExecutionMode(ExecutionMode.PARTITIONED);
+
+ // Creates the variable mapping for the UNIONALL operator.
+
+ // PK Variable(s) that will be fed into the primary index-search has been re-assigned in the left path.
+ List<LogicalVariable> pkVarsInLeftPathFromSIdxSearchBeforeSplit = new ArrayList<>();
+ for (LogicalVariable v : pkVarsFromSIdxUnnestMapOp) {
+ pkVarsInLeftPathFromSIdxSearchBeforeSplit.add(liveVarAfterSplitToLeftPathMap.get(v));
+ }
+ // PK and Record variable(s) from the primary-index search will be reassigned in the left path
+ // to make the output of the UNIONALL the original variables from the data-scan.
+ List<LogicalVariable> pkVarsFromPIdxSearchInLeftPath = new ArrayList<>();
+ for (int i = 0; i < primaryIndexUnnestVars.size(); i++) {
+ LogicalVariable replacedVar = context.newVar();
+ pkVarsFromPIdxSearchInLeftPath.add(replacedVar);
+ origPKRecAndSKVarToleftPathMap.put(primaryIndexUnnestVars.get(i), replacedVar);
+ }
+
+ // Are the used variables after SELECT or JOIN operator from the primary index?
+ // Then, creates the variable mapping between two paths.
+ for (LogicalVariable tVar : usedVarsAfterTopOp) {
+ // Checks whether this variable is already added to the union variable map.
+ // It should be also a part of the primary key variables.
+ if (findVarInTripleVarList(unionVarMap, tVar, false) || !primaryIndexUnnestVars.contains(tVar)) {
+ continue;
+ }
+ int pIndexPKIdx = primaryIndexUnnestVars.indexOf(tVar);
+ // If the above value is -1, either it is a secondary key variable or a variable
+ // from different branch (join case). These cases will be dealt with later.
+ if (pIndexPKIdx == -1) {
+ continue;
+ }
+ unionVarMap.add(new Triple<>(pkVarsFromPIdxSearchInLeftPath.get(pIndexPKIdx),
+ pkVarsFromSIdxUnnestMapOp.get(pIndexPKIdx), tVar));
+ origVarToOutputVarMap.put(pkVarsFromSIdxUnnestMapOp.get(pIndexPKIdx), tVar);
+
+ // Constructs the mapping between the PK from the original data-scan to the PK
+ // from the secondary index search since they are different logical variables.
+ origVarToSIdxUnnestMapOpVarMap.put(tVar, pkVarsFromSIdxUnnestMapOp.get(pIndexPKIdx));
+ }
+
+ // Are the used variables after SELECT or JOIN operator from the given secondary index?
+ for (LogicalVariable tVar : usedVarsAfterTopOp) {
+ // Checks whether this variable is already added to the union variable map.
+ if (findVarInTripleVarList(unionVarMap, tVar, false)) {
+ continue;
+ }
+ // Should be either used in the condition or a composite index field that is not used in the condition.
+ if (!usedVarsInTopOp.contains(tVar) && !producedVarsInAssignsBeforeTopOp.contains(tVar)) {
+ continue;
+ }
+ int sIndexIdx = chosenIndexFieldNames.indexOf(subTree.getVarsToFieldNameMap().get(tVar));
+ // For the join-case, the match might not exist.
+ // In this case, we just propagate the variables later.
+ if (sIndexIdx == -1) {
+ continue;
+ }
+ if (idxType == IndexType.RTREE) {
+ // R-Tree case: we need this variable in case if we need to do an additional verification,
+ // or the secondary key field is used after SELECT or JOIN operator.
+ // We need to use the re-constructed secondary key from the result (an MBR) of R-Tree search.
+ // For the join case, the match might not exist.
+ // In this case, we just propagate the variables later.
+ if (!skFieldUsedAfterTopOp && !requireVerificationAfterSIdxSearch) {
+ continue;
+ }
+ LogicalVariable replacedVar = context.newVar();
+ origPKRecAndSKVarToleftPathMap.put(tVar, replacedVar);
+ origSKFieldVarToNewSKFieldVarMap.put(tVar, restoredSKVarFromRTree.get(sIndexIdx));
+ unionVarMap.add(new Triple<>(replacedVar, restoredSKVarFromRTree.get(sIndexIdx), tVar));
+ continue;
+ }
+ // B-Tree case:
+ LogicalVariable replacedVar = context.newVar();
+ origPKRecAndSKVarToleftPathMap.put(tVar, replacedVar);
+ origVarToOutputVarMap.put(skVarsFromSIdxUnnestMap.get(sIndexIdx), tVar);
+ unionVarMap.add(new Triple<LogicalVariable, LogicalVariable, LogicalVariable>(replacedVar,
+ skVarsFromSIdxUnnestMap.get(sIndexIdx), tVar));
+ // Constructs the mapping between the SK from the original data-scan
+ // and the SK from the secondary index search since they are different logical variables.
+ origVarToSIdxUnnestMapOpVarMap.put(tVar, skVarsFromSIdxUnnestMap.get(sIndexIdx));
+ }
+
+ // For R-Tree case: if the given secondary key field variable is used only in the select or join condition,
+ // we were not able to catch the mapping between the original secondary key field and the newly restored
+ // secondary key field in the assign operator in the right path.
+ if (idxType == IndexType.RTREE && (skFieldUsedAfterTopOp || requireVerificationAfterSIdxSearch)) {
+ for (LogicalVariable v : uniqueUsedVarsInTopOp) {
+ if (!primaryIndexUnnestVars.contains(v)) {
+ origSKFieldVarToNewSKFieldVarMap.put(v, restoredSKVarFromRTree.get(0));
+ }
+ }
+ }
+
+ // For the index-nested-loop join case,
+ // we propagate all variables that come from the outer relation and are used after join operator.
+ // Adds the variables that are both live after JOIN and used after the JOIN operator.
+ VariableUtilities.getLiveVariables((ILogicalOperator) topOpRef.getValue(), liveVarsAfterTopOp);
+ for (LogicalVariable v : usedVarsAfterTopOp) {
+ if (!liveVarsAfterTopOp.contains(v) || findVarInTripleVarList(unionVarMap, v, false)) {
+ continue;
+ }
+ LogicalVariable outputVar = context.newVar();
+ origVarToOutputVarMap.put(v, outputVar);
+ unionVarMap.add(new Triple<>(liveVarAfterSplitToLeftPathMap.get(v), v, outputVar));
+ }
+
+ // Replaces the original variables in the operators after the SELECT or JOIN operator to satisfy SSA.
+ if (afterTopOpRefs != null) {
+ for (Mutable<ILogicalOperator> afterTopOpRef : afterTopOpRefs) {
+ VariableUtilities.substituteVariables((ILogicalOperator) afterTopOpRef.getValue(),
+ origVarToOutputVarMap, context);
+ }
+ }
+
+ // Creates the primary index lookup operator.
+ // The job gen parameters are transferred to the actual job gen via the UnnestMapOperator's function arguments.
+ AbstractUnnestMapOperator primaryIndexUnnestMapOp = createPrimaryIndexUnnestMapOp(dataset, retainInput,
+ retainMissing, requiresBroadcast, pkVarsInLeftPathFromSIdxSearchBeforeSplit,
+ pkVarsFromPIdxSearchInLeftPath, primaryIndexOutputTypes);
+ primaryIndexUnnestMapOp.getInputs().add(new MutableObject<ILogicalOperator>(origVarsToLeftPathVarsAssignOp));
+ context.computeAndSetTypeEnvironmentForOperator(primaryIndexUnnestMapOp);
+ primaryIndexUnnestMapOp.setExecutionMode(ExecutionMode.PARTITIONED);
+
+ // Now, generates the UnionAllOperator to merge the left and right paths.
+ // If we are transforming a join, in the instantTryLock on PK fail path, a SELECT operator should be
+ // constructed from the join condition and placed after the primary index lookup
+ // to do the final verification. If this is a select plan, we just need to use the original
+ // SELECT operator after the primary index lookup to do the final verification.
+ LinkedHashMap<LogicalVariable, LogicalVariable> origVarToNewVarInLeftPathMap = new LinkedHashMap<>();
+ origVarToNewVarInLeftPathMap.putAll(liveVarAfterSplitToLeftPathMap);
+ origVarToNewVarInLeftPathMap.putAll(origPKRecAndSKVarToleftPathMap);
+ ILogicalExpression conditionRefExpr = conditionRef.getValue().cloneExpression();
+ // The retainMissing variable contains the information whether we are optimizing a left-outer join or not.
+ LogicalVariable newMissingPlaceHolderVar = retainMissing ? newMissingPlaceHolderForLOJ : null;
+ newSelectOpInLeftPath = new SelectOperator(new MutableObject<ILogicalExpression>(conditionRefExpr),
+ retainMissing, newMissingPlaceHolderVar);
+ VariableUtilities.substituteVariables(newSelectOpInLeftPath, origVarToNewVarInLeftPathMap, context);
+
+ // If there are ASSIGN operators before the SELECT or JOIN operator,
+ // we need to put these operators between the SELECT or JOIN and the primary index lookup in the left path.
+ if (assignsBeforeTopOpRef != null) {
+ // Makes the primary unnest-map as the child of the last ASSIGN (from top) in the path.
+ assignBeforeTopOp = assignsBeforeTopOpRef.get(assignsBeforeTopOpRef.size() - 1).getValue();
+ assignBeforeTopOp.getInputs().clear();
+ assignBeforeTopOp.getInputs().add(new MutableObject<ILogicalOperator>(primaryIndexUnnestMapOp));
+
+ // Makes the first ASSIGN (from top) as the child of the SELECT operator.
+ for (int i = assignsBeforeTopOpRef.size() - 1; i >= 0; i--) {
+ if (assignsBeforeTopOpRef.get(i) != null) {
+ AbstractLogicalOperator assignTmpOp =
+ (AbstractLogicalOperator) assignsBeforeTopOpRef.get(i).getValue();
+ assignTmpOp.setExecutionMode(ExecutionMode.PARTITIONED);
+ VariableUtilities.substituteVariables(assignTmpOp, origVarToNewVarInLeftPathMap, context);
+ context.computeAndSetTypeEnvironmentForOperator(assignTmpOp);
+ }
+ }
+ newSelectOpInLeftPath.getInputs().clear();
+ newSelectOpInLeftPath.getInputs()
+ .add(new MutableObject<ILogicalOperator>(assignsBeforeTopOpRef.get(0).getValue()));
+ } else {
+ newSelectOpInLeftPath.getInputs().add(new MutableObject<ILogicalOperator>(primaryIndexUnnestMapOp));
+ }
+ newSelectOpInLeftPath.setExecutionMode(ExecutionMode.PARTITIONED);
+ context.computeAndSetTypeEnvironmentForOperator(newSelectOpInLeftPath);
+
+ // Now, we take care of the right path (instantTryLock on PK success path).
+ ILogicalOperator currentTopOpInRightPath = splitOp;
+ // For an R-Tree index, if there are operators that are using the secondary key field value,
+ // we need to reconstruct that field value from the result of R-Tree search.
+ // This is done by adding the following assign operator that we have made in the beginning of this method.
+ if (skVarAssignOpInRightPath != null) {
+ skVarAssignOpInRightPath.getInputs().add(new MutableObject<ILogicalOperator>(splitOp));
+ skVarAssignOpInRightPath.setExecutionMode(ExecutionMode.PARTITIONED);
+ context.computeAndSetTypeEnvironmentForOperator(skVarAssignOpInRightPath);
+ currentTopOpInRightPath = skVarAssignOpInRightPath;
+ }
+
+ // For an R-Tree index, if the given query shape is not RECTANGLE or POINT,
+ // we need to add the original SELECT operator to filter out the false positive results.
+ // (e.g., spatial-intersect($o.pointfield, create-circle(create-point(30.0,70.0), 5.0)) )
+ //
+ // Also, for a B-Tree composite index, we need to apply SELECT operators in the right path
+ // to remove any false positive results from the secondary composite index search.
+ //
+ // Lastly, if there is an index-nested-loop-join and the join contains more conditions
+ // other than joining fields, then those conditions need to be applied to filter out
+ // false positive results in the right path.
+ // (e.g., where $a.authors /*+ indexnl */ = $b.authors and $a.id = $b.id <- authors:SK, id:PK)
+ if ((idxType == IndexType.RTREE || uniqueUsedVarsInTopOp.size() > 1) && requireVerificationAfterSIdxSearch) {
+ // Creates a new SELECT operator by deep-copying the SELECT operator in the left path
+ // since we need to change the variable reference in the SELECT operator.
+ // For the index-nested-loop join case, we copy the condition of the join operator.
+ ILogicalExpression conditionRefExpr2 = conditionRef.getValue().cloneExpression();
+ newSelectOpInRightPath = new SelectOperator(new MutableObject<ILogicalExpression>(conditionRefExpr2),
+ retainMissing, newMissingPlaceHolderVar);
+ newSelectOpInRightPath.getInputs().add(new MutableObject<ILogicalOperator>(currentTopOpInRightPath));
+ VariableUtilities.substituteVariables(newSelectOpInRightPath, origVarToSIdxUnnestMapOpVarMap, context);
+ VariableUtilities.substituteVariables(newSelectOpInRightPath, origSKFieldVarToNewSKFieldVarMap, context);
+ newSelectOpInRightPath.setExecutionMode(ExecutionMode.PARTITIONED);
+ context.computeAndSetTypeEnvironmentForOperator(newSelectOpInRightPath);
+ currentTopOpInRightPath = newSelectOpInRightPath;
+ }
+
+ // Adds the new missing place holder in case of a left-outer-join if it's not been added yet.
+ // The assumption here is that this variable is the first PK variable that was set.
+ if (retainMissing && newMissingPlaceHolderForLOJ == primaryIndexUnnestVars.get(0)
+ && !findVarInTripleVarList(unionVarMap, newMissingPlaceHolderForLOJ, false)) {
+ unionVarMap.add(new Triple<>(origPKRecAndSKVarToleftPathMap.get(newMissingPlaceHolderForLOJ),
+ pkVarsFromSIdxUnnestMapOp.get(0), newMissingPlaceHolderForLOJ));
+ }
+
+ // UNIONALL operator that combines both paths.
+ unionAllOp = new UnionAllOperator(unionVarMap);
+ unionAllOp.getInputs().add(new MutableObject<ILogicalOperator>(newSelectOpInLeftPath));
+ unionAllOp.getInputs().add(new MutableObject<ILogicalOperator>(currentTopOpInRightPath));
+
+ unionAllOp.setExecutionMode(ExecutionMode.PARTITIONED);
+ context.computeAndSetTypeEnvironmentForOperator(unionAllOp);
+
+ // If an assign operator that keeps constant values was added, set the UNIONALL operator as its child.
+ if (!constAssignVars.isEmpty() && !constantAssignVarUsedInTopOp) {
+ constAssignOp.getInputs().clear();
+ constAssignOp.getInputs().add(new MutableObject<ILogicalOperator>(unionAllOp));
+ constAssignOp.setExecutionMode(ExecutionMode.PARTITIONED);
+ context.computeAndSetTypeEnvironmentForOperator(constAssignOp);
+
+ // This constant assign operator is the new child of the first operator after the original
+ // SELECT or JOIN operator.
+ currentOpAfterTopOp = afterTopOpRefs.get(afterTopOpRefs.size() - 1).getValue();
+ currentOpAfterTopOp.getInputs().clear();
+ currentOpAfterTopOp.getInputs().add(new MutableObject<ILogicalOperator>(constAssignOp));
+ context.computeAndSetTypeEnvironmentForOperator(currentOpAfterTopOp);
+ afterTopOpRefs.add(new MutableObject<ILogicalOperator>(constAssignOp));
+ }
+
+ // Index-only plan is now constructed. Return this operator to the caller.
+ return unionAllOp;
+ }
+
+ private static AbstractUnnestMapOperator createPrimaryIndexUnnestMapOp(Dataset dataset, boolean retainInput,
+ boolean retainMissing, boolean requiresBroadcast, List<LogicalVariable> primaryKeyVars,
+ List<LogicalVariable> primaryIndexUnnestVars, List<Object> primaryIndexOutputTypes)
+ throws AlgebricksException {
// The job gen parameters are transferred to the actual job gen via the UnnestMapOperator's function arguments.
List<Mutable<ILogicalExpression>> primaryIndexFuncArgs = new ArrayList<>();
BTreeJobGenParams jobGenParams = new BTreeJobGenParams(dataset.getDatasetName(), IndexType.BTREE,
@@ -570,22 +1336,17 @@ public class AccessMethodUtils {
jobGenParams.setHighKeyVarList(primaryKeyVars, 0, primaryKeyVars.size());
jobGenParams.setIsEqCondition(true);
jobGenParams.writeToFuncArgs(primaryIndexFuncArgs);
- // Variables and types coming out of the primary-index search.
- List<LogicalVariable> primaryIndexUnnestVars = new ArrayList<>();
- List<Object> primaryIndexOutputTypes = new ArrayList<>();
- // Append output variables/types generated by the primary-index search (not forwarded from input).
- primaryIndexUnnestVars.addAll(dataSourceOp.getVariables());
- appendPrimaryIndexTypes(dataset, recordType, metaRecordType, primaryIndexOutputTypes);
// An index search is expressed as an unnest over an index-search function.
IFunctionInfo primaryIndexSearch = FunctionUtil.getFunctionInfo(BuiltinFunctions.INDEX_SEARCH);
AbstractFunctionCallExpression primaryIndexSearchFunc =
new ScalarFunctionCallExpression(primaryIndexSearch, primaryIndexFuncArgs);
- // This is the operator that jobgen will be looking for. It contains an unnest function that has all necessary arguments to determine
- // which index to use, which variables contain the index-search keys, what is the original dataset, etc.
- AbstractUnnestMapOperator primaryIndexUnnestOp = null;
- if (retainNull) {
+ // This is the operator that jobgen will be looking for. It contains an unnest function that has
+ // all necessary arguments to determine which index to use, which variables contain the index-search keys,
+ // what is the original dataset, etc.
+ AbstractUnnestMapOperator primaryIndexUnnestMapOp = null;
+ if (retainMissing) {
if (retainInput) {
- primaryIndexUnnestOp = new LeftOuterUnnestMapOperator(primaryIndexUnnestVars,
+ primaryIndexUnnestMapOp = new LeftOuterUnnestMapOperator(primaryIndexUnnestVars,
new MutableObject<ILogicalExpression>(primaryIndexSearchFunc), primaryIndexOutputTypes,
retainInput);
} else {
@@ -593,29 +1354,98 @@ public class AccessMethodUtils {
throw new AlgebricksException("Left-outer-join should propagate all inputs from the outer branch.");
}
} else {
- primaryIndexUnnestOp = new UnnestMapOperator(primaryIndexUnnestVars,
+ primaryIndexUnnestMapOp = new UnnestMapOperator(primaryIndexUnnestVars,
new MutableObject<ILogicalExpression>(primaryIndexSearchFunc), primaryIndexOutputTypes,
retainInput);
}
- // Fed by the order operator or the secondaryIndexUnnestOp.
- if (sortPrimaryKeys) {
- primaryIndexUnnestOp.getInputs().add(new MutableObject<ILogicalOperator>(order));
+ return primaryIndexUnnestMapOp;
+ }
+
+ /**
+ * Creates operators that do a primary index lookup in the plan. In case of an index-only plan,
+ * this creates two paths including the primary index lookup in the left path.
+ * If this is an index-only plan (only using PK and/or secondary field(s) after SELECT operator) and/or
+ * the combination of the SELECT (JOIN) condition and the chosen secondary index do not generate
+ * false positive results, we can apply instantTryLock() on PK optimization since a result from these indexes
+ * doesn't have to be verified by the primary index-lookup and a subsequent SELECT operator.
+ * (i.e., we can guarantee the correctness of the result.)
+ *
+ * Case A) non-index-only plan
+ * sidx-search -> (optional) sort -> pdix-search
+ *
+ * Case B) index-only plan
+ * left path (an instantTryLock() on the PK fail path):
+ * right path(an instantTryLock() on the PK success path):
+ * (left) sidx-search -> assign? -> split -> primary index-search -> select (verification) -> union ->
+ * (right) ........................ split -> assign? -> select? -> .......................... union ...
+ */
+ public static ILogicalOperator createRestOfIndexSearchPlan(List<Mutable<ILogicalOperator>> afterTopOpRefs,
+ Mutable<ILogicalOperator> topOpRef, Mutable<ILogicalExpression> conditionRef,
+ List<Mutable<ILogicalOperator>> assignsBeforeTopOpRef, AbstractDataSourceOperator dataSourceOp,
+ Dataset dataset, ARecordType recordType, ARecordType metaRecordType, ILogicalOperator inputOp,
+ IOptimizationContext context, boolean sortPrimaryKeys, boolean retainInput, boolean retainMissing,
+ boolean requiresBroadcast, Index secondaryIndex, AccessMethodAnalysisContext analysisCtx,
+ OptimizableOperatorSubTree subTree, LogicalVariable newMissingPlaceHolderForLOJ)
+ throws AlgebricksException {
+ // Common part for the non-index-only plan and index-only plan
+ // Variables and types for the primary-index search.
+ List<LogicalVariable> primaryIndexUnnestVars = new ArrayList<>();
+ List<Object> primaryIndexOutputTypes = new ArrayList<Object>();
+ // Appends output variables/types generated by the primary-index search (not forwarded from input).
+ primaryIndexUnnestVars.addAll(dataSourceOp.getVariables());
+ appendPrimaryIndexTypes(dataset, recordType, metaRecordType, primaryIndexOutputTypes);
+
+ // Fetches PK variable(s) from the secondary-index search operator.
+ List<LogicalVariable> pkVarsFromSIdxUnnestMapOp = AccessMethodUtils.getKeyVarsFromSecondaryUnnestMap(dataset,
+ recordType, metaRecordType, inputOp, secondaryIndex, SecondaryUnnestMapOutputVarType.PRIMARY_KEY);
+
+ // Index-only plan or not?
+ boolean isIndexOnlyPlan = analysisCtx.getIndexOnlyPlanInfo().getFirst();
+
+ // Non-index-only plan case: creates ORDER -> UNNEST-MAP(Primary-index search) and return that unnest-map op.
+ if (!isIndexOnlyPlan) {
+ return createFinalNonIndexOnlySearchPlan(dataset, inputOp, context, sortPrimaryKeys, retainInput,
+ retainMissing, requiresBroadcast, pkVarsFromSIdxUnnestMapOp, primaryIndexUnnestVars,
+ primaryIndexOutputTypes);
} else {
- primaryIndexUnnestOp.getInputs().add(new MutableObject<>(inputOp));
+ // Index-only plan case: creates a UNIONALL operator that has two paths after the secondary unnest-map op,
+ // and returns it.
+ return createFinalIndexOnlySearchPlan(afterTopOpRefs, topOpRef, conditionRef, assignsBeforeTopOpRef,
+ dataset, recordType, metaRecordType, inputOp, context, retainInput, retainMissing,
+ requiresBroadcast, secondaryIndex, analysisCtx, subTree, newMissingPlaceHolderForLOJ,
+ pkVarsFromSIdxUnnestMapOp, primaryIndexUnnestVars, primaryIndexOutputTypes);
}
- context.computeAndSetTypeEnvironmentForOperator(primaryIndexUnnestOp);
- primaryIndexUnnestOp.setExecutionMode(ExecutionMode.PARTITIONED);
- return primaryIndexUnnestOp;
+ }
+
+ private static AbstractFunctionCallExpression createPointExpression(List<LogicalVariable> pointVars) {
+ List<Mutable<ILogicalExpression>> expressions = new ArrayList<>();
+ AbstractFunctionCallExpression createPointExpr1 =
+ new ScalarFunctionCallExpression(FunctionUtil.getFunctionInfo(BuiltinFunctions.CREATE_POINT));
+ expressions.add(new MutableObject<ILogicalExpression>(new VariableReferenceExpression(pointVars.get(0))));
+ expressions.add(new MutableObject<ILogicalExpression>(new VariableReferenceExpression(pointVars.get(1))));
+ createPointExpr1.getArguments().addAll(expressions);
+ return createPointExpr1;
+ }
+
+ private static AbstractFunctionCallExpression createRectangleExpression(
+ AbstractFunctionCallExpression createPointExpr1, AbstractFunctionCallExpression createPointExpr2) {
+ List<Mutable<ILogicalExpression>> expressions = new ArrayList<>();
+ AbstractFunctionCallExpression createRectangleExpr =
+ new ScalarFunctionCallExpression(FunctionUtil.getFunctionInfo(BuiltinFunctions.CREATE_RECTANGLE));
+ expressions.add(new MutableObject<ILogicalExpression>(createPointExpr1));
+ expressions.add(new MutableObject<ILogicalExpression>(createPointExpr2));
+ createRectangleExpr.getArguments().addAll(expressions);
+ return createRectangleExpr;
}
public static ScalarFunctionCallExpression findLOJIsMissingFuncInGroupBy(GroupByOperator lojGroupbyOp)
throws AlgebricksException {
- //find IS_NULL function of which argument has the nullPlaceholder variable in the nested plan of groupby.
+ //find IS_MISSING function of which argument has the nullPlaceholder variable in the nested plan of groupby.
ALogicalPlanImpl subPlan = (ALogicalPlanImpl) lojGroupbyOp.getNestedPlans().get(0);
Mutable<ILogicalOperator> subPlanRootOpRef = subPlan.getRoots().get(0);
AbstractLogicalOperator subPlanRootOp = (AbstractLogicalOperator) subPlanRootOpRef.getValue();
- boolean foundSelectNonNull = false;
- ScalarFunctionCallExpression isNullFuncExpr = null;
+ boolean foundSelectNonMissing = false;
+ ScalarFunctionCallExpression isMissingFuncExpr = null;
AbstractLogicalOperator inputOp = subPlanRootOp;
while (inputOp != null) {
if (inputOp.getOperatorTag() == LogicalOperatorTag.SELECT) {
@@ -629,11 +1459,11 @@ public class AccessMethodUtils {
.getExpressionTag() == LogicalExpressionTag.FUNCTION_CALL) {
if (((AbstractFunctionCallExpression) notFuncExpr.getArguments().get(0).getValue())
.getFunctionIdentifier().equals(AlgebricksBuiltinFunctions.IS_MISSING)) {
- isNullFuncExpr =
+ isMissingFuncExpr =
(ScalarFunctionCallExpression) notFuncExpr.getArguments().get(0).getValue();
- if (isNullFuncExpr.getArguments().get(0).getValue()
+ if (isMissingFuncExpr.getArguments().get(0).getValue()
.getExpressionTag() == LogicalExpressionTag.VARIABLE) {
- foundSelectNonNull = true;
+ foundSelectNonMissing = true;
break;
}
}
@@ -645,21 +1475,20 @@ public class AccessMethodUtils {
: null;
}
- if (!foundSelectNonNull) {
- throw new AlgebricksException(
- "Could not find the non-null select operator in GroupByOperator for LEFTOUTERJOIN plan optimization.");
+ if (!foundSelectNonMissing) {
+ throw CompilationException.create(ErrorCode.CANNOT_FIND_NON_MISSING_SELECT_OPERATOR);
}
- return isNullFuncExpr;
+ return isMissingFuncExpr;
}
- public static void resetLOJNullPlaceholderVariableInGroupByOp(AccessMethodAnalysisContext analysisCtx,
- LogicalVariable newNullPlaceholderVaraible, IOptimizationContext context) throws AlgebricksException {
+ public static void resetLOJMissingPlaceholderVarInGroupByOp(AccessMethodAnalysisContext analysisCtx,
+ LogicalVariable newMissingPlaceholderVaraible, IOptimizationContext context) throws AlgebricksException {
- //reset the null placeholder variable in groupby operator
- ScalarFunctionCallExpression isNullFuncExpr = analysisCtx.getLOJIsNullFuncInGroupBy();
- isNullFuncExpr.getArguments().clear();
- isNullFuncExpr.getArguments().add(
- new MutableObject<ILogicalExpression>(new VariableReferenceExpression(newNullPlaceholderVaraible)));
+ //reset the missing placeholder variable in groupby operator
+ ScalarFunctionCallExpression isMissingFuncExpr = analysisCtx.getLOJIsMissingFuncInGroupBy();
+ isMissingFuncExpr.getArguments().clear();
+ isMissingFuncExpr.getArguments().add(
+ new MutableObject<ILogicalExpression>(new VariableReferenceExpression(newMissingPlaceholderVaraible)));
//recompute type environment.
OperatorPropertiesUtil.typeOpRec(analysisCtx.getLOJGroupbyOpRef(), context);
@@ -695,11 +1524,11 @@ public class AccessMethodUtils {
}
public static UnnestMapOperator createExternalDataLookupUnnestMap(AbstractDataSourceOperator dataSourceOp,
- Dataset dataset, ARecordType recordType, ILogicalOperator inputOp, IOptimizationContext context,
- boolean retainInput, boolean retainNull) throws AlgebricksException {
- List<LogicalVariable> primaryKeyVars =
- AccessMethodUtils.getPrimaryKeyVarsFromSecondaryUnnestMap(dataset, inputOp);
-
+ Dataset dataset, ARecordType recordType, ARecordType metaRecordType, ILogicalOperator inputOp,
+ IOptimizationContext context, Index secondaryIndex, boolean retainInput, boolean retainNull)
+ throws AlgebricksException {
+ List<LogicalVariable> primaryKeyVars = AccessMethodUtils.getKeyVarsFromSecondaryUnnestMap(dataset, recordType,
+ metaRecordType, inputOp, secondaryIndex, SecondaryUnnestMapOutputVarType.PRIMARY_KEY);
// add a sort on the RID fields before fetching external data.
OrderOperator order = new OrderOperator();
for (LogicalVariable pkVar : primaryKeyVars) {
@@ -774,4 +1603,845 @@ public class AccessMethodUtils {
return usedVars.isEmpty() ? false : true;
}
+ /**
+ * Checks whether the given function can generate false-positive results when using a corresponding index type.
+ */
+ public static Pair<Boolean, Boolean> canFunctionGenerateFalsePositiveResultsUsingIndex(
+ AbstractFunctionCallExpression funcExpr, List<Pair<FunctionIdentifier, Boolean>> funcIdents) {
+ boolean requireVerificationAfterSIdxSearch = true;
+
+ // Check whether the given function-call can generate false positive results.
+ FunctionIdentifier argFuncIdent = funcExpr.getFunctionIdentifier();
+ boolean functionFound = false;
+ for (int i = 0; i < funcIdents.size(); i++) {
+ if (argFuncIdent.equals(funcIdents.get(i).first)) {
+ functionFound = true;
+ requireVerificationAfterSIdxSearch = funcIdents.get(i).second;
+ break;
+ }
+ }
+
+ // If function-call itself is not an index-based access method, we check its arguments.
+ if (!functionFound) {
+ for (Mutable<ILogicalExpression> arg : funcExpr.getArguments()) {
+ ILogicalExpression argExpr = arg.getValue();
+ if (argExpr.getExpressionTag() != LogicalExpressionTag.FUNCTION_CALL) {
+ continue;
+ }
+ AbstractFunctionCallExpression argFuncExpr = (AbstractFunctionCallExpression) argExpr;
+ FunctionIdentifier argExprFuncIdent = argFuncExpr.getFunctionIdentifier();
+ for (int i = 0; i < funcIdents.size(); i++) {
+ if (argExprFuncIdent.equals(funcIdents.get(i).first)) {
+ functionFound = true;
+ requireVerificationAfterSIdxSearch = funcIdents.get(i).second;
+ break;
+ }
+ }
+ }
+ }
+
+ return new Pair<>(functionFound, requireVerificationAfterSIdxSearch);
+ }
+
+ /**
+ * Checks whether the given plan is an index-only plan (a.k.a. instantTryLock() on PK optimization).
+ * Refer to the IntroduceSelectAccessMethodRule or IntroduceJoinAccessMethodRule for more details.
+ *
+ * @throws AlgebricksException
+ */
+ public static void indexOnlyPlanCheck(List<Mutable<ILogicalOperator>> afterTopRefs,
+ Mutable<ILogicalOperator> topRef, OptimizableOperatorSubTree indexSubTree,
+ OptimizableOperatorSubTree probeSubTree, Index chosenIndex, AccessMethodAnalysisContext analysisCtx,
+ IOptimizationContext context, Quadruple<Boolean, Boolean, Boolean, Boolean> indexOnlyPlanInfo)
+ throws AlgebricksException {
+ // First, checks all cases that the index-only can't be applied. If so, we can stop here.
+ Dataset dataset = indexSubTree.getDataset();
+ // For an external dataset, primary index, we don't apply index-only plan optimization.
+ // For a non-enforced index, we also don't apply index-only plan since it can contain a casted numeric value.
+ // For an enforced index, we also don't apply the index-only pan since the key field from a secondary index
+ // may not be equal to the actual value in the record. (e.g., INT index and BIGINT value in the actual record)
+ // Since index-only plan doesn't access the primary index, we can't get the actual value in this case.
+ // Also, if no-index-only option is given, we stop here to honor that request.
+ boolean noIndexOnlyPlanOption = getNoIndexOnlyOption(context);
+ // TODO: For the inverted index access-method cases only:
+ // Since an inverted index can contain multiple secondary key entries per one primary key,
+ // Index-only plan can't be applied. For example, suppose there are two entries (SK1, SK2) for one PK.
+ // Since we can't access <SK1, PK>, <SK2, PK> at the same time unless we use tryLock (we use instantTryLock),
+ // right now, we can't support an index-only plan on an inverted index.
+ // Once this issue is resolved, we can apply an index-only plan.
+ // One additional condition:
+ // Even if the above is resolved, if a secondary key field is used after
+ // SELECT or JOIN operator, this can't be qualified as an index-only plan since
+ // an inverted index contains a part of a field value, not all of it.
+ if (dataset.getDatasetType() == DatasetType.EXTERNAL || chosenIndex.isPrimaryIndex()
+ || chosenIndex.isOverridingKeyFieldTypes() || chosenIndex.isEnforced() || isInvertedIndex(chosenIndex)
+ || noIndexOnlyPlanOption) {
+ indexOnlyPlanInfo.setFirst(false);
+ return;
+ }
+
+ // index-only plan possible?
+ boolean isIndexOnlyPlan = false;
+
+ // secondary key field usage after the select (join) operators
+ // This boolean is mainly used for R-Tree case since R-Tree index generates an MBR
+ // and we can restore original point or rectangle from this MBR if an index is built on point or rectangle.
+ boolean secondaryKeyFieldUsedAfterSelectOrJoinOp;
+
+ // Whether a post verification (especially for R-Tree case) is required after the secondary index search
+ // (e.g., the shape of the given query is not a point or rectangle.
+ // Then, we may need to apply the select again using the real polygon, not MBR of it to get the true
+ // result, not a super-set of it.)
+ boolean requireVerificationAfterSIdxSearch = indexOnlyPlanInfo.getThird();
+
+ // Does the given index can cover all search predicates?
+ boolean doesSIdxSearchCoverAllPredicates;
+
+ // matched function expressions
+ List<IOptimizableFuncExpr> matchedFuncExprs = analysisCtx.getMatchedFuncExprs();
+
+ // logical variables that select (join) operator is using
+ List<LogicalVariable> usedVarsInSelJoinOp = new ArrayList<>();
+ List<LogicalVariable> usedVarsInSelJoinOpTemp = new ArrayList<>();
+
+ // live variables that select (join) operator can access
+ List<LogicalVariable> liveVarsAfterSelJoinOp = new ArrayList<>();
+
+ // PK, record variable
+ List<LogicalVariable> dataScanPKRecordVars;
+ List<LogicalVariable> dataScanPKVars = new ArrayList<>();
+ List<LogicalVariable> dataScanRecordVars = new ArrayList<>();
+
+ // Collects the used variables in the given select (join) operator.
+ VariableUtilities.getUsedVariables((ILogicalOperator) topRef.getValue(), usedVarsInSelJoinOpTemp);
+
+ // Removes the duplicated variables that are used in the select (join) operator
+ // in case where the variable is used multiple times in the operator's expression.
+ // (e.g., $i < 100 and $i > 10)
+ copyVarsToAnotherList(usedVarsInSelJoinOpTemp, usedVarsInSelJoinOp);
+
+ // If this is a join, we need to traverse the index subtree and find possible SELECT conditions
+ // since there may be more SELECT conditions and we need to collect used variables.
+ List<LogicalVariable> selectInIndexSubTreeVars = new ArrayList<>();
+ if (probeSubTree != null) {
+ ILogicalOperator tmpOp = indexSubTree.getRoot();
+ while (tmpOp.getOperatorTag() != LogicalOperatorTag.EMPTYTUPLESOURCE) {
+ if (tmpOp.getOperatorTag() == LogicalOperatorTag.SELECT) {
+ VariableUtilities.getUsedVariables(tmpOp, selectInIndexSubTreeVars);
+ // Remove any duplicated variables.
+ copyVarsToAnotherList(selectInIndexSubTreeVars, usedVarsInSelJoinOp);
+ selectInIndexSubTreeVars.clear();
+ }
+ tmpOp = tmpOp.getInputs().get(0).getValue();
+ }
+ }
+ usedVarsInSelJoinOpTemp.clear();
+
+ // For the index-nested-loop join case, we need to remove variables from the left (outer) relat
<TRUNCATED>