hbase-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From te...@apache.org
Subject svn commit: r1354294 - in /hbase/branches/0.92: CHANGES.txt src/main/java/org/apache/hadoop/hbase/KeyValue.java src/test/java/org/apache/hadoop/hbase/TestKeyValue.java
Date Tue, 26 Jun 2012 23:46:13 GMT
Author: tedyu
Date: Tue Jun 26 23:46:12 2012
New Revision: 1354294

URL: http://svn.apache.org/viewvc?rev=1354294&view=rev
Log:
HBASE-6200 KeyComparator.compareWithoutRow can be wrong when families have the same prefix
(Jieshan)


Modified:
    hbase/branches/0.92/CHANGES.txt
    hbase/branches/0.92/src/main/java/org/apache/hadoop/hbase/KeyValue.java
    hbase/branches/0.92/src/test/java/org/apache/hadoop/hbase/TestKeyValue.java

Modified: hbase/branches/0.92/CHANGES.txt
URL: http://svn.apache.org/viewvc/hbase/branches/0.92/CHANGES.txt?rev=1354294&r1=1354293&r2=1354294&view=diff
==============================================================================
--- hbase/branches/0.92/CHANGES.txt (original)
+++ hbase/branches/0.92/CHANGES.txt Tue Jun 26 23:46:12 2012
@@ -83,6 +83,7 @@ Release 0.92.2 - Unreleased
    HBASE-6160  META entries from daughters can be deleted before parent entries
                (Enis Soztutar)
    HBASE-6182  TestStoreFile fails with jdk1.7 (Jimmy Xiang)
+   HBASE-6200  KeyComparator.compareWithoutRow can be wrong when families have the same prefix
(Jieshan)
 
   IMPROVEMENTS
    HBASE-5592  Make it easier to get a table from shell (Ben West)

Modified: hbase/branches/0.92/src/main/java/org/apache/hadoop/hbase/KeyValue.java
URL: http://svn.apache.org/viewvc/hbase/branches/0.92/src/main/java/org/apache/hadoop/hbase/KeyValue.java?rev=1354294&r1=1354293&r2=1354294&view=diff
==============================================================================
--- hbase/branches/0.92/src/main/java/org/apache/hadoop/hbase/KeyValue.java (original)
+++ hbase/branches/0.92/src/main/java/org/apache/hadoop/hbase/KeyValue.java Tue Jun 26 23:46:12
2012
@@ -131,6 +131,15 @@ public class KeyValue implements Writabl
     return COMPARATOR.getRawComparator();
   }
 
+  /** Size of the row length field in bytes */
+  public static final int ROW_LENGTH_SIZE = Bytes.SIZEOF_SHORT;
+
+  /** Size of the family length field in bytes */
+  public static final int FAMILY_LENGTH_SIZE = Bytes.SIZEOF_BYTE;
+
+  /** Size of the timestamp field in bytes */
+  public static final int TIMESTAMP_SIZE = Bytes.SIZEOF_LONG;
+
   // Size of the timestamp and type byte on end of a key -- a long + a byte.
   public static final int TIMESTAMP_TYPE_SIZE =
     Bytes.SIZEOF_LONG /* timestamp */ +
@@ -1910,39 +1919,104 @@ public class KeyValue implements Writabl
         return compare;
       }
 
