Optimize cellname comparison patch by benedict; reviewed by slebresne for CASSANDRA-6934
Project: http://git-wip-us.apache.org/repos/asf/cassandra/repo Commit: http://git-wip-us.apache.org/repos/asf/cassandra/commit/acf1b180 Tree: http://git-wip-us.apache.org/repos/asf/cassandra/tree/acf1b180 Diff: http://git-wip-us.apache.org/repos/asf/cassandra/diff/acf1b180 Branch: refs/heads/trunk Commit: acf1b1801352cdc6103325ff4498c2020dcc1c32 Parents: fad144a Author: belliottsmith <[email protected]> Authored: Fri Apr 25 16:56:34 2014 +0100 Committer: Sylvain Lebresne <[email protected]> Committed: Tue Apr 29 14:27:44 2014 +0200 ---------------------------------------------------------------------- CHANGES.txt | 1 + .../cassandra/db/composites/AbstractCType.java | 71 +++++++++----------- .../db/composites/AbstractCellNameType.java | 3 +- .../AbstractCompoundCellNameType.java | 1 + .../composites/AbstractSimpleCellNameType.java | 26 +++++++ .../cassandra/db/composites/Composite.java | 21 +++--- .../cassandra/db/composites/Composites.java | 9 +++ .../cassandra/db/composites/CompoundCType.java | 1 + .../composites/CompoundSparseCellNameType.java | 28 ++++++++ .../cassandra/db/composites/SimpleCType.java | 27 ++++++++ .../apache/cassandra/db/filter/ColumnSlice.java | 7 +- .../db/marshal/AbstractCompositeType.java | 6 +- .../cassandra/db/marshal/AbstractType.java | 9 +++ .../apache/cassandra/db/marshal/AsciiType.java | 8 ++- .../cassandra/db/marshal/BooleanType.java | 6 +- .../apache/cassandra/db/marshal/BytesType.java | 13 ++-- .../cassandra/db/marshal/CounterColumnType.java | 8 ++- .../apache/cassandra/db/marshal/DateType.java | 15 ++--- .../cassandra/db/marshal/DecimalType.java | 14 ++-- .../apache/cassandra/db/marshal/DoubleType.java | 10 +-- .../db/marshal/DynamicCompositeType.java | 5 ++ .../apache/cassandra/db/marshal/FloatType.java | 10 +-- .../cassandra/db/marshal/InetAddressType.java | 5 ++ .../apache/cassandra/db/marshal/Int32Type.java | 12 +--- .../cassandra/db/marshal/LexicalUUIDType.java | 10 +-- .../apache/cassandra/db/marshal/ListType.java | 6 +- .../apache/cassandra/db/marshal/LongType.java | 11 +-- .../apache/cassandra/db/marshal/MapType.java | 11 +-- .../apache/cassandra/db/marshal/SetType.java | 5 ++ .../cassandra/db/marshal/TimeUUIDType.java | 11 +-- .../apache/cassandra/db/marshal/UTF8Type.java | 8 ++- .../apache/cassandra/db/marshal/UUIDType.java | 1 + .../cassandra/hadoop/cql3/CqlRecordReader.java | 4 +- .../apache/cassandra/utils/ByteBufferUtil.java | 2 - .../org/apache/cassandra/utils/btree/BTree.java | 25 +------ .../apache/cassandra/utils/btree/Builder.java | 2 +- .../cassandra/utils/btree/NodeBuilder.java | 54 ++++++++++++--- .../org/apache/cassandra/utils/btree/Path.java | 32 ++++++++- 38 files changed, 309 insertions(+), 189 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/cassandra/blob/acf1b180/CHANGES.txt ---------------------------------------------------------------------- diff --git a/CHANGES.txt b/CHANGES.txt index 92cea62..09aebcd 100644 --- a/CHANGES.txt +++ b/CHANGES.txt @@ -53,6 +53,7 @@ * Use OpOrder to guard sstable references for reads (CASSANDRA-6919) * Preemptive opening of compaction result (CASSANDRA-6916) * Multi-threaded scrub/cleanup/upgradesstables (CASSANDRA-5547) + * Optimize cellname comparison (CASSANDRA-6934) Merged from 2.0: * Set JMX RMI port to 7199 (CASSANDRA-7087) * Use LOCAL_QUORUM for data reads at LOCAL_SERIAL (CASSANDRA-6939) http://git-wip-us.apache.org/repos/asf/cassandra/blob/acf1b180/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 e015379..0e73397 100644 --- a/src/java/org/apache/cassandra/db/composites/AbstractCType.java +++ b/src/java/org/apache/cassandra/db/composites/AbstractCType.java @@ -52,7 +52,9 @@ public abstract class AbstractCType implements CType private final RangeTombstone.Serializer rangeTombstoneSerializer; private final RowIndexEntry.Serializer rowIndexEntrySerializer; - protected AbstractCType() + protected final boolean isByteOrderComparable; + + protected AbstractCType(boolean isByteOrderComparable) { reverseComparator = new Comparator<Composite>() { @@ -84,57 +86,46 @@ public abstract class AbstractCType implements CType deletionInfoSerializer = new DeletionInfo.Serializer(this); rangeTombstoneSerializer = new RangeTombstone.Serializer(this); rowIndexEntrySerializer = new RowIndexEntry.Serializer(this); + this.isByteOrderComparable = isByteOrderComparable; } - public int compare(Composite c1, Composite c2) + protected static boolean isByteOrderComparable(Iterable<AbstractType<?>> types) { - if (c1 == null || c1.isEmpty()) - return c2 == null || c2.isEmpty() ? 0 : -1; - if (c2 == null || c2.isEmpty()) - return 1; - - if (c1.isStatic() != c2.isStatic()) - return c1.isStatic() ? -1 : 1; - - ByteBuffer previous = null; - int i; - int minSize = Math.min(c1.size(), c2.size()); - for (i = 0; i < minSize; i++) - { - AbstractType<?> comparator = subtype(i); - ByteBuffer value1 = c1.get(i); - ByteBuffer value2 = c2.get(i); - - int cmp = comparator.compareCollectionMembers(value1, value2, previous); - if (cmp != 0) - return cmp; + boolean isByteOrderComparable = true; + for (AbstractType<?> type : types) + isByteOrderComparable &= type.isByteOrderComparable(); + return isByteOrderComparable; + } - previous = value1; - } + public int compare(Composite c1, Composite c2) + { + int s1 = c1.size(); + int s2 = c2.size(); + int minSize = Math.min(s1, s2); - if (c1.size() == c2.size()) + if (isByteOrderComparable) { - if (c1.eoc() != c2.eoc()) + for (int i = 0; i < minSize; i++) { - switch (c1.eoc()) - { - case START: return -1; - case END: return 1; - case NONE: return c2.eoc() == Composite.EOC.START ? 1 : -1; - } + int cmp = ByteBufferUtil.compareUnsigned(c1.get(i), c2.get(i)); + if (cmp != 0) + return cmp; } - return 0; - } - - if (i == c1.size()) - { - return c1.eoc() == Composite.EOC.END ? 1 : -1; } else { - assert i == c2.size(); - return c2.eoc() == Composite.EOC.END ? -1 : 1; + for (int i = 0; i < minSize; i++) + { + AbstractType<?> comparator = subtype(i); + int cmp = comparator.compare(c1.get(i), c2.get(i)); + if (cmp != 0) + return cmp; + } } + + if (s1 == s2) + return c1.eoc().compareTo(c2.eoc()); + return s1 < s2 ? c1.eoc().prefixComparisonResult : -c2.eoc().prefixComparisonResult; } public void validate(Composite name) http://git-wip-us.apache.org/repos/asf/cassandra/blob/acf1b180/src/java/org/apache/cassandra/db/composites/AbstractCellNameType.java ---------------------------------------------------------------------- diff --git a/src/java/org/apache/cassandra/db/composites/AbstractCellNameType.java b/src/java/org/apache/cassandra/db/composites/AbstractCellNameType.java index 74e24f7..826f71a 100644 --- a/src/java/org/apache/cassandra/db/composites/AbstractCellNameType.java +++ b/src/java/org/apache/cassandra/db/composites/AbstractCellNameType.java @@ -50,8 +50,9 @@ public abstract class AbstractCellNameType extends AbstractCType implements Cell private final IVersionedSerializer<NamesQueryFilter> namesQueryFilterSerializer; private final IVersionedSerializer<IDiskAtomFilter> diskAtomFilterSerializer; - protected AbstractCellNameType() + protected AbstractCellNameType(boolean isByteOrderComparable) { + super(isByteOrderComparable); columnComparator = new Comparator<Cell>() { public int compare(Cell c1, Cell c2) http://git-wip-us.apache.org/repos/asf/cassandra/blob/acf1b180/src/java/org/apache/cassandra/db/composites/AbstractCompoundCellNameType.java ---------------------------------------------------------------------- diff --git a/src/java/org/apache/cassandra/db/composites/AbstractCompoundCellNameType.java b/src/java/org/apache/cassandra/db/composites/AbstractCompoundCellNameType.java index 1cb605e..641f14d 100644 --- a/src/java/org/apache/cassandra/db/composites/AbstractCompoundCellNameType.java +++ b/src/java/org/apache/cassandra/db/composites/AbstractCompoundCellNameType.java @@ -34,6 +34,7 @@ public abstract class AbstractCompoundCellNameType extends AbstractCellNameType protected AbstractCompoundCellNameType(CompoundCType clusteringType, CompoundCType fullType) { + super(isByteOrderComparable(fullType.types)); this.clusteringType = clusteringType; this.fullType = fullType; http://git-wip-us.apache.org/repos/asf/cassandra/blob/acf1b180/src/java/org/apache/cassandra/db/composites/AbstractSimpleCellNameType.java ---------------------------------------------------------------------- diff --git a/src/java/org/apache/cassandra/db/composites/AbstractSimpleCellNameType.java b/src/java/org/apache/cassandra/db/composites/AbstractSimpleCellNameType.java index 94c0c4d..6500069 100644 --- a/src/java/org/apache/cassandra/db/composites/AbstractSimpleCellNameType.java +++ b/src/java/org/apache/cassandra/db/composites/AbstractSimpleCellNameType.java @@ -30,6 +30,7 @@ public abstract class AbstractSimpleCellNameType extends AbstractCellNameType protected AbstractSimpleCellNameType(AbstractType<?> type) { + super(type.isByteOrderComparable()); this.type = type; } @@ -43,6 +44,31 @@ public abstract class AbstractSimpleCellNameType extends AbstractCellNameType return 1; } + public int compare(Composite c1, Composite c2) + { + // This method assumes that simple composites never have an EOC != NONE. This assumption + // stands in particular on the fact that a Composites.EMPTY never has a non-NONE EOC. If + // this ever change, we'll need to update this. + + if (isByteOrderComparable) + { + // toByteBuffer is always cheap for simple types, and we keep virtual method calls to a minimum: + // hasRemaining will always be inlined, as will most of the call-stack for BBU.compareUnsigned + ByteBuffer b1 = c1.toByteBuffer(); + ByteBuffer b2 = c2.toByteBuffer(); + if (!b1.hasRemaining() || !b2.hasRemaining()) + return b1.hasRemaining() ? 1 : (b2.hasRemaining() ? -1 : 0); + return ByteBufferUtil.compareUnsigned(b1, b2); + } + + boolean c1isEmpty = c1.isEmpty(); + boolean c2isEmpty = c2.isEmpty(); + if (c1isEmpty || c2isEmpty) + return c1isEmpty ? 1 : (c2isEmpty ? -1 : 0); + + return type.compare(c1.get(0), c2.get(0)); + } + public AbstractType<?> subtype(int i) { if (i != 0) http://git-wip-us.apache.org/repos/asf/cassandra/blob/acf1b180/src/java/org/apache/cassandra/db/composites/Composite.java ---------------------------------------------------------------------- diff --git a/src/java/org/apache/cassandra/db/composites/Composite.java b/src/java/org/apache/cassandra/db/composites/Composite.java index 98b1c91..b15daef 100644 --- a/src/java/org/apache/cassandra/db/composites/Composite.java +++ b/src/java/org/apache/cassandra/db/composites/Composite.java @@ -39,22 +39,21 @@ public interface Composite extends IMeasurableMemory { public enum EOC { - START, NONE, END; + START(-1), NONE(-1), END(1); - public static EOC from(int eoc) + // If composite p has this EOC and is a strict prefix of composite c, then this + // the result of the comparison of p and c. Basically, p sorts before c unless + // it's EOC is END. + public final int prefixComparisonResult; + + private EOC(int prefixComparisonResult) { - return eoc == 0 ? NONE : (eoc < 0 ? START : END); + this.prefixComparisonResult = prefixComparisonResult; } - public byte toByte() + public static EOC from(int eoc) { - switch (this) - { - case START: return (byte)-1; - case NONE: return (byte) 0; - case END: return (byte) 1; - default: throw new AssertionError(); - } + return eoc == 0 ? NONE : (eoc < 0 ? START : END); } } http://git-wip-us.apache.org/repos/asf/cassandra/blob/acf1b180/src/java/org/apache/cassandra/db/composites/Composites.java ---------------------------------------------------------------------- diff --git a/src/java/org/apache/cassandra/db/composites/Composites.java b/src/java/org/apache/cassandra/db/composites/Composites.java index 42ec72d..58938c6 100644 --- a/src/java/org/apache/cassandra/db/composites/Composites.java +++ b/src/java/org/apache/cassandra/db/composites/Composites.java @@ -65,16 +65,25 @@ public abstract class Composites public Composite start() { + // Note that SimpleCType/AbstractSimpleCellNameType compare method + // indirectly rely on the fact that EMPTY == EMPTY.start() == EMPTY.end() + // (or more precisely on the fact that the EOC is NONE for all of those). return this; } public Composite end() { + // Note that SimpleCType/AbstractSimpleCellNameType compare method + // indirectly rely on the fact that EMPTY == EMPTY.start() == EMPTY.end() + // (or more precisely on the fact that the EOC is NONE for all of those). return this; } public Composite withEOC(EOC newEoc) { + // Note that SimpleCType/AbstractSimpleCellNameType compare method + // indirectly rely on the fact that EMPTY == EMPTY.start() == EMPTY.end() + // (or more precisely on the fact that the EOC is NONE for all of those). return this; } http://git-wip-us.apache.org/repos/asf/cassandra/blob/acf1b180/src/java/org/apache/cassandra/db/composites/CompoundCType.java ---------------------------------------------------------------------- diff --git a/src/java/org/apache/cassandra/db/composites/CompoundCType.java b/src/java/org/apache/cassandra/db/composites/CompoundCType.java index d638f16..4322055 100644 --- a/src/java/org/apache/cassandra/db/composites/CompoundCType.java +++ b/src/java/org/apache/cassandra/db/composites/CompoundCType.java @@ -35,6 +35,7 @@ public class CompoundCType extends AbstractCType // It's up to the caller to pass a list that is effectively immutable public CompoundCType(List<AbstractType<?>> types) { + super(isByteOrderComparable(types)); this.types = types; } http://git-wip-us.apache.org/repos/asf/cassandra/blob/acf1b180/src/java/org/apache/cassandra/db/composites/CompoundSparseCellNameType.java ---------------------------------------------------------------------- diff --git a/src/java/org/apache/cassandra/db/composites/CompoundSparseCellNameType.java b/src/java/org/apache/cassandra/db/composites/CompoundSparseCellNameType.java index bcb500d..29e1617 100644 --- a/src/java/org/apache/cassandra/db/composites/CompoundSparseCellNameType.java +++ b/src/java/org/apache/cassandra/db/composites/CompoundSparseCellNameType.java @@ -41,6 +41,7 @@ public class CompoundSparseCellNameType extends AbstractCompoundCellNameType protected final Map<ByteBuffer, ColumnIdentifier> internedIds; private final Composite staticPrefix; + private final boolean isByteOrderComparable; public CompoundSparseCellNameType(List<AbstractType<?>> types) { @@ -63,6 +64,7 @@ public class CompoundSparseCellNameType extends AbstractCompoundCellNameType this.columnNameType = columnNameType; this.internedIds = internedIds; this.staticPrefix = makeStaticPrefix(clusteringType.size()); + this.isByteOrderComparable = isByteOrderComparable(fullType.types); } private static Composite makeStaticPrefix(int size) @@ -263,6 +265,32 @@ public class CompoundSparseCellNameType extends AbstractCompoundCellNameType } @Override + public int compare(Composite c1, Composite c2) + { + int s1 = c1.size(); + int s2 = c2.size(); + int minSize = Math.min(s1, s2); + + ByteBuffer previous = null; + for (int i = 0; i < minSize; i++) + { + AbstractType<?> comparator = subtype(i); + ByteBuffer value1 = c1.get(i); + ByteBuffer value2 = c2.get(i); + + int cmp = comparator.compareCollectionMembers(value1, value2, previous); + if (cmp != 0) + return cmp; + + previous = value1; + } + + if (s1 == s2) + return c1.eoc().compareTo(c2.eoc()); + return s1 < s2 ? c1.eoc().prefixComparisonResult : -c2.eoc().prefixComparisonResult; + } + + @Override public boolean hasCollections() { return true; http://git-wip-us.apache.org/repos/asf/cassandra/blob/acf1b180/src/java/org/apache/cassandra/db/composites/SimpleCType.java ---------------------------------------------------------------------- diff --git a/src/java/org/apache/cassandra/db/composites/SimpleCType.java b/src/java/org/apache/cassandra/db/composites/SimpleCType.java index 08ace8b..fe86655 100644 --- a/src/java/org/apache/cassandra/db/composites/SimpleCType.java +++ b/src/java/org/apache/cassandra/db/composites/SimpleCType.java @@ -20,6 +20,7 @@ package org.apache.cassandra.db.composites; import java.nio.ByteBuffer; import org.apache.cassandra.db.marshal.AbstractType; +import org.apache.cassandra.utils.ByteBufferUtil; /** * A not truly-composite CType. @@ -30,6 +31,7 @@ public class SimpleCType extends AbstractCType public SimpleCType(AbstractType<?> type) { + super(type.isByteOrderComparable()); this.type = type; } @@ -43,6 +45,31 @@ public class SimpleCType extends AbstractCType return 1; } + public int compare(Composite c1, Composite c2) + { + // This method assumes that simple composites never have an EOC != NONE. This assumption + // stands in particular on the fact that a Composites.EMPTY never has a non-NONE EOC. If + // this ever change, we'll need to update this. + + if (isByteOrderComparable) + { + // toByteBuffer is always cheap for simple types, and we keep virtual method calls to a minimum: + // hasRemaining will always be inlined, as will most of the call-stack for BBU.compareUnsigned + ByteBuffer b1 = c1.toByteBuffer(); + ByteBuffer b2 = c2.toByteBuffer(); + if (!b1.hasRemaining() || !b2.hasRemaining()) + + return ByteBufferUtil.compareUnsigned(b1, b2); + } + + boolean c1isEmpty = c1.isEmpty(); + boolean c2isEmpty = c2.isEmpty(); + if (c1isEmpty || c2isEmpty) + return c1isEmpty ? 1 : (c2isEmpty ? -1 : 0); + + return type.compare(c1.get(0), c2.get(0)); + } + public AbstractType<?> subtype(int i) { if (i != 0) http://git-wip-us.apache.org/repos/asf/cassandra/blob/acf1b180/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 ad3b2fe..6821e94 100644 --- a/src/java/org/apache/cassandra/db/filter/ColumnSlice.java +++ b/src/java/org/apache/cassandra/db/filter/ColumnSlice.java @@ -219,7 +219,7 @@ public class ColumnSlice private static Cell fakeCell(Composite name) { - return new BufferCell(new FakeCellName(name), ByteBufferUtil.EMPTY_BYTE_BUFFER); + return new BufferCell(name instanceof CellName ? (CellName) name : new FakeCellName(name), ByteBufferUtil.EMPTY_BYTE_BUFFER); } /* @@ -260,6 +260,11 @@ public class ColumnSlice return prefix.eoc(); } + public ByteBuffer toByteBuffer() + { + return prefix.toByteBuffer(); + } + public int clusteringSize() { throw new UnsupportedOperationException(); http://git-wip-us.apache.org/repos/asf/cassandra/blob/acf1b180/src/java/org/apache/cassandra/db/marshal/AbstractCompositeType.java ---------------------------------------------------------------------- diff --git a/src/java/org/apache/cassandra/db/marshal/AbstractCompositeType.java b/src/java/org/apache/cassandra/db/marshal/AbstractCompositeType.java index 8f3aec4..4e830ab 100644 --- a/src/java/org/apache/cassandra/db/marshal/AbstractCompositeType.java +++ b/src/java/org/apache/cassandra/db/marshal/AbstractCompositeType.java @@ -37,10 +37,8 @@ public abstract class AbstractCompositeType extends AbstractType<ByteBuffer> { public int compare(ByteBuffer o1, ByteBuffer o2) { - if (o1 == null || !o1.hasRemaining()) - return o2 == null || !o2.hasRemaining() ? 0 : -1; - if (o2 == null || !o2.hasRemaining()) - return 1; + if (!o1.hasRemaining() || !o2.hasRemaining()) + return o1.hasRemaining() ? 1 : o2.hasRemaining() ? -1 : 0; ByteBuffer bb1 = o1.duplicate(); ByteBuffer bb2 = o2.duplicate(); http://git-wip-us.apache.org/repos/asf/cassandra/blob/acf1b180/src/java/org/apache/cassandra/db/marshal/AbstractType.java ---------------------------------------------------------------------- diff --git a/src/java/org/apache/cassandra/db/marshal/AbstractType.java b/src/java/org/apache/cassandra/db/marshal/AbstractType.java index ce233de..631e05a 100644 --- a/src/java/org/apache/cassandra/db/marshal/AbstractType.java +++ b/src/java/org/apache/cassandra/db/marshal/AbstractType.java @@ -162,6 +162,15 @@ public abstract class AbstractType<T> implements Comparator<ByteBuffer> } /** + * @return true IFF the byte representation of this type can be compared unsigned + * and always return the same result as calling this object's compare or compareCollectionMembers methods + */ + public boolean isByteOrderComparable() + { + return false; + } + + /** * An alternative comparison function used by CollectionsType in conjunction with CompositeType. * * This comparator is only called to compare components of a CompositeType. It gets the value of the http://git-wip-us.apache.org/repos/asf/cassandra/blob/acf1b180/src/java/org/apache/cassandra/db/marshal/AsciiType.java ---------------------------------------------------------------------- diff --git a/src/java/org/apache/cassandra/db/marshal/AsciiType.java b/src/java/org/apache/cassandra/db/marshal/AsciiType.java index 74ae6be..3b64cc0 100644 --- a/src/java/org/apache/cassandra/db/marshal/AsciiType.java +++ b/src/java/org/apache/cassandra/db/marshal/AsciiType.java @@ -22,6 +22,7 @@ import java.nio.ByteBuffer; import org.apache.cassandra.cql3.CQL3Type; import org.apache.cassandra.serializers.TypeSerializer; import org.apache.cassandra.serializers.AsciiSerializer; +import org.apache.cassandra.utils.ByteBufferUtil; public class AsciiType extends AbstractType<String> { @@ -31,7 +32,7 @@ public class AsciiType extends AbstractType<String> public int compare(ByteBuffer o1, ByteBuffer o2) { - return BytesType.bytesCompare(o1, o2); + return ByteBufferUtil.compareUnsigned(o1, o2); } public ByteBuffer fromString(String source) @@ -48,4 +49,9 @@ public class AsciiType extends AbstractType<String> { return AsciiSerializer.instance; } + + public boolean isByteOrderComparable() + { + return true; + } } http://git-wip-us.apache.org/repos/asf/cassandra/blob/acf1b180/src/java/org/apache/cassandra/db/marshal/BooleanType.java ---------------------------------------------------------------------- diff --git a/src/java/org/apache/cassandra/db/marshal/BooleanType.java b/src/java/org/apache/cassandra/db/marshal/BooleanType.java index d5f44ce..70d7559 100644 --- a/src/java/org/apache/cassandra/db/marshal/BooleanType.java +++ b/src/java/org/apache/cassandra/db/marshal/BooleanType.java @@ -37,10 +37,8 @@ public class BooleanType extends AbstractType<Boolean> public int compare(ByteBuffer o1, ByteBuffer o2) { - if ((o1 == null) || (o1.remaining() != 1)) - return ((o2 == null) || (o2.remaining() != 1)) ? 0 : -1; - if ((o2 == null) || (o2.remaining() != 1)) - return 1; + if (!o1.hasRemaining() || !o2.hasRemaining()) + return o1.hasRemaining() ? 1 : o2.hasRemaining() ? -1 : 0; // False is 0, True is anything else, makes False sort before True. byte b1 = o1.get(o1.position()); http://git-wip-us.apache.org/repos/asf/cassandra/blob/acf1b180/src/java/org/apache/cassandra/db/marshal/BytesType.java ---------------------------------------------------------------------- diff --git a/src/java/org/apache/cassandra/db/marshal/BytesType.java b/src/java/org/apache/cassandra/db/marshal/BytesType.java index 9e122cc..9d9eb05 100644 --- a/src/java/org/apache/cassandra/db/marshal/BytesType.java +++ b/src/java/org/apache/cassandra/db/marshal/BytesType.java @@ -34,14 +34,6 @@ public class BytesType extends AbstractType<ByteBuffer> public int compare(ByteBuffer o1, ByteBuffer o2) { - return BytesType.bytesCompare(o1, o2); - } - - public static int bytesCompare(ByteBuffer o1, ByteBuffer o2) - { - if (o1 == null) - return o2 == null ? 0 : -1; - return ByteBufferUtil.compareUnsigned(o1, o2); } @@ -72,6 +64,11 @@ public class BytesType extends AbstractType<ByteBuffer> return true; } + public boolean isByteOrderComparable() + { + return true; + } + public CQL3Type asCQL3Type() { return CQL3Type.Native.BLOB; http://git-wip-us.apache.org/repos/asf/cassandra/blob/acf1b180/src/java/org/apache/cassandra/db/marshal/CounterColumnType.java ---------------------------------------------------------------------- diff --git a/src/java/org/apache/cassandra/db/marshal/CounterColumnType.java b/src/java/org/apache/cassandra/db/marshal/CounterColumnType.java index 73e9f6f..2bcb4db 100644 --- a/src/java/org/apache/cassandra/db/marshal/CounterColumnType.java +++ b/src/java/org/apache/cassandra/db/marshal/CounterColumnType.java @@ -36,6 +36,11 @@ public class CounterColumnType extends AbstractType<Long> return true; } + public boolean isByteOrderComparable() + { + throw new AssertionError(); + } + @Override public Long compose(ByteBuffer bytes) { @@ -50,9 +55,6 @@ public class CounterColumnType extends AbstractType<Long> public int compare(ByteBuffer o1, ByteBuffer o2) { - if (o1 == null) - return o2 == null ? 0 : -1; - return ByteBufferUtil.compareUnsigned(o1, o2); } http://git-wip-us.apache.org/repos/asf/cassandra/blob/acf1b180/src/java/org/apache/cassandra/db/marshal/DateType.java ---------------------------------------------------------------------- diff --git a/src/java/org/apache/cassandra/db/marshal/DateType.java b/src/java/org/apache/cassandra/db/marshal/DateType.java index 1ca5fa8..f63b878 100644 --- a/src/java/org/apache/cassandra/db/marshal/DateType.java +++ b/src/java/org/apache/cassandra/db/marshal/DateType.java @@ -41,14 +41,8 @@ public class DateType extends AbstractType<Date> public int compare(ByteBuffer o1, ByteBuffer o2) { - if (o1.remaining() == 0) - { - return o2.remaining() == 0 ? 0 : -1; - } - if (o2.remaining() == 0) - { - return 1; - } + if (!o1.hasRemaining() || !o2.hasRemaining()) + return o1.hasRemaining() ? 1 : o2.hasRemaining() ? -1 : 0; return ByteBufferUtil.compareUnsigned(o1, o2); } @@ -116,6 +110,11 @@ public class DateType extends AbstractType<Date> return false; } + public boolean isByteOrderComparable() + { + return true; + } + @Override public CQL3Type asCQL3Type() { http://git-wip-us.apache.org/repos/asf/cassandra/blob/acf1b180/src/java/org/apache/cassandra/db/marshal/DecimalType.java ---------------------------------------------------------------------- diff --git a/src/java/org/apache/cassandra/db/marshal/DecimalType.java b/src/java/org/apache/cassandra/db/marshal/DecimalType.java index 2ac8480..b7e481d 100644 --- a/src/java/org/apache/cassandra/db/marshal/DecimalType.java +++ b/src/java/org/apache/cassandra/db/marshal/DecimalType.java @@ -32,18 +32,12 @@ public class DecimalType extends AbstractType<BigDecimal> DecimalType() {} // singleton - public int compare(ByteBuffer bb0, ByteBuffer bb1) + public int compare(ByteBuffer o1, ByteBuffer o2) { - if (bb0.remaining() == 0) - { - return bb1.remaining() == 0 ? 0 : -1; - } - if (bb1.remaining() == 0) - { - return 1; - } + if (!o1.hasRemaining() || !o2.hasRemaining()) + return o1.hasRemaining() ? 1 : o2.hasRemaining() ? -1 : 0; - return compose(bb0).compareTo(compose(bb1)); + return compose(o1).compareTo(compose(o2)); } public ByteBuffer fromString(String source) throws MarshalException http://git-wip-us.apache.org/repos/asf/cassandra/blob/acf1b180/src/java/org/apache/cassandra/db/marshal/DoubleType.java ---------------------------------------------------------------------- diff --git a/src/java/org/apache/cassandra/db/marshal/DoubleType.java b/src/java/org/apache/cassandra/db/marshal/DoubleType.java index 35b33d6..af11a36 100644 --- a/src/java/org/apache/cassandra/db/marshal/DoubleType.java +++ b/src/java/org/apache/cassandra/db/marshal/DoubleType.java @@ -33,14 +33,8 @@ public class DoubleType extends AbstractType<Double> public int compare(ByteBuffer o1, ByteBuffer o2) { - if (o1.remaining() == 0) - { - return o2.remaining() == 0 ? 0 : -1; - } - if (o2.remaining() == 0) - { - return 1; - } + if (!o1.hasRemaining() || !o2.hasRemaining()) + return o1.hasRemaining() ? 1 : o2.hasRemaining() ? -1 : 0; return compose(o1).compareTo(compose(o2)); } http://git-wip-us.apache.org/repos/asf/cassandra/blob/acf1b180/src/java/org/apache/cassandra/db/marshal/DynamicCompositeType.java ---------------------------------------------------------------------- diff --git a/src/java/org/apache/cassandra/db/marshal/DynamicCompositeType.java b/src/java/org/apache/cassandra/db/marshal/DynamicCompositeType.java index 8311e7e..7f39a11 100644 --- a/src/java/org/apache/cassandra/db/marshal/DynamicCompositeType.java +++ b/src/java/org/apache/cassandra/db/marshal/DynamicCompositeType.java @@ -391,5 +391,10 @@ public class DynamicCompositeType extends AbstractCompositeType { throw new UnsupportedOperationException(); } + + public boolean isByteOrderComparable() + { + return false; + } } } http://git-wip-us.apache.org/repos/asf/cassandra/blob/acf1b180/src/java/org/apache/cassandra/db/marshal/FloatType.java ---------------------------------------------------------------------- diff --git a/src/java/org/apache/cassandra/db/marshal/FloatType.java b/src/java/org/apache/cassandra/db/marshal/FloatType.java index bee226e..9364928 100644 --- a/src/java/org/apache/cassandra/db/marshal/FloatType.java +++ b/src/java/org/apache/cassandra/db/marshal/FloatType.java @@ -34,14 +34,8 @@ public class FloatType extends AbstractType<Float> public int compare(ByteBuffer o1, ByteBuffer o2) { - if (o1.remaining() == 0) - { - return o2.remaining() == 0 ? 0 : -1; - } - if (o2.remaining() == 0) - { - return 1; - } + if (!o1.hasRemaining() || !o2.hasRemaining()) + return o1.hasRemaining() ? 1 : o2.hasRemaining() ? -1 : 0; return compose(o1).compareTo(compose(o2)); } http://git-wip-us.apache.org/repos/asf/cassandra/blob/acf1b180/src/java/org/apache/cassandra/db/marshal/InetAddressType.java ---------------------------------------------------------------------- diff --git a/src/java/org/apache/cassandra/db/marshal/InetAddressType.java b/src/java/org/apache/cassandra/db/marshal/InetAddressType.java index c29e8ac..0473ee8 100644 --- a/src/java/org/apache/cassandra/db/marshal/InetAddressType.java +++ b/src/java/org/apache/cassandra/db/marshal/InetAddressType.java @@ -66,4 +66,9 @@ public class InetAddressType extends AbstractType<InetAddress> { return InetAddressSerializer.instance; } + + public boolean isByteOrderComparable() + { + return true; + } } http://git-wip-us.apache.org/repos/asf/cassandra/blob/acf1b180/src/java/org/apache/cassandra/db/marshal/Int32Type.java ---------------------------------------------------------------------- diff --git a/src/java/org/apache/cassandra/db/marshal/Int32Type.java b/src/java/org/apache/cassandra/db/marshal/Int32Type.java index 2f37721..976c7a8 100644 --- a/src/java/org/apache/cassandra/db/marshal/Int32Type.java +++ b/src/java/org/apache/cassandra/db/marshal/Int32Type.java @@ -35,20 +35,13 @@ public class Int32Type extends AbstractType<Integer> public int compare(ByteBuffer o1, ByteBuffer o2) { - if (o1.remaining() == 0) - { - return o2.remaining() == 0 ? 0 : -1; - } - if (o2.remaining() == 0) - { - return 1; - } + if (!o1.hasRemaining() || !o2.hasRemaining()) + return o1.hasRemaining() ? 1 : o2.hasRemaining() ? -1 : 0; int diff = o1.get(o1.position()) - o2.get(o2.position()); if (diff != 0) return diff; - return ByteBufferUtil.compareUnsigned(o1, o2); } @@ -81,4 +74,5 @@ public class Int32Type extends AbstractType<Integer> { return Int32Serializer.instance; } + } http://git-wip-us.apache.org/repos/asf/cassandra/blob/acf1b180/src/java/org/apache/cassandra/db/marshal/LexicalUUIDType.java ---------------------------------------------------------------------- diff --git a/src/java/org/apache/cassandra/db/marshal/LexicalUUIDType.java b/src/java/org/apache/cassandra/db/marshal/LexicalUUIDType.java index 303169f..634194f 100644 --- a/src/java/org/apache/cassandra/db/marshal/LexicalUUIDType.java +++ b/src/java/org/apache/cassandra/db/marshal/LexicalUUIDType.java @@ -36,14 +36,8 @@ public class LexicalUUIDType extends AbstractType<UUID> public int compare(ByteBuffer o1, ByteBuffer o2) { - if (o1.remaining() == 0) - { - return o2.remaining() == 0 ? 0 : -1; - } - if (o2.remaining() == 0) - { - return 1; - } + if (!o1.hasRemaining() || !o2.hasRemaining()) + return o1.hasRemaining() ? 1 : o2.hasRemaining() ? -1 : 0; return UUIDGen.getUUID(o1).compareTo(UUIDGen.getUUID(o2)); } http://git-wip-us.apache.org/repos/asf/cassandra/blob/acf1b180/src/java/org/apache/cassandra/db/marshal/ListType.java ---------------------------------------------------------------------- diff --git a/src/java/org/apache/cassandra/db/marshal/ListType.java b/src/java/org/apache/cassandra/db/marshal/ListType.java index 1cc0425..43ace65 100644 --- a/src/java/org/apache/cassandra/db/marshal/ListType.java +++ b/src/java/org/apache/cassandra/db/marshal/ListType.java @@ -86,10 +86,8 @@ public class ListType<T> extends CollectionType<List<T>> static int compareListOrSet(AbstractType<?> elementsComparator, ByteBuffer o1, ByteBuffer o2) { // Note that this is only used if the collection is inside an UDT - if (o1 == null || !o1.hasRemaining()) - return o2 == null || !o2.hasRemaining() ? 0 : -1; - if (o2 == null || !o2.hasRemaining()) - return 1; + if (!o1.hasRemaining() || !o2.hasRemaining()) + return o1.hasRemaining() ? 1 : o2.hasRemaining() ? -1 : 0; ByteBuffer bb1 = o1.duplicate(); ByteBuffer bb2 = o2.duplicate(); http://git-wip-us.apache.org/repos/asf/cassandra/blob/acf1b180/src/java/org/apache/cassandra/db/marshal/LongType.java ---------------------------------------------------------------------- diff --git a/src/java/org/apache/cassandra/db/marshal/LongType.java b/src/java/org/apache/cassandra/db/marshal/LongType.java index 9ad078e..5f073c9 100644 --- a/src/java/org/apache/cassandra/db/marshal/LongType.java +++ b/src/java/org/apache/cassandra/db/marshal/LongType.java @@ -38,14 +38,8 @@ public class LongType extends AbstractType<Long> public static int compareLongs(ByteBuffer o1, ByteBuffer o2) { - if (o1.remaining() == 0) - { - return o2.remaining() == 0 ? 0 : -1; - } - if (o2.remaining() == 0) - { - return 1; - } + if (!o1.hasRemaining() || !o2.hasRemaining()) + return o1.hasRemaining() ? 1 : o2.hasRemaining() ? -1 : 0; int diff = o1.get(o1.position()) - o2.get(o2.position()); if (diff != 0) @@ -83,4 +77,5 @@ public class LongType extends AbstractType<Long> { return LongSerializer.instance; } + } http://git-wip-us.apache.org/repos/asf/cassandra/blob/acf1b180/src/java/org/apache/cassandra/db/marshal/MapType.java ---------------------------------------------------------------------- diff --git a/src/java/org/apache/cassandra/db/marshal/MapType.java b/src/java/org/apache/cassandra/db/marshal/MapType.java index 2e693d6..213e213 100644 --- a/src/java/org/apache/cassandra/db/marshal/MapType.java +++ b/src/java/org/apache/cassandra/db/marshal/MapType.java @@ -80,10 +80,8 @@ public class MapType<K, V> extends CollectionType<Map<K, V>> public int compare(ByteBuffer o1, ByteBuffer o2) { // Note that this is only used if the collection is inside an UDT - if (o1 == null || !o1.hasRemaining()) - return o2 == null || !o2.hasRemaining() ? 0 : -1; - if (o2 == null || !o2.hasRemaining()) - return 1; + if (!o1.hasRemaining() || !o2.hasRemaining()) + return o1.hasRemaining() ? 1 : o2.hasRemaining() ? -1 : 0; ByteBuffer bb1 = o1.duplicate(); ByteBuffer bb2 = o2.duplicate(); @@ -115,6 +113,11 @@ public class MapType<K, V> extends CollectionType<Map<K, V>> return serializer; } + public boolean isByteOrderComparable() + { + return keys.isByteOrderComparable(); + } + protected void appendToStringBuilder(StringBuilder sb) { sb.append(getClass().getName()).append(TypeParser.stringifyTypeParameters(Arrays.asList(keys, values))); http://git-wip-us.apache.org/repos/asf/cassandra/blob/acf1b180/src/java/org/apache/cassandra/db/marshal/SetType.java ---------------------------------------------------------------------- diff --git a/src/java/org/apache/cassandra/db/marshal/SetType.java b/src/java/org/apache/cassandra/db/marshal/SetType.java index 5c13c2e..3b686b8 100644 --- a/src/java/org/apache/cassandra/db/marshal/SetType.java +++ b/src/java/org/apache/cassandra/db/marshal/SetType.java @@ -82,6 +82,11 @@ public class SetType<T> extends CollectionType<Set<T>> return serializer; } + public boolean isByteOrderComparable() + { + return elements.isByteOrderComparable(); + } + protected void appendToStringBuilder(StringBuilder sb) { sb.append(getClass().getName()).append(TypeParser.stringifyTypeParameters(Collections.<AbstractType<?>>singletonList(elements))); http://git-wip-us.apache.org/repos/asf/cassandra/blob/acf1b180/src/java/org/apache/cassandra/db/marshal/TimeUUIDType.java ---------------------------------------------------------------------- diff --git a/src/java/org/apache/cassandra/db/marshal/TimeUUIDType.java b/src/java/org/apache/cassandra/db/marshal/TimeUUIDType.java index 51cf47a..82f5ce9 100644 --- a/src/java/org/apache/cassandra/db/marshal/TimeUUIDType.java +++ b/src/java/org/apache/cassandra/db/marshal/TimeUUIDType.java @@ -40,14 +40,9 @@ public class TimeUUIDType extends AbstractType<UUID> public int compare(ByteBuffer o1, ByteBuffer o2) { - if (o1.remaining() == 0) - { - return o2.remaining() == 0 ? 0 : -1; - } - if (o2.remaining() == 0) - { - return 1; - } + if (!o1.hasRemaining() || !o2.hasRemaining()) + return o1.hasRemaining() ? 1 : o2.hasRemaining() ? -1 : 0; + int res = compareTimestampBytes(o1, o2); if (res != 0) return res; http://git-wip-us.apache.org/repos/asf/cassandra/blob/acf1b180/src/java/org/apache/cassandra/db/marshal/UTF8Type.java ---------------------------------------------------------------------- diff --git a/src/java/org/apache/cassandra/db/marshal/UTF8Type.java b/src/java/org/apache/cassandra/db/marshal/UTF8Type.java index e763316..6d58db2 100644 --- a/src/java/org/apache/cassandra/db/marshal/UTF8Type.java +++ b/src/java/org/apache/cassandra/db/marshal/UTF8Type.java @@ -22,6 +22,7 @@ import java.nio.ByteBuffer; import org.apache.cassandra.cql3.CQL3Type; import org.apache.cassandra.serializers.TypeSerializer; import org.apache.cassandra.serializers.UTF8Serializer; +import org.apache.cassandra.utils.ByteBufferUtil; public class UTF8Type extends AbstractType<String> { @@ -31,7 +32,7 @@ public class UTF8Type extends AbstractType<String> public int compare(ByteBuffer o1, ByteBuffer o2) { - return BytesType.bytesCompare(o1, o2); + return ByteBufferUtil.compareUnsigned(o1, o2); } public ByteBuffer fromString(String source) @@ -47,6 +48,11 @@ public class UTF8Type extends AbstractType<String> return this == previous || previous == AsciiType.instance; } + public boolean isByteOrderComparable() + { + return true; + } + public CQL3Type asCQL3Type() { return CQL3Type.Native.TEXT; http://git-wip-us.apache.org/repos/asf/cassandra/blob/acf1b180/src/java/org/apache/cassandra/db/marshal/UUIDType.java ---------------------------------------------------------------------- diff --git a/src/java/org/apache/cassandra/db/marshal/UUIDType.java b/src/java/org/apache/cassandra/db/marshal/UUIDType.java index 4b0751e..a083736 100644 --- a/src/java/org/apache/cassandra/db/marshal/UUIDType.java +++ b/src/java/org/apache/cassandra/db/marshal/UUIDType.java @@ -222,4 +222,5 @@ public class UUIDType extends AbstractType<UUID> { return UUIDSerializer.instance; } + } http://git-wip-us.apache.org/repos/asf/cassandra/blob/acf1b180/src/java/org/apache/cassandra/hadoop/cql3/CqlRecordReader.java ---------------------------------------------------------------------- diff --git a/src/java/org/apache/cassandra/hadoop/cql3/CqlRecordReader.java b/src/java/org/apache/cassandra/hadoop/cql3/CqlRecordReader.java index 62fa1c9..09fb543 100644 --- a/src/java/org/apache/cassandra/hadoop/cql3/CqlRecordReader.java +++ b/src/java/org/apache/cassandra/hadoop/cql3/CqlRecordReader.java @@ -35,6 +35,7 @@ import org.apache.cassandra.db.marshal.BytesType; import org.apache.cassandra.dht.IPartitioner; import org.apache.cassandra.hadoop.ColumnFamilySplit; import org.apache.cassandra.hadoop.ConfigHelper; +import org.apache.cassandra.utils.ByteBufferUtil; import org.apache.cassandra.utils.Pair; import org.apache.hadoop.conf.Configuration; import org.apache.hadoop.mapreduce.InputSplit; @@ -252,7 +253,8 @@ public class CqlRecordReader extends RecordReader<Long, Row> { for (String column : partitionBoundColumns.keySet()) { - if (BytesType.bytesCompare(keyColumns.get(column), previousRowKey.get(column)) != 0) + // this is not correct - but we don't seem to have easy access to better type information here + if (ByteBufferUtil.compareUnsigned(keyColumns.get(column), previousRowKey.get(column)) != 0) { previousRowKey = keyColumns; totalRead++; http://git-wip-us.apache.org/repos/asf/cassandra/blob/acf1b180/src/java/org/apache/cassandra/utils/ByteBufferUtil.java ---------------------------------------------------------------------- diff --git a/src/java/org/apache/cassandra/utils/ByteBufferUtil.java b/src/java/org/apache/cassandra/utils/ByteBufferUtil.java index f20a46a..420a776 100644 --- a/src/java/org/apache/cassandra/utils/ByteBufferUtil.java +++ b/src/java/org/apache/cassandra/utils/ByteBufferUtil.java @@ -80,8 +80,6 @@ public class ByteBufferUtil public static int compareUnsigned(ByteBuffer o1, ByteBuffer o2) { - assert o1 != null; - assert o2 != null; return FastByteOperations.compareUnsigned(o1, o2); } http://git-wip-us.apache.org/repos/asf/cassandra/blob/acf1b180/src/java/org/apache/cassandra/utils/btree/BTree.java ---------------------------------------------------------------------- diff --git a/src/java/org/apache/cassandra/utils/btree/BTree.java b/src/java/org/apache/cassandra/utils/btree/BTree.java index 0e8f156..eb8295c 100644 --- a/src/java/org/apache/cassandra/utils/btree/BTree.java +++ b/src/java/org/apache/cassandra/utils/btree/BTree.java @@ -268,27 +268,13 @@ public class BTree // wrapping generic Comparator with support for Special +/- infinity sentinels static <V> int find(Comparator<V> comparator, Object key, Object[] a, final int fromIndex, final int toIndex) { - // attempt to terminate quickly by checking the first element, - // as many uses of this class will (probably) be updating identical sets - if (fromIndex >= toIndex) - return -(fromIndex + 1); - - int c = compare(comparator, key, a[fromIndex]); - if (c <= 0) - { - if (c == 0) - return fromIndex; - else - return -(fromIndex + 1); - } - - int low = fromIndex + 1; + int low = fromIndex; int high = toIndex - 1; while (low <= high) { int mid = (low + high) / 2; - int cmp = compare(comparator, key, a[mid]); + int cmp = comparator.compare((V) key, (V) a[mid]); if (cmp > 0) low = mid + 1; @@ -350,7 +336,7 @@ public class BTree } // Special class for making certain operations easier, so we can define a +/- Inf - private static interface Special extends Comparable<Object> { } + static interface Special extends Comparable<Object> { } static final Special POSITIVE_INFINITY = new Special() { public int compareTo(Object o) @@ -397,11 +383,6 @@ public class BTree return cmp.compare((V) a, (V) b); } - public static boolean isWellFormed(Object[] btree) - { - return isWellFormed(null, btree, true, NEGATIVE_INFINITY, POSITIVE_INFINITY); - } - public static boolean isWellFormed(Object[] btree, Comparator<? extends Object> cmp) { return isWellFormed(cmp, btree, true, NEGATIVE_INFINITY, POSITIVE_INFINITY); http://git-wip-us.apache.org/repos/asf/cassandra/blob/acf1b180/src/java/org/apache/cassandra/utils/btree/Builder.java ---------------------------------------------------------------------- diff --git a/src/java/org/apache/cassandra/utils/btree/Builder.java b/src/java/org/apache/cassandra/utils/btree/Builder.java index 36325fe..f6677d4 100644 --- a/src/java/org/apache/cassandra/utils/btree/Builder.java +++ b/src/java/org/apache/cassandra/utils/btree/Builder.java @@ -83,7 +83,7 @@ final class Builder // finish copying any remaining keys from the original btree while (true) { - NodeBuilder next = current.update(POSITIVE_INFINITY); + NodeBuilder next = current.finish(); if (next == null) break; current = next; http://git-wip-us.apache.org/repos/asf/cassandra/blob/acf1b180/src/java/org/apache/cassandra/utils/btree/NodeBuilder.java ---------------------------------------------------------------------- diff --git a/src/java/org/apache/cassandra/utils/btree/NodeBuilder.java b/src/java/org/apache/cassandra/utils/btree/NodeBuilder.java index 5a9b149..ba6cf21 100644 --- a/src/java/org/apache/cassandra/utils/btree/NodeBuilder.java +++ b/src/java/org/apache/cassandra/utils/btree/NodeBuilder.java @@ -104,6 +104,21 @@ final class NodeBuilder copyFromChildPosition = 0; } + NodeBuilder finish() + { + assert copyFrom != null; + int copyFromKeyEnd = getKeyEnd(copyFrom); + + if (buildKeyPosition + buildChildPosition > 0) + { + // only want to copy if we've already changed something, otherwise we'll return the original + copyKeys(copyFromKeyEnd); + if (!isLeaf(copyFrom)) + copyChildren(copyFromKeyEnd + 1); + } + return isRoot() ? null : ascend(); + } + /** * Inserts or replaces the provided key, copying all not-yet-visited keys prior to it into our buffer. * @@ -117,9 +132,33 @@ final class NodeBuilder assert copyFrom != null; int copyFromKeyEnd = getKeyEnd(copyFrom); - int i = find(comparator, key, copyFrom, copyFromKeyPosition, copyFromKeyEnd); - boolean found = i >= 0; // exact key match? + int i = copyFromKeyPosition; + boolean found; // exact key match? boolean owns = true; // true iff this node (or a child) should contain the key + if (i == copyFromKeyEnd) + { + found = false; + } + else + { + // this optimisation is for the common scenario of updating an existing row with the same columns/keys + // and simply avoids performing a binary search until we've checked the proceeding key; + // possibly we should disable this check if we determine that it fails more than a handful of times + // during any given builder use to get the best of both worlds + int c = comparator.compare(copyFrom[i], key); + if (c >= 0) + { + found = c == 0; + } + else + { + i = find(comparator, key, copyFrom, i + 1, copyFromKeyEnd); + found = i >= 0; + if (!found) + i = -i - 1; + } + } + if (found) { Object prev = copyFrom[i]; @@ -129,12 +168,8 @@ final class NodeBuilder return null; key = next; } - else - { - i = -i - 1; - if (i == copyFromKeyEnd && compare(comparator, upperBound, key) <= 0) - owns = false; - } + else if (i == copyFromKeyEnd && compare(comparator, upperBound, key) <= 0) + owns = false; if (isLeaf(copyFrom)) { @@ -203,9 +238,6 @@ final class NodeBuilder } } - if (key == POSITIVE_INFINITY && isRoot()) - return null; - return ascend(); } http://git-wip-us.apache.org/repos/asf/cassandra/blob/acf1b180/src/java/org/apache/cassandra/utils/btree/Path.java ---------------------------------------------------------------------- diff --git a/src/java/org/apache/cassandra/utils/btree/Path.java b/src/java/org/apache/cassandra/utils/btree/Path.java index 148c713..51207ba 100644 --- a/src/java/org/apache/cassandra/utils/btree/Path.java +++ b/src/java/org/apache/cassandra/utils/btree/Path.java @@ -20,6 +20,8 @@ package org.apache.cassandra.utils.btree; import java.util.Comparator; +import static org.apache.cassandra.utils.btree.BTree.NEGATIVE_INFINITY; +import static org.apache.cassandra.utils.btree.BTree.POSITIVE_INFINITY; import static org.apache.cassandra.utils.btree.BTree.getBranchKeyEnd; import static org.apache.cassandra.utils.btree.BTree.getKeyEnd; import static org.apache.cassandra.utils.btree.BTree.getLeafKeyEnd; @@ -50,7 +52,7 @@ class Path // the index within the node of our path at a given depth byte[] indexes; // current depth. nothing in path[i] for i > depth is valid. - byte depth = -1; + byte depth; Path() { } Path(int depth) @@ -69,6 +71,20 @@ class Path } } + void moveEnd(Object[] node, boolean forwards) + { + push(node, getKeyEnd(node)); + if (!forwards) + predecessor(); + } + + void moveStart(Object[] node, boolean forwards) + { + push(node, -1); + if (forwards) + successor(); + } + /** * Find the provided key in the tree rooted at node, and store the root to it in the path * @@ -87,6 +103,17 @@ class Path // search depth = -1; + if (target instanceof BTree.Special) + { + if (target == POSITIVE_INFINITY) + moveEnd(node, forwards); + else if (target == NEGATIVE_INFINITY) + moveStart(node, forwards); + else + throw new AssertionError(); + return; + } + while (true) { int keyEnd = getKeyEnd(node); @@ -107,18 +134,17 @@ class Path } return; } + i = -i - 1; // traverse into the appropriate child if (!isLeaf(node)) { - i = -i - 1; push(node, forwards ? i - 1 : i); node = (Object[]) node[keyEnd + i]; continue; } // bottom of the tree and still not found. pick the right index to satisfy Op - i = -i - 1; switch (mode) { case FLOOR:
