cassandra-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From j...@apache.org
Subject [5/5] git commit: Handle overlapping multislices in thrift and cql
Date Wed, 28 May 2014 17:58:21 GMT
Handle overlapping multislices in thrift and cql

Patch by pcmanus and tjake; reviewed by tjake for CASSANDRA-7279


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

Branch: refs/heads/cassandra-2.1
Commit: e9e91d7b505d5c76cf099b7792a1c884276b56c0
Parents: 7f63b1f
Author: Jake Luciani <jake@apache.org>
Authored: Wed May 28 13:14:43 2014 -0400
Committer: Jake Luciani <jake@apache.org>
Committed: Wed May 28 13:14:43 2014 -0400

----------------------------------------------------------------------
 CHANGES.txt                                     |   1 +
 .../cql3/statements/CQL3CasConditions.java      |   1 +
 .../cql3/statements/SelectStatement.java        |   1 +
 .../cassandra/db/composites/AbstractCType.java  |   5 +
 .../apache/cassandra/db/filter/ColumnSlice.java |  97 +++++++++++++
 .../cassandra/thrift/CassandraServer.java       |   6 +-
 .../cassandra/db/filter/ColumnSliceTest.java    | 137 +++++++++++++++++--
 .../apache/cassandra/thrift/MultiSliceTest.java |  20 ++-
 8 files changed, 252 insertions(+), 16 deletions(-)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/cassandra/blob/e9e91d7b/CHANGES.txt
----------------------------------------------------------------------
diff --git a/CHANGES.txt b/CHANGES.txt
index a7cc872..8e0dead 100644
--- a/CHANGES.txt
+++ b/CHANGES.txt
@@ -26,6 +26,7 @@
  * Fix IllegalArgumentException in CqlStorage (CASSANDRA-7287)
  * Allow nulls/non-existant fields in UDT (CASSANDRA-7206)
  * Backport Thrift MultiSliceRequest (CASSANDRA-7027)
+ * Handle overlapping MultiSlices (CASSANDRA-7279)
 Merged from 2.0:
  * Copy compaction options to make sure they are reloaded (CASSANDRA-7290)
  * Add option to do more aggressive tombstone compactions (CASSANDRA-6563)

http://git-wip-us.apache.org/repos/asf/cassandra/blob/e9e91d7b/src/java/org/apache/cassandra/cql3/statements/CQL3CasConditions.java
----------------------------------------------------------------------
diff --git a/src/java/org/apache/cassandra/cql3/statements/CQL3CasConditions.java b/src/java/org/apache/cassandra/cql3/statements/CQL3CasConditions.java
index b06b2ee..8b5a403 100644
--- a/src/java/org/apache/cassandra/cql3/statements/CQL3CasConditions.java
+++ b/src/java/org/apache/cassandra/cql3/statements/CQL3CasConditions.java
@@ -98,6 +98,7 @@ public class CQL3CasConditions implements CASConditions
             slices[i++] = prefix.slice();
 
         int toGroup = cfm.comparator.isDense() ? -1 : cfm.clusteringColumns().size();
+        assert ColumnSlice.validateSlices(slices, cfm.comparator, false);
         return new SliceQueryFilter(slices, false, slices.length, toGroup);
     }
 

