diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/api/ITupleAcceptor.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/api/ITupleAcceptor.java
new file mode 100644
index 0000000..1e2b623
--- /dev/null
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/api/ITupleAcceptor.java
@@ -0,0 +1,7 @@
+package edu.uci.ics.hyracks.storage.am.btree.api;
+
+import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference;
+
+public interface ITupleAcceptor {
+    public boolean accept(ITupleReference tuple);
+}
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 9728be8..efe1158 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
@@ -27,6 +27,7 @@
 import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeFrame;
 import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeInteriorFrame;
 import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeLeafFrame;
+import edu.uci.ics.hyracks.storage.am.btree.api.ITupleAcceptor;
 import edu.uci.ics.hyracks.storage.am.btree.exceptions.BTreeException;
 import edu.uci.ics.hyracks.storage.am.btree.exceptions.BTreeNonExistentKeyException;
 import edu.uci.ics.hyracks.storage.am.btree.exceptions.BTreeNotUpdateableException;
@@ -375,10 +376,14 @@
             throws Exception {
         boolean restartOp = false;
         ITupleReference beforeTuple = ctx.leafFrame.getBeforeTuple(tuple, targetTupleIndex);
-        if (beforeTuple == null) {
-            restartOp = insertLeaf(tuple, targetTupleIndex, pageId, ctx);
+        if (ctx.acceptor.accept(beforeTuple)) {
+            if (beforeTuple == null) {
+                restartOp = insertLeaf(tuple, targetTupleIndex, pageId, ctx);
+            } else {
+                restartOp = updateLeaf(tuple, targetTupleIndex, pageId, ctx);
+            }
         } else {
-            restartOp = updateLeaf(tuple, targetTupleIndex, pageId, ctx);
+            restartOp = insertLeaf(tuple, targetTupleIndex, pageId, ctx);
         }
         return restartOp;
     }
@@ -768,7 +773,13 @@
 
         @Override
         public void upsert(ITupleReference tuple) throws HyracksDataException, TreeIndexException {
+            upsertIfConditionElseInsert(tuple, UnconditionalTupleAcceptor.INSTANCE);
+        }
+
+        public void upsertIfConditionElseInsert(ITupleReference tuple, ITupleAcceptor acceptor)
+                throws HyracksDataException, TreeIndexException {
             ctx.reset(IndexOp.UPSERT);
+            ctx.acceptor = acceptor;
             btree.upsert(tuple, ctx);
         }
 
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 98ad4a2..c5f6bd6 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
@@ -18,6 +18,7 @@
 import edu.uci.ics.hyracks.api.dataflow.value.IBinaryComparatorFactory;
 import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeInteriorFrame;
 import edu.uci.ics.hyracks.storage.am.btree.api.IBTreeLeafFrame;
+import edu.uci.ics.hyracks.storage.am.btree.api.ITupleAcceptor;
 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;
@@ -49,6 +50,7 @@
     public boolean exceptionHandled;
     public IModificationOperationCallback modificationCallback;
     public ISearchOperationCallback searchCallback;
+    public ITupleAcceptor acceptor;
 
     public BTreeOpContext(ITreeIndexFrameFactory leafFrameFactory, ITreeIndexFrameFactory interiorFrameFactory,
             ITreeIndexMetaDataFrame metaFrame, IBinaryComparatorFactory[] cmpFactories,
diff --git a/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/UnconditionalTupleAcceptor.java b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/UnconditionalTupleAcceptor.java
new file mode 100644
index 0000000..9ae2523
--- /dev/null
+++ b/hyracks-storage-am-btree/src/main/java/edu/uci/ics/hyracks/storage/am/btree/impls/UnconditionalTupleAcceptor.java
@@ -0,0 +1,14 @@
+package edu.uci.ics.hyracks.storage.am.btree.impls;
+
+import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference;
+import edu.uci.ics.hyracks.storage.am.btree.api.ITupleAcceptor;
+
+public enum UnconditionalTupleAcceptor implements ITupleAcceptor {
+    INSTANCE;
+
+    @Override
+    public boolean accept(ITupleReference tuple) {
+        return true;
+    }
+
+}
diff --git a/hyracks-storage-am-lsm-btree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/btree/impls/AntimatterAwareTupleAcceptor.java b/hyracks-storage-am-lsm-btree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/btree/impls/AntimatterAwareTupleAcceptor.java
new file mode 100644
index 0000000..a1d00a6
--- /dev/null
+++ b/hyracks-storage-am-lsm-btree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/btree/impls/AntimatterAwareTupleAcceptor.java
@@ -0,0 +1,17 @@
+package edu.uci.ics.hyracks.storage.am.lsm.btree.impls;
+
+import edu.uci.ics.hyracks.dataflow.common.data.accessors.ITupleReference;
+import edu.uci.ics.hyracks.storage.am.btree.api.ITupleAcceptor;
+import edu.uci.ics.hyracks.storage.am.lsm.btree.tuples.LSMBTreeTupleReference;
+
+public class AntimatterAwareTupleAcceptor implements ITupleAcceptor {
+
+    @Override
+    public boolean accept(ITupleReference tuple) {
+        if (tuple == null) {
+            return true;
+        }
+        return ((LSMBTreeTupleReference) tuple).isAntimatter();
+    }
+
+}
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 c76400c..abc8460 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
@@ -48,6 +48,7 @@
 import edu.uci.ics.hyracks.storage.am.common.api.TreeIndexException;
 import edu.uci.ics.hyracks.storage.am.common.impls.NoOpOperationCallback;
 import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
+import edu.uci.ics.hyracks.storage.am.lsm.btree.tuples.LSMBTreeTupleReference;
 import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMComponentFinalizer;
 import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMFileManager;
 import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMFlushController;
@@ -73,6 +74,7 @@
     private final BTree memBTree;
     private final FileReference memBtreeFile = new FileReference(new File("memBtree"));
     private final InMemoryFreePageManager memFreePageManager;
+    private final AntimatterAwareTupleAcceptor acceptor = new AntimatterAwareTupleAcceptor();
 
     // On-disk components.    
     private final ILSMFileManager fileManager;
@@ -229,7 +231,11 @@
         ctx.memBTreeAccessor.search(memCursor, predicate);
         try {
             if (memCursor.hasNext()) {
-                throw new BTreeDuplicateKeyException("Failed to insert key since key already exists.");
+                memCursor.next();
+                LSMBTreeTupleReference lsmbtreeTuple = (LSMBTreeTupleReference) memCursor.getTuple();
+                if (!lsmbtreeTuple.isAntimatter()) {
+                    throw new BTreeDuplicateKeyException("Failed to insert key since key already exists.");
+                }
             }
         } finally {
             memCursor.close();
@@ -243,7 +249,7 @@
         } finally {
             searchCursor.close();
         }
-        ctx.memBTreeAccessor.insert(tuple);
+        ctx.memBTreeAccessor.upsertIfConditionElseInsert(tuple, acceptor);
 
         return true;
     }