diff --git a/hyracks-storage-am-lsm-invertedindex/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/invertedindex/api/IInvertedListBuilder.java b/hyracks-storage-am-lsm-invertedindex/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/invertedindex/api/IInvertedListBuilder.java
index 51086d2..dcb5fdd 100644
--- a/hyracks-storage-am-lsm-invertedindex/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/invertedindex/api/IInvertedListBuilder.java
+++ b/hyracks-storage-am-lsm-invertedindex/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/invertedindex/api/IInvertedListBuilder.java
@@ -1,5 +1,5 @@
 /*
- * Copyright 2009-2010 by The Regents of the University of California
+ * Copyright 2009-2012 by The Regents of the University of California
  * Licensed under the Apache License, Version 2.0 (the "License");
  * you may not use this file except in compliance with the License.
  * you may obtain a copy of the License from
diff --git a/hyracks-storage-am-lsm-invertedindex/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/invertedindex/impls/LSMInvertedIndex.java b/hyracks-storage-am-lsm-invertedindex/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/invertedindex/impls/LSMInvertedIndex.java
index c284149..78d1cfe 100644
--- a/hyracks-storage-am-lsm-invertedindex/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/invertedindex/impls/LSMInvertedIndex.java
+++ b/hyracks-storage-am-lsm-invertedindex/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/invertedindex/impls/LSMInvertedIndex.java
@@ -47,6 +47,7 @@
 import edu.uci.ics.hyracks.storage.am.common.impls.NoOpOperationCallback;
 import edu.uci.ics.hyracks.storage.am.common.ophelpers.IndexOp;
 import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
+import edu.uci.ics.hyracks.storage.am.common.tuples.PermutingTupleReference;
 import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMComponentFinalizer;
 import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMFlushController;
 import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMIOOperation;
@@ -420,22 +421,34 @@
     private ICursorInitialState createCursorInitialState(ISearchPredicate pred, IIndexOpContext ictx,
             boolean includeMemComponent, AtomicInteger searcherRefCount, ArrayList<IIndexAccessor> indexAccessors,
             ArrayList<IIndexAccessor> deletedKeysBTreeAccessors) {
-        // TODO: This check is not pretty, but it does the job. Come up with something more OO in the future.
         ICursorInitialState initState = null;
+        PermutingTupleReference keysOnlyTuple = createKeysOnlyTupleReference();
+        MultiComparator keyCmp = MultiComparator.create(invListCmpFactories);
+        // TODO: This check is not pretty, but it does the job. Come up with something more OO in the future.
         // Distinguish between regular searches and range searches (mostly used in merges).
         if (pred instanceof InvertedIndexSearchPredicate) {
-            initState = new LSMInvertedIndexCursorInitialState(indexAccessors, ictx, includeMemComponent,
-                    searcherRefCount, lsmHarness);
+            initState = new LSMInvertedIndexSearchCursorInitialState(keyCmp, keysOnlyTuple, indexAccessors,
+                    deletedKeysBTreeAccessors, ictx, includeMemComponent, searcherRefCount, lsmHarness);
         } else {
-            InMemoryInvertedIndex memInvIndex = (InMemoryInvertedIndex) memComponent.getInvIndex();
-            MultiComparator tokensAndKeyCmp = MultiComparator.create(memInvIndex.getBTree().getComparatorFactories());
-            MultiComparator keyCmp = MultiComparator.create(invListCmpFactories);
-            initState = new LSMInvertedIndexRangeSearchCursorInitialState(tokensAndKeyCmp, keyCmp, includeMemComponent, searcherRefCount,
-                    lsmHarness, indexAccessors, deletedKeysBTreeAccessors, pred);
+            initState = new LSMInvertedIndexRangeSearchCursorInitialState(keyCmp, keysOnlyTuple, includeMemComponent,
+                    searcherRefCount, lsmHarness, indexAccessors, deletedKeysBTreeAccessors, pred);
         }
         return initState;
     }
     
+    /**
+     * Returns a permuting tuple reference that projects away the document field(s) of a tuple, only leaving the key fields.
+     */
+    private PermutingTupleReference createKeysOnlyTupleReference() {
+        // Project away token fields.
+        int[] keyFieldPermutation = new int[invListTypeTraits.length];
+        int numTokenFields = tokenTypeTraits.length;
+        for (int i = 0; i < invListTypeTraits.length; i++) {
+            keyFieldPermutation[i] = numTokenFields + i;
+        }
+        return new PermutingTupleReference(keyFieldPermutation);
+    }
+    
     @Override
     // TODO: Deal with deletions properly.
     public Object merge(List<Object> mergedComponents, ILSMIOOperation operation) throws HyracksDataException,
