cassandra-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From alek...@apache.org
Subject git commit: Cleanup and optimize collation and slice iterators
Date Mon, 05 May 2014 19:53:57 GMT
Repository: cassandra
Updated Branches:
  refs/heads/cassandra-2.1 07dfb58ad -> 9881ea6b3


Cleanup and optimize collation and slice iterators

patch by Aleksey Yeschenko and Benedict Elliott Smith; reviewed by
Aleksey Yeschenko for CASSANDRA-7107


Project: http://git-wip-us.apache.org/repos/asf/cassandra/repo
Commit: http://git-wip-us.apache.org/repos/asf/cassandra/commit/9881ea6b
Tree: http://git-wip-us.apache.org/repos/asf/cassandra/tree/9881ea6b
Diff: http://git-wip-us.apache.org/repos/asf/cassandra/diff/9881ea6b

Branch: refs/heads/cassandra-2.1
Commit: 9881ea6b3e4c48fab071bf3e1cf3535775adefa2
Parents: 07dfb58
Author: belliottsmith <github@sub.laerad.com>
Authored: Sun Apr 27 17:26:34 2014 +0100
Committer: Aleksey Yeschenko <aleksey@apache.org>
Committed: Mon May 5 22:53:25 2014 +0300

----------------------------------------------------------------------
 CHANGES.txt                                     |   1 +
 .../cassandra/db/ArrayBackedSortedColumns.java  | 260 +++++++++++--------
 .../apache/cassandra/db/AtomicBTreeColumns.java |  76 +++++-
 .../cassandra/db/CollationController.java       |  46 ++--
 .../org/apache/cassandra/db/ColumnFamily.java   |  17 +-
 .../apache/cassandra/db/ColumnFamilyStore.java  |   5 +-
 .../apache/cassandra/db/RowIteratorFactory.java |  19 +-
 .../apache/cassandra/db/filter/ColumnSlice.java | 146 -----------
 .../cassandra/db/filter/ExtendedFilter.java     |   4 +-
 .../cassandra/db/filter/IDiskAtomFilter.java    |   4 +-
 .../cassandra/db/filter/NamesQueryFilter.java   |  35 ++-
 .../apache/cassandra/db/filter/QueryFilter.java |  56 ++--
 .../cassandra/db/filter/SliceQueryFilter.java   |  24 +-
 .../cassandra/service/RowDataResolver.java      |  11 +-
 .../apache/cassandra/utils/MergeIterator.java   |  25 +-
 .../org/apache/cassandra/utils/btree/BTree.java |  12 +-
 .../apache/cassandra/utils/btree/BTreeSet.java  |   8 +-
 .../apache/cassandra/utils/btree/Cursor.java    |   8 +-
 18 files changed, 361 insertions(+), 396 deletions(-)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/cassandra/blob/9881ea6b/CHANGES.txt
----------------------------------------------------------------------
diff --git a/CHANGES.txt b/CHANGES.txt
index 86b261d..a8b6ae4 100644
--- a/CHANGES.txt
+++ b/CHANGES.txt
@@ -2,6 +2,7 @@
  * Parallel streaming for sstableloader (CASSANDRA-3668)
  * Fix bugs in supercolumns handling (CASSANDRA-7138)
  * Fix ClassClassException on composite dense tables (CASSANDRA-7112)
+ * Cleanup and optimize collation and slice iterators (CASSANDRA-7107)
 Merged from 2.0:
  * Correctly delete scheduled range xfers (CASSANDRA-7143)
  * Make batchlog replica selection rack-aware (CASSANDRA-6551)

http://git-wip-us.apache.org/repos/asf/cassandra/blob/9881ea6b/src/java/org/apache/cassandra/db/ArrayBackedSortedColumns.java
----------------------------------------------------------------------
diff --git a/src/java/org/apache/cassandra/db/ArrayBackedSortedColumns.java b/src/java/org/apache/cassandra/db/ArrayBackedSortedColumns.java
index c9cff77..f5624d2 100644
--- a/src/java/org/apache/cassandra/db/ArrayBackedSortedColumns.java
+++ b/src/java/org/apache/cassandra/db/ArrayBackedSortedColumns.java
@@ -22,16 +22,13 @@ import java.util.Arrays;
 import java.util.Collection;
 import java.util.Comparator;
 import java.util.Iterator;
-import java.util.List;
 
 import com.google.common.base.Function;
 import com.google.common.collect.AbstractIterator;
 import com.google.common.collect.Iterables;
-import com.google.common.collect.Lists;
 
 import org.apache.cassandra.config.CFMetaData;
 import org.apache.cassandra.db.composites.CellName;
-import org.apache.cassandra.db.composites.CellNameType;
 import org.apache.cassandra.db.composites.Composite;
 import org.apache.cassandra.db.filter.ColumnSlice;
 import org.apache.cassandra.utils.memory.AbstractAllocator;
@@ -202,6 +199,21 @@ public class ArrayBackedSortedColumns extends ColumnFamily
         return pos >= 0 ? cells[pos] : null;
     }
 
+    /**
+      * Adds a cell, assuming that:
+      * - it's non-gc-able (if a tombstone) or not a tombstone
+      * - it has a more recent timestamp than any partition/range tombstone shadowing it
+      * - it sorts *strictly after* the current-last cell in the array.
+      */
+    public void maybeAppendColumn(Cell cell, DeletionInfo.InOrderTester tester, int gcBefore)
+    {
+        if (cell.getLocalDeletionTime() >= gcBefore && !tester.isDeleted(cell.name(), cell.timestamp()))
+        {
+            internalAdd(cell);
+            sortedSize++;
+        }
+    }
+
     public void addColumn(Cell cell)
     {
         if (size == 0)
@@ -211,7 +223,7 @@ public class ArrayBackedSortedColumns extends ColumnFamily
             return;
         }
 
