fix for issue 731, needs optimization on existential queries
diff --git a/asterix-algebra/src/main/java/edu/uci/ics/asterix/optimizer/base/RuleCollections.java b/asterix-algebra/src/main/java/edu/uci/ics/asterix/optimizer/base/RuleCollections.java
index c2469dc..b7a8832 100644
--- a/asterix-algebra/src/main/java/edu/uci/ics/asterix/optimizer/base/RuleCollections.java
+++ b/asterix-algebra/src/main/java/edu/uci/ics/asterix/optimizer/base/RuleCollections.java
@@ -32,6 +32,7 @@
import edu.uci.ics.asterix.optimizer.rules.IfElseToSwitchCaseFunctionRule;
import edu.uci.ics.asterix.optimizer.rules.InlineUnnestFunctionRule;
import edu.uci.ics.asterix.optimizer.rules.IntroduceAutogenerateIDRule;
+import edu.uci.ics.asterix.optimizer.rules.IntroduceDistinctByForExistentialSubplanRule;
import edu.uci.ics.asterix.optimizer.rules.IntroduceDynamicTypeCastRule;
import edu.uci.ics.asterix.optimizer.rules.IntroduceEnforcedListTypeRule;
import edu.uci.ics.asterix.optimizer.rules.IntroduceInstantLockSearchCallbackRule;
@@ -180,6 +181,7 @@
condPushDownAndJoinInference.add(new NestGroupByRule());
condPushDownAndJoinInference.add(new EliminateGroupByEmptyKeyRule());
condPushDownAndJoinInference.add(new LeftOuterJoinToInnerJoinRule());
+ condPushDownAndJoinInference.add(new IntroduceDistinctByForExistentialSubplanRule());
return condPushDownAndJoinInference;
}
diff --git a/asterix-algebra/src/main/java/edu/uci/ics/asterix/optimizer/rules/IntroduceDistinctByForExistentialSubplanRule.java b/asterix-algebra/src/main/java/edu/uci/ics/asterix/optimizer/rules/IntroduceDistinctByForExistentialSubplanRule.java
new file mode 100644
index 0000000..c826b3a
--- /dev/null
+++ b/asterix-algebra/src/main/java/edu/uci/ics/asterix/optimizer/rules/IntroduceDistinctByForExistentialSubplanRule.java
@@ -0,0 +1,168 @@
+/*
+ * 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;
+
+import java.util.ArrayList;
+import java.util.HashSet;
+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.om.functions.AsterixBuiltinFunctions;
+import edu.uci.ics.hyracks.algebricks.common.exceptions.AlgebricksException;
+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.AggregateFunctionCallExpression;
+import edu.uci.ics.hyracks.algebricks.core.algebra.expressions.VariableReferenceExpression;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.AbstractLogicalOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.AggregateOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.DistinctOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.SelectOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.SubplanOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.UnnestOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.visitors.VariableUtilities;
+import edu.uci.ics.hyracks.algebricks.core.algebra.properties.FunctionalDependency;
+import edu.uci.ics.hyracks.algebricks.core.rewriter.base.IAlgebraicRewriteRule;
+import edu.uci.ics.hyracks.algebricks.rewriter.util.PhysicalOptimizationsUtil;
+
+/*
+ * Before Plan:
+ * select ($x)
+ * subplan {
+ * aggregate [$x] <- [function-call: asterix:non-empty-stream ]
+ * select (cond($y))
+ * unnest $y <- function-call: asterix:scan-collection
+ * nested tuple source
+ * }
+ * Rest
+ *
+ * After Plan:
+ * distinct (pk of $y)
+ * select(cond($y))
+ * unnest $y <- function-call: asterix:scan-collection
+ * Rest
+ */
+public class IntroduceDistinctByForExistentialSubplanRule implements IAlgebraicRewriteRule {
+
+ @Override
+ public boolean rewritePre(Mutable<ILogicalOperator> opRef, IOptimizationContext context) throws AlgebricksException {
+ return false;
+ }
+
+ @Override
+ public boolean rewritePost(Mutable<ILogicalOperator> opRef, IOptimizationContext context)
+ throws AlgebricksException {
+ AbstractLogicalOperator op0 = (AbstractLogicalOperator) opRef.getValue();
+ if (op0.getOperatorTag() != LogicalOperatorTag.SELECT) {
+ return false;
+ }
+ SelectOperator so = (SelectOperator) op0;
+ if (so.getCondition().getValue().getExpressionTag() != LogicalExpressionTag.VARIABLE) {
+ return false;
+ }
+ AbstractLogicalOperator op1 = (AbstractLogicalOperator) op0.getInputs().get(0).getValue();
+ if (op1.getOperatorTag() != LogicalOperatorTag.SUBPLAN) {
+ return false;
+ }
+ SubplanOperator subplan = (SubplanOperator) op1;
+ if (subplan.getNestedPlans().size() != 1 || subplan.getNestedPlans().get(0).getRoots().size() != 1) {
+ return false;
+ }
+ Mutable<ILogicalOperator> subplanRoot = subplan.getNestedPlans().get(0).getRoots().get(0);
+ AbstractLogicalOperator op2 = (AbstractLogicalOperator) subplanRoot.getValue();
+
+ if (op2.getOperatorTag() != LogicalOperatorTag.AGGREGATE) {
+ return false;
+ }
+ AggregateOperator aggregate = (AggregateOperator) op2;
+ if (aggregate.getExpressions().size() != 1) {
+ return false;
+ }
+ AggregateFunctionCallExpression aggFun = (AggregateFunctionCallExpression) aggregate.getExpressions().get(0).getValue();
+ if (aggFun.getFunctionIdentifier() != AsterixBuiltinFunctions.NON_EMPTY_STREAM) {
+ return false;
+ }
+
+ AbstractLogicalOperator op3 = (AbstractLogicalOperator) aggregate.getInputs().get(0).getValue();
+ if (op3.getOperatorTag() != LogicalOperatorTag.SELECT) {
+ return false;
+ }
+ SelectOperator topSelect = (SelectOperator) op3;
+
+ AbstractLogicalOperator prevOp = op3;
+ AbstractLogicalOperator curOp;
+ do {
+ curOp = (AbstractLogicalOperator) prevOp.getInputs().get(0).getValue();
+ if (curOp.getOperatorTag() == LogicalOperatorTag.NESTEDTUPLESOURCE) {
+ break;
+ }
+ if (curOp.getOperatorTag() != LogicalOperatorTag.SELECT && curOp.getOperatorTag() != LogicalOperatorTag.UNNEST) {
+ return false;
+ }
+ prevOp = curOp;
+ } while (curOp.getInputs().size() == 1);
+
+
+ // Compute distinct by variables
+ Set<LogicalVariable> free = new HashSet<LogicalVariable>();
+ Set<LogicalVariable> pkVars = computeDistinctByVars(topSelect, free, context);
+ if (pkVars == null || pkVars.isEmpty()) {
+ return false;
+ }
+ List<Mutable<ILogicalExpression>> expressions = new ArrayList<Mutable<ILogicalExpression>>();
+ for (LogicalVariable v : pkVars) {
+ ILogicalExpression varExpr = new VariableReferenceExpression(v);
+ expressions.add(new MutableObject<ILogicalExpression>(varExpr));
+ }
+ DistinctOperator distinct = new DistinctOperator(expressions);
+ distinct.getInputs().add(new MutableObject<ILogicalOperator>(topSelect));
+ opRef.setValue(distinct);
+
+ AbstractLogicalOperator bottomOp = (AbstractLogicalOperator) subplan.getInputs().get(0).getValue();
+ List<Mutable<ILogicalOperator>> unnestInputList = prevOp.getInputs();
+ unnestInputList.clear();
+ unnestInputList.add(new MutableObject<ILogicalOperator>(bottomOp));
+
+ context.computeAndSetTypeEnvironmentForOperator(distinct);
+
+ return true;
+ }
+
+ protected Set<LogicalVariable> computeDistinctByVars(AbstractLogicalOperator op, Set<LogicalVariable> freeVars,
+ IOptimizationContext context) throws AlgebricksException {
+ PhysicalOptimizationsUtil.computeFDsAndEquivalenceClasses(op, context);
+ List<FunctionalDependency> fdList = context.getFDList(op);
+ if (fdList == null) {
+ return null;
+ }
+ // check if any of the FDs is a key
+ List<LogicalVariable> all = new ArrayList<LogicalVariable>();
+ VariableUtilities.getLiveVariables(op, all);
+ all.retainAll(freeVars);
+ for (FunctionalDependency fd : fdList) {
+ if (fd.getTail().containsAll(all)) {
+ return new HashSet<LogicalVariable>(fd.getHead());
+ }
+ }
+ return null;
+ }
+
+}
diff --git a/asterix-algebra/src/main/java/edu/uci/ics/asterix/optimizer/rules/am/AbstractIntroduceAccessMethodRule.java b/asterix-algebra/src/main/java/edu/uci/ics/asterix/optimizer/rules/am/AbstractIntroduceAccessMethodRule.java
index 6b68b7f..1023c6d 100644
--- a/asterix-algebra/src/main/java/edu/uci/ics/asterix/optimizer/rules/am/AbstractIntroduceAccessMethodRule.java
+++ b/asterix-algebra/src/main/java/edu/uci/ics/asterix/optimizer/rules/am/AbstractIntroduceAccessMethodRule.java
@@ -29,20 +29,23 @@
import edu.uci.ics.asterix.om.base.AString;
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.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.AbstractLogicalExpression;
import edu.uci.ics.hyracks.algebricks.core.algebra.expressions.ConstantExpression;
+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.FunctionIdentifier;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.AbstractLogicalOperator;
import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.AssignOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.UnnestOperator;
import edu.uci.ics.hyracks.algebricks.core.rewriter.base.IAlgebraicRewriteRule;
/**
@@ -176,7 +179,7 @@
* Analyzes the given selection condition, filling analyzedAMs with applicable access method types.
* At this point we are not yet consulting the metadata whether an actual index exists or not.
*/
- protected boolean analyzeCondition(ILogicalExpression cond, List<AssignOperator> assigns,
+ protected boolean analyzeCondition(ILogicalExpression cond, List<AbstractLogicalOperator> assignsAndUnnests,
Map<IAccessMethod, AccessMethodAnalysisContext> analyzedAMs) {
AbstractFunctionCallExpression funcExpr = (AbstractFunctionCallExpression) cond;
FunctionIdentifier funcIdent = funcExpr.getFunctionIdentifier();
@@ -184,14 +187,14 @@
if (funcIdent == AlgebricksBuiltinFunctions.OR) {
return false;
}
- boolean found = analyzeFunctionExpr(funcExpr, assigns, analyzedAMs);
+ boolean found = analyzeFunctionExpr(funcExpr, assignsAndUnnests, analyzedAMs);
for (Mutable<ILogicalExpression> arg : funcExpr.getArguments()) {
ILogicalExpression argExpr = arg.getValue();
if (argExpr.getExpressionTag() != LogicalExpressionTag.FUNCTION_CALL) {
continue;
}
AbstractFunctionCallExpression argFuncExpr = (AbstractFunctionCallExpression) argExpr;
- boolean matchFound = analyzeFunctionExpr(argFuncExpr, assigns, analyzedAMs);
+ boolean matchFound = analyzeFunctionExpr(argFuncExpr, assignsAndUnnests, analyzedAMs);
found = found || matchFound;
}
return found;
@@ -202,7 +205,7 @@
* on the function identifier, and an analysis of the function's arguments.
* Updates the analyzedAMs accordingly.
*/
- protected boolean analyzeFunctionExpr(AbstractFunctionCallExpression funcExpr, List<AssignOperator> assigns,
+ protected boolean analyzeFunctionExpr(AbstractFunctionCallExpression funcExpr, List<AbstractLogicalOperator> assignsAndUnnests,
Map<IAccessMethod, AccessMethodAnalysisContext> analyzedAMs) {
FunctionIdentifier funcIdent = funcExpr.getFunctionIdentifier();
if (funcIdent == AlgebricksBuiltinFunctions.AND) {
@@ -223,7 +226,7 @@
analysisCtx = newAnalysisCtx;
}
// Analyzes the funcExpr's arguments to see if the accessMethod is truly applicable.
- boolean matchFound = accessMethod.analyzeFuncExprArgs(funcExpr, assigns, analysisCtx);
+ boolean matchFound = accessMethod.analyzeFuncExprArgs(funcExpr, assignsAndUnnests, analysisCtx);
if (matchFound) {
// If we've used the current new context placeholder, replace it with a new one.
if (analysisCtx == newAnalysisCtx) {
@@ -270,21 +273,43 @@
throws AlgebricksException {
for (int optFuncExprIndex = 0; optFuncExprIndex < analysisCtx.matchedFuncExprs.size(); optFuncExprIndex++) {
IOptimizableFuncExpr optFuncExpr = analysisCtx.matchedFuncExprs.get(optFuncExprIndex);
- // Try to match variables from optFuncExpr to assigns.
- for (int assignIndex = 0; assignIndex < subTree.assigns.size(); assignIndex++) {
- AssignOperator assignOp = subTree.assigns.get(assignIndex);
- List<LogicalVariable> varList = assignOp.getVariables();
- for (int varIndex = 0; varIndex < varList.size(); varIndex++) {
- LogicalVariable var = varList.get(varIndex);
+ // Try to match variables from optFuncExpr to assigns or unnests.
+ for (int assignOrUnnestIndex = 0; assignOrUnnestIndex < subTree.assignsAndUnnests.size(); assignOrUnnestIndex++) {
+ AbstractLogicalOperator op = subTree.assignsAndUnnests.get(assignOrUnnestIndex);
+ if (op.getOperatorTag() == LogicalOperatorTag.ASSIGN) {
+ AssignOperator assignOp = (AssignOperator) op;
+ List<LogicalVariable> varList = assignOp.getVariables();
+ for (int varIndex = 0; varIndex < varList.size(); varIndex++) {
+ LogicalVariable var = varList.get(varIndex);
+ int funcVarIndex = optFuncExpr.findLogicalVar(var);
+ // No matching var in optFuncExpr.
+ if (funcVarIndex == -1) {
+ continue;
+ }
+ // At this point we have matched the optimizable func expr at optFuncExprIndex to an assigned variable.
+ // Remember matching subtree.
+ optFuncExpr.setOptimizableSubTree(funcVarIndex, subTree);
+ String fieldName = getFieldNameFromSubTree(optFuncExpr, subTree, assignOrUnnestIndex, varIndex);
+ if (fieldName == null) {
+ continue;
+ }
+ // Set the fieldName in the corresponding matched function expression.
+ optFuncExpr.setFieldName(funcVarIndex, fieldName);
+ fillIndexExprs(fieldName, optFuncExprIndex, subTree.dataset, analysisCtx);
+ }
+ }
+ else {
+ UnnestOperator unnestOp = (UnnestOperator) op;
+ LogicalVariable var = unnestOp.getVariable();
int funcVarIndex = optFuncExpr.findLogicalVar(var);
// No matching var in optFuncExpr.
if (funcVarIndex == -1) {
continue;
}
- // At this point we have matched the optimizable func expr at optFuncExprIndex to an assigned variable.
+ // At this point we have matched the optimizable func expr at optFuncExprIndex to an unnest variable.
// Remember matching subtree.
optFuncExpr.setOptimizableSubTree(funcVarIndex, subTree);
- String fieldName = getFieldNameOfFieldAccess(assignOp, subTree.recordType, varIndex);
+ String fieldName = getFieldNameFromSubTree(optFuncExpr, subTree, assignOrUnnestIndex, 0);
if (fieldName == null) {
continue;
}
@@ -293,6 +318,7 @@
fillIndexExprs(fieldName, optFuncExprIndex, subTree.dataset, analysisCtx);
}
}
+
// Try to match variables from optFuncExpr to datasourcescan if not already matched in assigns.
List<LogicalVariable> dsVarList = subTree.dataSourceScan.getVariables();
for (int varIndex = 0; varIndex < dsVarList.size(); varIndex++) {
@@ -311,37 +337,87 @@
}
}
}
-
/**
* Returns the field name corresponding to the assigned variable at varIndex.
- * Returns null if the expr at varIndex is not a field access function.
+ * Returns null if the expr at varIndex does not yield to a field access function after following a set of allowed functions.
*/
- protected String getFieldNameOfFieldAccess(AssignOperator assign, ARecordType recordType, int varIndex) {
- // Get expression corresponding to var at varIndex.
- AbstractLogicalExpression assignExpr = (AbstractLogicalExpression) assign.getExpressions().get(varIndex)
- .getValue();
- if (assignExpr.getExpressionTag() != LogicalExpressionTag.FUNCTION_CALL) {
+ protected String getFieldNameFromSubTree(IOptimizableFuncExpr optFuncExpr, OptimizableOperatorSubTree subTree, int opIndex, int assignVarIndex) {
+ // Get expression corresponding to opVar at varIndex.
+ AbstractLogicalExpression expr = null;
+ AbstractLogicalOperator op = subTree.assignsAndUnnests.get(opIndex);
+ if (op.getOperatorTag() == LogicalOperatorTag.ASSIGN) {
+ AssignOperator assignOp = (AssignOperator) op;
+ expr = (AbstractLogicalExpression) assignOp.getExpressions().get(assignVarIndex).getValue();
+ } else {
+ UnnestOperator unnestOp = (UnnestOperator) op;
+ expr = (AbstractLogicalExpression) unnestOp.getExpressionRef().getValue();
+ if (expr.getExpressionTag() != LogicalExpressionTag.FUNCTION_CALL) {
+ return null;
+ }
+ AbstractFunctionCallExpression childFuncExpr = (AbstractFunctionCallExpression) expr;
+ if (childFuncExpr.getFunctionIdentifier() != AsterixBuiltinFunctions.SCAN_COLLECTION) {
+ return null;
+ }
+ expr = (AbstractLogicalExpression) childFuncExpr.getArguments().get(0).getValue();
+ }
+ if (expr.getExpressionTag() != LogicalExpressionTag.FUNCTION_CALL) {
return null;
}
- // Analyze the assign op to get the field name
- // corresponding to the field being assigned at varIndex.
- AbstractFunctionCallExpression assignFuncExpr = (AbstractFunctionCallExpression) assignExpr;
- FunctionIdentifier assignFuncIdent = assignFuncExpr.getFunctionIdentifier();
- if (assignFuncIdent == AsterixBuiltinFunctions.FIELD_ACCESS_BY_NAME) {
- ILogicalExpression nameArg = assignFuncExpr.getArguments().get(1).getValue();
+ AbstractFunctionCallExpression funcExpr = (AbstractFunctionCallExpression) expr;
+ FunctionIdentifier funcIdent = funcExpr.getFunctionIdentifier();
+ if (funcIdent == AsterixBuiltinFunctions.FIELD_ACCESS_BY_NAME) {
+ ILogicalExpression nameArg = funcExpr.getArguments().get(1).getValue();
if (nameArg.getExpressionTag() != LogicalExpressionTag.CONSTANT) {
return null;
}
ConstantExpression constExpr = (ConstantExpression) nameArg;
return ((AString) ((AsterixConstantValue) constExpr.getValue()).getObject()).getStringValue();
- } else if (assignFuncIdent == AsterixBuiltinFunctions.FIELD_ACCESS_BY_INDEX) {
- ILogicalExpression idxArg = assignFuncExpr.getArguments().get(1).getValue();
+ } else if (funcIdent == AsterixBuiltinFunctions.FIELD_ACCESS_BY_INDEX) {
+ ILogicalExpression idxArg = funcExpr.getArguments().get(1).getValue();
if (idxArg.getExpressionTag() != LogicalExpressionTag.CONSTANT) {
return null;
}
ConstantExpression constExpr = (ConstantExpression) idxArg;
int fieldIndex = ((AInt32) ((AsterixConstantValue) constExpr.getValue()).getObject()).getIntegerValue();
- return recordType.getFieldNames()[fieldIndex];
+ return subTree.recordType.getFieldNames()[fieldIndex];
+ }
+ if (funcIdent != AsterixBuiltinFunctions.WORD_TOKENS
+ && funcIdent != AsterixBuiltinFunctions.GRAM_TOKENS
+ && funcIdent != AsterixBuiltinFunctions.SUBSTRING
+ && funcIdent != AsterixBuiltinFunctions.SUBSTRING_BEFORE
+ && funcIdent != AsterixBuiltinFunctions.SUBSTRING_AFTER) {
+ return null;
+ }
+ // We use a part of the field in edit distance computation
+ if (optFuncExpr.getFuncExpr().getFunctionIdentifier() == AsterixBuiltinFunctions.EDIT_DISTANCE_CHECK) {
+ optFuncExpr.setPartialField(true);
+ }
+ // We expect the function's argument to be a variable, otherwise we cannot apply an index.
+ ILogicalExpression argExpr = funcExpr.getArguments().get(0).getValue();
+ if (argExpr.getExpressionTag() != LogicalExpressionTag.VARIABLE) {
+ return null;
+ }
+ LogicalVariable curVar = ((VariableReferenceExpression) argExpr).getVariableReference();
+ // We look for the assign or unnest operator that produces curVar below the current operator
+ for (int assignOrUnnestIndex = opIndex + 1; assignOrUnnestIndex < subTree.assignsAndUnnests.size(); assignOrUnnestIndex++) {
+ AbstractLogicalOperator curOp = subTree.assignsAndUnnests.get(assignOrUnnestIndex);
+ if (curOp.getOperatorTag() == LogicalOperatorTag.ASSIGN) {
+ AssignOperator assignOp = (AssignOperator) curOp;
+ List<LogicalVariable> varList = assignOp.getVariables();
+ for (int varIndex = 0; varIndex < varList.size(); varIndex++) {
+ LogicalVariable var = varList.get(varIndex);
+ if (var.equals(curVar)) {
+ return getFieldNameFromSubTree(optFuncExpr, subTree, assignOrUnnestIndex, varIndex);
+ }
+ }
+ }
+ else {
+ UnnestOperator unnestOp = (UnnestOperator) curOp;
+ LogicalVariable var = unnestOp.getVariable();
+ if (var.equals(curVar)) {
+ getFieldNameFromSubTree(optFuncExpr, subTree, assignOrUnnestIndex, 0);
+ }
+ }
}
return null;
}
diff --git a/asterix-algebra/src/main/java/edu/uci/ics/asterix/optimizer/rules/am/BTreeAccessMethod.java b/asterix-algebra/src/main/java/edu/uci/ics/asterix/optimizer/rules/am/BTreeAccessMethod.java
index 7a15c32..701efd9 100644
--- a/asterix-algebra/src/main/java/edu/uci/ics/asterix/optimizer/rules/am/BTreeAccessMethod.java
+++ b/asterix-algebra/src/main/java/edu/uci/ics/asterix/optimizer/rules/am/BTreeAccessMethod.java
@@ -87,7 +87,7 @@
}
@Override
- public boolean analyzeFuncExprArgs(AbstractFunctionCallExpression funcExpr, List<AssignOperator> assigns,
+ public boolean analyzeFuncExprArgs(AbstractFunctionCallExpression funcExpr, List<AbstractLogicalOperator> assignsAndUnnests,
AccessMethodAnalysisContext analysisCtx) {
boolean matches = AccessMethodUtils.analyzeFuncExprArgsForOneConstAndVar(funcExpr, analysisCtx);
if (!matches) {
@@ -118,25 +118,25 @@
if (primaryIndexUnnestOp == null) {
return false;
}
- Mutable<ILogicalOperator> assignRef = (subTree.assignRefs.isEmpty()) ? null : subTree.assignRefs.get(0);
- AssignOperator assign = null;
- if (assignRef != null) {
- assign = (AssignOperator) assignRef.getValue();
+ 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 (assign != null) {
+ if (op != null) {
subTree.dataSourceScanRef.setValue(primaryIndexUnnestOp);
- select.getInputs().add(new MutableObject<ILogicalOperator>(assign));
+ select.getInputs().add(new MutableObject<ILogicalOperator>(op));
} else {
select.getInputs().add(new MutableObject<ILogicalOperator>(primaryIndexUnnestOp));
}
} else {
((AbstractLogicalOperator) primaryIndexUnnestOp).setExecutionMode(ExecutionMode.PARTITIONED);
- if (assign != null) {
+ if (op != null) {
subTree.dataSourceScanRef.setValue(primaryIndexUnnestOp);
- selectRef.setValue(assign);
+ selectRef.setValue(op);
} else {
selectRef.setValue(primaryIndexUnnestOp);
}
diff --git a/asterix-algebra/src/main/java/edu/uci/ics/asterix/optimizer/rules/am/IAccessMethod.java b/asterix-algebra/src/main/java/edu/uci/ics/asterix/optimizer/rules/am/IAccessMethod.java
index 4e2c1c8..0be4204 100644
--- a/asterix-algebra/src/main/java/edu/uci/ics/asterix/optimizer/rules/am/IAccessMethod.java
+++ b/asterix-algebra/src/main/java/edu/uci/ics/asterix/optimizer/rules/am/IAccessMethod.java
@@ -24,6 +24,7 @@
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;
import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.AssignOperator;
/**
@@ -51,7 +52,7 @@
* @return true if funcExpr is optimizable by this access method, false
* otherwise
*/
- public boolean analyzeFuncExprArgs(AbstractFunctionCallExpression funcExpr, List<AssignOperator> assigns,
+ public boolean analyzeFuncExprArgs(AbstractFunctionCallExpression funcExpr, List<AbstractLogicalOperator> assignsAndUnnests,
AccessMethodAnalysisContext analysisCtx);
/**
diff --git a/asterix-algebra/src/main/java/edu/uci/ics/asterix/optimizer/rules/am/IOptimizableFuncExpr.java b/asterix-algebra/src/main/java/edu/uci/ics/asterix/optimizer/rules/am/IOptimizableFuncExpr.java
index 5ec9702..4d43375 100644
--- a/asterix-algebra/src/main/java/edu/uci/ics/asterix/optimizer/rules/am/IOptimizableFuncExpr.java
+++ b/asterix-algebra/src/main/java/edu/uci/ics/asterix/optimizer/rules/am/IOptimizableFuncExpr.java
@@ -47,4 +47,8 @@
public int findFieldName(String fieldName);
public void substituteVar(LogicalVariable original, LogicalVariable substitution);
+
+ public void setPartialField(boolean partialField);
+
+ public boolean containsPartialField();
}
diff --git a/asterix-algebra/src/main/java/edu/uci/ics/asterix/optimizer/rules/am/IntroduceJoinAccessMethodRule.java b/asterix-algebra/src/main/java/edu/uci/ics/asterix/optimizer/rules/am/IntroduceJoinAccessMethodRule.java
index 8790c7c..1ee8107 100644
--- a/asterix-algebra/src/main/java/edu/uci/ics/asterix/optimizer/rules/am/IntroduceJoinAccessMethodRule.java
+++ b/asterix-algebra/src/main/java/edu/uci/ics/asterix/optimizer/rules/am/IntroduceJoinAccessMethodRule.java
@@ -38,8 +38,8 @@
/**
* This rule optimizes a join with secondary indexes into an indexed nested-loop join.
* Matches the following operator pattern:
- * (join) <-- (select)? <-- (assign)+ <-- (datasource scan)
- * <-- (select)? <-- (assign)+ <-- (datasource scan)
+ * (join) <-- (select)? <-- (assign | unnest)+ <-- (datasource scan)
+ * <-- (select)? <-- (assign | unnest)+ <-- (datasource scan)
* Replaces the above pattern with the following simplified plan:
* (select) <-- (assign) <-- (btree search) <-- (sort) <-- (unnest(index search)) <-- (assign) <-- (datasource scan)
* The sort is optional, and some access methods may choose not to sort.
@@ -86,10 +86,10 @@
boolean matchInLeftSubTree = false;
boolean matchInRightSubTree = false;
if (leftSubTree.hasDataSourceScan()) {
- matchInLeftSubTree = analyzeCondition(joinCond, leftSubTree.assigns, analyzedAMs);
+ matchInLeftSubTree = analyzeCondition(joinCond, leftSubTree.assignsAndUnnests, analyzedAMs);
}
if (rightSubTree.hasDataSourceScan()) {
- matchInRightSubTree = analyzeCondition(joinCond, rightSubTree.assigns, analyzedAMs);
+ matchInRightSubTree = analyzeCondition(joinCond, rightSubTree.assignsAndUnnests, analyzedAMs);
}
if (!matchInLeftSubTree && !matchInRightSubTree) {
return false;
diff --git a/asterix-algebra/src/main/java/edu/uci/ics/asterix/optimizer/rules/am/IntroduceSelectAccessMethodRule.java b/asterix-algebra/src/main/java/edu/uci/ics/asterix/optimizer/rules/am/IntroduceSelectAccessMethodRule.java
index 47efeb0..9ae8c9f 100644
--- a/asterix-algebra/src/main/java/edu/uci/ics/asterix/optimizer/rules/am/IntroduceSelectAccessMethodRule.java
+++ b/asterix-algebra/src/main/java/edu/uci/ics/asterix/optimizer/rules/am/IntroduceSelectAccessMethodRule.java
@@ -42,7 +42,7 @@
* Matches the following operator patterns:
* Standard secondary index pattern:
* There must be at least one assign, but there may be more, e.g., when matching similarity-jaccard-check().
- * (select) <-- (assign)+ <-- (datasource scan)
+ * (select) <-- (assign | unnest)+ <-- (datasource scan)
* Primary index lookup pattern:
* Since no assign is necessary to get the primary key fields (they are already stored fields in the BTree tuples).
* (select) <-- (datasource scan)
@@ -89,7 +89,7 @@
// Analyze select condition.
Map<IAccessMethod, AccessMethodAnalysisContext> analyzedAMs = new HashMap<IAccessMethod, AccessMethodAnalysisContext>();
- if (!analyzeCondition(selectCond, subTree.assigns, analyzedAMs)) {
+ if (!analyzeCondition(selectCond, subTree.assignsAndUnnests, analyzedAMs)) {
return false;
}
diff --git a/asterix-algebra/src/main/java/edu/uci/ics/asterix/optimizer/rules/am/InvertedIndexAccessMethod.java b/asterix-algebra/src/main/java/edu/uci/ics/asterix/optimizer/rules/am/InvertedIndexAccessMethod.java
index 6636d07..2ff8e50 100644
--- a/asterix-algebra/src/main/java/edu/uci/ics/asterix/optimizer/rules/am/InvertedIndexAccessMethod.java
+++ b/asterix-algebra/src/main/java/edu/uci/ics/asterix/optimizer/rules/am/InvertedIndexAccessMethod.java
@@ -48,6 +48,7 @@
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;
@@ -66,8 +67,10 @@
import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.SelectOperator;
import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.UnionAllOperator;
import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.UnnestMapOperator;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.UnnestOperator;
import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.visitors.VariableUtilities;
import edu.uci.ics.hyracks.storage.am.lsm.invertedindex.api.IInvertedIndexSearchModifierFactory;
+import edu.uci.ics.hyracks.storage.am.lsm.invertedindex.search.ConjunctiveEditDistanceSearchModifierFactory;
import edu.uci.ics.hyracks.storage.am.lsm.invertedindex.search.ConjunctiveSearchModifierFactory;
import edu.uci.ics.hyracks.storage.am.lsm.invertedindex.search.EditDistanceSearchModifierFactory;
import edu.uci.ics.hyracks.storage.am.lsm.invertedindex.search.JaccardSearchModifierFactory;
@@ -84,6 +87,7 @@
CONJUNCTIVE,
JACCARD,
EDIT_DISTANCE,
+ CONJUNCTIVE_EDIT_DISTANCE,
INVALID
}
@@ -111,15 +115,15 @@
}
@Override
- public boolean analyzeFuncExprArgs(AbstractFunctionCallExpression funcExpr, List<AssignOperator> assigns,
+ public boolean analyzeFuncExprArgs(AbstractFunctionCallExpression funcExpr, List<AbstractLogicalOperator> assignsAndUnnests,
AccessMethodAnalysisContext analysisCtx) {
if (funcExpr.getFunctionIdentifier() == AsterixBuiltinFunctions.CONTAINS) {
return AccessMethodUtils.analyzeFuncExprArgsForOneConstAndVar(funcExpr, analysisCtx);
}
- return analyzeGetItemFuncExpr(funcExpr, assigns, analysisCtx);
+ return analyzeGetItemFuncExpr(funcExpr, assignsAndUnnests, analysisCtx);
}
- public boolean analyzeGetItemFuncExpr(AbstractFunctionCallExpression funcExpr, List<AssignOperator> assigns,
+ public boolean analyzeGetItemFuncExpr(AbstractFunctionCallExpression funcExpr, List<AbstractLogicalOperator> assignsAndUnnests,
AccessMethodAnalysisContext analysisCtx) {
if (funcExpr.getFunctionIdentifier() != AsterixBuiltinFunctions.GET_ITEM) {
return false;
@@ -141,31 +145,49 @@
if (arg1.getExpressionTag() == LogicalExpressionTag.FUNCTION_CALL) {
matchedFuncExpr = (AbstractFunctionCallExpression) arg1;
}
- // The get-item arg is a variable. Search the assigns for its origination function.
- int matchedAssignIndex = -1;
+ // The get-item arg is a variable. Search the assigns and unnests for its origination function.
+ int matchedAssignOrUnnestIndex = -1;
if (arg1.getExpressionTag() == LogicalExpressionTag.VARIABLE) {
VariableReferenceExpression varRefExpr = (VariableReferenceExpression) arg1;
// Try to find variable ref expr in all assigns.
- for (int i = 0; i < assigns.size(); i++) {
- AssignOperator assign = assigns.get(i);
- List<LogicalVariable> assignVars = assign.getVariables();
- List<Mutable<ILogicalExpression>> assignExprs = assign.getExpressions();
- for (int j = 0; j < assignVars.size(); j++) {
- LogicalVariable var = assignVars.get(j);
- if (var != varRefExpr.getVariableReference()) {
- continue;
+ for (int i = 0; i < assignsAndUnnests.size(); i++) {
+ AbstractLogicalOperator op = assignsAndUnnests.get(i);
+ if (op.getOperatorTag() == LogicalOperatorTag.ASSIGN) {
+ AssignOperator assign = (AssignOperator) op;
+ List<LogicalVariable> assignVars = assign.getVariables();
+ List<Mutable<ILogicalExpression>> assignExprs = assign.getExpressions();
+ for (int j = 0; j < assignVars.size(); j++) {
+ LogicalVariable var = assignVars.get(j);
+ if (var != varRefExpr.getVariableReference()) {
+ continue;
+ }
+ // We've matched the variable in the first assign. Now analyze the originating function.
+ ILogicalExpression matchedExpr = assignExprs.get(j).getValue();
+ if (matchedExpr.getExpressionTag() != LogicalExpressionTag.FUNCTION_CALL) {
+ return false;
+ }
+ matchedFuncExpr = (AbstractFunctionCallExpression) matchedExpr;
+ break;
}
- // We've matched the variable in the first assign. Now analyze the originating function.
- ILogicalExpression matchedExpr = assignExprs.get(j).getValue();
- if (matchedExpr.getExpressionTag() != LogicalExpressionTag.FUNCTION_CALL) {
- return false;
+ }
+ else {
+ UnnestOperator unnest = (UnnestOperator) op;
+ LogicalVariable var = unnest.getVariable();
+ if (var == varRefExpr.getVariableReference()) {
+ ILogicalExpression matchedExpr = unnest.getExpressionRef().getValue();
+ if (matchedExpr.getExpressionTag() != LogicalExpressionTag.FUNCTION_CALL) {
+ return false;
+ }
+ AbstractFunctionCallExpression unnestFuncExpr = (AbstractFunctionCallExpression) matchedExpr;
+ if (unnestFuncExpr.getFunctionIdentifier() != AsterixBuiltinFunctions.SCAN_COLLECTION) {
+ return false;
+ }
+ matchedFuncExpr = (AbstractFunctionCallExpression) unnestFuncExpr.getArguments().get(0).getValue();
}
- matchedAssignIndex = i;
- matchedFuncExpr = (AbstractFunctionCallExpression) matchedExpr;
- break;
}
// We've already found a match.
if (matchedFuncExpr != null) {
+ matchedAssignOrUnnestIndex = i;
break;
}
}
@@ -174,9 +196,9 @@
if (!secondLevelFuncIdents.contains(matchedFuncExpr.getFunctionIdentifier())) {
return false;
}
- boolean selectMatchFound = analyzeSelectSimilarityCheckFuncExprArgs(matchedFuncExpr, assigns,
- matchedAssignIndex, analysisCtx);
- boolean joinMatchFound = analyzeJoinSimilarityCheckFuncExprArgs(matchedFuncExpr, assigns, matchedAssignIndex,
+ boolean selectMatchFound = analyzeSelectSimilarityCheckFuncExprArgs(matchedFuncExpr, assignsAndUnnests,
+ matchedAssignOrUnnestIndex, analysisCtx);
+ boolean joinMatchFound = analyzeJoinSimilarityCheckFuncExprArgs(matchedFuncExpr, assignsAndUnnests, matchedAssignOrUnnestIndex,
analysisCtx);
if (selectMatchFound || joinMatchFound) {
return true;
@@ -185,7 +207,7 @@
}
private boolean analyzeJoinSimilarityCheckFuncExprArgs(AbstractFunctionCallExpression funcExpr,
- List<AssignOperator> assigns, int matchedAssignIndex, AccessMethodAnalysisContext analysisCtx) {
+ List<AbstractLogicalOperator> assignsAndUnnests, int matchedAssignOrUnnestIndex, AccessMethodAnalysisContext analysisCtx) {
// There should be exactly three arguments.
// The last function argument is assumed to be the similarity threshold.
IAlgebricksConstantValue constThreshVal = null;
@@ -201,11 +223,11 @@
|| arg2.getExpressionTag() == LogicalExpressionTag.CONSTANT) {
return false;
}
- LogicalVariable fieldVar1 = getNonConstArgFieldVar(arg1, funcExpr, assigns, matchedAssignIndex);
+ LogicalVariable fieldVar1 = getNonConstArgFieldVar(arg1, funcExpr, assignsAndUnnests, matchedAssignOrUnnestIndex);
if (fieldVar1 == null) {
return false;
}
- LogicalVariable fieldVar2 = getNonConstArgFieldVar(arg2, funcExpr, assigns, matchedAssignIndex);
+ LogicalVariable fieldVar2 = getNonConstArgFieldVar(arg2, funcExpr, assignsAndUnnests, matchedAssignOrUnnestIndex);
if (fieldVar2 == null) {
return false;
}
@@ -215,7 +237,7 @@
}
private boolean analyzeSelectSimilarityCheckFuncExprArgs(AbstractFunctionCallExpression funcExpr,
- List<AssignOperator> assigns, int matchedAssignIndex, AccessMethodAnalysisContext analysisCtx) {
+ List<AbstractLogicalOperator> assignsAndUnnests, int matchedAssignOrUnnestIndex, AccessMethodAnalysisContext analysisCtx) {
// There should be exactly three arguments.
// The last function argument is assumed to be the similarity threshold.
IAlgebricksConstantValue constThreshVal = null;
@@ -242,7 +264,7 @@
}
ConstantExpression constExpr = (ConstantExpression) constArg;
IAlgebricksConstantValue constFilterVal = constExpr.getValue();
- LogicalVariable fieldVar = getNonConstArgFieldVar(nonConstArg, funcExpr, assigns, matchedAssignIndex);
+ LogicalVariable fieldVar = getNonConstArgFieldVar(nonConstArg, funcExpr, assignsAndUnnests, matchedAssignOrUnnestIndex);
if (fieldVar == null) {
return false;
}
@@ -252,7 +274,7 @@
}
private LogicalVariable getNonConstArgFieldVar(ILogicalExpression nonConstArg,
- AbstractFunctionCallExpression funcExpr, List<AssignOperator> assigns, int matchedAssignIndex) {
+ AbstractFunctionCallExpression funcExpr, List<AbstractLogicalOperator> assignsAndUnnests, int matchedAssignOrUnnestIndex) {
LogicalVariable fieldVar = null;
// Analyze nonConstArg depending on similarity function.
if (funcExpr.getFunctionIdentifier() == AsterixBuiltinFunctions.SIMILARITY_JACCARD_CHECK) {
@@ -267,49 +289,23 @@
// Find the variable that is being tokenized.
nonConstArg = nonConstFuncExpr.getArguments().get(0).getValue();
}
- if (nonConstArg.getExpressionTag() == LogicalExpressionTag.VARIABLE) {
- VariableReferenceExpression varExpr = (VariableReferenceExpression) nonConstArg;
- fieldVar = varExpr.getVariableReference();
- // Find expr corresponding to var in assigns below.
- for (int i = matchedAssignIndex + 1; i < assigns.size(); i++) {
- AssignOperator assign = assigns.get(i);
- boolean found = false;
- for (int j = 0; j < assign.getVariables().size(); j++) {
- if (fieldVar != assign.getVariables().get(j)) {
- continue;
- }
- ILogicalExpression childExpr = assign.getExpressions().get(j).getValue();
- if (childExpr.getExpressionTag() != LogicalExpressionTag.FUNCTION_CALL) {
- break;
- }
- AbstractFunctionCallExpression childFuncExpr = (AbstractFunctionCallExpression) childExpr;
- // If fieldVar references the result of a tokenization, then we should remember the variable being tokenized.
- if (childFuncExpr.getFunctionIdentifier() != AsterixBuiltinFunctions.WORD_TOKENS
- && childFuncExpr.getFunctionIdentifier() != AsterixBuiltinFunctions.GRAM_TOKENS) {
- break;
- }
- // We expect the tokenizer's argument to be a variable, otherwise we cannot apply an index.
- ILogicalExpression tokArgExpr = childFuncExpr.getArguments().get(0).getValue();
- if (tokArgExpr.getExpressionTag() != LogicalExpressionTag.VARIABLE) {
- break;
- }
- // Pass the variable being tokenized to the optimizable func expr.
- VariableReferenceExpression tokArgVarExpr = (VariableReferenceExpression) tokArgExpr;
- fieldVar = tokArgVarExpr.getVariableReference();
- found = true;
- break;
- }
- if (found) {
- break;
- }
- }
- }
}
if (funcExpr.getFunctionIdentifier() == AsterixBuiltinFunctions.EDIT_DISTANCE_CHECK) {
- if (nonConstArg.getExpressionTag() == LogicalExpressionTag.VARIABLE) {
- fieldVar = ((VariableReferenceExpression) nonConstArg).getVariableReference();
+ if(nonConstArg.getExpressionTag() == LogicalExpressionTag.FUNCTION_CALL) {
+ AbstractFunctionCallExpression nonConstFuncExpr = (AbstractFunctionCallExpression) nonConstArg;
+ if (nonConstFuncExpr.getFunctionIdentifier() != AsterixBuiltinFunctions.WORD_TOKENS
+ && nonConstFuncExpr.getFunctionIdentifier() != AsterixBuiltinFunctions.SUBSTRING
+ && nonConstFuncExpr.getFunctionIdentifier() != AsterixBuiltinFunctions.SUBSTRING_BEFORE
+ && nonConstFuncExpr.getFunctionIdentifier() != AsterixBuiltinFunctions.SUBSTRING_AFTER) {
+ return null;
+ }
+ // Find the variable whose substring is used in the similarity function
+ nonConstArg = nonConstFuncExpr.getArguments().get(0).getValue();
}
}
+ if (nonConstArg.getExpressionTag() == LogicalExpressionTag.VARIABLE) {
+ fieldVar = ((VariableReferenceExpression) nonConstArg).getVariableReference();
+ }
return fieldVar;
}
@@ -748,7 +744,11 @@
jobGenParams.setSimilarityThreshold(optFuncExpr.getConstantVal(optFuncExpr.getNumConstantVals() - 1));
}
if (optFuncExpr.getFuncExpr().getFunctionIdentifier() == AsterixBuiltinFunctions.EDIT_DISTANCE_CHECK) {
- jobGenParams.setSearchModifierType(SearchModifierType.EDIT_DISTANCE);
+ if (optFuncExpr.containsPartialField()) {
+ jobGenParams.setSearchModifierType(SearchModifierType.CONJUNCTIVE_EDIT_DISTANCE);
+ } else {
+ jobGenParams.setSearchModifierType(SearchModifierType.EDIT_DISTANCE);
+ }
// Add the similarity threshold which, by convention, is the last constant value.
jobGenParams.setSimilarityThreshold(optFuncExpr.getConstantVal(optFuncExpr.getNumConstantVals() - 1));
}
@@ -788,9 +788,14 @@
if (listOrStrObj.getType().getTypeTag() == ATypeTag.STRING
&& (index.getIndexType() == IndexType.SINGLE_PARTITION_NGRAM_INVIX || index.getIndexType() == IndexType.LENGTH_PARTITIONED_NGRAM_INVIX)) {
AString astr = (AString) listOrStrObj;
- // Compute merge threshold.
- mergeThreshold = (astr.getStringValue().length() + index.getGramLength() - 1)
+ // Compute merge threshold depending on the query grams contain pre- and postfixing
+ if (optFuncExpr.containsPartialField()) {
+ mergeThreshold = (astr.getStringValue().length() - index.getGramLength() + 1)
+ - edThresh.getIntegerValue() * index.getGramLength();
+ } else {
+ mergeThreshold = (astr.getStringValue().length() + index.getGramLength() - 1)
- edThresh.getIntegerValue() * index.getGramLength();
+ }
}
// We can only optimize edit distance on lists using a word index.
if ((listOrStrObj.getType().getTypeTag() == ATypeTag.ORDEREDLIST || listOrStrObj.getType().getTypeTag() == ATypeTag.UNORDEREDLIST)
@@ -861,7 +866,7 @@
case SINGLE_PARTITION_NGRAM_INVIX:
case LENGTH_PARTITIONED_NGRAM_INVIX: {
// Make sure not to use pre- and postfixing for conjunctive searches.
- boolean prePost = (searchModifierType == SearchModifierType.CONJUNCTIVE) ? false : true;
+ boolean prePost = (searchModifierType == SearchModifierType.CONJUNCTIVE || searchModifierType == SearchModifierType.CONJUNCTIVE_EDIT_DISTANCE) ? false : true;
return AqlBinaryTokenizerFactoryProvider.INSTANCE.getNGramTokenizerFactory(searchKeyType,
index.getGramLength(), prePost, false);
}
@@ -900,6 +905,10 @@
}
}
}
+ case CONJUNCTIVE_EDIT_DISTANCE: {
+ int edThresh = ((AInt32) simThresh).getIntegerValue();
+ return new ConjunctiveEditDistanceSearchModifierFactory(index.getGramLength(), edThresh);
+ }
default: {
throw new AlgebricksException("Unknown search modifier type '" + searchModifierType + "'.");
}
diff --git a/asterix-algebra/src/main/java/edu/uci/ics/asterix/optimizer/rules/am/OptimizableFuncExpr.java b/asterix-algebra/src/main/java/edu/uci/ics/asterix/optimizer/rules/am/OptimizableFuncExpr.java
index f1b93fe..78acc26 100644
--- a/asterix-algebra/src/main/java/edu/uci/ics/asterix/optimizer/rules/am/OptimizableFuncExpr.java
+++ b/asterix-algebra/src/main/java/edu/uci/ics/asterix/optimizer/rules/am/OptimizableFuncExpr.java
@@ -28,6 +28,7 @@
protected final String[] fieldNames;
protected final OptimizableOperatorSubTree[] subTrees;
protected final IAlgebricksConstantValue[] constantVals;
+ protected boolean partialField;
public OptimizableFuncExpr(AbstractFunctionCallExpression funcExpr, LogicalVariable[] logicalVars,
IAlgebricksConstantValue[] constantVals) {
@@ -35,6 +36,7 @@
this.logicalVars = logicalVars;
this.constantVals = constantVals;
this.fieldNames = new String[logicalVars.length];
+ this.partialField = false;
this.subTrees = new OptimizableOperatorSubTree[logicalVars.length];
}
@@ -43,6 +45,7 @@
IAlgebricksConstantValue constantVal) {
this.funcExpr = funcExpr;
this.logicalVars = new LogicalVariable[] { logicalVar };
+ this.partialField = false;
this.constantVals = new IAlgebricksConstantValue[] { constantVal };
this.fieldNames = new String[logicalVars.length];
this.subTrees = new OptimizableOperatorSubTree[logicalVars.length];
@@ -124,4 +127,14 @@
}
}
}
+
+ @Override
+ public void setPartialField(boolean partialField) {
+ this.partialField = partialField;
+ }
+
+ @Override
+ public boolean containsPartialField() {
+ return partialField;
+ }
}
diff --git a/asterix-algebra/src/main/java/edu/uci/ics/asterix/optimizer/rules/am/OptimizableOperatorSubTree.java b/asterix-algebra/src/main/java/edu/uci/ics/asterix/optimizer/rules/am/OptimizableOperatorSubTree.java
index 334d411..33ca4d1 100644
--- a/asterix-algebra/src/main/java/edu/uci/ics/asterix/optimizer/rules/am/OptimizableOperatorSubTree.java
+++ b/asterix-algebra/src/main/java/edu/uci/ics/asterix/optimizer/rules/am/OptimizableOperatorSubTree.java
@@ -33,20 +33,19 @@
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.operators.logical.AbstractLogicalOperator;
-import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.AssignOperator;
import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.DataSourceScanOperator;
/**
* Operator subtree that matches the following patterns, and provides convenient access to its nodes:
- * (select)? <-- (assign)+ <-- (datasource scan)
+ * (select)? <-- (assign | unnest)+ <-- (datasource scan)
* and
* (select)? <-- (datasource scan)
*/
public class OptimizableOperatorSubTree {
public ILogicalOperator root = null;
public Mutable<ILogicalOperator> rootRef = null;
- public final List<Mutable<ILogicalOperator>> assignRefs = new ArrayList<Mutable<ILogicalOperator>>();
- public final List<AssignOperator> assigns = new ArrayList<AssignOperator>();
+ public final List<Mutable<ILogicalOperator>> assignsAndUnnestsRefs = new ArrayList<Mutable<ILogicalOperator>>();
+ public final List<AbstractLogicalOperator> assignsAndUnnests = new ArrayList<AbstractLogicalOperator>();
public Mutable<ILogicalOperator> dataSourceScanRef = null;
public DataSourceScanOperator dataSourceScan = null;
// Dataset and type metadata. Set in setDatasetAndTypeMetadata().
@@ -65,7 +64,7 @@
subTreeOp = (AbstractLogicalOperator) subTreeOpRef.getValue();
}
// Check primary-index pattern.
- if (subTreeOp.getOperatorTag() != LogicalOperatorTag.ASSIGN) {
+ if (subTreeOp.getOperatorTag() != LogicalOperatorTag.ASSIGN && subTreeOp.getOperatorTag() != LogicalOperatorTag.UNNEST) {
// Pattern may still match if we are looking for primary index matches as well.
if (subTreeOp.getOperatorTag() == LogicalOperatorTag.DATASOURCESCAN) {
dataSourceScanRef = subTreeOpRef;
@@ -74,24 +73,21 @@
}
return false;
}
- // Match (assign)+.
+ // Match (assign | unnest)+.
do {
- assignRefs.add(subTreeOpRef);
- assigns.add((AssignOperator) subTreeOp);
+ assignsAndUnnestsRefs.add(subTreeOpRef);
+ assignsAndUnnests.add(subTreeOp);
+
subTreeOpRef = subTreeOp.getInputs().get(0);
subTreeOp = (AbstractLogicalOperator) subTreeOpRef.getValue();
- } while (subTreeOp.getOperatorTag() == LogicalOperatorTag.ASSIGN);
- // Set to last valid assigns.
- subTreeOpRef = assignRefs.get(assignRefs.size() - 1);
- subTreeOp = assigns.get(assigns.size() - 1);
+ } while (subTreeOp.getOperatorTag() == LogicalOperatorTag.ASSIGN || subTreeOp.getOperatorTag() == LogicalOperatorTag.UNNEST);
+
// Match datasource scan.
- Mutable<ILogicalOperator> opRef3 = subTreeOp.getInputs().get(0);
- AbstractLogicalOperator op3 = (AbstractLogicalOperator) opRef3.getValue();
- if (op3.getOperatorTag() != LogicalOperatorTag.DATASOURCESCAN) {
+ if (subTreeOp.getOperatorTag() != LogicalOperatorTag.DATASOURCESCAN) {
return false;
}
- dataSourceScanRef = opRef3;
- dataSourceScan = (DataSourceScanOperator) op3;
+ dataSourceScanRef = subTreeOpRef;
+ dataSourceScan = (DataSourceScanOperator) subTreeOp;
return true;
}
@@ -133,8 +129,8 @@
public void reset() {
root = null;
rootRef = null;
- assignRefs.clear();
- assigns.clear();
+ assignsAndUnnestsRefs.clear();
+ assignsAndUnnests.clear();
dataSourceScanRef = null;
dataSourceScan = null;
dataset = null;
diff --git a/asterix-algebra/src/main/java/edu/uci/ics/asterix/optimizer/rules/am/RTreeAccessMethod.java b/asterix-algebra/src/main/java/edu/uci/ics/asterix/optimizer/rules/am/RTreeAccessMethod.java
index c714aa9..fb5ad49 100644
--- a/asterix-algebra/src/main/java/edu/uci/ics/asterix/optimizer/rules/am/RTreeAccessMethod.java
+++ b/asterix-algebra/src/main/java/edu/uci/ics/asterix/optimizer/rules/am/RTreeAccessMethod.java
@@ -43,6 +43,7 @@
import edu.uci.ics.hyracks.algebricks.core.algebra.functions.FunctionIdentifier;
import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.AbstractBinaryJoinOperator;
import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.AbstractLogicalOperator.ExecutionMode;
+import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.AbstractLogicalOperator;
import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.AssignOperator;
import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.DataSourceScanOperator;
import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.SelectOperator;
@@ -66,7 +67,7 @@
}
@Override
- public boolean analyzeFuncExprArgs(AbstractFunctionCallExpression funcExpr, List<AssignOperator> assigns,
+ public boolean analyzeFuncExprArgs(AbstractFunctionCallExpression funcExpr, List<AbstractLogicalOperator> assignsAndUnnests,
AccessMethodAnalysisContext analysisCtx) {
boolean matches = AccessMethodUtils.analyzeFuncExprArgsForOneConstAndVar(funcExpr, analysisCtx);
if (!matches) {
diff --git a/asterix-app/src/test/resources/optimizerts/queries/inverted-index-complex/ngram-edit-distance-check-substring.aql b/asterix-app/src/test/resources/optimizerts/queries/inverted-index-complex/ngram-edit-distance-check-substring.aql
new file mode 100644
index 0000000..a506053
--- /dev/null
+++ b/asterix-app/src/test/resources/optimizerts/queries/inverted-index-complex/ngram-edit-distance-check-substring.aql
@@ -0,0 +1,31 @@
+/*
+ * Description : Tests whether an ngram_index index is applied to optimize a selection query using the similarity-edit-distance-check function on the substring of the field.
+ * Tests that the optimizer rule correctly drills through the substring function.
+ * The index should be applied.
+ * Success : Yes
+ */
+
+drop dataverse test if exists;
+create dataverse test;
+use dataverse test;
+
+create type DBLPType as closed {
+ id: int32,
+ dblpid: string,
+ title: string,
+ authors: string,
+ misc: string
+}
+
+create dataset DBLP(DBLPType) primary key id;
+
+create index ngram_index on DBLP(title) type ngram(3);
+
+write output to nc1:"rttest/inverted-index-complex_ngram-edit-distance-check-substring.adm";
+
+for $paper in dataset('DBLP')
+where edit-distance-check(substring($paper.title, 0, 8), "datbase", 1)[0]
+return {
+ "id" : $paper.id,
+ "title" : $paper.title
+}
\ No newline at end of file
diff --git a/asterix-app/src/test/resources/optimizerts/queries/inverted-index-complex/ngram-edit-distance-check-word-tokens.aql b/asterix-app/src/test/resources/optimizerts/queries/inverted-index-complex/ngram-edit-distance-check-word-tokens.aql
new file mode 100644
index 0000000..8f1c1fc
--- /dev/null
+++ b/asterix-app/src/test/resources/optimizerts/queries/inverted-index-complex/ngram-edit-distance-check-word-tokens.aql
@@ -0,0 +1,31 @@
+/*
+ * Description : Tests whether an ngram_index index is applied to optimize a selection query using the similarity-edit-distance-check function on individual word tokens.
+ * Tests that the optimizer rule correctly drills through the word-tokens function and existential query.
+ * The index should be applied.
+ * Success : Yes
+ */
+
+drop dataverse test if exists;
+create dataverse test;
+use dataverse test;
+
+create type DBLPType as closed {
+ id: int32,
+ dblpid: string,
+ title: string,
+ authors: string,
+ misc: string
+}
+
+create dataset DBLP(DBLPType) primary key id;
+
+create index ngram_index on DBLP(title) type ngram(3);
+
+write output to nc1:"rttest/inverted-index-complex_ngram-edit-distance-check-word-tokens.adm";
+
+for $paper in dataset('DBLP')
+where (some $word in word-tokens($paper.title) satisfies edit-distance-check($word, "datbase", 1)[0] )
+return {
+ "id" : $paper.id,
+ "title" : $paper.title
+}
\ No newline at end of file
diff --git a/asterix-app/src/test/resources/optimizerts/results/inverted-index-complex/ngram-edit-distance-check-substring.plan b/asterix-app/src/test/resources/optimizerts/results/inverted-index-complex/ngram-edit-distance-check-substring.plan
new file mode 100644
index 0000000..259a003
--- /dev/null
+++ b/asterix-app/src/test/resources/optimizerts/results/inverted-index-complex/ngram-edit-distance-check-substring.plan
@@ -0,0 +1,19 @@
+-- DISTRIBUTE_RESULT |PARTITIONED|
+ -- ONE_TO_ONE_EXCHANGE |PARTITIONED|
+ -- STREAM_PROJECT |PARTITIONED|
+ -- ASSIGN |PARTITIONED|
+ -- STREAM_SELECT |PARTITIONED|
+ -- STREAM_PROJECT |PARTITIONED|
+ -- ASSIGN |PARTITIONED|
+ -- STREAM_PROJECT |PARTITIONED|
+ -- ONE_TO_ONE_EXCHANGE |PARTITIONED|
+ -- BTREE_SEARCH |PARTITIONED|
+ -- ONE_TO_ONE_EXCHANGE |PARTITIONED|
+ -- STABLE_SORT [$$13(ASC)] |PARTITIONED|
+ -- ONE_TO_ONE_EXCHANGE |PARTITIONED|
+ -- STREAM_PROJECT |PARTITIONED|
+ -- ONE_TO_ONE_EXCHANGE |PARTITIONED|
+ -- LENGTH_PARTITIONED_INVERTED_INDEX_SEARCH |PARTITIONED|
+ -- ONE_TO_ONE_EXCHANGE |PARTITIONED|
+ -- ASSIGN |PARTITIONED|
+ -- EMPTY_TUPLE_SOURCE |PARTITIONED|
\ No newline at end of file
diff --git a/asterix-app/src/test/resources/optimizerts/results/inverted-index-complex/ngram-edit-distance-check-word-tokens.plan b/asterix-app/src/test/resources/optimizerts/results/inverted-index-complex/ngram-edit-distance-check-word-tokens.plan
new file mode 100644
index 0000000..e62a269
--- /dev/null
+++ b/asterix-app/src/test/resources/optimizerts/results/inverted-index-complex/ngram-edit-distance-check-word-tokens.plan
@@ -0,0 +1,24 @@
+-- DISTRIBUTE_RESULT |PARTITIONED|
+ -- ONE_TO_ONE_EXCHANGE |PARTITIONED|
+ -- STREAM_PROJECT |PARTITIONED|
+ -- ASSIGN |PARTITIONED|
+ -- ONE_TO_ONE_EXCHANGE |PARTITIONED|
+ -- PRE_SORTED_DISTINCT_BY |PARTITIONED|
+ -- ONE_TO_ONE_EXCHANGE |PARTITIONED|
+ -- STREAM_PROJECT |PARTITIONED|
+ -- STREAM_SELECT |PARTITIONED|
+ -- UNNEST |PARTITIONED|
+ -- STREAM_PROJECT |PARTITIONED|
+ -- ASSIGN |PARTITIONED|
+ -- STREAM_PROJECT |PARTITIONED|
+ -- ONE_TO_ONE_EXCHANGE |PARTITIONED|
+ -- BTREE_SEARCH |PARTITIONED|
+ -- ONE_TO_ONE_EXCHANGE |PARTITIONED|
+ -- STABLE_SORT [$$16(ASC)] |PARTITIONED|
+ -- ONE_TO_ONE_EXCHANGE |PARTITIONED|
+ -- STREAM_PROJECT |PARTITIONED|
+ -- ONE_TO_ONE_EXCHANGE |PARTITIONED|
+ -- LENGTH_PARTITIONED_INVERTED_INDEX_SEARCH |PARTITIONED|
+ -- ONE_TO_ONE_EXCHANGE |PARTITIONED|
+ -- ASSIGN |PARTITIONED|
+ -- EMPTY_TUPLE_SOURCE |PARTITIONED|
\ No newline at end of file
diff --git a/asterix-app/src/test/resources/optimizerts/results/q1.plan b/asterix-app/src/test/resources/optimizerts/results/q1.plan
index aa5daa2..3843154 100644
--- a/asterix-app/src/test/resources/optimizerts/results/q1.plan
+++ b/asterix-app/src/test/resources/optimizerts/results/q1.plan
@@ -2,19 +2,16 @@
-- ONE_TO_ONE_EXCHANGE |PARTITIONED|
-- STREAM_PROJECT |PARTITIONED|
-- ASSIGN |PARTITIONED|
- -- STREAM_PROJECT |PARTITIONED|
- -- STREAM_SELECT |PARTITIONED|
- -- STREAM_PROJECT |PARTITIONED|
- -- SUBPLAN |PARTITIONED|
- {
- -- AGGREGATE |LOCAL|
- -- STREAM_SELECT |LOCAL|
- -- UNNEST |LOCAL|
- -- NESTED_TUPLE_SOURCE |LOCAL|
- }
- -- STREAM_PROJECT |PARTITIONED|
- -- ASSIGN |PARTITIONED|
- -- ONE_TO_ONE_EXCHANGE |PARTITIONED|
- -- DATASOURCE_SCAN |PARTITIONED|
- -- ONE_TO_ONE_EXCHANGE |PARTITIONED|
- -- EMPTY_TUPLE_SOURCE |PARTITIONED|
+ -- ONE_TO_ONE_EXCHANGE |PARTITIONED|
+ -- PRE_SORTED_DISTINCT_BY |PARTITIONED|
+ -- ONE_TO_ONE_EXCHANGE |PARTITIONED|
+ -- STREAM_PROJECT |PARTITIONED|
+ -- STREAM_SELECT |PARTITIONED|
+ -- STREAM_PROJECT |PARTITIONED|
+ -- UNNEST |PARTITIONED|
+ -- STREAM_PROJECT |PARTITIONED|
+ -- ASSIGN |PARTITIONED|
+ -- ONE_TO_ONE_EXCHANGE |PARTITIONED|
+ -- DATASOURCE_SCAN |PARTITIONED|
+ -- ONE_TO_ONE_EXCHANGE |PARTITIONED|
+ -- EMPTY_TUPLE_SOURCE |PARTITIONED|
diff --git a/asterix-app/src/test/resources/runtimets/queries/index-selection/inverted-index-ngram-edit-distance-word-tokens/inverted-index-ngram-edit-distance-word-tokens.1.ddl.aql b/asterix-app/src/test/resources/runtimets/queries/index-selection/inverted-index-ngram-edit-distance-word-tokens/inverted-index-ngram-edit-distance-word-tokens.1.ddl.aql
new file mode 100644
index 0000000..49c6b3b
--- /dev/null
+++ b/asterix-app/src/test/resources/runtimets/queries/index-selection/inverted-index-ngram-edit-distance-word-tokens/inverted-index-ngram-edit-distance-word-tokens.1.ddl.aql
@@ -0,0 +1,17 @@
+drop dataverse test if exists;
+create dataverse test;
+use dataverse test;
+
+create type DBLPType as closed {
+ id: int32,
+ dblpid: string,
+ title: string,
+ authors: string,
+ misc: string
+}
+
+create nodegroup group1 if not exists on nc1, nc2;
+
+create dataset DBLP(DBLPType)
+ primary key id on group1;
+
diff --git a/asterix-app/src/test/resources/runtimets/queries/index-selection/inverted-index-ngram-edit-distance-word-tokens/inverted-index-ngram-edit-distance-word-tokens.2.update.aql b/asterix-app/src/test/resources/runtimets/queries/index-selection/inverted-index-ngram-edit-distance-word-tokens/inverted-index-ngram-edit-distance-word-tokens.2.update.aql
new file mode 100644
index 0000000..29632d3
--- /dev/null
+++ b/asterix-app/src/test/resources/runtimets/queries/index-selection/inverted-index-ngram-edit-distance-word-tokens/inverted-index-ngram-edit-distance-word-tokens.2.update.aql
@@ -0,0 +1,6 @@
+use dataverse test;
+
+load dataset DBLP
+using "edu.uci.ics.asterix.external.dataset.adapter.NCFileSystemAdapter"
+(("path"="nc1://data/dblp-small/dblp-small-id.txt"),("format"="delimited-text"),("delimiter"=":")) pre-sorted;
+
diff --git a/asterix-app/src/test/resources/runtimets/queries/index-selection/inverted-index-ngram-edit-distance-word-tokens/inverted-index-ngram-edit-distance-word-tokens.3.ddl.aql b/asterix-app/src/test/resources/runtimets/queries/index-selection/inverted-index-ngram-edit-distance-word-tokens/inverted-index-ngram-edit-distance-word-tokens.3.ddl.aql
new file mode 100644
index 0000000..4209874
--- /dev/null
+++ b/asterix-app/src/test/resources/runtimets/queries/index-selection/inverted-index-ngram-edit-distance-word-tokens/inverted-index-ngram-edit-distance-word-tokens.3.ddl.aql
@@ -0,0 +1,3 @@
+use dataverse test;
+
+create index ngram_index on DBLP(title) type ngram(3);
diff --git a/asterix-app/src/test/resources/runtimets/queries/index-selection/inverted-index-ngram-edit-distance-word-tokens/inverted-index-ngram-edit-distance-word-tokens.4.query.aql b/asterix-app/src/test/resources/runtimets/queries/index-selection/inverted-index-ngram-edit-distance-word-tokens/inverted-index-ngram-edit-distance-word-tokens.4.query.aql
new file mode 100644
index 0000000..4584c3e
--- /dev/null
+++ b/asterix-app/src/test/resources/runtimets/queries/index-selection/inverted-index-ngram-edit-distance-word-tokens/inverted-index-ngram-edit-distance-word-tokens.4.query.aql
@@ -0,0 +1,9 @@
+use dataverse test;
+
+for $paper in dataset('DBLP')
+where (some $word in word-tokens($paper.title) satisfies edit-distance-check($word, "Multmedia", 1)[0] )
+order by $paper.id
+return {
+ "id" : $paper.id,
+ "title" : $paper.title
+}
\ No newline at end of file
diff --git a/asterix-app/src/test/resources/runtimets/results/index-selection/inverted-index-ngram-edit-distance-word-tokens/inverted-index-ngram-edit-distance-word-tokens.1.adm b/asterix-app/src/test/resources/runtimets/results/index-selection/inverted-index-ngram-edit-distance-word-tokens/inverted-index-ngram-edit-distance-word-tokens.1.adm
new file mode 100644
index 0000000..12593bf
--- /dev/null
+++ b/asterix-app/src/test/resources/runtimets/results/index-selection/inverted-index-ngram-edit-distance-word-tokens/inverted-index-ngram-edit-distance-word-tokens.1.adm
@@ -0,0 +1,3 @@
+{ "id": 4, "title": "Multimedia Information Systems Issues and Approaches." }
+{ "id": 89, "title": "VORTEX Video Retrieval and Tracking from Compressed Multimedia Databases." }
+{ "id": 90, "title": "VORTEX Video Retrieval and Tracking from Compressed Multimedia Databases ¾ Visual Search Engine." }
\ No newline at end of file
diff --git a/asterix-app/src/test/resources/runtimets/testsuite.xml b/asterix-app/src/test/resources/runtimets/testsuite.xml
index d1297a4..39f01c8 100644
--- a/asterix-app/src/test/resources/runtimets/testsuite.xml
+++ b/asterix-app/src/test/resources/runtimets/testsuite.xml
@@ -2330,6 +2330,11 @@
</compilation-unit>
</test-case>
<test-case FilePath="index-selection">
+ <compilation-unit name="inverted-index-ngram-edit-distance-word-tokens">
+ <output-dir compare="Text">inverted-index-ngram-edit-distance-word-tokens</output-dir>
+ </compilation-unit>
+ </test-case>
+ <test-case FilePath="index-selection">
<compilation-unit name="inverted-index-ngram-jaccard">
<output-dir compare="Text">inverted-index-ngram-jaccard</output-dir>
</compilation-unit>