diff --git a/hyracks-storage-am-lsm-invertedindex/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/invertedindex/impls/LSMInvertedIndexRangeSearchCursor.java b/hyracks-storage-am-lsm-invertedindex/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/invertedindex/impls/LSMInvertedIndexRangeSearchCursor.java
index b8b7de3..ccbffa3 100644
--- a/hyracks-storage-am-lsm-invertedindex/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/invertedindex/impls/LSMInvertedIndexRangeSearchCursor.java
+++ b/hyracks-storage-am-lsm-invertedindex/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/invertedindex/impls/LSMInvertedIndexRangeSearchCursor.java
@@ -52,16 +52,10 @@
         }
         
         // For searching the deleted-keys BTrees.
+        this.keysOnlyTuple = lsmInitState.getKeysOnlyTuple();
         deletedKeysBTreeAccessors = lsmInitState.getDeletedKeysBTreeAccessors();
         deletedKeysBTreeCursor = deletedKeysBTreeAccessors.get(0).createSearchCursor();        
         MultiComparator keyCmp = lsmInitState.getKeyComparator();
-        // Project away token fields.
-        int[] keyFieldPermutation = new int[keyCmp.getKeyFieldCount()];
-        int numTokenFields = cmp.getKeyFieldCount() - keyCmp.getKeyFieldCount();
-        for (int i = 0; i < keyCmp.getKeyFieldCount(); i++) {
-            keyFieldPermutation[i] = numTokenFields + i;
-        }
-        keysOnlyTuple = new PermutingTupleReference(keyFieldPermutation);
         keySearchPred = new RangePredicate(keysOnlyTuple, keysOnlyTuple, true, true, keyCmp, keyCmp);
         
         searcherRefCount = lsmInitState.getSearcherRefCount();
diff --git a/hyracks-storage-am-lsm-invertedindex/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/invertedindex/impls/LSMInvertedIndexRangeSearchCursorInitialState.java b/hyracks-storage-am-lsm-invertedindex/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/invertedindex/impls/LSMInvertedIndexRangeSearchCursorInitialState.java
index c4f83a0..fdb4a19 100644
--- a/hyracks-storage-am-lsm-invertedindex/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/invertedindex/impls/LSMInvertedIndexRangeSearchCursorInitialState.java
+++ b/hyracks-storage-am-lsm-invertedindex/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/invertedindex/impls/LSMInvertedIndexRangeSearchCursorInitialState.java
@@ -23,12 +23,12 @@
 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.ophelpers.MultiComparator;