-        if (size != sortedSize)
+        if (!isSorted)
         {
             internalAdd(cell);
             return;
@@ -349,14 +361,12 @@ public class ArrayBackedSortedColumns extends ColumnFamily
 
     public Collection<Cell> getSortedColumns()
     {
-        maybeSortCells();
-        return reversed ? new ReverseSortedCollection() : new ForwardSortedCollection();
+        return new CellCollection(reversed);
     }
 
     public Collection<Cell> getReverseSortedColumns()
     {
-        maybeSortCells();
-        return reversed ? new ForwardSortedCollection() : new ReverseSortedCollection();
+        return new CellCollection(!reversed);
     }
 
     public int getColumnCount()
@@ -415,8 +425,7 @@ public class ArrayBackedSortedColumns extends ColumnFamily
 
     public Iterable<CellName> getColumnNames()
     {
-        maybeSortCells();
-        return Iterables.transform(new ForwardSortedCollection(), new Function<Cell, CellName>()
+        return Iterables.transform(new CellCollection(false), new Function<Cell, CellName>()
         {
             public CellName apply(Cell cell)
             {
@@ -428,30 +437,33 @@ public class ArrayBackedSortedColumns extends ColumnFamily
     public Iterator<Cell> iterator(ColumnSlice[] slices)
     {
         maybeSortCells();
-        return new SlicesIterator(Arrays.asList(cells).subList(0, size), getComparator(), slices, reversed);
+        return slices.length == 1
+             ? slice(slices[0], reversed, null)
+             : new SlicesIterator(slices, reversed);
     }
 
     public Iterator<Cell> reverseIterator(ColumnSlice[] slices)
     {
         maybeSortCells();
-        return new SlicesIterator(Arrays.asList(cells).subList(0, size), getComparator(), slices, !reversed);
+        return slices.length == 1
+             ? slice(slices[0], !reversed, null)
+             : new SlicesIterator(slices, !reversed);
     }
 
-    private static class SlicesIterator extends AbstractIterator<Cell>
+    private class SlicesIterator extends AbstractIterator<Cell>
     {
-        private final List<Cell> cells;
         private final ColumnSlice[] slices;
-        private final Comparator<Composite> comparator;
+        private final boolean invert;
 
         private int idx = 0;
-        private int previousSliceEnd = 0;
+        private int previousSliceEnd;
         private Iterator<Cell> currentSlice;
 
-        public SlicesIterator(List<Cell> cells, CellNameType comparator, ColumnSlice[] slices, boolean reversed)
+        public SlicesIterator(ColumnSlice[] slices, boolean invert)
         {
-            this.cells = reversed ? Lists.reverse(cells) : cells;
             this.slices = slices;
-            this.comparator = reversed ? comparator.reverseComparator() : comparator;
+            this.invert = invert;
+            previousSliceEnd = invert ? size : 0;
         }
 
         protected Cell computeNext()
@@ -460,26 +472,7 @@ public class ArrayBackedSortedColumns extends ColumnFamily
             {
                 if (idx >= slices.length)
                     return endOfData();
-
-                ColumnSlice slice = slices[idx++];
-                // The first idx to include
-                int startIdx = slice.start.isEmpty() ? 0 : binarySearch(previousSliceEnd, slice.start);
-                if (startIdx < 0)
-                    startIdx = -startIdx - 1;
-
-                // The first idx to exclude
-                int finishIdx = slice.finish.isEmpty() ? cells.size() - 1 : binarySearch(previousSliceEnd, slice.finish);
-                if (finishIdx >= 0)
-                    finishIdx++;
-                else
-                    finishIdx = -finishIdx - 1;
-
-                if (startIdx == 0 && finishIdx == cells.size())
-                    currentSlice = cells.iterator();
-                else
-                    currentSlice = cells.subList(startIdx, finishIdx).iterator();
-
-                previousSliceEnd = finishIdx > 0 ? finishIdx - 1 : 0;
+                currentSlice = slice(slices[idx++], invert, this);
             }
 
             if (currentSlice.hasNext())
@@ -488,99 +481,142 @@ public class ArrayBackedSortedColumns extends ColumnFamily
             currentSlice = null;
             return computeNext();
         }
+    }
 
-        // Copy of ABSC.binarySearch() that takes lists
-        private int binarySearch(int fromIndex, Composite name)
+    /**
+     * @return a sub-range of our cells as an Iterator, between the provided composites (inclusive)
+     *
+     * @param slice  The slice with the inclusive start and finish bounds
+     * @param invert If the sort order of our collection is opposite to the desired sort order of the result;
+     *               this results in swapping the start/finish (since they are provided based on the desired
+     *               sort order, not our sort order), to normalise to our sort order, and a backwards iterator is returned
+     * @param iter   If this slice is part of a multi-slice, the iterator will be updated to ensure cells are visited only once
+     */
+    private Iterator<Cell> slice(ColumnSlice slice, boolean invert, SlicesIterator iter)
+    {
+        Composite start = invert ? slice.finish : slice.start;
+        Composite finish = invert ? slice.start : slice.finish;
+
+        int lowerBound = 0, upperBound = size;
+        if (iter != null)
         {
-            int low = fromIndex;
-            int mid = cells.size();
-            int high = mid - 1;
-            int result = -1;
-            while (low <= high)
-            {
-                mid = (low + high) >> 1;
-                if ((result = comparator.compare(name, cells.get(mid).name())) > 0)
-                    low = mid + 1;
-                else if (result == 0)
-                    return mid;
-                else
-                    high = mid - 1;
-            }
-            return -mid - (result < 0 ? 1 : 2);
+            if (invert)
+                upperBound = iter.previousSliceEnd;
+            else
+                lowerBound = iter.previousSliceEnd;
+        }
+
+        if (!start.isEmpty())
+        {
+            lowerBound = binarySearch(lowerBound, upperBound, start, internalComparator());
+            if (lowerBound < 0)
+                lowerBound = -lowerBound - 1;
+        }
+
+        if (!finish.isEmpty())
+        {
+            upperBound = binarySearch(lowerBound, upperBound, finish, internalComparator());
+            upperBound = upperBound < 0
+                       ? -upperBound - 1
+                       : upperBound + 1; // upperBound is exclusive for the iterators
         }
+
+        // If we're going backwards (wrt our sort order) we store the startIdx and use it as our upper bound next round
+        if (iter != null)
+            iter.previousSliceEnd = invert ? lowerBound : upperBound;
+
+        return invert
+             ? new BackwardsCellIterator(lowerBound, upperBound)
+             : new ForwardsCellIterator(lowerBound, upperBound);
     }
 
-    private class ReverseSortedCollection extends AbstractCollection<Cell>
+    private final class BackwardsCellIterator implements Iterator<Cell>
     {
-        public int size()
+        private int idx, end;
+        private boolean shouldCallNext = true;
+
+        // lowerBound inclusive, upperBound exclusive
+        private BackwardsCellIterator(int lowerBound, int upperBound)
         {
-            return size;
+            idx = upperBound - 1;
+            end = lowerBound - 1;
         }
 
-        public Iterator<Cell> iterator()
+        public boolean hasNext()
         {
-            return new Iterator<Cell>()
-            {
-                int idx = size - 1;
-                boolean shouldCallNext = true;
-
-                public boolean hasNext()
-                {
-                    return idx >= 0;
-                }
-
-                public Cell next()
-                {
-                    shouldCallNext = false;
-                    return cells[idx--];
-                }
-
-                public void remove()
-                {
-                    if (shouldCallNext)
-                        throw new IllegalStateException();
-                    internalRemove(idx + 1);
-                    shouldCallNext = true;
-                    sortedSize--;
-                }
-            };
+            return idx > end;
+        }
+
+        public Cell next()
+        {
+            shouldCallNext = false;
+            return cells[idx--];
+        }
+
+        public void remove()
+        {
+            if (shouldCallNext)
+                throw new IllegalStateException();
+            shouldCallNext = true;
+            internalRemove(idx + 1);
+            sortedSize--;
         }
     }
 
-    private class ForwardSortedCollection extends AbstractCollection<Cell>
+    private final class ForwardsCellIterator implements Iterator<Cell>
     {
+        private int idx, end;
+        private boolean shouldCallNext = true;
+
+        // lowerBound inclusive, upperBound exclusive
+        private ForwardsCellIterator(int lowerBound, int upperBound)
+        {
+            idx = lowerBound;
+            end = upperBound;
+        }
+
+        public boolean hasNext()
+        {
+            return idx < end;
+        }
+
+        public Cell next()
+        {
+            shouldCallNext = false;
+            return cells[idx++];
+        }
+
+        public void remove()
+        {
+            if (shouldCallNext)
+                throw new IllegalStateException();
+            shouldCallNext = true;
+            internalRemove(--idx);
+            sortedSize--;
+            end--;
+        }
+    }
+
+    private final class CellCollection extends AbstractCollection<Cell>
+    {
+        private final boolean invert;
+
+        private CellCollection(boolean invert)
+        {
+            this.invert = invert;
+        }
+
         public int size()
         {
-            return size;
+            return getColumnCount();
         }
 
         public Iterator<Cell> iterator()
         {
-            return new Iterator<Cell>()
-            {
-                int idx = 0;
-                boolean shouldCallNext = true;
-
-                public boolean hasNext()
-                {
-                    return idx < size;
-                }
-
-                public Cell next()
-                {
-                    shouldCallNext = false;
-                    return cells[idx++];
-                }
-
-                public void remove()
-                {
-                    if (shouldCallNext)
-                        throw new IllegalStateException();
-                    internalRemove(--idx);
-                    shouldCallNext = true;
-                    sortedSize--;
-                }
-            };
+            maybeSortCells();
+            return invert
+                 ? new BackwardsCellIterator(0, size)
+                 : new ForwardsCellIterator(0, size);
         }
     }
 }

http://git-wip-us.apache.org/repos/asf/cassandra/blob/9881ea6b/src/java/org/apache/cassandra/db/AtomicBTreeColumns.java
----------------------------------------------------------------------
diff --git a/src/java/org/apache/cassandra/db/AtomicBTreeColumns.java b/src/java/org/apache/cassandra/db/AtomicBTreeColumns.java
index 20fe64c..27eb46d 100644
--- a/src/java/org/apache/cassandra/db/AtomicBTreeColumns.java
+++ b/src/java/org/apache/cassandra/db/AtomicBTreeColumns.java
@@ -27,16 +27,15 @@ import java.util.concurrent.atomic.AtomicReferenceFieldUpdater;
 
 import com.google.common.base.Function;
 import com.google.common.base.Functions;
+import com.google.common.collect.AbstractIterator;
 import com.google.common.collect.Iterators;
 
 import org.apache.cassandra.config.CFMetaData;
 import org.apache.cassandra.db.composites.CellName;
 import org.apache.cassandra.db.composites.Composite;
 import org.apache.cassandra.db.filter.ColumnSlice;
-import org.apache.cassandra.db.index.SecondaryIndexManager;
 import org.apache.cassandra.utils.ObjectSizes;
 import org.apache.cassandra.utils.btree.BTree;
-import org.apache.cassandra.utils.btree.BTreeSet;
 import org.apache.cassandra.utils.btree.UpdateFunction;
 import org.apache.cassandra.utils.concurrent.OpOrder;
 import org.apache.cassandra.utils.memory.MemtableAllocator;
@@ -199,6 +198,11 @@ public class AtomicBTreeColumns extends ColumnFamily
         throw new UnsupportedOperationException();
     }
 
+    public void maybeAppendColumn(Cell cell, DeletionInfo.InOrderTester tester, int gcBefore)
+    {
+        throw new UnsupportedOperationException();
+    }
+
     public void addAll(ColumnFamily cf)
     {
         throw new UnsupportedOperationException();
@@ -216,12 +220,12 @@ public class AtomicBTreeColumns extends ColumnFamily
 
     private Comparator<Object> asymmetricComparator()
     {
-        final Comparator<? super CellName> cmp = metadata.comparator;
+        final Comparator<Composite> cmp = metadata.comparator;
         return new Comparator<Object>()
         {
             public int compare(Object o1, Object o2)
             {
-                return cmp.compare((CellName) o1, ((Cell) o2).name());
+                return cmp.compare((Composite) o1, ((Cell) o2).name());
             }
         };
     }
@@ -270,12 +274,16 @@ public class AtomicBTreeColumns extends ColumnFamily
 
     public Iterator<Cell> iterator(ColumnSlice[] slices)
     {
-        return new ColumnSlice.NavigableSetIterator(new BTreeSet<>(ref.tree, getComparator().columnComparator()), slices);
+        return slices.length == 1
+             ? slice(ref.tree, asymmetricComparator(), slices[0].start, slices[0].finish, true)
+             : new SliceIterator(ref.tree, asymmetricComparator(), true, slices);
     }
 
     public Iterator<Cell> reverseIterator(ColumnSlice[] slices)
     {
-        return new ColumnSlice.NavigableSetIterator(new BTreeSet<>(ref.tree, getComparator().columnComparator()).descendingSet(), slices);
+        return slices.length == 1
+             ? slice(ref.tree, asymmetricComparator(), slices[0].finish, slices[0].start, false)
+             : new SliceIterator(ref.tree, asymmetricComparator(), false, slices);
     }
 
     public boolean isInsertReversed()
@@ -299,11 +307,6 @@ public class AtomicBTreeColumns extends ColumnFamily
         {
             return new Holder(this.tree, info);
         }
-
-        private Iterator<Cell> cellRange(Comparator<Cell> comparator, Composite start, Composite finish)
-        {
-            return new ColumnSlice.NavigableSetIterator(new BTreeSet<>(tree, comparator), new ColumnSlice[]{ new ColumnSlice(start, finish) });
-        }
     }
 
     // the function we provide to the btree utilities to perform any column replacements
@@ -398,4 +401,55 @@ public class AtomicBTreeColumns extends ColumnFamily
             reclaimer.commit();
         }
     }
+
+    private static class SliceIterator extends AbstractIterator<Cell>
+    {
+        private final Object[] btree;
+        private final boolean forwards;
+        private final Comparator<Object> comparator;
+        private final ColumnSlice[] slices;
+
+        private int idx = 0;
+        private Iterator<Cell> currentSlice;
+
+        SliceIterator(Object[] btree, Comparator<Object> comparator, boolean forwards, ColumnSlice[] slices)
+        {
+            this.btree = btree;
+            this.comparator = comparator;
+            this.slices = slices;
+            this.forwards = forwards;
+        }
+
+        protected Cell computeNext()
+        {
+            if (currentSlice == null)
+            {
+                if (idx >= slices.length)
+                    return endOfData();
+
+                ColumnSlice slice = slices[idx++];
+                if (forwards)
+                    currentSlice = slice(btree, comparator, slice.start, slice.finish, true);
+                else
+                    currentSlice = slice(btree, comparator, slice.finish, slice.start, false);
+            }
+
+            if (currentSlice.hasNext())
+                return currentSlice.next();
+
+            currentSlice = null;
+            return computeNext();
+        }
+    }
+
+    private static Iterator<Cell> slice(Object[] btree, Comparator<Object> comparator, Composite start, Composite finish, boolean forwards)
+    {
+        return BTree.slice(btree,
+                           comparator,
+                           start.isEmpty() ? null : start,
+                           true,
+                           finish.isEmpty() ? null : finish,
+                           true,
+                           forwards);
+    }
 }

