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 28d55f3..44d35726 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
@@ -15,8 +15,9 @@
 package edu.uci.ics.asterix.optimizer.rules.am;
 
 import java.util.ArrayList;
-import java.util.HashMap;
 import java.util.List;
+import java.util.Map;
+import java.util.TreeMap;
 
 import org.apache.commons.lang3.mutable.Mutable;
 
@@ -36,13 +37,13 @@
     // Contains candidate indexes and a list of (integer,integer) tuples that index into matchedFuncExprs and matched variable inside this expr.
     // We are mapping from candidate indexes to a list of function expressions 
     // that match one of the index's expressions.
-    public HashMap<Index, List<Pair<Integer, Integer>>> indexExprsAndVars = new HashMap<Index, List<Pair<Integer, Integer>>>();
+    public Map<Index, List<Pair<Integer, Integer>>> indexExprsAndVars = new TreeMap<Index, List<Pair<Integer, Integer>>>();
 
     // Maps from index to the dataset it is indexing.
-    public HashMap<Index, Dataset> indexDatasetMap = new HashMap<Index, Dataset>();
+    public Map<Index, Dataset> indexDatasetMap = new TreeMap<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>();
+    public Map<Index, Integer> indexNumMatchedKeys = new TreeMap<Index, Integer>();
 
     // variables for resetting null placeholder for left-outer-join
     private Mutable<ILogicalOperator> lojGroupbyOpRef = null;
diff --git a/asterix-app/src/test/resources/optimizerts/results/nested-open-index/inverted-index-join/word-fuzzyeq-jaccard_04.plan b/asterix-app/src/test/resources/optimizerts/results/nested-open-index/inverted-index-join/word-fuzzyeq-jaccard_04.plan
index 1aec683..6dcb9fa 100644
--- a/asterix-app/src/test/resources/optimizerts/results/nested-open-index/inverted-index-join/word-fuzzyeq-jaccard_04.plan
+++ b/asterix-app/src/test/resources/optimizerts/results/nested-open-index/inverted-index-join/word-fuzzyeq-jaccard_04.plan
@@ -4,12 +4,12 @@
       -- ASSIGN  |PARTITIONED|
         -- STREAM_PROJECT  |PARTITIONED|
           -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
-            -- HYBRID_HASH_JOIN [$$30][$$21]  |PARTITIONED|
+            -- HYBRID_HASH_JOIN [$$30][$$20]  |PARTITIONED|
               -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
                 -- DATASOURCE_SCAN  |PARTITIONED|
                   -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
                     -- EMPTY_TUPLE_SOURCE  |PARTITIONED|
-              -- HASH_PARTITION_EXCHANGE [$$21]  |PARTITIONED|
+              -- HASH_PARTITION_EXCHANGE [$$20]  |PARTITIONED|
                 -- STREAM_PROJECT  |PARTITIONED|
                   -- STREAM_SELECT  |PARTITIONED|
                     -- ASSIGN  |PARTITIONED|
@@ -29,4 +29,4 @@
                                                 -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
                                                   -- DATASOURCE_SCAN  |PARTITIONED|
                                                     -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
-                                                      -- EMPTY_TUPLE_SOURCE  |PARTITIONED|
\ No newline at end of file
+                                                      -- EMPTY_TUPLE_SOURCE  |PARTITIONED|
diff --git a/asterix-app/src/test/resources/optimizerts/results/open-index-enforced/inverted-index-join/word-fuzzyeq-jaccard_04.plan b/asterix-app/src/test/resources/optimizerts/results/open-index-enforced/inverted-index-join/word-fuzzyeq-jaccard_04.plan
index 10b34a3..420d3ea 100644
--- a/asterix-app/src/test/resources/optimizerts/results/open-index-enforced/inverted-index-join/word-fuzzyeq-jaccard_04.plan
+++ b/asterix-app/src/test/resources/optimizerts/results/open-index-enforced/inverted-index-join/word-fuzzyeq-jaccard_04.plan
@@ -4,12 +4,12 @@
       -- ASSIGN  |PARTITIONED|
         -- STREAM_PROJECT  |PARTITIONED|
           -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
-            -- HYBRID_HASH_JOIN [$$24][$$15]  |PARTITIONED|
+            -- HYBRID_HASH_JOIN [$$24][$$14]  |PARTITIONED|
               -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
                 -- DATASOURCE_SCAN  |PARTITIONED|
                   -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
                     -- EMPTY_TUPLE_SOURCE  |PARTITIONED|
-              -- HASH_PARTITION_EXCHANGE [$$15]  |PARTITIONED|
+              -- HASH_PARTITION_EXCHANGE [$$14]  |PARTITIONED|
                 -- STREAM_PROJECT  |PARTITIONED|
                   -- STREAM_SELECT  |PARTITIONED|
                     -- ASSIGN  |PARTITIONED|
diff --git a/asterix-app/src/test/resources/optimizerts/results/open-index-enforced/inverted-index-join/word-jaccard-check_04.plan b/asterix-app/src/test/resources/optimizerts/results/open-index-enforced/inverted-index-join/word-jaccard-check_04.plan
index 27e8085..5b169eba 100644
--- a/asterix-app/src/test/resources/optimizerts/results/open-index-enforced/inverted-index-join/word-jaccard-check_04.plan
+++ b/asterix-app/src/test/resources/optimizerts/results/open-index-enforced/inverted-index-join/word-jaccard-check_04.plan
@@ -4,12 +4,12 @@
       -- ASSIGN  |PARTITIONED|
         -- STREAM_PROJECT  |PARTITIONED|
           -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
