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 730a3b2..18f6f57 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
@@ -23,6 +23,7 @@
 
 import edu.uci.ics.asterix.common.config.DatasetConfig.IndexType;
 import edu.uci.ics.asterix.metadata.api.IMetadataEntity;
+import edu.uci.ics.asterix.metadata.bootstrap.MetadataConstants;
 import edu.uci.ics.asterix.metadata.declared.AqlMetadataProvider;
 import edu.uci.ics.asterix.metadata.entities.Dataset;
 import edu.uci.ics.asterix.metadata.entities.Index;
@@ -162,11 +163,16 @@
      */
     public void pruneIndexCandidates(IAccessMethod accessMethod, AccessMethodAnalysisContext analysisCtx) {
         Iterator<Map.Entry<Index, List<Integer>>> it = analysisCtx.indexExprs.entrySet().iterator();
+        // Used to keep track of matched expressions (added for prefix search)
+        int numMatchedKeys = 0;
+        ArrayList<Integer> matchedExpressions = new ArrayList<Integer>();
         while (it.hasNext()) {
             Map.Entry<Index, List<Integer>> entry = it.next();
             Index index = entry.getKey();
             boolean allUsed = true;
             int lastFieldMatched = -1;
+            matchedExpressions.clear();
+            numMatchedKeys = 0;
             for (int i = 0; i < index.getKeyFieldNames().size(); i++) {
                 String keyField = index.getKeyFieldNames().get(i);
                 boolean foundKeyField = false;
@@ -183,6 +189,8 @@
                     // Check if any field name in the optFuncExpr matches.
                     if (optFuncExpr.findFieldName(keyField) != -1) {
                         foundKeyField = true;
+                        matchedExpressions.add(ix);
+                        numMatchedKeys++;
                         if (lastFieldMatched == i - 1) {
                             lastFieldMatched = i;
                         }
@@ -191,6 +199,15 @@
                 }
                 if (!foundKeyField) {
                     allUsed = false;
+                    // if any expression was matched, remove the non-matched expressions, otherwise the index is unusable
+                    if (lastFieldMatched >= 0) {
+                        exprsIter = entry.getValue().iterator();
+                        while (exprsIter.hasNext()) {
+                            if (!matchedExpressions.contains(exprsIter.next())) {
+                                exprsIter.remove();
+                            }
+                        }
+                    }
                     break;
                 }
             }
@@ -198,11 +215,22 @@
             // are not, remove this candidate.
             if (!allUsed && accessMethod.matchAllIndexExprs()) {
                 it.remove();
+                continue;
             }
             // A prefix of the index exprs may have been matched.
-            if (lastFieldMatched < 0 && accessMethod.matchPrefixIndexExprs()) {
-                it.remove();
+            if (accessMethod.matchPrefixIndexExprs()) {
+                // Remove the candidate if the dataset is a metadata dataset and the index is secondary
+                if (index.getDataverseName().equals(MetadataConstants.METADATA_DATAVERSE_NAME)
+                        && !index.isPrimaryIndex()) {
+                    it.remove();
+                    continue;
+                }
+                if (lastFieldMatched < 0) {
+                    it.remove();
+                    continue;
+                }
             }
+            analysisCtx.indexNumMatchedKeys.put(index, new Integer(numMatchedKeys));
         }
     }
 
diff --git a/asterix-algebra/src/main/java/edu/uci/ics/asterix/optimizer/rules/am/AccessMethodAnalysisContext.java b/asterix-algebra/src/main/java/edu/uci/ics/asterix/optimizer/rules/am/AccessMethodAnalysisContext.java
index 9d121a7a..60bffce 100644
--- a/asterix-algebra/src/main/java/edu/uci/ics/asterix/optimizer/rules/am/AccessMethodAnalysisContext.java
+++ b/asterix-algebra/src/main/java/edu/uci/ics/asterix/optimizer/rules/am/AccessMethodAnalysisContext.java
@@ -39,6 +39,9 @@
 
     // Maps from index to the dataset it is indexing.
     public HashMap<Index, Dataset> indexDatasetMap = new HashMap<Index, Dataset>();
+    
+    // Maps from an index to the number of matched fields in the query plan (for performing prefix search)
+    public HashMap<Index, Integer> indexNumMatchedKeys = new HashMap<Index, Integer>();
 
     // variables for resetting null placeholder for left-outer-join
     private Mutable<ILogicalOperator> lojGroupbyOpRef = 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 96c1b02..12bb0dc 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
@@ -100,13 +100,12 @@
 
     @Override
     public boolean matchAllIndexExprs() {
-        return true;
+        return false;
     }
 
     @Override
     public boolean matchPrefixIndexExprs() {
-        // TODO: The BTree can support prefix searches. Enable this later and add tests.
-        return false;
+        return true;
     }
 
     @Override
@@ -215,7 +214,12 @@
         ARecordType recordType = indexSubTree.recordType;
         // we made sure indexSubTree has datasource scan
         DataSourceScanOperator dataSourceScan = (DataSourceScanOperator) indexSubTree.dataSourceRef.getValue();
-        int numSecondaryKeys = chosenIndex.getKeyFieldNames().size();
+        List<Integer> exprList = analysisCtx.indexExprs.get(chosenIndex);
+        List<IOptimizableFuncExpr> matchedFuncExprs = analysisCtx.matchedFuncExprs;
+        int numSecondaryKeys = analysisCtx.indexNumMatchedKeys.get(chosenIndex);
+        // List of function expressions that will be replaced by the secondary-index search.
+        // These func exprs will be removed from the select condition at the very end of this method.
+        Set<ILogicalExpression> replacedFuncExprs = new HashSet<ILogicalExpression>();
 
         // Info on high and low keys for the BTree search predicate.
         ILogicalExpression[] lowKeyExprs = new ILogicalExpression[numSecondaryKeys];
@@ -225,11 +229,6 @@
         boolean[] lowKeyInclusive = new boolean[numSecondaryKeys];
         boolean[] highKeyInclusive = new boolean[numSecondaryKeys];
 
-        List<Integer> exprList = analysisCtx.indexExprs.get(chosenIndex);
-        List<IOptimizableFuncExpr> matchedFuncExprs = analysisCtx.matchedFuncExprs;
-        // List of function expressions that will be replaced by the secondary-index search.
-        // These func exprs will be removed from the select condition at the very end of this method.
-        Set<ILogicalExpression> replacedFuncExprs = new HashSet<ILogicalExpression>();
         // TODO: For now we don't do any sophisticated analysis of the func exprs to come up with "the best" range predicate.
         // If we can't figure out how to integrate a certain funcExpr into the current predicate, we just bail by setting this flag.
         boolean couldntFigureOut = false;
diff --git a/asterix-app/src/test/resources/optimizerts/queries/btree-index/btree-primary-01.aql b/asterix-app/src/test/resources/optimizerts/queries/btree-index/btree-primary-01.aql
index 0d096a7..1877676b 100644
--- a/asterix-app/src/test/resources/optimizerts/queries/btree-index/btree-primary-01.aql
+++ b/asterix-app/src/test/resources/optimizerts/queries/btree-index/btree-primary-01.aql
@@ -1,11 +1,11 @@
 /*
- *  Description     : This test is intended to verify that the primary BTree index is NOT used 
+ *  Description     : This test is intended to verify that the primary BTree index is used 
  *                  : in the optimized query plan.
  *  Expected Result : Success
  *  Date            : 13th Aug 2012
  */
 
-// Please note this is a Negative test and the BTree index should NOT be used in the plan.
+// Please note this is a Positive test and the BTree index should be used in the plan.
 
 drop dataverse test if exists;
 create dataverse test;
diff --git a/asterix-app/src/test/resources/optimizerts/queries/btree-index/btree-primary-02.aql b/asterix-app/src/test/resources/optimizerts/queries/btree-index/btree-primary-02.aql
index fbcdd50..305b793 100644
--- a/asterix-app/src/test/resources/optimizerts/queries/btree-index/btree-primary-02.aql
+++ b/asterix-app/src/test/resources/optimizerts/queries/btree-index/btree-primary-02.aql
@@ -1,11 +1,11 @@
 /*
- *  Description     : This test is intended to verify that the primary BTree index is NOT used 
+ *  Description     : This test is intended to verify that the primary BTree index is used 
  *                  : in the optimized query plan.
  *  Expected Result : Success
  *  Date            : 13th Aug 2012
  */
 
-// This is a Negative test - prefix search, BTree index should not be used in the plan.
+// This is a Positive test - prefix search, BTree index should be used in the plan.
 
 drop dataverse test if exists;
 create dataverse test;
diff --git a/asterix-app/src/test/resources/optimizerts/queries/btree-index/btree-primary-03.aql b/asterix-app/src/test/resources/optimizerts/queries/btree-index/btree-primary-03.aql
index 2047b62..c752bb6 100644
--- a/asterix-app/src/test/resources/optimizerts/queries/btree-index/btree-primary-03.aql
+++ b/asterix-app/src/test/resources/optimizerts/queries/btree-index/btree-primary-03.aql
@@ -1,11 +1,11 @@
 /*
- *  Description     : This test is intended to verify that the primary BTree index is NOT used 
+ *  Description     : This test is intended to verify that the primary BTree index is used 
  *                  : in the optimized query plan.
  *  Expected Result : Success
  *  Date            : 13th Aug 2012
  */
 
-// Negative test - prefix search, BTree index should not be used.
+// Positive test - prefix search, BTree index should be used.
 
 drop dataverse test if exists;
 create dataverse test;
diff --git a/asterix-app/src/test/resources/optimizerts/queries/btree-index/btree-primary-04.aql b/asterix-app/src/test/resources/optimizerts/queries/btree-index/btree-primary-04.aql
index 84147ae..079f30c 100644
--- a/asterix-app/src/test/resources/optimizerts/queries/btree-index/btree-primary-04.aql
+++ b/asterix-app/src/test/resources/optimizerts/queries/btree-index/btree-primary-04.aql
@@ -1,11 +1,11 @@
 /*
- *  Description     : This test is intended to verify that the primary BTree index is NOT used 
+ *  Description     : This test is intended to verify that the primary BTree index is used 
  *                  : in the optimized query plan.
  *  Expected Result : Success
  *  Date            : 13th Aug 2012
  */
 
-// Negative test - prefix search, BTree index should not be used in query plan
+// Positive test - prefix search, BTree index should be used in query plan
 
 drop dataverse test if exists;
 create dataverse test;
diff --git a/asterix-app/src/test/resources/optimizerts/queries/btree-index/btree-primary-06.aql b/asterix-app/src/test/resources/optimizerts/queries/btree-index/btree-primary-06.aql
index 08164fd..3532676 100644
--- a/asterix-app/src/test/resources/optimizerts/queries/btree-index/btree-primary-06.aql
+++ b/asterix-app/src/test/resources/optimizerts/queries/btree-index/btree-primary-06.aql
@@ -5,7 +5,7 @@
  *  Date            : 13th Aug 2012
  */
 
-// Negative test - prefix search, BTree index should NOT be used in the query plan.
+// Positive test - prefix search, BTree index should be used in the query plan.
 
 drop dataverse test if exists;
 create dataverse test;
diff --git a/asterix-app/src/test/resources/optimizerts/queries/btree-index/btree-secondary-31.aql b/asterix-app/src/test/resources/optimizerts/queries/btree-index/btree-secondary-31.aql
index c2e6257..9f8ebc4 100644
--- a/asterix-app/src/test/resources/optimizerts/queries/btree-index/btree-secondary-31.aql
+++ b/asterix-app/src/test/resources/optimizerts/queries/btree-index/btree-secondary-31.aql
@@ -1,12 +1,12 @@
 /*
  *  Description     : BTree Index verification test
- *                  : This test is intended to verify that the secondary BTree index is NOT used 
+ *                  : This test is intended to verify that the secondary BTree index is used 
  *                  : in the optimized query plan.
  *  Expected Result : Success
  *  Date            : 13th Aug 2012
  */
 
-// Please note this is a Negative test and the BTree index should NOT be used in the plan.
+// Please note this is a Positive test and the BTree index should be used in the plan.
 
 drop dataverse test if exists;
 create dataverse test;
diff --git a/asterix-app/src/test/resources/optimizerts/queries/btree-index/btree-secondary-32.aql b/asterix-app/src/test/resources/optimizerts/queries/btree-index/btree-secondary-32.aql
index d009e2e..f2a12d6 100644
--- a/asterix-app/src/test/resources/optimizerts/queries/btree-index/btree-secondary-32.aql
+++ b/asterix-app/src/test/resources/optimizerts/queries/btree-index/btree-secondary-32.aql
@@ -1,12 +1,12 @@
 /*
  *  Description     : BTree Index verification test
- *                  : This test is intended to verify that the secondary BTree index is NOT used 
+ *                  : This test is intended to verify that the secondary BTree index is used 
  *                  : in the optimized query plan.
  *  Expected Result : Success
  *  Date            : 13th Aug 2012
  */
 
-// This is a Negative test - prefix search, BTree index should not be used in the plan.
+// This is a Positive test - prefix search, BTree index should be used in the plan.
 
 drop dataverse test if exists;
 create dataverse test;
diff --git a/asterix-app/src/test/resources/optimizerts/queries/btree-index/btree-secondary-33.aql b/asterix-app/src/test/resources/optimizerts/queries/btree-index/btree-secondary-33.aql
index 2b364e4..f73fe6d 100644
--- a/asterix-app/src/test/resources/optimizerts/queries/btree-index/btree-secondary-33.aql
+++ b/asterix-app/src/test/resources/optimizerts/queries/btree-index/btree-secondary-33.aql
@@ -6,7 +6,7 @@
  *  Date            : 13th Aug 2012
  */
 
-// Negative test - prefix search, BTree index should not be used.
+// Positive test - prefix search, BTree index should be used.
 
 drop dataverse test if exists;
 create dataverse test;
diff --git a/asterix-app/src/test/resources/optimizerts/queries/btree-index/btree-secondary-34.aql b/asterix-app/src/test/resources/optimizerts/queries/btree-index/btree-secondary-34.aql
index f20b5a9..c637649 100644
--- a/asterix-app/src/test/resources/optimizerts/queries/btree-index/btree-secondary-34.aql
+++ b/asterix-app/src/test/resources/optimizerts/queries/btree-index/btree-secondary-34.aql
@@ -1,12 +1,12 @@
 /*
  *  Description     : BTree Index verification test
- *                  : This test is intended to verify that the secondary BTree index is NOT used 
+ *                  : This test is intended to verify that the secondary BTree index is used 
  *                  : in the optimized query plan.
  *  Expected Result : Success
  *  Date            : 13th Aug 2012
  */
 
-// Negative test - prefix search, BTree index should not be used in query plan
+// Positive test - prefix search, BTree index should be used in query plan
 
 drop dataverse test if exists;
 create dataverse test;
diff --git a/asterix-app/src/test/resources/optimizerts/queries/btree-index/btree-secondary-36.aql b/asterix-app/src/test/resources/optimizerts/queries/btree-index/btree-secondary-36.aql
index 7d72623..894ba63 100644
--- a/asterix-app/src/test/resources/optimizerts/queries/btree-index/btree-secondary-36.aql
+++ b/asterix-app/src/test/resources/optimizerts/queries/btree-index/btree-secondary-36.aql
@@ -6,7 +6,7 @@
  *  Date            : 13th Aug 2012
  */
 
-// Negative test - prefix search, BTree index should NOT be used in the query plan.
+// Positive test - prefix search, BTree index should be used in the query plan.
 
 drop dataverse test if exists;
 create dataverse test;
diff --git a/asterix-app/src/test/resources/optimizerts/results/btree-index/btree-primary-01.plan b/asterix-app/src/test/resources/optimizerts/results/btree-index/btree-primary-01.plan
index 3d9e18f..6f13ebb 100644
--- a/asterix-app/src/test/resources/optimizerts/results/btree-index/btree-primary-01.plan
+++ b/asterix-app/src/test/resources/optimizerts/results/btree-index/btree-primary-01.plan
@@ -1,9 +1,8 @@
 -- DISTRIBUTE_RESULT  |PARTITIONED|
   -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
     -- STREAM_PROJECT  |PARTITIONED|
-      -- STREAM_SELECT  |PARTITIONED|
-        -- STREAM_PROJECT  |PARTITIONED|
+      -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
+        -- BTREE_SEARCH  |PARTITIONED|
           -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
-            -- DATASOURCE_SCAN  |PARTITIONED|
-              -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
-                -- EMPTY_TUPLE_SOURCE  |PARTITIONED|
+            -- ASSIGN  |PARTITIONED|
+              -- EMPTY_TUPLE_SOURCE  |PARTITIONED|
diff --git a/asterix-app/src/test/resources/optimizerts/results/btree-index/btree-primary-02.plan b/asterix-app/src/test/resources/optimizerts/results/btree-index/btree-primary-02.plan
index 3d9e18f..a9e223a 100644
--- a/asterix-app/src/test/resources/optimizerts/results/btree-index/btree-primary-02.plan
+++ b/asterix-app/src/test/resources/optimizerts/results/btree-index/btree-primary-02.plan
@@ -1,9 +1,8 @@
 -- DISTRIBUTE_RESULT  |PARTITIONED|
   -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
     -- STREAM_PROJECT  |PARTITIONED|
-      -- STREAM_SELECT  |PARTITIONED|
-        -- STREAM_PROJECT  |PARTITIONED|
+      -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
+        -- BTREE_SEARCH  |PARTITIONED|
           -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
-            -- DATASOURCE_SCAN  |PARTITIONED|
-              -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
-                -- EMPTY_TUPLE_SOURCE  |PARTITIONED|
+            -- ASSIGN  |PARTITIONED|
+              -- EMPTY_TUPLE_SOURCE  |PARTITIONED|
\ No newline at end of file
diff --git a/asterix-app/src/test/resources/optimizerts/results/btree-index/btree-primary-03.plan b/asterix-app/src/test/resources/optimizerts/results/btree-index/btree-primary-03.plan
index 3d9e18f..6f13ebb 100644
--- a/asterix-app/src/test/resources/optimizerts/results/btree-index/btree-primary-03.plan
+++ b/asterix-app/src/test/resources/optimizerts/results/btree-index/btree-primary-03.plan
@@ -1,9 +1,8 @@
 -- DISTRIBUTE_RESULT  |PARTITIONED|
   -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
     -- STREAM_PROJECT  |PARTITIONED|
-      -- STREAM_SELECT  |PARTITIONED|
-        -- STREAM_PROJECT  |PARTITIONED|
+      -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
+        -- BTREE_SEARCH  |PARTITIONED|
           -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
-            -- DATASOURCE_SCAN  |PARTITIONED|
-              -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
-                -- EMPTY_TUPLE_SOURCE  |PARTITIONED|
+            -- ASSIGN  |PARTITIONED|
+              -- EMPTY_TUPLE_SOURCE  |PARTITIONED|
diff --git a/asterix-app/src/test/resources/optimizerts/results/btree-index/btree-primary-04.plan b/asterix-app/src/test/resources/optimizerts/results/btree-index/btree-primary-04.plan
index 3d9e18f..6f13ebb 100644
--- a/asterix-app/src/test/resources/optimizerts/results/btree-index/btree-primary-04.plan
+++ b/asterix-app/src/test/resources/optimizerts/results/btree-index/btree-primary-04.plan
@@ -1,9 +1,8 @@
 -- DISTRIBUTE_RESULT  |PARTITIONED|
   -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
     -- STREAM_PROJECT  |PARTITIONED|
-      -- STREAM_SELECT  |PARTITIONED|
-        -- STREAM_PROJECT  |PARTITIONED|
+      -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
+        -- BTREE_SEARCH  |PARTITIONED|
           -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
-            -- DATASOURCE_SCAN  |PARTITIONED|
-              -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
-                -- EMPTY_TUPLE_SOURCE  |PARTITIONED|
+            -- ASSIGN  |PARTITIONED|
+              -- EMPTY_TUPLE_SOURCE  |PARTITIONED|
diff --git a/asterix-app/src/test/resources/optimizerts/results/btree-index/btree-primary-06.plan b/asterix-app/src/test/resources/optimizerts/results/btree-index/btree-primary-06.plan
index 3d9e18f..6f13ebb 100644
--- a/asterix-app/src/test/resources/optimizerts/results/btree-index/btree-primary-06.plan
+++ b/asterix-app/src/test/resources/optimizerts/results/btree-index/btree-primary-06.plan
@@ -1,9 +1,8 @@
 -- DISTRIBUTE_RESULT  |PARTITIONED|
   -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
     -- STREAM_PROJECT  |PARTITIONED|
-      -- STREAM_SELECT  |PARTITIONED|
-        -- STREAM_PROJECT  |PARTITIONED|
+      -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
+        -- BTREE_SEARCH  |PARTITIONED|
           -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
-            -- DATASOURCE_SCAN  |PARTITIONED|
-              -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
-                -- EMPTY_TUPLE_SOURCE  |PARTITIONED|
+            -- ASSIGN  |PARTITIONED|
+              -- EMPTY_TUPLE_SOURCE  |PARTITIONED|
diff --git a/asterix-app/src/test/resources/optimizerts/results/btree-index/btree-secondary-31.plan b/asterix-app/src/test/resources/optimizerts/results/btree-index/btree-secondary-31.plan
index 06194e4..d7667d6 100644
--- a/asterix-app/src/test/resources/optimizerts/results/btree-index/btree-secondary-31.plan
+++ b/asterix-app/src/test/resources/optimizerts/results/btree-index/btree-secondary-31.plan
@@ -3,6 +3,13 @@
     -- STREAM_SELECT  |PARTITIONED|
       -- STREAM_PROJECT  |PARTITIONED|
         -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
-          -- DATASOURCE_SCAN  |PARTITIONED|
+          -- BTREE_SEARCH  |PARTITIONED|
             -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
-              -- EMPTY_TUPLE_SOURCE  |PARTITIONED|
+              -- STABLE_SORT [$$9(ASC)]  |PARTITIONED|
+                -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
+                  -- STREAM_PROJECT  |PARTITIONED|
+                    -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
+                      -- BTREE_SEARCH  |PARTITIONED|
+                        -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
+                          -- ASSIGN  |PARTITIONED|
+                            -- EMPTY_TUPLE_SOURCE  |PARTITIONED|
diff --git a/asterix-app/src/test/resources/optimizerts/results/btree-index/btree-secondary-32.plan b/asterix-app/src/test/resources/optimizerts/results/btree-index/btree-secondary-32.plan
index 06194e4..d7667d6 100644
--- a/asterix-app/src/test/resources/optimizerts/results/btree-index/btree-secondary-32.plan
+++ b/asterix-app/src/test/resources/optimizerts/results/btree-index/btree-secondary-32.plan
@@ -3,6 +3,13 @@
     -- STREAM_SELECT  |PARTITIONED|
       -- STREAM_PROJECT  |PARTITIONED|
         -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
-          -- DATASOURCE_SCAN  |PARTITIONED|
+          -- BTREE_SEARCH  |PARTITIONED|
             -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
-              -- EMPTY_TUPLE_SOURCE  |PARTITIONED|
+              -- STABLE_SORT [$$9(ASC)]  |PARTITIONED|
+                -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
+                  -- STREAM_PROJECT  |PARTITIONED|
+                    -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
+                      -- BTREE_SEARCH  |PARTITIONED|
+                        -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
+                          -- ASSIGN  |PARTITIONED|
+                            -- EMPTY_TUPLE_SOURCE  |PARTITIONED|
diff --git a/asterix-app/src/test/resources/optimizerts/results/btree-index/btree-secondary-33.plan b/asterix-app/src/test/resources/optimizerts/results/btree-index/btree-secondary-33.plan
index 06194e4..d7667d6 100644
--- a/asterix-app/src/test/resources/optimizerts/results/btree-index/btree-secondary-33.plan
+++ b/asterix-app/src/test/resources/optimizerts/results/btree-index/btree-secondary-33.plan
@@ -3,6 +3,13 @@
     -- STREAM_SELECT  |PARTITIONED|
       -- STREAM_PROJECT  |PARTITIONED|
         -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
-          -- DATASOURCE_SCAN  |PARTITIONED|
+          -- BTREE_SEARCH  |PARTITIONED|
             -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
-              -- EMPTY_TUPLE_SOURCE  |PARTITIONED|
+              -- STABLE_SORT [$$9(ASC)]  |PARTITIONED|
+                -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
+                  -- STREAM_PROJECT  |PARTITIONED|
+                    -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
+                      -- BTREE_SEARCH  |PARTITIONED|
+                        -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
+                          -- ASSIGN  |PARTITIONED|
+                            -- EMPTY_TUPLE_SOURCE  |PARTITIONED|
diff --git a/asterix-app/src/test/resources/optimizerts/results/btree-index/btree-secondary-34.plan b/asterix-app/src/test/resources/optimizerts/results/btree-index/btree-secondary-34.plan
index 06194e4..d7667d6 100644
--- a/asterix-app/src/test/resources/optimizerts/results/btree-index/btree-secondary-34.plan
+++ b/asterix-app/src/test/resources/optimizerts/results/btree-index/btree-secondary-34.plan
@@ -3,6 +3,13 @@
     -- STREAM_SELECT  |PARTITIONED|
       -- STREAM_PROJECT  |PARTITIONED|
         -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
-          -- DATASOURCE_SCAN  |PARTITIONED|
+          -- BTREE_SEARCH  |PARTITIONED|
             -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
-              -- EMPTY_TUPLE_SOURCE  |PARTITIONED|
+              -- STABLE_SORT [$$9(ASC)]  |PARTITIONED|
+                -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
+                  -- STREAM_PROJECT  |PARTITIONED|
+                    -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
+                      -- BTREE_SEARCH  |PARTITIONED|
+                        -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
+                          -- ASSIGN  |PARTITIONED|
+                            -- EMPTY_TUPLE_SOURCE  |PARTITIONED|
diff --git a/asterix-app/src/test/resources/optimizerts/results/btree-index/btree-secondary-36.plan b/asterix-app/src/test/resources/optimizerts/results/btree-index/btree-secondary-36.plan
index 06194e4..caa0446 100644
--- a/asterix-app/src/test/resources/optimizerts/results/btree-index/btree-secondary-36.plan
+++ b/asterix-app/src/test/resources/optimizerts/results/btree-index/btree-secondary-36.plan
@@ -3,6 +3,13 @@
     -- STREAM_SELECT  |PARTITIONED|
       -- STREAM_PROJECT  |PARTITIONED|
         -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
-          -- DATASOURCE_SCAN  |PARTITIONED|
+          -- BTREE_SEARCH  |PARTITIONED|
             -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
-              -- EMPTY_TUPLE_SOURCE  |PARTITIONED|
+              -- STABLE_SORT [$$10(ASC)]  |PARTITIONED|
+                -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
+                  -- STREAM_PROJECT  |PARTITIONED|
+                    -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
+                      -- BTREE_SEARCH  |PARTITIONED|
+                        -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
+                          -- ASSIGN  |PARTITIONED|
+                            -- EMPTY_TUPLE_SOURCE  |PARTITIONED|
\ No newline at end of file