diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTreeRangeSearchCursor.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTreeRangeSearchCursor.java
index 758eb71..2f2eb43 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTreeRangeSearchCursor.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTreeRangeSearchCursor.java
@@ -189,6 +189,8 @@
                 frameTuple.resetByTupleIndex(frame, tupleIndex);
                 if (originalKeyCmp.compare(reconciliationTuple, frameTuple) == 0) {
                     return true;
+                } else {
+                    searchCb.cancel(reconciliationTuple);
                 }
             }
         }
diff --git a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ISearchOperationCallback.java b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ISearchOperationCallback.java
index aad109f..079adae 100644
--- a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ISearchOperationCallback.java
+++ b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ISearchOperationCallback.java
@@ -32,4 +32,13 @@
      * @param tuple the tuple that failed to proceed
      */
     public void reconcile(ITupleReference tuple);
+
+    /**
+     * This method is only called on a tuple that was reconciled on, but not found after 
+     * retraversing. This method allows an opportunity to cancel some action that was taken in 
+     * {@link #reconcile(ITupleReference))}.
+     * 
+     * @param tuple the tuple that was previously reconciled
+     */
+    public void cancel(ITupleReference tuple);
 }
diff --git a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/impls/NoOpOperationCallback.java b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/impls/NoOpOperationCallback.java
index ee36f9f..5324b10 100644
--- a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/impls/NoOpOperationCallback.java
+++ b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/impls/NoOpOperationCallback.java
@@ -44,4 +44,9 @@
     public void found(ITupleReference tuple) {
         // Do nothing.        
     }
+
+    @Override
+    public void cancel(ITupleReference tuple) {
+        // Do nothing.
+    }
 }
diff --git a/hyracks-storage-am-lsm-btree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/btree/impls/LSMBTreeRangeSearchCursor.java b/hyracks-storage-am-lsm-btree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/btree/impls/LSMBTreeRangeSearchCursor.java
index 3916ac7..7aab9df 100644
--- a/hyracks-storage-am-lsm-btree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/btree/impls/LSMBTreeRangeSearchCursor.java
+++ b/hyracks-storage-am-lsm-btree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/btree/impls/LSMBTreeRangeSearchCursor.java
@@ -111,6 +111,12 @@
             if (!pushIntoPriorityQueue(inMemElement)) {
                 return !outputPriorityQueue.isEmpty();
             }
+
+            if (pqHead.getCursorIndex() == 0) {
+                if (cmp.compare(copyTuple, inMemElement.getTuple()) != 0) {
+                    searchCallback.cancel(copyTuple);
+                }
+            }
             checkPriorityQueue();
         } else {
             searchCallback.reconcile(pqHead.getTuple());
diff --git a/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/btree/AbstractSearchOperationCallbackTest.java b/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/btree/AbstractSearchOperationCallbackTest.java
index 8094a1d..ffa7c9a 100644
--- a/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/btree/AbstractSearchOperationCallbackTest.java
+++ b/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/btree/AbstractSearchOperationCallbackTest.java
@@ -68,6 +68,7 @@
         private final ArrayTupleReference tuple;
 
         private boolean blockOnHigh;
+        private int blockingValue;
         private int expectedAfterBlock;
 
         public SearchTask() {
@@ -79,6 +80,7 @@
             this.tuple = new ArrayTupleReference();
 
             this.blockOnHigh = false;
+            this.blockingValue = -1;
             this.expectedAfterBlock = -1;
         }
 
@@ -107,7 +109,7 @@
             } finally {
                 lock.unlock();
             }
-            
+
             return true;
         }
 
@@ -120,6 +122,7 @@
             for (int i = begin; i <= end; i++) {
                 if (blockOnHigh == true && i == end) {
                     this.blockOnHigh = true;
+                    this.blockingValue = end;
                     this.expectedAfterBlock = expectedAfterBlock;
                 }
                 TupleUtils.createIntegerTuple(builder, tuple, i);
@@ -158,6 +161,17 @@
                 }
             }
 
+            @Override
+            public void cancel(ITupleReference tuple) {
+                try {
+                    TupleUtils.createIntegerTuple(builder, SearchTask.this.tuple, blockingValue);
+                    Assert.assertEquals(0, cmp.compare(tuple, SearchTask.this.tuple));
+                    TupleUtils.createIntegerTuple(builder, SearchTask.this.tuple, expectedAfterBlock);
+                } catch (HyracksDataException e) {
+                    e.printStackTrace();
+                }
+            }
+
         }
     }
 
diff --git a/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/common/TestOperationCallback.java b/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/common/TestOperationCallback.java
index 4096b45..4ec21fb 100644
--- a/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/common/TestOperationCallback.java
+++ b/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/common/TestOperationCallback.java
@@ -37,4 +37,9 @@
         // Do nothing.        
     }
 
+    @Override
+    public void cancel(ITupleReference tuple) {
+        // Do nothing.
+    }
+
 }
diff --git a/hyracks-tests/hyracks-storage-am-lsm-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsm/btree/LSMBTreeSearchOperationCallbackTest.java b/hyracks-tests/hyracks-storage-am-lsm-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsm/btree/LSMBTreeSearchOperationCallbackTest.java
index 6cf4dd2..be79257 100644
--- a/hyracks-tests/hyracks-storage-am-lsm-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsm/btree/LSMBTreeSearchOperationCallbackTest.java
+++ b/hyracks-tests/hyracks-storage-am-lsm-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsm/btree/LSMBTreeSearchOperationCallbackTest.java
@@ -170,6 +170,11 @@
                 }
             }
 
+            @Override
+            public void cancel(ITupleReference tuple) {
+                // Do nothing.
+            }
+
         }
     }