http://git-wip-us.apache.org/repos/asf/cassandra/blob/e9e91d7b/src/java/org/apache/cassandra/cql3/statements/SelectStatement.java
----------------------------------------------------------------------
diff --git a/src/java/org/apache/cassandra/cql3/statements/SelectStatement.java b/src/java/org/apache/cassandra/cql3/statements/SelectStatement.java
index 501ef45..d484c5f 100644
--- a/src/java/org/apache/cassandra/cql3/statements/SelectStatement.java
+++ b/src/java/org/apache/cassandra/cql3/statements/SelectStatement.java
@@ -533,6 +533,7 @@ public class SelectStatement implements CQLStatement, MeasurableForPreparedCache
 
     private SliceQueryFilter sliceFilter(ColumnSlice[] slices, int limit, int toGroup)
     {
+        assert ColumnSlice.validateSlices(slices, cfm.comparator, isReversed) : String.format("Invalid
slices: " + Arrays.toString(slices) + (isReversed ? " (reversed)" : ""));
         return new SliceQueryFilter(slices, isReversed, limit, toGroup);
     }
 

http://git-wip-us.apache.org/repos/asf/cassandra/blob/e9e91d7b/src/java/org/apache/cassandra/db/composites/AbstractCType.java
----------------------------------------------------------------------
diff --git a/src/java/org/apache/cassandra/db/composites/AbstractCType.java b/src/java/org/apache/cassandra/db/composites/AbstractCType.java
index 0e73397..e299e42 100644
--- a/src/java/org/apache/cassandra/db/composites/AbstractCType.java
+++ b/src/java/org/apache/cassandra/db/composites/AbstractCType.java
@@ -60,6 +60,11 @@ public abstract class AbstractCType implements CType
         {
             public int compare(Composite c1, Composite c2)
             {
+                if (c1.isEmpty())
+                    return c2.isEmpty() ? 0 : -1;
+                if (c2.isEmpty())
+                    return 1;
+
                 return AbstractCType.this.compare(c2, c1);
             }
         };

http://git-wip-us.apache.org/repos/asf/cassandra/blob/e9e91d7b/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 a945114..bca4743 100644
--- a/src/java/org/apache/cassandra/db/filter/ColumnSlice.java
+++ b/src/java/org/apache/cassandra/db/filter/ColumnSlice.java
@@ -19,6 +19,8 @@ package org.apache.cassandra.db.filter;
 
 import java.io.*;
 import java.nio.ByteBuffer;
+import java.util.ArrayList;
+import java.util.Arrays;
 import java.util.Comparator;
 import java.util.List;
 
@@ -108,6 +110,101 @@ public class ColumnSlice
         return 0;
     }
 
