cassandra-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From slebre...@apache.org
Subject [1/3] git commit: Improve handling of range tomsbstones for wide partitions
Date Wed, 26 Feb 2014 13:48:55 GMT
Repository: cassandra
Updated Branches:
  refs/heads/cassandra-2.1 5b6d2e40c -> dc38e4b7d


Improve handling of range tomsbstones for wide partitions

patch by m0nstermind; reviewed by slebresne for CASSANDRA-6446


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

Branch: refs/heads/cassandra-2.1
Commit: 74258e2dc1a9720c4de172d9d2342d552f7ac3f7
Parents: e0857f2
Author: Sylvain Lebresne <sylvain@datastax.com>
Authored: Fri Dec 6 12:34:31 2013 +0100
Committer: Sylvain Lebresne <sylvain@datastax.com>
Committed: Wed Feb 26 14:46:18 2014 +0100

----------------------------------------------------------------------
 .../apache/cassandra/db/AtomicBTreeColumns.java |  28 +++--
 .../cassandra/db/CollationController.java       |   6 +-
 .../org/apache/cassandra/db/DeletionInfo.java   |  15 ++-
 .../org/apache/cassandra/db/RangeTombstone.java |   5 +
 .../apache/cassandra/db/RangeTombstoneList.java |  65 ++++++++++--
 .../cassandra/db/filter/IDiskAtomFilter.java    |   2 +
 .../cassandra/db/filter/NamesQueryFilter.java   |  30 ++++++
 .../apache/cassandra/db/filter/QueryFilter.java |   9 ++
 .../cassandra/db/filter/SliceQueryFilter.java   |  41 ++++++++
 .../cassandra/db/RangeTombstoneListTest.java    |  26 ++---
 .../apache/cassandra/db/RangeTombstoneTest.java | 102 +++++++++++++++++++
 .../cassandra/tools/SSTableImportTest.java      |   2 +-
 12 files changed, 293 insertions(+), 38 deletions(-)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/cassandra/blob/74258e2d/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 5cc43d9..80e2995 100644
--- a/src/java/org/apache/cassandra/db/AtomicBTreeColumns.java
+++ b/src/java/org/apache/cassandra/db/AtomicBTreeColumns.java
@@ -33,6 +33,8 @@ import com.google.common.collect.*;
 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.index.SecondaryIndexManager;
 import org.apache.cassandra.db.filter.ColumnSlice;
 import org.apache.cassandra.utils.ObjectSizes;
 import org.apache.cassandra.utils.btree.BTree;
@@ -75,6 +77,8 @@ public class AtomicBTreeColumns extends ColumnFamily
     };
 
     private static final DeletionInfo LIVE = DeletionInfo.live();
+    // This is a small optimization: DeletionInfo is mutable, but we know that we will always
copy it in that class,
+    // so we can safely alias one DeletionInfo.live() reference and avoid some allocations.
     private static final Holder EMPTY = new Holder(BTree.empty(), LIVE);
 
     private volatile Holder ref;
@@ -126,7 +130,8 @@ public class AtomicBTreeColumns extends ColumnFamily
         while (true)
         {
             Holder current = ref;
-            DeletionInfo newDelInfo = current.deletionInfo.copy().add(info);
+            DeletionInfo curDelInfo = current.deletionInfo;
+            DeletionInfo newDelInfo = info.mayModify(curDelInfo) ? curDelInfo.copy().add(info)
: curDelInfo;
             if (refUpdater.compareAndSet(this, current, current.with(newDelInfo)))
                 break;
         }
