diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ISearchOperationCallback.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ISearchOperationCallback.java
index b62bbcb..62d5054 100644
--- a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ISearchOperationCallback.java
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ISearchOperationCallback.java
@@ -42,4 +42,14 @@
      * @param tuple the tuple that was previously reconciled
      */
     public void cancel(ITupleReference tuple) throws HyracksDataException;
+    
+    /**
+     * This method is only called on a tuple that was reconciled on, and found after
+     * retraversing. This method allows an opportunity to do some subsequent action that was 
+     * taken in {@link #reconcile(ITupleReference))}.
+     * 
+     * @param tuple
+     *            the tuple that was previously reconciled
+     */
+    public void complete(ITupleReference tuple) throws HyracksDataException;
 }
diff --git a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/impls/NoOpOperationCallback.java b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/impls/NoOpOperationCallback.java
index 6fc8dcf..8178101 100644
--- a/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/impls/NoOpOperationCallback.java
+++ b/hyracks/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/impls/NoOpOperationCallback.java
@@ -15,6 +15,7 @@
 
 package edu.uci.ics.hyracks.storage.am.common.impls;
 
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
 import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference;
 import edu.uci.ics.hyracks.storage.am.common.api.IModificationOperationCallback;
 import edu.uci.ics.hyracks.storage.am.common.api.ISearchOperationCallback;
@@ -49,4 +50,9 @@
     public void cancel(ITupleReference tuple) {
         // Do nothing.
     }
+
+    @Override
+    public void complete(ITupleReference tuple) throws HyracksDataException {
+        // Do nothing.
+    }
 }
diff --git a/hyracks/hyracks-storage-am-lsm-btree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/btree/impls/LSMBTreePointSearchCursor.java b/hyracks/hyracks-storage-am-lsm-btree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/btree/impls/LSMBTreePointSearchCursor.java
index 0204833..5736200 100644
--- a/hyracks/hyracks-storage-am-lsm-btree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/btree/impls/LSMBTreePointSearchCursor.java
+++ b/hyracks/hyracks-storage-am-lsm-btree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/btree/impls/LSMBTreePointSearchCursor.java
@@ -91,6 +91,7 @@
 
                     // retraverse
                     memBTreeAccessor.search(rangeCursors[i], predicate);
+                    searchCallback.complete(predicate.getLowKey());
                     if (rangeCursors[i].hasNext()) {
                         rangeCursors[i].next();
                         if (((ILSMTreeTupleReference) rangeCursors[i].getTuple()).isAntimatter()) {
@@ -108,6 +109,7 @@
                 } else {
                     frameTuple = rangeCursors[i].getTuple();
                     searchCallback.reconcile(frameTuple);
+                    searchCallback.complete(frameTuple);
                     foundTuple = true;
                     return true;
                 }
diff --git a/hyracks/hyracks-storage-am-lsm-btree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/btree/impls/LSMBTreeRangeSearchCursor.java b/hyracks/hyracks-storage-am-lsm-btree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/btree/impls/LSMBTreeRangeSearchCursor.java
index 4255dbf..2923c53 100644
--- a/hyracks/hyracks-storage-am-lsm-btree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/btree/impls/LSMBTreeRangeSearchCursor.java
+++ b/hyracks/hyracks-storage-am-lsm-btree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/btree/impls/LSMBTreeRangeSearchCursor.java
@@ -101,14 +101,20 @@
                                 searchCallback.reconcile(copyTuple);
                             } else {
                                 searchCallback.reconcile(checkElement.getTuple());
+                                searchCallback.complete(checkElement.getTuple());
                             }
                             // retraverse
                             reusablePred.setLowKey(copyTuple, true);
                             memBTreeAccessor.search(rangeCursors[0], reusablePred);
-                            pushIntoPriorityQueue(inMemElement);
-                            if (cmp.compare(copyTuple, inMemElement.getTuple()) != 0) {
-                                searchCallback.cancel(copyTuple);
-                                continue;
+                            boolean isNotExhaustedCursor = pushIntoPriorityQueue(inMemElement);
+                            
+                            if (checkElement.getCursorIndex() == 0) {
+                                if (!isNotExhaustedCursor || cmp.compare(copyTuple, inMemElement.getTuple()) != 0) {
+                                    searchCallback.complete(copyTuple);
+                                    searchCallback.cancel(copyTuple);
+                                    continue;
+                                }
+                                searchCallback.complete(copyTuple);
                             }
                         } else {
                             // the in-memory cursor is exhausted
@@ -211,4 +217,4 @@
         initPriorityQueue();
         proceed = true;
     }
-}
\ No newline at end of file
+}
diff --git a/hyracks/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/btree/AbstractSearchOperationCallbackTest.java b/hyracks/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/btree/AbstractSearchOperationCallbackTest.java
index ffa7c9a..63e320d 100644
--- a/hyracks/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/btree/AbstractSearchOperationCallbackTest.java
+++ b/hyracks/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/btree/AbstractSearchOperationCallbackTest.java
@@ -172,6 +172,11 @@
                 }
             }
 
+            @Override
+            public void complete(ITupleReference tuple) throws HyracksDataException {
+
+            }
+
         }
     }
 
diff --git a/hyracks/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/common/TestOperationCallback.java b/hyracks/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/common/TestOperationCallback.java
index 04f888b..2a803d3 100644
--- a/hyracks/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/common/TestOperationCallback.java
+++ b/hyracks/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/common/TestOperationCallback.java
@@ -2,6 +2,7 @@
 
 import java.util.Random;
 
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
 import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference;
 import edu.uci.ics.hyracks.storage.am.common.api.IModificationOperationCallback;
 import edu.uci.ics.hyracks.storage.am.common.api.ISearchOperationCallback;
@@ -42,4 +43,9 @@
         // Do nothing.
     }
 
+    @Override
+    public void complete(ITupleReference tuple) throws HyracksDataException {
+        // Do nothing.
+    }
+
 }
diff --git a/hyracks/hyracks-tests/hyracks-storage-am-lsm-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsm/btree/LSMBTreeSearchOperationCallbackTest.java b/hyracks/hyracks-tests/hyracks-storage-am-lsm-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsm/btree/LSMBTreeSearchOperationCallbackTest.java
index 389c87f..41d7ae8 100644
--- a/hyracks/hyracks-tests/hyracks-storage-am-lsm-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsm/btree/LSMBTreeSearchOperationCallbackTest.java
+++ b/hyracks/hyracks-tests/hyracks-storage-am-lsm-btree-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsm/btree/LSMBTreeSearchOperationCallbackTest.java
@@ -164,10 +164,6 @@
                     condition.awaitUninterruptibly();
                     blockOnHigh = false;
                 }
-                expectedTupleToBeLockedValue++;
-                TupleUtils.createIntegerTuple(expectedTupleToBeLockedBuilder, expectedTupleToBeLocked,
-                        expectedTupleToBeLockedValue);
-
             }
 
             @Override
@@ -183,6 +179,14 @@
                 Assert.assertTrue(found);
             }
 
+            @Override
+            public void complete(ITupleReference tuple) throws HyracksDataException {
+                Assert.assertEquals(0, cmp.compare(SearchTask.this.expectedTupleToBeLocked, tuple));
+                expectedTupleToBeLockedValue++;
+                TupleUtils.createIntegerTuple(expectedTupleToBeLockedBuilder, expectedTupleToBeLocked,
+                        expectedTupleToBeLockedValue);
+            }
+
         }
     }