http://git-wip-us.apache.org/repos/asf/cassandra/blob/9881ea6b/src/java/org/apache/cassandra/db/CollationController.java
----------------------------------------------------------------------
diff --git a/src/java/org/apache/cassandra/db/CollationController.java b/src/java/org/apache/cassandra/db/CollationController.java
index f88c1a7..1030ccf 100644
--- a/src/java/org/apache/cassandra/db/CollationController.java
+++ b/src/java/org/apache/cassandra/db/CollationController.java
@@ -17,13 +17,16 @@
  */
 package org.apache.cassandra.db;
 
+import java.io.Closeable;
 import java.util.ArrayList;
 import java.util.Collections;
 import java.util.Iterator;
 import java.util.List;
 import java.util.TreeSet;
 
+import com.google.common.base.Function;
 import com.google.common.collect.Iterables;
+import com.google.common.collect.Iterators;
 
 import org.apache.cassandra.db.columniterator.OnDiskAtomIterator;
 import org.apache.cassandra.db.compaction.SizeTieredCompactionStrategy;
@@ -68,6 +71,7 @@ public class CollationController
     {
         final ColumnFamily container = ArrayBackedSortedColumns.factory.create(cfs.metadata, filter.filter.isReversed());
         List<OnDiskAtomIterator> iterators = new ArrayList<>();
+        boolean isEmpty = true;
         Tracing.trace("Acquiring sstable references");
         ColumnFamilyStore.ViewFragment view = cfs.select(cfs.viewFilter(filter.key));
 
@@ -79,15 +83,15 @@ public class CollationController
                 ColumnFamily cf = memtable.getColumnFamily(filter.key);
                 if (cf != null)
                 {
-                    OnDiskAtomIterator iter = filter.getColumnFamilyIterator(cf);
-                    iterators.add(iter);
-                    filter.delete(container.deletionInfo(), iter.getColumnFamily());
+                    filter.delete(container.deletionInfo(), cf);
+                    isEmpty = false;
+                    Iterator<Cell> iter = filter.getIterator(cf);
                     while (iter.hasNext())
                     {
-                        OnDiskAtom atom = iter.next();
+                        Cell cell = iter.next();
                         if (copyOnHeap)
-                            atom = ((Cell) atom).localCopy(cfs.metadata, HeapAllocator.instance);
-                        container.addAtom(atom);
+                            cell = cell.localCopy(cfs.metadata, HeapAllocator.instance);
+                        container.addColumn(cell);
                     }
                 }
             }
@@ -119,6 +123,7 @@ public class CollationController
                 Tracing.trace("Merging data from sstable {}", sstable.descriptor.generation);
                 OnDiskAtomIterator iter = reducedFilter.getSSTableColumnIterator(sstable);
                 iterators.add(iter);
