asterixdb-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From ima...@apache.org
Subject [27/51] [partial] incubator-asterixdb git commit: Change folder structure for Java repackage
Date Tue, 25 Aug 2015 16:44:15 GMT
http://git-wip-us.apache.org/repos/asf/incubator-asterixdb/blob/34d81630/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/am/AccessMethodUtils.java
----------------------------------------------------------------------
diff --git a/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/am/AccessMethodUtils.java b/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/am/AccessMethodUtils.java
new file mode 100644
index 0000000..73377b9
--- /dev/null
+++ b/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/am/AccessMethodUtils.java
@@ -0,0 +1,609 @@
+/*
+ * Copyright 2009-2013 by The Regents of the University of California
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * you may obtain a copy of the License from
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package edu.uci.ics.asterix.optimizer.rules.am;
+
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.List;
+
+import org.apache.commons.lang3.mutable.Mutable;
+import org.apache.commons.lang3.mutable.MutableObject;
+
+import edu.uci.ics.asterix.algebra.operators.physical.ExternalDataLookupPOperator;
+import edu.uci.ics.asterix.aql.util.FunctionUtils;
+import edu.uci.ics.asterix.common.config.DatasetConfig.DatasetType;
+import edu.uci.ics.asterix.common.config.DatasetConfig.IndexType;
+import edu.uci.ics.asterix.common.exceptions.AsterixException;
+import edu.uci.ics.asterix.metadata.declared.AqlSourceId;
+import edu.uci.ics.asterix.metadata.entities.Dataset;
+import edu.uci.ics.asterix.metadata.entities.Index;
+import edu.uci.ics.asterix.metadata.external.IndexingConstants;
+import edu.uci.ics.asterix.metadata.utils.DatasetUtils;
+import edu.uci.ics.asterix.om.base.ABoolean;
+import edu.uci.ics.asterix.om.base.AInt32;
+import edu.uci.ics.asterix.om.base.AString;
+import edu.uci.ics.asterix.om.base.IAObject;
+import edu.uci.ics.asterix.om.constants.AsterixConstantValue;
+import edu.uci.ics.asterix.om.functions.AsterixBuiltinFunctions;
+import edu.uci.ics.asterix.om.types.ARecordType;
+import edu.uci.ics.asterix.om.types.ATypeTag;
+import edu.uci.ics.asterix.om.types.IAType;
+import edu.uci.ics.asterix.om.types.hierachy.ATypeHierarchy;
+import edu.uci.ics.asterix.om.util.NonTaggedFormatUtil;
+import edu.uci.ics.hyracks.algebricks.common.exceptions.AlgebricksException;
+import edu.uci.ics.hyracks.algebricks.common.utils.Pair;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.ILogicalExpression;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.ILogicalOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.IOptimizationContext;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.LogicalExpressionTag;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.LogicalOperatorTag;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.LogicalVariable;
+import edu.uci.ics.hyracks.algebricks.core.algebra.expressions.AbstractFunctionCallExpression;
+import edu.uci.ics.hyracks.algebricks.core.algebra.expressions.ConstantExpression;
+import edu.uci.ics.hyracks.algebricks.core.algebra.expressions.IAlgebricksConstantValue;
+import edu.uci.ics.hyracks.algebricks.core.algebra.expressions.ScalarFunctionCallExpression;
+import edu.uci.ics.hyracks.algebricks.core.algebra.expressions.UnnestingFunctionCallExpression;
+import edu.uci.ics.hyracks.algebricks.core.algebra.expressions.VariableReferenceExpression;
+import edu.uci.ics.hyracks.algebricks.core.algebra.functions.AlgebricksBuiltinFunctions;
+import edu.uci.ics.hyracks.algebricks.core.algebra.functions.IFunctionInfo;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.AbstractDataSourceOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.AbstractLogicalOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.AbstractLogicalOperator.ExecutionMode;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.ExternalDataLookupOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.GroupByOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.OrderOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.OrderOperator.IOrder;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.SelectOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.UnnestMapOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.plan.ALogicalPlanImpl;
+import edu.uci.ics.hyracks.algebricks.core.algebra.util.OperatorPropertiesUtil;
+
+/**
+ * Static helper functions for rewriting plans using indexes.
+ */
+public class AccessMethodUtils {
+
+    public static void appendPrimaryIndexTypes(Dataset dataset, IAType itemType, List<Object> target)
+            throws IOException, AlgebricksException {
+        ARecordType recordType = (ARecordType) itemType;
+        List<List<String>> partitioningKeys = DatasetUtils.getPartitioningKeys(dataset);
+        for (List<String> partitioningKey : partitioningKeys) {
+            target.add(recordType.getSubFieldType(partitioningKey));
+        }
+        target.add(itemType);
+    }
+
+    public static ConstantExpression createStringConstant(String str) {
+        return new ConstantExpression(new AsterixConstantValue(new AString(str)));
+    }
+
+    public static ConstantExpression createInt32Constant(int i) {
+        return new ConstantExpression(new AsterixConstantValue(new AInt32(i)));
+    }
+
+    public static ConstantExpression createBooleanConstant(boolean b) {
+        if (b) {
+            return new ConstantExpression(new AsterixConstantValue(ABoolean.TRUE));
+        } else {
+            return new ConstantExpression(new AsterixConstantValue(ABoolean.FALSE));
+        }
+    }
+
+    public static String getStringConstant(Mutable<ILogicalExpression> expr) {
+        IAObject obj = ((AsterixConstantValue) ((ConstantExpression) expr.getValue()).getValue()).getObject();
+        return ((AString) obj).getStringValue();
+    }
+
+    public static int getInt32Constant(Mutable<ILogicalExpression> expr) {
+        IAObject obj = ((AsterixConstantValue) ((ConstantExpression) expr.getValue()).getValue()).getObject();
+        return ((AInt32) obj).getIntegerValue();
+    }
+
+    public static boolean getBooleanConstant(Mutable<ILogicalExpression> expr) {
+        IAObject obj = ((AsterixConstantValue) ((ConstantExpression) expr.getValue()).getValue()).getObject();
+        return ((ABoolean) obj).getBoolean();
+    }
+
+    public static boolean analyzeFuncExprArgsForOneConstAndVar(AbstractFunctionCallExpression funcExpr,
+            AccessMethodAnalysisContext analysisCtx) {
+        IAlgebricksConstantValue constFilterVal = null;
+        LogicalVariable fieldVar = null;
+        ILogicalExpression arg1 = funcExpr.getArguments().get(0).getValue();
+        ILogicalExpression arg2 = funcExpr.getArguments().get(1).getValue();
+        // One of the args must be a constant, and the other arg must be a variable.
+        if (arg1.getExpressionTag() == LogicalExpressionTag.CONSTANT
+                && arg2.getExpressionTag() == LogicalExpressionTag.VARIABLE) {
+            // The arguments of contains() function are asymmetrical, we can only use index if it is on the first argument
+            if (funcExpr.getFunctionIdentifier() == AsterixBuiltinFunctions.CONTAINS) {
+                return false;
+            }
+            ConstantExpression constExpr = (ConstantExpression) arg1;
+            constFilterVal = constExpr.getValue();
+            VariableReferenceExpression varExpr = (VariableReferenceExpression) arg2;
+            fieldVar = varExpr.getVariableReference();
+        } else if (arg1.getExpressionTag() == LogicalExpressionTag.VARIABLE
+                && arg2.getExpressionTag() == LogicalExpressionTag.CONSTANT) {
+            ConstantExpression constExpr = (ConstantExpression) arg2;
+            constFilterVal = constExpr.getValue();
+            VariableReferenceExpression varExpr = (VariableReferenceExpression) arg1;
+            fieldVar = varExpr.getVariableReference();
+        } else {
+            return false;
+        }
+        OptimizableFuncExpr newOptFuncExpr = new OptimizableFuncExpr(funcExpr, fieldVar, constFilterVal);
+        for (IOptimizableFuncExpr optFuncExpr : analysisCtx.matchedFuncExprs) {
+            //avoid additional optFuncExpressions in case of a join
+            if (optFuncExpr.getFuncExpr().equals(funcExpr))
+                return true;
+        }
+        analysisCtx.matchedFuncExprs.add(newOptFuncExpr);
+        return true;
+    }
+
+    public static boolean analyzeFuncExprArgsForTwoVars(AbstractFunctionCallExpression funcExpr,
+            AccessMethodAnalysisContext analysisCtx) {
+        LogicalVariable fieldVar1 = null;
+        LogicalVariable fieldVar2 = null;
+        ILogicalExpression arg1 = funcExpr.getArguments().get(0).getValue();
+        ILogicalExpression arg2 = funcExpr.getArguments().get(1).getValue();
+        if (arg1.getExpressionTag() == LogicalExpressionTag.VARIABLE
+                && arg2.getExpressionTag() == LogicalExpressionTag.VARIABLE) {
+            fieldVar1 = ((VariableReferenceExpression) arg1).getVariableReference();
+            fieldVar2 = ((VariableReferenceExpression) arg2).getVariableReference();
+        } else {
+            return false;
+        }
+        OptimizableFuncExpr newOptFuncExpr = new OptimizableFuncExpr(funcExpr, new LogicalVariable[] { fieldVar1,
+                fieldVar2 }, null);
+        for (IOptimizableFuncExpr optFuncExpr : analysisCtx.matchedFuncExprs) {
+            //avoid additional optFuncExpressions in case of a join
+            if (optFuncExpr.getFuncExpr().equals(funcExpr))
+                return true;
+        }
+        analysisCtx.matchedFuncExprs.add(newOptFuncExpr);
+        return true;
+    }
+
+    public static int getNumSecondaryKeys(Index index, ARecordType recordType) throws AlgebricksException {
+        switch (index.getIndexType()) {
+            case BTREE:
+            case SINGLE_PARTITION_WORD_INVIX:
+            case SINGLE_PARTITION_NGRAM_INVIX:
+            case LENGTH_PARTITIONED_WORD_INVIX:
+            case LENGTH_PARTITIONED_NGRAM_INVIX: {
+                return index.getKeyFieldNames().size();
+            }
+            case RTREE: {
+                Pair<IAType, Boolean> keyPairType = Index.getNonNullableOpenFieldType(index.getKeyFieldTypes().get(0),
+                        index.getKeyFieldNames().get(0), recordType);
+                IAType keyType = keyPairType.first;
+                int numDimensions = NonTaggedFormatUtil.getNumDimensions(keyType.getTypeTag());
+                return numDimensions * 2;
+            }
+            default: {
+                throw new AlgebricksException("Unknown index kind: " + index.getIndexType());
+            }
+        }
+    }
+
+    /**
+     * Appends the types of the fields produced by the given secondary index to dest.
+     */
+    public static void appendSecondaryIndexTypes(Dataset dataset, ARecordType recordType, Index index,
+            boolean primaryKeysOnly, List<Object> dest) throws AlgebricksException {
+        if (!primaryKeysOnly) {
+            switch (index.getIndexType()) {
+                case BTREE:
+                case SINGLE_PARTITION_WORD_INVIX:
+                case SINGLE_PARTITION_NGRAM_INVIX: {
+                    for (int i = 0; i < index.getKeyFieldNames().size(); i++) {
+                        Pair<IAType, Boolean> keyPairType = Index.getNonNullableOpenFieldType(index.getKeyFieldTypes()
+                                .get(i), index.getKeyFieldNames().get(i), recordType);
+                        dest.add(keyPairType.first);
+                    }
+                    break;
+                }
+                case RTREE: {
+                    Pair<IAType, Boolean> keyPairType = Index.getNonNullableOpenFieldType(
+                            index.getKeyFieldTypes().get(0), index.getKeyFieldNames().get(0), recordType);
+                    IAType keyType = keyPairType.first;
+                    IAType nestedKeyType = NonTaggedFormatUtil.getNestedSpatialType(keyType.getTypeTag());
+                    int numKeys = getNumSecondaryKeys(index, recordType);
+                    for (int i = 0; i < numKeys; i++) {
+                        dest.add(nestedKeyType);
+                    }
+                    break;
+                }
+                case LENGTH_PARTITIONED_NGRAM_INVIX:
+                case LENGTH_PARTITIONED_WORD_INVIX:
+                default:
+                    break;
+            }
+        }
+        // Primary keys.
+        if (dataset.getDatasetType() == DatasetType.EXTERNAL) {
+            //add primary keys
+            try {
+                appendExternalRecPrimaryKeys(dataset, dest);
+            } catch (AsterixException e) {
+                throw new AlgebricksException(e);
+            }
+        } else {
+            List<List<String>> partitioningKeys = DatasetUtils.getPartitioningKeys(dataset);
+            for (List<String> partitioningKey : partitioningKeys) {
+                try {
+                    dest.add(recordType.getSubFieldType(partitioningKey));
+                } catch (IOException e) {
+                    throw new AlgebricksException(e);
+                }
+            }
+        }
+    }
+
+    public static void appendSecondaryIndexOutputVars(Dataset dataset, ARecordType recordType, Index index,
+            boolean primaryKeysOnly, IOptimizationContext context, List<LogicalVariable> dest)
+            throws AlgebricksException {
+        int numPrimaryKeys = 0;
+        if (dataset.getDatasetType() == DatasetType.EXTERNAL) {
+            numPrimaryKeys = IndexingConstants.getRIDSize(dataset);
+        } else {
+            numPrimaryKeys = DatasetUtils.getPartitioningKeys(dataset).size();
+        }
+        int numSecondaryKeys = getNumSecondaryKeys(index, recordType);
+        int numVars = (primaryKeysOnly) ? numPrimaryKeys : numPrimaryKeys + numSecondaryKeys;
+        for (int i = 0; i < numVars; i++) {
+            dest.add(context.newVar());
+        }
+    }
+
+    public static List<LogicalVariable> getPrimaryKeyVarsFromSecondaryUnnestMap(Dataset dataset,
+            ILogicalOperator unnestMapOp) {
+        int numPrimaryKeys;
+        if (dataset.getDatasetType() == DatasetType.EXTERNAL) {
+            numPrimaryKeys = IndexingConstants.getRIDSize(dataset);
+        } else {
+            numPrimaryKeys = DatasetUtils.getPartitioningKeys(dataset).size();
+        }
+        List<LogicalVariable> primaryKeyVars = new ArrayList<LogicalVariable>();
+        List<LogicalVariable> sourceVars = ((UnnestMapOperator) unnestMapOp).getVariables();
+        // Assumes the primary keys are located at the end.
+        int start = sourceVars.size() - numPrimaryKeys;
+        int stop = sourceVars.size();
+        for (int i = start; i < stop; i++) {
+            primaryKeyVars.add(sourceVars.get(i));
+        }
+        return primaryKeyVars;
+    }
+
+    public static List<LogicalVariable> getPrimaryKeyVarsFromPrimaryUnnestMap(Dataset dataset,
+            ILogicalOperator unnestMapOp) {
+        int numPrimaryKeys = DatasetUtils.getPartitioningKeys(dataset).size();
+        List<LogicalVariable> primaryKeyVars = new ArrayList<LogicalVariable>();
+        List<LogicalVariable> sourceVars = ((UnnestMapOperator) unnestMapOp).getVariables();
+        // Assumes the primary keys are located at the beginning.
+        for (int i = 0; i < numPrimaryKeys; i++) {
+            primaryKeyVars.add(sourceVars.get(i));
+        }
+        return primaryKeyVars;
+    }
+
+    /**
+     * Returns the search key expression which feeds a secondary-index search. If we are optimizing a selection query then this method returns
+     * the a ConstantExpression from the first constant value in the optimizable function expression.
+     * If we are optimizing a join, then this method returns the VariableReferenceExpression that should feed the secondary index probe.
+     *
+     * @throws AlgebricksException
+     */
+    public static Pair<ILogicalExpression, Boolean> createSearchKeyExpr(IOptimizableFuncExpr optFuncExpr,
+            OptimizableOperatorSubTree indexSubTree, 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
+            IAType fieldType = optFuncExpr.getFieldType(0);
+            IAObject constantObj = ((AsterixConstantValue) optFuncExpr.getConstantVal(0)).getObject();
+            ATypeTag constantValueTag = constantObj.getType().getTypeTag();
+            // type casting applied?
+            boolean typeCastingApplied = false;
+            // type casting happened from real (FLOAT, DOUBLE) value -> INT value?
+            boolean realTypeConvertedToIntegerType = false;
+            AsterixConstantValue replacedConstantValue = null;
+
+            // if the constant type and target type does not match, we do a type conversion
+            if (constantValueTag != fieldType.getTypeTag()) {
+                replacedConstantValue = ATypeHierarchy.getAsterixConstantValueFromNumericTypeObject(constantObj,
+                        fieldType.getTypeTag());
+                if (replacedConstantValue != null) {
+                    typeCastingApplied = true;
+                }
+
+                // 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.
+                switch (constantValueTag) {
+                    case DOUBLE:
+                    case FLOAT:
+                        switch (fieldType.getTypeTag()) {
+                            case INT8:
+                            case INT16:
+                            case INT32:
+                            case INT64:
+                                realTypeConvertedToIntegerType = true;
+                                break;
+                            default:
+                                break;
+                        }
+                    default:
+                        break;
+                }
+            }
+
+            if (typeCastingApplied) {
+                return new Pair<ILogicalExpression, Boolean>(new ConstantExpression(replacedConstantValue),
+                        realTypeConvertedToIntegerType);
+            } else {
+                return new Pair<ILogicalExpression, Boolean>(new ConstantExpression(optFuncExpr.getConstantVal(0)),
+                        false);
+            }
+        } else {
+            // We are optimizing a join query. Determine which variable feeds the secondary index.
+            if (optFuncExpr.getOperatorSubTree(0) == null || optFuncExpr.getOperatorSubTree(0) == probeSubTree) {
+                return new Pair<ILogicalExpression, Boolean>(new VariableReferenceExpression(
+                        optFuncExpr.getLogicalVar(0)), false);
+            } else {
+                return new Pair<ILogicalExpression, Boolean>(new VariableReferenceExpression(
+                        optFuncExpr.getLogicalVar(1)), false);
+            }
+        }
+    }
+
+    /**
+     * Returns the first expr optimizable by this index.
+     */
+    public static IOptimizableFuncExpr chooseFirstOptFuncExpr(Index chosenIndex, AccessMethodAnalysisContext analysisCtx) {
+        List<Pair<Integer, Integer>> indexExprs = analysisCtx.getIndexExprs(chosenIndex);
+        int firstExprIndex = indexExprs.get(0).first;
+        return analysisCtx.matchedFuncExprs.get(firstExprIndex);
+    }
+
+    public static int chooseFirstOptFuncVar(Index chosenIndex, AccessMethodAnalysisContext analysisCtx) {
+        List<Pair<Integer, Integer>> indexExprs = analysisCtx.getIndexExprs(chosenIndex);
+        return indexExprs.get(0).second;
+    }
+
+    public static UnnestMapOperator createSecondaryIndexUnnestMap(Dataset dataset, ARecordType recordType, Index index,
+            ILogicalOperator inputOp, AccessMethodJobGenParams jobGenParams, IOptimizationContext context,
+            boolean outputPrimaryKeysOnly, boolean retainInput) 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<Mutable<ILogicalExpression>>();
+        jobGenParams.writeToFuncArgs(secondaryIndexFuncArgs);
+        // Variables and types coming out of the secondary-index search.
+        List<LogicalVariable> secondaryIndexUnnestVars = new ArrayList<LogicalVariable>();
+        List<Object> secondaryIndexOutputTypes = new ArrayList<Object>();
+        // Append output variables/types generated by the secondary-index search (not forwarded from input).
+        appendSecondaryIndexOutputVars(dataset, recordType, index, outputPrimaryKeysOnly, context,
+                secondaryIndexUnnestVars);
+        appendSecondaryIndexTypes(dataset, recordType, index, outputPrimaryKeysOnly, secondaryIndexOutputTypes);
+        // An index search is expressed as an unnest over an index-search function.
+        IFunctionInfo secondaryIndexSearch = FunctionUtils.getFunctionInfo(AsterixBuiltinFunctions.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.
+        UnnestMapOperator secondaryIndexUnnestOp = new UnnestMapOperator(secondaryIndexUnnestVars,
+                new MutableObject<ILogicalExpression>(secondaryIndexSearchFunc), secondaryIndexOutputTypes, retainInput);
+        secondaryIndexUnnestOp.getInputs().add(new MutableObject<ILogicalOperator>(inputOp));
+        context.computeAndSetTypeEnvironmentForOperator(secondaryIndexUnnestOp);
+        secondaryIndexUnnestOp.setExecutionMode(ExecutionMode.PARTITIONED);
+        return secondaryIndexUnnestOp;
+    }
+
+    public static UnnestMapOperator createPrimaryIndexUnnestMap(AbstractDataSourceOperator dataSourceOp,
+            Dataset dataset, ARecordType recordType, ILogicalOperator inputOp, IOptimizationContext context,
+            boolean sortPrimaryKeys, boolean retainInput, boolean retainNull, boolean requiresBroadcast)
+            throws AlgebricksException {
+        List<LogicalVariable> primaryKeyVars = AccessMethodUtils.getPrimaryKeyVarsFromSecondaryUnnestMap(dataset,
+                inputOp);
+        // Optionally add a sort on the primary-index keys before searching the primary index.
+        OrderOperator order = null;
+        if (sortPrimaryKeys) {
+            order = new OrderOperator();
+            for (LogicalVariable pkVar : primaryKeyVars) {
+                Mutable<ILogicalExpression> vRef = new MutableObject<ILogicalExpression>(
+                        new VariableReferenceExpression(pkVar));
+                order.getOrderExpressions().add(
+                        new Pair<IOrder, Mutable<ILogicalExpression>>(OrderOperator.ASC_ORDER, vRef));
+            }
+            // The secondary-index search feeds into the sort.
+            order.getInputs().add(new MutableObject<ILogicalOperator>(inputOp));
+            order.setExecutionMode(ExecutionMode.LOCAL);
+            context.computeAndSetTypeEnvironmentForOperator(order);
+        }
+        // The job gen parameters are transferred to the actual job gen via the UnnestMapOperator's function arguments.
+        List<Mutable<ILogicalExpression>> primaryIndexFuncArgs = new ArrayList<Mutable<ILogicalExpression>>();
+        BTreeJobGenParams jobGenParams = new BTreeJobGenParams(dataset.getDatasetName(), IndexType.BTREE,
+                dataset.getDataverseName(), dataset.getDatasetName(), retainInput, retainNull, requiresBroadcast);
+        // Set low/high inclusive to true for a point lookup.
+        jobGenParams.setLowKeyInclusive(true);
+        jobGenParams.setHighKeyInclusive(true);
+        jobGenParams.setLowKeyVarList(primaryKeyVars, 0, primaryKeyVars.size());
+        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<LogicalVariable>();
+        List<Object> primaryIndexOutputTypes = new ArrayList<Object>();
+        // Append output variables/types generated by the primary-index search (not forwarded from input).
+        primaryIndexUnnestVars.addAll(dataSourceOp.getVariables());
+        try {
+            appendPrimaryIndexTypes(dataset, recordType, primaryIndexOutputTypes);
+        } catch (IOException e) {
+            throw new AlgebricksException(e);
+        }
+        // An index search is expressed as an unnest over an index-search function.
+        IFunctionInfo primaryIndexSearch = FunctionUtils.getFunctionInfo(AsterixBuiltinFunctions.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.
+        UnnestMapOperator primaryIndexUnnestOp = 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));
+        } else {
+            primaryIndexUnnestOp.getInputs().add(new MutableObject<ILogicalOperator>(inputOp));
+        }
+        context.computeAndSetTypeEnvironmentForOperator(primaryIndexUnnestOp);
+        primaryIndexUnnestOp.setExecutionMode(ExecutionMode.PARTITIONED);
+        return primaryIndexUnnestOp;
+    }
+
+    public static ScalarFunctionCallExpression findLOJIsNullFuncInGroupBy(GroupByOperator lojGroupbyOp)
+            throws AlgebricksException {
+        //find IS_NULL 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;
+        AbstractLogicalOperator inputOp = subPlanRootOp;
+        while (inputOp != null) {
+            if (inputOp.getOperatorTag() == LogicalOperatorTag.SELECT) {
+                SelectOperator selectOp = (SelectOperator) inputOp;
+                if (selectOp.getCondition().getValue().getExpressionTag() == LogicalExpressionTag.FUNCTION_CALL) {
+                    if (((AbstractFunctionCallExpression) selectOp.getCondition().getValue()).getFunctionIdentifier()
+                            .equals(AlgebricksBuiltinFunctions.NOT)) {
+                        ScalarFunctionCallExpression notFuncExpr = (ScalarFunctionCallExpression) selectOp
+                                .getCondition().getValue();
+                        if (notFuncExpr.getArguments().get(0).getValue().getExpressionTag() == LogicalExpressionTag.FUNCTION_CALL) {
+                            if (((AbstractFunctionCallExpression) notFuncExpr.getArguments().get(0).getValue())
+                                    .getFunctionIdentifier().equals(AlgebricksBuiltinFunctions.IS_NULL)) {
+                                isNullFuncExpr = (ScalarFunctionCallExpression) notFuncExpr.getArguments().get(0)
+                                        .getValue();
+                                if (isNullFuncExpr.getArguments().get(0).getValue().getExpressionTag() == LogicalExpressionTag.VARIABLE) {
+                                    foundSelectNonNull = true;
+                                    break;
+                                }
+                            }
+                        }
+                    }
+                }
+            }
+            inputOp = inputOp.getInputs().size() > 0 ? (AbstractLogicalOperator) inputOp.getInputs().get(0).getValue()
+                    : null;
+        }
+
+        if (!foundSelectNonNull) {
+            throw new AlgebricksException(
+                    "Could not find the non-null select operator in GroupByOperator for LEFTOUTERJOIN plan optimization.");
+        }
+        return isNullFuncExpr;
+    }
+
+    public static void resetLOJNullPlaceholderVariableInGroupByOp(AccessMethodAnalysisContext analysisCtx,
+            LogicalVariable newNullPlaceholderVaraible, 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)));
+
+        //recompute type environment.
+        OperatorPropertiesUtil.typeOpRec(analysisCtx.getLOJGroupbyOpRef(), context);
+    }
+
+    // New < For external datasets indexing>
+    private static void appendExternalRecTypes(Dataset dataset, IAType itemType, List<Object> target) {
+        target.add(itemType);
+    }
+
+    private static void appendExternalRecPrimaryKeys(Dataset dataset, List<Object> target) throws AsterixException {
+        int numPrimaryKeys = IndexingConstants.getRIDSize(dataset);
+        for (int i = 0; i < numPrimaryKeys; i++) {
+            target.add(IndexingConstants.getFieldType(i));
+        }
+    }
+
+    private static void writeVarList(List<LogicalVariable> varList, List<Mutable<ILogicalExpression>> funcArgs) {
+        Mutable<ILogicalExpression> numKeysRef = new MutableObject<ILogicalExpression>(new ConstantExpression(
+                new AsterixConstantValue(new AInt32(varList.size()))));
+        funcArgs.add(numKeysRef);
+        for (LogicalVariable keyVar : varList) {
+            Mutable<ILogicalExpression> keyVarRef = new MutableObject<ILogicalExpression>(
+                    new VariableReferenceExpression(keyVar));
+            funcArgs.add(keyVarRef);
+        }
+    }
+
+    private static void addStringArg(String argument, List<Mutable<ILogicalExpression>> funcArgs) {
+        Mutable<ILogicalExpression> stringRef = new MutableObject<ILogicalExpression>(new ConstantExpression(
+                new AsterixConstantValue(new AString(argument))));
+        funcArgs.add(stringRef);
+    }
+
+    public static ExternalDataLookupOperator createExternalDataLookupUnnestMap(AbstractDataSourceOperator dataSourceOp,
+            Dataset dataset, ARecordType recordType, ILogicalOperator inputOp, IOptimizationContext context,
+            Index secondaryIndex, boolean retainInput, boolean retainNull) throws AlgebricksException {
+        List<LogicalVariable> primaryKeyVars = AccessMethodUtils.getPrimaryKeyVarsFromSecondaryUnnestMap(dataset,
+                inputOp);
+
+        // add a sort on the RID fields before fetching external data.
+        OrderOperator order = new OrderOperator();
+        for (LogicalVariable pkVar : primaryKeyVars) {
+            Mutable<ILogicalExpression> vRef = new MutableObject<ILogicalExpression>(new VariableReferenceExpression(
+                    pkVar));
+            order.getOrderExpressions().add(
+                    new Pair<IOrder, Mutable<ILogicalExpression>>(OrderOperator.ASC_ORDER, vRef));
+        }
+        // The secondary-index search feeds into the sort.
+        order.getInputs().add(new MutableObject<ILogicalOperator>(inputOp));
+        order.setExecutionMode(ExecutionMode.LOCAL);
+        context.computeAndSetTypeEnvironmentForOperator(order);
+        List<Mutable<ILogicalExpression>> externalRIDAccessFuncArgs = new ArrayList<Mutable<ILogicalExpression>>();
+        //Add dataverse and dataset to the arguments
+        AccessMethodUtils.addStringArg(dataset.getDataverseName(), externalRIDAccessFuncArgs);
+        AccessMethodUtils.addStringArg(dataset.getDatasetName(), externalRIDAccessFuncArgs);
+        AccessMethodUtils.writeVarList(primaryKeyVars, externalRIDAccessFuncArgs);
+
+        // Variables and types coming out of the external access.
+        List<LogicalVariable> externalAccessByRIDVars = new ArrayList<LogicalVariable>();
+        List<Object> externalAccessOutputTypes = new ArrayList<Object>();
+        // Append output variables/types generated by the data scan (not forwarded from input).
+        externalAccessByRIDVars.addAll(dataSourceOp.getVariables());
+        appendExternalRecTypes(dataset, recordType, externalAccessOutputTypes);
+
+        IFunctionInfo externalAccessByRID = FunctionUtils.getFunctionInfo(AsterixBuiltinFunctions.EXTERNAL_LOOKUP);
+        AbstractFunctionCallExpression externalAccessFunc = new ScalarFunctionCallExpression(externalAccessByRID,
+                externalRIDAccessFuncArgs);
+
+        ExternalDataLookupOperator externalLookupOp = new ExternalDataLookupOperator(externalAccessByRIDVars,
+                new MutableObject<ILogicalExpression>(externalAccessFunc), externalAccessOutputTypes, retainInput,
+                dataSourceOp.getDataSource());
+        // Fed by the order operator or the secondaryIndexUnnestOp.
+        externalLookupOp.getInputs().add(new MutableObject<ILogicalOperator>(order));
+
+        context.computeAndSetTypeEnvironmentForOperator(externalLookupOp);
+        externalLookupOp.setExecutionMode(ExecutionMode.PARTITIONED);
+
+        //set the physical operator
+        AqlSourceId dataSourceId = new AqlSourceId(dataset.getDataverseName(), dataset.getDatasetName());
+        externalLookupOp.setPhysicalOperator(new ExternalDataLookupPOperator(dataSourceId, dataset, recordType,
+                secondaryIndex, primaryKeyVars, false, retainInput, retainNull));
+        return externalLookupOp;
+    }
+}

