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 <j...@apache.org> Authored: Wed May 28 13:14:43 2014 -0400 Committer: Jake Luciani <j...@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 +}