@@ -233,15 +238,17 @@ public class AtomicBTreeColumns extends ColumnFamily
             DeletionInfo deletionInfo;
             if (cm.deletionInfo().mayModify(current.deletionInfo))
             {
-                if (cm.deletionInfo().hasRanges())
+                if (indexer != SecondaryIndexManager.nullUpdater && cm.deletionInfo().hasRanges())
                 {
-                    for (Iterator<Cell> iter : new Iterator[] { insert.iterator(),
BTree.<Cell>slice(current.tree, true) })
+                    for (Iterator<RangeTombstone> rangeIterator = cm.deletionInfo().rangeIterator();
rangeIterator.hasNext(); )
                     {
-                        while (iter.hasNext())
+                        RangeTombstone rt = rangeIterator.next();
+                        long deleteAt = rt.maxTimestamp();
+                        for (Iterator<Cell> iter = current.cellRange(getComparator().columnComparator(),
rt.min, rt.max); iter.hasNext(); )
                         {
-                            Cell col = iter.next();
-                            if (cm.deletionInfo().isDeleted(col))
-                                indexer.remove(col);
+                            Cell c = iter.next();
+                            if (deleteAt >= c.timestamp())
+                                indexer.remove(c);
                         }
                     }
                 }
@@ -361,8 +368,6 @@ public class AtomicBTreeColumns extends ColumnFamily
 
     private static class Holder
     {
-        // This is a small optimization: DeletionInfo is mutable, but we know that we will
always copy it in that class,
-        // so we can safely alias one DeletionInfo.live() reference and avoid some allocations.
         final DeletionInfo deletionInfo;
         // the btree of columns
         final Object[] tree;
@@ -377,6 +382,11 @@ 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) });
+        }
     }
 
     // TODO: create a stack-allocation-friendly list to help optimise garbage for updates
to rows with few columns

http://git-wip-us.apache.org/repos/asf/cassandra/blob/74258e2d/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 e5d3495..0df3619 100644
--- a/src/java/org/apache/cassandra/db/CollationController.java
+++ b/src/java/org/apache/cassandra/db/CollationController.java
@@ -75,7 +75,7 @@ public class CollationController
                 if (iter != null)
                 {
                     iterators.add(iter);
-                    container.delete(iter.getColumnFamily());
+                    filter.delete(container.deletionInfo(), iter.getColumnFamily());
                     while (iter.hasNext())
                         container.addAtom(iter.next());
                 }
@@ -179,7 +179,7 @@ public class CollationController
         ColumnFamilyStore.ViewFragment view = cfs.markReferenced(filter.key);
         List<OnDiskAtomIterator> 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
         {
             Tracing.trace("Merging memtable tombstones");
@@ -188,7 +188,7 @@ public class CollationController
                 OnDiskAtomIterator iter = filter.getMemtableColumnIterator(memtable);
                 if (iter != null)
                 {
-                    returnCF.delete(iter.getColumnFamily());
+                    filter.delete(returnDeletionInfo, iter.getColumnFamily());
                     iterators.add(iter);
                 }
             }

http://git-wip-us.apache.org/repos/asf/cassandra/blob/74258e2d/src/java/org/apache/cassandra/db/DeletionInfo.java
----------------------------------------------------------------------
diff --git a/src/java/org/apache/cassandra/db/DeletionInfo.java b/src/java/org/apache/cassandra/db/DeletionInfo.java
index 7e587f3..3a74d52 100644
--- a/src/java/org/apache/cassandra/db/DeletionInfo.java
+++ b/src/java/org/apache/cassandra/db/DeletionInfo.java
@@ -252,7 +252,17 @@ public class DeletionInfo implements IMeasurableMemory
         return ranges == null ? Iterators.<RangeTombstone>emptyIterator() : ranges.iterator();
     }
 
-    public DeletionTime rangeCovering(Composite name)
+    public Iterator<RangeTombstone> rangeIterator(Composite start, Composite finish)
+    {
+        return ranges == null ? Iterators.<RangeTombstone>emptyIterator() : ranges.iterator(start,
finish);
+    }
+
+    public DeletionTime deletionTimeFor(Composite name)
+    {
+        return ranges == null ? null : ranges.searchDeletionTime(name);
+    }
+
+    public RangeTombstone rangeCovering(Composite name)
     {
         return ranges == null ? null : ranges.search(name);
     }
