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>