http://git-wip-us.apache.org/repos/asf/incubator-asterixdb/blob/34d81630/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/am/BTreeAccessMethod.java
----------------------------------------------------------------------
diff --git a/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/am/BTreeAccessMethod.java b/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/am/BTreeAccessMethod.java
new file mode 100644
index 0000000..22f3b80
--- /dev/null
+++ b/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/am/BTreeAccessMethod.java
@@ -0,0 +1,660 @@
+/*
+ * Copyright 2009-2013 by The Regents of the University of California
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * you may obtain a copy of the License from
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package edu.uci.ics.asterix.optimizer.rules.am;
+
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.BitSet;
+import java.util.HashSet;
+import java.util.Iterator;
+import java.util.List;
+import java.util.Set;
+
+import org.apache.commons.lang3.mutable.Mutable;
+import org.apache.commons.lang3.mutable.MutableObject;
+
+import edu.uci.ics.asterix.aql.util.FunctionUtils;
+import edu.uci.ics.asterix.common.annotations.SkipSecondaryIndexSearchExpressionAnnotation;
+import edu.uci.ics.asterix.common.config.DatasetConfig.DatasetType;
+import edu.uci.ics.asterix.common.config.DatasetConfig.IndexType;
+import edu.uci.ics.asterix.metadata.entities.Dataset;
+import edu.uci.ics.asterix.metadata.entities.Index;
+import edu.uci.ics.asterix.om.types.ARecordType;
+import edu.uci.ics.asterix.optimizer.rules.util.EquivalenceClassUtils;
+import edu.uci.ics.hyracks.algebricks.common.exceptions.AlgebricksException;
+import edu.uci.ics.hyracks.algebricks.common.utils.Pair;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.ILogicalExpression;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.ILogicalOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.IOptimizationContext;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.LogicalExpressionTag;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.LogicalVariable;
+import edu.uci.ics.hyracks.algebricks.core.algebra.expressions.AbstractFunctionCallExpression;
+import edu.uci.ics.hyracks.algebricks.core.algebra.expressions.IndexedNLJoinExpressionAnnotation;
+import edu.uci.ics.hyracks.algebricks.core.algebra.expressions.ScalarFunctionCallExpression;
+import edu.uci.ics.hyracks.algebricks.core.algebra.expressions.VariableReferenceExpression;
+import edu.uci.ics.hyracks.algebricks.core.algebra.functions.AlgebricksBuiltinFunctions;
+import edu.uci.ics.hyracks.algebricks.core.algebra.functions.AlgebricksBuiltinFunctions.ComparisonKind;
+import edu.uci.ics.hyracks.algebricks.core.algebra.functions.FunctionIdentifier;
+import edu.uci.ics.hyracks.algebricks.core.algebra.functions.IFunctionInfo;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.AbstractBinaryJoinOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.AbstractDataSourceOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.AbstractLogicalOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.AbstractLogicalOperator.ExecutionMode;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.AssignOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.ExternalDataLookupOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.SelectOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.UnnestMapOperator;
+
+/**
+ * Class for helping rewrite rules to choose and apply BTree indexes.
+ */
+public class BTreeAccessMethod implements IAccessMethod {
+
+    // Describes whether a search predicate is an open/closed interval.
+    private enum LimitType {
+        LOW_INCLUSIVE,
+        LOW_EXCLUSIVE,
+        HIGH_INCLUSIVE,
+        HIGH_EXCLUSIVE,
+        EQUAL
+    }
+
+    // TODO: There is some redundancy here, since these are listed in AlgebricksBuiltinFunctions as well.
+    private static List<FunctionIdentifier> funcIdents = new ArrayList<FunctionIdentifier>();
+    static {
+        funcIdents.add(AlgebricksBuiltinFunctions.EQ);
+        funcIdents.add(AlgebricksBuiltinFunctions.LE);
+        funcIdents.add(AlgebricksBuiltinFunctions.GE);
+        funcIdents.add(AlgebricksBuiltinFunctions.LT);
+        funcIdents.add(AlgebricksBuiltinFunctions.GT);
+    }
+
+    public static BTreeAccessMethod INSTANCE = new BTreeAccessMethod();
+
+    @Override
+    public List<FunctionIdentifier> getOptimizableFunctions() {
+        return funcIdents;
+    }
+
+    @Override
+    public boolean analyzeFuncExprArgs(AbstractFunctionCallExpression funcExpr,
+            List<AbstractLogicalOperator> assignsAndUnnests, AccessMethodAnalysisContext analysisCtx) {
+        boolean matches = AccessMethodUtils.analyzeFuncExprArgsForOneConstAndVar(funcExpr, analysisCtx);
+        if (!matches) {
+            matches = AccessMethodUtils.analyzeFuncExprArgsForTwoVars(funcExpr, analysisCtx);
+        }
+        return matches;
+    }
+
+    @Override
+    public boolean matchAllIndexExprs() {
+        return false;
+    }
+
+    @Override
+    public boolean matchPrefixIndexExprs() {
+        return true;
+    }
+
+    @Override
+    public boolean applySelectPlanTransformation(Mutable<ILogicalOperator> selectRef,
+            OptimizableOperatorSubTree subTree, Index chosenIndex, AccessMethodAnalysisContext analysisCtx,
+            IOptimizationContext context) throws AlgebricksException {
+        SelectOperator select = (SelectOperator) selectRef.getValue();
+        Mutable<ILogicalExpression> conditionRef = select.getCondition();
+        ILogicalOperator primaryIndexUnnestOp = createSecondaryToPrimaryPlan(selectRef, conditionRef, subTree, null,
+                chosenIndex, analysisCtx, false, false, false, context);
+        if (primaryIndexUnnestOp == null) {
+            return false;
+        }
+        Mutable<ILogicalOperator> opRef = (subTree.assignsAndUnnestsRefs.isEmpty()) ? null
+                : subTree.assignsAndUnnestsRefs.get(0);
+        ILogicalOperator op = null;
+        if (opRef != null) {
+            op = opRef.getValue();
+        }
+        // Generate new select using the new condition.
+        if (conditionRef.getValue() != null) {
+            select.getInputs().clear();
+            if (op != null) {
+                subTree.dataSourceRef.setValue(primaryIndexUnnestOp);
+                select.getInputs().add(new MutableObject<ILogicalOperator>(op));
+            } else {
+                select.getInputs().add(new MutableObject<ILogicalOperator>(primaryIndexUnnestOp));
+            }
+        } else {
+            ((AbstractLogicalOperator) primaryIndexUnnestOp).setExecutionMode(ExecutionMode.PARTITIONED);
+            if (op != null) {
+                subTree.dataSourceRef.setValue(primaryIndexUnnestOp);
+                selectRef.setValue(op);
+            } else {
+                selectRef.setValue(primaryIndexUnnestOp);
+            }
+        }
+        return true;
+    }
+
+    @Override
+    public boolean applyJoinPlanTransformation(Mutable<ILogicalOperator> joinRef,
+            OptimizableOperatorSubTree leftSubTree, OptimizableOperatorSubTree rightSubTree, Index chosenIndex,
+            AccessMethodAnalysisContext analysisCtx, IOptimizationContext context, boolean isLeftOuterJoin,
+            boolean hasGroupBy) throws AlgebricksException {
+        AbstractBinaryJoinOperator joinOp = (AbstractBinaryJoinOperator) joinRef.getValue();
+        Mutable<ILogicalExpression> conditionRef = joinOp.getCondition();
+        // Determine if the index is applicable on the left or right side (if both, we arbitrarily prefer the left side).
+        Dataset dataset = analysisCtx.indexDatasetMap.get(chosenIndex);
+        // Determine probe and index subtrees based on chosen index.
+        OptimizableOperatorSubTree indexSubTree = null;
+        OptimizableOperatorSubTree probeSubTree = null;
+        if (!isLeftOuterJoin && leftSubTree.hasDataSourceScan()
+                && dataset.getDatasetName().equals(leftSubTree.dataset.getDatasetName())) {
+            indexSubTree = leftSubTree;
+            probeSubTree = rightSubTree;
+        } else if (rightSubTree.hasDataSourceScan()
+                && dataset.getDatasetName().equals(rightSubTree.dataset.getDatasetName())) {
+            indexSubTree = rightSubTree;
+            probeSubTree = leftSubTree;
+        }
+        if (indexSubTree == null) {
+            //This may happen for left outer join case
+            return false;
+        }
+
+        LogicalVariable newNullPlaceHolderVar = null;
+        if (isLeftOuterJoin) {
+            //get a new null place holder variable that is the first field variable of the primary key
+            //from the indexSubTree's datasourceScanOp
+            newNullPlaceHolderVar = indexSubTree.getDataSourceVariables().get(0);
+        }
+
+        ILogicalOperator primaryIndexUnnestOp = createSecondaryToPrimaryPlan(joinRef, conditionRef, indexSubTree,
+                probeSubTree, chosenIndex, analysisCtx, true, isLeftOuterJoin, true, context);
+        if (primaryIndexUnnestOp == null) {
+            return false;
+        }
+
+        if (isLeftOuterJoin && hasGroupBy) {
+            //reset the null place holder variable
+            AccessMethodUtils.resetLOJNullPlaceholderVariableInGroupByOp(analysisCtx, newNullPlaceHolderVar, context);
+        }
+
+        // If there are conditions left, add a new select operator on top.
+        indexSubTree.dataSourceRef.setValue(primaryIndexUnnestOp);
+        if (conditionRef.getValue() != null) {
+            SelectOperator topSelect = new SelectOperator(conditionRef, isLeftOuterJoin, newNullPlaceHolderVar);
+            topSelect.getInputs().add(indexSubTree.rootRef);
+            topSelect.setExecutionMode(ExecutionMode.LOCAL);
+            context.computeAndSetTypeEnvironmentForOperator(topSelect);
+            // Replace the original join with the new subtree rooted at the select op.
+            joinRef.setValue(topSelect);
+        } else {
+            joinRef.setValue(indexSubTree.rootRef.getValue());
+        }
+        return true;
+    }
+
+    private ILogicalOperator createSecondaryToPrimaryPlan(Mutable<ILogicalOperator> topOpRef,
+            Mutable<ILogicalExpression> conditionRef, OptimizableOperatorSubTree indexSubTree,
+            OptimizableOperatorSubTree probeSubTree, Index chosenIndex, AccessMethodAnalysisContext analysisCtx,
+            boolean retainInput, boolean retainNull, boolean requiresBroadcast, IOptimizationContext context)
+            throws AlgebricksException {
+        Dataset dataset = indexSubTree.dataset;
+        ARecordType recordType = indexSubTree.recordType;
+        // we made sure indexSubTree has datasource scan
+        AbstractDataSourceOperator dataSourceOp = (AbstractDataSourceOperator) indexSubTree.dataSourceRef.getValue();
+        List<Pair<Integer, Integer>> exprAndVarList = analysisCtx.indexExprsAndVars.get(chosenIndex);
+        List<IOptimizableFuncExpr> matchedFuncExprs = analysisCtx.matchedFuncExprs;
+        int numSecondaryKeys = analysisCtx.indexNumMatchedKeys.get(chosenIndex);
+        // List of function expressions that will be replaced by the secondary-index search.
+        // These func exprs will be removed from the select condition at the very end of this method.
+        Set<ILogicalExpression> replacedFuncExprs = new HashSet<ILogicalExpression>();
+
+        // Info on high and low keys for the BTree search predicate.
+        ILogicalExpression[] lowKeyExprs = new ILogicalExpression[numSecondaryKeys];
+        ILogicalExpression[] highKeyExprs = new ILogicalExpression[numSecondaryKeys];
+        LimitType[] lowKeyLimits = new LimitType[numSecondaryKeys];
+        LimitType[] highKeyLimits = new LimitType[numSecondaryKeys];
+        boolean[] lowKeyInclusive = new boolean[numSecondaryKeys];
+        boolean[] highKeyInclusive = new boolean[numSecondaryKeys];
+
+        // TODO: For now we don't do any sophisticated analysis of the func exprs to come up with "the best" range predicate.
+        // If we can't figure out how to integrate a certain funcExpr into the current predicate, we just bail by setting this flag.
+        boolean couldntFigureOut = false;
+        boolean doneWithExprs = false;
+        boolean isEqCondition = false;
+        // TODO: For now don't consider prefix searches.
+        BitSet setLowKeys = new BitSet(numSecondaryKeys);
+        BitSet setHighKeys = new BitSet(numSecondaryKeys);
+        // Go through the func exprs listed as optimizable by the chosen index,
+        // and formulate a range predicate on the secondary-index keys.
+
+        // checks whether a type casting happened from a real (FLOAT, DOUBLE) value to an INT value
+        // since we have a round issues when dealing with LT(<) OR GT(>) operator.
+        boolean realTypeConvertedToIntegerType = false;
+
+        for (Pair<Integer, Integer> exprIndex : exprAndVarList) {
+            // Position of the field of matchedFuncExprs.get(exprIndex) in the chosen index's indexed exprs.
+            IOptimizableFuncExpr optFuncExpr = matchedFuncExprs.get(exprIndex.first);
+            int keyPos = indexOf(optFuncExpr.getFieldName(0), chosenIndex.getKeyFieldNames());
+            if (keyPos < 0) {
+                if (optFuncExpr.getNumLogicalVars() > 1) {
+                    // If we are optimizing a join, the matching field may be the second field name.
+                    keyPos = indexOf(optFuncExpr.getFieldName(1), chosenIndex.getKeyFieldNames());
+                }
+            }
+            if (keyPos < 0) {
+                throw new AlgebricksException(
+                        "Could not match optimizable function expression to any index field name.");
+            }
+            Pair<ILogicalExpression, Boolean> returnedSearchKeyExpr = AccessMethodUtils.createSearchKeyExpr(
+                    optFuncExpr, indexSubTree, probeSubTree);
+            ILogicalExpression searchKeyExpr = returnedSearchKeyExpr.first;
+            realTypeConvertedToIntegerType = returnedSearchKeyExpr.second;
+
+            LimitType limit = getLimitType(optFuncExpr, probeSubTree);
+
+            // 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, for 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
+            // fail after truncating the fraction part (there is no INT whose value is greater than 2 and less than 3.)
+            //
+            // Therefore, we convert LT(<) to LE(<=) and GT(>) to GE(>=) to find candidates.
+            // This does not change the result of an actual comparison since this conversion is only applied
+            // for finding candidates from an index.
+            //
+            if (realTypeConvertedToIntegerType) {
+                if (limit == LimitType.HIGH_EXCLUSIVE) {
+                    limit = LimitType.HIGH_INCLUSIVE;
+                } else if (limit == LimitType.LOW_EXCLUSIVE) {
+                    limit = LimitType.LOW_INCLUSIVE;
+                }
+            }
+
+            switch (limit) {
+                case EQUAL: {
+                    if (lowKeyLimits[keyPos] == null && highKeyLimits[keyPos] == null) {
+                        lowKeyLimits[keyPos] = highKeyLimits[keyPos] = limit;
+                        lowKeyInclusive[keyPos] = highKeyInclusive[keyPos] = true;
+                        lowKeyExprs[keyPos] = highKeyExprs[keyPos] = searchKeyExpr;
+                        setLowKeys.set(keyPos);
+                        setHighKeys.set(keyPos);
+                        isEqCondition = true;
+                    } else {
+                        // Has already been set to the identical values. When optimizing join we may encounter the same optimizable expression twice
+                        // (once from analyzing each side of the join)
+                        if (lowKeyLimits[keyPos] == limit && lowKeyInclusive[keyPos] == true
+                                && lowKeyExprs[keyPos].equals(searchKeyExpr) && highKeyLimits[keyPos] == limit
+                                && highKeyInclusive[keyPos] == true && highKeyExprs[keyPos].equals(searchKeyExpr)) {
+                            isEqCondition = true;
+                            break;
+                        }
+                        couldntFigureOut = true;
+                    }
+                    // TODO: For now don't consider prefix searches.
+                    // If high and low keys are set, we exit for now.
+                    if (setLowKeys.cardinality() == numSecondaryKeys && setHighKeys.cardinality() == numSecondaryKeys) {
+                        doneWithExprs = true;
+                    }
+                    break;
+                }
+                case HIGH_EXCLUSIVE: {
+                    if (highKeyLimits[keyPos] == null || (highKeyLimits[keyPos] != null && highKeyInclusive[keyPos])) {
+                        highKeyLimits[keyPos] = limit;
+                        highKeyExprs[keyPos] = searchKeyExpr;
+                        highKeyInclusive[keyPos] = false;
+                    } else {
+                        // Has already been set to the identical values. When optimizing join we may encounter the same optimizable expression twice
+                        // (once from analyzing each side of the join)
+                        if (highKeyLimits[keyPos] == limit && highKeyInclusive[keyPos] == false
+                                && highKeyExprs[keyPos].equals(searchKeyExpr)) {
+                            break;
+                        }
+                        couldntFigureOut = true;
+                        doneWithExprs = true;
+                    }
+                    break;
+                }
+                case HIGH_INCLUSIVE: {
+                    if (highKeyLimits[keyPos] == null) {
+                        highKeyLimits[keyPos] = limit;
+                        highKeyExprs[keyPos] = searchKeyExpr;
+                        highKeyInclusive[keyPos] = true;
+                    } else {
+                        // Has already been set to the identical values. When optimizing join we may encounter the same optimizable expression twice
+                        // (once from analyzing each side of the join)
+                        if (highKeyLimits[keyPos] == limit && highKeyInclusive[keyPos] == true
+                                && highKeyExprs[keyPos].equals(searchKeyExpr)) {
+                            break;
+                        }
+                        couldntFigureOut = true;
+                        doneWithExprs = true;
+                    }
+                    break;
+                }
+                case LOW_EXCLUSIVE: {
+                    if (lowKeyLimits[keyPos] == null || (lowKeyLimits[keyPos] != null && lowKeyInclusive[keyPos])) {
+                        lowKeyLimits[keyPos] = limit;
+                        lowKeyExprs[keyPos] = searchKeyExpr;
+                        lowKeyInclusive[keyPos] = false;
+                    } else {
+                        // Has already been set to the identical values. When optimizing join we may encounter the same optimizable expression twice
+                        // (once from analyzing each side of the join)
+                        if (lowKeyLimits[keyPos] == limit && lowKeyInclusive[keyPos] == false
+                                && lowKeyExprs[keyPos].equals(searchKeyExpr)) {
+                            break;
+                        }
+                        couldntFigureOut = true;
+                        doneWithExprs = true;
+                    }
+                    break;
+                }
+                case LOW_INCLUSIVE: {
+                    if (lowKeyLimits[keyPos] == null) {
+                        lowKeyLimits[keyPos] = limit;
+                        lowKeyExprs[keyPos] = searchKeyExpr;
+                        lowKeyInclusive[keyPos] = true;
+                    } else {
+                        // Has already been set to the identical values. When optimizing join we may encounter the same optimizable expression twice
+                        // (once from analyzing each side of the join)
+                        if (lowKeyLimits[keyPos] == limit && lowKeyInclusive[keyPos] == true
+                                && lowKeyExprs[keyPos].equals(searchKeyExpr)) {
+                            break;
+                        }
+                        couldntFigureOut = true;
+                        doneWithExprs = true;
+                    }
+                    break;
+                }
+                default: {
+                    throw new IllegalStateException();
+                }
+            }
+            if (!couldntFigureOut) {
+                // Remember to remove this funcExpr later.
+                replacedFuncExprs.add(matchedFuncExprs.get(exprIndex.first).getFuncExpr());
+            }
+            if (doneWithExprs) {
+                break;
+            }
+        }
+        if (couldntFigureOut) {
+            return null;
+        }
+
+        // If the select condition contains mixed open/closed intervals on multiple keys, then we make all intervals closed to obtain a superset of answers and leave the original selection in place.
+        boolean primaryIndexPostProccessingIsNeeded = false;
+        for (int i = 1; i < numSecondaryKeys; ++i) {
+            if (lowKeyInclusive[i] != lowKeyInclusive[0]) {
+                Arrays.fill(lowKeyInclusive, true);
+                primaryIndexPostProccessingIsNeeded = true;
+                break;
+            }
+        }
+        for (int i = 1; i < numSecondaryKeys; ++i) {
+            if (highKeyInclusive[i] != highKeyInclusive[0]) {
+                Arrays.fill(highKeyInclusive, true);
+                primaryIndexPostProccessingIsNeeded = true;
+                break;
+            }
+        }
+
+        // determine cases when prefix search could be applied
+        for (int i = 1; i < lowKeyExprs.length; i++) {
+            if (lowKeyLimits[0] == null && lowKeyLimits[i] != null || lowKeyLimits[0] != null
+                    && lowKeyLimits[i] == null || highKeyLimits[0] == null && highKeyLimits[i] != null
+                    || highKeyLimits[0] != null && highKeyLimits[i] == null) {
+                numSecondaryKeys--;
+                primaryIndexPostProccessingIsNeeded = true;
+            }
+        }
+        if (lowKeyLimits[0] == null) {
+            lowKeyInclusive[0] = true;
+        }
+        if (highKeyLimits[0] == null) {
+            highKeyInclusive[0] = true;
+        }
+
+        // Here we generate vars and funcs for assigning the secondary-index keys to be fed into the secondary-index search.
+        // List of variables for the assign.
+        ArrayList<LogicalVariable> keyVarList = new ArrayList<LogicalVariable>();
+        // List of variables and expressions for the assign.
+        ArrayList<LogicalVariable> assignKeyVarList = new ArrayList<LogicalVariable>();
+        ArrayList<Mutable<ILogicalExpression>> assignKeyExprList = new ArrayList<Mutable<ILogicalExpression>>();
+        int numLowKeys = createKeyVarsAndExprs(numSecondaryKeys, lowKeyLimits, lowKeyExprs, assignKeyVarList,
+                assignKeyExprList, keyVarList, context);
+        int numHighKeys = createKeyVarsAndExprs(numSecondaryKeys, highKeyLimits, highKeyExprs, assignKeyVarList,
+                assignKeyExprList, keyVarList, context);
+
+        BTreeJobGenParams jobGenParams = new BTreeJobGenParams(chosenIndex.getIndexName(), IndexType.BTREE,
+                dataset.getDataverseName(), dataset.getDatasetName(), retainInput, retainNull, requiresBroadcast);
+        jobGenParams.setLowKeyInclusive(lowKeyInclusive[0]);
+        jobGenParams.setHighKeyInclusive(highKeyInclusive[0]);
+        jobGenParams.setIsEqCondition(isEqCondition);
+        jobGenParams.setLowKeyVarList(keyVarList, 0, numLowKeys);
+        jobGenParams.setHighKeyVarList(keyVarList, numLowKeys, numHighKeys);
+
+        ILogicalOperator inputOp = null;
+        if (!assignKeyVarList.isEmpty()) {
+            // Assign operator that sets the constant secondary-index search-key fields if necessary.
+            AssignOperator assignConstantSearchKeys = new AssignOperator(assignKeyVarList, assignKeyExprList);
+            // Input to this assign is the EmptyTupleSource (which the dataSourceScan also must have had as input).
+            assignConstantSearchKeys.getInputs().add(dataSourceOp.getInputs().get(0));
+            assignConstantSearchKeys.setExecutionMode(dataSourceOp.getExecutionMode());
+            inputOp = assignConstantSearchKeys;
+        } else {
+            // All index search keys are variables.
+            inputOp = probeSubTree.root;
+        }
+
+        UnnestMapOperator secondaryIndexUnnestOp = AccessMethodUtils.createSecondaryIndexUnnestMap(dataset, recordType,
+                chosenIndex, inputOp, jobGenParams, context, false, retainInput);
+
+        // Generate the rest of the upstream plan which feeds the search results into the primary index.
+        UnnestMapOperator primaryIndexUnnestOp = null;
+        boolean isPrimaryIndex = chosenIndex.isPrimaryIndex();
+        if (dataset.getDatasetType() == DatasetType.EXTERNAL) {
+            // External dataset
+            ExternalDataLookupOperator externalDataAccessOp = AccessMethodUtils.createExternalDataLookupUnnestMap(
+                    dataSourceOp, dataset, recordType, secondaryIndexUnnestOp, context, chosenIndex, retainInput,
+                    retainNull);
+            indexSubTree.dataSourceRef.setValue(externalDataAccessOp);
+            return externalDataAccessOp;
+        } else if (!isPrimaryIndex) {
+            primaryIndexUnnestOp = AccessMethodUtils.createPrimaryIndexUnnestMap(dataSourceOp, dataset, recordType,
+                    secondaryIndexUnnestOp, context, true, retainInput, retainNull, false);
+
+            // Replace the datasource scan with the new plan rooted at
+            // primaryIndexUnnestMap.
+            indexSubTree.dataSourceRef.setValue(primaryIndexUnnestOp);
+        } else {
+            List<Object> primaryIndexOutputTypes = new ArrayList<Object>();
+            try {
+                AccessMethodUtils.appendPrimaryIndexTypes(dataset, recordType, primaryIndexOutputTypes);
+            } catch (IOException e) {
+                throw new AlgebricksException(e);
+            }
+            List<LogicalVariable> scanVariables = dataSourceOp.getVariables();
+            primaryIndexUnnestOp = new UnnestMapOperator(scanVariables, secondaryIndexUnnestOp.getExpressionRef(),
+                    primaryIndexOutputTypes, retainInput);
+            primaryIndexUnnestOp.getInputs().add(new MutableObject<ILogicalOperator>(inputOp));
+
+            if (!primaryIndexPostProccessingIsNeeded) {
+                List<Mutable<ILogicalExpression>> remainingFuncExprs = new ArrayList<Mutable<ILogicalExpression>>();
+                getNewConditionExprs(conditionRef, replacedFuncExprs, remainingFuncExprs);
+                // Generate new condition.
+                if (!remainingFuncExprs.isEmpty()) {
+                    ILogicalExpression pulledCond = createSelectCondition(remainingFuncExprs);
+                    conditionRef.setValue(pulledCond);
+                } else {
+                    conditionRef.setValue(null);
+                }
+            }
+
+            // Adds equivalence classes --- one equivalent class between a primary key
+            // variable and a record field-access expression.
+            EquivalenceClassUtils.addEquivalenceClassesForPrimaryIndexAccess(primaryIndexUnnestOp, scanVariables,
+                    recordType, dataset, context);
+        }
+
+        return primaryIndexUnnestOp;
+    }
+
+    private int createKeyVarsAndExprs(int numKeys, LimitType[] keyLimits, ILogicalExpression[] searchKeyExprs,
+            ArrayList<LogicalVariable> assignKeyVarList, ArrayList<Mutable<ILogicalExpression>> assignKeyExprList,
+            ArrayList<LogicalVariable> keyVarList, IOptimizationContext context) {
+        if (keyLimits[0] == null) {
+            return 0;
+        }
+        for (int i = 0; i < numKeys; i++) {
+            ILogicalExpression searchKeyExpr = searchKeyExprs[i];
+            LogicalVariable keyVar = null;
+            if (searchKeyExpr.getExpressionTag() == LogicalExpressionTag.CONSTANT) {
+                keyVar = context.newVar();
+                assignKeyExprList.add(new MutableObject<ILogicalExpression>(searchKeyExpr));
+                assignKeyVarList.add(keyVar);
+            } else {
+                keyVar = ((VariableReferenceExpression) searchKeyExpr).getVariableReference();
+            }
+            keyVarList.add(keyVar);
+        }
+        return numKeys;
+    }
+
+    private void getNewConditionExprs(Mutable<ILogicalExpression> conditionRef,
+            Set<ILogicalExpression> replacedFuncExprs, List<Mutable<ILogicalExpression>> remainingFuncExprs) {
+        remainingFuncExprs.clear();
+        if (replacedFuncExprs.isEmpty()) {
+            return;
+        }
+        AbstractFunctionCallExpression funcExpr = (AbstractFunctionCallExpression) conditionRef.getValue();
+        if (replacedFuncExprs.size() == 1) {
+            Iterator<ILogicalExpression> it = replacedFuncExprs.iterator();
+            if (!it.hasNext()) {
+                return;
+            }
+            if (funcExpr == it.next()) {
+                // There are no remaining function exprs.
+                return;
+            }
+        }
+        // The original select cond must be an AND. Check it just to be sure.
+        if (funcExpr.getFunctionIdentifier() != AlgebricksBuiltinFunctions.AND) {
+            throw new IllegalStateException();
+        }
+        // Clean the conjuncts.
+        for (Mutable<ILogicalExpression> arg : funcExpr.getArguments()) {
+            ILogicalExpression argExpr = arg.getValue();
+            if (argExpr.getExpressionTag() != LogicalExpressionTag.FUNCTION_CALL) {
+                continue;
+            }
+            // If the function expression was not replaced by the new index
+            // plan, then add it to the list of remaining function expressions.
+            if (!replacedFuncExprs.contains(argExpr)) {
+                remainingFuncExprs.add(arg);
+            }
+        }
+    }
+
+    private <T> int indexOf(T value, List<T> coll) {
+        int i = 0;
+        for (T member : coll) {
+            if (member.equals(value)) {
+                return i;
+            }
+            i++;
+        }
+        return -1;
+    }
+
+    private LimitType getLimitType(IOptimizableFuncExpr optFuncExpr, OptimizableOperatorSubTree probeSubTree) {
+        ComparisonKind ck = AlgebricksBuiltinFunctions.getComparisonType(optFuncExpr.getFuncExpr()
+                .getFunctionIdentifier());
+        LimitType limit = null;
+        switch (ck) {
+            case EQ: {
+                limit = LimitType.EQUAL;
+                break;
+            }
+            case GE: {
+                limit = probeIsOnLhs(optFuncExpr, probeSubTree) ? LimitType.HIGH_INCLUSIVE : LimitType.LOW_INCLUSIVE;
+                break;
+            }
+            case GT: {
+                limit = probeIsOnLhs(optFuncExpr, probeSubTree) ? LimitType.HIGH_EXCLUSIVE : LimitType.LOW_EXCLUSIVE;
+                break;
+            }
+            case LE: {
+                limit = probeIsOnLhs(optFuncExpr, probeSubTree) ? LimitType.LOW_INCLUSIVE : LimitType.HIGH_INCLUSIVE;
+                break;
+            }
+            case LT: {
+                limit = probeIsOnLhs(optFuncExpr, probeSubTree) ? LimitType.LOW_EXCLUSIVE : LimitType.HIGH_EXCLUSIVE;
+                break;
+            }
+            case NEQ: {
+                limit = null;
+                break;
+            }
+            default: {
+                throw new IllegalStateException();
+            }
+        }
+        return limit;
+    }
+
+    private boolean probeIsOnLhs(IOptimizableFuncExpr optFuncExpr, OptimizableOperatorSubTree probeSubTree) {
+        if (probeSubTree == null) {
+            // We are optimizing a selection query. Search key is a constant. Return true if constant is on lhs.
+            return optFuncExpr.getFuncExpr().getArguments().get(0) == optFuncExpr.getConstantVal(0);
+        } else {
+            // We are optimizing a join query. Determine whether the feeding variable is on the lhs.
+            return (optFuncExpr.getOperatorSubTree(0) == null || optFuncExpr.getOperatorSubTree(0) == probeSubTree);
+        }
+    }
+
+    private ILogicalExpression createSelectCondition(List<Mutable<ILogicalExpression>> predList) {
+        if (predList.size() > 1) {
+            IFunctionInfo finfo = FunctionUtils.getFunctionInfo(AlgebricksBuiltinFunctions.AND);
+            return new ScalarFunctionCallExpression(finfo, predList);
+        }
+        return predList.get(0).getValue();
+    }
+
+    @Override
+    public boolean exprIsOptimizable(Index index, IOptimizableFuncExpr optFuncExpr) {
+        // If we are optimizing a join, check for the indexed nested-loop join hint.
+        if (optFuncExpr.getNumLogicalVars() == 2) {
+            if (!optFuncExpr.getFuncExpr().getAnnotations().containsKey(IndexedNLJoinExpressionAnnotation.INSTANCE)) {
+                return false;
+            }
+        }
+        if (!index.isPrimaryIndex()
+                && optFuncExpr.getFuncExpr().getAnnotations()
+                        .containsKey(SkipSecondaryIndexSearchExpressionAnnotation.INSTANCE)) {
+            return false;
+        }
+        // No additional analysis required for BTrees.
+        return true;
+    }
+}
\ No newline at end of file