@@ -278,8 +288,7 @@ public class DeletionInfo implements IMeasurableMemory
      */
     public boolean mayModify(DeletionInfo delInfo)
     {
-        return topLevel.markedForDeleteAt > delInfo.topLevel.markedForDeleteAt
-            || hasRanges();
+        return topLevel.compareTo(delInfo.topLevel) > 0 || hasRanges();
     }
 
     @Override

http://git-wip-us.apache.org/repos/asf/cassandra/blob/74258e2d/src/java/org/apache/cassandra/db/RangeTombstone.java
----------------------------------------------------------------------
diff --git a/src/java/org/apache/cassandra/db/RangeTombstone.java b/src/java/org/apache/cassandra/db/RangeTombstone.java
index c10349a..097a835 100644
--- a/src/java/org/apache/cassandra/db/RangeTombstone.java
+++ b/src/java/org/apache/cassandra/db/RangeTombstone.java
@@ -98,6 +98,11 @@ public class RangeTombstone extends Interval<Composite, DeletionTime>
implements
         return comparator.compare(min, rt.min) <= 0 && comparator.compare(max,
rt.max) >= 0;
     }
 
+    public boolean includes(Comparator<Composite> comparator, Composite name)
+    {
+        return comparator.compare(name, min) >= 0 && comparator.compare(name,
max) <= 0;
+    }
+
     public static class Tracker
     {
         private final Comparator<Composite> comparator;

http://git-wip-us.apache.org/repos/asf/cassandra/blob/74258e2d/src/java/org/apache/cassandra/db/RangeTombstoneList.java
----------------------------------------------------------------------
diff --git a/src/java/org/apache/cassandra/db/RangeTombstoneList.java b/src/java/org/apache/cassandra/db/RangeTombstoneList.java
index 1158e20..344c098 100644
--- a/src/java/org/apache/cassandra/db/RangeTombstoneList.java
+++ b/src/java/org/apache/cassandra/db/RangeTombstoneList.java
@@ -25,6 +25,7 @@ import java.util.Comparator;
 import java.util.Iterator;
 
 import com.google.common.collect.AbstractIterator;
+import com.google.common.collect.Iterators;
 
 import org.apache.cassandra.cache.IMeasurableMemory;
 import org.apache.cassandra.db.composites.CType;
@@ -212,7 +213,7 @@ public class RangeTombstoneList implements Iterable<RangeTombstone>,
IMeasurable
      */
     public boolean isDeleted(Composite name, long timestamp)
     {
-        int idx = searchInternal(name);
+        int idx = searchInternal(name, 0);
         return idx >= 0 && markedAts[idx] >= timestamp;
     }
 
@@ -228,17 +229,28 @@ public class RangeTombstoneList implements Iterable<RangeTombstone>,
IMeasurable
      * Returns the DeletionTime for the tombstone overlapping {@code name} (there can't be
more than one),
      * or null if {@code name} is not covered by any tombstone.
      */
-    public DeletionTime search(Composite name) {
-        int idx = searchInternal(name);
+    public DeletionTime searchDeletionTime(Composite name)
+    {
+        int idx = searchInternal(name, 0);
         return idx < 0 ? null : new DeletionTime(markedAts[idx], delTimes[idx]);
     }
 
-    private int searchInternal(Composite name)
+    public RangeTombstone search(Composite name)
+    {
+        int idx = searchInternal(name, 0);
+        return idx < 0 ? null : rangeTombstone(idx);
+    }
+
+    /*
+     * Return is the index of the range covering name if name is covered. If the return idx
is negative,
+     * no range cover name and -idx-1 is the index of the first range whose start is greater
than name.
+     */
+    private int searchInternal(Composite name, int startIdx)
     {
         if (isEmpty())
             return -1;
 
-        int pos = Arrays.binarySearch(starts, 0, size, name, comparator);
+        int pos = Arrays.binarySearch(starts, startIdx, size, name, comparator);
         if (pos >= 0)
         {
             // We're exactly on an interval start. The one subtility is that we need to check
if
@@ -255,7 +267,7 @@ public class RangeTombstoneList implements Iterable<RangeTombstone>,
IMeasurable
             if (idx < 0)
                 return -1;
 
-            return comparator.compare(name, ends[idx]) <= 0 ? idx : -1;
+            return comparator.compare(name, ends[idx]) <= 0 ? idx : -idx-2;
         }
     }
 
@@ -320,6 +332,11 @@ public class RangeTombstoneList implements Iterable<RangeTombstone>,
IMeasurable
         return false;
     }
 
+    private RangeTombstone rangeTombstone(int idx)
+    {
+        return new RangeTombstone(starts[idx], ends[idx], markedAts[idx], delTimes[idx]);
+    }
+
     public Iterator<RangeTombstone> iterator()
     {
         return new AbstractIterator<RangeTombstone>()
@@ -331,9 +348,39 @@ public class RangeTombstoneList implements Iterable<RangeTombstone>,
IMeasurable
                 if (idx >= size)
                     return endOfData();
 
-                RangeTombstone t = new RangeTombstone(starts[idx], ends[idx], markedAts[idx],
delTimes[idx]);
-                idx++;
-                return t;
+                return rangeTombstone(idx++);
+            }
+        };
+    }
+
+    public Iterator<RangeTombstone> iterator(Composite from, Composite till)
+    {
+        int startIdx = from.isEmpty() ? 0 : searchInternal(from, 0);
+        final int start = startIdx < 0 ? -startIdx-1 : startIdx;
+
+        if (start >= size)
+            return Iterators.<RangeTombstone>emptyIterator();
+
+        int finishIdx = till.isEmpty() ? size : searchInternal(till, start);
+        // if stopIdx is the first range after 'till' we care only until the previous range
+        final int finish = finishIdx < 0 ? -finishIdx-2 : finishIdx;
+
+        // Note: the following is true because we know 'from' is before 'till' in sorted
order.
+        if (start > finish)
+            return Iterators.<RangeTombstone>emptyIterator();
+        else if (start == finish)
+            return Iterators.<RangeTombstone>singletonIterator(rangeTombstone(start));
+
+        return new AbstractIterator<RangeTombstone>()
+        {
+            private int idx = start;
+
+            protected RangeTombstone computeNext()
+            {
+                if (idx >= size || idx > finish)
+                    return endOfData();
+
+                return rangeTombstone(idx++);
             }
         };
     }