+                isEmpty = false;
                 if (iter.getColumnFamily() != null)
                 {
                     ColumnFamily cf = iter.getColumnFamily();
@@ -133,7 +138,7 @@ public class CollationController
 
             // we need to distinguish between "there is no data at all for this row" (BF will let us rebuild that efficiently)
             // and "there used to be data, but it's gone now" (we should cache the empty CF so we don't need to rebuild that slower)
-            if (iterators.isEmpty())
+            if (isEmpty)
                 return null;
 
             // do a final collate.  toCollate is boilerplate required to provide a CloseableIterator
@@ -187,7 +192,7 @@ public class CollationController
     {
         Tracing.trace("Acquiring sstable references");
         ColumnFamilyStore.ViewFragment view = cfs.select(cfs.viewFilter(filter.key));
-        List<OnDiskAtomIterator> iterators = new ArrayList<>(Iterables.size(view.memtables) + view.sstables.size());
+        List<Iterator<? extends OnDiskAtom>> iterators = new ArrayList<>(Iterables.size(view.memtables) + view.sstables.size());
         ColumnFamily returnCF = ArrayBackedSortedColumns.factory.create(cfs.metadata, filter.filter.isReversed());
         DeletionInfo returnDeletionInfo = returnCF.deletionInfo();
         try
@@ -195,21 +200,21 @@ public class CollationController
             Tracing.trace("Merging memtable tombstones");
             for (Memtable memtable : view.memtables)
             {
-                ColumnFamily cf = memtable.getColumnFamily(filter.key);
+                final ColumnFamily cf = memtable.getColumnFamily(filter.key);
                 if (cf != null)
                 {
-                    OnDiskAtomIterator iter = filter.getColumnFamilyIterator(cf);
+                    filter.delete(returnDeletionInfo, cf);
+                    Iterator<Cell> iter = filter.getIterator(cf);
                     if (copyOnHeap)
                     {
-                        ColumnFamily newCf = cf.cloneMeShallow(ArrayBackedSortedColumns.factory, false);
-                        for (Cell cell : cf)
+                        iter = Iterators.transform(iter, new Function<Cell, Cell>()
                         {
-                            newCf.addColumn(cell.localCopy(cfs.metadata, HeapAllocator.instance));
-                        }
-                        cf = newCf;
-                        iter = filter.getColumnFamilyIterator(cf);
+                            public Cell apply(Cell cell)
+                            {
+                                return cell.localCopy(cf.metadata, HeapAllocator.instance);
+                            }
+                        });
                     }
-                    filter.delete(returnDeletionInfo, cf);
                     iterators.add(iter);
                 }
             }
@@ -223,7 +228,7 @@ public class CollationController
              *   timestamp(tombstone) > maxTimestamp_s0
              * since we necessarily have
              *   timestamp(tombstone) <= maxTimestamp_s1
-             * In othere words, iterating in maxTimestamp order allow to do our mostRecentTombstone elimination
+             * In other words, iterating in maxTimestamp order allow to do our mostRecentTombstone elimination
              * in one pass, and minimize the number of sstables for which we read a rowTombstone.
              */
             Collections.sort(view.sstables, SSTableReader.maxTimestampComparator);
@@ -308,8 +313,9 @@ public class CollationController
         }
         finally
         {
-            for (OnDiskAtomIterator iter : iterators)
-                FileUtils.closeQuietly(iter);
+            for (Object iter : iterators)
+                if (iter instanceof Closeable)
+                    FileUtils.closeQuietly((Closeable) iter);
         }
     }
 

http://git-wip-us.apache.org/repos/asf/cassandra/blob/9881ea6b/src/java/org/apache/cassandra/db/ColumnFamily.java
----------------------------------------------------------------------
diff --git a/src/java/org/apache/cassandra/db/ColumnFamily.java b/src/java/org/apache/cassandra/db/ColumnFamily.java
index a261d73..45b8eff 100644
--- a/src/java/org/apache/cassandra/db/ColumnFamily.java
+++ b/src/java/org/apache/cassandra/db/ColumnFamily.java
@@ -109,17 +109,6 @@ public abstract class ColumnFamily implements Iterable<Cell>, IRowCacheEntry
         return metadata;
     }
 
