You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@asterixdb.apache.org by im...@apache.org on 2015/08/25 18:44:15 UTC
[27/51] [partial] incubator-asterixdb git commit: Change folder
structure for Java repackage
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);
+}