http://git-wip-us.apache.org/repos/asf/cassandra/blob/74258e2d/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 17967a8..8142304 100644
--- a/src/java/org/apache/cassandra/db/filter/IDiskAtomFilter.java
+++ b/src/java/org/apache/cassandra/db/filter/IDiskAtomFilter.java
@@ -139,4 +139,6 @@ public interface IDiskAtomFilter
             return size;
         }
     }
+
+    public Iterator<RangeTombstone> getRangeTombstoneIterator(ColumnFamily source);
 }

http://git-wip-us.apache.org/repos/asf/cassandra/blob/74258e2d/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 208bbdf..b1745c3 100644
--- a/src/java/org/apache/cassandra/db/filter/NamesQueryFilter.java
+++ b/src/java/org/apache/cassandra/db/filter/NamesQueryFilter.java
@@ -27,6 +27,7 @@ import java.util.TreeSet;
 
 import org.apache.commons.lang3.StringUtils;
 import com.google.common.collect.AbstractIterator;
+import com.google.common.collect.Iterators;
 
 import org.apache.cassandra.db.*;
 import org.apache.cassandra.db.columniterator.OnDiskAtomIterator;
@@ -258,4 +259,33 @@ public class NamesQueryFilter implements IDiskAtomFilter
             return size;
         }
     }
