Updated Branches: refs/heads/trunk 496035585 -> 1ea5059fe
fix bug in intersection checking, and improve collection of max/min column Patch by marcuse, reviewed by pcmanus for CASSANDRA-5600 Project: http://git-wip-us.apache.org/repos/asf/cassandra/repo Commit: http://git-wip-us.apache.org/repos/asf/cassandra/commit/1ea5059f Tree: http://git-wip-us.apache.org/repos/asf/cassandra/tree/1ea5059f Diff: http://git-wip-us.apache.org/repos/asf/cassandra/diff/1ea5059f Branch: refs/heads/trunk Commit: 1ea5059fe3976ce8f660b46520859c31bb433fda Parents: 4960355 Author: Marcus Eriksson <marc...@spotify.com> Authored: Fri May 31 16:20:54 2013 +0200 Committer: Marcus Eriksson <marc...@spotify.com> Committed: Fri May 31 16:22:17 2013 +0200 ---------------------------------------------------------------------- CHANGES.txt | 2 +- .../apache/cassandra/db/marshal/CompositeType.java | 26 +--- .../cassandra/io/sstable/ColumnNameHelper.java | 105 ++++++++++----- 3 files changed, 78 insertions(+), 55 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/cassandra/blob/1ea5059f/CHANGES.txt ---------------------------------------------------------------------- diff --git a/CHANGES.txt b/CHANGES.txt index abde4b3..eec5ea7 100644 --- a/CHANGES.txt +++ b/CHANGES.txt @@ -51,7 +51,7 @@ * Use range tombstones when dropping cfs/columns from schema (CASSANDRA-5579) * cqlsh: drop CQL2/CQL3-beta support (CASSANDRA-5585) * Track max/min column names in sstables to be able to optimize slice - queries (CASSANDRA-5514, CASSANDRA-5595) + queries (CASSANDRA-5514, CASSANDRA-5595, CASSANDRA-5600) * Binary protocol: allow batching already prepared statements (CASSANDRA-4693) * Allow preparing timestamp, ttl and limit in CQL3 queries (CASSANDRA-4450) * Support native link w/o JNA in Java7 (CASSANDRA-3734) http://git-wip-us.apache.org/repos/asf/cassandra/blob/1ea5059f/src/java/org/apache/cassandra/db/marshal/CompositeType.java ---------------------------------------------------------------------- diff --git a/src/java/org/apache/cassandra/db/marshal/CompositeType.java b/src/java/org/apache/cassandra/db/marshal/CompositeType.java index ccc3b20..7679907 100644 --- a/src/java/org/apache/cassandra/db/marshal/CompositeType.java +++ b/src/java/org/apache/cassandra/db/marshal/CompositeType.java @@ -191,32 +191,20 @@ public class CompositeType extends AbstractCompositeType return true; } - /** - * Deconstructs the composite and fills out any missing components with EMPTY_BYTE_BUFFER. - */ - public List<AbstractCompositeType.CompositeComponent> deconstructAndExpand(ByteBuffer composite) - { - List<AbstractCompositeType.CompositeComponent> components = deconstruct(composite); - for (int i = components.size(); i < types.size(); i++) - components.add(new AbstractCompositeType.CompositeComponent(this.types.get(i), ByteBufferUtil.EMPTY_BYTE_BUFFER)); - return components; - } - @Override public boolean intersects(List<ByteBuffer> minColumnNames, List<ByteBuffer> maxColumnNames, SliceQueryFilter filter) { - int typeCount = types.get(types.size() - 1) instanceof ColumnToCollectionType ? types.size() - 1 : types.size(); - - assert minColumnNames.size() == typeCount; - + assert minColumnNames.size() == maxColumnNames.size(); for (ColumnSlice slice : filter.slices) { - List<AbstractCompositeType.CompositeComponent> start = deconstructAndExpand(filter.isReversed() ? slice.finish : slice.start); - List<AbstractCompositeType.CompositeComponent> finish = deconstructAndExpand(filter.isReversed() ? slice.start : slice.finish); - for (int i = 0; i < typeCount; i++) + ByteBuffer[] start = split(filter.isReversed() ? slice.finish : slice.start); + ByteBuffer[] finish = split(filter.isReversed() ? slice.start : slice.finish); + for (int i = 0; i < minColumnNames.size(); i++) { AbstractType<?> t = types.get(i); - if (!t.intersects(minColumnNames.get(i), maxColumnNames.get(i), start.get(i).value, finish.get(i).value)) + ByteBuffer s = i < start.length ? start[i] : ByteBufferUtil.EMPTY_BYTE_BUFFER; + ByteBuffer f = i < finish.length ? finish[i] : ByteBufferUtil.EMPTY_BYTE_BUFFER; + if (!t.intersects(minColumnNames.get(i), maxColumnNames.get(i), s, f)) return false; } } http://git-wip-us.apache.org/repos/asf/cassandra/blob/1ea5059f/src/java/org/apache/cassandra/io/sstable/ColumnNameHelper.java ---------------------------------------------------------------------- diff --git a/src/java/org/apache/cassandra/io/sstable/ColumnNameHelper.java b/src/java/org/apache/cassandra/io/sstable/ColumnNameHelper.java index d9dc4b8..2ad1cff 100644 --- a/src/java/org/apache/cassandra/io/sstable/ColumnNameHelper.java +++ b/src/java/org/apache/cassandra/io/sstable/ColumnNameHelper.java @@ -23,8 +23,8 @@ import java.util.Arrays; import java.util.Collections; import java.util.List; -import org.apache.cassandra.db.marshal.AbstractCompositeType; import org.apache.cassandra.db.marshal.AbstractType; +import org.apache.cassandra.db.marshal.ColumnToCollectionType; import org.apache.cassandra.db.marshal.CompositeType; public class ColumnNameHelper @@ -36,6 +36,8 @@ public class ColumnNameHelper * component is compared to the component on the same place in maxSeen, and then returning the list * with the max columns. * + * will collect at most the number of types in the comparator. + * * if comparator is not CompositeType, maxSeen is assumed to be of size 1 and the item there is * compared to the candidate. * @@ -46,18 +48,26 @@ public class ColumnNameHelper */ public static List<ByteBuffer> maxComponents(List<ByteBuffer> maxSeen, ByteBuffer candidate, AbstractType<?> comparator) { - if (comparator instanceof AbstractCompositeType) + if (comparator instanceof CompositeType) { - if (maxSeen.size() == 0) - return Arrays.asList(((AbstractCompositeType)comparator).split(candidate)); - - List<AbstractCompositeType.CompositeComponent> components = ((AbstractCompositeType)comparator).deconstruct(candidate); - List<ByteBuffer> retList = new ArrayList<ByteBuffer>(components.size()); - for (int i = 0; i < maxSeen.size(); i++) - { - AbstractCompositeType.CompositeComponent component = components.get(i); - retList.add(ColumnNameHelper.max(maxSeen.get(i), component.value, component.comparator)); - } + CompositeType ct = (CompositeType)comparator; + if (maxSeen.isEmpty()) + return Arrays.asList(ct.split(candidate)); + + int typeCount = getTypeCount(ct); + + List<ByteBuffer> components = Arrays.asList(ct.split(candidate)); + List<ByteBuffer> biggest = maxSeen.size() > components.size() ? maxSeen : components; + // if typecount is less than both the components and maxseen, we only keep typecount columns. + int minSize = Math.min(typeCount, Math.min(components.size(), maxSeen.size())); + int maxSize = Math.min(typeCount, biggest.size()); + List<ByteBuffer> retList = new ArrayList<ByteBuffer>(maxSize); + + for (int i = 0; i < minSize; i++) + retList.add(ColumnNameHelper.max(maxSeen.get(i), components.get(i), ct.types.get(i))); + for (int i = minSize; i < maxSize; i++) + retList.add(biggest.get(i)); + return retList; } else @@ -65,7 +75,6 @@ public class ColumnNameHelper if (maxSeen.size() == 0) return Collections.singletonList(candidate); return Collections.singletonList(ColumnNameHelper.max(maxSeen.get(0), candidate, comparator)); - } } /** @@ -87,16 +96,24 @@ public class ColumnNameHelper { if (comparator instanceof CompositeType) { - if (minSeen.size() == 0) - return Arrays.asList(((CompositeType)comparator).split(candidate)); - - List<AbstractCompositeType.CompositeComponent> components = ((AbstractCompositeType)comparator).deconstruct(candidate); - List<ByteBuffer> retList = new ArrayList<ByteBuffer>(components.size()); - for (int i = 0; i < minSeen.size(); i++) - { - AbstractCompositeType.CompositeComponent component = components.get(i); - retList.add(ColumnNameHelper.min(minSeen.get(i), component.value, component.comparator)); - } + CompositeType ct = (CompositeType)comparator; + if (minSeen.isEmpty()) + return Arrays.asList(ct.split(candidate)); + + int typeCount = getTypeCount(ct); + + List<ByteBuffer> components = Arrays.asList(ct.split(candidate)); + List<ByteBuffer> biggest = minSeen.size() > components.size() ? minSeen : components; + // if typecount is less than both the components and maxseen, we only collect typecount columns. + int minSize = Math.min(typeCount, Math.min(components.size(), minSeen.size())); + int maxSize = Math.min(typeCount, biggest.size()); + List<ByteBuffer> retList = new ArrayList<ByteBuffer>(maxSize); + + for (int i = 0; i < minSize; i++) + retList.add(ColumnNameHelper.min(minSeen.get(i), components.get(i), ct.types.get(i))); + for (int i = minSize; i < maxSize; i++) + retList.add(biggest.get(i)); + return retList; } else @@ -156,20 +173,27 @@ public class ColumnNameHelper */ public static List<ByteBuffer> mergeMin(List<ByteBuffer> minColumnNames, List<ByteBuffer> candidates, AbstractType<?> columnNameComparator) { - if (minColumnNames.size() == 0) + if (minColumnNames.isEmpty()) return candidates; - if (candidates.size() == 0) + if (candidates.isEmpty()) return minColumnNames; if (columnNameComparator instanceof CompositeType) { CompositeType ct = (CompositeType)columnNameComparator; - List<ByteBuffer> retList = new ArrayList<ByteBuffer>(ct.types.size()); - for (int i = 0; i < minColumnNames.size(); i++) - { + List<ByteBuffer> biggest = minColumnNames.size() > candidates.size() ? minColumnNames : candidates; + int typeCount = getTypeCount(ct); + int minSize = Math.min(typeCount, Math.min(minColumnNames.size(), candidates.size())); + int maxSize = Math.min(typeCount, biggest.size()); + + List<ByteBuffer> retList = new ArrayList<ByteBuffer>(maxSize); + + for (int i = 0; i < minSize; i++) retList.add(min(minColumnNames.get(i), candidates.get(i), ct.types.get(i))); - } + for (int i = minSize; i < maxSize; i++) + retList.add(biggest.get(i)); + return retList; } else @@ -192,20 +216,26 @@ public class ColumnNameHelper */ public static List<ByteBuffer> mergeMax(List<ByteBuffer> maxColumnNames, List<ByteBuffer> candidates, AbstractType<?> columnNameComparator) { - if (maxColumnNames.size() == 0) + if (maxColumnNames.isEmpty()) return candidates; - if (candidates.size() == 0) + if (candidates.isEmpty()) return maxColumnNames; if (columnNameComparator instanceof CompositeType) { CompositeType ct = (CompositeType)columnNameComparator; - List<ByteBuffer> retList = new ArrayList<ByteBuffer>(ct.types.size()); - for (int i = 0; i < maxColumnNames.size(); i++) - { + List<ByteBuffer> biggest = maxColumnNames.size() > candidates.size() ? maxColumnNames : candidates; + int typeCount = getTypeCount(ct); + int minSize = Math.min(typeCount, Math.min(maxColumnNames.size(), candidates.size())); + int maxSize = Math.min(typeCount, biggest.size()); + List<ByteBuffer> retList = new ArrayList<ByteBuffer>(maxSize); + + for (int i = 0; i < minSize; i++) retList.add(max(maxColumnNames.get(i), candidates.get(i), ct.types.get(i))); - } + for (int i = minSize; i < maxSize; i++) + retList.add(biggest.get(i)); + return retList; } else @@ -214,4 +244,9 @@ public class ColumnNameHelper } } + + private static int getTypeCount(CompositeType ct) + { + return ct.types.get(ct.types.size() - 1) instanceof ColumnToCollectionType ? ct.types.size() - 1 : ct.types.size(); + } }