Return-Path: X-Original-To: apmail-hbase-commits-archive@www.apache.org Delivered-To: apmail-hbase-commits-archive@www.apache.org Received: from mail.apache.org (hermes.apache.org [140.211.11.3]) by minotaur.apache.org (Postfix) with SMTP id DF73410FB6 for ; Sat, 29 Mar 2014 17:19:33 +0000 (UTC) Received: (qmail 97669 invoked by uid 500); 29 Mar 2014 17:19:33 -0000 Delivered-To: apmail-hbase-commits-archive@hbase.apache.org Received: (qmail 97572 invoked by uid 500); 29 Mar 2014 17:19:32 -0000 Mailing-List: contact commits-help@hbase.apache.org; run by ezmlm Precedence: bulk List-Help: List-Unsubscribe: List-Post: List-Id: Reply-To: dev@hbase.apache.org Delivered-To: mailing list commits@hbase.apache.org Received: (qmail 97560 invoked by uid 99); 29 Mar 2014 17:19:32 -0000 Received: from nike.apache.org (HELO nike.apache.org) (192.87.106.230) by apache.org (qpsmtpd/0.29) with ESMTP; Sat, 29 Mar 2014 17:19:32 +0000 X-ASF-Spam-Status: No, hits=-2000.0 required=5.0 tests=ALL_TRUSTED X-Spam-Check-By: apache.org Received: from [140.211.11.4] (HELO eris.apache.org) (140.211.11.4) by apache.org (qpsmtpd/0.29) with ESMTP; Sat, 29 Mar 2014 17:19:22 +0000 Received: from eris.apache.org (localhost [127.0.0.1]) by eris.apache.org (Postfix) with ESMTP id DC98123889D5; Sat, 29 Mar 2014 17:18:58 +0000 (UTC) Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Subject: svn commit: r1583031 [1/2] - in /hbase/trunk: hbase-common/src/main/java/org/apache/hadoop/hbase/ hbase-common/src/main/java/org/apache/hadoop/hbase/io/encoding/ hbase-common/src/main/java/org/apache/hadoop/hbase/util/ hbase-common/src/test/java/org/ap... Date: Sat, 29 Mar 2014 17:18:57 -0000 To: commits@hbase.apache.org From: ramkrishna@apache.org X-Mailer: svnmailer-1.0.9 Message-Id: <20140329171858.DC98123889D5@eris.apache.org> X-Virus-Checked: Checked by ClamAV on apache.org Author: ramkrishna Date: Sat Mar 29 17:18:56 2014 New Revision: 1583031 URL: http://svn.apache.org/r1583031 Log: HBASE-10531-Revisit how the key byte[] is passed to HFileScanner.seekTo and reseekTo (Ram) Added: hbase/trunk/hbase-common/src/test/java/org/apache/hadoop/hbase/TestCellComparator.java hbase/trunk/hbase-server/src/test/java/org/apache/hadoop/hbase/io/encoding/TestSeekToBlockWithEncoders.java Modified: hbase/trunk/hbase-common/src/main/java/org/apache/hadoop/hbase/CellComparator.java hbase/trunk/hbase-common/src/main/java/org/apache/hadoop/hbase/KeyValue.java hbase/trunk/hbase-common/src/main/java/org/apache/hadoop/hbase/io/encoding/BufferedDataBlockEncoder.java hbase/trunk/hbase-common/src/main/java/org/apache/hadoop/hbase/io/encoding/DataBlockEncoder.java hbase/trunk/hbase-common/src/main/java/org/apache/hadoop/hbase/util/Bytes.java hbase/trunk/hbase-prefix-tree/src/main/java/org/apache/hadoop/hbase/codec/prefixtree/PrefixTreeSeeker.java hbase/trunk/hbase-prefix-tree/src/main/java/org/apache/hadoop/hbase/codec/prefixtree/decode/PrefixTreeArrayScanner.java hbase/trunk/hbase-prefix-tree/src/main/java/org/apache/hadoop/hbase/codec/prefixtree/decode/PrefixTreeCell.java hbase/trunk/hbase-server/src/main/java/org/apache/hadoop/hbase/io/HalfStoreFileReader.java hbase/trunk/hbase-server/src/main/java/org/apache/hadoop/hbase/io/hfile/HFileBlockIndex.java hbase/trunk/hbase-server/src/main/java/org/apache/hadoop/hbase/io/hfile/HFileReaderV2.java hbase/trunk/hbase-server/src/main/java/org/apache/hadoop/hbase/io/hfile/HFileReaderV3.java hbase/trunk/hbase-server/src/main/java/org/apache/hadoop/hbase/io/hfile/HFileScanner.java hbase/trunk/hbase-server/src/main/java/org/apache/hadoop/hbase/regionserver/HStore.java hbase/trunk/hbase-server/src/main/java/org/apache/hadoop/hbase/regionserver/StoreFileScanner.java hbase/trunk/hbase-server/src/main/java/org/apache/hadoop/hbase/util/BloomFilterFactory.java hbase/trunk/hbase-server/src/main/java/org/apache/hadoop/hbase/util/ByteBloomFilter.java hbase/trunk/hbase-server/src/main/java/org/apache/hadoop/hbase/util/CompoundBloomFilter.java hbase/trunk/hbase-server/src/test/java/org/apache/hadoop/hbase/io/TestHalfStoreFileReader.java hbase/trunk/hbase-server/src/test/java/org/apache/hadoop/hbase/io/encoding/TestDataBlockEncoders.java hbase/trunk/hbase-server/src/test/java/org/apache/hadoop/hbase/io/encoding/TestPrefixTreeEncoding.java hbase/trunk/hbase-server/src/test/java/org/apache/hadoop/hbase/io/hfile/TestHFile.java hbase/trunk/hbase-server/src/test/java/org/apache/hadoop/hbase/io/hfile/TestHFileBlockIndex.java hbase/trunk/hbase-server/src/test/java/org/apache/hadoop/hbase/io/hfile/TestHFileEncryption.java hbase/trunk/hbase-server/src/test/java/org/apache/hadoop/hbase/io/hfile/TestHFileInlineToRootChunkConversion.java hbase/trunk/hbase-server/src/test/java/org/apache/hadoop/hbase/io/hfile/TestHFileSeek.java hbase/trunk/hbase-server/src/test/java/org/apache/hadoop/hbase/io/hfile/TestReseekTo.java hbase/trunk/hbase-server/src/test/java/org/apache/hadoop/hbase/io/hfile/TestSeekTo.java Modified: hbase/trunk/hbase-common/src/main/java/org/apache/hadoop/hbase/CellComparator.java URL: http://svn.apache.org/viewvc/hbase/trunk/hbase-common/src/main/java/org/apache/hadoop/hbase/CellComparator.java?rev=1583031&r1=1583030&r2=1583031&view=diff ============================================================================== --- hbase/trunk/hbase-common/src/main/java/org/apache/hadoop/hbase/CellComparator.java (original) +++ hbase/trunk/hbase-common/src/main/java/org/apache/hadoop/hbase/CellComparator.java Sat Mar 29 17:18:56 2014 @@ -45,54 +45,85 @@ public class CellComparator implements C @Override public int compare(Cell a, Cell b) { - return compareStatic(a, b); + return compareStatic(a, b, false); } - - public static int compareStatic(Cell a, Cell b) { - //row - int c = Bytes.compareTo( - a.getRowArray(), a.getRowOffset(), a.getRowLength(), - b.getRowArray(), b.getRowOffset(), b.getRowLength()); + public static int compareStatic(Cell a, Cell b, boolean onlyKey) { + // row + int c = compareRows(a, b); if (c != 0) return c; - // 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 (a.getFamilyLength() == 0 && a.getTypeByte() == Type.Minimum.getCode()) { - // a is "bigger", i.e. it appears later in the sorted order - return 1; - } - if (b.getFamilyLength() == 0 && b.getTypeByte() == Type.Minimum.getCode()) { - return -1; + c = compareWithoutRow(a, b); + if(c != 0) return c; + + if (!onlyKey) { + // Negate following comparisons so later edits show up first + + // compare log replay tag value if there is any + // when either keyvalue tagged with log replay sequence number, we need to compare them: + // 1) when both keyvalues have the tag, then use the tag values for comparison + // 2) when one has and the other doesn't have, the one without the log + // replay tag wins because + // it means the edit isn't from recovery but new one coming from clients during recovery + // 3) when both doesn't have, then skip to the next mvcc comparison + long leftChangeSeqNum = getReplaySeqNum(a); + long RightChangeSeqNum = getReplaySeqNum(b); + if (leftChangeSeqNum != Long.MAX_VALUE || RightChangeSeqNum != Long.MAX_VALUE) { + return Longs.compare(RightChangeSeqNum, leftChangeSeqNum); + } + // mvccVersion: later sorts first + return Longs.compare(b.getMvccVersion(), a.getMvccVersion()); + } else { + return c; } + } - //family - c = Bytes.compareTo( - a.getFamilyArray(), a.getFamilyOffset(), a.getFamilyLength(), - b.getFamilyArray(), b.getFamilyOffset(), b.getFamilyLength()); - if (c != 0) return c; + /** + * Return replay log sequence number for the cell + * + * @param c + * @return Long.MAX_VALUE if there is no LOG_REPLAY_TAG + */ + private static long getReplaySeqNum(final Cell c) { + Tag tag = Tag.getTag(c.getTagsArray(), c.getTagsOffset(), c.getTagsLength(), + TagType.LOG_REPLAY_TAG_TYPE); - //qualifier - c = Bytes.compareTo( - a.getQualifierArray(), a.getQualifierOffset(), a.getQualifierLength(), - b.getQualifierArray(), b.getQualifierOffset(), b.getQualifierLength()); - if (c != 0) return c; + if (tag != null) { + return Bytes.toLong(tag.getBuffer(), tag.getTagOffset(), tag.getTagLength()); + } + return Long.MAX_VALUE; + } - //timestamp: later sorts first - c = Longs.compare(b.getTimestamp(), a.getTimestamp()); - if (c != 0) return c; + public static int findCommonPrefixInRowPart(Cell left, Cell right, int rowCommonPrefix) { + return findCommonPrefix(left.getRowArray(), right.getRowArray(), left.getRowLength() + - rowCommonPrefix, right.getRowLength() - rowCommonPrefix, left.getRowOffset() + + rowCommonPrefix, right.getRowOffset() + rowCommonPrefix); + } - //type - c = (0xff & b.getTypeByte()) - (0xff & a.getTypeByte()); - if (c != 0) return c; + private static int findCommonPrefix(byte[] left, byte[] right, int leftLength, int rightLength, + int leftOffset, int rightOffset) { + int length = Math.min(leftLength, rightLength); + int result = 0; - //mvccVersion: later sorts first - return Longs.compare(b.getMvccVersion(), a.getMvccVersion()); + while (result < length && left[leftOffset + result] == right[rightOffset + result]) { + result++; + } + return result; } + public static int findCommonPrefixInFamilyPart(Cell left, Cell right, int familyCommonPrefix) { + return findCommonPrefix(left.getFamilyArray(), right.getFamilyArray(), left.getFamilyLength() + - familyCommonPrefix, right.getFamilyLength() - familyCommonPrefix, left.getFamilyOffset() + + familyCommonPrefix, right.getFamilyOffset() + familyCommonPrefix); + } + + public static int findCommonPrefixInQualifierPart(Cell left, Cell right, + int qualifierCommonPrefix) { + return findCommonPrefix(left.getQualifierArray(), right.getQualifierArray(), + left.getQualifierLength() - qualifierCommonPrefix, right.getQualifierLength() + - qualifierCommonPrefix, left.getQualifierOffset() + qualifierCommonPrefix, + right.getQualifierOffset() + qualifierCommonPrefix); + } /**************** equals ****************************/ @@ -130,6 +161,88 @@ public class CellComparator implements C return a.getTypeByte() == b.getTypeByte(); } + public static int compareColumns(final Cell left, final Cell right) { + int lfoffset = left.getFamilyOffset(); + int rfoffset = right.getFamilyOffset(); + int lclength = left.getQualifierLength(); + int rclength = right.getQualifierLength(); + int lfamilylength = left.getFamilyLength(); + int rfamilylength = right.getFamilyLength(); + int diff = compare(left.getFamilyArray(), lfoffset, lfamilylength, right.getFamilyArray(), + rfoffset, rfamilylength); + if (diff != 0) { + return diff; + } else { + return compare(left.getQualifierArray(), left.getQualifierOffset(), lclength, + right.getQualifierArray(), right.getQualifierOffset(), rclength); + } + } + + public static int compareFamilies(Cell left, Cell right) { + return Bytes.compareTo(left.getFamilyArray(), left.getFamilyOffset(), left.getFamilyLength(), + right.getFamilyArray(), right.getFamilyOffset(), right.getFamilyLength()); + } + + public static int compareQualifiers(Cell left, Cell right) { + return Bytes.compareTo(left.getQualifierArray(), left.getQualifierOffset(), + left.getQualifierLength(), right.getQualifierArray(), right.getQualifierOffset(), + right.getQualifierLength()); + } + + public int compareFlatKey(Cell left, Cell right) { + int compare = compareRows(left, right); + if (compare != 0) { + return compare; + } + return compareWithoutRow(left, right); + } + + public static int compareRows(final Cell left, final Cell right) { + return Bytes.compareTo(left.getRowArray(), left.getRowOffset(), left.getRowLength(), + right.getRowArray(), right.getRowOffset(), right.getRowLength()); + } + + public static int compareRows(byte[] left, int loffset, int llength, byte[] right, int roffset, + int rlength) { + return Bytes.compareTo(left, loffset, llength, right, roffset, rlength); + } + + public static int compareWithoutRow(final Cell leftCell, final Cell rightCell) { + if (leftCell.getFamilyLength() + leftCell.getQualifierLength() == 0 + && leftCell.getTypeByte() == Type.Minimum.getCode()) { + // left is "bigger", i.e. it appears later in the sorted order + return 1; + } + if (rightCell.getFamilyLength() + rightCell.getQualifierLength() == 0 + && rightCell.getTypeByte() == Type.Minimum.getCode()) { + return -1; + } + boolean sameFamilySize = (leftCell.getFamilyLength() == rightCell.getFamilyLength()); + if (!sameFamilySize) { + // comparing column family is enough. + + return Bytes.compareTo(leftCell.getFamilyArray(), leftCell.getFamilyOffset(), + leftCell.getFamilyLength(), rightCell.getFamilyArray(), rightCell.getFamilyOffset(), + rightCell.getFamilyLength()); + } + int diff = compareColumns(leftCell, rightCell); + if (diff != 0) return diff; + + diff = compareTimestamps(leftCell, rightCell); + if (diff != 0) return diff; + + // Compare types. Let the delete types sort ahead of puts; i.e. types + // of higher numbers sort before those of lesser numbers. Maximum (255) + // appears ahead of everything, and minimum (0) appears after + // everything. + return (0xff & rightCell.getTypeByte()) - (0xff & leftCell.getTypeByte()); + } + + public static int compareTimestamps(final Cell left, final Cell right) { + long ltimestamp = left.getTimestamp(); + long rtimestamp = right.getTimestamp(); + return compareTimestamps(ltimestamp, rtimestamp); + } /********************* hashCode ************************/ @@ -172,32 +285,54 @@ public class CellComparator implements C } - /***************** special cases ****************************/ + /*********************common prefixes*************************/ + + private static int compare(byte[] left, int leftOffset, int leftLength, byte[] right, + int rightOffset, int rightLength) { + return Bytes.compareTo(left, leftOffset, leftLength, right, rightOffset, rightLength); + } + + public static int compareCommonRowPrefix(Cell left, Cell right, int rowCommonPrefix) { + return compare(left.getRowArray(), left.getRowOffset() + rowCommonPrefix, left.getRowLength() + - rowCommonPrefix, right.getRowArray(), right.getRowOffset() + rowCommonPrefix, + right.getRowLength() - rowCommonPrefix); + } + + public static int compareCommonFamilyPrefix(Cell left, Cell right, + int familyCommonPrefix) { + return compare(left.getFamilyArray(), left.getFamilyOffset() + familyCommonPrefix, + left.getFamilyLength() - familyCommonPrefix, right.getFamilyArray(), + right.getFamilyOffset() + familyCommonPrefix, + right.getFamilyLength() - familyCommonPrefix); + } + + public static int compareCommonQualifierPrefix(Cell left, Cell right, + int qualCommonPrefix) { + return compare(left.getQualifierArray(), left.getQualifierOffset() + qualCommonPrefix, + left.getQualifierLength() - qualCommonPrefix, right.getQualifierArray(), + right.getQualifierOffset() + qualCommonPrefix, right.getQualifierLength() + - qualCommonPrefix); + } + /***************** special cases ****************************/ /** * special case for KeyValue.equals */ - private static int compareStaticIgnoreMvccVersion(Cell a, Cell b) { - //row - int c = Bytes.compareTo( - a.getRowArray(), a.getRowOffset(), a.getRowLength(), - b.getRowArray(), b.getRowOffset(), b.getRowLength()); - if (c != 0) return c; + public static boolean equalsIgnoreMvccVersion(Cell a, Cell b){ + return 0 == compareStaticIgnoreMvccVersion(a, b); + } - //family - c = Bytes.compareTo( - a.getFamilyArray(), a.getFamilyOffset(), a.getFamilyLength(), - b.getFamilyArray(), b.getFamilyOffset(), b.getFamilyLength()); + private static int compareStaticIgnoreMvccVersion(Cell a, Cell b) { + // row + int c = compareRows(a, b); if (c != 0) return c; - //qualifier - c = Bytes.compareTo( - a.getQualifierArray(), a.getQualifierOffset(), a.getQualifierLength(), - b.getQualifierArray(), b.getQualifierOffset(), b.getQualifierLength()); + // family + c = compareColumns(a, b); if (c != 0) return c; - //timestamp: later sorts first - c = Longs.compare(b.getTimestamp(), a.getTimestamp()); + // timestamp: later sorts first + c = compareTimestamps(a, b); if (c != 0) return c; //type @@ -205,11 +340,17 @@ public class CellComparator implements C return c; } - /** - * special case for KeyValue.equals - */ - public static boolean equalsIgnoreMvccVersion(Cell a, Cell b){ - return 0 == compareStaticIgnoreMvccVersion(a, b); + private static 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 + // found when we iterate over a memstore and newer versions are the + // first we trip over when reading from a store file. + if (ltimestamp < rtimestamp) { + return 1; + } else if (ltimestamp > rtimestamp) { + return -1; + } + return 0; } } Modified: hbase/trunk/hbase-common/src/main/java/org/apache/hadoop/hbase/KeyValue.java URL: http://svn.apache.org/viewvc/hbase/trunk/hbase-common/src/main/java/org/apache/hadoop/hbase/KeyValue.java?rev=1583031&r1=1583030&r2=1583031&view=diff ============================================================================== --- hbase/trunk/hbase-common/src/main/java/org/apache/hadoop/hbase/KeyValue.java (original) +++ hbase/trunk/hbase-common/src/main/java/org/apache/hadoop/hbase/KeyValue.java Sat Mar 29 17:18:56 2014 @@ -43,7 +43,7 @@ import org.apache.hadoop.hbase.util.Clas import org.apache.hadoop.io.IOUtils; import org.apache.hadoop.io.RawComparator; -import com.google.common.primitives.Longs; +import com.google.common.annotations.VisibleForTesting; /** * An HBase Key/Value. This is the fundamental HBase Type. @@ -1839,6 +1839,20 @@ public class KeyValue implements Cell, H * table. */ @Override + public int compare(final Cell left, final Cell right) { + int c = compareRowKey(left, right); + if (c != 0) { + return c; + } + return CellComparator.compareWithoutRow(left, right); + } + + @Override + public int compareOnlyKeyPortion(Cell left, Cell right) { + return compare(left, right); + } + + @Override public int compareRows(byte [] left, int loffset, int llength, byte [] right, int roffset, int rlength) { int leftDelimiter = getDelimiter(left, loffset, llength, @@ -1952,9 +1966,7 @@ public class KeyValue implements Cell, H * @return 0 if equal, <0 if left smaller, >0 if right smaller */ protected int compareRowKey(final Cell left, final Cell right) { - return Bytes.compareTo( - left.getRowArray(), left.getRowOffset(), left.getRowLength(), - right.getRowArray(), right.getRowOffset(), right.getRowLength()); + return CellComparator.compareRows(left, right); } /** @@ -1990,109 +2002,22 @@ public class KeyValue implements Cell, H return compareFlatKey(left, 0, left.length, right, 0, right.length); } + public int compareOnlyKeyPortion(Cell left, Cell right) { + return CellComparator.compareStatic(left, right, true); + } + /** * Compares the Key of a cell -- with fields being more significant in this order: * rowkey, colfam/qual, timestamp, type, mvcc */ + @Override public int compare(final Cell left, final Cell right) { - // compare row - int compare = compareRowKey(left, right); - if (compare != 0) { - return compare; - } - - // compare vs minimum - byte ltype = left.getTypeByte(); - byte rtype = right.getTypeByte(); - // 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. - int lcfqLen = left.getFamilyLength() + left.getQualifierLength() ; - int rcfqLen = right.getFamilyLength() + right.getQualifierLength() ; - if (lcfqLen == 0 && ltype == Type.Minimum.getCode()) { - // left is "bigger", i.e. it appears later in the sorted order - return 1; - } - if (rcfqLen == 0 && rtype == Type.Minimum.getCode()) { - return -1; - } - - - // compare col family / col fam + qual - // If left family size is not equal to right family size, we need not - // compare the qualifiers. - compare = Bytes.compareTo( - left.getFamilyArray(), left.getFamilyOffset(), left.getFamilyLength(), - right.getFamilyArray(), right.getFamilyOffset(), right.getFamilyLength()); - if (compare != 0) { - return compare; - } - - // Compare qualifier - compare = Bytes.compareTo( - left.getQualifierArray(), left.getQualifierOffset(), left.getQualifierLength(), - right.getQualifierArray(), right.getQualifierOffset(), right.getQualifierLength()); - if (compare!= 0) { - return compare; - } - - // compare timestamp - long ltimestamp = left.getTimestamp(); - long rtimestamp = right.getTimestamp(); - compare = compareTimestamps(ltimestamp, rtimestamp); - if (compare != 0) { - return compare; - } - - // Compare types. Let the delete types sort ahead of puts; i.e. types - // of higher numbers sort before those of lesser numbers. Maximum (255) - // appears ahead of everything, and minimum (0) appears after - // everything. - compare = (0xff & rtype) - (0xff & ltype); - if (compare != 0) { - return compare; - } - - // Negate following comparisons so later edits show up first - - // compare log replay tag value if there is any - // when either keyvalue tagged with log replay sequence number, we need to compare them: - // 1) when both keyvalues have the tag, then use the tag values for comparison - // 2) when one has and the other doesn't have, the one without the log replay tag wins because - // it means the edit isn't from recovery but new one coming from clients during recovery - // 3) when both doesn't have, then skip to the next mvcc comparison - long leftChangeSeqNum = getReplaySeqNum(left); - long RightChangeSeqNum = getReplaySeqNum(right); - if (leftChangeSeqNum != Long.MAX_VALUE || RightChangeSeqNum != Long.MAX_VALUE) { - return Longs.compare(RightChangeSeqNum, leftChangeSeqNum); - } - - // compare Mvcc Version - return Longs.compare(right.getMvccVersion(), left.getMvccVersion()); - } - - /** - * Return replay log sequence number for the cell - * @param c - * @return Long.MAX_VALUE if there is no LOG_REPLAY_TAG - */ - private long getReplaySeqNum(final Cell c) { - Tag tag = Tag.getTag(c.getTagsArray(), c.getTagsOffset(), c.getTagsLength(), - TagType.LOG_REPLAY_TAG_TYPE); - - if(tag != null) { - return Bytes.toLong(tag.getBuffer(), tag.getTagOffset(), tag.getTagLength()); - } - return Long.MAX_VALUE; + int compare = CellComparator.compareStatic(left, right, false); + return compare; } - public int compareTimestamps(final KeyValue left, final KeyValue right) { - // Compare timestamps - long ltimestamp = left.getTimestamp(left.getKeyLength()); - long rtimestamp = right.getTimestamp(right.getKeyLength()); - return compareTimestamps(ltimestamp, rtimestamp); + public int compareTimestamps(final Cell left, final Cell right) { + return CellComparator.compareTimestamps(left, right); } /** @@ -2100,7 +2025,7 @@ public class KeyValue implements Cell, H * @param right * @return Result comparing rows. */ - public int compareRows(final KeyValue left, final KeyValue right) { + public int compareRows(final Cell left, final Cell right) { return compareRows(left.getRowArray(),left.getRowOffset(), left.getRowLength(), right.getRowArray(), right.getRowOffset(), right.getRowLength()); } @@ -2120,17 +2045,9 @@ public class KeyValue implements Cell, H return Bytes.compareTo(left, loffset, llength, right, roffset, rlength); } - int compareColumns(final KeyValue left, final short lrowlength, - final KeyValue right, final short rrowlength) { - int lfoffset = left.getFamilyOffset(lrowlength); - int rfoffset = right.getFamilyOffset(rrowlength); - int lclength = left.getTotalColumnLength(lrowlength,lfoffset); - int rclength = right.getTotalColumnLength(rrowlength, rfoffset); - int lfamilylength = left.getFamilyLength(lfoffset); - int rfamilylength = right.getFamilyLength(rfoffset); - return compareColumns(left.getBuffer(), lfoffset, - lclength, lfamilylength, - right.getBuffer(), rfoffset, rclength, rfamilylength); + int compareColumns(final Cell left, final short lrowlength, final Cell right, + final short rrowlength) { + return CellComparator.compareColumns(left, right); } protected int compareColumns( @@ -2297,20 +2214,31 @@ public class KeyValue implements Cell, H return (0xff & rtype) - (0xff & ltype); } + protected int compareFamilies(final byte[] left, final int loffset, final int lfamilylength, + final byte[] right, final int roffset, final int rfamilylength) { + int diff = Bytes.compareTo(left, loffset, lfamilylength, right, roffset, rfamilylength); + return diff; + } + + protected int compareColumns(final byte[] left, final int loffset, final int lquallength, + final byte[] right, final int roffset, final int rquallength) { + int diff = Bytes.compareTo(left, loffset, lquallength, right, roffset, rquallength); + return diff; + } /** * Compares the row and column of two keyvalues for equality * @param left * @param right * @return True if same row and column. */ - public boolean matchingRowColumn(final KeyValue left, - final KeyValue right) { + public boolean matchingRowColumn(final Cell left, + final Cell right) { short lrowlength = left.getRowLength(); short rrowlength = right.getRowLength(); // TsOffset = end of column data. just comparing Row+CF length of each - if ((left.getTimestampOffset() - left.getOffset()) != - (right.getTimestampOffset() - right.getOffset())) { + if ((left.getRowLength() + left.getFamilyLength() + left.getQualifierLength()) != (right + .getRowLength() + right.getFamilyLength() + right.getQualifierLength())) { return false; } @@ -2318,15 +2246,21 @@ public class KeyValue implements Cell, H return false; } - int lfoffset = left.getFamilyOffset(lrowlength); - int rfoffset = right.getFamilyOffset(rrowlength); - int lclength = left.getTotalColumnLength(lrowlength,lfoffset); - int rclength = right.getTotalColumnLength(rrowlength, rfoffset); - int lfamilylength = left.getFamilyLength(lfoffset); - int rfamilylength = right.getFamilyLength(rfoffset); - int ccRes = compareColumns(left.getBuffer(), lfoffset, lclength, lfamilylength, - right.getBuffer(), rfoffset, rclength, rfamilylength); - return ccRes == 0; + int lfoffset = left.getFamilyOffset(); + int rfoffset = right.getFamilyOffset(); + int lclength = left.getQualifierLength(); + int rclength = right.getQualifierLength(); + int lfamilylength = left.getFamilyLength(); + int rfamilylength = right.getFamilyLength(); + int diff = compareFamilies(left.getFamilyArray(), lfoffset, lfamilylength, + right.getFamilyArray(), rfoffset, rfamilylength); + if (diff != 0) { + return false; + } else { + diff = compareColumns(left.getQualifierArray(), left.getQualifierOffset(), lclength, + right.getQualifierArray(), right.getQualifierOffset(), rclength); + return diff == 0; + } } /** @@ -2335,7 +2269,7 @@ public class KeyValue implements Cell, H * @param right * @return True if rows match. */ - public boolean matchingRows(final KeyValue left, final KeyValue right) { + public boolean matchingRows(final Cell left, final Cell right) { short lrowlength = left.getRowLength(); short rrowlength = right.getRowLength(); return matchingRows(left, lrowlength, right, rrowlength); @@ -2348,8 +2282,8 @@ public class KeyValue implements Cell, H * @param rrowlength * @return True if rows match. */ - private boolean matchingRows(final KeyValue left, final short lrowlength, - final KeyValue right, final short rrowlength) { + private boolean matchingRows(final Cell left, final short lrowlength, + final Cell right, final short rrowlength) { return lrowlength == rrowlength && matchingRows(left.getRowArray(), left.getRowOffset(), lrowlength, right.getRowArray(), right.getRowOffset(), rrowlength); @@ -2929,6 +2863,37 @@ public class KeyValue implements Cell, H return Bytes.BYTES_RAWCOMPARATOR.compare(left, loffset, llength, right, roffset, rlength); } + @Override + public int compare(Cell left, Cell right) { + return compareOnlyKeyPortion(left, right); + } + + @VisibleForTesting + public int compareOnlyKeyPortion(Cell left, Cell right) { + int c = Bytes.BYTES_RAWCOMPARATOR.compare(left.getRowArray(), left.getRowOffset(), + left.getRowLength(), right.getRowArray(), right.getRowOffset(), right.getRowLength()); + if (c != 0) { + return c; + } + c = Bytes.BYTES_RAWCOMPARATOR.compare(left.getFamilyArray(), left.getFamilyOffset(), + left.getFamilyLength(), right.getFamilyArray(), right.getFamilyOffset(), + right.getFamilyLength()); + if (c != 0) { + return c; + } + c = Bytes.BYTES_RAWCOMPARATOR.compare(left.getQualifierArray(), left.getQualifierOffset(), + left.getQualifierLength(), right.getQualifierArray(), right.getQualifierOffset(), + right.getQualifierLength()); + if (c != 0) { + return c; + } + c = compareTimestamps(left.getTimestamp(), right.getTimestamp()); + if (c != 0) { + return c; + } + return (0xff & left.getTypeByte()) - (0xff & right.getTypeByte()); + } + public byte[] calcIndexKey(byte[] lastKeyOfPreviousBlock, byte[] firstKeyInBlock) { return firstKeyInBlock; } @@ -2952,4 +2917,171 @@ public class KeyValue implements Cell, H sum += Bytes.SIZEOF_LONG;// memstoreTS return ClassSize.align(sum); } + + /** + * A simple form of KeyValue that creates a keyvalue with only the key part of the byte[] + * Mainly used in places where we need to compare two cells. Avoids copying of bytes + * In places like block index keys, we need to compare the key byte[] with a cell. + * Hence create a Keyvalue(aka Cell) that would help in comparing as two cells + */ + public static class KeyOnlyKeyValue extends KeyValue { + private int length = 0; + private int offset = 0; + private byte[] b; + + public KeyOnlyKeyValue() { + + } + + public KeyOnlyKeyValue(byte[] b, int offset, int length) { + this.b = b; + this.length = length; + this.offset = offset; + } + + @Override + public int getKeyOffset() { + return this.offset; + } + + /** + * A setter that helps to avoid object creation every time and whenever + * there is a need to create new KeyOnlyKeyValue. + * @param key + * @param offset + * @param length + */ + public void setKey(byte[] key, int offset, int length) { + this.b = key; + this.offset = offset; + this.length = length; + } + + @Override + public byte[] getKey() { + int keylength = getKeyLength(); + byte[] key = new byte[keylength]; + System.arraycopy(this.b, getKeyOffset(), key, 0, keylength); + return key; + } + + @Override + public byte[] getRowArray() { + return b; + } + + @Override + public int getRowOffset() { + return getKeyOffset() + Bytes.SIZEOF_SHORT; + } + + @Override + public byte[] getFamilyArray() { + return b; + } + + @Override + public byte getFamilyLength() { + return this.b[getFamilyOffset() - 1]; + } + + @Override + public int getFamilyOffset() { + return this.offset + Bytes.SIZEOF_SHORT + getRowLength() + Bytes.SIZEOF_BYTE; + } + + @Override + public byte[] getQualifierArray() { + return b; + } + + @Override + public int getQualifierLength() { + return getQualifierLength(getRowLength(), getFamilyLength()); + } + + @Override + public int getQualifierOffset() { + return getFamilyOffset() + getFamilyLength(); + } + + @Override + public int getKeyLength() { + return length; + } + + @Override + public short getRowLength() { + return Bytes.toShort(this.b, getKeyOffset()); + } + + @Override + public byte getTypeByte() { + return this.b[this.offset + getKeyLength() - 1]; + } + + private int getQualifierLength(int rlength, int flength) { + return getKeyLength() - (int) getKeyDataStructureSize(rlength, flength, 0); + } + + @Override + public long getTimestamp() { + int tsOffset = getTimestampOffset(); + return Bytes.toLong(this.b, tsOffset); + } + + @Override + public int getTimestampOffset() { + return getKeyOffset() + getKeyLength() - TIMESTAMP_TYPE_SIZE; + } + + @Override + public byte[] getTagsArray() { + return HConstants.EMPTY_BYTE_ARRAY; + } + + @Override + public int getTagsOffset() { + return (short) 0; + } + + @Override + public byte[] getValueArray() { + throw new IllegalArgumentException("KeyOnlyKeyValue does not work with values."); + } + + @Override + public int getValueOffset() { + throw new IllegalArgumentException("KeyOnlyKeyValue does not work with values."); + } + + @Override + public int getValueLength() { + throw new IllegalArgumentException("KeyOnlyKeyValue does not work with values."); + } + + @Override + public short getTagsLength() { + return (short) 0; + } + + @Override + public String toString() { + if (this.b == null || this.b.length == 0) { + return "empty"; + } + return keyToString(this.b, this.offset + ROW_OFFSET, getKeyLength()) + "/vlen=" + + getValueLength() + "/mvcc=" + 0; + } + + @Override + public int hashCode() { + return super.hashCode(); + } + + @Override + public boolean equals(Object other) { + return super.equals(other); + } + } } Modified: hbase/trunk/hbase-common/src/main/java/org/apache/hadoop/hbase/io/encoding/BufferedDataBlockEncoder.java URL: http://svn.apache.org/viewvc/hbase/trunk/hbase-common/src/main/java/org/apache/hadoop/hbase/io/encoding/BufferedDataBlockEncoder.java?rev=1583031&r1=1583030&r2=1583031&view=diff ============================================================================== --- hbase/trunk/hbase-common/src/main/java/org/apache/hadoop/hbase/io/encoding/BufferedDataBlockEncoder.java (original) +++ hbase/trunk/hbase-common/src/main/java/org/apache/hadoop/hbase/io/encoding/BufferedDataBlockEncoder.java Sat Mar 29 17:18:56 2014 @@ -22,10 +22,13 @@ import java.io.IOException; import java.nio.ByteBuffer; import org.apache.hadoop.classification.InterfaceAudience; +import org.apache.hadoop.hbase.Cell; +import org.apache.hadoop.hbase.CellComparator; import org.apache.hadoop.hbase.HConstants; import org.apache.hadoop.hbase.KeyValue; import org.apache.hadoop.hbase.KeyValue.KVComparator; import org.apache.hadoop.hbase.KeyValue.SamePrefixComparator; +import org.apache.hadoop.hbase.KeyValue.Type; import org.apache.hadoop.hbase.io.TagCompressionContext; import org.apache.hadoop.hbase.io.hfile.BlockType; import org.apache.hadoop.hbase.io.hfile.HFileContext; @@ -194,6 +197,12 @@ abstract class BufferedDataBlockEncoder } @Override + public int compareKey(KVComparator comparator, Cell key) { + return comparator.compareOnlyKeyPortion(key, + new KeyValue.KeyOnlyKeyValue(current.keyBuffer, 0, current.keyLength)); + } + + @Override public void setCurrentBuffer(ByteBuffer buffer) { if (this.tagCompressionContext != null) { this.tagCompressionContext.clear(); @@ -304,36 +313,89 @@ abstract class BufferedDataBlockEncoder } @Override - public int seekToKeyInBlock(byte[] key, int offset, int length, - boolean seekBefore) { - int commonPrefix = 0; + public int seekToKeyInBlock(byte[] key, int offset, int length, boolean seekBefore) { + return seekToKeyInBlock(new KeyValue.KeyOnlyKeyValue(key, offset, length), seekBefore); + } + + @Override + public int seekToKeyInBlock(Cell seekCell, boolean seekBefore) { + int rowCommonPrefix = 0; + int familyCommonPrefix = 0; + int qualCommonPrefix = 0; previous.invalidate(); + KeyValue.KeyOnlyKeyValue currentCell = new KeyValue.KeyOnlyKeyValue(); do { int comp; if (samePrefixComparator != null) { - commonPrefix = Math.min(commonPrefix, current.lastCommonPrefix); - - // extend commonPrefix - commonPrefix += ByteBufferUtils.findCommonPrefix( - key, offset + commonPrefix, length - commonPrefix, - current.keyBuffer, commonPrefix, - current.keyLength - commonPrefix); - - comp = samePrefixComparator.compareIgnoringPrefix(commonPrefix, key, - offset, length, current.keyBuffer, 0, current.keyLength); + currentCell.setKey(current.keyBuffer, 0, current.keyLength); + if (current.lastCommonPrefix != 0) { + // The KV format has row key length also in the byte array. The + // common prefix + // includes it. So we need to subtract to find out the common prefix + // in the + // row part alone + rowCommonPrefix = Math.min(rowCommonPrefix, current.lastCommonPrefix - 2); + } + if (current.lastCommonPrefix <= 2) { + rowCommonPrefix = 0; + } + rowCommonPrefix += CellComparator.findCommonPrefixInRowPart(seekCell, currentCell, + rowCommonPrefix); + comp = CellComparator.compareCommonRowPrefix(seekCell, currentCell, rowCommonPrefix); + if (comp == 0) { + comp = compareTypeBytes(seekCell, currentCell); + if (comp == 0) { + // Subtract the fixed row key length and the family key fixed length + familyCommonPrefix = Math.max( + 0, + Math.min(familyCommonPrefix, + current.lastCommonPrefix - (3 + currentCell.getRowLength()))); + familyCommonPrefix += CellComparator.findCommonPrefixInFamilyPart(seekCell, + currentCell, familyCommonPrefix); + comp = CellComparator.compareCommonFamilyPrefix(seekCell, currentCell, + familyCommonPrefix); + if (comp == 0) { + // subtract the rowkey fixed length and the family key fixed + // length + qualCommonPrefix = Math.max( + 0, + Math.min( + qualCommonPrefix, + current.lastCommonPrefix + - (3 + currentCell.getRowLength() + currentCell.getFamilyLength()))); + qualCommonPrefix += CellComparator.findCommonPrefixInQualifierPart(seekCell, + currentCell, qualCommonPrefix); + comp = CellComparator.compareCommonQualifierPrefix(seekCell, currentCell, + qualCommonPrefix); + if (comp == 0) { + comp = CellComparator.compareTimestamps(seekCell, currentCell); + if (comp == 0) { + // Compare types. Let the delete types sort ahead of puts; + // i.e. types + // of higher numbers sort before those of lesser numbers. + // Maximum + // (255) + // appears ahead of everything, and minimum (0) appears + // after + // everything. + comp = (0xff & currentCell.getTypeByte()) - (0xff & seekCell.getTypeByte()); + } + } + } + } + } } else { - comp = comparator.compareFlatKey(key, offset, length, - current.keyBuffer, 0, current.keyLength); + Cell r = new KeyValue.KeyOnlyKeyValue(current.keyBuffer, 0, current.keyLength); + comp = comparator.compareOnlyKeyPortion(seekCell, r); } - if (comp == 0) { // exact match if (seekBefore) { if (!previous.isValid()) { // The caller (seekBefore) has to ensure that we are not at the // first key in the block. - throw new IllegalStateException("Cannot seekBefore if " + - "positioned at the first key in the block: key=" + - Bytes.toStringBinary(key, offset, length)); + throw new IllegalStateException("Cannot seekBefore if " + + "positioned at the first key in the block: key=" + + Bytes.toStringBinary(seekCell.getRowArray())); } moveToPrevious(); return 1; @@ -363,6 +425,20 @@ abstract class BufferedDataBlockEncoder return 1; } + private int compareTypeBytes(Cell key, Cell right) { + if (key.getFamilyLength() + key.getQualifierLength() == 0 + && key.getTypeByte() == Type.Minimum.getCode()) { + // left is "bigger", i.e. it appears later in the sorted order + return 1; + } + if (right.getFamilyLength() + right.getQualifierLength() == 0 + && right.getTypeByte() == Type.Minimum.getCode()) { + return -1; + } + return 0; + } + + private void moveToPrevious() { if (!previous.isValid()) { throw new IllegalStateException( Modified: hbase/trunk/hbase-common/src/main/java/org/apache/hadoop/hbase/io/encoding/DataBlockEncoder.java URL: http://svn.apache.org/viewvc/hbase/trunk/hbase-common/src/main/java/org/apache/hadoop/hbase/io/encoding/DataBlockEncoder.java?rev=1583031&r1=1583030&r2=1583031&view=diff ============================================================================== --- hbase/trunk/hbase-common/src/main/java/org/apache/hadoop/hbase/io/encoding/DataBlockEncoder.java (original) +++ hbase/trunk/hbase-common/src/main/java/org/apache/hadoop/hbase/io/encoding/DataBlockEncoder.java Sat Mar 29 17:18:56 2014 @@ -21,6 +21,7 @@ import java.io.IOException; import java.nio.ByteBuffer; import org.apache.hadoop.classification.InterfaceAudience; +import org.apache.hadoop.hbase.Cell; import org.apache.hadoop.hbase.KeyValue; import org.apache.hadoop.hbase.KeyValue.KVComparator; import org.apache.hadoop.hbase.io.hfile.HFileContext; @@ -174,9 +175,26 @@ public interface DataBlockEncoder { * of an exact match. Does not matter in case of an inexact match. * @return 0 on exact match, 1 on inexact match. */ + @Deprecated int seekToKeyInBlock( byte[] key, int offset, int length, boolean seekBefore ); + /** + * Moves the seeker position within the current block to: + *
    + *
  • the last key that that is less than or equal to the given key if + * seekBefore is false
    • + *
  • the last key that is strictly less than the given key if + * seekBefore is true. The caller is responsible for loading the + * previous block if the requested key turns out to be the first key of the + * current block.
    • + *
+ * @param key - Cell to which the seek should happen + * @param seekBefore find the key strictly less than the given key in case + * of an exact match. Does not matter in case of an inexact match. + * @return 0 on exact match, 1 on inexact match. + */ + int seekToKeyInBlock(Cell key, boolean seekBefore); /** * Compare the given key against the current key @@ -187,5 +205,7 @@ public interface DataBlockEncoder { * @return -1 is the passed key is smaller than the current key, 0 if equal and 1 if greater */ public int compareKey(KVComparator comparator, byte[] key, int offset, int length); + + public int compareKey(KVComparator comparator, Cell key); } } Modified: hbase/trunk/hbase-common/src/main/java/org/apache/hadoop/hbase/util/Bytes.java URL: http://svn.apache.org/viewvc/hbase/trunk/hbase-common/src/main/java/org/apache/hadoop/hbase/util/Bytes.java?rev=1583031&r1=1583030&r2=1583031&view=diff ============================================================================== --- hbase/trunk/hbase-common/src/main/java/org/apache/hadoop/hbase/util/Bytes.java (original) +++ hbase/trunk/hbase-common/src/main/java/org/apache/hadoop/hbase/util/Bytes.java Sat Mar 29 17:18:56 2014 @@ -43,6 +43,8 @@ import org.apache.commons.logging.Log; import org.apache.commons.logging.LogFactory; import org.apache.hadoop.classification.InterfaceAudience; import org.apache.hadoop.classification.InterfaceStability; +import org.apache.hadoop.hbase.Cell; +import org.apache.hadoop.hbase.KeyValue; import org.apache.hadoop.hbase.io.ImmutableBytesWritable; import org.apache.hadoop.io.RawComparator; import org.apache.hadoop.io.WritableComparator; @@ -1635,6 +1637,43 @@ public class Bytes { } /** + * Binary search for keys in indexes. + * + * @param arr array of byte arrays to search for + * @param key the key you want to find + * @param comparator a comparator to compare. + * @return zero-based index of the key, if the key is present in the array. + * Otherwise, a value -(i + 1) such that the key is between arr[i - + * 1] and arr[i] non-inclusively, where i is in [0, i], if we define + * arr[-1] = -Inf and arr[N] = Inf for an N-element array. The above + * means that this function can return 2N + 1 different values + * ranging from -(N + 1) to N - 1. + * @return the index of the block + */ + public static int binarySearch(byte[][] arr, Cell key, RawComparator comparator) { + int low = 0; + int high = arr.length - 1; + KeyValue.KeyOnlyKeyValue r = new KeyValue.KeyOnlyKeyValue(); + while (low <= high) { + int mid = (low+high) >>> 1; + // we have to compare in this order, because the comparator order + // has special logic when the 'left side' is a special key. + r.setKey(arr[mid], 0, arr[mid].length); + int cmp = comparator.compare(key, r); + // key lives above the midpoint + if (cmp > 0) + low = mid + 1; + // key lives below the midpoint + else if (cmp < 0) + high = mid - 1; + // BAM. how often does this really happen? + else + return mid; + } + return - (low+1); + } + + /** * Bytewise binary increment/deincrement of long contained in byte array * on given amount. * Added: hbase/trunk/hbase-common/src/test/java/org/apache/hadoop/hbase/TestCellComparator.java URL: http://svn.apache.org/viewvc/hbase/trunk/hbase-common/src/test/java/org/apache/hadoop/hbase/TestCellComparator.java?rev=1583031&view=auto ============================================================================== --- hbase/trunk/hbase-common/src/test/java/org/apache/hadoop/hbase/TestCellComparator.java (added) +++ hbase/trunk/hbase-common/src/test/java/org/apache/hadoop/hbase/TestCellComparator.java Sat Mar 29 17:18:56 2014 @@ -0,0 +1,76 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package org.apache.hadoop.hbase; + +import static org.junit.Assert.assertTrue; + +import org.apache.hadoop.hbase.KeyValue.Type; +import org.apache.hadoop.hbase.util.Bytes; +import org.junit.Test; +import org.junit.experimental.categories.Category; +@Category(SmallTests.class) +public class TestCellComparator { + + byte[] row1 = Bytes.toBytes("row1"); + byte[] row2 = Bytes.toBytes("row2"); + byte[] row_1_0 = Bytes.toBytes("row10"); + + byte[] fam1 = Bytes.toBytes("fam1"); + byte[] fam2 = Bytes.toBytes("fam2"); + byte[] fam_1_2 = Bytes.toBytes("fam12"); + + byte[] qual1 = Bytes.toBytes("qual1"); + byte[] qual2 = Bytes.toBytes("qual2"); + + byte[] val = Bytes.toBytes("val"); + + @Test + public void testCompareCells() { + KeyValue kv1 = new KeyValue(row1, fam1, qual1, val); + KeyValue kv2 = new KeyValue(row2, fam1, qual1, val); + assertTrue((CellComparator.compareStatic(kv1, kv2, false)) < 0); + + kv1 = new KeyValue(row1, fam2, qual1, val); + kv2 = new KeyValue(row1, fam1, qual1, val); + assertTrue((CellComparator.compareFamilies(kv1, kv2) > 0)); + + kv1 = new KeyValue(row1, fam1, qual1, 1l, val); + kv2 = new KeyValue(row1, fam1, qual1, 2l, val); + assertTrue((CellComparator.compareStatic(kv1, kv2, false) > 0)); + + kv1 = new KeyValue(row1, fam1, qual1, 1l, Type.Put); + kv2 = new KeyValue(row1, fam1, qual1, 1l, Type.Maximum); + assertTrue((CellComparator.compareStatic(kv1, kv2, false) > 0)); + + kv1 = new KeyValue(row1, fam1, qual1, 1l, Type.Put); + kv2 = new KeyValue(row1, fam_1_2, qual1, 1l, Type.Maximum); + assertTrue((CellComparator.compareCommonFamilyPrefix(kv1, kv2, 4) < 0)); + + kv1 = new KeyValue(row1, fam1, qual1, 1l, Type.Put); + kv2 = new KeyValue(row_1_0, fam_1_2, qual1, 1l, Type.Maximum); + assertTrue((CellComparator.compareCommonRowPrefix(kv1, kv2, 4) < 0)); + + kv1 = new KeyValue(row1, fam1, qual2, 1l, Type.Put); + kv2 = new KeyValue(row1, fam1, qual1, 1l, Type.Maximum); + assertTrue((CellComparator.compareCommonQualifierPrefix(kv1, kv2, 4) > 0)); + + kv1 = new KeyValue(row1, fam1, qual1, 1l, Type.Put); + kv2 = new KeyValue(row1, fam1, qual1, 1l, Type.Put); + assertTrue((CellComparator.equals(kv1, kv2))); + } +} Modified: hbase/trunk/hbase-prefix-tree/src/main/java/org/apache/hadoop/hbase/codec/prefixtree/PrefixTreeSeeker.java URL: http://svn.apache.org/viewvc/hbase/trunk/hbase-prefix-tree/src/main/java/org/apache/hadoop/hbase/codec/prefixtree/PrefixTreeSeeker.java?rev=1583031&r1=1583030&r2=1583031&view=diff ============================================================================== --- hbase/trunk/hbase-prefix-tree/src/main/java/org/apache/hadoop/hbase/codec/prefixtree/PrefixTreeSeeker.java (original) +++ hbase/trunk/hbase-prefix-tree/src/main/java/org/apache/hadoop/hbase/codec/prefixtree/PrefixTreeSeeker.java Sat Mar 29 17:18:56 2014 @@ -24,8 +24,8 @@ import org.apache.hadoop.classification. import org.apache.hadoop.hbase.Cell; import org.apache.hadoop.hbase.CellUtil; import org.apache.hadoop.hbase.KeyValue; -import org.apache.hadoop.hbase.KeyValueUtil; import org.apache.hadoop.hbase.KeyValue.KVComparator; +import org.apache.hadoop.hbase.KeyValueUtil; import org.apache.hadoop.hbase.codec.prefixtree.decode.DecoderFactory; import org.apache.hadoop.hbase.codec.prefixtree.decode.PrefixTreeArraySearcher; import org.apache.hadoop.hbase.codec.prefixtree.scanner.CellScannerPosition; @@ -152,15 +152,13 @@ public class PrefixTreeSeeker implements boolean forceBeforeOnExactMatch) { if (USE_POSITION_BEFORE) { return seekToOrBeforeUsingPositionAtOrBefore(keyOnlyBytes, offset, length, - forceBeforeOnExactMatch); - }else{ + forceBeforeOnExactMatch); + } else { return seekToOrBeforeUsingPositionAtOrAfter(keyOnlyBytes, offset, length, - forceBeforeOnExactMatch); + forceBeforeOnExactMatch); } } - - /* * Support both of these options since the underlying PrefixTree supports both. Possibly * expand the EncodedSeeker to utilize them both. @@ -169,11 +167,22 @@ public class PrefixTreeSeeker implements protected int seekToOrBeforeUsingPositionAtOrBefore(byte[] keyOnlyBytes, int offset, int length, boolean seekBefore){ // this does a deep copy of the key byte[] because the CellSearcher interface wants a Cell - KeyValue kv = KeyValue.createKeyValueFromKey(keyOnlyBytes, offset, length); + KeyValue kv = new KeyValue.KeyOnlyKeyValue(keyOnlyBytes, offset, length); + + return seekToOrBeforeUsingPositionAtOrBefore(kv, seekBefore); + } + + /* + * Support both of these options since the underlying PrefixTree supports + * both. Possibly expand the EncodedSeeker to utilize them both. + */ + protected int seekToOrBeforeUsingPositionAtOrBefore(Cell kv, boolean seekBefore) { + // this does a deep copy of the key byte[] because the CellSearcher + // interface wants a Cell CellScannerPosition position = ptSearcher.seekForwardToOrBefore(kv); - if(CellScannerPosition.AT == position){ + if (CellScannerPosition.AT == position) { if (seekBefore) { ptSearcher.previous(); return 1; @@ -184,16 +193,19 @@ public class PrefixTreeSeeker implements return 1; } - protected int seekToOrBeforeUsingPositionAtOrAfter(byte[] keyOnlyBytes, int offset, int length, - boolean seekBefore){ - // this does a deep copy of the key byte[] because the CellSearcher interface wants a Cell - KeyValue kv = KeyValue.createKeyValueFromKey(keyOnlyBytes, offset, length); + boolean seekBefore) { + // this does a deep copy of the key byte[] because the CellSearcher + // interface wants a Cell + KeyValue kv = new KeyValue.KeyOnlyKeyValue(keyOnlyBytes, offset, length); + return seekToOrBeforeUsingPositionAtOrAfter(kv, seekBefore); + } - //should probably switch this to use the seekForwardToOrBefore method + protected int seekToOrBeforeUsingPositionAtOrAfter(Cell kv, boolean seekBefore) { + // should probably switch this to use the seekForwardToOrBefore method CellScannerPosition position = ptSearcher.seekForwardToOrAfter(kv); - if(CellScannerPosition.AT == position){ + if (CellScannerPosition.AT == position) { if (seekBefore) { ptSearcher.previous(); return 1; @@ -202,21 +214,21 @@ public class PrefixTreeSeeker implements } - if(CellScannerPosition.AFTER == position){ - if(!ptSearcher.isBeforeFirst()){ + if (CellScannerPosition.AFTER == position) { + if (!ptSearcher.isBeforeFirst()) { ptSearcher.previous(); } return 1; } - if(position == CellScannerPosition.AFTER_LAST){ + if (position == CellScannerPosition.AFTER_LAST) { if (seekBefore) { ptSearcher.previous(); } return 1; } - throw new RuntimeException("unexpected CellScannerPosition:"+position); + throw new RuntimeException("unexpected CellScannerPosition:" + position); } @Override @@ -225,4 +237,20 @@ public class PrefixTreeSeeker implements ByteBuffer bb = getKeyDeepCopy(); return comparator.compareFlatKey(key, offset, length, bb.array(), bb.arrayOffset(), bb.limit()); } + + @Override + public int seekToKeyInBlock(Cell key, boolean forceBeforeOnExactMatch) { + if (USE_POSITION_BEFORE) { + return seekToOrBeforeUsingPositionAtOrBefore(key, forceBeforeOnExactMatch); + }else{ + return seekToOrBeforeUsingPositionAtOrAfter(key, forceBeforeOnExactMatch); + } + } + + @Override + public int compareKey(KVComparator comparator, Cell key) { + ByteBuffer bb = getKeyDeepCopy(); + return comparator.compare(key, + new KeyValue.KeyOnlyKeyValue(bb.array(), bb.arrayOffset(), bb.limit())); + } } Modified: hbase/trunk/hbase-prefix-tree/src/main/java/org/apache/hadoop/hbase/codec/prefixtree/decode/PrefixTreeArrayScanner.java URL: http://svn.apache.org/viewvc/hbase/trunk/hbase-prefix-tree/src/main/java/org/apache/hadoop/hbase/codec/prefixtree/decode/PrefixTreeArrayScanner.java?rev=1583031&r1=1583030&r2=1583031&view=diff ============================================================================== --- hbase/trunk/hbase-prefix-tree/src/main/java/org/apache/hadoop/hbase/codec/prefixtree/decode/PrefixTreeArrayScanner.java (original) +++ hbase/trunk/hbase-prefix-tree/src/main/java/org/apache/hadoop/hbase/codec/prefixtree/decode/PrefixTreeArrayScanner.java Sat Mar 29 17:18:56 2014 @@ -28,7 +28,6 @@ import org.apache.hadoop.hbase.codec.pre import org.apache.hadoop.hbase.codec.prefixtree.decode.timestamp.MvccVersionDecoder; import org.apache.hadoop.hbase.codec.prefixtree.decode.timestamp.TimestampDecoder; import org.apache.hadoop.hbase.codec.prefixtree.encode.other.ColumnNodeType; -import org.apache.hadoop.hbase.util.Bytes; /** * Extends PtCell and manipulates its protected fields. Could alternatively contain a PtCell and @@ -420,7 +419,7 @@ public class PrefixTreeArrayScanner exte protected int populateNonRowFieldsAndCompareTo(int cellNum, Cell key) { populateNonRowFields(cellNum); - return CellComparator.compareStatic(this, key); + return CellComparator.compareStatic(this, key, false); } protected void populateFirstNonRowFields() { Modified: hbase/trunk/hbase-prefix-tree/src/main/java/org/apache/hadoop/hbase/codec/prefixtree/decode/PrefixTreeCell.java URL: http://svn.apache.org/viewvc/hbase/trunk/hbase-prefix-tree/src/main/java/org/apache/hadoop/hbase/codec/prefixtree/decode/PrefixTreeCell.java?rev=1583031&r1=1583030&r2=1583031&view=diff ============================================================================== --- hbase/trunk/hbase-prefix-tree/src/main/java/org/apache/hadoop/hbase/codec/prefixtree/decode/PrefixTreeCell.java (original) +++ hbase/trunk/hbase-prefix-tree/src/main/java/org/apache/hadoop/hbase/codec/prefixtree/decode/PrefixTreeCell.java Sat Mar 29 17:18:56 2014 @@ -106,7 +106,7 @@ public class PrefixTreeCell implements C @Override public int compareTo(Cell other) { - return CellComparator.compareStatic(this, other); + return CellComparator.compareStatic(this, other, false); } @Override Modified: hbase/trunk/hbase-server/src/main/java/org/apache/hadoop/hbase/io/HalfStoreFileReader.java URL: http://svn.apache.org/viewvc/hbase/trunk/hbase-server/src/main/java/org/apache/hadoop/hbase/io/HalfStoreFileReader.java?rev=1583031&r1=1583030&r2=1583031&view=diff ============================================================================== --- hbase/trunk/hbase-server/src/main/java/org/apache/hadoop/hbase/io/HalfStoreFileReader.java (original) +++ hbase/trunk/hbase-server/src/main/java/org/apache/hadoop/hbase/io/HalfStoreFileReader.java Sat Mar 29 17:18:56 2014 @@ -27,6 +27,7 @@ import org.apache.hadoop.classification. import org.apache.hadoop.conf.Configuration; import org.apache.hadoop.fs.FileSystem; import org.apache.hadoop.fs.Path; +import org.apache.hadoop.hbase.Cell; import org.apache.hadoop.hbase.HConstants; import org.apache.hadoop.hbase.KeyValue; import org.apache.hadoop.hbase.client.Scan; @@ -55,9 +56,11 @@ public class HalfStoreFileReader extends // This is the key we split around. Its the first possible entry on a row: // i.e. empty column and a timestamp of LATEST_TIMESTAMP. protected final byte [] splitkey; - + + protected final Cell splitCell; + private byte[] firstKey = null; - + private boolean firstKeySeeked = false; /** @@ -79,6 +82,7 @@ public class HalfStoreFileReader extends // have an actual midkey themselves. No midkey is how we indicate file is // not splittable. this.splitkey = r.getSplitKey(); + this.splitCell = new KeyValue.KeyOnlyKeyValue(this.splitkey, 0, this.splitkey.length); // Is it top or bottom half? this.top = Reference.isTopFileRegion(r.getFileRegion()); } @@ -104,6 +108,7 @@ public class HalfStoreFileReader extends // have an actual midkey themselves. No midkey is how we indicate file is // not splittable. this.splitkey = r.getSplitKey(); + this.splitCell = new KeyValue.KeyOnlyKeyValue(this.splitkey, 0, this.splitkey.length); // Is it top or bottom half? this.top = Reference.isTopFileRegion(r.getFileRegion()); } @@ -168,33 +173,21 @@ public class HalfStoreFileReader extends return true; } + @Override public boolean seekBefore(byte[] key) throws IOException { return seekBefore(key, 0, key.length); } + @Override public boolean seekBefore(byte [] key, int offset, int length) throws IOException { - if (top) { - byte[] fk = getFirstKey(); - // This will be null when the file is empty in which we can not seekBefore to any key - if (fk == null) return false; - if (getComparator().compareFlatKey(key, offset, length, fk, 0, - fk.length) <= 0) { - return false; - } - } else { - // The equals sign isn't strictly necessary just here to be consistent with seekTo - if (getComparator().compareFlatKey(key, offset, length, splitkey, 0, - splitkey.length) >= 0) { - return this.delegate.seekBefore(splitkey, 0, splitkey.length); - } - } - return this.delegate.seekBefore(key, offset, length); + return seekBefore(new KeyValue.KeyOnlyKeyValue(key, offset, length)); } + @Override public boolean seekTo() throws IOException { if (top) { - int r = this.delegate.seekTo(splitkey); + int r = this.delegate.seekTo(new KeyValue.KeyOnlyKeyValue(splitkey, 0, splitkey.length)); if (r == HConstants.INDEX_KEY_MAGIC) { return true; } @@ -219,55 +212,76 @@ public class HalfStoreFileReader extends splitkey, 0, splitkey.length) < 0; } + @Override public int seekTo(byte[] key) throws IOException { return seekTo(key, 0, key.length); } + @Override public int seekTo(byte[] key, int offset, int length) throws IOException { + return seekTo(new KeyValue.KeyOnlyKeyValue(key, offset, length)); + } + + @Override + public int reseekTo(byte[] key) throws IOException { + return reseekTo(key, 0, key.length); + } + + @Override + public int reseekTo(byte[] key, int offset, int length) + throws IOException { + //This function is identical to the corresponding seekTo function except + //that we call reseekTo (and not seekTo) on the delegate. + return reseekTo(new KeyValue.KeyOnlyKeyValue(key, offset, length)); + } + + public org.apache.hadoop.hbase.io.hfile.HFile.Reader getReader() { + return this.delegate.getReader(); + } + + public boolean isSeeked() { + return this.delegate.isSeeked(); + } + + @Override + public int seekTo(Cell key) throws IOException { if (top) { - if (getComparator().compareFlatKey(key, offset, length, splitkey, 0, - splitkey.length) < 0) { + if (getComparator().compareOnlyKeyPortion(key, splitCell) < 0) { return -1; } } else { - if (getComparator().compareFlatKey(key, offset, length, splitkey, 0, - splitkey.length) >= 0) { + if (getComparator().compareOnlyKeyPortion(key, splitCell) >= 0) { // we would place the scanner in the second half. // it might be an error to return false here ever... - boolean res = delegate.seekBefore(splitkey, 0, splitkey.length); + boolean res = delegate.seekBefore(splitCell); if (!res) { - throw new IOException("Seeking for a key in bottom of file, but key exists in top of file, failed on seekBefore(midkey)"); + throw new IOException( + "Seeking for a key in bottom of file, but key exists in top of file, " + + "failed on seekBefore(midkey)"); } return 1; } } - return delegate.seekTo(key, offset, length); - } - - @Override - public int reseekTo(byte[] key) throws IOException { - return reseekTo(key, 0, key.length); + return delegate.seekTo(key); } @Override - public int reseekTo(byte[] key, int offset, int length) - throws IOException { - //This function is identical to the corresponding seekTo function except - //that we call reseekTo (and not seekTo) on the delegate. + public int reseekTo(Cell key) throws IOException { + // This function is identical to the corresponding seekTo function + // except + // that we call reseekTo (and not seekTo) on the delegate. if (top) { - if (getComparator().compareFlatKey(key, offset, length, splitkey, 0, - splitkey.length) < 0) { + if (getComparator().compareOnlyKeyPortion(key, splitCell) < 0) { return -1; } } else { - if (getComparator().compareFlatKey(key, offset, length, splitkey, 0, - splitkey.length) >= 0) { + if (getComparator().compareOnlyKeyPortion(key, splitCell) >= 0) { // we would place the scanner in the second half. // it might be an error to return false here ever... - boolean res = delegate.seekBefore(splitkey, 0, splitkey.length); + boolean res = delegate.seekBefore(splitCell); if (!res) { - throw new IOException("Seeking for a key in bottom of file, but" + - " key exists in top of file, failed on seekBefore(midkey)"); + throw new IOException("Seeking for a key in bottom of file, but" + + " key exists in top of file, failed on seekBefore(midkey)"); } return 1; } @@ -276,15 +290,28 @@ public class HalfStoreFileReader extends // skip the 'reseek' and just return 1. return 1; } - return delegate.reseekTo(key, offset, length); + return delegate.reseekTo(key); } - public org.apache.hadoop.hbase.io.hfile.HFile.Reader getReader() { - return this.delegate.getReader(); - } - - public boolean isSeeked() { - return this.delegate.isSeeked(); + @Override + public boolean seekBefore(Cell key) throws IOException { + if (top) { + Cell fk = new KeyValue.KeyOnlyKeyValue(getFirstKey(), 0, getFirstKey().length); + // This will be null when the file is empty in which we can not + // seekBefore to any key + if (fk == null) + return false; + if (getComparator().compareOnlyKeyPortion(key, fk) <= 0) { + return false; + } + } else { + // The equals sign isn't strictly necessary just here to be consistent + // with seekTo + if (getComparator().compareOnlyKeyPortion(key, splitCell) >= 0) { + return this.delegate.seekBefore(splitCell); + } + } + return this.delegate.seekBefore(key); } }; } @@ -316,7 +343,7 @@ public class HalfStoreFileReader extends // Returns null to indicate file is not splitable. return null; } - + @Override public byte[] getFirstKey() { if (!firstKeySeeked) { Modified: hbase/trunk/hbase-server/src/main/java/org/apache/hadoop/hbase/io/hfile/HFileBlockIndex.java URL: http://svn.apache.org/viewvc/hbase/trunk/hbase-server/src/main/java/org/apache/hadoop/hbase/io/hfile/HFileBlockIndex.java?rev=1583031&r1=1583030&r2=1583031&view=diff ============================================================================== --- hbase/trunk/hbase-server/src/main/java/org/apache/hadoop/hbase/io/hfile/HFileBlockIndex.java (original) +++ hbase/trunk/hbase-server/src/main/java/org/apache/hadoop/hbase/io/hfile/HFileBlockIndex.java Sat Mar 29 17:18:56 2014 @@ -36,9 +36,11 @@ import org.apache.commons.logging.LogFac import org.apache.hadoop.classification.InterfaceAudience; import org.apache.hadoop.conf.Configuration; import org.apache.hadoop.fs.FSDataOutputStream; +import org.apache.hadoop.hbase.Cell; import org.apache.hadoop.hbase.HConstants; import org.apache.hadoop.hbase.KeyValue; import org.apache.hadoop.hbase.KeyValue.KVComparator; +import org.apache.hadoop.hbase.KeyValueUtil; import org.apache.hadoop.hbase.io.HeapSize; import org.apache.hadoop.hbase.io.encoding.DataBlockEncoding; import org.apache.hadoop.hbase.io.hfile.HFile.CachingBlockReader; @@ -165,8 +167,6 @@ public class HFileBlockIndex { * be called when the HFile version is larger than 1. * * @param key the key we are looking for - * @param keyOffset the offset of the key in its byte array - * @param keyLength the length of the key * @param currentBlock the current block, to avoid re-reading the same block * @param cacheBlocks * @param pread @@ -177,12 +177,12 @@ public class HFileBlockIndex { * @return reader a basic way to load blocks * @throws IOException */ - public HFileBlock seekToDataBlock(final byte[] key, int keyOffset, - int keyLength, HFileBlock currentBlock, boolean cacheBlocks, + public HFileBlock seekToDataBlock(final Cell key, HFileBlock currentBlock, boolean cacheBlocks, boolean pread, boolean isCompaction, DataBlockEncoding expectedDataBlockEncoding) throws IOException { - BlockWithScanInfo blockWithScanInfo = loadDataBlockWithScanInfo(key, keyOffset, keyLength, - currentBlock, cacheBlocks, pread, isCompaction, expectedDataBlockEncoding); + BlockWithScanInfo blockWithScanInfo = loadDataBlockWithScanInfo(key, currentBlock, + cacheBlocks, + pread, isCompaction, expectedDataBlockEncoding); if (blockWithScanInfo == null) { return null; } else { @@ -191,30 +191,29 @@ public class HFileBlockIndex { } /** - * Return the BlockWithScanInfo which contains the DataBlock with other scan info - * such as nextIndexedKey. - * This function will only be called when the HFile version is larger than 1. - * - * @param key the key we are looking for - * @param keyOffset the offset of the key in its byte array - * @param keyLength the length of the key - * @param currentBlock the current block, to avoid re-reading the same - * block + * Return the BlockWithScanInfo which contains the DataBlock with other scan + * info such as nextIndexedKey. This function will only be called when the + * HFile version is larger than 1. + * + * @param key + * the key we are looking for + * @param currentBlock + * the current block, to avoid re-reading the same block * @param cacheBlocks * @param pread * @param isCompaction * @param expectedDataBlockEncoding the data block encoding the caller is * expecting the data block to be in, or null to not perform this * check and return the block irrespective of the encoding. - * @return the BlockWithScanInfo which contains the DataBlock with other scan info - * such as nextIndexedKey. + * @return the BlockWithScanInfo which contains the DataBlock with other + * scan info such as nextIndexedKey. * @throws IOException */ - public BlockWithScanInfo loadDataBlockWithScanInfo(final byte[] key, int keyOffset, - int keyLength, HFileBlock currentBlock, boolean cacheBlocks, + public BlockWithScanInfo loadDataBlockWithScanInfo(Cell key, HFileBlock currentBlock, + boolean cacheBlocks, boolean pread, boolean isCompaction, DataBlockEncoding expectedDataBlockEncoding) throws IOException { - int rootLevelIndex = rootBlockContainingKey(key, keyOffset, keyLength); + int rootLevelIndex = rootBlockContainingKey(key); if (rootLevelIndex < 0 || rootLevelIndex >= blockOffsets.length) { return null; } @@ -283,10 +282,13 @@ public class HFileBlockIndex { // Locate the entry corresponding to the given key in the non-root // (leaf or intermediate-level) index block. ByteBuffer buffer = block.getBufferWithoutHeader(); - index = locateNonRootIndexEntry(buffer, key, keyOffset, keyLength, comparator); + index = locateNonRootIndexEntry(buffer, key, comparator); if (index == -1) { + // This has to be changed + // For now change this to key value + KeyValue kv = KeyValueUtil.ensureKeyValue(key); throw new IOException("The key " - + Bytes.toStringBinary(key, keyOffset, keyLength) + + Bytes.toStringBinary(kv.getKey(), kv.getKeyOffset(), kv.getKeyLength()) + " is before the" + " first key of the non-root index block " + block); } @@ -395,10 +397,35 @@ public class HFileBlockIndex { * number of blocks - 1) or -1 if this file does not contain the * request. */ - public int rootBlockContainingKey(final byte[] key, int offset, - int length) { - int pos = Bytes.binarySearch(blockKeys, key, offset, length, - comparator); + public int rootBlockContainingKey(final byte[] key, int offset, int length) { + int pos = Bytes.binarySearch(blockKeys, key, offset, length, comparator); + // pos is between -(blockKeys.length + 1) to blockKeys.length - 1, see + // binarySearch's javadoc. + + if (pos >= 0) { + // This means this is an exact match with an element of blockKeys. + assert pos < blockKeys.length; + return pos; + } + + // Otherwise, pos = -(i + 1), where blockKeys[i - 1] < key < blockKeys[i], + // and i is in [0, blockKeys.length]. We are returning j = i - 1 such that + // blockKeys[j] <= key < blockKeys[j + 1]. In particular, j = -1 if + // key < blockKeys[0], meaning the file does not contain the given key. + + int i = -pos - 1; + assert 0 <= i && i <= blockKeys.length; + return i - 1; + } + + /** + * Finds the root-level index block containing the given key. + * + * @param key + * Key to find + */ + public int rootBlockContainingKey(final Cell key) { + int pos = Bytes.binarySearch(blockKeys, key, comparator); // pos is between -(blockKeys.length + 1) to blockKeys.length - 1, see // binarySearch's javadoc. @@ -471,20 +498,19 @@ public class HFileBlockIndex { * Performs a binary search over a non-root level index block. Utilizes the * secondary index, which records the offsets of (offset, onDiskSize, * firstKey) tuples of all entries. - * - * @param key the key we are searching for offsets to individual entries in + * + * @param key + * the key we are searching for offsets to individual entries in * the blockIndex buffer - * @param keyOffset the offset of the key in its byte array - * @param keyLength the length of the key - * @param nonRootIndex the non-root index block buffer, starting with the - * secondary index. The position is ignored. + * @param nonRootIndex + * the non-root index block buffer, starting with the secondary + * index. The position is ignored. * @return the index i in [0, numEntries - 1] such that keys[i] <= key < * keys[i + 1], if keys is the array of all keys being searched, or * -1 otherwise * @throws IOException */ - static int binarySearchNonRootIndex(byte[] key, int keyOffset, - int keyLength, ByteBuffer nonRootIndex, + static int binarySearchNonRootIndex(Cell key, ByteBuffer nonRootIndex, KVComparator comparator) { int numEntries = nonRootIndex.getInt(0); @@ -499,7 +525,7 @@ public class HFileBlockIndex { // If we imagine that keys[-1] = -Infinity and // keys[numEntries] = Infinity, then we are maintaining an invariant that // keys[low - 1] < key < keys[high + 1] while narrowing down the range. - + KeyValue.KeyOnlyKeyValue nonRootIndexKV = new KeyValue.KeyOnlyKeyValue(); while (low <= high) { mid = (low + high) >>> 1; @@ -520,9 +546,9 @@ public class HFileBlockIndex { // we have to compare in this order, because the comparator order // has special logic when the 'left side' is a special key. - int cmp = comparator.compareFlatKey(key, keyOffset, keyLength, - nonRootIndex.array(), nonRootIndex.arrayOffset() + midKeyOffset, - midLength); + nonRootIndexKV.setKey(nonRootIndex.array(), + nonRootIndex.arrayOffset() + midKeyOffset, midLength); + int cmp = comparator.compareOnlyKeyPortion(key, nonRootIndexKV); // key lives above the midpoint if (cmp > 0) @@ -562,19 +588,18 @@ public class HFileBlockIndex { * of success, positions the provided buffer at the entry of interest, where * the file offset and the on-disk-size can be read. * - * @param nonRootBlock a non-root block without header. Initial position - * does not matter. - * @param key the byte array containing the key - * @param keyOffset the offset of the key in its byte array - * @param keyLength the length of the key - * @return the index position where the given key was found, - * otherwise return -1 in the case the given key is before the first key. + * @param nonRootBlock + * a non-root block without header. Initial position does not + * matter. + * @param key + * the byte array containing the key + * @return the index position where the given key was found, otherwise + * return -1 in the case the given key is before the first key. * */ - static int locateNonRootIndexEntry(ByteBuffer nonRootBlock, byte[] key, - int keyOffset, int keyLength, KVComparator comparator) { - int entryIndex = binarySearchNonRootIndex(key, keyOffset, keyLength, - nonRootBlock, comparator); + static int locateNonRootIndexEntry(ByteBuffer nonRootBlock, Cell key, + KVComparator comparator) { + int entryIndex = binarySearchNonRootIndex(key, nonRootBlock, comparator); if (entryIndex != -1) { int numEntries = nonRootBlock.getInt(0); @@ -584,8 +609,7 @@ public class HFileBlockIndex { // The offset of the entry we are interested in relative to the end of // the secondary index. - int entryRelOffset = nonRootBlock.getInt(Bytes.SIZEOF_INT - * (1 + entryIndex)); + int entryRelOffset = nonRootBlock.getInt(Bytes.SIZEOF_INT * (1 + entryIndex)); nonRootBlock.position(entriesOffset + entryRelOffset); }