+import edu.uci.ics.hyracks.storage.am.common.tuples.PermutingTupleReference;
 import edu.uci.ics.hyracks.storage.am.lsm.common.impls.LSMHarness;
 import edu.uci.ics.hyracks.storage.common.buffercache.ICachedPage;
 
 public class LSMInvertedIndexRangeSearchCursorInitialState implements ICursorInitialState {
 
-    private final MultiComparator tokensAndKeyCmp;
     private final MultiComparator keyCmp;
     private final AtomicInteger searcherRefCount;
     private final LSMHarness lsmHarness;
@@ -36,15 +36,16 @@
     private final ArrayList<IIndexAccessor> indexAccessors;
     private final ArrayList<IIndexAccessor> deletedKeysBTreeAccessors;
     private final ISearchPredicate predicate;
+    private final PermutingTupleReference keysOnlyTuple;
     
     private final boolean includeMemComponent;
 
-    public LSMInvertedIndexRangeSearchCursorInitialState(MultiComparator tokensAndKeyCmp, MultiComparator keyCmp,
-            boolean includeMemComponent, AtomicInteger searcherRefCount, LSMHarness lsmHarness,
+    public LSMInvertedIndexRangeSearchCursorInitialState(MultiComparator keyCmp,
+            PermutingTupleReference keysOnlyTuple, boolean includeMemComponent, AtomicInteger searcherRefCount, LSMHarness lsmHarness,
             ArrayList<IIndexAccessor> indexAccessors, ArrayList<IIndexAccessor> deletedKeysBTreeAccessors,
             ISearchPredicate predicate) {
-        this.tokensAndKeyCmp = tokensAndKeyCmp;
         this.keyCmp = keyCmp;
+        this.keysOnlyTuple = keysOnlyTuple;
         this.searcherRefCount = searcherRefCount;
         this.lsmHarness = lsmHarness;
         this.indexAccessors = indexAccessors;
@@ -96,21 +97,25 @@
         return predicate;
     }
 
-    public MultiComparator getKeyComparator() {
-        return keyCmp;
-    }
-    
-    @Override
-    public MultiComparator getOriginalKeyComparator() {
-        return tokensAndKeyCmp;
-    }
-
     @Override
     public void setOriginialKeyComparator(MultiComparator originalCmp) {
         // Do nothing.
     }
     
+    @Override
+    public MultiComparator getOriginalKeyComparator() {
+        return null;
+    }
+
+    public MultiComparator getKeyComparator() {
+        return keyCmp;
+    }
+    
     public boolean getIncludeMemComponent() {
         return includeMemComponent;
     }
+    
+    public PermutingTupleReference getKeysOnlyTuple() {
+        return keysOnlyTuple;
+    }
 }
diff --git a/hyracks-storage-am-lsm-invertedindex/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/invertedindex/impls/LSMInvertedIndexSearchCursor.java b/hyracks-storage-am-lsm-invertedindex/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/invertedindex/impls/LSMInvertedIndexSearchCursor.java
index 60084da..88231a6 100644
--- a/hyracks-storage-am-lsm-invertedindex/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/invertedindex/impls/LSMInvertedIndexSearchCursor.java
+++ b/hyracks-storage-am-lsm-invertedindex/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/invertedindex/impls/LSMInvertedIndexSearchCursor.java
@@ -14,17 +14,19 @@
  */
 package edu.uci.ics.hyracks.storage.am.lsm.invertedindex.impls;
 
-import java.util.ArrayList;
 import java.util.List;
 import java.util.concurrent.atomic.AtomicInteger;
 
 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.btree.impls.RangePredicate;
 import edu.uci.ics.hyracks.storage.am.common.api.ICursorInitialState;
 import edu.uci.ics.hyracks.storage.am.common.api.IIndexAccessor;
 import edu.uci.ics.hyracks.storage.am.common.api.IIndexCursor;
 import edu.uci.ics.hyracks.storage.am.common.api.ISearchPredicate;
 import edu.uci.ics.hyracks.storage.am.common.api.IndexException;
+import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
+import edu.uci.ics.hyracks.storage.am.common.tuples.PermutingTupleReference;
 import edu.uci.ics.hyracks.storage.am.lsm.common.impls.LSMHarness;
 
 /**
@@ -33,123 +35,90 @@
  */
 public class LSMInvertedIndexSearchCursor implements IIndexCursor {
 
-    private final List<IIndexCursor> indexCursors = new ArrayList<IIndexCursor>();
-    private int cursorIndex = -1;
+    private IIndexAccessor currentAccessor;
+    private IIndexCursor currentCursor;
+    private int accessorIndex = -1;
     private LSMHarness harness;
     private boolean includeMemComponent;
     private AtomicInteger searcherRefCount;
     private List<IIndexAccessor> indexAccessors;
     private ISearchPredicate searchPred;
+    
+    // Assuming the cursor for all deleted-keys indexes are of the same type.
+    protected IIndexCursor deletedKeysBTreeCursor;
+    protected List<IIndexAccessor> deletedKeysBTreeAccessors;
+    protected PermutingTupleReference keysOnlyTuple;
+    protected RangePredicate keySearchPred;
 
     @Override
     public void open(ICursorInitialState initialState, ISearchPredicate searchPred) throws HyracksDataException {
-        LSMInvertedIndexCursorInitialState lsmInitialState = (LSMInvertedIndexCursorInitialState) initialState;
-        harness = lsmInitialState.getLSMHarness();
-        includeMemComponent = lsmInitialState.getIncludeMemComponent();
-        searcherRefCount = lsmInitialState.getSearcherRefCount();
-        indexAccessors = lsmInitialState.getIndexAccessors();
-        indexCursors.clear();
-        cursorIndex = 0;
+        LSMInvertedIndexSearchCursorInitialState lsmInitState = (LSMInvertedIndexSearchCursorInitialState) initialState;
+        harness = lsmInitState.getLSMHarness();
+        includeMemComponent = lsmInitState.getIncludeMemComponent();
+        searcherRefCount = lsmInitState.getSearcherRefCount();
+        indexAccessors = lsmInitState.getIndexAccessors();
+        accessorIndex = 0;
         this.searchPred = searchPred;
-        while (cursorIndex < indexAccessors.size()) {
-            // Open cursors and perform search lazily as each component is passed over
-            IIndexAccessor currentAccessor = indexAccessors.get(cursorIndex);
-            IIndexCursor currentCursor = currentAccessor.createSearchCursor();
-            try {
-                currentAccessor.search(currentCursor, searchPred);
-            } catch (IndexException e) {
-                throw new HyracksDataException(e);
-            }
-            indexCursors.add(currentCursor);
-            if (currentCursor.hasNext()) {
-                break;
-            }
-            // Close as we go to release any resources.
-            currentCursor.close();
-            cursorIndex++;
-        }
+        
+        // For searching the deleted-keys BTrees.
+        this.keysOnlyTuple = lsmInitState.getKeysOnlyTuple();
+        deletedKeysBTreeAccessors = lsmInitState.getDeletedKeysBTreeAccessors();
+        deletedKeysBTreeCursor = deletedKeysBTreeAccessors.get(0).createSearchCursor();        
+        MultiComparator keyCmp = lsmInitState.getKeyComparator();
+        keySearchPred = new RangePredicate(keysOnlyTuple, keysOnlyTuple, true, true, keyCmp, keyCmp);        
     }
 
     @Override
     public boolean hasNext() throws HyracksDataException {
-        if (cursorIndex >= indexAccessors.size()) {
-            return false;
+        if (currentCursor != null) {
+            if (currentCursor.hasNext()) {
+                return true;
+            }
+            currentCursor.close();
+            accessorIndex++;
         }
-        IIndexCursor currentCursor = indexCursors.get(cursorIndex);
-        if (currentCursor.hasNext()) {
-            return true;
-        }
-        currentCursor.close();
-        cursorIndex++;
-        while (cursorIndex < indexAccessors.size()) {
-            IIndexAccessor currentAccessor = indexAccessors.get(cursorIndex);
+        while (accessorIndex < indexAccessors.size()) {
+            // Current cursor has been exhausted, switch to next accessor/cursor.
+            currentAccessor = indexAccessors.get(accessorIndex);
             currentCursor = currentAccessor.createSearchCursor();
             try {
                 currentAccessor.search(currentCursor, searchPred);
             } catch (IndexException e) {
                 throw new HyracksDataException(e);
             }
-            indexCursors.add(currentCursor);
             if (currentCursor.hasNext()) {
                 return true;
             }
+            // Close as we go to release resources.
             currentCursor.close();
-            cursorIndex++;
+            accessorIndex++;
         }
         return false;
     }
 
     @Override
     public void next() throws HyracksDataException {
-        IIndexCursor currentCursor = indexCursors.get(cursorIndex);
-        if (currentCursor.hasNext()) {
-            currentCursor.next();
-        } else {
-            currentCursor.close();
-            cursorIndex++;
-            while (cursorIndex < indexAccessors.size()) {
-                IIndexAccessor currentAccessor = indexAccessors.get(cursorIndex);
-                currentCursor = currentAccessor.createSearchCursor();
-                try {
-                    currentAccessor.search(currentCursor, searchPred);
-                } catch (IndexException e) {
-                    throw new HyracksDataException(e);
-                }
-                indexCursors.add(currentCursor);
-                if (currentCursor.hasNext()) {
-                    currentCursor.next();
-                    break;
-                } else {
-                    cursorIndex++;
-                }
-            }
-        }
+        currentCursor.next();
     }
 
     @Override
     public void close() throws HyracksDataException {
-        cursorIndex = -1;
-        for (int i = 0; i < indexCursors.size(); i++) {
-            indexCursors.get(i).close();
-        }
-        indexCursors.clear();
+        reset();
+        accessorIndex = -1;
         harness.closeSearchCursor(searcherRefCount, includeMemComponent);
     }
 
     @Override
     public void reset() throws HyracksDataException {
-        cursorIndex = 0;
-        for (int i = 0; i < indexCursors.size(); i++) {
-            indexCursors.get(i).reset();
+        if (currentCursor != null) {
+            currentCursor.close();
+            currentCursor = null;
         }
+        accessorIndex = 0;
     }
 
     @Override
     public ITupleReference getTuple() {
-        if (cursorIndex < indexCursors.size()) {
-            return indexCursors.get(cursorIndex).getTuple();
-        }
-        return null;
+        return currentCursor.getTuple();
     }
-
 }
diff --git a/hyracks-storage-am-lsm-invertedindex/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/invertedindex/impls/LSMInvertedIndexCursorInitialState.java b/hyracks-storage-am-lsm-invertedindex/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/invertedindex/impls/LSMInvertedIndexSearchCursorInitialState.java
similarity index 72%
rename from hyracks-storage-am-lsm-invertedindex/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/invertedindex/impls/LSMInvertedIndexCursorInitialState.java
rename to hyracks-storage-am-lsm-invertedindex/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/invertedindex/impls/LSMInvertedIndexSearchCursorInitialState.java
index b7897a8..6102cee 100644
--- a/hyracks-storage-am-lsm-invertedindex/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/invertedindex/impls/LSMInvertedIndexCursorInitialState.java
+++ b/hyracks-storage-am-lsm-invertedindex/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/invertedindex/impls/LSMInvertedIndexSearchCursorInitialState.java
@@ -23,22 +23,30 @@
 import edu.uci.ics.hyracks.storage.am.common.api.IIndexOpContext;
 import edu.uci.ics.hyracks.storage.am.common.api.ISearchOperationCallback;
 import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
+import edu.uci.ics.hyracks.storage.am.common.tuples.PermutingTupleReference;
 import edu.uci.ics.hyracks.storage.am.lsm.common.impls.LSMHarness;
 import edu.uci.ics.hyracks.storage.common.buffercache.ICachedPage;
 
-public class LSMInvertedIndexCursorInitialState implements ICursorInitialState {
+public class LSMInvertedIndexSearchCursorInitialState implements ICursorInitialState {
 
     private final boolean includeMemComponent;
     private final AtomicInteger searcherfRefCount;
     private final LSMHarness lsmHarness;
     private final List<IIndexAccessor> indexAccessors;
+    private final List<IIndexAccessor> deletedKeysBTreeAccessors;
     private final IIndexOpContext opContext;
     private ISearchOperationCallback searchCallback;
     private MultiComparator originalCmp;
+    private final MultiComparator keyCmp;
+    private final PermutingTupleReference keysOnlyTuple;
 
-    public LSMInvertedIndexCursorInitialState(List<IIndexAccessor> indexAccessors, IIndexOpContext ctx,
-            boolean includeMemComponent, AtomicInteger searcherfRefCount, LSMHarness lsmHarness) {
+    public LSMInvertedIndexSearchCursorInitialState(final MultiComparator keyCmp, PermutingTupleReference keysOnlyTuple, List<IIndexAccessor> indexAccessors,
+            List<IIndexAccessor> deletedKeysBTreeAccessors, IIndexOpContext ctx, boolean includeMemComponent,
+            AtomicInteger searcherfRefCount, LSMHarness lsmHarness) {
+        this.keyCmp = keyCmp;
+        this.keysOnlyTuple = keysOnlyTuple;
         this.indexAccessors = indexAccessors;
+        this.deletedKeysBTreeAccessors = deletedKeysBTreeAccessors;
         this.includeMemComponent = includeMemComponent;
         this.searcherfRefCount = searcherfRefCount;
         this.lsmHarness = lsmHarness;
@@ -93,4 +101,16 @@
     public void setOriginialKeyComparator(MultiComparator originalCmp) {
         this.originalCmp = originalCmp;
     }
+    
+    public MultiComparator getKeyComparator() {
+        return keyCmp;
+    }
+    
+    public List<IIndexAccessor> getDeletedKeysBTreeAccessors() {
+        return deletedKeysBTreeAccessors;
+    }
+    
+    public PermutingTupleReference getKeysOnlyTuple() {
+        return keysOnlyTuple;
+    }
 }