asterixdb-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From wangs...@apache.org
Subject [15/16] asterixdb git commit: [ASTERIXDB-1972][COMP][RT][TX] index-only plan
Date Fri, 16 Feb 2018 19:04:21 GMT
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>

Mime
View raw message