http://git-wip-us.apache.org/repos/asf/incubator-asterixdb/blob/34d81630/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/am/BTreeJobGenParams.java
----------------------------------------------------------------------
diff --git a/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/am/BTreeJobGenParams.java b/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/am/BTreeJobGenParams.java
new file mode 100644
index 0000000..a3df9d3
--- /dev/null
+++ b/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/am/BTreeJobGenParams.java
@@ -0,0 +1,134 @@
+/*
+ * Copyright 2009-2013 by The Regents of the University of California
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * you may obtain a copy of the License from
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package edu.uci.ics.asterix.optimizer.rules.am;
+
+import java.util.ArrayList;
+import java.util.List;
+
+import org.apache.commons.lang3.mutable.Mutable;
+import org.apache.commons.lang3.mutable.MutableObject;
+
+import edu.uci.ics.asterix.common.config.DatasetConfig.IndexType;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.ILogicalExpression;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.LogicalVariable;
+import edu.uci.ics.hyracks.algebricks.core.algebra.expressions.ConstantExpression;
+
+/**
+ * Helper class for reading and writing job-gen parameters for BTree access methods to
+ * and from a list of function arguments, typically of an unnest-map.
+ */
+public class BTreeJobGenParams extends AccessMethodJobGenParams {
+
+    protected List<LogicalVariable> lowKeyVarList;
+    protected List<LogicalVariable> highKeyVarList;
+
+    protected boolean lowKeyInclusive;
+    protected boolean highKeyInclusive;
+    protected boolean isEqCondition;
+
+    public BTreeJobGenParams() {
+        super();
+    }
+
+    public BTreeJobGenParams(String indexName, IndexType indexType, String dataverseName, String datasetName,
+            boolean retainInput, boolean retainNull, boolean requiresBroadcast) {
+        super(indexName, indexType, dataverseName, datasetName, retainInput, retainNull, requiresBroadcast);
+    }
+
+    public void setLowKeyVarList(List<LogicalVariable> keyVarList, int startIndex, int numKeys) {
+        lowKeyVarList = new ArrayList<LogicalVariable>(numKeys);
+        setKeyVarList(keyVarList, lowKeyVarList, startIndex, numKeys);
+    }
+
+    public void setHighKeyVarList(List<LogicalVariable> keyVarList, int startIndex, int numKeys) {
+        highKeyVarList = new ArrayList<LogicalVariable>(numKeys);
+        setKeyVarList(keyVarList, highKeyVarList, startIndex, numKeys);
+    }
+
+    private void setKeyVarList(List<LogicalVariable> src, List<LogicalVariable> dest, int startIndex, int numKeys) {
+        for (int i = 0; i < numKeys; i++) {
+            dest.add(src.get(startIndex + i));
+        }
+    }
+
+    public void setLowKeyInclusive(boolean lowKeyInclusive) {
+        this.lowKeyInclusive = lowKeyInclusive;
+    }
+
+    public void setHighKeyInclusive(boolean highKeyInclusive) {
+        this.highKeyInclusive = highKeyInclusive;
+    }
+
+    public void setIsEqCondition(boolean isEqConsition) {
+        this.isEqCondition = isEqConsition;
+    }
+
+    public void writeToFuncArgs(List<Mutable<ILogicalExpression>> funcArgs) {
+        super.writeToFuncArgs(funcArgs);
+        writeVarList(lowKeyVarList, funcArgs);
+        writeVarList(highKeyVarList, funcArgs);
+        writeBoolean(lowKeyInclusive, funcArgs);
+        writeBoolean(highKeyInclusive, funcArgs);
+        writeBoolean(isEqCondition, funcArgs);
+    }
+
+    public void readFromFuncArgs(List<Mutable<ILogicalExpression>> funcArgs) {
+        super.readFromFuncArgs(funcArgs);
+        int index = super.getNumParams();
+        lowKeyVarList = new ArrayList<LogicalVariable>();
+        highKeyVarList = new ArrayList<LogicalVariable>();
+        int nextIndex = readVarList(funcArgs, index, lowKeyVarList);
+        nextIndex = readVarList(funcArgs, nextIndex, highKeyVarList);
+        nextIndex = readKeyInclusives(funcArgs, nextIndex);
+        readIsEqCondition(funcArgs, nextIndex);
+    }
+
+    private int readKeyInclusives(List<Mutable<ILogicalExpression>> funcArgs, int index) {
+        lowKeyInclusive = ((ConstantExpression) funcArgs.get(index).getValue()).getValue().isTrue();
+        // Read the next function argument at index + 1.
+        highKeyInclusive = ((ConstantExpression) funcArgs.get(index + 1).getValue()).getValue().isTrue();
+        // We have read two of the function arguments, so the next index is at index + 2.
+        return index + 2;
+    }
+
+    private void readIsEqCondition(List<Mutable<ILogicalExpression>> funcArgs, int index) {
+        isEqCondition = ((ConstantExpression) funcArgs.get(index).getValue()).getValue().isTrue();
+    }
+
+    private void writeBoolean(boolean val, List<Mutable<ILogicalExpression>> funcArgs) {
+        ILogicalExpression keyExpr = val ? ConstantExpression.TRUE : ConstantExpression.FALSE;
+        funcArgs.add(new MutableObject<ILogicalExpression>(keyExpr));
+    }
+
+    public List<LogicalVariable> getLowKeyVarList() {
+        return lowKeyVarList;
+    }
+
+    public List<LogicalVariable> getHighKeyVarList() {
+        return highKeyVarList;
+    }
+
+    public boolean isEqCondition() {
+        return isEqCondition;
+    }
+
+    public boolean isLowKeyInclusive() {
+        return lowKeyInclusive;
+    }
+
+    public boolean isHighKeyInclusive() {
+        return highKeyInclusive;
+    }
+}

