cassandra-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From slebre...@apache.org
Subject git commit: Optimize cellname comparison
Date Tue, 29 Apr 2014 12:33:55 GMT
Repository: cassandra
Updated Branches:
  refs/heads/cassandra-2.1 fad144ae5 -> acf1b1801


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/cassandra-2.1
Commit: acf1b1801352cdc6103325ff4498c2020dcc1c32
Parents: fad144a
Author: belliottsmith <github@sub.laerad.com>
Authored: Fri Apr 25 16:56:34 2014 +0100
Committer: Sylvain Lebresne <sylvain@datastax.com>
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:


Mime
View raw message