-            -- HYBRID_HASH_JOIN [$$25][$$16]  |PARTITIONED|
+            -- HYBRID_HASH_JOIN [$$25][$$15]  |PARTITIONED|
               -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
                 -- DATASOURCE_SCAN  |PARTITIONED|
                   -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
                     -- EMPTY_TUPLE_SOURCE  |PARTITIONED|
-              -- HASH_PARTITION_EXCHANGE [$$16]  |PARTITIONED|
+              -- HASH_PARTITION_EXCHANGE [$$15]  |PARTITIONED|
                 -- STREAM_PROJECT  |PARTITIONED|
                   -- STREAM_SELECT  |PARTITIONED|
                     -- ASSIGN  |PARTITIONED|
diff --git a/asterix-app/src/test/resources/optimizerts/results/open-index-enforced/inverted-index-join/word-jaccard_04.plan b/asterix-app/src/test/resources/optimizerts/results/open-index-enforced/inverted-index-join/word-jaccard_04.plan
index 27e8085..5b169eba 100644
--- a/asterix-app/src/test/resources/optimizerts/results/open-index-enforced/inverted-index-join/word-jaccard_04.plan
+++ b/asterix-app/src/test/resources/optimizerts/results/open-index-enforced/inverted-index-join/word-jaccard_04.plan
@@ -4,12 +4,12 @@
       -- ASSIGN  |PARTITIONED|
         -- STREAM_PROJECT  |PARTITIONED|
           -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
-            -- HYBRID_HASH_JOIN [$$25][$$16]  |PARTITIONED|
+            -- HYBRID_HASH_JOIN [$$25][$$15]  |PARTITIONED|
               -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
                 -- DATASOURCE_SCAN  |PARTITIONED|
                   -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
                     -- EMPTY_TUPLE_SOURCE  |PARTITIONED|
-              -- HASH_PARTITION_EXCHANGE [$$16]  |PARTITIONED|
+              -- HASH_PARTITION_EXCHANGE [$$15]  |PARTITIONED|
                 -- STREAM_PROJECT  |PARTITIONED|
                   -- STREAM_SELECT  |PARTITIONED|
                     -- ASSIGN  |PARTITIONED|
diff --git a/asterix-app/src/test/resources/optimizerts/results/rtree-index-join/query-issue838.plan b/asterix-app/src/test/resources/optimizerts/results/rtree-index-join/query-issue838.plan
index c43cac1..29d64e7 100644
--- a/asterix-app/src/test/resources/optimizerts/results/rtree-index-join/query-issue838.plan
+++ b/asterix-app/src/test/resources/optimizerts/results/rtree-index-join/query-issue838.plan
@@ -15,9 +15,9 @@
                             -- RTREE_SEARCH  |PARTITIONED|
                               -- BROADCAST_EXCHANGE  |PARTITIONED|
                                 -- ASSIGN  |PARTITIONED|
-                                  -- ASSIGN  |PARTITIONED|
-                                    -- STREAM_PROJECT  |PARTITIONED|
+                                  -- STREAM_PROJECT  |PARTITIONED|
+                                    -- ASSIGN  |PARTITIONED|
                                       -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
                                         -- DATASOURCE_SCAN  |PARTITIONED|
                                           -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
-                                            -- EMPTY_TUPLE_SOURCE  |PARTITIONED|
\ No newline at end of file
+                                            -- EMPTY_TUPLE_SOURCE  |PARTITIONED|
diff --git a/asterix-metadata/src/main/java/edu/uci/ics/asterix/metadata/entities/Index.java b/asterix-metadata/src/main/java/edu/uci/ics/asterix/metadata/entities/Index.java
index 1e47e21..eb11d60 100644
--- a/asterix-metadata/src/main/java/edu/uci/ics/asterix/metadata/entities/Index.java
+++ b/asterix-metadata/src/main/java/edu/uci/ics/asterix/metadata/entities/Index.java
@@ -31,7 +31,7 @@
 /**
  * Metadata describing an index.
  */
-public class Index implements IMetadataEntity {
+public class Index implements IMetadataEntity, Comparable<Index> {
 
     private static final long serialVersionUID = 1L;
 
@@ -210,4 +210,42 @@
     public Object dropFromCache(MetadataCache cache) {
         return cache.dropIndex(this);
     }
+
+    @Override
+    public int compareTo(Index otherIndex) {
+        /** Gives a primary index first priority. */
+        if (isPrimaryIndex && !otherIndex.isPrimaryIndex) {
+            return -1;
+        }
+        if (!isPrimaryIndex && otherIndex.isPrimaryIndex) {
+            return 1;
+        }
+
+        /** Gives a B-Tree index the second priority. */
+        if (indexType == IndexType.BTREE && otherIndex.indexType != IndexType.BTREE) {
+            return -1;
+        }
+        if (indexType != IndexType.BTREE && otherIndex.indexType == IndexType.BTREE) {
+            return 1;
+        }
+
+        /** Gives a R-Tree index the third priority */
+        if (indexType == IndexType.RTREE && otherIndex.indexType != IndexType.RTREE) {
+            return -1;
+        }
+        if (indexType != IndexType.RTREE && otherIndex.indexType == IndexType.RTREE) {
+            return 1;
+        }
+
+        /** Finally, compares based on names. */
+        int result = indexName.compareTo(otherIndex.getIndexName());
+        if (result != 0) {
+            return result;
+        }
+        result = datasetName.compareTo(otherIndex.getDatasetName());
+        if (result != 0) {
+            return result;
+        }
+        return dataverseName.compareTo(otherIndex.getDataverseName());
+    }
 }