You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@hbase.apache.org by ra...@apache.org on 2014/03/29 18:18:57 UTC
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...
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:
+ * <ul>
+ * <li>the last key that that is less than or equal to the given key if
+ * <code>seekBefore</code> is false</li>
+ * <li>the last key that is strictly less than the given key if <code>
+ * seekBefore</code> 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.</li>
+ * </ul>
+ * @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<Cell> 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);
}