http://git-wip-us.apache.org/repos/asf/incubator-asterixdb/blob/34d81630/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/am/IAccessMethod.java
----------------------------------------------------------------------
diff --git a/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/am/IAccessMethod.java b/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/am/IAccessMethod.java
new file mode 100644
index 0000000..d03d1a0
--- /dev/null
+++ b/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/am/IAccessMethod.java
@@ -0,0 +1,96 @@
+/*
+ * Copyright 2009-2013 by The Regents of the University of California
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * you may obtain a copy of the License from
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package edu.uci.ics.asterix.optimizer.rules.am;
+
+import java.util.List;
+
+import org.apache.commons.lang3.mutable.Mutable;
+
+import edu.uci.ics.asterix.metadata.entities.Index;
+import edu.uci.ics.hyracks.algebricks.common.exceptions.AlgebricksException;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.ILogicalOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.IOptimizationContext;
+import edu.uci.ics.hyracks.algebricks.core.algebra.expressions.AbstractFunctionCallExpression;
+import edu.uci.ics.hyracks.algebricks.core.algebra.functions.FunctionIdentifier;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.AbstractLogicalOperator;
+
+/**
+ * Interface that an access method should implement to work with the rewrite
+ * rules to apply it for join and/or selection queries. This interface provides
+ * methods for analyzing a select/join condition, and for rewriting the plan
+ * with a given index.
+ */
+public interface IAccessMethod {
+
+    /**
+     * @return A list of function identifiers that are optimizable by this
+     *         access method.
+     */
+    public List<FunctionIdentifier> getOptimizableFunctions();
+
+    /**
+     * Analyzes the arguments of a given optimizable funcExpr to see if this
+     * access method is applicable (e.g., one arg is a constant and one is a
+     * var). We assume that the funcExpr has already been determined to be
+     * optimizable by this access method based on its function identifier. If
+     * funcExpr has been found to be optimizable, this method adds an
+     * OptimizableFunction to analysisCtx.matchedFuncExprs for further analysis.
+     *
+     * @return true if funcExpr is optimizable by this access method, false
+     *         otherwise
+     */
+    public boolean analyzeFuncExprArgs(AbstractFunctionCallExpression funcExpr,
+            List<AbstractLogicalOperator> assignsAndUnnests, AccessMethodAnalysisContext analysisCtx);
+
+    /**
+     * Indicates whether all index expressions must be matched in order for this
+     * index to be applicable.
+     *
+     * @return boolean
+     */
+    public boolean matchAllIndexExprs();
+
+    /**
+     * Indicates whether this index is applicable if only a prefix of the index
+     * expressions are matched.
+     *
+     * @return boolean
+     */
+    public boolean matchPrefixIndexExprs();
+
+    /**
+     * Applies the plan transformation to use chosenIndex to optimize a selection query.
+     */
+    public boolean applySelectPlanTransformation(Mutable<ILogicalOperator> selectRef,
+            OptimizableOperatorSubTree subTree, Index chosenIndex, AccessMethodAnalysisContext analysisCtx,
+            IOptimizationContext context) throws AlgebricksException;
+
+    /**
+     * Applies the plan transformation to use chosenIndex to optimize a join query.
+     * In the case of a LeftOuterJoin, there may or may not be a needed groupby operation
+     * If there is, we will need to include it in the transformation
+     */
+    public boolean applyJoinPlanTransformation(Mutable<ILogicalOperator> joinRef,
+            OptimizableOperatorSubTree leftSubTree, OptimizableOperatorSubTree rightSubTree, Index chosenIndex,
+            AccessMethodAnalysisContext analysisCtx, IOptimizationContext context, boolean isLeftOuterJoin,
+            boolean hasGroupBy) throws AlgebricksException;
+
+    /**
+     * Analyzes expr to see whether it is optimizable by the given concrete index.
+     * 
+     * @throws AlgebricksException
+     */
+    public boolean exprIsOptimizable(Index index, IOptimizableFuncExpr optFuncExpr) throws AlgebricksException;
+}