+    /**
+     * Validates that the provided slice array contains only non-overlapped slices valid
for a query {@code reversed}
+     * or not on a table using {@code comparator}.
+     */
+    public static boolean validateSlices(ColumnSlice[] slices, CellNameType comparator, boolean
reversed)
+    {
+        return validateSlices(slices, reversed ? comparator.reverseComparator() : comparator);
+    }
+
+    /**
+     * Validates that the provided slice array contains only non-overlapped slices in {@code
comparator} order.
+     */
+    public static boolean validateSlices(ColumnSlice[] slices, Comparator<Composite>
comparator)
+    {
+        for (int i = 0; i < slices.length; i++)
+        {
+            if (i > 0 && comparator.compare(slices[i-1].finish, slices[i].start)
>= 0)
+                return false;
+
+            if (slices[i].finish.isEmpty())
+                return i == slices.length - 1;
+
+            if (comparator.compare(slices[i].start, slices[i].finish) > 0)
+                return false;
+        }
+        return true;
+    }
+
+    /**
+     * Takes an array of slices (potentially overlapping and in any order, though each individual
slice must have
+     * its start before or equal its end in {@code comparator} orde) and return an equivalent
array of non-overlapping
+     * slices in {@code comparator order}.
+     *
+     * @param slices an array of slices. This may be modified by this method.
+     * @param comparator the order in which to sort the slices.
+     * @return the smallest possible array of non-overlapping slices in {@code compator}
order. If the original
+     * slices are already non-overlapping and in comparator order, this may or may not return
the provided slices
+     * directly.
+     */
+    public static ColumnSlice[] deoverlapSlices(ColumnSlice[] slices, final Comparator<Composite>
comparator)
+    {
+        if (slices.length <= 1)
+            return slices;
+
+        Arrays.sort(slices, new Comparator<ColumnSlice>()
+        {
+            @Override
+            public int compare(ColumnSlice s1, ColumnSlice s2)
+            {
+                int c = comparator.compare(s1.start, s2.start);
+                if (c != 0)
+                    return c;
+
+                // For the finish, empty always means greater
+                return s1.finish.isEmpty() || s2.finish.isEmpty()
+                     ? s1.finish.isEmpty() ? 1 : s2.finish.isEmpty() ? -1 : 0
+                     : comparator.compare(s1.finish, s2.finish);
+            }
+        });
+
+        List<ColumnSlice> slicesCopy = new ArrayList<>(slices.length);
+
+        ColumnSlice last = slices[0];
+
+        for (int i = 1; i < slices.length; i++)
+        {
+            ColumnSlice s2 = slices[i];
+
+            boolean includesStart = last.includes(comparator, s2.start);
+            boolean includesFinish = s2.finish.isEmpty() ? last.finish.isEmpty() : last.includes(comparator,
s2.finish);
+
+            if (includesStart && includesFinish)
+                continue;
+
+            if (!includesStart && !includesFinish)
+            {
+                slicesCopy.add(last);
+                last = s2;
+                continue;
+            }
+
+            if (includesStart)
+            {
+                last = new ColumnSlice(last.start, s2.finish);
+                continue;
+            }
+
+            assert !includesFinish;
+        }
+
+        slicesCopy.add(last);
+
+        return slicesCopy.toArray(new ColumnSlice[slicesCopy.size()]);
+    }
+
     @Override
     public final int hashCode()
     {

http://git-wip-us.apache.org/repos/asf/cassandra/blob/e9e91d7b/src/java/org/apache/cassandra/thrift/CassandraServer.java
----------------------------------------------------------------------
diff --git a/src/java/org/apache/cassandra/thrift/CassandraServer.java b/src/java/org/apache/cassandra/thrift/CassandraServer.java
index 917e4cb..1a77ffa 100644
--- a/src/java/org/apache/cassandra/thrift/CassandraServer.java
+++ b/src/java/org/apache/cassandra/thrift/CassandraServer.java
@@ -2065,7 +2065,7 @@ public class CassandraServer implements Cassandra.Iface
             org.apache.cassandra.db.ConsistencyLevel consistencyLevel = ThriftConversion.fromThrift(request.getConsistency_level());
             consistencyLevel.validateForRead(keyspace);
             List<ReadCommand> commands = new ArrayList<>(1);
-            ColumnSlice [] slices = new ColumnSlice[request.getColumn_slices().size()];
+            ColumnSlice[] slices = new ColumnSlice[request.getColumn_slices().size()];
             for (int i = 0 ; i < request.getColumn_slices().size() ; i++)
             {
                 fixOptionalSliceParameters(request.getColumn_slices().get(i));
@@ -2078,7 +2078,9 @@ public class CassandraServer implements Cassandra.Iface
                     throw new InvalidRequestException(String.format("Reversed column slice
at index %d had start less than finish", i));
                 slices[i] = new ColumnSlice(start, finish);
             }
-            SliceQueryFilter filter = new SliceQueryFilter(slices, request.reversed, request.count);
+
+            ColumnSlice[] deoverlapped = ColumnSlice.deoverlapSlices(slices, request.reversed
? metadata.comparator.reverseComparator() : metadata.comparator);
+            SliceQueryFilter filter = new SliceQueryFilter(deoverlapped, request.reversed,
request.count);
             ThriftValidation.validateKey(metadata, request.key);
             commands.add(ReadCommand.create(keyspace, request.key, request.column_parent.getColumn_family(),
System.currentTimeMillis(), filter));
             return getSlice(commands, request.column_parent.isSetSuper_column(), consistencyLevel).entrySet().iterator().next().getValue();

http://git-wip-us.apache.org/repos/asf/cassandra/blob/e9e91d7b/test/unit/org/apache/cassandra/db/filter/ColumnSliceTest.java
----------------------------------------------------------------------
diff --git a/test/unit/org/apache/cassandra/db/filter/ColumnSliceTest.java b/test/unit/org/apache/cassandra/db/filter/ColumnSliceTest.java
index 6553de5..2dc3744 100644
--- a/test/unit/org/apache/cassandra/db/filter/ColumnSliceTest.java
+++ b/test/unit/org/apache/cassandra/db/filter/ColumnSliceTest.java
@@ -18,22 +18,23 @@
  * */
 package org.apache.cassandra.db.filter;
 
-import org.apache.cassandra.db.composites.Composite;
-import org.apache.cassandra.db.composites.CompoundDenseCellNameType;
+
+import java.nio.ByteBuffer;
+import java.util.*;
+
+import org.junit.Test;
+
+import org.apache.cassandra.db.composites.*;
 import org.apache.cassandra.db.marshal.AbstractType;
 import org.apache.cassandra.db.marshal.Int32Type;
 import org.apache.cassandra.utils.ByteBufferUtil;
-import org.junit.Test;
 
-import java.nio.ByteBuffer;
-import java.util.ArrayList;
-import java.util.List;
-
-import static org.junit.Assert.assertFalse;
-import static org.junit.Assert.assertTrue;
+import static org.junit.Assert.*;
 
 public class ColumnSliceTest
 {
+    private static final CellNameType simpleIntType = new SimpleDenseCellNameType(Int32Type.instance);
+
     @Test
     public void testIntersectsSingleSlice()
     {
@@ -278,6 +279,65 @@ public class ColumnSliceTest
         assertTrue(slice.intersects(columnNames(1, 0, 0), columnNames(2, 2, 2), nameType,
true));
     }
 
+    @Test
+    public void testDeoverlapSlices()
+    {
+        ColumnSlice[] slices;
+        ColumnSlice[] deoverlapped;
+
+        // Preserve correct slices
+        slices = slices(s(0, 3), s(4, 5), s(6, 9));
+        assertSlicesValid(slices);
+        assertSlicesEquals(slices, deoverlapSlices(slices));
+
+        // Simple overlap
+        slices = slices(s(0, 3), s(2, 5), s(8, 9));
+        assertSlicesInvalid(slices);
+        assertSlicesEquals(slices(s(0, 5), s(8, 9)), deoverlapSlices(slices));
+
+        // Slice overlaps others fully
+        slices = slices(s(0, 10), s(2, 5), s(8, 9));
+        assertSlicesInvalid(slices);
+        assertSlicesEquals(slices(s(0, 10)), deoverlapSlices(slices));
+
+        // Slice with empty end overlaps others fully
+        slices = slices(s(0, -1), s(2, 5), s(8, 9));
+        assertSlicesInvalid(slices);
+        assertSlicesEquals(slices(s(0, -1)), deoverlapSlices(slices));
+
+        // Overlap with slices selecting only one element
+        slices = slices(s(0, 4), s(4, 4), s(4, 8));
+        assertSlicesInvalid(slices);
+        assertSlicesEquals(slices(s(0, 8)), deoverlapSlices(slices));
+
+        // Unordered slices (without overlap)
+        slices = slices(s(4, 8), s(0, 3), s(9, 9));
+        assertSlicesInvalid(slices);
+        assertSlicesEquals(slices(s(0, 3), s(4, 8), s(9, 9)), deoverlapSlices(slices));
+
+        // All range select but not by a single slice
+        slices = slices(s(5, -1), s(2, 5), s(-1, 2));
+        assertSlicesInvalid(slices);
+        assertSlicesEquals(slices(s(-1, -1)), deoverlapSlices(slices));
+    }
+
+    @Test
+    public void testValidateSlices()
+    {
+        assertSlicesValid(slices(s(0, 3)));
+        assertSlicesValid(slices(s(3, 3)));
+        assertSlicesValid(slices(s(3, 3), s(4, 4)));
+        assertSlicesValid(slices(s(0, 3), s(4, 5), s(6, 9)));
+        assertSlicesValid(slices(s(-1, -1)));
+        assertSlicesValid(slices(s(-1, 3), s(4, -1)));
+
+        assertSlicesInvalid(slices(s(3, 0)));
+        assertSlicesInvalid(slices(s(0, 2), s(2, 4)));
+        assertSlicesInvalid(slices(s(0, 2), s(1, 4)));
+        assertSlicesInvalid(slices(s(0, 2), s(3, 4), s(3, 4)));
+        assertSlicesInvalid(slices(s(-1, 2), s(3, -1), s(5, 9)));
+    }
+
     private static Composite composite(Integer ... components)
     {
         List<AbstractType<?>> types = new ArrayList<>();
@@ -295,4 +355,61 @@ public class ColumnSliceTest
             names.add(ByteBufferUtil.bytes(component));
         return names;
     }
-}
\ No newline at end of file
+
+    private static Composite simpleComposite(int i)
+    {
+        // We special negative values to mean EMPTY for convenience sake
+        if (i < 0)
+            return Composites.EMPTY;
+
+        return simpleIntType.make(i);
+    }
+
+    private static ColumnSlice s(int start, int finish)
+    {
+        return new ColumnSlice(simpleComposite(start), simpleComposite(finish));
+    }
+
+    private static ColumnSlice[] slices(ColumnSlice... slices)
+    {
+        return slices;
+    }
+
+    private static ColumnSlice[] deoverlapSlices(ColumnSlice[] slices)
+    {
+        return ColumnSlice.deoverlapSlices(slices, simpleIntType);
+    }
+
+    private static void assertSlicesValid(ColumnSlice[] slices)
+    {
+        assertTrue("Slices " + toString(slices) + " should be valid", ColumnSlice.validateSlices(slices,
simpleIntType));
+    }
+
+    private static void assertSlicesInvalid(ColumnSlice[] slices)
+    {
+        assertFalse("Slices " + toString(slices) + " shouldn't be valid", ColumnSlice.validateSlices(slices,
simpleIntType));
+    }
+
+    private static void assertSlicesEquals(ColumnSlice[] expected, ColumnSlice[] actual)
+    {
+        assertTrue("Expected " + toString(expected) + " but got " + toString(actual), Arrays.equals(expected,
actual));
+    }
+
+    private static String toString(ColumnSlice[] slices)
+    {
+        StringBuilder sb = new StringBuilder().append("[");
+        for (int i = 0; i < slices.length; i++)
+        {
+            if (i > 0)
+                sb.append(", ");
+
+            ColumnSlice slice = slices[i];
+            sb.append("(");
+            sb.append(slice.start.isEmpty() ? "-1" : simpleIntType.getString(slice.start));
+            sb.append(", ");
+            sb.append(slice.finish.isEmpty() ? "-1" : simpleIntType.getString(slice.finish));
+            sb.append(")");
+        }
+        return sb.append("]").toString();
+    }
+}

http://git-wip-us.apache.org/repos/asf/cassandra/blob/e9e91d7b/test/unit/org/apache/cassandra/thrift/MultiSliceTest.java
----------------------------------------------------------------------
diff --git a/test/unit/org/apache/cassandra/thrift/MultiSliceTest.java b/test/unit/org/apache/cassandra/thrift/MultiSliceTest.java
index d1c913b..9193258 100644
--- a/test/unit/org/apache/cassandra/thrift/MultiSliceTest.java
+++ b/test/unit/org/apache/cassandra/thrift/MultiSliceTest.java
@@ -114,9 +114,21 @@ public class MultiSliceTest extends SchemaLoader
         req.setCount(6);
         req.reversed = true;
         req.setColumn_slices(Arrays.asList(columnSliceFrom("e", "a"), columnSliceFrom("g",
"d")));
-        assertColumnNameMatches(Arrays.asList("g", "e", "d", "c", "b", "a"), server.get_multi_slice(req));

+        assertColumnNameMatches(Arrays.asList("g", "f", "e", "d", "c", "b"), server.get_multi_slice(req));
     }
-    
+
+    @Test
+    public void test_with_overlap_with_count() throws TException
+    {
+        ColumnParent cp = new ColumnParent("Standard1");
+        ByteBuffer key = ByteBuffer.wrap("overlap_reversed_count".getBytes());
+        addTheAlphabetToRow(key, cp);
+        MultiSliceRequest req = makeMultiSliceRequest(key);
+        req.setCount(6);
+        req.setColumn_slices(Arrays.asList(columnSliceFrom("a", "e"), columnSliceFrom("d",
"g"), columnSliceFrom("d", "g")));
+        assertColumnNameMatches(Arrays.asList("a", "b", "c", "d", "e", "f"), server.get_multi_slice(req));
+    }
+
     private static void addTheAlphabetToRow(ByteBuffer key, ColumnParent parent) 
             throws InvalidRequestException, UnavailableException, TimedOutException
     {
@@ -135,7 +147,7 @@ public class MultiSliceTest extends SchemaLoader
         for (int i = 0 ; i< expected.size() ; i++)
         {
             Assert.assertEquals(actual.get(i) +" did not equal "+ expected.get(i), 
-                    new String(actual.get(i).getColumn().getName()), expected.get(i));
+                    expected.get(i), new String(actual.get(i).getColumn().getName()));
         }
     }
     
@@ -146,4 +158,4 @@ public class MultiSliceTest extends SchemaLoader
         cs.setFinish(ByteBufferUtil.bytes(endInclusive));
         return cs;
     }
-}
\ No newline at end of file
+}


Mime
View raw message