-    public void addIfRelevant(Cell cell, DeletionInfo.InOrderTester tester, int gcBefore)
-    {
-        // the cell itself must be not gc-able (it is live, or a still relevant tombstone), (1)
-        // and if its container is deleted, the cell must be changed more recently than the container tombstone (2)
-        if ((cell.getLocalDeletionTime() >= gcBefore) // (1)
-            && (!tester.isDeleted(cell.name(), cell.timestamp())))                                // (2)
-        {
-            addColumn(cell);
-        }
-    }
-
     public void addColumn(CellName name, ByteBuffer value, long timestamp)
     {
         addColumn(name, value, timestamp, 0);
@@ -203,6 +192,12 @@ public abstract class ColumnFamily implements Iterable<Cell>, IRowCacheEntry
     public abstract void addColumn(Cell cell);
 
     /**
+     * Adds a cell if it's non-gc-able and isn't shadowed by a partition/range tombstone with a higher timestamp.
+     * Requires that the cell to add is sorted strictly after the last cell in the container.
+     */
+    public abstract void maybeAppendColumn(Cell cell, DeletionInfo.InOrderTester tester, int gcBefore);
+
+    /**
      * Adds all the columns of a given column map to this column map.
      * This is equivalent to:
      *   <code>

http://git-wip-us.apache.org/repos/asf/cassandra/blob/9881ea6b/src/java/org/apache/cassandra/db/ColumnFamilyStore.java
----------------------------------------------------------------------
diff --git a/src/java/org/apache/cassandra/db/ColumnFamilyStore.java b/src/java/org/apache/cassandra/db/ColumnFamilyStore.java
index 3b02019..1fdcb73 100644
--- a/src/java/org/apache/cassandra/db/ColumnFamilyStore.java
+++ b/src/java/org/apache/cassandra/db/ColumnFamilyStore.java
@@ -44,7 +44,6 @@ import org.apache.cassandra.concurrent.NamedThreadFactory;
 import org.apache.cassandra.concurrent.StageManager;
 import org.apache.cassandra.config.*;
 import org.apache.cassandra.config.CFMetaData.SpeculativeRetry;
-import org.apache.cassandra.db.columniterator.OnDiskAtomIterator;
 import org.apache.cassandra.db.commitlog.CommitLog;
 import org.apache.cassandra.db.commitlog.ReplayPosition;
 import org.apache.cassandra.db.compaction.*;
@@ -1714,10 +1713,8 @@ public class ColumnFamilyStore implements ColumnFamilyStoreMBean
             return null;
 
         ColumnFamily cf = cached.cloneMeShallow(ArrayBackedSortedColumns.factory, filter.filter.isReversed());
-        OnDiskAtomIterator ci = filter.getColumnFamilyIterator(cached);
-
         int gcBefore = gcBefore(filter.timestamp);
-        filter.collateOnDiskAtom(cf, ci, gcBefore);
+        filter.collateOnDiskAtom(cf, filter.getIterator(cached), gcBefore);
         return removeDeletedCF(cf, gcBefore);
     }
 

http://git-wip-us.apache.org/repos/asf/cassandra/blob/9881ea6b/src/java/org/apache/cassandra/db/RowIteratorFactory.java
----------------------------------------------------------------------
diff --git a/src/java/org/apache/cassandra/db/RowIteratorFactory.java b/src/java/org/apache/cassandra/db/RowIteratorFactory.java
index 500291e..5bd2d9b 100644
--- a/src/java/org/apache/cassandra/db/RowIteratorFactory.java
+++ b/src/java/org/apache/cassandra/db/RowIteratorFactory.java
@@ -19,13 +19,14 @@ package org.apache.cassandra.db;
 
 import java.util.*;
 
+import com.google.common.collect.Iterables;
+
 import org.apache.cassandra.db.columniterator.IColumnIteratorFactory;
 import org.apache.cassandra.db.columniterator.LazyColumnIterator;
 import org.apache.cassandra.db.columniterator.OnDiskAtomIterator;
 import org.apache.cassandra.db.filter.QueryFilter;
 import org.apache.cassandra.db.filter.IDiskAtomFilter;
 import org.apache.cassandra.io.sstable.SSTableReader;
-import org.apache.cassandra.io.sstable.SSTableScanner;
 import org.apache.cassandra.utils.CloseableIterator;
 import org.apache.cassandra.utils.MergeIterator;
 
@@ -57,32 +58,26 @@ public class RowIteratorFactory
                                                      final long now)
     {
         // fetch data from current memtable, historical memtables, and SSTables in the correct order.
-        final List<CloseableIterator<OnDiskAtomIterator>> iterators = new ArrayList<CloseableIterator<OnDiskAtomIterator>>();
+        final List<CloseableIterator<OnDiskAtomIterator>> iterators = new ArrayList<>(Iterables.size(memtables) + sstables.size());
 
-        // memtables
         for (Memtable memtable : memtables)
-        {
             iterators.add(new ConvertToColumnIterator(range, memtable.getEntryIterator(range.startKey(), range.stopKey())));
-        }
 
         for (SSTableReader sstable : sstables)
-        {
-            final SSTableScanner scanner = sstable.getScanner(range);
-            iterators.add(scanner);
-        }
+            iterators.add(sstable.getScanner(range));
 
         // reduce rows from all sources into a single row
         return MergeIterator.get(iterators, COMPARE_BY_KEY, new MergeIterator.Reducer<OnDiskAtomIterator, Row>()
         {
             private final int gcBefore = cfs.gcBefore(now);
-            private final List<OnDiskAtomIterator> colIters = new ArrayList<OnDiskAtomIterator>();
+            private final List<OnDiskAtomIterator> colIters = new ArrayList<>();
             private DecoratedKey key;
             private ColumnFamily returnCF;
 
             @Override
             protected void onKeyChange()
             {
-                this.returnCF = ArrayBackedSortedColumns.factory.create(cfs.metadata);
+                this.returnCF = ArrayBackedSortedColumns.factory.create(cfs.metadata, range.columnFilter.isReversed());
             }
 
             public void reduce(OnDiskAtomIterator current)
@@ -150,7 +145,7 @@ public class RowIteratorFactory
             {
                 public OnDiskAtomIterator create()
                 {
-                    return range.columnFilter(entry.getKey().getKey()).getColumnFamilyIterator(entry.getKey(), entry.getValue());
+                    return range.columnFilter(entry.getKey().getKey()).getColumnIterator(entry.getKey(), entry.getValue());
                 }
             });
         }

http://git-wip-us.apache.org/repos/asf/cassandra/blob/9881ea6b/src/java/org/apache/cassandra/db/filter/ColumnSlice.java
----------------------------------------------------------------------
diff --git a/src/java/org/apache/cassandra/db/filter/ColumnSlice.java b/src/java/org/apache/cassandra/db/filter/ColumnSlice.java
index 6821e94..a945114 100644
--- a/src/java/org/apache/cassandra/db/filter/ColumnSlice.java
+++ b/src/java/org/apache/cassandra/db/filter/ColumnSlice.java
@@ -20,14 +20,8 @@ package org.apache.cassandra.db.filter;
 import java.io.*;
 import java.nio.ByteBuffer;
 import java.util.Comparator;
-import java.util.Iterator;
 import java.util.List;
-import java.util.NavigableSet;
 
-import com.google.common.collect.AbstractIterator;
-
-import org.apache.cassandra.config.CFMetaData;
-import org.apache.cassandra.cql3.ColumnIdentifier;
 import org.apache.cassandra.db.*;
 import org.apache.cassandra.db.composites.*;
 import org.apache.cassandra.db.marshal.AbstractType;
@@ -35,7 +29,6 @@ import org.apache.cassandra.io.ISerializer;
 import org.apache.cassandra.io.IVersionedSerializer;
 import org.apache.cassandra.io.util.DataOutputPlus;
 import org.apache.cassandra.utils.ByteBufferUtil;
-import org.apache.cassandra.utils.memory.AbstractAllocator;
 
 public class ColumnSlice
 {
@@ -167,143 +160,4 @@ public class ColumnSlice
             return serializer.serializedSize(cs.start, TypeSizes.NATIVE) + serializer.serializedSize(cs.finish, TypeSizes.NATIVE);
         }
     }
-
-    public static class NavigableSetIterator extends AbstractIterator<Cell>
-    {
-        private final NavigableSet<Cell> set;
-        private final ColumnSlice[] slices;
-
-        private int idx = 0;
-        private Iterator<Cell> currentSlice;
-
-        public NavigableSetIterator(NavigableSet<Cell> set, ColumnSlice[] slices)
-        {
-            this.set = set;
-            this.slices = slices;
-        }
-
-        protected Cell computeNext()
-        {
-            if (currentSlice == null)
-            {
-                if (idx >= slices.length)
-                    return endOfData();
-
-                ColumnSlice slice = slices[idx++];
-                // We specialize the case of start == "" and finish = "" because it is slightly more efficient,
-                // but also they have a specific meaning (namely, they always extend to the beginning/end of the range).
-                if (slice.start.isEmpty())
-                {
-                    if (slice.finish.isEmpty())
-                        currentSlice = set.iterator();
-                    else
-                        currentSlice = set.headSet(fakeCell(slice.finish), true).iterator();
-                }
-                else if (slice.finish.isEmpty())
-                {
-                    currentSlice = set.tailSet(fakeCell(slice.start), true).iterator();
-                }
-                else
-                {
-                    currentSlice = set.subSet(fakeCell(slice.start), true, fakeCell(slice.finish), true).iterator();
-                }
-            }
-
-            if (currentSlice.hasNext())
-                return currentSlice.next();
-
-            currentSlice = null;
-            return computeNext();
-        }
-    }
-
-    private static Cell fakeCell(Composite name)
-    {
-        return new BufferCell(name instanceof CellName ? (CellName) name : new FakeCellName(name), ByteBufferUtil.EMPTY_BYTE_BUFFER);
-    }
-
-    /*
-    * We need to take a slice (headMap/tailMap/subMap) of a CellName map
-    * based on a Composite. While CellName and Composite are comparable
-    * and so this should work, I haven't found how to generify it properly.
-    * So instead we create a "fake" CellName object that just encapsulate
-    * the prefix. I might not be a valid CellName with respect to the CF
-    * CellNameType, but this doesn't matter here (since we only care about
-    * comparison). This is arguably a bit of a hack.
-    */
-    private static class FakeCellName extends AbstractComposite implements CellName
-    {
-        private final Composite prefix;
-
-        private FakeCellName(Composite prefix)
-        {
-            this.prefix = prefix;
-        }
-
-        public int size()
-        {
-            return prefix.size();
-        }
-
-        public boolean isStatic()
-        {
-            return prefix.isStatic();
-        }
-
-        public ByteBuffer get(int i)
-        {
-            return prefix.get(i);
-        }
-
-        public Composite.EOC eoc()
-        {
-            return prefix.eoc();
-        }
-
-        public ByteBuffer toByteBuffer()
-        {
-            return prefix.toByteBuffer();
-        }
-
-        public int clusteringSize()
-        {
-            throw new UnsupportedOperationException();
-        }
-
-        public ColumnIdentifier cql3ColumnName(CFMetaData metadata)
-        {
-            throw new UnsupportedOperationException();
-        }
-
-        public ByteBuffer collectionElement()
-        {
-            throw new UnsupportedOperationException();
-        }
-
-        public boolean isCollectionCell()
-        {
-            throw new UnsupportedOperationException();
-        }
-
-        public boolean isSameCQL3RowAs(CellNameType type, CellName other)
-        {
-            throw new UnsupportedOperationException();
-        }
-
-        public CellName copy(CFMetaData cfm, AbstractAllocator allocator)
-        {
-            throw new UnsupportedOperationException();
-        }
-
-        @Override
-        public long excessHeapSizeExcludingData()
-        {
-            throw new UnsupportedOperationException();
-        }
-
-        public long unsharedHeapSize()
-        {
-            throw new UnsupportedOperationException();
-        }
-    }
 }

http://git-wip-us.apache.org/repos/asf/cassandra/blob/9881ea6b/src/java/org/apache/cassandra/db/filter/ExtendedFilter.java
----------------------------------------------------------------------
diff --git a/src/java/org/apache/cassandra/db/filter/ExtendedFilter.java b/src/java/org/apache/cassandra/db/filter/ExtendedFilter.java
index 2659439..5e410bc 100644
--- a/src/java/org/apache/cassandra/db/filter/ExtendedFilter.java
+++ b/src/java/org/apache/cassandra/db/filter/ExtendedFilter.java
@@ -19,6 +19,7 @@ package org.apache.cassandra.db.filter;
 
 import java.nio.ByteBuffer;
 import java.util.Collections;
+import java.util.Iterator;
 import java.util.List;
 import java.util.SortedSet;
 import java.util.TreeSet;
@@ -34,7 +35,6 @@ import org.apache.cassandra.db.composites.CellName;
 import org.apache.cassandra.db.composites.Composite;
 import org.apache.cassandra.db.marshal.AbstractType;
 import org.apache.cassandra.db.marshal.CompositeType;
