diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/api/IBTreeLeafFrame.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/api/IBTreeLeafFrame.java
index 74bf2b0..427ab9a 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/api/IBTreeLeafFrame.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/api/IBTreeLeafFrame.java
@@ -32,5 +32,5 @@
             FindTupleMode ftm, FindTupleNoExactMatchPolicy ftp) throws HyracksDataException;
     
     public int findUpsertTupleIndex(ITupleReference tuple) throws TreeIndexException;
-    public ITupleReference getUpsertBeforeTuple(ITupleReference tuple, int targetTupleIndex) throws TreeIndexException;
+    public ITupleReference getBeforeTuple(ITupleReference tuple, int targetTupleIndex) throws TreeIndexException;
 }
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/BTreeFieldPrefixNSMLeafFrame.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/BTreeFieldPrefixNSMLeafFrame.java
index 5d3dd65..87c3b7f 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/BTreeFieldPrefixNSMLeafFrame.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/BTreeFieldPrefixNSMLeafFrame.java
@@ -380,7 +380,7 @@
     }
 
     @Override
-    public ITupleReference getUpsertBeforeTuple(ITupleReference tuple, int targetTupleIndex) throws TreeIndexException {
+    public ITupleReference getBeforeTuple(ITupleReference tuple, int targetTupleIndex) throws TreeIndexException {
         int tupleIndex = slotManager.decodeSecondSlotField(targetTupleIndex);
         // Examine the tuple index to determine whether it is valid or not.
         if (tupleIndex != slotManager.getGreatestKeyIndicator()) {
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/BTreeNSMLeafFrame.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/BTreeNSMLeafFrame.java
index 0437a5d..6935ab0 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/BTreeNSMLeafFrame.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/frames/BTreeNSMLeafFrame.java
@@ -86,13 +86,13 @@
     }
 
     @Override
-    public ITupleReference getUpsertBeforeTuple(ITupleReference tuple, int targetTupleIndex) throws TreeIndexException {
+    public ITupleReference getBeforeTuple(ITupleReference tuple, int targetTupleIndex) throws TreeIndexException {
         // Examine the tuple index to determine whether it is valid or not.
         if (targetTupleIndex != slotManager.getGreatestKeyIndicator()) {
-            // We need to check the key to determine whether it's an insert or an update.
+            // We need to check the key to determine whether it's an insert or an update/delete
             frameTuple.resetByTupleIndex(this, targetTupleIndex);
             if (cmp.compare(tuple, frameTuple) == 0) {
-                // The keys match, it's an update.
+                // The keys match, it's an update/delete
                 return frameTuple;
             }
         }
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTree.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTree.java
index 0e48e04..000cd4d 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTree.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTree.java
@@ -124,6 +124,7 @@
             cursor.setCurrentPageId(currentPageId);
             cursor.setMaxPageId(maxPageId);
             ctx.cursorInitialState.setPage(page);
+            ctx.cursorInitialState.setSearchOperationCallback(ctx.searchCallback);
             cursor.open(ctx.cursorInitialState, diskOrderScanPred);
         } catch (Exception e) {
             page.releaseReadLatch();
@@ -254,8 +255,8 @@
             unsetSmPages(ctx);
             repeatOp = false;
         }
-        
-        if(ctx.opRestarts >= MAX_RESTARTS) {
+
+        if (ctx.opRestarts >= MAX_RESTARTS) {
             throw new BTreeException("Operation exceeded the maximum number of restarts");
         }
     }
@@ -349,7 +350,7 @@
 
             // Perform an update (delete + insert) if the updateTupleIndex != -1
             if (updateTupleIndex != -1) {
-                ITupleReference beforeTuple = ctx.leafFrame.getUpsertBeforeTuple(tuple, updateTupleIndex);
+                ITupleReference beforeTuple = ctx.leafFrame.getBeforeTuple(tuple, updateTupleIndex);
                 ctx.modificationCallback.found(beforeTuple);
                 ctx.leafFrame.delete(tuple, updateTupleIndex);
             } else {
@@ -386,7 +387,7 @@
     private boolean updateLeaf(ITupleReference tuple, int oldTupleIndex, int pageId, BTreeOpContext ctx)
             throws Exception {
         FrameOpSpaceStatus spaceStatus = ctx.leafFrame.hasSpaceUpdate(tuple, oldTupleIndex);
-        ITupleReference beforeTuple = ctx.leafFrame.getUpsertBeforeTuple(tuple, oldTupleIndex);
+        ITupleReference beforeTuple = ctx.leafFrame.getBeforeTuple(tuple, oldTupleIndex);
         boolean restartOp = false;
         switch (spaceStatus) {
             case SUFFICIENT_INPLACE_SPACE: {
@@ -422,7 +423,7 @@
     private boolean upsertLeaf(ITupleReference tuple, int targetTupleIndex, int pageId, BTreeOpContext ctx)
             throws Exception {
         boolean restartOp = false;
-        ITupleReference beforeTuple = ctx.leafFrame.getUpsertBeforeTuple(tuple, targetTupleIndex);
+        ITupleReference beforeTuple = ctx.leafFrame.getBeforeTuple(tuple, targetTupleIndex);
         if (beforeTuple == null) {
             restartOp = insertLeaf(tuple, targetTupleIndex, pageId, ctx);
         } else {
@@ -494,7 +495,7 @@
             throw new BTreeNonExistentKeyException("Trying to delete a tuple with a nonexistent key in leaf node.");
         }
         int tupleIndex = ctx.leafFrame.findDeleteTupleIndex(tuple);
-        ITupleReference beforeTuple = ctx.leafFrame.getUpsertBeforeTuple(tuple, tupleIndex);
+        ITupleReference beforeTuple = ctx.leafFrame.getBeforeTuple(tuple, tupleIndex);
         ctx.modificationCallback.found(beforeTuple);
         ctx.leafFrame.delete(tuple, tupleIndex);
         return false;
@@ -667,6 +668,7 @@
                         break;
                     }
                     case SEARCH: {
+                        ctx.cursorInitialState.setSearchOperationCallback(ctx.searchCallback);
                         ctx.cursorInitialState.setPage(node);
                         ctx.cursor.open(ctx.cursorInitialState, ctx.pred);
                         break;
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTreeCursorInitialState.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTreeCursorInitialState.java
index 855f9e6..c7f4c0c 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTreeCursorInitialState.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTreeCursorInitialState.java
@@ -1,13 +1,16 @@
 package edu.uci.ics.hyracks.storage.am.btree.impls;
 
 import edu.uci.ics.hyracks.storage.am.common.api.ICursorInitialState;
+import edu.uci.ics.hyracks.storage.am.common.api.ISearchOperationCallback;
 import edu.uci.ics.hyracks.storage.common.buffercache.ICachedPage;
 
 public class BTreeCursorInitialState implements ICursorInitialState {
 
     private ICachedPage page;
 
-    public BTreeCursorInitialState(ICachedPage page) {
+    private ISearchOperationCallback searchCallback;
+
+    public BTreeCursorInitialState(ICachedPage page, ISearchOperationCallback searchCallback) {
         this.page = page;
     }
 
@@ -18,4 +21,14 @@
     public void setPage(ICachedPage page) {
         this.page = page;
     }
+
+    @Override
+    public ISearchOperationCallback getSearchOperationCallback() {
+        return searchCallback;
+    }
+
+    @Override
+    public void setSearchOperationCallback(ISearchOperationCallback searchCallback) {
+        this.searchCallback = searchCallback;
+    }
 }
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTreeOpContext.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTreeOpContext.java
index d19b083..98ad4a2 100644
--- a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTreeOpContext.java
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/BTreeOpContext.java
@@ -85,7 +85,7 @@
     public void reset(IndexOp newOp) {
         if (newOp == IndexOp.SEARCH || newOp == IndexOp.DISKORDERSCAN) {
             if (cursorInitialState == null) {
-                cursorInitialState = new BTreeCursorInitialState(null);
+                cursorInitialState = new BTreeCursorInitialState(null, searchCallback);
             }
         } else {
             // Insert, delete, update or upsert operation.
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 8bf4db3..8d475e3 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
@@ -19,6 +19,7 @@
 import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference;
 import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeLeafFrame;
 import edu.uci.ics.hyracks.storage.am.common.api.ICursorInitialState;
+import edu.uci.ics.hyracks.storage.am.common.api.ISearchOperationCallback;
 import edu.uci.ics.hyracks.storage.am.common.api.ISearchPredicate;
 import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexCursor;
 import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexTupleReference;
@@ -55,6 +56,8 @@
     private ITupleReference lowKey;
     private ITupleReference highKey;
 
+    private ISearchOperationCallback searchCallback;
+
     public BTreeRangeSearchCursor(IBTreeLeafFrame frame, boolean exclusiveLatchNodes) {
         this.frame = frame;
         this.frameTuple = frame.createTupleReference();
@@ -125,7 +128,7 @@
             return false;
         }
     }
-    
+
     @Override
     public void next() throws HyracksDataException {
         tupleIndex += tupleIndexInc;
@@ -154,8 +157,7 @@
         if (pred.highKeyInclusive) {
             if (index < 0) {
                 index = frame.getTupleCount() - 1;
-            }
-            else {
+            } else {
                 index--;
             }
         }
@@ -173,8 +175,8 @@
             }
             bufferCache.unpin(page);
         }
-
-        page = ((BTreeCursorInitialState) initialState).getPage();
+        searchCallback = initialState.getSearchOperationCallback();
+        page = initialState.getPage();
         frame.setPage(page);
 
         pred = (RangePredicate) searchPred;
@@ -198,7 +200,7 @@
         } else {
             highKeyFtp = FindTupleNoExactMatchPolicy.LOWER_KEY;
         }
-        
+
         tupleIndex = getLowKeyIndex();
         stopTupleIndex = getHighKeyIndex();
         tupleIndexInc = 1;
diff --git a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ICursorInitialState.java b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ICursorInitialState.java
index 60e8ba9..04e1539 100644
--- a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ICursorInitialState.java
+++ b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/api/ICursorInitialState.java
@@ -18,6 +18,11 @@
 import edu.uci.ics.hyracks.storage.common.buffercache.ICachedPage;
 
 public interface ICursorInitialState {
-	public ICachedPage getPage();
-	public void setPage(ICachedPage page);
+    public ICachedPage getPage();
+
+    public void setPage(ICachedPage page);
+
+    public ISearchOperationCallback getSearchOperationCallback();
+
+    public void setSearchOperationCallback(ISearchOperationCallback searchCallback);
 }
diff --git a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/impls/TreeDiskOrderScanCursor.java b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/impls/TreeDiskOrderScanCursor.java
index ea4c105..8a094ba 100644
--- a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/impls/TreeDiskOrderScanCursor.java
+++ b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/impls/TreeDiskOrderScanCursor.java
@@ -17,6 +17,7 @@
 
 import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
 import edu.uci.ics.hyracks.storage.am.common.api.ICursorInitialState;
+import edu.uci.ics.hyracks.storage.am.common.api.ISearchOperationCallback;
 import edu.uci.ics.hyracks.storage.am.common.api.ISearchPredicate;
 import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexCursor;
 import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexFrame;
@@ -27,128 +28,126 @@
 
 public class TreeDiskOrderScanCursor implements ITreeIndexCursor {
 
-	private int tupleIndex = 0;
-	private int fileId = -1;
-	private int currentPageId = -1;
-	private int maxPageId = -1;
-	private ICachedPage page = null;	
-	private IBufferCache bufferCache = null;
-	
-	private final ITreeIndexFrame frame;
-	private final ITreeIndexTupleReference frameTuple;
-	
-	public TreeDiskOrderScanCursor(ITreeIndexFrame frame) {
-		this.frame = frame;		
-		this.frameTuple = frame.createTupleReference();
-	}
+    private int tupleIndex = 0;
+    private int fileId = -1;
+    private int currentPageId = -1;
+    private int maxPageId = -1;
+    private ICachedPage page = null;
+    private IBufferCache bufferCache = null;
+    private ISearchOperationCallback searchCallback;
 
-	@Override
-	public void close() throws HyracksDataException {
-		page.releaseReadLatch();
-		bufferCache.unpin(page);
-		page = null;
-	}
+    private final ITreeIndexFrame frame;
+    private final ITreeIndexTupleReference frameTuple;
 
-	@Override
-	public ITreeIndexTupleReference getTuple() {
-		return frameTuple;
-	}
+    public TreeDiskOrderScanCursor(ITreeIndexFrame frame) {
+        this.frame = frame;
+        this.frameTuple = frame.createTupleReference();
+    }
 
-	@Override
-	public ICachedPage getPage() {
-		return page;
-	}
+    @Override
+    public void close() throws HyracksDataException {
+        page.releaseReadLatch();
+        bufferCache.unpin(page);
+        page = null;
+    }
 
-	private boolean positionToNextLeaf(boolean skipCurrent)
-			throws HyracksDataException {
-		while ((frame.getLevel() != 0 || skipCurrent || frame.getTupleCount() == 0) && (currentPageId <= maxPageId)) {
-			currentPageId++;
+    @Override
+    public ITreeIndexTupleReference getTuple() {
+        return frameTuple;
+    }
 
-			page.releaseReadLatch();
+    @Override
+    public ICachedPage getPage() {
+        return page;
+    }
+
+    private boolean positionToNextLeaf(boolean skipCurrent) throws HyracksDataException {
+        while ((frame.getLevel() != 0 || skipCurrent || frame.getTupleCount() == 0) && (currentPageId <= maxPageId)) {
+            currentPageId++;
+
+            page.releaseReadLatch();
             bufferCache.unpin(page);
-			
-			ICachedPage nextPage = bufferCache.pin(
-					BufferedFileHandle.getDiskPageId(fileId, currentPageId),
-					false);
-			nextPage.acquireReadLatch();
 
-			page = nextPage;
-			frame.setPage(page);
-			tupleIndex = 0;
-			skipCurrent = false;
-		}
-		if (currentPageId <= maxPageId) {
-			return true;
-		} else {
-			return false;
-		}
-	}
+            ICachedPage nextPage = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, currentPageId), false);
+            nextPage.acquireReadLatch();
 
-	@Override
-	public boolean hasNext() throws HyracksDataException {		
-		if (currentPageId > maxPageId) {
-			return false;
-		}
-		if (tupleIndex >= frame.getTupleCount()) {
-			boolean nextLeafExists = positionToNextLeaf(true);
-			if (nextLeafExists) {
-				frameTuple.resetByTupleIndex(frame, tupleIndex);
-				return true;
-			} else {
-				return false;
-			}
-		}		
-		frameTuple.resetByTupleIndex(frame, tupleIndex);		
-		return true;
-	}
+            page = nextPage;
+            frame.setPage(page);
+            tupleIndex = 0;
+            skipCurrent = false;
+        }
+        if (currentPageId <= maxPageId) {
+            return true;
+        } else {
+            return false;
+        }
+    }
 
-	@Override
-	public void next() throws HyracksDataException {
-		tupleIndex++;
-	}
+    @Override
+    public boolean hasNext() throws HyracksDataException {
+        if (currentPageId > maxPageId) {
+            return false;
+        }
+        if (tupleIndex >= frame.getTupleCount()) {
+            boolean nextLeafExists = positionToNextLeaf(true);
+            if (nextLeafExists) {
+                frameTuple.resetByTupleIndex(frame, tupleIndex);
+                return true;
+            } else {
+                return false;
+            }
+        }
+        frameTuple.resetByTupleIndex(frame, tupleIndex);
+        return true;
+    }
 
-	@Override
-	public void open(ICursorInitialState initialState,
-			ISearchPredicate searchPred) throws HyracksDataException {
-		// in case open is called multiple times without closing
-		if (page != null) {
-			page.releaseReadLatch();
-			bufferCache.unpin(page);
-		}
-		page = initialState.getPage();
-		tupleIndex = 0;		
-		frame.setPage(page);
-		positionToNextLeaf(false);
-	}
+    @Override
+    public void next() throws HyracksDataException {
+        tupleIndex++;
+    }
 
-	@Override
-	public void reset() {
-		tupleIndex = 0;
-		currentPageId = -1;
-		maxPageId = -1;
-		page = null;
-	}
+    @Override
+    public void open(ICursorInitialState initialState, ISearchPredicate searchPred) throws HyracksDataException {
+        // in case open is called multiple times without closing
+        if (page != null) {
+            page.releaseReadLatch();
+            bufferCache.unpin(page);
+        }
+        searchCallback = initialState.getSearchOperationCallback();
+        page = initialState.getPage();
+        tupleIndex = 0;
+        frame.setPage(page);
+        positionToNextLeaf(false);
+    }
 
-	@Override
-	public void setBufferCache(IBufferCache bufferCache) {
-		this.bufferCache = bufferCache;
-	}
+    @Override
+    public void reset() {
+        tupleIndex = 0;
+        currentPageId = -1;
+        maxPageId = -1;
+        page = null;
+    }
 
-	@Override
-	public void setFileId(int fileId) {
-		this.fileId = fileId;
-	}
+    @Override
+    public void setBufferCache(IBufferCache bufferCache) {
+        this.bufferCache = bufferCache;
+    }
 
-	public void setCurrentPageId(int currentPageId) {
-		this.currentPageId = currentPageId;
-	}
+    @Override
+    public void setFileId(int fileId) {
+        this.fileId = fileId;
+    }
 
-	public void setMaxPageId(int maxPageId) {
-		this.maxPageId = maxPageId;
-	}
+    public void setCurrentPageId(int currentPageId) {
+        this.currentPageId = currentPageId;
+    }
 
-	@Override
-	public boolean exclusiveLatchNodes() {
-		return false;
-	}
+    public void setMaxPageId(int maxPageId) {
+        this.maxPageId = maxPageId;
+    }
+
+    @Override
+    public boolean exclusiveLatchNodes() {
+        return false;
+    }
 }
diff --git a/hyracks-storage-am-lsm-btree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/btree/impls/LSMBTree.java b/hyracks-storage-am-lsm-btree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/btree/impls/LSMBTree.java
index 2f253e9..f19457b 100644
--- a/hyracks-storage-am-lsm-btree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/btree/impls/LSMBTree.java
+++ b/hyracks-storage-am-lsm-btree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/btree/impls/LSMBTree.java
@@ -258,7 +258,7 @@
         int numDiskBTrees = diskComponents.size();
         int numBTrees = (includeMemComponent) ? numDiskBTrees + 1 : numDiskBTrees;
         LSMBTreeCursorInitialState initialState = new LSMBTreeCursorInitialState(numBTrees, insertLeafFrameFactory,
-                ctx.cmp, includeMemComponent, searcherRefCount, lsmHarness);
+                ctx.cmp, includeMemComponent, searcherRefCount, lsmHarness, null);
         lsmTreeCursor.open(initialState, pred);
 
         int cursorIx;
diff --git a/hyracks-storage-am-lsm-btree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/btree/impls/LSMBTreeCursorInitialState.java b/hyracks-storage-am-lsm-btree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/btree/impls/LSMBTreeCursorInitialState.java
index e866326..96b4deb 100644
--- a/hyracks-storage-am-lsm-btree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/btree/impls/LSMBTreeCursorInitialState.java
+++ b/hyracks-storage-am-lsm-btree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/btree/impls/LSMBTreeCursorInitialState.java
@@ -18,6 +18,7 @@
 import java.util.concurrent.atomic.AtomicInteger;
 
 import edu.uci.ics.hyracks.storage.am.common.api.ICursorInitialState;
+import edu.uci.ics.hyracks.storage.am.common.api.ISearchOperationCallback;
 import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexFrameFactory;
 import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
 import edu.uci.ics.hyracks.storage.am.lsm.common.impls.LSMHarness;
@@ -25,53 +26,67 @@
 
 public class LSMBTreeCursorInitialState implements ICursorInitialState {
 
-	private final int numBTrees;
-	private final ITreeIndexFrameFactory leafFrameFactory;
-	private final MultiComparator cmp;
-	private final boolean includeMemComponent;
-	private final AtomicInteger searcherfRefCount;
-	private final LSMHarness lsmHarness;
-	
+    private final int numBTrees;
+    private final ITreeIndexFrameFactory leafFrameFactory;
+    private final MultiComparator cmp;
+    private final boolean includeMemComponent;
+    private final AtomicInteger searcherfRefCount;
+    private final LSMHarness lsmHarness;
+
+    private ISearchOperationCallback searchCallback;
+
     public LSMBTreeCursorInitialState(int numBTrees, ITreeIndexFrameFactory leafFrameFactory, MultiComparator cmp,
-            boolean includeMemComponent, AtomicInteger searcherfRefCount, LSMHarness lsmHarness) {
+            boolean includeMemComponent, AtomicInteger searcherfRefCount, LSMHarness lsmHarness,
+            ISearchOperationCallback searchCallback) {
         this.numBTrees = numBTrees;
         this.leafFrameFactory = leafFrameFactory;
         this.cmp = cmp;
         this.includeMemComponent = includeMemComponent;
         this.searcherfRefCount = searcherfRefCount;
         this.lsmHarness = lsmHarness;
+        this.searchCallback = searchCallback;
     }
-	
-	public int getNumBTrees() {
-		return numBTrees;
-	}
 
-	public ITreeIndexFrameFactory getLeafFrameFactory() {
-		return leafFrameFactory;
-	}
+    public int getNumBTrees() {
+        return numBTrees;
+    }
 
-	public MultiComparator getCmp() {
-		return cmp;
-	}
+    public ITreeIndexFrameFactory getLeafFrameFactory() {
+        return leafFrameFactory;
+    }
 
-	@Override
-	public ICachedPage getPage() {
-		return null;
-	}
+    public MultiComparator getCmp() {
+        return cmp;
+    }
 
-	@Override
-	public void setPage(ICachedPage page) {
-	}
+    @Override
+    public ICachedPage getPage() {
+        return null;
+    }
 
-	public AtomicInteger getSearcherRefCount() {
-	    return searcherfRefCount;
-	}
-	
-	public boolean getIncludeMemComponent() {
-	    return includeMemComponent;
-	}
-	
-	public LSMHarness getLSMHarness() {
-	    return lsmHarness;
-	}
+    @Override
+    public void setPage(ICachedPage page) {
+    }
+
+    public AtomicInteger getSearcherRefCount() {
+        return searcherfRefCount;
+    }
+
+    public boolean getIncludeMemComponent() {
+        return includeMemComponent;
+    }
+
+    public LSMHarness getLSMHarness() {
+        return lsmHarness;
+    }
+
+    @Override
+    public ISearchOperationCallback getSearchOperationCallback() {
+        return searchCallback;
+    }
+
+    @Override
+    public void setSearchOperationCallback(ISearchOperationCallback searchCallback) {
+        this.searchCallback = searchCallback;
+    }
 }
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 24ba4eb..ef0a9cd 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
@@ -24,6 +24,7 @@
 import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeLeafFrame;
 import edu.uci.ics.hyracks.storage.am.btree.impls.BTreeRangeSearchCursor;
 import edu.uci.ics.hyracks.storage.am.common.api.ICursorInitialState;
+import edu.uci.ics.hyracks.storage.am.common.api.ISearchOperationCallback;
 import edu.uci.ics.hyracks.storage.am.common.api.ISearchPredicate;
 import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexCursor;
 import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
@@ -43,14 +44,14 @@
     private boolean includeMemComponent;
     private AtomicInteger searcherfRefCount;
     private LSMHarness lsmHarness;
+    private ISearchOperationCallback searchCallback;
 
     public LSMBTreeRangeSearchCursor() {
         outputElement = null;
         needPush = false;
     }
 
-    public void initPriorityQueue()
-            throws HyracksDataException {
+    public void initPriorityQueue() throws HyracksDataException {
         int pqInitSize = (rangeCursors.length > 0) ? rangeCursors.length : 1;
         outputPriorityQueue = new PriorityQueue<PriorityQueueElement>(pqInitSize, pqCmp);
         for (int i = 0; i < rangeCursors.length; i++) {
@@ -92,6 +93,7 @@
     @Override
     public void open(ICursorInitialState initialState, ISearchPredicate searchPred) throws HyracksDataException {
         LSMBTreeCursorInitialState lsmInitialState = (LSMBTreeCursorInitialState) initialState;
+        searchCallback = lsmInitialState.getSearchOperationCallback();
         cmp = lsmInitialState.getCmp();
         int numBTrees = lsmInitialState.getNumBTrees();
         rangeCursors = new BTreeRangeSearchCursor[numBTrees];
@@ -104,7 +106,7 @@
         lsmHarness = lsmInitialState.getLSMHarness();
         setPriorityQueueComparator();
     }
-    
+
     private void setPriorityQueueComparator() {
         if (pqCmp == null || cmp != pqCmp.getMultiComparator()) {
             pqCmp = new PriorityQueueComparator(cmp);
@@ -129,7 +131,7 @@
             lsmHarness.closeSearchCursor(searcherfRefCount, includeMemComponent);
         }
     }
-    
+
     @Override
     public void setBufferCache(IBufferCache bufferCache) {
         // do nothing
@@ -209,7 +211,7 @@
     public boolean exclusiveLatchNodes() {
         return false;
     }
-    
+
     public class PriorityQueueComparator implements Comparator<PriorityQueueElement> {
 
         private final MultiComparator cmp;
@@ -235,11 +237,11 @@
             return cmp;
         }
     }
-    
+
     public class PriorityQueueElement {
         private ITupleReference tuple;
         private int cursorIndex;
-        
+
         public PriorityQueueElement(ITupleReference tuple, int cursorIndex) {
             reset(tuple, cursorIndex);
         }
@@ -251,7 +253,7 @@
         public int getCursorIndex() {
             return cursorIndex;
         }
-        
+
         public void reset(ITupleReference tuple, int cursorIndex) {
             this.tuple = tuple;
             this.cursorIndex = cursorIndex;
diff --git a/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/LSMRTree.java b/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/LSMRTree.java
index 2bea518..2f9f954 100644
--- a/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/LSMRTree.java
+++ b/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/LSMRTree.java
@@ -387,7 +387,7 @@
         LSMRTreeSearchCursor lsmRTreeCursor = (LSMRTreeSearchCursor) cursor;
         LSMRTreeCursorInitialState initialState = new LSMRTreeCursorInitialState(numTrees, rtreeLeafFrameFactory,
                 rtreeInteriorFrameFactory, btreeLeafFrameFactory, ctx.getBTreeMultiComparator(), rTreeAccessors,
-                bTreeAccessors, searcherRefCount, includeMemComponent, lsmHarness);
+                bTreeAccessors, searcherRefCount, includeMemComponent, lsmHarness, ctx.searchCallback);
         lsmRTreeCursor.open(initialState, pred);
     }
 
@@ -564,7 +564,7 @@
                         .getMetaDataFrameFactory().createFrame(), 8, (BTree.BTreeAccessor) memComponent.getBTree()
                         .createAccessor(NoOpOperationCallback.INSTANCE, NoOpOperationCallback.INSTANCE),
                 btreeLeafFrameFactory, btreeInteriorFrameFactory, memFreePageManager.getMetaDataFrameFactory()
-                        .createFrame(), rtreeCmpFactories, btreeCmpFactories);
+                        .createFrame(), rtreeCmpFactories, btreeCmpFactories, null, null);
     }
 
     @Override
diff --git a/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/LSMRTreeCursorInitialState.java b/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/LSMRTreeCursorInitialState.java
index d55ffdb..2d1f744 100644
--- a/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/LSMRTreeCursorInitialState.java
+++ b/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/LSMRTreeCursorInitialState.java
@@ -18,6 +18,7 @@
 import java.util.concurrent.atomic.AtomicInteger;
 
 import edu.uci.ics.hyracks.storage.am.common.api.ICursorInitialState;
+import edu.uci.ics.hyracks.storage.am.common.api.ISearchOperationCallback;
 import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexAccessor;
 import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexFrameFactory;
 import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
@@ -37,10 +38,13 @@
     private final boolean includeMemRTree;
     private final LSMHarness lsmHarness;
 
+    private ISearchOperationCallback searchCallback;
+
     public LSMRTreeCursorInitialState(int numberOfTrees, ITreeIndexFrameFactory rtreeLeafFrameFactory,
             ITreeIndexFrameFactory rtreeInteriorFrameFactory, ITreeIndexFrameFactory btreeLeafFrameFactory,
             MultiComparator btreeCmp, ITreeIndexAccessor[] rTreeAccessors, ITreeIndexAccessor[] bTreeAccessors,
-            AtomicInteger searcherRefCount, boolean includeMemRTree, LSMHarness lsmHarness) {
+            AtomicInteger searcherRefCount, boolean includeMemRTree, LSMHarness lsmHarness,
+            ISearchOperationCallback searchCallback) {
         this.numberOfTrees = numberOfTrees;
         this.rtreeLeafFrameFactory = rtreeLeafFrameFactory;
         this.rtreeInteriorFrameFactory = rtreeInteriorFrameFactory;
@@ -51,6 +55,7 @@
         this.searcherRefCount = searcherRefCount;
         this.includeMemRTree = includeMemRTree;
         this.lsmHarness = lsmHarness;
+        this.searchCallback = searchCallback;
     }
 
     public int getNumberOfTrees() {
@@ -102,4 +107,14 @@
         return lsmHarness;
     }
 
+    @Override
+    public ISearchOperationCallback getSearchOperationCallback() {
+        return searchCallback;
+    }
+
+    @Override
+    public void setSearchOperationCallback(ISearchOperationCallback searchCallback) {
+        this.searchCallback = searchCallback;
+    }
+
 }
\ No newline at end of file
diff --git a/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/LSMRTreeOpContext.java b/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/LSMRTreeOpContext.java
index 8cead2a..ef48ac9 100644
--- a/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/LSMRTreeOpContext.java
+++ b/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/LSMRTreeOpContext.java
@@ -19,6 +19,8 @@
 import edu.uci.ics.hyracks.storage.am.btree.impls.BTree;
 import edu.uci.ics.hyracks.storage.am.btree.impls.BTreeOpContext;
 import edu.uci.ics.hyracks.storage.am.common.api.IIndexOpContext;
+import edu.uci.ics.hyracks.storage.am.common.api.IModificationOperationCallback;
+import edu.uci.ics.hyracks.storage.am.common.api.ISearchOperationCallback;
 import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexFrameFactory;
 import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexMetaDataFrame;
 import edu.uci.ics.hyracks.storage.am.common.impls.NoOpOperationCallback;
@@ -36,16 +38,21 @@
     public final RTree.RTreeAccessor memRTreeAccessor;
     public final BTree.BTreeAccessor memBTreeAccessor;
     private IndexOp op;
+    public final IModificationOperationCallback modificationCallback;
+    public final ISearchOperationCallback searchCallback;
 
     public LSMRTreeOpContext(RTree.RTreeAccessor memRtreeAccessor, IRTreeLeafFrame rtreeLeafFrame,
             IRTreeInteriorFrame rtreeInteriorFrame, ITreeIndexMetaDataFrame rtreeMetaFrame, int rTreeHeightHint,
             BTree.BTreeAccessor memBtreeAccessor, ITreeIndexFrameFactory btreeLeafFrameFactory,
             ITreeIndexFrameFactory btreeInteriorFrameFactory, ITreeIndexMetaDataFrame btreeMetaFrame,
-            IBinaryComparatorFactory[] rtreeCmpFactories, IBinaryComparatorFactory[] btreeCmpFactories) {
+            IBinaryComparatorFactory[] rtreeCmpFactories, IBinaryComparatorFactory[] btreeCmpFactories,
+            IModificationOperationCallback modificationCallback, ISearchOperationCallback searchCallback) {
         this.memRTreeAccessor = memRtreeAccessor;
         this.memBTreeAccessor = memBtreeAccessor;
+        this.modificationCallback = modificationCallback;
+        this.searchCallback = searchCallback;
         this.rtreeOpContext = new RTreeOpContext(rtreeLeafFrame, rtreeInteriorFrame, rtreeMetaFrame, rtreeCmpFactories,
-                rTreeHeightHint);
+                rTreeHeightHint, NoOpOperationCallback.INSTANCE, NoOpOperationCallback.INSTANCE);
         this.btreeOpContext = new BTreeOpContext(btreeLeafFrameFactory, btreeInteriorFrameFactory, btreeMetaFrame,
                 btreeCmpFactories, NoOpOperationCallback.INSTANCE, NoOpOperationCallback.INSTANCE);
     }
diff --git a/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/LSMRTreeSearchCursor.java b/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/LSMRTreeSearchCursor.java
index 7690909..6e77eaf 100644
--- a/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/LSMRTreeSearchCursor.java
+++ b/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/LSMRTreeSearchCursor.java
@@ -23,6 +23,7 @@
 import edu.uci.ics.hyracks.storage.am.btree.impls.BTreeRangeSearchCursor;
 import edu.uci.ics.hyracks.storage.am.btree.impls.RangePredicate;
 import edu.uci.ics.hyracks.storage.am.common.api.ICursorInitialState;
+import edu.uci.ics.hyracks.storage.am.common.api.ISearchOperationCallback;
 import edu.uci.ics.hyracks.storage.am.common.api.ISearchPredicate;
 import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexAccessor;
 import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexCursor;
@@ -52,6 +53,7 @@
     private boolean includeMemRTree;
     private LSMHarness lsmHarness;
     private boolean foundNext = false;
+    private ISearchOperationCallback searchCallback;
 
     public LSMRTreeSearchCursor() {
         currentCursror = 0;
@@ -128,6 +130,7 @@
     @Override
     public void open(ICursorInitialState initialState, ISearchPredicate searchPred) throws HyracksDataException {
         LSMRTreeCursorInitialState lsmInitialState = (LSMRTreeCursorInitialState) initialState;
+        searchCallback = lsmInitialState.getSearchOperationCallback();
         btreeCmp = lsmInitialState.getBTreeCmp();
         searcherRefCount = lsmInitialState.getSearcherRefCount();
         includeMemRTree = lsmInitialState.getIncludeMemRTree();
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/api/IRTreeLeafFrame.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/api/IRTreeLeafFrame.java
index 3005785..858a40d 100644
--- a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/api/IRTreeLeafFrame.java
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/api/IRTreeLeafFrame.java
@@ -20,8 +20,9 @@
 
 public interface IRTreeLeafFrame extends IRTreeFrame {
 
-	public int findTupleIndex(ITupleReference tuple, MultiComparator cmp);
+    public int findTupleIndex(ITupleReference tuple, MultiComparator cmp);
 
-	public boolean intersect(ITupleReference tuple, int tupleIndex,
-			MultiComparator cmp);
+    public boolean intersect(ITupleReference tuple, int tupleIndex, MultiComparator cmp);
+
+    public ITupleReference getBeforeTuple(ITupleReference tuple, int targetTupleIndex, MultiComparator cmp);
 }
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/RTreeNSMLeafFrame.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/RTreeNSMLeafFrame.java
index f1d71ff..3c6701e 100644
--- a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/RTreeNSMLeafFrame.java
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/frames/RTreeNSMLeafFrame.java
@@ -96,4 +96,19 @@
     public int getFieldCount() {
         return frameTuple.getFieldCount();
     }
+
+    public ITupleReference getBeforeTuple(ITupleReference tuple, int targetTupleIndex, MultiComparator cmp) {
+        // Examine the tuple index to determine whether it is valid or not.
+        if (targetTupleIndex != slotManager.getGreatestKeyIndicator()) {
+            // We need to check the key to determine whether it's an insert or an update.
+            frameTuple.resetByTupleIndex(this, targetTupleIndex);
+            if (cmp.compare(tuple, frameTuple) == 0) {
+                // The keys match, it's an update.
+                return frameTuple;
+            }
+        }
+        // Either the tuple index is a special indicator, or the keys don't match.
+        // In those cases, we are definitely dealing with an insert.
+        return null;
+    }
 }
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTree.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTree.java
index 03091b0..d69de4b 100644
--- a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTree.java
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTree.java
@@ -212,10 +212,11 @@
         return bufferCache;
     }
 
-    private RTreeOpContext createOpContext() {
+    private RTreeOpContext createOpContext(IModificationOperationCallback modificationCallback,
+            ISearchOperationCallback searchCallback) {
         return new RTreeOpContext((IRTreeLeafFrame) leafFrameFactory.createFrame(),
                 (IRTreeInteriorFrame) interiorFrameFactory.createFrame(), freePageManager.getMetaDataFrameFactory()
-                        .createFrame(), cmpFactories, 8);
+                        .createFrame(), cmpFactories, 8, modificationCallback, searchCallback);
     }
 
     private void insert(ITupleReference tuple, IIndexOpContext ictx) throws HyracksDataException, TreeIndexException {
@@ -225,6 +226,7 @@
         ctx.splitKey.reset();
         ctx.splitKey.getLeftTuple().setFieldCount(cmpFactories.length);
         ctx.splitKey.getRightTuple().setFieldCount(cmpFactories.length);
+        ctx.modificationCallback.commence(tuple);
 
         int maxFieldPos = cmpFactories.length / 2;
         for (int i = 0; i < maxFieldPos; i++) {
@@ -407,6 +409,7 @@
                     if (!isLeaf) {
                         ctx.interiorFrame.insert(tuple, -1);
                     } else {
+                        ctx.modificationCallback.found(null);
                         ctx.leafFrame.insert(tuple, -1);
                     }
                     succeeded = true;
@@ -431,6 +434,7 @@
                         ctx.interiorFrame.insert(tuple, -1);
                     } else {
                         ctx.leafFrame.compact();
+                        ctx.modificationCallback.found(null);
                         ctx.leafFrame.insert(tuple, -1);
                     }
                     succeeded = true;
@@ -467,6 +471,7 @@
                         rightFrame.setPage(rightNode);
                         rightFrame.initBuffer((byte) 0);
                         rightFrame.setRightPage(ctx.interiorFrame.getRightPage());
+                        ctx.modificationCallback.found(null);
                         ctx.leafFrame.split(rightFrame, tuple, ctx.splitKey);
                         ctx.leafFrame.setRightPage(rightPageId);
                     }
@@ -798,6 +803,8 @@
     }
 
     private void deleteTuple(int tupleIndex, RTreeOpContext ctx) throws HyracksDataException {
+        ITupleReference beforeTuple = ctx.leafFrame.getBeforeTuple(ctx.getTuple(), tupleIndex, ctx.cmp);
+        ctx.modificationCallback.found(beforeTuple);
         ctx.leafFrame.delete(tupleIndex, ctx.cmp);
         ctx.leafFrame.setPageLsn(incrementGlobalNsn());
     }
@@ -906,6 +913,7 @@
             cursor.setFileId(fileId);
             cursor.setCurrentPageId(currentPageId);
             cursor.setMaxPageId(maxPageId);
+            ctx.cursorInitialState.setSearchOperationCallback(ctx.searchCallback);
             ctx.cursorInitialState.setPage(page);
             cursor.open(ctx.cursorInitialState, searchPred);
         } catch (Exception e) {
@@ -933,16 +941,17 @@
     @Override
     public ITreeIndexAccessor createAccessor(IModificationOperationCallback modificationCallback,
             ISearchOperationCallback searchCallback) {
-        return new RTreeAccessor(this);
+        return new RTreeAccessor(this, modificationCallback, searchCallback);
     }
 
     public class RTreeAccessor implements ITreeIndexAccessor {
         private RTree rtree;
         private RTreeOpContext ctx;
 
-        public RTreeAccessor(RTree rtree) {
+        public RTreeAccessor(RTree rtree, IModificationOperationCallback modificationCallback,
+                ISearchOperationCallback searchCallback) {
             this.rtree = rtree;
-            this.ctx = rtree.createOpContext();
+            this.ctx = rtree.createOpContext(modificationCallback, searchCallback);
         }
 
         @Override
@@ -994,7 +1003,7 @@
         @Override
         public void upsert(ITupleReference tuple) throws HyracksDataException, TreeIndexException {
             throw new UnsupportedOperationException(
-                    "The RTree does not suypport the notion of keys, therefore upsert does not make sense.");
+                    "The RTree does not support the notion of keys, therefore upsert does not make sense.");
         }
     }
 }
\ No newline at end of file
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTreeCursorInitialState.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTreeCursorInitialState.java
index ac1eb7d..70c59a7 100644
--- a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTreeCursorInitialState.java
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTreeCursorInitialState.java
@@ -16,36 +16,48 @@
 package edu.uci.ics.hyracks.storage.am.rtree.impls;
 
 import edu.uci.ics.hyracks.storage.am.common.api.ICursorInitialState;
+import edu.uci.ics.hyracks.storage.am.common.api.ISearchOperationCallback;
 import edu.uci.ics.hyracks.storage.common.buffercache.ICachedPage;
 
 public class RTreeCursorInitialState implements ICursorInitialState {
 
-	private PathList pathList;
-	private int rootPage;
-	private ICachedPage page; // for disk order scan
+    private PathList pathList;
+    private int rootPage;
+    private ICachedPage page; // for disk order scan
+    private ISearchOperationCallback searchCallback;
 
-	public RTreeCursorInitialState(PathList pathList, int rootPage) {
-		this.pathList = pathList;
-		this.rootPage = rootPage;
-	}
+    public RTreeCursorInitialState(PathList pathList, int rootPage, ISearchOperationCallback searchCallback) {
+        this.pathList = pathList;
+        this.rootPage = rootPage;
+    }
 
-	public PathList getPathList() {
-		return pathList;
-	}
+    public PathList getPathList() {
+        return pathList;
+    }
 
-	public int getRootPage() {
-		return rootPage;
-	}
+    public int getRootPage() {
+        return rootPage;
+    }
 
-	public void setRootPage(int rootPage) {
-		this.rootPage = rootPage;
-	}
+    public void setRootPage(int rootPage) {
+        this.rootPage = rootPage;
+    }
 
-	public ICachedPage getPage() {
-		return page;
-	}
+    public ICachedPage getPage() {
+        return page;
+    }
 
-	public void setPage(ICachedPage page) {
-		this.page = page;
-	}
+    public void setPage(ICachedPage page) {
+        this.page = page;
+    }
+
+    @Override
+    public ISearchOperationCallback getSearchOperationCallback() {
+        return searchCallback;
+    }
+
+    @Override
+    public void setSearchOperationCallback(ISearchOperationCallback searchCallback) {
+        this.searchCallback = searchCallback;
+    }
 }
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTreeOpContext.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTreeOpContext.java
index 6683444..f703510 100644
--- a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTreeOpContext.java
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTreeOpContext.java
@@ -20,6 +20,8 @@
 import edu.uci.ics.hyracks.api.dataflow.value.IBinaryComparatorFactory;
 import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference;
 import edu.uci.ics.hyracks.storage.am.common.api.IIndexOpContext;
+import edu.uci.ics.hyracks.storage.am.common.api.IModificationOperationCallback;
+import edu.uci.ics.hyracks.storage.am.common.api.ISearchOperationCallback;
 import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexCursor;
 import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexMetaDataFrame;
 import edu.uci.ics.hyracks.storage.am.common.ophelpers.IndexOp;
@@ -47,12 +49,18 @@
     public ArrayList<ICachedPage> NSNUpdates;
     public ArrayList<ICachedPage> LSNUpdates;
 
+    public final IModificationOperationCallback modificationCallback;
+    public final ISearchOperationCallback searchCallback;
+
     public RTreeOpContext(IRTreeLeafFrame leafFrame, IRTreeInteriorFrame interiorFrame,
-            ITreeIndexMetaDataFrame metaFrame, IBinaryComparatorFactory[] cmpFactories, int treeHeightHint) {
+            ITreeIndexMetaDataFrame metaFrame, IBinaryComparatorFactory[] cmpFactories, int treeHeightHint,
+            IModificationOperationCallback modificationCallback, ISearchOperationCallback searchCallback) {
         this.cmp = MultiComparator.create(cmpFactories);
         this.interiorFrame = interiorFrame;
         this.leafFrame = leafFrame;
         this.metaFrame = metaFrame;
+        this.modificationCallback = modificationCallback;
+        this.searchCallback = searchCallback;
         pathList = new PathList(treeHeightHint, treeHeightHint);
         NSNUpdates = new ArrayList<ICachedPage>();
         LSNUpdates = new ArrayList<ICachedPage>();
@@ -92,7 +100,7 @@
             }
         }
         if (cursorInitialState == null) {
-            cursorInitialState = new RTreeCursorInitialState(pathList, 1);
+            cursorInitialState = new RTreeCursorInitialState(pathList, 1, searchCallback);
         }
         this.op = newOp;
     }
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTreeSearchCursor.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTreeSearchCursor.java
index ee7ec5f..0ae8969 100644
--- a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTreeSearchCursor.java
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTreeSearchCursor.java
@@ -18,6 +18,7 @@
 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.ICursorInitialState;
+import edu.uci.ics.hyracks.storage.am.common.api.ISearchOperationCallback;
 import edu.uci.ics.hyracks.storage.am.common.api.ISearchPredicate;
 import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexCursor;
 import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexTupleReference;
@@ -51,6 +52,8 @@
     private ITreeIndexTupleReference frameTuple;
     private boolean readLatched = false;
 
+    private ISearchOperationCallback searchCallback;
+
     public RTreeSearchCursor(IRTreeInteriorFrame interiorFrame, IRTreeLeafFrame leafFrame) {
         this.interiorFrame = interiorFrame;
         this.leafFrame = leafFrame;
@@ -203,6 +206,7 @@
             pathList.clear();
         }
 
+        searchCallback = initialState.getSearchOperationCallback();
         pathList = ((RTreeCursorInitialState) initialState).getPathList();
         rootPage = ((RTreeCursorInitialState) initialState).getRootPage();