+
+    public Iterator<RangeTombstone> getRangeTombstoneIterator(final ColumnFamily source)
+    {
+        if (!source.deletionInfo().hasRanges())
+            return Iterators.<RangeTombstone>emptyIterator();
+
+        return new AbstractIterator<RangeTombstone>()
+        {
+            private final Iterator<CellName> names = columns.iterator();
+            private RangeTombstone lastFindRange;
+
+            protected RangeTombstone computeNext()
+            {
+                while (names.hasNext())
+                {
+                    CellName next = names.next();
+                    if (lastFindRange != null && lastFindRange.includes(source.getComparator(),
next))
+                        return lastFindRange;
+
+                    // We keep the last range around as since names are in sort order, it's
+                    // possible it will match the next name too.
+                    lastFindRange = source.deletionInfo().rangeCovering(next);
+                    if (lastFindRange != null)
+                        return lastFindRange;
+                }
+                return endOfData();
+            }
+        };
+    }
 }

http://git-wip-us.apache.org/repos/asf/cassandra/blob/74258e2d/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 53a2180..9c3cc49 100644
--- a/src/java/org/apache/cassandra/db/filter/QueryFilter.java
+++ b/src/java/org/apache/cassandra/db/filter/QueryFilter.java
@@ -234,4 +234,13 @@ public class QueryFilter
     {
         return filter.shouldInclude(sstable);
     }
+
+    public void delete(DeletionInfo target, ColumnFamily source)
+    {
+        target.add(source.deletionInfo().getTopLevelDeletion());
+        // source is the CF currently in the memtable, and it can be large compared to what
the filter selects,
+        // so only consider those range tombstones that the filter do select.
+        for (Iterator<RangeTombstone> iter = filter.getRangeTombstoneIterator(source);
iter.hasNext(); )
+            target.add(iter.next(), source.getComparator());
+    }
 }

http://git-wip-us.apache.org/repos/asf/cassandra/blob/74258e2d/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 26f6d9d..f448db9 100644
--- a/src/java/org/apache/cassandra/db/filter/SliceQueryFilter.java
+++ b/src/java/org/apache/cassandra/db/filter/SliceQueryFilter.java
@@ -23,6 +23,8 @@ import java.io.DataOutput;
 import java.io.IOException;
 import java.util.*;
 
+import com.google.common.collect.AbstractIterator;
+import com.google.common.collect.Iterators;
 import org.slf4j.Logger;
 import org.slf4j.LoggerFactory;
 
@@ -426,4 +428,43 @@ public class SliceQueryFilter implements IDiskAtomFilter
             return size;
         }
     }
+
+    public Iterator<RangeTombstone> getRangeTombstoneIterator(final ColumnFamily source)
+    {
+        final DeletionInfo delInfo = source.deletionInfo();
+        if (!delInfo.hasRanges() || slices.length == 0)
+            return Iterators.<RangeTombstone>emptyIterator();
+
+        return new AbstractIterator<RangeTombstone>()
+        {
+            private int sliceIdx = 0;
+            private Iterator<RangeTombstone> sliceIter = currentRangeIter();
+
+            protected RangeTombstone computeNext()
+            {
+                while (true)
+                {
+                    if (sliceIter.hasNext())
+                        return sliceIter.next();
+
+                    if (!nextSlice())
+                        return endOfData();
+
+                    sliceIter = currentRangeIter();
+                }
+            }
+
+            private Iterator<RangeTombstone> currentRangeIter()
+            {
+                ColumnSlice slice = slices[reversed ? (slices.length - 1 - sliceIdx) : sliceIdx];
+                return reversed ? delInfo.rangeIterator(slice.finish, slice.start)
+                                : delInfo.rangeIterator(slice.start, slice.finish);
+            }
+
+            private boolean nextSlice()
+            {
+                return ++sliceIdx < slices.length;
+            }
+        };
+    }
 }