-import org.apache.cassandra.db.columniterator.OnDiskAtomIterator;
 
 /**
  * Extends a column filter (IFilter) to include a number of IndexExpression.
@@ -279,7 +279,7 @@ public abstract class ExtendedFilter
 
             ColumnFamily pruned = data.cloneMeShallow();
             IDiskAtomFilter filter = dataRange.columnFilter(rowKey.getKey());
-            OnDiskAtomIterator iter = filter.getColumnFamilyIterator(rowKey, data);
+            Iterator<Cell> iter = filter.getColumnIterator(data);
             filter.collectReducedColumns(pruned, QueryFilter.gatherTombstones(pruned, iter), cfs.gcBefore(timestamp), timestamp);
             return pruned;
         }

http://git-wip-us.apache.org/repos/asf/cassandra/blob/9881ea6b/src/java/org/apache/cassandra/db/filter/IDiskAtomFilter.java
----------------------------------------------------------------------
diff --git a/src/java/org/apache/cassandra/db/filter/IDiskAtomFilter.java b/src/java/org/apache/cassandra/db/filter/IDiskAtomFilter.java
index e44a1a7..3750c75 100644
--- a/src/java/org/apache/cassandra/db/filter/IDiskAtomFilter.java
+++ b/src/java/org/apache/cassandra/db/filter/IDiskAtomFilter.java
@@ -45,7 +45,9 @@ public interface IDiskAtomFilter
      * returns an iterator that returns columns from the given columnFamily
      * matching the Filter criteria in sorted order.
      */
-    public OnDiskAtomIterator getColumnFamilyIterator(DecoratedKey key, ColumnFamily cf);
+    public Iterator<Cell> getColumnIterator(ColumnFamily cf);
+
+    public OnDiskAtomIterator getColumnIterator(DecoratedKey key, ColumnFamily cf);
 
     /**
      * Get an iterator that returns columns from the given SSTable using the opened file

http://git-wip-us.apache.org/repos/asf/cassandra/blob/9881ea6b/src/java/org/apache/cassandra/db/filter/NamesQueryFilter.java
----------------------------------------------------------------------
diff --git a/src/java/org/apache/cassandra/db/filter/NamesQueryFilter.java b/src/java/org/apache/cassandra/db/filter/NamesQueryFilter.java
index 37b8d44..0e0643f 100644
--- a/src/java/org/apache/cassandra/db/filter/NamesQueryFilter.java
+++ b/src/java/org/apache/cassandra/db/filter/NamesQueryFilter.java
@@ -71,10 +71,17 @@ public class NamesQueryFilter implements IDiskAtomFilter
        return new NamesQueryFilter(newColumns, countCQL3Rows);
     }
 
-    public OnDiskAtomIterator getColumnFamilyIterator(DecoratedKey key, ColumnFamily cf)
+    @SuppressWarnings("unchecked")
+    public Iterator<Cell> getColumnIterator(ColumnFamily cf)
     {
         assert cf != null;
-        return new ByNameColumnIterator(columns.iterator(), cf, key);
+        return (Iterator<Cell>) (Iterator<?>) new ByNameColumnIterator(columns.iterator(), null, cf);
+    }
+
+    public OnDiskAtomIterator getColumnIterator(DecoratedKey key, ColumnFamily cf)
+    {
+        assert cf != null;
+        return new ByNameColumnIterator(columns.iterator(), key, cf);
     }
 
     public OnDiskAtomIterator getSSTableColumnIterator(SSTableReader sstable, DecoratedKey key)
@@ -91,7 +98,7 @@ public class NamesQueryFilter implements IDiskAtomFilter
     {
         DeletionInfo.InOrderTester tester = container.inOrderDeletionTester();
         while (reducedColumns.hasNext())
-            container.addIfRelevant(reducedColumns.next(), tester, gcBefore);
+            container.maybeAppendColumn(reducedColumns.next(), tester, gcBefore);
     }
 
     public Comparator<Cell> getColumnComparator(CellNameType comparator)
@@ -186,23 +193,13 @@ public class NamesQueryFilter implements IDiskAtomFilter
         private final DecoratedKey key;
         private final Iterator<CellName> iter;
 
-        public ByNameColumnIterator(Iterator<CellName> iter, ColumnFamily cf, DecoratedKey key)
+        public ByNameColumnIterator(Iterator<CellName> iter, DecoratedKey key, ColumnFamily cf)
         {
             this.iter = iter;
             this.cf = cf;
             this.key = key;
         }
 
-        public ColumnFamily getColumnFamily()
-        {
-            return cf;
-        }
-
-        public DecoratedKey getKey()
-        {
-            return key;
-        }
-
         protected OnDiskAtom computeNext()
         {
             while (iter.hasNext())
@@ -215,6 +212,16 @@ public class NamesQueryFilter implements IDiskAtomFilter
             return endOfData();
         }
 
+        public ColumnFamily getColumnFamily()
+        {
+            return cf;
+        }
+
+        public DecoratedKey getKey()
+        {
+            return key;
+        }
+
         public void close() throws IOException { }
     }
 

http://git-wip-us.apache.org/repos/asf/cassandra/blob/9881ea6b/src/java/org/apache/cassandra/db/filter/QueryFilter.java
----------------------------------------------------------------------
diff --git a/src/java/org/apache/cassandra/db/filter/QueryFilter.java b/src/java/org/apache/cassandra/db/filter/QueryFilter.java
index 8236912..f58fa9f 100644
--- a/src/java/org/apache/cassandra/db/filter/QueryFilter.java
+++ b/src/java/org/apache/cassandra/db/filter/QueryFilter.java
@@ -51,10 +51,10 @@ public class QueryFilter
         this.timestamp = timestamp;
     }
 
-    public OnDiskAtomIterator getColumnFamilyIterator(ColumnFamily cf)
+    public Iterator<Cell> getIterator(ColumnFamily cf)
     {
         assert cf != null;
-        return filter.getColumnFamilyIterator(key, cf);
+        return filter.getColumnIterator(cf);
     }
 
     public OnDiskAtomIterator getSSTableColumnIterator(SSTableReader sstable)
@@ -62,45 +62,62 @@ public class QueryFilter
         return filter.getSSTableColumnIterator(sstable, key);
     }
 
-    public void collateOnDiskAtom(final ColumnFamily returnCF, List<? extends Iterator<? extends OnDiskAtom>> toCollate, final int gcBefore)
+    public void collateOnDiskAtom(ColumnFamily returnCF,
+                                  List<? extends Iterator<? extends OnDiskAtom>> toCollate,
+                                  int gcBefore)
     {
         collateOnDiskAtom(returnCF, toCollate, filter, gcBefore, timestamp);
     }
 
-    public static void collateOnDiskAtom(final ColumnFamily returnCF, List<? extends Iterator<? extends OnDiskAtom>> toCollate, IDiskAtomFilter filter, int gcBefore, long timestamp)
+    public static void collateOnDiskAtom(ColumnFamily returnCF,
+                                         List<? extends Iterator<? extends OnDiskAtom>> toCollate,
+                                         IDiskAtomFilter filter,
+                                         int gcBefore,
+                                         long timestamp)
     {
-        List<Iterator<Cell>> filteredIterators = new ArrayList<Iterator<Cell>>(toCollate.size());
+        List<Iterator<Cell>> filteredIterators = new ArrayList<>(toCollate.size());
         for (Iterator<? extends OnDiskAtom> iter : toCollate)
             filteredIterators.add(gatherTombstones(returnCF, iter));
         collateColumns(returnCF, filteredIterators, filter, gcBefore, timestamp);
     }
 
-    /**
-     * When there is only a single source of atoms, we can skip the collate step
-     */
+    // When there is only a single source of atoms, we can skip the collate step
     public void collateOnDiskAtom(ColumnFamily returnCF, Iterator<? extends OnDiskAtom> toCollate, int gcBefore)
     {
-        Iterator<Cell> columns = gatherTombstones(returnCF, toCollate);
-        filter.collectReducedColumns(returnCF, columns, gcBefore, timestamp);
+        filter.collectReducedColumns(returnCF, gatherTombstones(returnCF, toCollate), gcBefore, timestamp);
     }
 
-    public void collateColumns(final ColumnFamily returnCF, List<? extends Iterator<Cell>> toCollate, int gcBefore)
+    public void collateColumns(ColumnFamily returnCF, List<? extends Iterator<Cell>> toCollate, int gcBefore)
     {
         collateColumns(returnCF, toCollate, filter, gcBefore, timestamp);
     }
 
