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 414dca3..6baf1b5 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
@@ -1,6 +1,7 @@
 package edu.uci.ics.asterix.optimizer.rules.am;
 
 import java.util.ArrayList;
+import java.util.BitSet;
 import java.util.HashSet;
 import java.util.Iterator;
 import java.util.List;
@@ -116,6 +117,9 @@
         // If we can't figure out how to integrate a certain funcExpr into the current predicate, we just bail by setting this flag.
         boolean couldntFigureOut = false;
         boolean doneWithExprs = false;
+        // TODO: For now don't consider prefix searches.
+        BitSet setLowKeys = new BitSet(numSecondaryKeys);
+        BitSet setHighKeys = new BitSet(numSecondaryKeys);
         // Go through the func exprs listed as optimizable by the chosen index, 
         // and formulate a range predicate on the secondary-index keys.
         for (Integer exprIndex : exprList) {
@@ -132,11 +136,17 @@
                         lowKeyLimits[keyPos] = highKeyLimits[keyPos] = limit;
                         lowKeyInclusive[keyPos] = highKeyInclusive[keyPos] = true;
                         lowKeyConstants[keyPos] = highKeyConstants[keyPos] = optFuncExpr.getConstantVal(0);
+                        setLowKeys.set(keyPos);
+                        setHighKeys.set(keyPos);
                     } else {
                         couldntFigureOut = true;
                     }
-                    // Mmmm, we would need an inference system here.
-                    doneWithExprs = true;
+                    // TODO: For now don't consider prefix searches.
+                    // If high and low keys are set, we exit for now.
+                    if (setLowKeys.cardinality() == numSecondaryKeys
+                            && setHighKeys.cardinality() == numSecondaryKeys) {
+                    	doneWithExprs = true;
+                    }             
                     break;
                 }
                 case HIGH_EXCLUSIVE: {
diff --git a/asterix-app/src/test/resources/optimizerts/queries/orders-composite-index-search.aql b/asterix-app/src/test/resources/optimizerts/queries/orders-composite-index-search.aql
new file mode 100644
index 0000000..d82be3c
--- /dev/null
+++ b/asterix-app/src/test/resources/optimizerts/queries/orders-composite-index-search.aql
@@ -0,0 +1,30 @@
+drop dataverse index_search if exists;
+create dataverse index_search;
+use dataverse index_search;
+
+create type OrderType as closed {
+  o_orderkey: int32, 
+  o_custkey: int32, 
+  o_orderstatus: string, 
+  o_totalprice: double, 
+  o_orderdate: string, 
+  o_orderpriority: string,
+  o_clerk: string, 
+  o_shippriority: int32, 
+  o_comment: string
+}
+
+create dataset Orders(OrderType) partitioned by key o_orderkey;
+
+create index idx_Custkey_Orderstatus on Orders(o_custkey, o_orderstatus);
+
+write output to nc1:"/tmp/index_search.adm";
+
+for $o in dataset('Orders')
+where
+  $o.o_custkey = 40 and $o.o_orderstatus = "P"
+return {  
+  "o_orderkey": $o.o_orderkey,
+  "o_custkey": $o.o_custkey,
+  "o_orderstatus": $o.o_orderstatus
+}
diff --git a/asterix-app/src/test/resources/optimizerts/results/orders-composite-index-search.plan b/asterix-app/src/test/resources/optimizerts/results/orders-composite-index-search.plan
new file mode 100644
index 0000000..2b19a64
--- /dev/null
+++ b/asterix-app/src/test/resources/optimizerts/results/orders-composite-index-search.plan
@@ -0,0 +1,16 @@
+-- SINK_WRITE  |PARTITIONED|
+  -- RANDOM_MERGE_EXCHANGE  |PARTITIONED|
+    -- STREAM_PROJECT  |PARTITIONED|
+      -- ASSIGN  |PARTITIONED|
+        -- ASSIGN  |PARTITIONED|
+          -- ONE_TO_ONE_EXCHANGE  |PARTITIONED|
+            -- BTREE_SEARCH  |PARTITIONED|
+              -- ONE_TO_ONE_EXCHANGE  |LOCAL|
+                -- STABLE_SORT [$$23(ASC)]  |LOCAL|
+                  -- 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-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 7c6d9ed..2aade27 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
@@ -123,4 +123,27 @@
         }
         throw new AlgebricksException("Could not find field " + expr + " in the schema.");
     }
+    
+    @Override
+    public int hashCode() {
+    	return indexName.hashCode() ^ datasetName.hashCode() ^ dataverseName.hashCode();
+    }
+    
+    @Override
+    public boolean equals(Object other) {
+    	if (!(other instanceof Index)) {
+    		return false;
+    	}
+    	Index otherIndex = (Index) other;
+    	if (!indexName.equals(otherIndex.getIndexName())) {
+    		return false;
+    	}
+    	if (!datasetName.equals(otherIndex.getDatasetName())) {
+    		return false;
+    	}
+    	if (!dataverseName.equals(otherIndex.getDataverseName())) {
+    		return false;
+    	}
+    	return true;
+    }
 }