http://git-wip-us.apache.org/repos/asf/cassandra/blob/74258e2d/test/unit/org/apache/cassandra/db/RangeTombstoneListTest.java
----------------------------------------------------------------------
diff --git a/test/unit/org/apache/cassandra/db/RangeTombstoneListTest.java b/test/unit/org/apache/cassandra/db/RangeTombstoneListTest.java
index d739372..faa15f0 100644
--- a/test/unit/org/apache/cassandra/db/RangeTombstoneListTest.java
+++ b/test/unit/org/apache/cassandra/db/RangeTombstoneListTest.java
@@ -112,7 +112,7 @@ public class RangeTombstoneListTest
         l2.add(rt(4, 10, 12L));
         l2.add(rt(0, 8, 25L));
 
-        assertEquals(25L, l2.search(b(8)).markedForDeleteAt);
+        assertEquals(25L, l2.searchDeletionTime(b(8)).markedForDeleteAt);
     }
 
     @Test
@@ -159,9 +159,9 @@ public class RangeTombstoneListTest
         l.add(rt(1, 4, 2));
         l.add(rt(4, 10, 5));
 
-        assertEquals(2, l.search(b(3)).markedForDeleteAt);
-        assertEquals(5, l.search(b(4)).markedForDeleteAt);
-        assertEquals(5, l.search(b(8)).markedForDeleteAt);
+        assertEquals(2, l.searchDeletionTime(b(3)).markedForDeleteAt);
+        assertEquals(5, l.searchDeletionTime(b(4)).markedForDeleteAt);
+        assertEquals(5, l.searchDeletionTime(b(8)).markedForDeleteAt);
         assertEquals(3, l.size());
     }
 
@@ -175,20 +175,20 @@ public class RangeTombstoneListTest
         l.add(rt(14, 15, 3));
         l.add(rt(15, 17, 6));
 
-        assertEquals(null, l.search(b(-1)));
+        assertEquals(null, l.searchDeletionTime(b(-1)));
 
-        assertEquals(5, l.search(b(0)).markedForDeleteAt);
-        assertEquals(5, l.search(b(3)).markedForDeleteAt);
-        assertEquals(5, l.search(b(4)).markedForDeleteAt);
+        assertEquals(5, l.searchDeletionTime(b(0)).markedForDeleteAt);
+        assertEquals(5, l.searchDeletionTime(b(3)).markedForDeleteAt);
+        assertEquals(5, l.searchDeletionTime(b(4)).markedForDeleteAt);
 
-        assertEquals(2, l.search(b(5)).markedForDeleteAt);
+        assertEquals(2, l.searchDeletionTime(b(5)).markedForDeleteAt);
 
-        assertEquals(null, l.search(b(7)));
+        assertEquals(null, l.searchDeletionTime(b(7)));
 
-        assertEquals(3, l.search(b(14)).markedForDeleteAt);
+        assertEquals(3, l.searchDeletionTime(b(14)).markedForDeleteAt);
 
-        assertEquals(6, l.search(b(15)).markedForDeleteAt);
-        assertEquals(null, l.search(b(18)));
+        assertEquals(6, l.searchDeletionTime(b(15)).markedForDeleteAt);
+        assertEquals(null, l.searchDeletionTime(b(18)));
     }
 
     @Test

http://git-wip-us.apache.org/repos/asf/cassandra/blob/74258e2d/test/unit/org/apache/cassandra/db/RangeTombstoneTest.java
----------------------------------------------------------------------
diff --git a/test/unit/org/apache/cassandra/db/RangeTombstoneTest.java b/test/unit/org/apache/cassandra/db/RangeTombstoneTest.java
index 1885716..a307485 100644
--- a/test/unit/org/apache/cassandra/db/RangeTombstoneTest.java
+++ b/test/unit/org/apache/cassandra/db/RangeTombstoneTest.java
@@ -26,6 +26,7 @@ import org.apache.cassandra.utils.memory.AbstractAllocator;
 import org.junit.Test;
 
 import com.google.common.collect.ImmutableMap;
+import org.apache.commons.collections.CollectionUtils;
 
 import org.apache.cassandra.SchemaLoader;
 import org.apache.cassandra.config.ColumnDefinition;