-    public static void collateColumns(final ColumnFamily returnCF, List<? extends Iterator<Cell>> toCollate, IDiskAtomFilter filter, int gcBefore, long timestamp)
+    public static void collateColumns(ColumnFamily returnCF,
+                                      List<? extends Iterator<Cell>> toCollate,
+                                      IDiskAtomFilter filter,
+                                      int gcBefore,
+                                      long timestamp)
+    {
+        Comparator<Cell> comparator = filter.getColumnComparator(returnCF.getComparator());
+
+        Iterator<Cell> reduced = toCollate.size() == 1
+                               ? toCollate.get(0)
+                               : MergeIterator.get(toCollate, comparator, getReducer(comparator));
+
+        filter.collectReducedColumns(returnCF, reduced, gcBefore, timestamp);
+    }
+
+    private static MergeIterator.Reducer<Cell, Cell> getReducer(final Comparator<Cell> comparator)
     {
-        final Comparator<Cell> fcomp = filter.getColumnComparator(returnCF.getComparator());
         // define a 'reduced' iterator that merges columns w/ the same name, which
         // greatly simplifies computing liveColumns in the presence of tombstones.
-        MergeIterator.Reducer<Cell, Cell> reducer = new MergeIterator.Reducer<Cell, Cell>()
+        return new MergeIterator.Reducer<Cell, Cell>()
         {
             Cell current;
 
             public void reduce(Cell next)
             {
-                assert current == null || fcomp.compare(current, next) == 0;
+                assert current == null || comparator.compare(current, next) == 0;
                 current = current == null ? next : current.reconcile(next);
             }
 
@@ -111,10 +128,13 @@ public class QueryFilter
                 current = null;
                 return toReturn;
             }
-        };
-        Iterator<Cell> reduced = MergeIterator.get(toCollate, fcomp, reducer);
 
-        filter.collectReducedColumns(returnCF, reduced, gcBefore, timestamp);
+            @Override
+            public boolean trivialReduceIsTrivial()
+            {
+                return true;
+            }
+        };
     }
 
     /**

http://git-wip-us.apache.org/repos/asf/cassandra/blob/9881ea6b/src/java/org/apache/cassandra/db/filter/SliceQueryFilter.java
----------------------------------------------------------------------
diff --git a/src/java/org/apache/cassandra/db/filter/SliceQueryFilter.java b/src/java/org/apache/cassandra/db/filter/SliceQueryFilter.java
index 3d3e820..e24f68b 100644
--- a/src/java/org/apache/cassandra/db/filter/SliceQueryFilter.java
+++ b/src/java/org/apache/cassandra/db/filter/SliceQueryFilter.java
@@ -35,7 +35,6 @@ import org.apache.cassandra.db.composites.CType;
 import org.apache.cassandra.db.composites.CellName;
 import org.apache.cassandra.db.composites.CellNameType;
 import org.apache.cassandra.db.composites.Composite;
-import org.apache.cassandra.db.marshal.AbstractType;
 import org.apache.cassandra.io.IVersionedSerializer;
 import org.apache.cassandra.io.sstable.SSTableReader;
 import org.apache.cassandra.io.util.DataOutputPlus;
@@ -110,19 +109,17 @@ public class SliceQueryFilter implements IDiskAtomFilter
     {
         Comparator<Composite> cmp = reversed ? comparator.reverseComparator() : comparator;
 
-        List<ColumnSlice> newSlices = new ArrayList<ColumnSlice>();
+        List<ColumnSlice> newSlices = new ArrayList<>(slices.length);
         boolean pastNewStart = false;
-        for (int i = 0; i < slices.length; i++)
+        for (ColumnSlice slice : slices)
         {
-            ColumnSlice slice = slices[i];
-
             if (pastNewStart)
             {
                 newSlices.add(slice);
                 continue;
             }
 
-            if (slices[i].isBefore(cmp, newStart))
+            if (slice.isBefore(cmp, newStart))
                 continue;
 
             if (slice.includes(cmp, newStart))
@@ -135,15 +132,16 @@ public class SliceQueryFilter implements IDiskAtomFilter
         return withUpdatedSlices(newSlices.toArray(new ColumnSlice[newSlices.size()]));
     }
 
-    public SliceQueryFilter withUpdatedSlice(Composite start, Composite finish)
+    public Iterator<Cell> getColumnIterator(ColumnFamily cf)
     {
-        return new SliceQueryFilter(new ColumnSlice[]{ new ColumnSlice(start, finish) }, reversed, count, compositesToGroup);
+        assert cf != null;
+        return reversed ? cf.reverseIterator(slices) : cf.iterator(slices);
     }
 
-    public OnDiskAtomIterator getColumnFamilyIterator(final DecoratedKey key, final ColumnFamily cf)
+    public OnDiskAtomIterator getColumnIterator(final DecoratedKey key, final ColumnFamily cf)
     {
         assert cf != null;
-        final Iterator<Cell> filteredIter = reversed ? cf.reverseIterator(slices) : cf.iterator(slices);
+        final Iterator<Cell> iter = getColumnIterator(cf);
 
         return new OnDiskAtomIterator()
         {
@@ -159,12 +157,12 @@ public class SliceQueryFilter implements IDiskAtomFilter
 
             public boolean hasNext()
             {
-                return filteredIter.hasNext();
+                return iter.hasNext();
             }
 
             public OnDiskAtom next()
             {
-                return filteredIter.next();
+                return iter.next();
             }
 
             public void close() throws IOException { }
@@ -216,7 +214,7 @@ public class SliceQueryFilter implements IDiskAtomFilter
                 throw new TombstoneOverwhelmingException();
             }
 
-            container.addIfRelevant(cell, tester, gcBefore);
+            container.maybeAppendColumn(cell, tester, gcBefore);
         }
 
         Tracing.trace("Read {} live and {} tombstoned cells", columnCounter.live(), columnCounter.ignored());

http://git-wip-us.apache.org/repos/asf/cassandra/blob/9881ea6b/src/java/org/apache/cassandra/service/RowDataResolver.java
----------------------------------------------------------------------
diff --git a/src/java/org/apache/cassandra/service/RowDataResolver.java b/src/java/org/apache/cassandra/service/RowDataResolver.java
index b7d1682..f5eee40 100644
--- a/src/java/org/apache/cassandra/service/RowDataResolver.java
+++ b/src/java/org/apache/cassandra/service/RowDataResolver.java
@@ -145,16 +145,13 @@ public class RowDataResolver extends AbstractRowResolver
             return null;
 
         // mimic the collectCollatedColumn + removeDeleted path that getColumnFamily takes.
-        // this will handle removing columns and subcolumns that are supressed by a row or
+        // this will handle removing columns and subcolumns that are suppressed by a row or
         // supercolumn tombstone.
         QueryFilter filter = new QueryFilter(null, resolved.metadata().cfName, new IdentityQueryFilter(), now);
-        List<CloseableIterator<Cell>> iters = new ArrayList<CloseableIterator<Cell>>();
+        List<CloseableIterator<Cell>> iters = new ArrayList<>(Iterables.size(versions));
         for (ColumnFamily version : versions)
-        {
-            if (version == null)
-                continue;
-            iters.add(FBUtilities.closeableIterator(version.iterator()));
-        }
+            if (version != null)
+                iters.add(FBUtilities.closeableIterator(version.iterator()));
         filter.collateColumns(resolved, iters, Integer.MIN_VALUE);
         return ColumnFamilyStore.removeDeleted(resolved, Integer.MIN_VALUE);
     }

http://git-wip-us.apache.org/repos/asf/cassandra/blob/9881ea6b/src/java/org/apache/cassandra/utils/MergeIterator.java
----------------------------------------------------------------------
diff --git a/src/java/org/apache/cassandra/utils/MergeIterator.java b/src/java/org/apache/cassandra/utils/MergeIterator.java
index 4c89edb..e61326e 100644
--- a/src/java/org/apache/cassandra/utils/MergeIterator.java
+++ b/src/java/org/apache/cassandra/utils/MergeIterator.java
@@ -35,15 +35,17 @@ public abstract class MergeIterator<In,Out> extends AbstractIterator<Out> implem
         this.reducer = reducer;
     }
 
-    public static <In, Out> IMergeIterator<In, Out> get(final List<? extends Iterator<In>> sources,
-                                                    Comparator<In> comparator,
-                                                    final Reducer<In, Out> reducer)
+    public static <In, Out> IMergeIterator<In, Out> get(List<? extends Iterator<In>> sources,
+                                                        Comparator<In> comparator,
+                                                        Reducer<In, Out> reducer)
     {
         if (sources.size() == 1)
+        {
             return reducer.trivialReduceIsTrivial()
-                   ? new TrivialOneToOne<In, Out>(sources, reducer)
-                   : new OneToOne<In, Out>(sources, reducer);
-        return new ManyToOne<In, Out>(sources, comparator, reducer);
+                 ? new TrivialOneToOne<>(sources, reducer)
+                 : new OneToOne<>(sources, reducer);
+        }
+        return new ManyToOne<>(sources, comparator, reducer);
     }
 
     public Iterable<? extends Iterator<In>> iterators()
@@ -80,16 +82,16 @@ public abstract class MergeIterator<In,Out> extends AbstractIterator<Out> implem
         public ManyToOne(List<? extends Iterator<In>> iters, Comparator<In> comp, Reducer<In, Out> reducer)
         {
             super(iters, reducer);
-            this.queue = new PriorityQueue<Candidate<In>>(Math.max(1, iters.size()));
+            this.queue = new PriorityQueue<>(Math.max(1, iters.size()));
             for (Iterator<In> iter : iters)
             {
-                Candidate<In> candidate = new Candidate<In>(iter, comp);
+                Candidate<In> candidate = new Candidate<>(iter, comp);
                 if (!candidate.advance())
                     // was empty
                     continue;
                 this.queue.add(candidate);
             }
-            this.candidates = new ArrayDeque<Candidate<In>>(queue.size());
+            this.candidates = new ArrayDeque<>(queue.size());
         }
 
         protected final Out computeNext()
@@ -174,8 +176,8 @@ public abstract class MergeIterator<In,Out> extends AbstractIterator<Out> implem
         protected abstract Out getReduced();
 
         /**
-         * Called at the begining of each new key, before any reduce is called.
-         * To be overriden by implementing classes.
+         * Called at the beginning of each new key, before any reduce is called.
+         * To be overridden by implementing classes.
          */
         protected void onKeyChange() {}
 
