You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@phoenix.apache.org by la...@apache.org on 2015/09/06 07:05:00 UTC
phoenix git commit: PHOENIX-2237 Optimiza search comparator in
KeyValyeUtil.
Repository: phoenix
Updated Branches:
refs/heads/master 4b9e740ef -> b3c05bfd6
PHOENIX-2237 Optimiza search comparator in KeyValyeUtil.
Project: http://git-wip-us.apache.org/repos/asf/phoenix/repo
Commit: http://git-wip-us.apache.org/repos/asf/phoenix/commit/b3c05bfd
Tree: http://git-wip-us.apache.org/repos/asf/phoenix/tree/b3c05bfd
Diff: http://git-wip-us.apache.org/repos/asf/phoenix/diff/b3c05bfd
Branch: refs/heads/master
Commit: b3c05bfd6a331a5d11e4d872dafbead108df3bf0
Parents: 4b9e740
Author: Lars Hofhansl <la...@apache.org>
Authored: Sat Sep 5 22:06:40 2015 -0700
Committer: Lars Hofhansl <la...@apache.org>
Committed: Sat Sep 5 22:06:40 2015 -0700
----------------------------------------------------------------------
.../org/apache/phoenix/util/KeyValueUtil.java | 91 ++++++--------------
1 file changed, 24 insertions(+), 67 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/phoenix/blob/b3c05bfd/phoenix-core/src/main/java/org/apache/phoenix/util/KeyValueUtil.java
----------------------------------------------------------------------
diff --git a/phoenix-core/src/main/java/org/apache/phoenix/util/KeyValueUtil.java b/phoenix-core/src/main/java/org/apache/phoenix/util/KeyValueUtil.java
index 3850ca9..b8850d2 100644
--- a/phoenix-core/src/main/java/org/apache/phoenix/util/KeyValueUtil.java
+++ b/phoenix-core/src/main/java/org/apache/phoenix/util/KeyValueUtil.java
@@ -23,6 +23,7 @@ import java.util.Comparator;
import java.util.List;
import org.apache.hadoop.hbase.Cell;
+import org.apache.hadoop.hbase.CellUtil;
import org.apache.hadoop.hbase.KeyValue;
import org.apache.hadoop.hbase.KeyValue.KVComparator;
import org.apache.hadoop.hbase.KeyValue.Type;
@@ -92,30 +93,15 @@ public class KeyValueUtil {
if (kvs.size() == 0) {
return null;
}
- Cell row = kvs.get(0);
- Comparator<Cell> comp = new SearchComparator(kvBuilder,
- row.getRowArray(), row.getRowOffset(), row.getRowLength(), family, qualifier);
- // pos === ( -(insertion point) - 1)
+ assert CellUtil.matchingRow(kvs.get(0), kvs.get(kvs.size()-1));
+
+ Comparator<Cell> comp = new SearchComparator(kvBuilder, family, qualifier);
int pos = Collections.binarySearch(kvs, null, comp);
- // never will exact match
- if (pos < 0) {
- pos = (pos+1) * -1;
- // pos is now insertion point
- }
- if (pos == kvs.size()) {
+ if (pos < 0 || pos == kvs.size()) {
return null; // doesn't exist
}
- Cell kv = kvs.get(pos);
- if (Bytes.compareTo(kv.getFamilyArray(), kv.getFamilyOffset(), kv.getFamilyLength(),
- family, 0, family.length) != 0) {
- return null;
- }
- if (Bytes.compareTo(kv.getQualifierArray(), kv.getQualifierOffset(), kv.getQualifierLength(),
- qualifier, 0, qualifier.length) != 0) {
- return null;
- }
- return kv;
+ return kvs.get(pos);
}
@@ -130,79 +116,50 @@ public class KeyValueUtil {
if (kvs.length == 0) {
return null;
}
- Cell kvForRow = kvs[0];
- Comparator<Cell> comp = new SearchComparator(kvBuilder, kvForRow.getRowArray(),
- kvForRow.getRowOffset(), kvForRow.getRowLength(), family, qualifier);
- // pos === ( -(insertion point) - 1)
+ assert CellUtil.matchingRow(kvs[0], kvs[kvs.length-1]);
+
+ Comparator<Cell> comp = new SearchComparator(kvBuilder, family, qualifier);
int pos = Arrays.binarySearch(kvs, null, comp);
- // never will exact match
- if (pos < 0) {
- pos = (pos+1) * -1;
- // pos is now insertion point
- }
- if (pos == kvs.length) {
+ if (pos < 0 || pos == kvs.length) {
return null; // doesn't exist
}
- Cell kv = kvs[pos];
- if (Bytes.compareTo(kv.getFamilyArray(), kv.getFamilyOffset(), kv.getFamilyLength(),
- family, 0, family.length) != 0) {
- return null;
- }
- if (Bytes.compareTo(kv.getQualifierArray(), kv.getQualifierOffset(), kv.getQualifierLength(),
- qualifier, 0, qualifier.length) != 0) {
- return null;
- }
- return kv;
+ return kvs[pos];
}
/*
* Special comparator, *only* works for binary search.
- * Current JDKs only uses the search term on the right side,
- * Making use of that saves instanceof checks, and allows us
- * to inline the search term in the comparator
+ *
+ * We make the following assumption:
+ * 1. All KVs compared have the same row key
+ * 2. For each (rowkey, family, qualifier) there is at most one version
+ * 3. Current JDKs only uses the search term on the right side
+ *
+ * #1 allows us to avoid row key comparisons altogether.
+ * #2 allows for exact matches
+ * #3 lets us save instanceof checks, and allows to inline the search term in the comparator
*/
private static class SearchComparator implements Comparator<Cell> {
private final KeyValueBuilder kvBuilder;
- private final byte[] row;
private final byte[] family;
private final byte[] qualifier;
- private final int rowOff;
- private final int rowLen;
- public SearchComparator(KeyValueBuilder kvBuilder, byte[] r, int rOff, int rLen, byte[] f, byte[] q) {
+ public SearchComparator(KeyValueBuilder kvBuilder, byte[] f, byte[] q) {
this.kvBuilder = kvBuilder;
- row = r;
family = f;
qualifier = q;
- rowOff = rOff;
- rowLen = rLen;
}
- @Override
+ @Override
public int compare(final Cell l, final Cell ignored) {
assert ignored == null;
- KVComparator comparator = kvBuilder.getKeyValueComparator();
- // row
- int val = comparator.compareRows(l.getRowArray(), l.getRowOffset(),
- l.getRowLength(), row, rowOff, rowLen);
- if (val != 0) {
- return val;
- }
// family
- val = kvBuilder.compareFamily(l, family, 0, family.length);
+ int val = kvBuilder.compareFamily(l, family, 0, family.length);
if (val != 0) {
return val;
}
// qualifier
- val = kvBuilder.compareQualifier(l, qualifier, 0, qualifier.length);
- if (val != 0) {
- return val;
- }
- // We want the latest TS and type, so we get the first one.
- // This assumes they KV are passed in ordered from latest to earliest,
- // as that's the order the server sends them.
- return 1;
+ return kvBuilder.compareQualifier(l, qualifier, 0, qualifier.length);
}
}
}