You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@hbase.apache.org by GitBox <gi...@apache.org> on 2020/12/06 03:29:50 UTC
[GitHub] [hbase] GeorryHuang opened a new pull request #2741: HBASE-25364 Redo the getMidPoint() in HFileWriterImpl to get rid of t…
GeorryHuang opened a new pull request #2741:
URL: https://github.com/apache/hbase/pull/2741
…he double comparison process
There is a TODO like this "TODO: Redo so only a single pass over the arrays rather than one to compare and then a second composing midpoint." in getMidpoint() of class HFileWriteImpl
The old logic compares the left byte array and the right byte array twice：
1. A comparison is performed before composing MinimumMidpointArray
2. During composing of MinimumMidpointArray, bytes were comparing again
My optimization combines them into one
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [hbase] saintstack commented on pull request #2741: HBASE-25364 Redo the getMidPoint() in HFileWriterImpl to get rid of t…
Posted by GitBox <gi...@apache.org>.
saintstack commented on pull request #2741:
URL: https://github.com/apache/hbase/pull/2741#issuecomment-744633516
@nyl3532016 You good w/ this change? If so, would like to add you as a sign-off. Thanks.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [hbase] saintstack commented on a change in pull request #2741: HBASE-25364 Redo the getMidPoint() in HFileWriterImpl to get rid of t…
Posted by GitBox <gi...@apache.org>.
saintstack commented on a change in pull request #2741:
URL: https://github.com/apache/hbase/pull/2741#discussion_r537740722
##########
File path: hbase-server/src/main/java/org/apache/hadoop/hbase/io/hfile/HFileWriterImpl.java
##########
@@ -366,8 +366,6 @@ private void finishBlock() throws IOException {
*/
public static Cell getMidpoint(final CellComparator comparator, final Cell left,
final Cell right) {
- // TODO: Redo so only a single pass over the arrays rather than one to
Review comment:
From HBASE-10800 ... By our Ramkrishna
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [hbase] Apache-HBase commented on pull request #2741: HBASE-25364 Redo the getMidPoint() in HFileWriterImpl to get rid of t…
Posted by GitBox <gi...@apache.org>.
Apache-HBase commented on pull request #2741:
URL: https://github.com/apache/hbase/pull/2741#issuecomment-739452013
:confetti_ball: **+1 overall**
| Vote | Subsystem | Runtime | Comment |
|:----:|----------:|--------:|:--------|
| +0 :ok: | reexec | 1m 8s | Docker mode activated. |
||| _ Prechecks _ |
| +1 :green_heart: | dupname | 0m 0s | No case conflicting files found. |
| +1 :green_heart: | hbaseanti | 0m 0s | Patch does not have any anti-patterns. |
| +1 :green_heart: | @author | 0m 0s | The patch does not contain any @author tags. |
||| _ master Compile Tests _ |
| +1 :green_heart: | mvninstall | 4m 9s | master passed |
| +1 :green_heart: | checkstyle | 1m 12s | master passed |
| +1 :green_heart: | spotbugs | 2m 11s | master passed |
||| _ Patch Compile Tests _ |
| +1 :green_heart: | mvninstall | 3m 47s | the patch passed |
| -0 :warning: | checkstyle | 1m 9s | hbase-server: The patch generated 2 new + 5 unchanged - 0 fixed = 7 total (was 5) |
| +1 :green_heart: | whitespace | 0m 0s | The patch has no whitespace issues. |
| +1 :green_heart: | hadoopcheck | 19m 7s | Patch does not cause any errors with Hadoop 3.1.2 3.2.1 3.3.0. |
| +1 :green_heart: | spotbugs | 2m 18s | the patch passed |
||| _ Other Tests _ |
| +1 :green_heart: | asflicense | 0m 13s | The patch does not generate ASF License warnings. |
| | | 43m 5s | |
| Subsystem | Report/Notes |
|----------:|:-------------|
| Docker | ClientAPI=1.40 ServerAPI=1.40 base: https://ci-hadoop.apache.org/job/HBase/job/HBase-PreCommit-GitHub-PR/job/PR-2741/1/artifact/yetus-general-check/output/Dockerfile |
| GITHUB PR | https://github.com/apache/hbase/pull/2741 |
| Optional Tests | dupname asflicense spotbugs hadoopcheck hbaseanti checkstyle |
| uname | Linux c64fb3ef40e9 4.15.0-112-generic #113-Ubuntu SMP Thu Jul 9 23:41:39 UTC 2020 x86_64 x86_64 x86_64 GNU/Linux |
| Build tool | maven |
| Personality | dev-support/hbase-personality.sh |
| git revision | master / 7d0a687e57 |
| checkstyle | https://ci-hadoop.apache.org/job/HBase/job/HBase-PreCommit-GitHub-PR/job/PR-2741/1/artifact/yetus-general-check/output/diff-checkstyle-hbase-server.txt |
| Max. process+thread count | 84 (vs. ulimit of 30000) |
| modules | C: hbase-server U: hbase-server |
| Console output | https://ci-hadoop.apache.org/job/HBase/job/HBase-PreCommit-GitHub-PR/job/PR-2741/1/console |
| versions | git=2.17.1 maven=3.6.3 spotbugs=3.1.12 |
| Powered by | Apache Yetus 0.12.0 https://yetus.apache.org |
This message was automatically generated.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [hbase] GeorryHuang commented on pull request #2741: HBASE-25364 Redo the getMidPoint() in HFileWriterImpl to get rid of t…
Posted by GitBox <gi...@apache.org>.
GeorryHuang commented on pull request #2741:
URL: https://github.com/apache/hbase/pull/2741#issuecomment-740378200
@saintstack Thanks for reviewing
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [hbase] GeorryHuang commented on a change in pull request #2741: HBASE-25364 Redo the getMidPoint() in HFileWriterImpl to get rid of t…
Posted by GitBox <gi...@apache.org>.
GeorryHuang commented on a change in pull request #2741:
URL: https://github.com/apache/hbase/pull/2741#discussion_r537050892
##########
File path: hbase-server/src/main/java/org/apache/hadoop/hbase/io/hfile/HFileWriterImpl.java
##########
@@ -380,143 +378,146 @@ public static Cell getMidpoint(final CellComparator comparator, final Cell left,
if (comparator instanceof MetaCellComparator) {
return right;
}
- int diff = comparator.compareRows(left, right);
- if (diff > 0) {
- throw new IllegalArgumentException("Left row sorts after right row; left="
- + CellUtil.getCellKeyAsString(left) + ", right=" + CellUtil.getCellKeyAsString(right));
- }
byte[] midRow;
boolean bufferBacked = left instanceof ByteBufferExtendedCell
&& right instanceof ByteBufferExtendedCell;
- if (diff < 0) {
- // Left row is < right row.
- if (bufferBacked) {
- midRow = getMinimumMidpointArray(((ByteBufferExtendedCell) left).getRowByteBuffer(),
- ((ByteBufferExtendedCell) left).getRowPosition(), left.getRowLength(),
- ((ByteBufferExtendedCell) right).getRowByteBuffer(),
- ((ByteBufferExtendedCell) right).getRowPosition(), right.getRowLength());
- } else {
- midRow = getMinimumMidpointArray(left.getRowArray(), left.getRowOffset(),
- left.getRowLength(), right.getRowArray(), right.getRowOffset(), right.getRowLength());
- }
- // If midRow is null, just return 'right'. Can't do optimization.
- if (midRow == null) {
- return right;
- }
+ if (bufferBacked) {
+ midRow = getMinimumMidpointArray(((ByteBufferExtendedCell) left).getRowByteBuffer(),
+ ((ByteBufferExtendedCell) left).getRowPosition(), left.getRowLength(),
+ ((ByteBufferExtendedCell) right).getRowByteBuffer(),
+ ((ByteBufferExtendedCell) right).getRowPosition(), right.getRowLength());
+ } else {
+ midRow = getMinimumMidpointArray(left.getRowArray(), left.getRowOffset(), left.getRowLength(),
+ right.getRowArray(), right.getRowOffset(), right.getRowLength());
+ }
+ if (midRow != null) {
return PrivateCellUtil.createFirstOnRow(midRow);
}
- // Rows are same. Compare on families.
- diff = comparator.compareFamilies(left, right);
- if (diff > 0) {
- throw new IllegalArgumentException("Left family sorts after right family; left="
- + CellUtil.getCellKeyAsString(left) + ", right=" + CellUtil.getCellKeyAsString(right));
- }
- if (diff < 0) {
- if (bufferBacked) {
- midRow = getMinimumMidpointArray(((ByteBufferExtendedCell) left).getFamilyByteBuffer(),
- ((ByteBufferExtendedCell) left).getFamilyPosition(), left.getFamilyLength(),
- ((ByteBufferExtendedCell) right).getFamilyByteBuffer(),
- ((ByteBufferExtendedCell) right).getFamilyPosition(), right.getFamilyLength());
- } else {
- midRow = getMinimumMidpointArray(left.getFamilyArray(), left.getFamilyOffset(),
- left.getFamilyLength(), right.getFamilyArray(), right.getFamilyOffset(),
- right.getFamilyLength());
- }
- // If midRow is null, just return 'right'. Can't do optimization.
- if (midRow == null) {
- return right;
- }
- // Return new Cell where we use right row and then a mid sort family.
+ //Rows are same. Compare on families.
+ if (bufferBacked) {
+ midRow = getMinimumMidpointArray(((ByteBufferExtendedCell) left).getFamilyByteBuffer(),
+ ((ByteBufferExtendedCell) left).getFamilyPosition(), left.getFamilyLength(),
+ ((ByteBufferExtendedCell) right).getFamilyByteBuffer(),
+ ((ByteBufferExtendedCell) right).getFamilyPosition(), right.getFamilyLength());
+ } else {
+ midRow = getMinimumMidpointArray(left.getFamilyArray(), left.getFamilyOffset(),
+ left.getFamilyLength(), right.getFamilyArray(), right.getFamilyOffset(),
+ right.getFamilyLength());
+ }
+ if (midRow != null) {
return PrivateCellUtil.createFirstOnRowFamily(right, midRow, 0, midRow.length);
}
// Families are same. Compare on qualifiers.
- diff = comparator.compareQualifiers(left, right);
- if (diff > 0) {
- throw new IllegalArgumentException("Left qualifier sorts after right qualifier; left="
- + CellUtil.getCellKeyAsString(left) + ", right=" + CellUtil.getCellKeyAsString(right));
- }
- if (diff < 0) {
- if (bufferBacked) {
- midRow = getMinimumMidpointArray(((ByteBufferExtendedCell) left).getQualifierByteBuffer(),
- ((ByteBufferExtendedCell) left).getQualifierPosition(), left.getQualifierLength(),
- ((ByteBufferExtendedCell) right).getQualifierByteBuffer(),
- ((ByteBufferExtendedCell) right).getQualifierPosition(), right.getQualifierLength());
- } else {
- midRow = getMinimumMidpointArray(left.getQualifierArray(), left.getQualifierOffset(),
- left.getQualifierLength(), right.getQualifierArray(), right.getQualifierOffset(),
- right.getQualifierLength());
- }
- // If midRow is null, just return 'right'. Can't do optimization.
- if (midRow == null) {
- return right;
- }
- // Return new Cell where we use right row and family and then a mid sort qualifier.
+ if (bufferBacked) {
+ midRow = getMinimumMidpointArray(((ByteBufferExtendedCell) left).getQualifierByteBuffer(),
+ ((ByteBufferExtendedCell) left).getQualifierPosition(), left.getQualifierLength(),
+ ((ByteBufferExtendedCell) right).getQualifierByteBuffer(),
+ ((ByteBufferExtendedCell) right).getQualifierPosition(), right.getQualifierLength());
+ } else {
+ midRow = getMinimumMidpointArray(left.getQualifierArray(), left.getQualifierOffset(),
+ left.getQualifierLength(), right.getQualifierArray(), right.getQualifierOffset(),
+ right.getQualifierLength());
+ }
+ if (midRow != null) {
return PrivateCellUtil.createFirstOnRowCol(right, midRow, 0, midRow.length);
}
// No opportunity for optimization. Just return right key.
return right;
}
/**
+ * Try to get a byte array that falls between left and right as short as possible with
+ * lexicographical order;
+ *
* @return Return a new array that is between left and right and minimally
- * sized else just return null as indicator that we could not create a
- * mid point.
+ * sized else just return null if left == right.
*/
private static byte[] getMinimumMidpointArray(final byte[] leftArray, final int leftOffset,
final int leftLength, final byte[] rightArray, final int rightOffset, final int rightLength) {
- // rows are different
int minLength = leftLength < rightLength ? leftLength : rightLength;
int diffIdx = 0;
- while (diffIdx < minLength
- && leftArray[leftOffset + diffIdx] == rightArray[rightOffset + diffIdx]) {
- diffIdx++;
- }
- byte[] minimumMidpointArray = null;
- if (diffIdx >= minLength) {
- // leftKey's row is prefix of rightKey's.
- minimumMidpointArray = new byte[diffIdx + 1];
- System.arraycopy(rightArray, rightOffset, minimumMidpointArray, 0, diffIdx + 1);
- } else {
- int diffByte = leftArray[leftOffset + diffIdx];
- if ((0xff & diffByte) < 0xff && (diffByte + 1) < (rightArray[rightOffset + diffIdx] & 0xff)) {
- minimumMidpointArray = new byte[diffIdx + 1];
- System.arraycopy(leftArray, leftOffset, minimumMidpointArray, 0, diffIdx);
- minimumMidpointArray[diffIdx] = (byte) (diffByte + 1);
+ for (; diffIdx < minLength; diffIdx++) {
+ byte leftByte = leftArray[leftOffset + diffIdx];
+ byte rightByte = rightArray[rightOffset + diffIdx];
+ if ((leftByte & 0xff) > (rightByte & 0xff)) {
+ throw new IllegalArgumentException("Left byte array sorts after right row; left=" + Bytes
+ .toStringBinary(leftArray, leftOffset, leftLength) + ", right=" + Bytes
+ .toStringBinary(rightArray, rightOffset, rightLength));
+ } else if (leftByte != rightByte) {
+ break;
+ }
+ }
+ if (diffIdx == minLength) {
+ if (leftLength > rightLength) {
+ //right is prefix of left
+ throw new IllegalArgumentException("Left byte array sorts after right row; left=" + Bytes
+ .toStringBinary(leftArray, leftOffset, leftLength) + ", right=" + Bytes
+ .toStringBinary(rightArray, rightOffset, rightLength));
+ } else if (leftLength < rightLength) {
+ //left is prefix of right.
+ byte[] minimumMidpointArray = new byte[minLength + 1];
+ System.arraycopy(rightArray, rightOffset, minimumMidpointArray, 0, minLength + 1);
+ minimumMidpointArray[minLength] = 0x00;
+ return minimumMidpointArray;
} else {
- minimumMidpointArray = new byte[diffIdx + 1];
- System.arraycopy(rightArray, rightOffset, minimumMidpointArray, 0, diffIdx + 1);
+ //left == right
+ return null;
}
}
+ //Note that left[diffIdx] can never be equal to 0xff since left < right
+ byte[] minimumMidpointArray = new byte[diffIdx + 1];
+ System.arraycopy(leftArray, leftOffset, minimumMidpointArray, 0, diffIdx + 1);
+ minimumMidpointArray[diffIdx] = (byte) (minimumMidpointArray[diffIdx] + 1);
return minimumMidpointArray;
}
+ /**
+ * Try to create a new byte array that falls between left and right as short as possible with
+ * lexicographical order.
+ *
+ * @return Return a new array that is between left and right and minimally
+ * sized else just return null if left == right.
+ */
private static byte[] getMinimumMidpointArray(ByteBuffer left, int leftOffset, int leftLength,
ByteBuffer right, int rightOffset, int rightLength) {
- // rows are different
int minLength = leftLength < rightLength ? leftLength : rightLength;
int diffIdx = 0;
- while (diffIdx < minLength && ByteBufferUtils.toByte(left,
- leftOffset + diffIdx) == ByteBufferUtils.toByte(right, rightOffset + diffIdx)) {
- diffIdx++;
- }
- byte[] minMidpoint = null;
- if (diffIdx >= minLength) {
- // leftKey's row is prefix of rightKey's.
- minMidpoint = new byte[diffIdx + 1];
- ByteBufferUtils.copyFromBufferToArray(minMidpoint, right, rightOffset, 0, diffIdx + 1);
- } else {
- int diffByte = ByteBufferUtils.toByte(left, leftOffset + diffIdx);
- if ((0xff & diffByte) < 0xff
- && (diffByte + 1) < (ByteBufferUtils.toByte(right, rightOffset + diffIdx) & 0xff)) {
- minMidpoint = new byte[diffIdx + 1];
- ByteBufferUtils.copyFromBufferToArray(minMidpoint, left, leftOffset, 0, diffIdx);
- minMidpoint[diffIdx] = (byte) (diffByte + 1);
+ for (; diffIdx < minLength; diffIdx++) {
+ int leftByte = ByteBufferUtils.toByte(left, leftOffset + diffIdx);
+ int rightByte = ByteBufferUtils.toByte(right, rightOffset + diffIdx);
+ if ((leftByte & 0xff) > (rightByte & 0xff)) {
+ throw new IllegalArgumentException(
+ "Left byte array sorts after right row; left=" + ByteBufferUtils
+ .toStringBinary(left, leftOffset, leftLength) + ", right=" + ByteBufferUtils
+ .toStringBinary(right, rightOffset, rightLength));
+ } else if (leftByte != rightByte) {
+ break;
+ }
+ }
+ if (diffIdx == minLength) {
+ if (leftLength > rightLength) {
+ //right is prefix of left
+ throw new IllegalArgumentException(
+ "Left byte array sorts after right row; left=" + ByteBufferUtils
+ .toStringBinary(left, leftOffset, leftLength) + ", right=" + ByteBufferUtils
+ .toStringBinary(right, rightOffset, rightLength));
+ } else if (leftLength < rightLength) {
+ //left is prefix of right.
+ byte[] minimumMidpointArray = new byte[minLength + 1];
+ ByteBufferUtils
+ .copyFromBufferToArray(minimumMidpointArray, right, rightOffset, 0, minLength + 1);
+ minimumMidpointArray[minLength] = 0x00;
Review comment:
Yes, I made some adjustments.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [hbase] Apache-HBase commented on pull request #2741: HBASE-25364 Redo the getMidPoint() in HFileWriterImpl to get rid of t…
Posted by GitBox <gi...@apache.org>.
Apache-HBase commented on pull request #2741:
URL: https://github.com/apache/hbase/pull/2741#issuecomment-739461777
:confetti_ball: **+1 overall**
| Vote | Subsystem | Runtime | Comment |
|:----:|----------:|--------:|:--------|
| +0 :ok: | reexec | 1m 6s | Docker mode activated. |
| -0 :warning: | yetus | 0m 4s | Unprocessed flag(s): --brief-report-file --spotbugs-strict-precheck --whitespace-eol-ignore-list --whitespace-tabs-ignore-list --quick-hadoopcheck |
||| _ Prechecks _ |
||| _ master Compile Tests _ |
| +1 :green_heart: | mvninstall | 4m 17s | master passed |
| +1 :green_heart: | compile | 1m 5s | master passed |
| +1 :green_heart: | shadedjars | 6m 42s | branch has no errors when building our shaded downstream artifacts. |
| +1 :green_heart: | javadoc | 0m 42s | master passed |
||| _ Patch Compile Tests _ |
| +1 :green_heart: | mvninstall | 4m 1s | the patch passed |
| +1 :green_heart: | compile | 1m 4s | the patch passed |
| +1 :green_heart: | javac | 1m 4s | the patch passed |
| +1 :green_heart: | shadedjars | 6m 35s | patch has no errors when building our shaded downstream artifacts. |
| +1 :green_heart: | javadoc | 0m 38s | the patch passed |
||| _ Other Tests _ |
| +1 :green_heart: | unit | 137m 39s | hbase-server in the patch passed. |
| | | 165m 53s | |
| Subsystem | Report/Notes |
|----------:|:-------------|
| Docker | ClientAPI=1.40 ServerAPI=1.40 base: https://ci-hadoop.apache.org/job/HBase/job/HBase-PreCommit-GitHub-PR/job/PR-2741/1/artifact/yetus-jdk11-hadoop3-check/output/Dockerfile |
| GITHUB PR | https://github.com/apache/hbase/pull/2741 |
| Optional Tests | javac javadoc unit shadedjars compile |
| uname | Linux 4e341520fd43 4.15.0-65-generic #74-Ubuntu SMP Tue Sep 17 17:06:04 UTC 2019 x86_64 x86_64 x86_64 GNU/Linux |
| Build tool | maven |
| Personality | dev-support/hbase-personality.sh |
| git revision | master / 7d0a687e57 |
| Default Java | AdoptOpenJDK-11.0.6+10 |
| Test Results | https://ci-hadoop.apache.org/job/HBase/job/HBase-PreCommit-GitHub-PR/job/PR-2741/1/testReport/ |
| Max. process+thread count | 4231 (vs. ulimit of 30000) |
| modules | C: hbase-server U: hbase-server |
| Console output | https://ci-hadoop.apache.org/job/HBase/job/HBase-PreCommit-GitHub-PR/job/PR-2741/1/console |
| versions | git=2.17.1 maven=3.6.3 |
| Powered by | Apache Yetus 0.12.0 https://yetus.apache.org |
This message was automatically generated.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [hbase] nyl3532016 commented on a change in pull request #2741: HBASE-25364 Redo the getMidPoint() in HFileWriterImpl to get rid of t…
Posted by GitBox <gi...@apache.org>.
nyl3532016 commented on a change in pull request #2741:
URL: https://github.com/apache/hbase/pull/2741#discussion_r537046002
##########
File path: hbase-server/src/main/java/org/apache/hadoop/hbase/io/hfile/HFileWriterImpl.java
##########
@@ -380,143 +378,146 @@ public static Cell getMidpoint(final CellComparator comparator, final Cell left,
if (comparator instanceof MetaCellComparator) {
return right;
}
- int diff = comparator.compareRows(left, right);
- if (diff > 0) {
- throw new IllegalArgumentException("Left row sorts after right row; left="
- + CellUtil.getCellKeyAsString(left) + ", right=" + CellUtil.getCellKeyAsString(right));
- }
byte[] midRow;
boolean bufferBacked = left instanceof ByteBufferExtendedCell
&& right instanceof ByteBufferExtendedCell;
- if (diff < 0) {
- // Left row is < right row.
- if (bufferBacked) {
- midRow = getMinimumMidpointArray(((ByteBufferExtendedCell) left).getRowByteBuffer(),
- ((ByteBufferExtendedCell) left).getRowPosition(), left.getRowLength(),
- ((ByteBufferExtendedCell) right).getRowByteBuffer(),
- ((ByteBufferExtendedCell) right).getRowPosition(), right.getRowLength());
- } else {
- midRow = getMinimumMidpointArray(left.getRowArray(), left.getRowOffset(),
- left.getRowLength(), right.getRowArray(), right.getRowOffset(), right.getRowLength());
- }
- // If midRow is null, just return 'right'. Can't do optimization.
- if (midRow == null) {
- return right;
- }
+ if (bufferBacked) {
+ midRow = getMinimumMidpointArray(((ByteBufferExtendedCell) left).getRowByteBuffer(),
+ ((ByteBufferExtendedCell) left).getRowPosition(), left.getRowLength(),
+ ((ByteBufferExtendedCell) right).getRowByteBuffer(),
+ ((ByteBufferExtendedCell) right).getRowPosition(), right.getRowLength());
+ } else {
+ midRow = getMinimumMidpointArray(left.getRowArray(), left.getRowOffset(), left.getRowLength(),
+ right.getRowArray(), right.getRowOffset(), right.getRowLength());
+ }
+ if (midRow != null) {
return PrivateCellUtil.createFirstOnRow(midRow);
}
- // Rows are same. Compare on families.
- diff = comparator.compareFamilies(left, right);
- if (diff > 0) {
- throw new IllegalArgumentException("Left family sorts after right family; left="
- + CellUtil.getCellKeyAsString(left) + ", right=" + CellUtil.getCellKeyAsString(right));
- }
- if (diff < 0) {
- if (bufferBacked) {
- midRow = getMinimumMidpointArray(((ByteBufferExtendedCell) left).getFamilyByteBuffer(),
- ((ByteBufferExtendedCell) left).getFamilyPosition(), left.getFamilyLength(),
- ((ByteBufferExtendedCell) right).getFamilyByteBuffer(),
- ((ByteBufferExtendedCell) right).getFamilyPosition(), right.getFamilyLength());
- } else {
- midRow = getMinimumMidpointArray(left.getFamilyArray(), left.getFamilyOffset(),
- left.getFamilyLength(), right.getFamilyArray(), right.getFamilyOffset(),
- right.getFamilyLength());
- }
- // If midRow is null, just return 'right'. Can't do optimization.
- if (midRow == null) {
- return right;
- }
- // Return new Cell where we use right row and then a mid sort family.
+ //Rows are same. Compare on families.
+ if (bufferBacked) {
+ midRow = getMinimumMidpointArray(((ByteBufferExtendedCell) left).getFamilyByteBuffer(),
+ ((ByteBufferExtendedCell) left).getFamilyPosition(), left.getFamilyLength(),
+ ((ByteBufferExtendedCell) right).getFamilyByteBuffer(),
+ ((ByteBufferExtendedCell) right).getFamilyPosition(), right.getFamilyLength());
+ } else {
+ midRow = getMinimumMidpointArray(left.getFamilyArray(), left.getFamilyOffset(),
+ left.getFamilyLength(), right.getFamilyArray(), right.getFamilyOffset(),
+ right.getFamilyLength());
+ }
+ if (midRow != null) {
return PrivateCellUtil.createFirstOnRowFamily(right, midRow, 0, midRow.length);
}
// Families are same. Compare on qualifiers.
- diff = comparator.compareQualifiers(left, right);
- if (diff > 0) {
- throw new IllegalArgumentException("Left qualifier sorts after right qualifier; left="
- + CellUtil.getCellKeyAsString(left) + ", right=" + CellUtil.getCellKeyAsString(right));
- }
- if (diff < 0) {
- if (bufferBacked) {
- midRow = getMinimumMidpointArray(((ByteBufferExtendedCell) left).getQualifierByteBuffer(),
- ((ByteBufferExtendedCell) left).getQualifierPosition(), left.getQualifierLength(),
- ((ByteBufferExtendedCell) right).getQualifierByteBuffer(),
- ((ByteBufferExtendedCell) right).getQualifierPosition(), right.getQualifierLength());
- } else {
- midRow = getMinimumMidpointArray(left.getQualifierArray(), left.getQualifierOffset(),
- left.getQualifierLength(), right.getQualifierArray(), right.getQualifierOffset(),
- right.getQualifierLength());
- }
- // If midRow is null, just return 'right'. Can't do optimization.
- if (midRow == null) {
- return right;
- }
- // Return new Cell where we use right row and family and then a mid sort qualifier.
+ if (bufferBacked) {
+ midRow = getMinimumMidpointArray(((ByteBufferExtendedCell) left).getQualifierByteBuffer(),
+ ((ByteBufferExtendedCell) left).getQualifierPosition(), left.getQualifierLength(),
+ ((ByteBufferExtendedCell) right).getQualifierByteBuffer(),
+ ((ByteBufferExtendedCell) right).getQualifierPosition(), right.getQualifierLength());
+ } else {
+ midRow = getMinimumMidpointArray(left.getQualifierArray(), left.getQualifierOffset(),
+ left.getQualifierLength(), right.getQualifierArray(), right.getQualifierOffset(),
+ right.getQualifierLength());
+ }
+ if (midRow != null) {
return PrivateCellUtil.createFirstOnRowCol(right, midRow, 0, midRow.length);
}
// No opportunity for optimization. Just return right key.
return right;
}
/**
+ * Try to get a byte array that falls between left and right as short as possible with
+ * lexicographical order;
+ *
* @return Return a new array that is between left and right and minimally
- * sized else just return null as indicator that we could not create a
- * mid point.
+ * sized else just return null if left == right.
*/
private static byte[] getMinimumMidpointArray(final byte[] leftArray, final int leftOffset,
final int leftLength, final byte[] rightArray, final int rightOffset, final int rightLength) {
- // rows are different
int minLength = leftLength < rightLength ? leftLength : rightLength;
int diffIdx = 0;
- while (diffIdx < minLength
- && leftArray[leftOffset + diffIdx] == rightArray[rightOffset + diffIdx]) {
- diffIdx++;
- }
- byte[] minimumMidpointArray = null;
- if (diffIdx >= minLength) {
- // leftKey's row is prefix of rightKey's.
- minimumMidpointArray = new byte[diffIdx + 1];
- System.arraycopy(rightArray, rightOffset, minimumMidpointArray, 0, diffIdx + 1);
- } else {
- int diffByte = leftArray[leftOffset + diffIdx];
- if ((0xff & diffByte) < 0xff && (diffByte + 1) < (rightArray[rightOffset + diffIdx] & 0xff)) {
- minimumMidpointArray = new byte[diffIdx + 1];
- System.arraycopy(leftArray, leftOffset, minimumMidpointArray, 0, diffIdx);
- minimumMidpointArray[diffIdx] = (byte) (diffByte + 1);
+ for (; diffIdx < minLength; diffIdx++) {
+ byte leftByte = leftArray[leftOffset + diffIdx];
+ byte rightByte = rightArray[rightOffset + diffIdx];
+ if ((leftByte & 0xff) > (rightByte & 0xff)) {
+ throw new IllegalArgumentException("Left byte array sorts after right row; left=" + Bytes
+ .toStringBinary(leftArray, leftOffset, leftLength) + ", right=" + Bytes
+ .toStringBinary(rightArray, rightOffset, rightLength));
+ } else if (leftByte != rightByte) {
+ break;
+ }
+ }
+ if (diffIdx == minLength) {
+ if (leftLength > rightLength) {
+ //right is prefix of left
+ throw new IllegalArgumentException("Left byte array sorts after right row; left=" + Bytes
+ .toStringBinary(leftArray, leftOffset, leftLength) + ", right=" + Bytes
+ .toStringBinary(rightArray, rightOffset, rightLength));
+ } else if (leftLength < rightLength) {
+ //left is prefix of right.
+ byte[] minimumMidpointArray = new byte[minLength + 1];
+ System.arraycopy(rightArray, rightOffset, minimumMidpointArray, 0, minLength + 1);
+ minimumMidpointArray[minLength] = 0x00;
+ return minimumMidpointArray;
} else {
- minimumMidpointArray = new byte[diffIdx + 1];
- System.arraycopy(rightArray, rightOffset, minimumMidpointArray, 0, diffIdx + 1);
+ //left == right
+ return null;
}
}
+ //Note that left[diffIdx] can never be equal to 0xff since left < right
+ byte[] minimumMidpointArray = new byte[diffIdx + 1];
+ System.arraycopy(leftArray, leftOffset, minimumMidpointArray, 0, diffIdx + 1);
+ minimumMidpointArray[diffIdx] = (byte) (minimumMidpointArray[diffIdx] + 1);
return minimumMidpointArray;
}
+ /**
+ * Try to create a new byte array that falls between left and right as short as possible with
+ * lexicographical order.
+ *
+ * @return Return a new array that is between left and right and minimally
+ * sized else just return null if left == right.
+ */
private static byte[] getMinimumMidpointArray(ByteBuffer left, int leftOffset, int leftLength,
ByteBuffer right, int rightOffset, int rightLength) {
- // rows are different
int minLength = leftLength < rightLength ? leftLength : rightLength;
int diffIdx = 0;
- while (diffIdx < minLength && ByteBufferUtils.toByte(left,
- leftOffset + diffIdx) == ByteBufferUtils.toByte(right, rightOffset + diffIdx)) {
- diffIdx++;
- }
- byte[] minMidpoint = null;
- if (diffIdx >= minLength) {
- // leftKey's row is prefix of rightKey's.
- minMidpoint = new byte[diffIdx + 1];
- ByteBufferUtils.copyFromBufferToArray(minMidpoint, right, rightOffset, 0, diffIdx + 1);
- } else {
- int diffByte = ByteBufferUtils.toByte(left, leftOffset + diffIdx);
- if ((0xff & diffByte) < 0xff
- && (diffByte + 1) < (ByteBufferUtils.toByte(right, rightOffset + diffIdx) & 0xff)) {
- minMidpoint = new byte[diffIdx + 1];
- ByteBufferUtils.copyFromBufferToArray(minMidpoint, left, leftOffset, 0, diffIdx);
- minMidpoint[diffIdx] = (byte) (diffByte + 1);
+ for (; diffIdx < minLength; diffIdx++) {
+ int leftByte = ByteBufferUtils.toByte(left, leftOffset + diffIdx);
+ int rightByte = ByteBufferUtils.toByte(right, rightOffset + diffIdx);
+ if ((leftByte & 0xff) > (rightByte & 0xff)) {
+ throw new IllegalArgumentException(
+ "Left byte array sorts after right row; left=" + ByteBufferUtils
+ .toStringBinary(left, leftOffset, leftLength) + ", right=" + ByteBufferUtils
+ .toStringBinary(right, rightOffset, rightLength));
+ } else if (leftByte != rightByte) {
+ break;
+ }
+ }
+ if (diffIdx == minLength) {
+ if (leftLength > rightLength) {
+ //right is prefix of left
+ throw new IllegalArgumentException(
+ "Left byte array sorts after right row; left=" + ByteBufferUtils
+ .toStringBinary(left, leftOffset, leftLength) + ", right=" + ByteBufferUtils
+ .toStringBinary(right, rightOffset, rightLength));
+ } else if (leftLength < rightLength) {
+ //left is prefix of right.
+ byte[] minimumMidpointArray = new byte[minLength + 1];
+ ByteBufferUtils
+ .copyFromBufferToArray(minimumMidpointArray, right, rightOffset, 0, minLength + 1);
+ minimumMidpointArray[minLength] = 0x00;
Review comment:
Here is different from original?
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [hbase] Apache-HBase commented on pull request #2741: HBASE-25364 Redo the getMidPoint() in HFileWriterImpl to get rid of t…
Posted by GitBox <gi...@apache.org>.
Apache-HBase commented on pull request #2741:
URL: https://github.com/apache/hbase/pull/2741#issuecomment-739466574
:confetti_ball: **+1 overall**
| Vote | Subsystem | Runtime | Comment |
|:----:|----------:|--------:|:--------|
| +0 :ok: | reexec | 1m 6s | Docker mode activated. |
| -0 :warning: | yetus | 0m 2s | Unprocessed flag(s): --brief-report-file --spotbugs-strict-precheck --whitespace-eol-ignore-list --whitespace-tabs-ignore-list --quick-hadoopcheck |
||| _ Prechecks _ |
||| _ master Compile Tests _ |
| +1 :green_heart: | mvninstall | 4m 12s | master passed |
| +1 :green_heart: | compile | 0m 59s | master passed |
| +1 :green_heart: | shadedjars | 7m 10s | branch has no errors when building our shaded downstream artifacts. |
| +1 :green_heart: | javadoc | 0m 39s | master passed |
||| _ Patch Compile Tests _ |
| +1 :green_heart: | mvninstall | 3m 50s | the patch passed |
| +1 :green_heart: | compile | 1m 0s | the patch passed |
| +1 :green_heart: | javac | 1m 0s | the patch passed |
| +1 :green_heart: | shadedjars | 7m 9s | patch has no errors when building our shaded downstream artifacts. |
| +1 :green_heart: | javadoc | 0m 36s | the patch passed |
||| _ Other Tests _ |
| +1 :green_heart: | unit | 204m 1s | hbase-server in the patch passed. |
| | | 232m 29s | |
| Subsystem | Report/Notes |
|----------:|:-------------|
| Docker | ClientAPI=1.40 ServerAPI=1.40 base: https://ci-hadoop.apache.org/job/HBase/job/HBase-PreCommit-GitHub-PR/job/PR-2741/1/artifact/yetus-jdk8-hadoop3-check/output/Dockerfile |
| GITHUB PR | https://github.com/apache/hbase/pull/2741 |
| Optional Tests | javac javadoc unit shadedjars compile |
| uname | Linux 0e740dfd9e37 4.15.0-112-generic #113-Ubuntu SMP Thu Jul 9 23:41:39 UTC 2020 x86_64 x86_64 x86_64 GNU/Linux |
| Build tool | maven |
| Personality | dev-support/hbase-personality.sh |
| git revision | master / 7d0a687e57 |
| Default Java | AdoptOpenJDK-1.8.0_232-b09 |
| Test Results | https://ci-hadoop.apache.org/job/HBase/job/HBase-PreCommit-GitHub-PR/job/PR-2741/1/testReport/ |
| Max. process+thread count | 3241 (vs. ulimit of 30000) |
| modules | C: hbase-server U: hbase-server |
| Console output | https://ci-hadoop.apache.org/job/HBase/job/HBase-PreCommit-GitHub-PR/job/PR-2741/1/console |
| versions | git=2.17.1 maven=3.6.3 |
| Powered by | Apache Yetus 0.12.0 https://yetus.apache.org |
This message was automatically generated.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [hbase] nyl3532016 commented on pull request #2741: HBASE-25364 Redo the getMidPoint() in HFileWriterImpl to get rid of t…
Posted by GitBox <gi...@apache.org>.
nyl3532016 commented on pull request #2741:
URL: https://github.com/apache/hbase/pull/2741#issuecomment-750804058
> @nyl3532016 You good w/ this change? If so, would like to add you as a sign-off. Thanks.
@saintstack, I am good with the patch after @GeorryHuang amend a bit
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [hbase] saintstack merged pull request #2741: HBASE-25364 Redo the getMidPoint() in HFileWriterImpl to get rid of t…
Posted by GitBox <gi...@apache.org>.
saintstack merged pull request #2741:
URL: https://github.com/apache/hbase/pull/2741
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [hbase] GeorryHuang commented on a change in pull request #2741: HBASE-25364 Redo the getMidPoint() in HFileWriterImpl to get rid of t…
Posted by GitBox <gi...@apache.org>.
GeorryHuang commented on a change in pull request #2741:
URL: https://github.com/apache/hbase/pull/2741#discussion_r537051205
##########
File path: hbase-server/src/main/java/org/apache/hadoop/hbase/io/hfile/HFileWriterImpl.java
##########
@@ -380,143 +378,146 @@ public static Cell getMidpoint(final CellComparator comparator, final Cell left,
if (comparator instanceof MetaCellComparator) {
return right;
}
- int diff = comparator.compareRows(left, right);
- if (diff > 0) {
- throw new IllegalArgumentException("Left row sorts after right row; left="
- + CellUtil.getCellKeyAsString(left) + ", right=" + CellUtil.getCellKeyAsString(right));
- }
byte[] midRow;
boolean bufferBacked = left instanceof ByteBufferExtendedCell
&& right instanceof ByteBufferExtendedCell;
- if (diff < 0) {
- // Left row is < right row.
- if (bufferBacked) {
- midRow = getMinimumMidpointArray(((ByteBufferExtendedCell) left).getRowByteBuffer(),
- ((ByteBufferExtendedCell) left).getRowPosition(), left.getRowLength(),
- ((ByteBufferExtendedCell) right).getRowByteBuffer(),
- ((ByteBufferExtendedCell) right).getRowPosition(), right.getRowLength());
- } else {
- midRow = getMinimumMidpointArray(left.getRowArray(), left.getRowOffset(),
- left.getRowLength(), right.getRowArray(), right.getRowOffset(), right.getRowLength());
- }
- // If midRow is null, just return 'right'. Can't do optimization.
- if (midRow == null) {
- return right;
- }
+ if (bufferBacked) {
+ midRow = getMinimumMidpointArray(((ByteBufferExtendedCell) left).getRowByteBuffer(),
+ ((ByteBufferExtendedCell) left).getRowPosition(), left.getRowLength(),
+ ((ByteBufferExtendedCell) right).getRowByteBuffer(),
+ ((ByteBufferExtendedCell) right).getRowPosition(), right.getRowLength());
+ } else {
+ midRow = getMinimumMidpointArray(left.getRowArray(), left.getRowOffset(), left.getRowLength(),
+ right.getRowArray(), right.getRowOffset(), right.getRowLength());
+ }
+ if (midRow != null) {
return PrivateCellUtil.createFirstOnRow(midRow);
}
- // Rows are same. Compare on families.
- diff = comparator.compareFamilies(left, right);
- if (diff > 0) {
- throw new IllegalArgumentException("Left family sorts after right family; left="
- + CellUtil.getCellKeyAsString(left) + ", right=" + CellUtil.getCellKeyAsString(right));
- }
- if (diff < 0) {
- if (bufferBacked) {
- midRow = getMinimumMidpointArray(((ByteBufferExtendedCell) left).getFamilyByteBuffer(),
- ((ByteBufferExtendedCell) left).getFamilyPosition(), left.getFamilyLength(),
- ((ByteBufferExtendedCell) right).getFamilyByteBuffer(),
- ((ByteBufferExtendedCell) right).getFamilyPosition(), right.getFamilyLength());
- } else {
- midRow = getMinimumMidpointArray(left.getFamilyArray(), left.getFamilyOffset(),
- left.getFamilyLength(), right.getFamilyArray(), right.getFamilyOffset(),
- right.getFamilyLength());
- }
- // If midRow is null, just return 'right'. Can't do optimization.
- if (midRow == null) {
- return right;
- }
- // Return new Cell where we use right row and then a mid sort family.
+ //Rows are same. Compare on families.
+ if (bufferBacked) {
+ midRow = getMinimumMidpointArray(((ByteBufferExtendedCell) left).getFamilyByteBuffer(),
+ ((ByteBufferExtendedCell) left).getFamilyPosition(), left.getFamilyLength(),
+ ((ByteBufferExtendedCell) right).getFamilyByteBuffer(),
+ ((ByteBufferExtendedCell) right).getFamilyPosition(), right.getFamilyLength());
+ } else {
+ midRow = getMinimumMidpointArray(left.getFamilyArray(), left.getFamilyOffset(),
+ left.getFamilyLength(), right.getFamilyArray(), right.getFamilyOffset(),
+ right.getFamilyLength());
+ }
+ if (midRow != null) {
return PrivateCellUtil.createFirstOnRowFamily(right, midRow, 0, midRow.length);
}
// Families are same. Compare on qualifiers.
- diff = comparator.compareQualifiers(left, right);
- if (diff > 0) {
- throw new IllegalArgumentException("Left qualifier sorts after right qualifier; left="
- + CellUtil.getCellKeyAsString(left) + ", right=" + CellUtil.getCellKeyAsString(right));
- }
- if (diff < 0) {
- if (bufferBacked) {
- midRow = getMinimumMidpointArray(((ByteBufferExtendedCell) left).getQualifierByteBuffer(),
- ((ByteBufferExtendedCell) left).getQualifierPosition(), left.getQualifierLength(),
- ((ByteBufferExtendedCell) right).getQualifierByteBuffer(),
- ((ByteBufferExtendedCell) right).getQualifierPosition(), right.getQualifierLength());
- } else {
- midRow = getMinimumMidpointArray(left.getQualifierArray(), left.getQualifierOffset(),
- left.getQualifierLength(), right.getQualifierArray(), right.getQualifierOffset(),
- right.getQualifierLength());
- }
- // If midRow is null, just return 'right'. Can't do optimization.
- if (midRow == null) {
- return right;
- }
- // Return new Cell where we use right row and family and then a mid sort qualifier.
+ if (bufferBacked) {
+ midRow = getMinimumMidpointArray(((ByteBufferExtendedCell) left).getQualifierByteBuffer(),
+ ((ByteBufferExtendedCell) left).getQualifierPosition(), left.getQualifierLength(),
+ ((ByteBufferExtendedCell) right).getQualifierByteBuffer(),
+ ((ByteBufferExtendedCell) right).getQualifierPosition(), right.getQualifierLength());
+ } else {
+ midRow = getMinimumMidpointArray(left.getQualifierArray(), left.getQualifierOffset(),
+ left.getQualifierLength(), right.getQualifierArray(), right.getQualifierOffset(),
+ right.getQualifierLength());
+ }
+ if (midRow != null) {
return PrivateCellUtil.createFirstOnRowCol(right, midRow, 0, midRow.length);
}
// No opportunity for optimization. Just return right key.
return right;
}
/**
+ * Try to get a byte array that falls between left and right as short as possible with
+ * lexicographical order;
+ *
* @return Return a new array that is between left and right and minimally
- * sized else just return null as indicator that we could not create a
- * mid point.
+ * sized else just return null if left == right.
*/
private static byte[] getMinimumMidpointArray(final byte[] leftArray, final int leftOffset,
final int leftLength, final byte[] rightArray, final int rightOffset, final int rightLength) {
- // rows are different
int minLength = leftLength < rightLength ? leftLength : rightLength;
int diffIdx = 0;
- while (diffIdx < minLength
- && leftArray[leftOffset + diffIdx] == rightArray[rightOffset + diffIdx]) {
- diffIdx++;
- }
- byte[] minimumMidpointArray = null;
- if (diffIdx >= minLength) {
- // leftKey's row is prefix of rightKey's.
- minimumMidpointArray = new byte[diffIdx + 1];
- System.arraycopy(rightArray, rightOffset, minimumMidpointArray, 0, diffIdx + 1);
- } else {
- int diffByte = leftArray[leftOffset + diffIdx];
- if ((0xff & diffByte) < 0xff && (diffByte + 1) < (rightArray[rightOffset + diffIdx] & 0xff)) {
- minimumMidpointArray = new byte[diffIdx + 1];
- System.arraycopy(leftArray, leftOffset, minimumMidpointArray, 0, diffIdx);
- minimumMidpointArray[diffIdx] = (byte) (diffByte + 1);
+ for (; diffIdx < minLength; diffIdx++) {
+ byte leftByte = leftArray[leftOffset + diffIdx];
+ byte rightByte = rightArray[rightOffset + diffIdx];
+ if ((leftByte & 0xff) > (rightByte & 0xff)) {
+ throw new IllegalArgumentException("Left byte array sorts after right row; left=" + Bytes
+ .toStringBinary(leftArray, leftOffset, leftLength) + ", right=" + Bytes
+ .toStringBinary(rightArray, rightOffset, rightLength));
+ } else if (leftByte != rightByte) {
+ break;
+ }
+ }
+ if (diffIdx == minLength) {
+ if (leftLength > rightLength) {
+ //right is prefix of left
+ throw new IllegalArgumentException("Left byte array sorts after right row; left=" + Bytes
+ .toStringBinary(leftArray, leftOffset, leftLength) + ", right=" + Bytes
+ .toStringBinary(rightArray, rightOffset, rightLength));
+ } else if (leftLength < rightLength) {
+ //left is prefix of right.
+ byte[] minimumMidpointArray = new byte[minLength + 1];
+ System.arraycopy(rightArray, rightOffset, minimumMidpointArray, 0, minLength + 1);
+ minimumMidpointArray[minLength] = 0x00;
+ return minimumMidpointArray;
} else {
- minimumMidpointArray = new byte[diffIdx + 1];
- System.arraycopy(rightArray, rightOffset, minimumMidpointArray, 0, diffIdx + 1);
+ //left == right
+ return null;
}
}
+ //Note that left[diffIdx] can never be equal to 0xff since left < right
+ byte[] minimumMidpointArray = new byte[diffIdx + 1];
+ System.arraycopy(leftArray, leftOffset, minimumMidpointArray, 0, diffIdx + 1);
+ minimumMidpointArray[diffIdx] = (byte) (minimumMidpointArray[diffIdx] + 1);
return minimumMidpointArray;
}
+ /**
+ * Try to create a new byte array that falls between left and right as short as possible with
+ * lexicographical order.
+ *
+ * @return Return a new array that is between left and right and minimally
+ * sized else just return null if left == right.
+ */
private static byte[] getMinimumMidpointArray(ByteBuffer left, int leftOffset, int leftLength,
ByteBuffer right, int rightOffset, int rightLength) {
- // rows are different
int minLength = leftLength < rightLength ? leftLength : rightLength;
int diffIdx = 0;
- while (diffIdx < minLength && ByteBufferUtils.toByte(left,
- leftOffset + diffIdx) == ByteBufferUtils.toByte(right, rightOffset + diffIdx)) {
- diffIdx++;
- }
- byte[] minMidpoint = null;
- if (diffIdx >= minLength) {
- // leftKey's row is prefix of rightKey's.
- minMidpoint = new byte[diffIdx + 1];
- ByteBufferUtils.copyFromBufferToArray(minMidpoint, right, rightOffset, 0, diffIdx + 1);
- } else {
- int diffByte = ByteBufferUtils.toByte(left, leftOffset + diffIdx);
- if ((0xff & diffByte) < 0xff
- && (diffByte + 1) < (ByteBufferUtils.toByte(right, rightOffset + diffIdx) & 0xff)) {
- minMidpoint = new byte[diffIdx + 1];
- ByteBufferUtils.copyFromBufferToArray(minMidpoint, left, leftOffset, 0, diffIdx);
- minMidpoint[diffIdx] = (byte) (diffByte + 1);
+ for (; diffIdx < minLength; diffIdx++) {
+ int leftByte = ByteBufferUtils.toByte(left, leftOffset + diffIdx);
+ int rightByte = ByteBufferUtils.toByte(right, rightOffset + diffIdx);
+ if ((leftByte & 0xff) > (rightByte & 0xff)) {
+ throw new IllegalArgumentException(
+ "Left byte array sorts after right row; left=" + ByteBufferUtils
+ .toStringBinary(left, leftOffset, leftLength) + ", right=" + ByteBufferUtils
+ .toStringBinary(right, rightOffset, rightLength));
+ } else if (leftByte != rightByte) {
+ break;
+ }
+ }
+ if (diffIdx == minLength) {
+ if (leftLength > rightLength) {
+ //right is prefix of left
+ throw new IllegalArgumentException(
+ "Left byte array sorts after right row; left=" + ByteBufferUtils
+ .toStringBinary(left, leftOffset, leftLength) + ", right=" + ByteBufferUtils
+ .toStringBinary(right, rightOffset, rightLength));
+ } else if (leftLength < rightLength) {
+ //left is prefix of right.
+ byte[] minimumMidpointArray = new byte[minLength + 1];
+ ByteBufferUtils
+ .copyFromBufferToArray(minimumMidpointArray, right, rightOffset, 0, minLength + 1);
+ minimumMidpointArray[minLength] = 0x00;
+ return minimumMidpointArray;
} else {
- minMidpoint = new byte[diffIdx + 1];
- ByteBufferUtils.copyFromBufferToArray(minMidpoint, right, rightOffset, 0, diffIdx + 1);
+ //left == right
+ return null;
}
}
- return minMidpoint;
+ //Note that left[diffIdx] can never be equal to 0xff since left < right
Review comment:
The logic of composing midPoint is basically the same, with some small differences
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [hbase] nyl3532016 commented on a change in pull request #2741: HBASE-25364 Redo the getMidPoint() in HFileWriterImpl to get rid of t…
Posted by GitBox <gi...@apache.org>.
nyl3532016 commented on a change in pull request #2741:
URL: https://github.com/apache/hbase/pull/2741#discussion_r537045604
##########
File path: hbase-server/src/main/java/org/apache/hadoop/hbase/io/hfile/HFileWriterImpl.java
##########
@@ -380,143 +378,146 @@ public static Cell getMidpoint(final CellComparator comparator, final Cell left,
if (comparator instanceof MetaCellComparator) {
return right;
}
- int diff = comparator.compareRows(left, right);
- if (diff > 0) {
- throw new IllegalArgumentException("Left row sorts after right row; left="
- + CellUtil.getCellKeyAsString(left) + ", right=" + CellUtil.getCellKeyAsString(right));
- }
byte[] midRow;
boolean bufferBacked = left instanceof ByteBufferExtendedCell
&& right instanceof ByteBufferExtendedCell;
- if (diff < 0) {
- // Left row is < right row.
- if (bufferBacked) {
- midRow = getMinimumMidpointArray(((ByteBufferExtendedCell) left).getRowByteBuffer(),
- ((ByteBufferExtendedCell) left).getRowPosition(), left.getRowLength(),
- ((ByteBufferExtendedCell) right).getRowByteBuffer(),
- ((ByteBufferExtendedCell) right).getRowPosition(), right.getRowLength());
- } else {
- midRow = getMinimumMidpointArray(left.getRowArray(), left.getRowOffset(),
- left.getRowLength(), right.getRowArray(), right.getRowOffset(), right.getRowLength());
- }
- // If midRow is null, just return 'right'. Can't do optimization.
- if (midRow == null) {
- return right;
- }
+ if (bufferBacked) {
+ midRow = getMinimumMidpointArray(((ByteBufferExtendedCell) left).getRowByteBuffer(),
+ ((ByteBufferExtendedCell) left).getRowPosition(), left.getRowLength(),
+ ((ByteBufferExtendedCell) right).getRowByteBuffer(),
+ ((ByteBufferExtendedCell) right).getRowPosition(), right.getRowLength());
+ } else {
+ midRow = getMinimumMidpointArray(left.getRowArray(), left.getRowOffset(), left.getRowLength(),
+ right.getRowArray(), right.getRowOffset(), right.getRowLength());
+ }
+ if (midRow != null) {
return PrivateCellUtil.createFirstOnRow(midRow);
}
- // Rows are same. Compare on families.
- diff = comparator.compareFamilies(left, right);
- if (diff > 0) {
- throw new IllegalArgumentException("Left family sorts after right family; left="
- + CellUtil.getCellKeyAsString(left) + ", right=" + CellUtil.getCellKeyAsString(right));
- }
- if (diff < 0) {
- if (bufferBacked) {
- midRow = getMinimumMidpointArray(((ByteBufferExtendedCell) left).getFamilyByteBuffer(),
- ((ByteBufferExtendedCell) left).getFamilyPosition(), left.getFamilyLength(),
- ((ByteBufferExtendedCell) right).getFamilyByteBuffer(),
- ((ByteBufferExtendedCell) right).getFamilyPosition(), right.getFamilyLength());
- } else {
- midRow = getMinimumMidpointArray(left.getFamilyArray(), left.getFamilyOffset(),
- left.getFamilyLength(), right.getFamilyArray(), right.getFamilyOffset(),
- right.getFamilyLength());
- }
- // If midRow is null, just return 'right'. Can't do optimization.
- if (midRow == null) {
- return right;
- }
- // Return new Cell where we use right row and then a mid sort family.
+ //Rows are same. Compare on families.
+ if (bufferBacked) {
+ midRow = getMinimumMidpointArray(((ByteBufferExtendedCell) left).getFamilyByteBuffer(),
+ ((ByteBufferExtendedCell) left).getFamilyPosition(), left.getFamilyLength(),
+ ((ByteBufferExtendedCell) right).getFamilyByteBuffer(),
+ ((ByteBufferExtendedCell) right).getFamilyPosition(), right.getFamilyLength());
+ } else {
+ midRow = getMinimumMidpointArray(left.getFamilyArray(), left.getFamilyOffset(),
+ left.getFamilyLength(), right.getFamilyArray(), right.getFamilyOffset(),
+ right.getFamilyLength());
+ }
+ if (midRow != null) {
return PrivateCellUtil.createFirstOnRowFamily(right, midRow, 0, midRow.length);
}
// Families are same. Compare on qualifiers.
- diff = comparator.compareQualifiers(left, right);
- if (diff > 0) {
- throw new IllegalArgumentException("Left qualifier sorts after right qualifier; left="
- + CellUtil.getCellKeyAsString(left) + ", right=" + CellUtil.getCellKeyAsString(right));
- }
- if (diff < 0) {
- if (bufferBacked) {
- midRow = getMinimumMidpointArray(((ByteBufferExtendedCell) left).getQualifierByteBuffer(),
- ((ByteBufferExtendedCell) left).getQualifierPosition(), left.getQualifierLength(),
- ((ByteBufferExtendedCell) right).getQualifierByteBuffer(),
- ((ByteBufferExtendedCell) right).getQualifierPosition(), right.getQualifierLength());
- } else {
- midRow = getMinimumMidpointArray(left.getQualifierArray(), left.getQualifierOffset(),
- left.getQualifierLength(), right.getQualifierArray(), right.getQualifierOffset(),
- right.getQualifierLength());
- }
- // If midRow is null, just return 'right'. Can't do optimization.
- if (midRow == null) {
- return right;
- }
- // Return new Cell where we use right row and family and then a mid sort qualifier.
+ if (bufferBacked) {
+ midRow = getMinimumMidpointArray(((ByteBufferExtendedCell) left).getQualifierByteBuffer(),
+ ((ByteBufferExtendedCell) left).getQualifierPosition(), left.getQualifierLength(),
+ ((ByteBufferExtendedCell) right).getQualifierByteBuffer(),
+ ((ByteBufferExtendedCell) right).getQualifierPosition(), right.getQualifierLength());
+ } else {
+ midRow = getMinimumMidpointArray(left.getQualifierArray(), left.getQualifierOffset(),
+ left.getQualifierLength(), right.getQualifierArray(), right.getQualifierOffset(),
+ right.getQualifierLength());
+ }
+ if (midRow != null) {
return PrivateCellUtil.createFirstOnRowCol(right, midRow, 0, midRow.length);
}
// No opportunity for optimization. Just return right key.
return right;
}
/**
+ * Try to get a byte array that falls between left and right as short as possible with
+ * lexicographical order;
+ *
* @return Return a new array that is between left and right and minimally
- * sized else just return null as indicator that we could not create a
- * mid point.
+ * sized else just return null if left == right.
*/
private static byte[] getMinimumMidpointArray(final byte[] leftArray, final int leftOffset,
final int leftLength, final byte[] rightArray, final int rightOffset, final int rightLength) {
- // rows are different
int minLength = leftLength < rightLength ? leftLength : rightLength;
int diffIdx = 0;
- while (diffIdx < minLength
- && leftArray[leftOffset + diffIdx] == rightArray[rightOffset + diffIdx]) {
- diffIdx++;
- }
- byte[] minimumMidpointArray = null;
- if (diffIdx >= minLength) {
- // leftKey's row is prefix of rightKey's.
- minimumMidpointArray = new byte[diffIdx + 1];
- System.arraycopy(rightArray, rightOffset, minimumMidpointArray, 0, diffIdx + 1);
- } else {
- int diffByte = leftArray[leftOffset + diffIdx];
- if ((0xff & diffByte) < 0xff && (diffByte + 1) < (rightArray[rightOffset + diffIdx] & 0xff)) {
- minimumMidpointArray = new byte[diffIdx + 1];
- System.arraycopy(leftArray, leftOffset, minimumMidpointArray, 0, diffIdx);
- minimumMidpointArray[diffIdx] = (byte) (diffByte + 1);
+ for (; diffIdx < minLength; diffIdx++) {
+ byte leftByte = leftArray[leftOffset + diffIdx];
+ byte rightByte = rightArray[rightOffset + diffIdx];
+ if ((leftByte & 0xff) > (rightByte & 0xff)) {
+ throw new IllegalArgumentException("Left byte array sorts after right row; left=" + Bytes
+ .toStringBinary(leftArray, leftOffset, leftLength) + ", right=" + Bytes
+ .toStringBinary(rightArray, rightOffset, rightLength));
+ } else if (leftByte != rightByte) {
+ break;
+ }
+ }
+ if (diffIdx == minLength) {
+ if (leftLength > rightLength) {
+ //right is prefix of left
+ throw new IllegalArgumentException("Left byte array sorts after right row; left=" + Bytes
+ .toStringBinary(leftArray, leftOffset, leftLength) + ", right=" + Bytes
+ .toStringBinary(rightArray, rightOffset, rightLength));
+ } else if (leftLength < rightLength) {
+ //left is prefix of right.
+ byte[] minimumMidpointArray = new byte[minLength + 1];
+ System.arraycopy(rightArray, rightOffset, minimumMidpointArray, 0, minLength + 1);
+ minimumMidpointArray[minLength] = 0x00;
+ return minimumMidpointArray;
} else {
- minimumMidpointArray = new byte[diffIdx + 1];
- System.arraycopy(rightArray, rightOffset, minimumMidpointArray, 0, diffIdx + 1);
+ //left == right
+ return null;
}
}
+ //Note that left[diffIdx] can never be equal to 0xff since left < right
+ byte[] minimumMidpointArray = new byte[diffIdx + 1];
+ System.arraycopy(leftArray, leftOffset, minimumMidpointArray, 0, diffIdx + 1);
+ minimumMidpointArray[diffIdx] = (byte) (minimumMidpointArray[diffIdx] + 1);
return minimumMidpointArray;
}
+ /**
+ * Try to create a new byte array that falls between left and right as short as possible with
+ * lexicographical order.
+ *
+ * @return Return a new array that is between left and right and minimally
+ * sized else just return null if left == right.
+ */
private static byte[] getMinimumMidpointArray(ByteBuffer left, int leftOffset, int leftLength,
ByteBuffer right, int rightOffset, int rightLength) {
- // rows are different
int minLength = leftLength < rightLength ? leftLength : rightLength;
int diffIdx = 0;
- while (diffIdx < minLength && ByteBufferUtils.toByte(left,
- leftOffset + diffIdx) == ByteBufferUtils.toByte(right, rightOffset + diffIdx)) {
- diffIdx++;
- }
- byte[] minMidpoint = null;
- if (diffIdx >= minLength) {
- // leftKey's row is prefix of rightKey's.
- minMidpoint = new byte[diffIdx + 1];
- ByteBufferUtils.copyFromBufferToArray(minMidpoint, right, rightOffset, 0, diffIdx + 1);
- } else {
- int diffByte = ByteBufferUtils.toByte(left, leftOffset + diffIdx);
- if ((0xff & diffByte) < 0xff
- && (diffByte + 1) < (ByteBufferUtils.toByte(right, rightOffset + diffIdx) & 0xff)) {
- minMidpoint = new byte[diffIdx + 1];
- ByteBufferUtils.copyFromBufferToArray(minMidpoint, left, leftOffset, 0, diffIdx);
- minMidpoint[diffIdx] = (byte) (diffByte + 1);
+ for (; diffIdx < minLength; diffIdx++) {
+ int leftByte = ByteBufferUtils.toByte(left, leftOffset + diffIdx);
+ int rightByte = ByteBufferUtils.toByte(right, rightOffset + diffIdx);
+ if ((leftByte & 0xff) > (rightByte & 0xff)) {
+ throw new IllegalArgumentException(
+ "Left byte array sorts after right row; left=" + ByteBufferUtils
+ .toStringBinary(left, leftOffset, leftLength) + ", right=" + ByteBufferUtils
+ .toStringBinary(right, rightOffset, rightLength));
+ } else if (leftByte != rightByte) {
+ break;
+ }
+ }
+ if (diffIdx == minLength) {
+ if (leftLength > rightLength) {
+ //right is prefix of left
+ throw new IllegalArgumentException(
+ "Left byte array sorts after right row; left=" + ByteBufferUtils
+ .toStringBinary(left, leftOffset, leftLength) + ", right=" + ByteBufferUtils
+ .toStringBinary(right, rightOffset, rightLength));
+ } else if (leftLength < rightLength) {
+ //left is prefix of right.
+ byte[] minimumMidpointArray = new byte[minLength + 1];
+ ByteBufferUtils
+ .copyFromBufferToArray(minimumMidpointArray, right, rightOffset, 0, minLength + 1);
+ minimumMidpointArray[minLength] = 0x00;
+ return minimumMidpointArray;
} else {
- minMidpoint = new byte[diffIdx + 1];
- ByteBufferUtils.copyFromBufferToArray(minMidpoint, right, rightOffset, 0, diffIdx + 1);
+ //left == right
+ return null;
}
}
- return minMidpoint;
+ //Note that left[diffIdx] can never be equal to 0xff since left < right
Review comment:
The logic here is different from original?
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [hbase] nyl3532016 commented on a change in pull request #2741: HBASE-25364 Redo the getMidPoint() in HFileWriterImpl to get rid of t…
Posted by GitBox <gi...@apache.org>.
nyl3532016 commented on a change in pull request #2741:
URL: https://github.com/apache/hbase/pull/2741#discussion_r542993866
##########
File path: hbase-server/src/main/java/org/apache/hadoop/hbase/io/hfile/HFileWriterImpl.java
##########
@@ -380,143 +378,146 @@ public static Cell getMidpoint(final CellComparator comparator, final Cell left,
if (comparator instanceof MetaCellComparator) {
return right;
}
- int diff = comparator.compareRows(left, right);
- if (diff > 0) {
- throw new IllegalArgumentException("Left row sorts after right row; left="
- + CellUtil.getCellKeyAsString(left) + ", right=" + CellUtil.getCellKeyAsString(right));
- }
byte[] midRow;
boolean bufferBacked = left instanceof ByteBufferExtendedCell
&& right instanceof ByteBufferExtendedCell;
- if (diff < 0) {
- // Left row is < right row.
- if (bufferBacked) {
- midRow = getMinimumMidpointArray(((ByteBufferExtendedCell) left).getRowByteBuffer(),
- ((ByteBufferExtendedCell) left).getRowPosition(), left.getRowLength(),
- ((ByteBufferExtendedCell) right).getRowByteBuffer(),
- ((ByteBufferExtendedCell) right).getRowPosition(), right.getRowLength());
- } else {
- midRow = getMinimumMidpointArray(left.getRowArray(), left.getRowOffset(),
- left.getRowLength(), right.getRowArray(), right.getRowOffset(), right.getRowLength());
- }
- // If midRow is null, just return 'right'. Can't do optimization.
- if (midRow == null) {
- return right;
- }
+ if (bufferBacked) {
+ midRow = getMinimumMidpointArray(((ByteBufferExtendedCell) left).getRowByteBuffer(),
+ ((ByteBufferExtendedCell) left).getRowPosition(), left.getRowLength(),
+ ((ByteBufferExtendedCell) right).getRowByteBuffer(),
+ ((ByteBufferExtendedCell) right).getRowPosition(), right.getRowLength());
+ } else {
+ midRow = getMinimumMidpointArray(left.getRowArray(), left.getRowOffset(), left.getRowLength(),
+ right.getRowArray(), right.getRowOffset(), right.getRowLength());
+ }
+ if (midRow != null) {
return PrivateCellUtil.createFirstOnRow(midRow);
}
- // Rows are same. Compare on families.
- diff = comparator.compareFamilies(left, right);
- if (diff > 0) {
- throw new IllegalArgumentException("Left family sorts after right family; left="
- + CellUtil.getCellKeyAsString(left) + ", right=" + CellUtil.getCellKeyAsString(right));
- }
- if (diff < 0) {
- if (bufferBacked) {
- midRow = getMinimumMidpointArray(((ByteBufferExtendedCell) left).getFamilyByteBuffer(),
- ((ByteBufferExtendedCell) left).getFamilyPosition(), left.getFamilyLength(),
- ((ByteBufferExtendedCell) right).getFamilyByteBuffer(),
- ((ByteBufferExtendedCell) right).getFamilyPosition(), right.getFamilyLength());
- } else {
- midRow = getMinimumMidpointArray(left.getFamilyArray(), left.getFamilyOffset(),
- left.getFamilyLength(), right.getFamilyArray(), right.getFamilyOffset(),
- right.getFamilyLength());
- }
- // If midRow is null, just return 'right'. Can't do optimization.
- if (midRow == null) {
- return right;
- }
- // Return new Cell where we use right row and then a mid sort family.
+ //Rows are same. Compare on families.
+ if (bufferBacked) {
+ midRow = getMinimumMidpointArray(((ByteBufferExtendedCell) left).getFamilyByteBuffer(),
+ ((ByteBufferExtendedCell) left).getFamilyPosition(), left.getFamilyLength(),
+ ((ByteBufferExtendedCell) right).getFamilyByteBuffer(),
+ ((ByteBufferExtendedCell) right).getFamilyPosition(), right.getFamilyLength());
+ } else {
+ midRow = getMinimumMidpointArray(left.getFamilyArray(), left.getFamilyOffset(),
+ left.getFamilyLength(), right.getFamilyArray(), right.getFamilyOffset(),
+ right.getFamilyLength());
+ }
+ if (midRow != null) {
return PrivateCellUtil.createFirstOnRowFamily(right, midRow, 0, midRow.length);
}
// Families are same. Compare on qualifiers.
- diff = comparator.compareQualifiers(left, right);
- if (diff > 0) {
- throw new IllegalArgumentException("Left qualifier sorts after right qualifier; left="
- + CellUtil.getCellKeyAsString(left) + ", right=" + CellUtil.getCellKeyAsString(right));
- }
- if (diff < 0) {
- if (bufferBacked) {
- midRow = getMinimumMidpointArray(((ByteBufferExtendedCell) left).getQualifierByteBuffer(),
- ((ByteBufferExtendedCell) left).getQualifierPosition(), left.getQualifierLength(),
- ((ByteBufferExtendedCell) right).getQualifierByteBuffer(),
- ((ByteBufferExtendedCell) right).getQualifierPosition(), right.getQualifierLength());
- } else {
- midRow = getMinimumMidpointArray(left.getQualifierArray(), left.getQualifierOffset(),
- left.getQualifierLength(), right.getQualifierArray(), right.getQualifierOffset(),
- right.getQualifierLength());
- }
- // If midRow is null, just return 'right'. Can't do optimization.
- if (midRow == null) {
- return right;
- }
- // Return new Cell where we use right row and family and then a mid sort qualifier.
+ if (bufferBacked) {
+ midRow = getMinimumMidpointArray(((ByteBufferExtendedCell) left).getQualifierByteBuffer(),
+ ((ByteBufferExtendedCell) left).getQualifierPosition(), left.getQualifierLength(),
+ ((ByteBufferExtendedCell) right).getQualifierByteBuffer(),
+ ((ByteBufferExtendedCell) right).getQualifierPosition(), right.getQualifierLength());
+ } else {
+ midRow = getMinimumMidpointArray(left.getQualifierArray(), left.getQualifierOffset(),
+ left.getQualifierLength(), right.getQualifierArray(), right.getQualifierOffset(),
+ right.getQualifierLength());
+ }
+ if (midRow != null) {
return PrivateCellUtil.createFirstOnRowCol(right, midRow, 0, midRow.length);
}
// No opportunity for optimization. Just return right key.
return right;
}
/**
+ * Try to get a byte array that falls between left and right as short as possible with
+ * lexicographical order;
+ *
* @return Return a new array that is between left and right and minimally
- * sized else just return null as indicator that we could not create a
- * mid point.
+ * sized else just return null if left == right.
*/
private static byte[] getMinimumMidpointArray(final byte[] leftArray, final int leftOffset,
final int leftLength, final byte[] rightArray, final int rightOffset, final int rightLength) {
- // rows are different
int minLength = leftLength < rightLength ? leftLength : rightLength;
int diffIdx = 0;
- while (diffIdx < minLength
- && leftArray[leftOffset + diffIdx] == rightArray[rightOffset + diffIdx]) {
- diffIdx++;
- }
- byte[] minimumMidpointArray = null;
- if (diffIdx >= minLength) {
- // leftKey's row is prefix of rightKey's.
- minimumMidpointArray = new byte[diffIdx + 1];
- System.arraycopy(rightArray, rightOffset, minimumMidpointArray, 0, diffIdx + 1);
- } else {
- int diffByte = leftArray[leftOffset + diffIdx];
- if ((0xff & diffByte) < 0xff && (diffByte + 1) < (rightArray[rightOffset + diffIdx] & 0xff)) {
- minimumMidpointArray = new byte[diffIdx + 1];
- System.arraycopy(leftArray, leftOffset, minimumMidpointArray, 0, diffIdx);
- minimumMidpointArray[diffIdx] = (byte) (diffByte + 1);
+ for (; diffIdx < minLength; diffIdx++) {
+ byte leftByte = leftArray[leftOffset + diffIdx];
+ byte rightByte = rightArray[rightOffset + diffIdx];
+ if ((leftByte & 0xff) > (rightByte & 0xff)) {
+ throw new IllegalArgumentException("Left byte array sorts after right row; left=" + Bytes
+ .toStringBinary(leftArray, leftOffset, leftLength) + ", right=" + Bytes
+ .toStringBinary(rightArray, rightOffset, rightLength));
+ } else if (leftByte != rightByte) {
+ break;
+ }
+ }
+ if (diffIdx == minLength) {
+ if (leftLength > rightLength) {
+ //right is prefix of left
+ throw new IllegalArgumentException("Left byte array sorts after right row; left=" + Bytes
+ .toStringBinary(leftArray, leftOffset, leftLength) + ", right=" + Bytes
+ .toStringBinary(rightArray, rightOffset, rightLength));
+ } else if (leftLength < rightLength) {
+ //left is prefix of right.
+ byte[] minimumMidpointArray = new byte[minLength + 1];
+ System.arraycopy(rightArray, rightOffset, minimumMidpointArray, 0, minLength + 1);
+ minimumMidpointArray[minLength] = 0x00;
+ return minimumMidpointArray;
} else {
- minimumMidpointArray = new byte[diffIdx + 1];
- System.arraycopy(rightArray, rightOffset, minimumMidpointArray, 0, diffIdx + 1);
+ //left == right
+ return null;
}
}
+ //Note that left[diffIdx] can never be equal to 0xff since left < right
+ byte[] minimumMidpointArray = new byte[diffIdx + 1];
+ System.arraycopy(leftArray, leftOffset, minimumMidpointArray, 0, diffIdx + 1);
+ minimumMidpointArray[diffIdx] = (byte) (minimumMidpointArray[diffIdx] + 1);
return minimumMidpointArray;
}
+ /**
+ * Try to create a new byte array that falls between left and right as short as possible with
+ * lexicographical order.
+ *
+ * @return Return a new array that is between left and right and minimally
+ * sized else just return null if left == right.
+ */
private static byte[] getMinimumMidpointArray(ByteBuffer left, int leftOffset, int leftLength,
ByteBuffer right, int rightOffset, int rightLength) {
- // rows are different
int minLength = leftLength < rightLength ? leftLength : rightLength;
int diffIdx = 0;
- while (diffIdx < minLength && ByteBufferUtils.toByte(left,
- leftOffset + diffIdx) == ByteBufferUtils.toByte(right, rightOffset + diffIdx)) {
- diffIdx++;
- }
- byte[] minMidpoint = null;
- if (diffIdx >= minLength) {
- // leftKey's row is prefix of rightKey's.
- minMidpoint = new byte[diffIdx + 1];
- ByteBufferUtils.copyFromBufferToArray(minMidpoint, right, rightOffset, 0, diffIdx + 1);
- } else {
- int diffByte = ByteBufferUtils.toByte(left, leftOffset + diffIdx);
- if ((0xff & diffByte) < 0xff
- && (diffByte + 1) < (ByteBufferUtils.toByte(right, rightOffset + diffIdx) & 0xff)) {
- minMidpoint = new byte[diffIdx + 1];
- ByteBufferUtils.copyFromBufferToArray(minMidpoint, left, leftOffset, 0, diffIdx);
- minMidpoint[diffIdx] = (byte) (diffByte + 1);
+ for (; diffIdx < minLength; diffIdx++) {
+ int leftByte = ByteBufferUtils.toByte(left, leftOffset + diffIdx);
+ int rightByte = ByteBufferUtils.toByte(right, rightOffset + diffIdx);
+ if ((leftByte & 0xff) > (rightByte & 0xff)) {
+ throw new IllegalArgumentException(
+ "Left byte array sorts after right row; left=" + ByteBufferUtils
+ .toStringBinary(left, leftOffset, leftLength) + ", right=" + ByteBufferUtils
+ .toStringBinary(right, rightOffset, rightLength));
+ } else if (leftByte != rightByte) {
+ break;
+ }
+ }
+ if (diffIdx == minLength) {
+ if (leftLength > rightLength) {
+ //right is prefix of left
+ throw new IllegalArgumentException(
+ "Left byte array sorts after right row; left=" + ByteBufferUtils
+ .toStringBinary(left, leftOffset, leftLength) + ", right=" + ByteBufferUtils
+ .toStringBinary(right, rightOffset, rightLength));
+ } else if (leftLength < rightLength) {
+ //left is prefix of right.
+ byte[] minimumMidpointArray = new byte[minLength + 1];
+ ByteBufferUtils
+ .copyFromBufferToArray(minimumMidpointArray, right, rightOffset, 0, minLength + 1);
+ minimumMidpointArray[minLength] = 0x00;
+ return minimumMidpointArray;
} else {
- minMidpoint = new byte[diffIdx + 1];
- ByteBufferUtils.copyFromBufferToArray(minMidpoint, right, rightOffset, 0, diffIdx + 1);
+ //left == right
+ return null;
}
}
- return minMidpoint;
+ //Note that left[diffIdx] can never be equal to 0xff since left < right
Review comment:
`(diffByte + 1) < (ByteBufferUtils.toByte(right, rightOffset + diffIdx) & 0xff)`
I think this logical branch is lost
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org