@@ -215,6 +217,7 @@ public abstract class MergeIterator<In,Out> extends AbstractIterator<Out> implem
             source = sources.get(0);
         }
 
+        @SuppressWarnings("unchecked")
         protected Out computeNext()
         {
             if (!source.hasNext())

http://git-wip-us.apache.org/repos/asf/cassandra/blob/9881ea6b/src/java/org/apache/cassandra/utils/btree/BTree.java
----------------------------------------------------------------------
diff --git a/src/java/org/apache/cassandra/utils/btree/BTree.java b/src/java/org/apache/cassandra/utils/btree/BTree.java
index eb8295c..1145d12 100644
--- a/src/java/org/apache/cassandra/utils/btree/BTree.java
+++ b/src/java/org/apache/cassandra/utils/btree/BTree.java
@@ -196,9 +196,9 @@ public class BTree
      * @param <V>
      * @return
      */
-    public static <V> Cursor<V> slice(Object[] btree, boolean forwards)
+    public static <V> Cursor<V, V> slice(Object[] btree, boolean forwards)
     {
-        Cursor<V> r = new Cursor<>();
+        Cursor<V, V> r = new Cursor<>();
         r.reset(btree, forwards);
         return r;
     }
@@ -214,9 +214,9 @@ public class BTree
      * @param <V>
      * @return
      */
-    public static <V> Cursor<V> slice(Object[] btree, Comparator<V> comparator, V start, V end, boolean forwards)
+    public static <K, V extends K> Cursor<K, V> slice(Object[] btree, Comparator<K> comparator, K start, K end, boolean forwards)
     {
-        Cursor<V> r = new Cursor<>();
+        Cursor<K, V> r = new Cursor<>();
         r.reset(btree, comparator, start, end, forwards);
         return r;
     }
@@ -232,9 +232,9 @@ public class BTree
      * @param <V>
      * @return
      */
-    public static <V> Cursor<V> slice(Object[] btree, Comparator<V> comparator, V start, boolean startInclusive, V end, boolean endInclusive, boolean forwards)
+    public static <K, V extends K> Cursor<K, V> slice(Object[] btree, Comparator<K> comparator, K start, boolean startInclusive, K end, boolean endInclusive, boolean forwards)
     {
-        Cursor<V> r = new Cursor<>();
+        Cursor<K, V> r = new Cursor<>();
         r.reset(btree, comparator, start, startInclusive, end, endInclusive, forwards);
         return r;
     }

http://git-wip-us.apache.org/repos/asf/cassandra/blob/9881ea6b/src/java/org/apache/cassandra/utils/btree/BTreeSet.java
----------------------------------------------------------------------
diff --git a/src/java/org/apache/cassandra/utils/btree/BTreeSet.java b/src/java/org/apache/cassandra/utils/btree/BTreeSet.java
index e170556..d80b32e 100644
--- a/src/java/org/apache/cassandra/utils/btree/BTreeSet.java
+++ b/src/java/org/apache/cassandra/utils/btree/BTreeSet.java
@@ -47,9 +47,9 @@ public class BTreeSet<V> implements NavigableSet<V>
         return comparator;
     }
 
-    protected Cursor<V> slice(boolean forwards, boolean permitInversion)
+    protected Cursor<V, V> slice(boolean forwards, boolean permitInversion)
     {
-        return BTree.<V>slice(tree, forwards);
+        return BTree.slice(tree, forwards);
     }
 
     @Override
@@ -313,7 +313,7 @@ public class BTreeSet<V> implements NavigableSet<V>
         }
 
         @Override
-        protected Cursor<V> slice(boolean forwards, boolean permitInversion)
+        protected Cursor<V, V> slice(boolean forwards, boolean permitInversion)
         {
             return BTree.slice(tree, comparator, lowerBound, inclusiveLowerBound, upperBound, inclusiveUpperBound, forwards);
         }
@@ -351,7 +351,7 @@ public class BTreeSet<V> implements NavigableSet<V>
         }
 
         @Override
-        protected Cursor<V> slice(boolean forwards, boolean permitInversion)
+        protected Cursor<V, V> slice(boolean forwards, boolean permitInversion)
         {
             return super.slice(permitInversion ? !forwards : forwards, false);
         }

http://git-wip-us.apache.org/repos/asf/cassandra/blob/9881ea6b/src/java/org/apache/cassandra/utils/btree/Cursor.java
----------------------------------------------------------------------
diff --git a/src/java/org/apache/cassandra/utils/btree/Cursor.java b/src/java/org/apache/cassandra/utils/btree/Cursor.java
index bc88442..02e047a 100644
--- a/src/java/org/apache/cassandra/utils/btree/Cursor.java
+++ b/src/java/org/apache/cassandra/utils/btree/Cursor.java
@@ -31,7 +31,7 @@ import static org.apache.cassandra.utils.btree.BTree.isLeaf;
  *
  * @param <V>
  */
-public final class Cursor<V> extends Path implements Iterator<V>
+public final class Cursor<K, V extends K> extends Path implements Iterator<V>
 {
     /*
      * Conceptually, a Cursor derives two Paths, one for the first object in the slice requested (inclusive),
@@ -70,7 +70,7 @@ public final class Cursor<V> extends Path implements Iterator<V>
      * @param upperBound the last item to include, exclusive
      * @param forwards   if false, the cursor will start at the end and move backwards
      */
-    public void reset(Object[] btree, Comparator<V> comparator, V lowerBound, V upperBound, boolean forwards)
+    public void reset(Object[] btree, Comparator<K> comparator, K lowerBound, K upperBound, boolean forwards)
     {
         _reset(btree, comparator, lowerBound, true, upperBound, false, forwards);
     }
@@ -86,12 +86,12 @@ public final class Cursor<V> extends Path implements Iterator<V>
      * @param inclusiveUpperBound should include end in the iterator, if present in the tree
      * @param forwards            if false, the cursor will start at the end and move backwards
      */
-    public void reset(Object[] btree, Comparator<V> comparator, V lowerBound, boolean inclusiveLowerBound, V upperBound, boolean inclusiveUpperBound, boolean forwards)
+    public void reset(Object[] btree, Comparator<K> comparator, K lowerBound, boolean inclusiveLowerBound, K upperBound, boolean inclusiveUpperBound, boolean forwards)
     {
         _reset(btree, comparator, lowerBound, inclusiveLowerBound, upperBound, inclusiveUpperBound, forwards);
     }
 
-    private void _reset(Object[] btree, Comparator<V> comparator, Object lowerBound, boolean inclusiveLowerBound, Object upperBound, boolean inclusiveUpperBound, boolean forwards)
+    private void _reset(Object[] btree, Comparator<K> comparator, Object lowerBound, boolean inclusiveLowerBound, Object upperBound, boolean inclusiveUpperBound, boolean forwards)
     {
         ensureDepth(btree);
         if (lowerBound == null)


Mime
View raw message