You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@cassandra.apache.org by ja...@apache.org on 2014/05/28 19:58:59 UTC
[5/6] git commit: Handle overlapping multislices in thrift and cql
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/trunk
Commit: e9e91d7b505d5c76cf099b7792a1c884276b56c0
Parents: 7f63b1f
Author: Jake Luciani <ja...@apache.org>
Authored: Wed May 28 13:14:43 2014 -0400
Committer: Jake Luciani <ja...@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
+}