You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by kr...@apache.org on 2016/10/20 19:31:33 UTC
[24/50] [abbrv] lucene-solr:jira/solr-8593: LUCENE-7501: BKDReader
should not store the split dimension explicitly in the 1D case.
LUCENE-7501: BKDReader should not store the split dimension explicitly in the 1D case.
Project: http://git-wip-us.apache.org/repos/asf/lucene-solr/repo
Commit: http://git-wip-us.apache.org/repos/asf/lucene-solr/commit/e8360714
Tree: http://git-wip-us.apache.org/repos/asf/lucene-solr/tree/e8360714
Diff: http://git-wip-us.apache.org/repos/asf/lucene-solr/diff/e8360714
Branch: refs/heads/jira/solr-8593
Commit: e8360714fae8bac3c705297641a735ed33cf47f9
Parents: b2188f4
Author: Adrien Grand <jp...@gmail.com>
Authored: Tue Oct 18 09:33:36 2016 +0200
Committer: Adrien Grand <jp...@gmail.com>
Committed: Tue Oct 18 15:05:50 2016 +0200
----------------------------------------------------------------------
lucene/CHANGES.txt | 3 ++
.../simpletext/SimpleTextPointsReader.java | 17 +++++++++--
.../org/apache/lucene/util/bkd/BKDReader.java | 32 +++++++++++---------
.../org/apache/lucene/util/bkd/BKDWriter.java | 14 ++++++---
4 files changed, 45 insertions(+), 21 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/e8360714/lucene/CHANGES.txt
----------------------------------------------------------------------
diff --git a/lucene/CHANGES.txt b/lucene/CHANGES.txt
index f3501cc..745d8fd 100644
--- a/lucene/CHANGES.txt
+++ b/lucene/CHANGES.txt
@@ -96,6 +96,9 @@ Improvements
Optimizations
+* LUCENE-7501: BKDReader should not store the split dimension explicitly in the
+ 1D case. (Adrien Grand)
+
Other
* LUCENE-7452: Block join query exception suggests how to find a doc, which
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/e8360714/lucene/codecs/src/java/org/apache/lucene/codecs/simpletext/SimpleTextPointsReader.java
----------------------------------------------------------------------
diff --git a/lucene/codecs/src/java/org/apache/lucene/codecs/simpletext/SimpleTextPointsReader.java b/lucene/codecs/src/java/org/apache/lucene/codecs/simpletext/SimpleTextPointsReader.java
index e3b880a..f7ff16e 100644
--- a/lucene/codecs/src/java/org/apache/lucene/codecs/simpletext/SimpleTextPointsReader.java
+++ b/lucene/codecs/src/java/org/apache/lucene/codecs/simpletext/SimpleTextPointsReader.java
@@ -139,15 +139,26 @@ class SimpleTextPointsReader extends PointsReader {
readLine(dataIn);
count = parseInt(SPLIT_COUNT);
- byte[] splitPackedValues = new byte[count * (1 + bytesPerDim)];
+ byte[] splitPackedValues;
+ int bytesPerIndexEntry;
+ if (numDims == 1) {
+ bytesPerIndexEntry = bytesPerDim;
+ } else {
+ bytesPerIndexEntry = 1 + bytesPerDim;
+ }
+ splitPackedValues = new byte[count * bytesPerIndexEntry];
for(int i=0;i<count;i++) {
readLine(dataIn);
- splitPackedValues[(1 + bytesPerDim) * i] = (byte) parseInt(SPLIT_DIM);
+ int address = bytesPerIndexEntry * i;
+ int splitDim = parseInt(SPLIT_DIM);
+ if (numDims != 1) {
+ splitPackedValues[address++] = (byte) splitDim;
+ }
readLine(dataIn);
assert startsWith(SPLIT_VALUE);
BytesRef br = SimpleTextUtil.fromBytesRefString(stripPrefix(SPLIT_VALUE));
assert br.length == bytesPerDim;
- System.arraycopy(br.bytes, br.offset, splitPackedValues, (1 + bytesPerDim) * i + 1, bytesPerDim);
+ System.arraycopy(br.bytes, br.offset, splitPackedValues, address, bytesPerDim);
}
return new SimpleTextBKDReader(dataIn, numDims, maxPointsInLeafNode, bytesPerDim, leafBlockFPs, splitPackedValues, minValue.bytes, maxValue.bytes, pointCount, docCount);
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/e8360714/lucene/core/src/java/org/apache/lucene/util/bkd/BKDReader.java
----------------------------------------------------------------------
diff --git a/lucene/core/src/java/org/apache/lucene/util/bkd/BKDReader.java b/lucene/core/src/java/org/apache/lucene/util/bkd/BKDReader.java
index 0fe549a..1ddb566 100644
--- a/lucene/core/src/java/org/apache/lucene/util/bkd/BKDReader.java
+++ b/lucene/core/src/java/org/apache/lucene/util/bkd/BKDReader.java
@@ -25,6 +25,7 @@ import org.apache.lucene.index.PointValues;
import org.apache.lucene.store.IndexInput;
import org.apache.lucene.util.Accountable;
import org.apache.lucene.util.BytesRef;
+import org.apache.lucene.util.RamUsageEstimator;
import org.apache.lucene.util.StringHelper;
/** Handles intersection of an multi-dimensional shape in byte[] space with a block KD-tree previously written with {@link BKDWriter}.
@@ -38,6 +39,7 @@ public class BKDReader extends PointValues implements Accountable {
final private int leafNodeOffset;
final int numDims;
final int bytesPerDim;
+ final int bytesPerIndexEntry;
final IndexInput in;
final int maxPointsInLeafNode;
final byte[] minPackedValue;
@@ -53,6 +55,7 @@ public class BKDReader extends PointValues implements Accountable {
numDims = in.readVInt();
maxPointsInLeafNode = in.readVInt();
bytesPerDim = in.readVInt();
+ bytesPerIndexEntry = numDims == 1 && version >= BKDWriter.VERSION_IMPLICIT_SPLIT_DIM_1D ? bytesPerDim : bytesPerDim + 1;
packedBytesLength = numDims * bytesPerDim;
// Read index:
@@ -69,7 +72,7 @@ public class BKDReader extends PointValues implements Accountable {
pointCount = in.readVLong();
docCount = in.readVInt();
- splitPackedValues = new byte[(1+bytesPerDim)*numLeaves];
+ splitPackedValues = new byte[bytesPerIndexEntry*numLeaves];
// TODO: don't write split packed values[0]!
in.readBytes(splitPackedValues, 0, splitPackedValues.length);
@@ -134,6 +137,7 @@ public class BKDReader extends PointValues implements Accountable {
this.numDims = numDims;
this.maxPointsInLeafNode = maxPointsInLeafNode;
this.bytesPerDim = bytesPerDim;
+ bytesPerIndexEntry = numDims == 1 ? bytesPerDim : bytesPerDim + 1;
packedBytesLength = numDims * bytesPerDim;
this.leafNodeOffset = leafBlockFPs.length;
this.leafBlockFPs = leafBlockFPs;
@@ -233,22 +237,22 @@ public class BKDReader extends PointValues implements Accountable {
} else {
// Non-leaf node:
- int address = nodeID * (bytesPerDim+1);
- int splitDim = splitPackedValues[address] & 0xff;
+ int address = nodeID * bytesPerIndexEntry;
+ int splitDim = numDims == 1 ? 0 : splitPackedValues[address++] & 0xff;
assert splitDim < numDims;
byte[] splitPackedValue = new byte[packedBytesLength];
// Recurse on left sub-tree:
System.arraycopy(cellMaxPacked, 0, splitPackedValue, 0, packedBytesLength);
- System.arraycopy(splitPackedValues, address+1, splitPackedValue, splitDim*bytesPerDim, bytesPerDim);
+ System.arraycopy(splitPackedValues, address, splitPackedValue, splitDim*bytesPerDim, bytesPerDim);
verify(state,
2*nodeID,
cellMinPacked, splitPackedValue);
// Recurse on right sub-tree:
System.arraycopy(cellMinPacked, 0, splitPackedValue, 0, packedBytesLength);
- System.arraycopy(splitPackedValues, address+1, splitPackedValue, splitDim*bytesPerDim, bytesPerDim);
+ System.arraycopy(splitPackedValues, address, splitPackedValue, splitDim*bytesPerDim, bytesPerDim);
verify(state,
2*nodeID+1,
splitPackedValue, cellMaxPacked);
@@ -456,8 +460,8 @@ public class BKDReader extends PointValues implements Accountable {
// Non-leaf node: recurse on the split left and right nodes
// TODO: save the unused 1 byte prefix (it's always 0) in the 1d case here:
- int address = nodeID * (bytesPerDim+1);
- int splitDim = splitPackedValues[address] & 0xff;
+ int address = nodeID * bytesPerIndexEntry;
+ int splitDim = numDims == 1 ? 0 : splitPackedValues[address++] & 0xff;
assert splitDim < numDims;
// TODO: can we alloc & reuse this up front?
@@ -467,14 +471,14 @@ public class BKDReader extends PointValues implements Accountable {
// Recurse on left sub-tree:
System.arraycopy(cellMaxPacked, 0, splitPackedValue, 0, packedBytesLength);
- System.arraycopy(splitPackedValues, address+1, splitPackedValue, splitDim*bytesPerDim, bytesPerDim);
+ System.arraycopy(splitPackedValues, address, splitPackedValue, splitDim*bytesPerDim, bytesPerDim);
intersect(state,
2*nodeID,
cellMinPacked, splitPackedValue);
// Recurse on right sub-tree:
System.arraycopy(cellMinPacked, 0, splitPackedValue, 0, packedBytesLength);
- System.arraycopy(splitPackedValues, address+1, splitPackedValue, splitDim*bytesPerDim, bytesPerDim);
+ System.arraycopy(splitPackedValues, address, splitPackedValue, splitDim*bytesPerDim, bytesPerDim);
intersect(state,
2*nodeID+1,
splitPackedValue, cellMaxPacked);
@@ -483,16 +487,16 @@ public class BKDReader extends PointValues implements Accountable {
/** Copies the split value for this node into the provided byte array */
public void copySplitValue(int nodeID, byte[] splitPackedValue) {
- int address = nodeID * (bytesPerDim+1);
- int splitDim = splitPackedValues[address] & 0xff;
+ int address = nodeID * bytesPerIndexEntry;
+ int splitDim = numDims == 1 ? 0 : splitPackedValues[address++] & 0xff;
assert splitDim < numDims;
- System.arraycopy(splitPackedValues, address+1, splitPackedValue, splitDim*bytesPerDim, bytesPerDim);
+ System.arraycopy(splitPackedValues, address, splitPackedValue, splitDim*bytesPerDim, bytesPerDim);
}
@Override
public long ramBytesUsed() {
- return splitPackedValues.length +
- leafBlockFPs.length * Long.BYTES;
+ return RamUsageEstimator.sizeOf(splitPackedValues) +
+ RamUsageEstimator.sizeOf(leafBlockFPs);
}
@Override
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/e8360714/lucene/core/src/java/org/apache/lucene/util/bkd/BKDWriter.java
----------------------------------------------------------------------
diff --git a/lucene/core/src/java/org/apache/lucene/util/bkd/BKDWriter.java b/lucene/core/src/java/org/apache/lucene/util/bkd/BKDWriter.java
index 6ee178b..5526624 100644
--- a/lucene/core/src/java/org/apache/lucene/util/bkd/BKDWriter.java
+++ b/lucene/core/src/java/org/apache/lucene/util/bkd/BKDWriter.java
@@ -82,7 +82,8 @@ public class BKDWriter implements Closeable {
public static final int VERSION_START = 0;
public static final int VERSION_COMPRESSED_DOC_IDS = 1;
public static final int VERSION_COMPRESSED_VALUES = 2;
- public static final int VERSION_CURRENT = VERSION_COMPRESSED_VALUES;
+ public static final int VERSION_IMPLICIT_SPLIT_DIM_1D = 3;
+ public static final int VERSION_CURRENT = VERSION_IMPLICIT_SPLIT_DIM_1D;
/** How many bytes each docs takes in the fixed-width offline format */
private final int bytesPerDoc;
@@ -1033,10 +1034,15 @@ public class BKDWriter implements Closeable {
out.writeVLong(pointCount);
out.writeVInt(docsSeen.cardinality());
- // TODO: for 1D case, don't waste the first byte of each split value (it's always 0)
-
// NOTE: splitPackedValues[0] is unused, because nodeID is 1-based:
- out.writeBytes(splitPackedValues, 0, splitPackedValues.length);
+ if (numDims == 1) {
+ // write the index, skipping the byte used to store the split dim since it is always 0
+ for (int i = 1; i < splitPackedValues.length; i += 1 + bytesPerDim) {
+ out.writeBytes(splitPackedValues, i, bytesPerDim);
+ }
+ } else {
+ out.writeBytes(splitPackedValues, 0, splitPackedValues.length);
+ }
long lastFP = 0;
for (int i=0;i<leafBlockFPs.length;i++) {