Implemented indexed-nested loops join using BTrees. Added basic tests.
git-svn-id: https://asterixdb.googlecode.com/svn/branches/asterix_stabilization@836 eaa15691-b419-025a-1212-ee371bd00084
diff --git a/asterix-algebra/src/main/java/edu/uci/ics/asterix/optimizer/rules/am/AccessMethodUtils.java b/asterix-algebra/src/main/java/edu/uci/ics/asterix/optimizer/rules/am/AccessMethodUtils.java
index cd3712d..26a8b83 100644
--- a/asterix-algebra/src/main/java/edu/uci/ics/asterix/optimizer/rules/am/AccessMethodUtils.java
+++ b/asterix-algebra/src/main/java/edu/uci/ics/asterix/optimizer/rules/am/AccessMethodUtils.java
@@ -109,6 +109,24 @@
analysisCtx.matchedFuncExprs.add(new OptimizableFuncExpr(funcExpr, fieldVar, constFilterVal));
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;
+ }
+ analysisCtx.matchedFuncExprs.add(new OptimizableFuncExpr(funcExpr,
+ new LogicalVariable[] { fieldVar1, fieldVar2 }, null));
+ return true;
+ }
public static int getNumSecondaryKeys(Index index, ARecordType recordType) throws AlgebricksException {
switch (index.getIndexType()) {
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 b6103b3..6d5c4fc 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
@@ -23,12 +23,14 @@
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.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.AbstractLogicalOperator;
import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.AbstractLogicalOperator.ExecutionMode;
import edu.uci.ics.hyracks.algebricks.core.algebra.operators.logical.AssignOperator;
@@ -70,7 +72,11 @@
@Override
public boolean analyzeFuncExprArgs(AbstractFunctionCallExpression funcExpr, List<AssignOperator> assigns,
AccessMethodAnalysisContext analysisCtx) {
- return AccessMethodUtils.analyzeFuncExprArgsForOneConstAndVar(funcExpr, analysisCtx);
+ boolean matches = AccessMethodUtils.analyzeFuncExprArgsForOneConstAndVar(funcExpr, analysisCtx);
+ if (!matches) {
+ matches = AccessMethodUtils.analyzeFuncExprArgsForTwoVars(funcExpr, analysisCtx);
+ }
+ return matches;
}
@Override
@@ -84,24 +90,110 @@
return false;
}
+ private ILogicalExpression createSearchKeyExpr(IOptimizableFuncExpr optFuncExpr,
+ OptimizableOperatorSubTree indexSubTree, OptimizableOperatorSubTree probeSubTree) {
+ if (probeSubTree == null) {
+ // We are optimizing a selection query. Search key is a constant.
+ return new ConstantExpression(optFuncExpr.getConstantVal(0));
+ } else {
+ // We are optimizing a join query. Determine which variable feeds the secondary index.
+ if (optFuncExpr.getOperatorSubTree(0) == probeSubTree) {
+ return new VariableReferenceExpression(optFuncExpr.getLogicalVar(0));
+ } else {
+ return new VariableReferenceExpression(optFuncExpr.getLogicalVar(1));
+ }
+ }
+ }
+
@Override
public boolean applySelectPlanTransformation(Mutable<ILogicalOperator> selectRef,
OptimizableOperatorSubTree subTree, Index chosenIndex, AccessMethodAnalysisContext analysisCtx,
IOptimizationContext context) throws AlgebricksException {
- Dataset dataset = subTree.dataset;
- ARecordType recordType = subTree.recordType;
SelectOperator select = (SelectOperator) selectRef.getValue();
- DataSourceScanOperator dataSourceScan = subTree.dataSourceScan;
+ Mutable<ILogicalExpression> conditionRef = select.getCondition();
+ ILogicalOperator primaryIndexUnnestOp = createSecondaryToPrimaryPlan(selectRef, conditionRef, subTree, null,
+ chosenIndex, analysisCtx, false, false, context);
+ 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();
}
+ // Generate new select using the new condition.
+ if (conditionRef.getValue() != null) {
+ select.getInputs().clear();
+ if (assign != null) {
+ subTree.dataSourceScanRef.setValue(primaryIndexUnnestOp);
+ select.getInputs().add(new MutableObject<ILogicalOperator>(assign));
+ } else {
+ select.getInputs().add(new MutableObject<ILogicalOperator>(primaryIndexUnnestOp));
+ }
+ } else {
+ ((AbstractLogicalOperator) primaryIndexUnnestOp).setExecutionMode(ExecutionMode.PARTITIONED);
+ if (assign != null) {
+ subTree.dataSourceScanRef.setValue(primaryIndexUnnestOp);
+ selectRef.setValue(assign);
+ } else {
+ selectRef.setValue(primaryIndexUnnestOp);
+ }
+ }
+ return true;
+ }
+
+ @Override
+ public boolean applyJoinPlanTransformation(Mutable<ILogicalOperator> joinRef,
+ OptimizableOperatorSubTree leftSubTree, OptimizableOperatorSubTree rightSubTree, Index chosenIndex,
+ AccessMethodAnalysisContext analysisCtx, IOptimizationContext context) throws AlgebricksException {
+
+ AbstractBinaryJoinOperator joinOp = (AbstractBinaryJoinOperator) joinRef.getValue();
+ Mutable<ILogicalExpression> conditionRef = joinOp.getCondition();
+
+ // Skip this rule if there is no index NL hint.
+ AbstractFunctionCallExpression conditionFunc = (AbstractFunctionCallExpression) conditionRef.getValue();
+ if (!conditionFunc.getAnnotations().containsKey(IndexedNLJoinExpressionAnnotation.INSTANCE)) {
+ return false;
+ }
+
+ // 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 (leftSubTree.dataset != null && dataset.getDatasetName().equals(leftSubTree.dataset.getDatasetName())) {
+ indexSubTree = leftSubTree;
+ probeSubTree = rightSubTree;
+ } else if (rightSubTree.dataset != null
+ && dataset.getDatasetName().equals(rightSubTree.dataset.getDatasetName())) {
+ indexSubTree = rightSubTree;
+ probeSubTree = leftSubTree;
+ }
+
+ ILogicalOperator primaryIndexUnnestOp = createSecondaryToPrimaryPlan(joinRef, conditionRef, indexSubTree, probeSubTree,
+ chosenIndex, analysisCtx, true, true, context);
+ if (primaryIndexUnnestOp == null) {
+ return false;
+ }
+
+ // TODO: If there are conditions left, add a new select operator on top!
+ joinRef.setValue(primaryIndexUnnestOp);
+ return true;
+ }
+
+ private ILogicalOperator createSecondaryToPrimaryPlan(Mutable<ILogicalOperator> topOpRef, Mutable<ILogicalExpression> conditionRef,
+ OptimizableOperatorSubTree indexSubTree,
+ OptimizableOperatorSubTree probeSubTree, Index chosenIndex, AccessMethodAnalysisContext analysisCtx,
+ boolean retainInput, boolean requiresBroadcast, IOptimizationContext context) throws AlgebricksException {
+ Dataset dataset = indexSubTree.dataset;
+ ARecordType recordType = indexSubTree.recordType;
+ DataSourceScanOperator dataSourceScan = indexSubTree.dataSourceScan;
int numSecondaryKeys = chosenIndex.getKeyFieldNames().size();
// Info on high and low keys for the BTree search predicate.
- IAlgebricksConstantValue[] lowKeyConstants = new IAlgebricksConstantValue[numSecondaryKeys];
- IAlgebricksConstantValue[] highKeyConstants = new IAlgebricksConstantValue[numSecondaryKeys];
+ 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];
@@ -128,13 +220,14 @@
if (keyPos < 0) {
throw new InternalError();
}
+ ILogicalExpression searchKeyExpr = createSearchKeyExpr(optFuncExpr, indexSubTree, probeSubTree);
LimitType limit = getLimitType(optFuncExpr);
switch (limit) {
case EQUAL: {
if (lowKeyLimits[keyPos] == null && highKeyLimits[keyPos] == null) {
lowKeyLimits[keyPos] = highKeyLimits[keyPos] = limit;
lowKeyInclusive[keyPos] = highKeyInclusive[keyPos] = true;
- lowKeyConstants[keyPos] = highKeyConstants[keyPos] = optFuncExpr.getConstantVal(0);
+ lowKeyExprs[keyPos] = highKeyExprs[keyPos] = searchKeyExpr;
setLowKeys.set(keyPos);
setHighKeys.set(keyPos);
} else {
@@ -144,14 +237,14 @@
// If high and low keys are set, we exit for now.
if (setLowKeys.cardinality() == numSecondaryKeys
&& setHighKeys.cardinality() == numSecondaryKeys) {
- doneWithExprs = true;
+ doneWithExprs = true;
}
break;
}
case HIGH_EXCLUSIVE: {
if (highKeyLimits[keyPos] == null || (highKeyLimits[keyPos] != null && highKeyInclusive[keyPos])) {
highKeyLimits[keyPos] = limit;
- highKeyConstants[keyPos] = optFuncExpr.getConstantVal(0);
+ highKeyExprs[keyPos] = searchKeyExpr;
highKeyInclusive[keyPos] = false;
} else {
couldntFigureOut = true;
@@ -162,7 +255,7 @@
case HIGH_INCLUSIVE: {
if (highKeyLimits[keyPos] == null) {
highKeyLimits[keyPos] = limit;
- highKeyConstants[keyPos] = optFuncExpr.getConstantVal(0);
+ highKeyExprs[keyPos] = searchKeyExpr;
highKeyInclusive[keyPos] = true;
} else {
couldntFigureOut = true;
@@ -173,7 +266,7 @@
case LOW_EXCLUSIVE: {
if (lowKeyLimits[keyPos] == null || (lowKeyLimits[keyPos] != null && lowKeyInclusive[keyPos])) {
lowKeyLimits[keyPos] = limit;
- lowKeyConstants[keyPos] = optFuncExpr.getConstantVal(0);
+ lowKeyExprs[keyPos] = searchKeyExpr;
lowKeyInclusive[keyPos] = false;
} else {
couldntFigureOut = true;
@@ -184,7 +277,7 @@
case LOW_INCLUSIVE: {
if (lowKeyLimits[keyPos] == null) {
lowKeyLimits[keyPos] = limit;
- lowKeyConstants[keyPos] = optFuncExpr.getConstantVal(0);
+ lowKeyExprs[keyPos] = searchKeyExpr;
lowKeyInclusive[keyPos] = true;
} else {
couldntFigureOut = true;
@@ -205,22 +298,22 @@
}
}
if (couldntFigureOut) {
- return false;
+ return null;
}
// Rule out the cases unsupported by the current btree search
// implementation.
for (int i = 1; i < numSecondaryKeys; i++) {
if (lowKeyInclusive[i] != lowKeyInclusive[0] || highKeyInclusive[i] != highKeyInclusive[0]) {
- return false;
+ return null;
}
if (lowKeyLimits[0] == null && lowKeyLimits[i] != null || lowKeyLimits[0] != null
&& lowKeyLimits[i] == null) {
- return false;
+ return null;
}
if (highKeyLimits[0] == null && highKeyLimits[i] != null || highKeyLimits[0] != null
&& highKeyLimits[i] == null) {
- return false;
+ return null;
}
}
if (lowKeyLimits[0] == null) {
@@ -233,97 +326,90 @@
// 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 expressions for the assign.
- ArrayList<Mutable<ILogicalExpression>> keyExprList = new ArrayList<Mutable<ILogicalExpression>>();
- int numLowKeys = createKeyVarsAndExprs(lowKeyLimits, lowKeyConstants, keyExprList, keyVarList, context);
- int numHighKeys = createKeyVarsAndExprs(highKeyLimits, highKeyConstants, keyExprList, keyVarList, context);
+ // 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(lowKeyLimits, lowKeyExprs, assignKeyVarList, assignKeyExprList, keyVarList, context);
+ int numHighKeys = createKeyVarsAndExprs(highKeyLimits, highKeyExprs, assignKeyVarList, assignKeyExprList, keyVarList, context);
BTreeJobGenParams jobGenParams = new BTreeJobGenParams(chosenIndex.getIndexName(), IndexType.BTREE,
- dataset.getDatasetName(), false, false);
+ dataset.getDatasetName(), retainInput, requiresBroadcast);
jobGenParams.setLowKeyInclusive(lowKeyInclusive[0]);
jobGenParams.setHighKeyInclusive(highKeyInclusive[0]);
jobGenParams.setLowKeyVarList(keyVarList, 0, numLowKeys);
jobGenParams.setHighKeyVarList(keyVarList, numLowKeys, numHighKeys);
- // Assign operator that sets the secondary-index search-key fields.
- AssignOperator assignSearchKeys = new AssignOperator(keyVarList, keyExprList);
- // Input to this assign is the EmptyTupleSource (which the dataSourceScan also must have had as input).
- assignSearchKeys.getInputs().add(dataSourceScan.getInputs().get(0));
- assignSearchKeys.setExecutionMode(dataSourceScan.getExecutionMode());
+ 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(dataSourceScan.getInputs().get(0));
+ assignConstantSearchKeys.setExecutionMode(dataSourceScan.getExecutionMode());
+ inputOp = assignConstantSearchKeys;
+ } else {
+ // All index search keys are variables.
+ inputOp = probeSubTree.root;
+ }
UnnestMapOperator secondaryIndexUnnestOp = AccessMethodUtils.createSecondaryIndexUnnestMap(dataset, recordType,
- chosenIndex, assignSearchKeys, jobGenParams, context, false, false);
+ chosenIndex, inputOp, jobGenParams, context, false, retainInput);
// Generate the rest of the upstream plan which feeds the search results into the primary index.
UnnestMapOperator primaryIndexUnnestOp;
boolean isPrimaryIndex = chosenIndex.getIndexName().equals(dataset.getDatasetName());
if (!isPrimaryIndex) {
primaryIndexUnnestOp = AccessMethodUtils.createPrimaryIndexUnnestMap(dataSourceScan, dataset, recordType,
- secondaryIndexUnnestOp, context, true, false, false);
+ secondaryIndexUnnestOp, context, true, retainInput, false);
} else {
List<Object> primaryIndexOutputTypes = new ArrayList<Object>();
AccessMethodUtils.appendPrimaryIndexTypes(dataset, recordType, primaryIndexOutputTypes);
primaryIndexUnnestOp = new UnnestMapOperator(dataSourceScan.getVariables(),
- secondaryIndexUnnestOp.getExpressionRef(), primaryIndexOutputTypes, false);
- primaryIndexUnnestOp.getInputs().add(new MutableObject<ILogicalOperator>(assignSearchKeys));
+ secondaryIndexUnnestOp.getExpressionRef(), primaryIndexOutputTypes, retainInput);
+ primaryIndexUnnestOp.getInputs().add(new MutableObject<ILogicalOperator>(inputOp));
}
List<Mutable<ILogicalExpression>> remainingFuncExprs = new ArrayList<Mutable<ILogicalExpression>>();
- getNewSelectExprs(select, replacedFuncExprs, remainingFuncExprs);
- // Generate new select using the new condition.
+ getNewConditionExprs(conditionRef, replacedFuncExprs, remainingFuncExprs);
+ // Generate new condition.
if (!remainingFuncExprs.isEmpty()) {
ILogicalExpression pulledCond = createSelectCondition(remainingFuncExprs);
- SelectOperator selectRest = new SelectOperator(new MutableObject<ILogicalExpression>(pulledCond));
- if (assign != null) {
- subTree.dataSourceScanRef.setValue(primaryIndexUnnestOp);
- selectRest.getInputs().add(new MutableObject<ILogicalOperator>(assign));
- } else {
- selectRest.getInputs().add(new MutableObject<ILogicalOperator>(primaryIndexUnnestOp));
- }
- selectRest.setExecutionMode(((AbstractLogicalOperator) selectRef.getValue()).getExecutionMode());
- selectRef.setValue(selectRest);
+ conditionRef.setValue(pulledCond);
} else {
- primaryIndexUnnestOp.setExecutionMode(ExecutionMode.PARTITIONED);
- if (assign != null) {
- subTree.dataSourceScanRef.setValue(primaryIndexUnnestOp);
- selectRef.setValue(assign);
- } else {
- selectRef.setValue(primaryIndexUnnestOp);
- }
+ conditionRef.setValue(null);
}
- return true;
+ return primaryIndexUnnestOp;
}
-
- @Override
- public boolean applyJoinPlanTransformation(Mutable<ILogicalOperator> joinRef,
- OptimizableOperatorSubTree leftSubTree, OptimizableOperatorSubTree rightSubTree, Index chosenIndex,
- AccessMethodAnalysisContext analysisCtx, IOptimizationContext context) throws AlgebricksException {
- // TODO: Implement this.
- return false;
- }
-
- private int createKeyVarsAndExprs(LimitType[] keyLimits, IAlgebricksConstantValue[] keyConstants,
- ArrayList<Mutable<ILogicalExpression>> keyExprList, ArrayList<LogicalVariable> keyVarList,
- IOptimizationContext context) {
+
+ private int createKeyVarsAndExprs(LimitType[] keyLimits, ILogicalExpression[] searchKeyExprs,
+ ArrayList<LogicalVariable> assignKeyVarList, ArrayList<Mutable<ILogicalExpression>> assignKeyExprList,
+ ArrayList<LogicalVariable> keyVarList, IOptimizationContext context) {
if (keyLimits[0] == null) {
return 0;
}
int numKeys = keyLimits.length;
for (int i = 0; i < numKeys; i++) {
- LogicalVariable keyVar = context.newVar();
+ 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);
- keyExprList.add(new MutableObject<ILogicalExpression>(new ConstantExpression(keyConstants[i])));
}
return numKeys;
}
- private void getNewSelectExprs(SelectOperator select, Set<ILogicalExpression> replacedFuncExprs,
- List<Mutable<ILogicalExpression>> remainingFuncExprs) {
+ private void getNewConditionExprs(Mutable<ILogicalExpression> conditionRef,
+ Set<ILogicalExpression> replacedFuncExprs, List<Mutable<ILogicalExpression>> remainingFuncExprs) {
remainingFuncExprs.clear();
if (replacedFuncExprs.isEmpty()) {
return;
}
- AbstractFunctionCallExpression funcExpr = (AbstractFunctionCallExpression) select.getCondition().getValue();
+ AbstractFunctionCallExpression funcExpr = (AbstractFunctionCallExpression) conditionRef.getValue();
if (replacedFuncExprs.size() == 1) {
Iterator<ILogicalExpression> it = replacedFuncExprs.iterator();
if (!it.hasNext()) {
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 e4555aa..1c9477e 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
@@ -57,7 +57,8 @@
// Register access methods.
protected static Map<FunctionIdentifier, List<IAccessMethod>> accessMethods = new HashMap<FunctionIdentifier, List<IAccessMethod>>();
static {
- registerAccessMethod(InvertedIndexAccessMethod.INSTANCE, accessMethods);
+ registerAccessMethod(BTreeAccessMethod.INSTANCE, accessMethods);
+ registerAccessMethod(InvertedIndexAccessMethod.INSTANCE, accessMethods);
}
@Override
diff --git a/asterix-app/src/test/resources/optimizerts/queries/btree-index-join/primary-equi-join_01.aql b/asterix-app/src/test/resources/optimizerts/queries/btree-index-join/primary-equi-join_01.aql
new file mode 100644
index 0000000..f7f8d6c
--- /dev/null
+++ b/asterix-app/src/test/resources/optimizerts/queries/btree-index-join/primary-equi-join_01.aql
@@ -0,0 +1,46 @@
+/*
+ * Description : Equi joins two datasets, Customers and Orders, based on the customer id.
+ * Given the 'indexnl' hint we expect the join to be transformed
+ * into an indexed nested-loop join using Customers' primary index.
+ * Success : Yes
+ */
+
+drop dataverse test if exists;
+create dataverse test;
+use dataverse test;
+
+create type AddressType as closed {
+ number: int32,
+ street: string,
+ city: string
+}
+
+create type CustomerType as closed {
+ cid: int32,
+ name: string,
+ age: int32?,
+ address: AddressType?,
+ lastorder: {
+ oid: int32,
+ total: float
+ }
+}
+
+create type OrderType as closed {
+ oid: int32,
+ cid: int32,
+ orderstatus: string,
+ orderpriority: string,
+ clerk: string,
+ total: float
+}
+
+create dataset Customers(CustomerType) partitioned by key cid;
+create dataset Orders(OrderType) partitioned by key oid;
+
+write output to nc1:"rttest/btree-index-join_primary-equi-join_01.adm";
+
+for $c in dataset('Customers')
+for $o in dataset('Orders')
+where $c.cid /*+ indexnl */ = $o.cid
+return {"customer":$c, "order": $o}
diff --git a/asterix-app/src/test/resources/optimizerts/queries/btree-index-join/primary-equi-join_02.aql b/asterix-app/src/test/resources/optimizerts/queries/btree-index-join/primary-equi-join_02.aql
new file mode 100644
index 0000000..9ac6140
--- /dev/null
+++ b/asterix-app/src/test/resources/optimizerts/queries/btree-index-join/primary-equi-join_02.aql
@@ -0,0 +1,46 @@
+/*
+ * Description : Equi joins two datasets, Customers and Orders, based on the customer id.
+ * Given the 'indexnl' hint we expect the join to be transformed
+ * into an indexed nested-loop join using Customers' primary index.
+ * Success : Yes
+ */
+
+drop dataverse test if exists;
+create dataverse test;
+use dataverse test;
+
+create type AddressType as closed {
+ number: int32,
+ street: string,
+ city: string
+}
+
+create type CustomerType as closed {
+ cid: int32,
+ name: string,
+ age: int32?,
+ address: AddressType?,
+ lastorder: {
+ oid: int32,
+ total: float
+ }
+}
+
+create type OrderType as closed {
+ oid: int32,
+ cid: int32,
+ orderstatus: string,
+ orderpriority: string,
+ clerk: string,
+ total: float
+}
+
+create dataset Customers(CustomerType) partitioned by key cid;
+create dataset Orders(OrderType) partitioned by key oid;
+
+write output to nc1:"rttest/btree-index-join_primary-equi-join_02.adm";
+
+for $o in dataset('Orders')
+for $c in dataset('Customers')
+where $o.cid /*+ indexnl */ = $c.cid
+return {"customer":$c, "order": $o}
diff --git a/asterix-app/src/test/resources/optimizerts/queries/btree-index-join/primary-equi-join_03.aql b/asterix-app/src/test/resources/optimizerts/queries/btree-index-join/primary-equi-join_03.aql
new file mode 100644
index 0000000..e33e2a9
--- /dev/null
+++ b/asterix-app/src/test/resources/optimizerts/queries/btree-index-join/primary-equi-join_03.aql
@@ -0,0 +1,36 @@
+/*
+ * Description : Self-equi joins a dataset, Customers, based on the customer id.
+ * Given the 'indexnl' hint we expect the join to be transformed
+ * into an indexed nested-loop join using Customers' primary index.
+ * Success : Yes
+ */
+
+drop dataverse test if exists;
+create dataverse test;
+use dataverse test;
+
+create type AddressType as closed {
+ number: int32,
+ street: string,
+ city: string
+}
+
+create type CustomerType as closed {
+ cid: int32,
+ name: string,
+ age: int32?,
+ address: AddressType?,
+ lastorder: {
+ oid: int32,
+ total: float
+ }
+}
+
+create dataset Customers(CustomerType) partitioned by key cid;
+
+write output to nc1:"rttest/btree-index-join_primary-equi-join_03.adm";
+
+for $c1 in dataset('Customers')
+for $c2 in dataset('Customers')
+where $c1.cid /*+ indexnl */ = $c2.cid
+return {"customer1":$c1, "customer2":$c2}
diff --git a/asterix-app/src/test/resources/optimizerts/queries/btree-index-join/secondary-equi-join_01.aql b/asterix-app/src/test/resources/optimizerts/queries/btree-index-join/secondary-equi-join_01.aql
new file mode 100644
index 0000000..c861e3f
--- /dev/null
+++ b/asterix-app/src/test/resources/optimizerts/queries/btree-index-join/secondary-equi-join_01.aql
@@ -0,0 +1,47 @@
+/*
+ * Description : Equi joins two datasets, DBLP and CSX, based on their title.
+ * DBLP has a secondary btree index on title, and given the 'indexnl' hint
+ * we expect the join to be transformed into an indexed nested-loop join.
+ * 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 type CSXType as closed {
+ id: int32,
+ csxid: string,
+ title: string,
+ authors: string,
+ misc: string
+}
+
+create dataset DBLP(DBLPType) partitioned by key id;
+
+create dataset CSX(CSXType) partitioned by key id;
+
+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;
+
+load dataset CSX
+using "edu.uci.ics.asterix.external.dataset.adapter.NCFileSystemAdapter"
+(("path"="nc1://data/pub-small/csx-small-id.txt"),("format"="delimited-text"),("delimiter"=":"));
+
+create index title_index on DBLP(title);
+
+write output to nc1:"rttest/btree-index-join_title-secondary-equi-join_01.adm";
+
+for $a in dataset('DBLP')
+for $b in dataset('CSX')
+where $a.title /*+ indexnl */ = $b.title
+return {"arec": $a, "brec": $b}
diff --git a/asterix-app/src/test/resources/optimizerts/queries/btree-index-join/secondary-equi-join_02.aql b/asterix-app/src/test/resources/optimizerts/queries/btree-index-join/secondary-equi-join_02.aql
new file mode 100644
index 0000000..1f07316
--- /dev/null
+++ b/asterix-app/src/test/resources/optimizerts/queries/btree-index-join/secondary-equi-join_02.aql
@@ -0,0 +1,47 @@
+/*
+ * Description : Equi joins two datasets, DBLP and CSX, based on their title.
+ * CSX has a secondary btree index on title, and given the 'indexnl' hint
+ * we expect the join to be transformed into an indexed nested-loop join.
+ * 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 type CSXType as closed {
+ id: int32,
+ csxid: string,
+ title: string,
+ authors: string,
+ misc: string
+}
+
+create dataset DBLP(DBLPType) partitioned by key id;
+
+create dataset CSX(CSXType) partitioned by key id;
+
+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;
+
+load dataset CSX
+using "edu.uci.ics.asterix.external.dataset.adapter.NCFileSystemAdapter"
+(("path"="nc1://data/pub-small/csx-small-id.txt"),("format"="delimited-text"),("delimiter"=":"));
+
+create index title_index on CSX(title);
+
+write output to nc1:"rttest/btree-index-join_title-secondary-equi-join_02.adm";
+
+for $a in dataset('DBLP')
+for $b in dataset('CSX')
+where $a.title /*+ indexnl */ = $b.title
+return {"arec": $a, "brec": $b}
diff --git a/asterix-app/src/test/resources/optimizerts/queries/btree-index-join/secondary-equi-join_03.aql b/asterix-app/src/test/resources/optimizerts/queries/btree-index-join/secondary-equi-join_03.aql
new file mode 100644
index 0000000..cd3d964
--- /dev/null
+++ b/asterix-app/src/test/resources/optimizerts/queries/btree-index-join/secondary-equi-join_03.aql
@@ -0,0 +1,33 @@
+/*
+ * Description : Equi self-joins a dataset, DBLP, based on its title.
+ * DBLP has a secondary btree index on title, and given the 'indexnl' hint
+ * we expect the join to be transformed into an indexed nested-loop join.
+ * 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) partitioned by key id;
+
+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;
+
+create index title_index on DBLP(title);
+
+write output to nc1:"rttest/btree-index-join_title-secondary-equi-join_03.adm";
+
+for $a in dataset('DBLP')
+for $b in dataset('DBLP')
+where $a.title /*+ indexnl */ = $b.title
+return {"arec": $a, "brec": $b}
diff --git a/asterix-app/src/test/resources/optimizerts/results/btree-index-join/primary-equi-join_01.plan b/asterix-app/src/test/resources/optimizerts/results/btree-index-join/primary-equi-join_01.plan
new file mode 100644
index 0000000..80eec0d
--- /dev/null
+++ b/asterix-app/src/test/resources/optimizerts/results/btree-index-join/primary-equi-join_01.plan
@@ -0,0 +1,12 @@
+-- SINK_WRITE |PARTITIONED|
+ -- RANDOM_MERGE_EXCHANGE |PARTITIONED|
+ -- STREAM_PROJECT |PARTITIONED|
+ -- ASSIGN |PARTITIONED|
+ -- ONE_TO_ONE_EXCHANGE |UNPARTITIONED|
+ -- BTREE_SEARCH |UNPARTITIONED|
+ -- BROADCAST_EXCHANGE |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/optimizerts/results/btree-index-join/primary-equi-join_02.plan b/asterix-app/src/test/resources/optimizerts/results/btree-index-join/primary-equi-join_02.plan
new file mode 100644
index 0000000..80eec0d
--- /dev/null
+++ b/asterix-app/src/test/resources/optimizerts/results/btree-index-join/primary-equi-join_02.plan
@@ -0,0 +1,12 @@
+-- SINK_WRITE |PARTITIONED|
+ -- RANDOM_MERGE_EXCHANGE |PARTITIONED|
+ -- STREAM_PROJECT |PARTITIONED|
+ -- ASSIGN |PARTITIONED|
+ -- ONE_TO_ONE_EXCHANGE |UNPARTITIONED|
+ -- BTREE_SEARCH |UNPARTITIONED|
+ -- BROADCAST_EXCHANGE |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/optimizerts/results/btree-index-join/primary-equi-join_03.plan b/asterix-app/src/test/resources/optimizerts/results/btree-index-join/primary-equi-join_03.plan
new file mode 100644
index 0000000..02f36b5
--- /dev/null
+++ b/asterix-app/src/test/resources/optimizerts/results/btree-index-join/primary-equi-join_03.plan
@@ -0,0 +1,10 @@
+-- SINK_WRITE |PARTITIONED|
+ -- RANDOM_MERGE_EXCHANGE |PARTITIONED|
+ -- STREAM_PROJECT |PARTITIONED|
+ -- ASSIGN |PARTITIONED|
+ -- ONE_TO_ONE_EXCHANGE |UNPARTITIONED|
+ -- BTREE_SEARCH |UNPARTITIONED|
+ -- BROADCAST_EXCHANGE |PARTITIONED|
+ -- DATASOURCE_SCAN |PARTITIONED|
+ -- ONE_TO_ONE_EXCHANGE |PARTITIONED|
+ -- EMPTY_TUPLE_SOURCE |PARTITIONED|
diff --git a/asterix-app/src/test/resources/optimizerts/results/btree-index-join/secondary-equi-join_01.plan b/asterix-app/src/test/resources/optimizerts/results/btree-index-join/secondary-equi-join_01.plan
new file mode 100644
index 0000000..14cd128
--- /dev/null
+++ b/asterix-app/src/test/resources/optimizerts/results/btree-index-join/secondary-equi-join_01.plan
@@ -0,0 +1,18 @@
+-- SINK_WRITE |PARTITIONED|
+ -- RANDOM_MERGE_EXCHANGE |PARTITIONED|
+ -- STREAM_PROJECT |PARTITIONED|
+ -- ASSIGN |PARTITIONED|
+ -- ONE_TO_ONE_EXCHANGE |PARTITIONED|
+ -- BTREE_SEARCH |PARTITIONED|
+ -- ONE_TO_ONE_EXCHANGE |LOCAL|
+ -- STABLE_SORT [$$13(ASC)] |LOCAL|
+ -- ONE_TO_ONE_EXCHANGE |PARTITIONED|
+ -- STREAM_PROJECT |PARTITIONED|
+ -- ONE_TO_ONE_EXCHANGE |PARTITIONED|
+ -- BTREE_SEARCH |PARTITIONED|
+ -- BROADCAST_EXCHANGE |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/optimizerts/results/btree-index-join/secondary-equi-join_02.plan b/asterix-app/src/test/resources/optimizerts/results/btree-index-join/secondary-equi-join_02.plan
new file mode 100644
index 0000000..14cd128
--- /dev/null
+++ b/asterix-app/src/test/resources/optimizerts/results/btree-index-join/secondary-equi-join_02.plan
@@ -0,0 +1,18 @@
+-- SINK_WRITE |PARTITIONED|
+ -- RANDOM_MERGE_EXCHANGE |PARTITIONED|
+ -- STREAM_PROJECT |PARTITIONED|
+ -- ASSIGN |PARTITIONED|
+ -- ONE_TO_ONE_EXCHANGE |PARTITIONED|
+ -- BTREE_SEARCH |PARTITIONED|
+ -- ONE_TO_ONE_EXCHANGE |LOCAL|
+ -- STABLE_SORT [$$13(ASC)] |LOCAL|
+ -- ONE_TO_ONE_EXCHANGE |PARTITIONED|
+ -- STREAM_PROJECT |PARTITIONED|
+ -- ONE_TO_ONE_EXCHANGE |PARTITIONED|
+ -- BTREE_SEARCH |PARTITIONED|
+ -- BROADCAST_EXCHANGE |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/optimizerts/results/btree-index-join/secondary-equi-join_03.plan b/asterix-app/src/test/resources/optimizerts/results/btree-index-join/secondary-equi-join_03.plan
new file mode 100644
index 0000000..14cd128
--- /dev/null
+++ b/asterix-app/src/test/resources/optimizerts/results/btree-index-join/secondary-equi-join_03.plan
@@ -0,0 +1,18 @@
+-- SINK_WRITE |PARTITIONED|
+ -- RANDOM_MERGE_EXCHANGE |PARTITIONED|
+ -- STREAM_PROJECT |PARTITIONED|
+ -- ASSIGN |PARTITIONED|
+ -- ONE_TO_ONE_EXCHANGE |PARTITIONED|
+ -- BTREE_SEARCH |PARTITIONED|
+ -- ONE_TO_ONE_EXCHANGE |LOCAL|
+ -- STABLE_SORT [$$13(ASC)] |LOCAL|
+ -- ONE_TO_ONE_EXCHANGE |PARTITIONED|
+ -- STREAM_PROJECT |PARTITIONED|
+ -- ONE_TO_ONE_EXCHANGE |PARTITIONED|
+ -- BTREE_SEARCH |PARTITIONED|
+ -- BROADCAST_EXCHANGE |PARTITIONED|
+ -- ASSIGN |PARTITIONED|
+ -- ONE_TO_ONE_EXCHANGE |PARTITIONED|
+ -- DATASOURCE_SCAN |PARTITIONED|
+ -- ONE_TO_ONE_EXCHANGE |PARTITIONED|
+ -- EMPTY_TUPLE_SOURCE |PARTITIONED|