-      // Compare column family.  Start compare past row and family length.
-      int lcolumnoffset = Bytes.SIZEOF_SHORT + lrowlength + 1 + loffset;
-      int rcolumnoffset = Bytes.SIZEOF_SHORT + rrowlength + 1 + roffset;
-      int lcolumnlength = llength - TIMESTAMP_TYPE_SIZE -
-        (lcolumnoffset - loffset);
-      int rcolumnlength = rlength - TIMESTAMP_TYPE_SIZE -
-        (rcolumnoffset - roffset);
+      // Compare the rest of the two KVs. This function will not compare rows
+      // anyway, so we don't need to tell it that the common prefix includes the
+      // row.
+      return compareWithoutRow(left, loffset, llength, right, roffset, rlength,
+          rrowlength);
+    }
+
+    public int compare(byte[] left, byte[] right) {
+      return compare(left, 0, left.length, right, 0, right.length);
+    }
+
+    public int compareRows(byte [] left, int loffset, int llength,
+        byte [] right, int roffset, int rlength) {
+      return Bytes.compareTo(left, loffset, llength, right, roffset, rlength);
+    }
+
+    protected int compareColumns(
+        byte [] left, int loffset, int llength, final int lfamilylength,
+        byte [] right, int roffset, int rlength, final int rfamilylength) {
+      return KeyValue.compareColumns(left, loffset, llength, lfamilylength,
+        right, roffset, rlength, rfamilylength);
+    }
+
+    /**
+     * Compare columnFamily, qualifier, timestamp, and key type (everything
+     * except the row). Note that we are assuming that row portions of both KVs
+     * have already been parsed and found identical, and we don't validate that
+     * assumption here.
+     * @return comparison result.
+     */
+    private int compareWithoutRow(byte[] left, int loffset,
+        int llength, byte[] right, int roffset, int rlength, short rowlength) {
+      // Column family offset.
+      int commonLength = ROW_LENGTH_SIZE + FAMILY_LENGTH_SIZE + rowlength;
+      int lfamilyoffset = commonLength + loffset;
+      int rfamilyoffset = commonLength + roffset;
+
+      // Column family length.
+      int lfamilylength = left[lfamilyoffset - 1];
+      int rfamilylength = right[rfamilyoffset - 1];
+
+      // Qualifier length.
+      int lqualifierlength = llength - TIMESTAMP_TYPE_SIZE - commonLength
+          - lfamilylength;
+      int rqualifierlength = rlength - TIMESTAMP_TYPE_SIZE - commonLength
+          - rfamilylength;
 
-      // if row matches, and no column in the 'left' AND put type is 'minimum',
+      // If row matches, and no column in the 'left' AND put type is 'minimum',
       // then return that left is larger than right.
 
-      // This supports 'last key on a row' - the magic is if there is no column in the
-      // left operand, and the left operand has a type of '0' - magical value,
-      // then we say the left is bigger.  This will let us seek to the last key in
-      // a row.
+      // This supports 'last key on a row' - the magic is if there is no column
+      // in the left operand, and the left operand has a type of '0' - magical
+      // value, then we say the left is bigger.  This will let us seek to the
+      // last key in a row.
 
       byte ltype = left[loffset + (llength - 1)];
       byte rtype = right[roffset + (rlength - 1)];
 
-      if (lcolumnlength == 0 && ltype == Type.Minimum.getCode()) {
-        return 1; // left is bigger.
+      // If the column is not specified, the "minimum" key type appears the
+      // latest in the sorted order, regardless of the timestamp. This is used
+      // for specifying the last key/value in a given row, because there is no
+      // "lexicographically last column" (it would be infinitely long). The
+      // "maximum" key type does not need this behavior.
+      if (lfamilylength == 0 && lqualifierlength == 0
+          && ltype == Type.Minimum.getCode()) {
+        // left is "bigger", i.e. it appears later in the sorted order
+        return 1;
       }
-      if (rcolumnlength == 0 && rtype == Type.Minimum.getCode()) {
+      if (rfamilylength == 0 && rqualifierlength == 0
+          && rtype == Type.Minimum.getCode()) {
         return -1;
       }
-
-      // TODO the family and qualifier should be compared separately
-      compare = Bytes.compareTo(left, lcolumnoffset, lcolumnlength, right,
-          rcolumnoffset, rcolumnlength);
-      if (compare != 0) {
-        return compare;
+      // If left family size is not equal to right family size, we need not
+      // compare the qualifiers. 
+      if (lfamilylength != rfamilylength) {
+        // Compare column family.
+        return Bytes.compareTo(left, lfamilyoffset,
+            lfamilylength, right, rfamilyoffset, rfamilylength);
+      }
+      // Compare family & qualifier together.
+      // commonLength + TIMESTAMP_TYPE_SIZE
+      int commonLengthWithTSAndType = TIMESTAMP_TYPE_SIZE + commonLength;
+      // ColumnFamily + Qualifier length.
+      int lcolumnlength = llength - commonLengthWithTSAndType;
+      int rcolumnlength = rlength - commonLengthWithTSAndType;
+      final int comparison = Bytes.compareTo(left, lfamilyoffset,
+          lcolumnlength, right, rfamilyoffset, rcolumnlength);
+      if (comparison != 0) {
+        return comparison;
       }
 
+      return compareTimestampAndType(left, loffset, llength, right, roffset,
+          rlength, ltype, rtype);
+    }
+
+    private int compareTimestampAndType(byte[] left, int loffset, int llength,
+        byte[] right, int roffset, int rlength, byte ltype, byte rtype) {
+      int compare;
       if (!this.ignoreTimestamp) {
         // Get timestamps.
         long ltimestamp = Bytes.toLong(left,
@@ -1957,28 +2031,14 @@ public class KeyValue implements Writabl
 
       if (!this.ignoreType) {
         // Compare types. Let the delete types sort ahead of puts; i.e. types
-        // of higher numbers sort before those of lesser numbers
+        // of higher numbers sort before those of lesser numbers. Maximum (255)
+        // appears ahead of everything, and minimum (0) appears after
+        // everything.
         return (0xff & rtype) - (0xff & ltype);
       }
       return 0;
     }
 
-    public int compare(byte[] left, byte[] right) {
-      return compare(left, 0, left.length, right, 0, right.length);
-    }
-
-    public int compareRows(byte [] left, int loffset, int llength,
-        byte [] right, int roffset, int rlength) {
-      return Bytes.compareTo(left, loffset, llength, right, roffset, rlength);
-    }
-
-    protected int compareColumns(
-        byte [] left, int loffset, int llength, final int lfamilylength,
-        byte [] right, int roffset, int rlength, final int rfamilylength) {
-      return KeyValue.compareColumns(left, loffset, llength, lfamilylength,
-        right, roffset, rlength, rfamilylength);
-    }
-
     int compareTimestamps(final long ltimestamp, final long rtimestamp) {
       // The below older timestamps sorting ahead of newer timestamps looks
       // wrong but it is intentional. This way, newer timestamps are first

Modified: hbase/branches/0.92/src/test/java/org/apache/hadoop/hbase/TestKeyValue.java
URL: http://svn.apache.org/viewvc/hbase/branches/0.92/src/test/java/org/apache/hadoop/hbase/TestKeyValue.java?rev=1354294&r1=1354293&r2=1354294&view=diff
==============================================================================
--- hbase/branches/0.92/src/test/java/org/apache/hadoop/hbase/TestKeyValue.java (original)
+++ hbase/branches/0.92/src/test/java/org/apache/hadoop/hbase/TestKeyValue.java Tue Jun 26
23:46:12 2012
@@ -339,6 +339,34 @@ public class TestKeyValue extends TestCa
     assertTrue(cmp > 0);
   }
 
+  public void testCompareWithoutRow() {
+    final KVComparator c = KeyValue.COMPARATOR;
+    byte[] row = Bytes.toBytes("row");
+    byte[] fami0 = Bytes.toBytes("fami");
+    byte[] fami1 = Bytes.toBytes("fami1");
+    byte[] fami2 = Bytes.toBytes("fami2");
+    byte[] qual0 = Bytes.toBytes("");
+    byte[] qual1 = Bytes.toBytes("qf1");
+    byte[] qual2 = Bytes.toBytes("qf2");
+    long ts = 1;
+    // 'fami1:'
+    KeyValue kv1_0 = new KeyValue(row, fami1, qual0, ts, Type.Put);
+    // 'fami1:qual1'
+    KeyValue kv1_1 = new KeyValue(row, fami1, qual1, ts, Type.Put);
+    // 'fami2:qual1'
+    KeyValue kv2_1 = new KeyValue(row, fami2, qual1, ts, Type.Put);
+    // 'fami:qf1'
+    KeyValue kv0_1 = new KeyValue(row, fami0, qual1, ts, Type.Put);
+    // 'fami:qf2'
+    KeyValue kv0_2 = new KeyValue(row, fami0, qual2, ts, Type.Put);
+    // 'fami:qf1' < 'fami:qf2'
+    assertKVLess(c, kv0_1, kv0_2);
+    // 'fami1:qual1' < 'fami2:qual1'
+    assertKVLess(c, kv1_1, kv2_1);
+    // 'fami:qf1' < 'fami1:'
+    assertKVLess(c, kv0_1, kv1_0);
+  }
+
   public void testFirstLastOnRow() {
     final KVComparator c = KeyValue.COMPARATOR;
     long ts = 1;



Mime
View raw message