@@ -112,6 +113,107 @@ public class RangeTombstoneTest extends SchemaLoader
     }
 
     @Test
+    public void rangeTombstoneFilteringTest() throws Exception
+    {
+        CompactionManager.instance.disableAutoCompaction();
+        Keyspace keyspace = Keyspace.open(KSNAME);
+        ColumnFamilyStore cfs = keyspace.getColumnFamilyStore(CFNAME);
+
+        // Inserting data
+        String key = "k111";
+        RowMutation rm;
+        ColumnFamily cf;
+
+        rm = new RowMutation(KSNAME, ByteBufferUtil.bytes(key));
+        for (int i = 0; i < 40; i += 2)
+            add(rm, i, 0);
+        rm.apply();
+
+        rm = new RowMutation(KSNAME, ByteBufferUtil.bytes(key));
+        cf = rm.addOrGet(CFNAME);
+        delete(cf, 5, 10, 1);
+        rm.apply();
+
+        rm = new RowMutation(KSNAME, ByteBufferUtil.bytes(key));
+        cf = rm.addOrGet(CFNAME);
+        delete(cf, 15, 20, 2);
+        rm.apply();
+
+        cf = cfs.getColumnFamily(QueryFilter.getSliceFilter(dk(key), CFNAME, b(11), b(14),
false, Integer.MAX_VALUE, System.currentTimeMillis()));
+        Collection<RangeTombstone> rt = rangeTombstones(cf);
+        assertEquals(0, rt.size());
+
+        cf = cfs.getColumnFamily(QueryFilter.getSliceFilter(dk(key), CFNAME, b(11), b(15),
false, Integer.MAX_VALUE, System.currentTimeMillis()));
+        rt = rangeTombstones(cf);
+        assertEquals(1, rt.size());
+
+        cf = cfs.getColumnFamily(QueryFilter.getSliceFilter(dk(key), CFNAME, b(20), b(25),
false, Integer.MAX_VALUE, System.currentTimeMillis()));
+        rt = rangeTombstones(cf);
+        assertEquals(1, rt.size());
+
+        cf = cfs.getColumnFamily(QueryFilter.getSliceFilter(dk(key), CFNAME, b(12), b(25),
false, Integer.MAX_VALUE, System.currentTimeMillis()));
+        rt = rangeTombstones(cf);
+        assertEquals(1, rt.size());
+
+        cf = cfs.getColumnFamily(QueryFilter.getSliceFilter(dk(key), CFNAME, b(25), b(35),
false, Integer.MAX_VALUE, System.currentTimeMillis()));
+        rt = rangeTombstones(cf);
+        assertEquals(0, rt.size());
+
+        cf = cfs.getColumnFamily(QueryFilter.getSliceFilter(dk(key), CFNAME, b(1), b(40),
false, Integer.MAX_VALUE, System.currentTimeMillis()));
+        rt = rangeTombstones(cf);
+        assertEquals(2, rt.size());
+
+        cf = cfs.getColumnFamily(QueryFilter.getSliceFilter(dk(key), CFNAME, b(7), b(17),
false, Integer.MAX_VALUE, System.currentTimeMillis()));
+        rt = rangeTombstones(cf);
+        assertEquals(2, rt.size());
+
+        cf = cfs.getColumnFamily(QueryFilter.getSliceFilter(dk(key), CFNAME, b(5), b(20),
false, Integer.MAX_VALUE, System.currentTimeMillis()));
+        rt = rangeTombstones(cf);
+        assertEquals(2, rt.size());
+
+        cf = cfs.getColumnFamily(QueryFilter.getSliceFilter(dk(key), CFNAME, b(5), b(15),
false, Integer.MAX_VALUE, System.currentTimeMillis()));
+        rt = rangeTombstones(cf);
+        assertEquals(2, rt.size());
+
+        cf = cfs.getColumnFamily(QueryFilter.getSliceFilter(dk(key), CFNAME, b(1), b(2),
false, Integer.MAX_VALUE, System.currentTimeMillis()));
+        rt = rangeTombstones(cf);
+        assertEquals(0, rt.size());
+
+        cf = cfs.getColumnFamily(QueryFilter.getSliceFilter(dk(key), CFNAME, b(1), b(5),
false, Integer.MAX_VALUE, System.currentTimeMillis()));
+        rt = rangeTombstones(cf);
+        assertEquals(1, rt.size());
+
+        cf = cfs.getColumnFamily(QueryFilter.getSliceFilter(dk(key), CFNAME, b(1), b(10),
false, Integer.MAX_VALUE, System.currentTimeMillis()));
+        rt = rangeTombstones(cf);
+        assertEquals(1, rt.size());
+
+        cf = cfs.getColumnFamily(QueryFilter.getSliceFilter(dk(key), CFNAME, b(5), b(6),
false, Integer.MAX_VALUE, System.currentTimeMillis()));
+        rt = rangeTombstones(cf);
+        assertEquals(1, rt.size());
+
+        cf = cfs.getColumnFamily(QueryFilter.getSliceFilter(dk(key), CFNAME, b(17), b(20),
false, Integer.MAX_VALUE, System.currentTimeMillis()));
+        rt = rangeTombstones(cf);
+        assertEquals(1, rt.size());
+
+        cf = cfs.getColumnFamily(QueryFilter.getSliceFilter(dk(key), CFNAME, b(17), b(18),
false, Integer.MAX_VALUE, System.currentTimeMillis()));
+        rt = rangeTombstones(cf);
+        assertEquals(1, rt.size());
+
+        ColumnSlice[] slices = new ColumnSlice[]{new ColumnSlice( b(1), b(10)), new ColumnSlice(
b(16), b(20))};
+        IDiskAtomFilter sqf = new SliceQueryFilter(slices, false, Integer.MAX_VALUE);
+        cf = cfs.getColumnFamily( new QueryFilter(dk(key), CFNAME, sqf, System.currentTimeMillis())
);
+        rt = rangeTombstones(cf);
+        assertEquals(2, rt.size());
+    }
+
+    private Collection<RangeTombstone> rangeTombstones(ColumnFamily cf)
+    {
+        List <RangeTombstone> res = new ArrayList<RangeTombstone>();
+        CollectionUtils.addAll(res, cf.deletionInfo().rangeIterator());
+        return res;
+    }
+
+    @Test
     public void overlappingRangeTest() throws Exception
     {
         CompactionManager.instance.disableAutoCompaction();

http://git-wip-us.apache.org/repos/asf/cassandra/blob/74258e2d/test/unit/org/apache/cassandra/tools/SSTableImportTest.java
----------------------------------------------------------------------
diff --git a/test/unit/org/apache/cassandra/tools/SSTableImportTest.java b/test/unit/org/apache/cassandra/tools/SSTableImportTest.java
index 6434143..3576005 100644
--- a/test/unit/org/apache/cassandra/tools/SSTableImportTest.java
+++ b/test/unit/org/apache/cassandra/tools/SSTableImportTest.java
@@ -109,7 +109,7 @@ public class SSTableImportTest extends SchemaLoader
         ColumnFamily cf = cloneForAdditions(qf.getSSTableColumnIterator(reader));
         qf.collateOnDiskAtom(cf, qf.getSSTableColumnIterator(reader), Integer.MIN_VALUE);
 
-        DeletionTime delTime = cf.deletionInfo().rangeCovering(cf.getComparator().make(ByteBufferUtil.bytes("superA")));
+        DeletionTime delTime = cf.deletionInfo().deletionTimeFor(cf.getComparator().make(ByteBufferUtil.bytes("superA")));
         assertEquals("supercolumn deletion time did not match the expected time", new DeletionInfo(0,
0), new DeletionInfo(delTime));
         Cell subCell = cf.getColumn(Util.cellname("superA", "636f6c4141"));
         assert subCell.value().equals(hexToBytes("76616c75654141"));


Mime
View raw message