http://git-wip-us.apache.org/repos/asf/incubator-asterixdb/blob/34d81630/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/am/IOptimizableFuncExpr.java
----------------------------------------------------------------------
diff --git a/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/am/IOptimizableFuncExpr.java b/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/am/IOptimizableFuncExpr.java
new file mode 100644
index 0000000..326d38b
--- /dev/null
+++ b/asterix-algebra/src/main/java/org/apache/asterix/optimizer/rules/am/IOptimizableFuncExpr.java
@@ -0,0 +1,70 @@
+/*
+ * Copyright 2009-2013 by The Regents of the University of California
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * you may obtain a copy of the License from
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package edu.uci.ics.asterix.optimizer.rules.am;
+
+import java.util.List;
+
+import edu.uci.ics.asterix.om.types.IAType;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.ILogicalExpression;
+import edu.uci.ics.hyracks.algebricks.core.algebra.base.LogicalVariable;
+import edu.uci.ics.hyracks.algebricks.core.algebra.expressions.AbstractFunctionCallExpression;
+import edu.uci.ics.hyracks.algebricks.core.algebra.expressions.IAlgebricksConstantValue;
+
+/**
+ * Describes a function expression that is optimizable by an access method.
+ * Provides convenient methods for accessing arguments (constants, variables)
+ * and metadata of such a function.
+ */
+public interface IOptimizableFuncExpr {
+    public AbstractFunctionCallExpression getFuncExpr();
+
+    public int getNumLogicalVars();
+
+    public int getNumConstantVals();
+
+    public LogicalVariable getLogicalVar(int index);
+
+    public void setLogicalExpr(int index, ILogicalExpression logExpr);
+
+    public ILogicalExpression getLogicalExpr(int index);
+
+    public void setFieldName(int index, List<String> fieldName);
+
+    public List<String> getFieldName(int index);
+
+    public void setFieldType(int index, IAType fieldName);
+
+    public IAType getFieldType(int index);
+
+    public void setOptimizableSubTree(int index, OptimizableOperatorSubTree subTree);
+
+    public OptimizableOperatorSubTree getOperatorSubTree(int index);
+
+    public IAlgebricksConstantValue getConstantVal(int index);
+
+    public int findLogicalVar(LogicalVariable var);
+
+    public int findFieldName(List<String> fieldName);
+
+    public void substituteVar(LogicalVariable original, LogicalVariable substitution);
+
+    public void setPartialField(boolean partialField);
+
+    public boolean containsPartialField();
+
+    public void setSourceVar(int index, LogicalVariable var);
+
+    public LogicalVariable getSourceVar(int index);
+}


Mime
View raw message