You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by ab...@apache.org on 2016/12/13 20:30:20 UTC
[13/42] lucene-solr:feature/metrics: LUCENE-7563: use a compressed
format for the in-heap BKD index
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/5e8db2e0/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 5526624..c82a0c8 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
@@ -33,6 +33,7 @@ import org.apache.lucene.store.ChecksumIndexInput;
import org.apache.lucene.store.Directory;
import org.apache.lucene.store.IOContext;
import org.apache.lucene.store.IndexOutput;
+import org.apache.lucene.store.RAMOutputStream;
import org.apache.lucene.store.TrackingDirectoryWrapper;
import org.apache.lucene.util.ArrayUtil;
import org.apache.lucene.util.BytesRef;
@@ -83,7 +84,8 @@ public class BKDWriter implements Closeable {
public static final int VERSION_COMPRESSED_DOC_IDS = 1;
public static final int VERSION_COMPRESSED_VALUES = 2;
public static final int VERSION_IMPLICIT_SPLIT_DIM_1D = 3;
- public static final int VERSION_CURRENT = VERSION_IMPLICIT_SPLIT_DIM_1D;
+ public static final int VERSION_PACKED_INDEX = 4;
+ public static final int VERSION_CURRENT = VERSION_PACKED_INDEX;
/** How many bytes each docs takes in the fixed-width offline format */
private final int bytesPerDoc;
@@ -325,15 +327,10 @@ public class BKDWriter implements Closeable {
bkd.numDims,
bkd.packedBytesLength,
bkd.maxPointsInLeafNode,
+ null,
null);
this.docMap = docMap;
- long minFP = Long.MAX_VALUE;
- //System.out.println("MR.init " + this + " bkdreader=" + bkd + " leafBlockFPs.length=" + bkd.leafBlockFPs.length);
- for(long fp : bkd.leafBlockFPs) {
- minFP = Math.min(minFP, fp);
- //System.out.println(" leaf fp=" + fp);
- }
- state.in.seek(minFP);
+ state.in.seek(bkd.getMinLeafBlockFP());
this.packedValues = new byte[bkd.maxPointsInLeafNode * bkd.packedBytesLength];
}
@@ -341,7 +338,7 @@ public class BKDWriter implements Closeable {
//System.out.println("MR.next this=" + this);
while (true) {
if (docBlockUpto == docsInBlock) {
- if (blockID == bkd.leafBlockFPs.length) {
+ if (blockID == bkd.leafNodeOffset) {
//System.out.println(" done!");
return false;
}
@@ -489,7 +486,6 @@ public class BKDWriter implements Closeable {
return indexFP;
}
-
/* In the 1D case, we can simply sort points in ascending order and use the
* same writing logic as we use at merge time. */
private long writeField1Dim(IndexOutput out, String fieldName, MutablePointValues reader) throws IOException {
@@ -648,6 +644,7 @@ public class BKDWriter implements Closeable {
}
private void writeLeafBlock() throws IOException {
+ //System.out.println("writeLeafBlock pos=" + out.getFilePointer());
assert leafCount != 0;
if (valueCount == 0) {
System.arraycopy(leafValues, 0, minPackedValue, 0, packedBytesLength);
@@ -811,6 +808,24 @@ public class BKDWriter implements Closeable {
}.sort(0, pointCount);
}
+ // useful for debugging:
+ /*
+ private void printPathSlice(String desc, PathSlice slice, int dim) throws IOException {
+ System.out.println(" " + desc + " dim=" + dim + " count=" + slice.count + ":");
+ try(PointReader r = slice.writer.getReader(slice.start, slice.count)) {
+ int count = 0;
+ while (r.next()) {
+ byte[] v = r.packedValue();
+ System.out.println(" " + count + ": " + new BytesRef(v, dim*bytesPerDim, bytesPerDim));
+ count++;
+ if (count == slice.count) {
+ break;
+ }
+ }
+ }
+ }
+ */
+
private PointWriter sort(int dim) throws IOException {
assert dim >= 0 && dim < numDims;
@@ -1019,46 +1034,238 @@ public class BKDWriter implements Closeable {
return indexFP;
}
- /** Subclass can change how it writes the index. */
- protected void writeIndex(IndexOutput out, long[] leafBlockFPs, byte[] splitPackedValues) throws IOException {
+ /** Packs the two arrays, representing a balanced binary tree, into a compact byte[] structure. */
+ private byte[] packIndex(long[] leafBlockFPs, byte[] splitPackedValues) throws IOException {
+
+ int numLeaves = leafBlockFPs.length;
+
+ // Possibly rotate the leaf block FPs, if the index not fully balanced binary tree (only happens
+ // if it was created by OneDimensionBKDWriter). In this case the leaf nodes may straddle the two bottom
+ // levels of the binary tree:
+ if (numDims == 1 && numLeaves > 1) {
+ int levelCount = 2;
+ while (true) {
+ if (numLeaves >= levelCount && numLeaves <= 2*levelCount) {
+ int lastLevel = 2*(numLeaves - levelCount);
+ assert lastLevel >= 0;
+ if (lastLevel != 0) {
+ // Last level is partially filled, so we must rotate the leaf FPs to match. We do this here, after loading
+ // at read-time, so that we can still delta code them on disk at write:
+ long[] newLeafBlockFPs = new long[numLeaves];
+ System.arraycopy(leafBlockFPs, lastLevel, newLeafBlockFPs, 0, leafBlockFPs.length - lastLevel);
+ System.arraycopy(leafBlockFPs, 0, newLeafBlockFPs, leafBlockFPs.length - lastLevel, lastLevel);
+ leafBlockFPs = newLeafBlockFPs;
+ }
+ break;
+ }
+
+ levelCount *= 2;
+ }
+ }
+
+ /** Reused while packing the index */
+ RAMOutputStream writeBuffer = new RAMOutputStream();
+
+ // This is the "file" we append the byte[] to:
+ List<byte[]> blocks = new ArrayList<>();
+ byte[] lastSplitValues = new byte[bytesPerDim * numDims];
+ //System.out.println("\npack index");
+ int totalSize = recursePackIndex(writeBuffer, leafBlockFPs, splitPackedValues, 0l, blocks, 1, lastSplitValues, new boolean[numDims], false);
+
+ // Compact the byte[] blocks into single byte index:
+ byte[] index = new byte[totalSize];
+ int upto = 0;
+ for(byte[] block : blocks) {
+ System.arraycopy(block, 0, index, upto, block.length);
+ upto += block.length;
+ }
+ assert upto == totalSize;
+
+ return index;
+ }
+
+ /** Appends the current contents of writeBuffer as another block on the growing in-memory file */
+ private int appendBlock(RAMOutputStream writeBuffer, List<byte[]> blocks) throws IOException {
+ int pos = Math.toIntExact(writeBuffer.getFilePointer());
+ byte[] bytes = new byte[pos];
+ writeBuffer.writeTo(bytes, 0);
+ writeBuffer.reset();
+ blocks.add(bytes);
+ return pos;
+ }
+
+ /**
+ * lastSplitValues is per-dimension split value previously seen; we use this to prefix-code the split byte[] on each inner node
+ */
+ private int recursePackIndex(RAMOutputStream writeBuffer, long[] leafBlockFPs, byte[] splitPackedValues, long minBlockFP, List<byte[]> blocks,
+ int nodeID, byte[] lastSplitValues, boolean[] negativeDeltas, boolean isLeft) throws IOException {
+ if (nodeID >= leafBlockFPs.length) {
+ int leafID = nodeID - leafBlockFPs.length;
+ //System.out.println("recursePack leaf nodeID=" + nodeID);
+
+ // In the unbalanced case it's possible the left most node only has one child:
+ if (leafID < leafBlockFPs.length) {
+ long delta = leafBlockFPs[leafID] - minBlockFP;
+ if (isLeft) {
+ assert delta == 0;
+ return 0;
+ } else {
+ assert nodeID == 1 || delta > 0: "nodeID=" + nodeID;
+ writeBuffer.writeVLong(delta);
+ return appendBlock(writeBuffer, blocks);
+ }
+ } else {
+ return 0;
+ }
+ } else {
+ long leftBlockFP;
+ if (isLeft == false) {
+ leftBlockFP = getLeftMostLeafBlockFP(leafBlockFPs, nodeID);
+ long delta = leftBlockFP - minBlockFP;
+ assert nodeID == 1 || delta > 0;
+ writeBuffer.writeVLong(delta);
+ } else {
+ // The left tree's left most leaf block FP is always the minimal FP:
+ leftBlockFP = minBlockFP;
+ }
+
+ int address = nodeID * (1+bytesPerDim);
+ int splitDim = splitPackedValues[address++] & 0xff;
+
+ //System.out.println("recursePack inner nodeID=" + nodeID + " splitDim=" + splitDim + " splitValue=" + new BytesRef(splitPackedValues, address, bytesPerDim));
+
+ // find common prefix with last split value in this dim:
+ int prefix = 0;
+ for(;prefix<bytesPerDim;prefix++) {
+ if (splitPackedValues[address+prefix] != lastSplitValues[splitDim * bytesPerDim + prefix]) {
+ break;
+ }
+ }
+
+ //System.out.println("writeNodeData nodeID=" + nodeID + " splitDim=" + splitDim + " numDims=" + numDims + " bytesPerDim=" + bytesPerDim + " prefix=" + prefix);
+
+ int firstDiffByteDelta;
+ if (prefix < bytesPerDim) {
+ //System.out.println(" delta byte cur=" + Integer.toHexString(splitPackedValues[address+prefix]&0xFF) + " prev=" + Integer.toHexString(lastSplitValues[splitDim * bytesPerDim + prefix]&0xFF) + " negated?=" + negativeDeltas[splitDim]);
+ firstDiffByteDelta = (splitPackedValues[address+prefix]&0xFF) - (lastSplitValues[splitDim * bytesPerDim + prefix]&0xFF);
+ if (negativeDeltas[splitDim]) {
+ firstDiffByteDelta = -firstDiffByteDelta;
+ }
+ //System.out.println(" delta=" + firstDiffByteDelta);
+ assert firstDiffByteDelta > 0;
+ } else {
+ firstDiffByteDelta = 0;
+ }
+
+ // pack the prefix, splitDim and delta first diff byte into a single vInt:
+ int code = (firstDiffByteDelta * (1+bytesPerDim) + prefix) * numDims + splitDim;
+
+ //System.out.println(" code=" + code);
+ //System.out.println(" splitValue=" + new BytesRef(splitPackedValues, address, bytesPerDim));
+
+ writeBuffer.writeVInt(code);
+
+ // write the split value, prefix coded vs. our parent's split value:
+ int suffix = bytesPerDim - prefix;
+ byte[] savSplitValue = new byte[suffix];
+ if (suffix > 1) {
+ writeBuffer.writeBytes(splitPackedValues, address+prefix+1, suffix-1);
+ }
+
+ byte[] cmp = lastSplitValues.clone();
+
+ System.arraycopy(lastSplitValues, splitDim * bytesPerDim + prefix, savSplitValue, 0, suffix);
+
+ // copy our split value into lastSplitValues for our children to prefix-code against
+ System.arraycopy(splitPackedValues, address+prefix, lastSplitValues, splitDim * bytesPerDim + prefix, suffix);
+
+ int numBytes = appendBlock(writeBuffer, blocks);
+
+ // placeholder for left-tree numBytes; we need this so that at search time if we only need to recurse into the right sub-tree we can
+ // quickly seek to its starting point
+ int idxSav = blocks.size();
+ blocks.add(null);
+
+ boolean savNegativeDelta = negativeDeltas[splitDim];
+ negativeDeltas[splitDim] = true;
+
+ int leftNumBytes = recursePackIndex(writeBuffer, leafBlockFPs, splitPackedValues, leftBlockFP, blocks, 2*nodeID, lastSplitValues, negativeDeltas, true);
+
+ if (nodeID * 2 < leafBlockFPs.length) {
+ writeBuffer.writeVInt(leftNumBytes);
+ } else {
+ assert leftNumBytes == 0: "leftNumBytes=" + leftNumBytes;
+ }
+ int numBytes2 = Math.toIntExact(writeBuffer.getFilePointer());
+ byte[] bytes2 = new byte[numBytes2];
+ writeBuffer.writeTo(bytes2, 0);
+ writeBuffer.reset();
+ // replace our placeholder:
+ blocks.set(idxSav, bytes2);
+
+ negativeDeltas[splitDim] = false;
+ int rightNumBytes = recursePackIndex(writeBuffer, leafBlockFPs, splitPackedValues, leftBlockFP, blocks, 2*nodeID+1, lastSplitValues, negativeDeltas, false);
+
+ negativeDeltas[splitDim] = savNegativeDelta;
+
+ // restore lastSplitValues to what caller originally passed us:
+ System.arraycopy(savSplitValue, 0, lastSplitValues, splitDim * bytesPerDim + prefix, suffix);
+
+ assert Arrays.equals(lastSplitValues, cmp);
+
+ return numBytes + numBytes2 + leftNumBytes + rightNumBytes;
+ }
+ }
+
+ private long getLeftMostLeafBlockFP(long[] leafBlockFPs, int nodeID) {
+ int nodeIDIn = nodeID;
+ // TODO: can we do this cheaper, e.g. a closed form solution instead of while loop? Or
+ // change the recursion while packing the index to return this left-most leaf block FP
+ // from each recursion instead?
+ //
+ // Still, the overall cost here is minor: this method's cost is O(log(N)), and while writing
+ // we call it O(N) times (N = number of leaf blocks)
+ while (nodeID < leafBlockFPs.length) {
+ nodeID *= 2;
+ }
+ int leafID = nodeID - leafBlockFPs.length;
+ long result = leafBlockFPs[leafID];
+ if (result < 0) {
+ throw new AssertionError(result + " for leaf " + leafID);
+ }
+ return result;
+ }
+
+ private void writeIndex(IndexOutput out, long[] leafBlockFPs, byte[] splitPackedValues) throws IOException {
+ byte[] packedIndex = packIndex(leafBlockFPs, splitPackedValues);
+ writeIndex(out, leafBlockFPs.length, packedIndex);
+ }
+
+ private void writeIndex(IndexOutput out, int numLeaves, byte[] packedIndex) throws IOException {
+
CodecUtil.writeHeader(out, CODEC_NAME, VERSION_CURRENT);
out.writeVInt(numDims);
out.writeVInt(maxPointsInLeafNode);
out.writeVInt(bytesPerDim);
- assert leafBlockFPs.length > 0;
- out.writeVInt(leafBlockFPs.length);
+ assert numLeaves > 0;
+ out.writeVInt(numLeaves);
out.writeBytes(minPackedValue, 0, packedBytesLength);
out.writeBytes(maxPackedValue, 0, packedBytesLength);
out.writeVLong(pointCount);
out.writeVInt(docsSeen.cardinality());
-
- // NOTE: splitPackedValues[0] is unused, because nodeID is 1-based:
- 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++) {
- long delta = leafBlockFPs[i]-lastFP;
- out.writeVLong(delta);
- lastFP = leafBlockFPs[i];
- }
+ out.writeVInt(packedIndex.length);
+ out.writeBytes(packedIndex, 0, packedIndex.length);
}
- protected void writeLeafBlockDocs(IndexOutput out, int[] docIDs, int start, int count) throws IOException {
+ private void writeLeafBlockDocs(IndexOutput out, int[] docIDs, int start, int count) throws IOException {
assert count > 0: "maxPointsInLeafNode=" + maxPointsInLeafNode;
out.writeVInt(count);
DocIdsWriter.writeDocIds(docIDs, start, count, out);
}
- protected void writeLeafBlockPackedValues(IndexOutput out, int[] commonPrefixLengths, int count, int sortedDim, IntFunction<BytesRef> packedValues) throws IOException {
+ private void writeLeafBlockPackedValues(IndexOutput out, int[] commonPrefixLengths, int count, int sortedDim, IntFunction<BytesRef> packedValues) throws IOException {
int prefixLenSum = Arrays.stream(commonPrefixLengths).sum();
if (prefixLenSum == packedBytesLength) {
// all values in this block are equal
@@ -1109,7 +1316,7 @@ public class BKDWriter implements Closeable {
return end - start;
}
- protected void writeCommonPrefixes(IndexOutput out, int[] commonPrefixes, byte[] packedValue) throws IOException {
+ private void writeCommonPrefixes(IndexOutput out, int[] commonPrefixes, byte[] packedValue) throws IOException {
for(int dim=0;dim<numDims;dim++) {
out.writeVInt(commonPrefixes[dim]);
//System.out.println(commonPrefixes[dim] + " of " + bytesPerDim);
@@ -1177,7 +1384,7 @@ public class BKDWriter implements Closeable {
// TODO: find a way to also checksum this reader? If we changed to markLeftTree, and scanned the final chunk, it could work?
try (PointReader reader = source.writer.getReader(source.start + source.count - rightCount, rightCount)) {
boolean result = reader.next();
- assert result;
+ assert result: "rightCount=" + rightCount + " source.count=" + source.count + " source.writer=" + source.writer;
System.arraycopy(reader.packedValue(), splitDim*bytesPerDim, scratch1, 0, bytesPerDim);
if (numDims > 1) {
assert ordBitSet.get(reader.ord()) == false;
@@ -1244,12 +1451,12 @@ public class BKDWriter implements Closeable {
/* Recursively reorders the provided reader and writes the bkd-tree on the fly. */
private void build(int nodeID, int leafNodeOffset,
- MutablePointValues reader, int from, int to,
- IndexOutput out,
- byte[] minPackedValue, byte[] maxPackedValue,
- byte[] splitPackedValues,
- long[] leafBlockFPs,
- int[] spareDocIds) throws IOException {
+ MutablePointValues reader, int from, int to,
+ IndexOutput out,
+ byte[] minPackedValue, byte[] maxPackedValue,
+ byte[] splitPackedValues,
+ long[] leafBlockFPs,
+ int[] spareDocIds) throws IOException {
if (nodeID >= leafNodeOffset) {
// leaf node
@@ -1311,6 +1518,7 @@ public class BKDWriter implements Closeable {
for (int i = from; i < to; ++i) {
docIDs[i - from] = reader.getDocID(i);
}
+ //System.out.println("writeLeafBlock pos=" + out.getFilePointer());
writeLeafBlockDocs(out, docIDs, 0, count);
// Write the common prefixes:
@@ -1344,6 +1552,7 @@ public class BKDWriter implements Closeable {
break;
}
}
+
MutablePointsReaderUtils.partition(maxDoc, splitDim, bytesPerDim, commonPrefixLen,
reader, from, to, mid, scratchBytesRef1, scratchBytesRef2);
@@ -1381,7 +1590,7 @@ public class BKDWriter implements Closeable {
for(PathSlice slice : slices) {
assert slice.count == slices[0].count;
}
-
+
if (numDims == 1 && slices[0].writer instanceof OfflinePointWriter && slices[0].count <= maxPointsSortInHeap) {
// Special case for 1D, to cutover to heap once we recurse deeply enough:
slices[0] = switchToHeap(slices[0], toCloseHeroically);
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/5e8db2e0/lucene/core/src/java/org/apache/lucene/util/bkd/HeapPointReader.java
----------------------------------------------------------------------
diff --git a/lucene/core/src/java/org/apache/lucene/util/bkd/HeapPointReader.java b/lucene/core/src/java/org/apache/lucene/util/bkd/HeapPointReader.java
index 0cd4bd2..99182cb 100644
--- a/lucene/core/src/java/org/apache/lucene/util/bkd/HeapPointReader.java
+++ b/lucene/core/src/java/org/apache/lucene/util/bkd/HeapPointReader.java
@@ -18,7 +18,10 @@ package org.apache.lucene.util.bkd;
import java.util.List;
-final class HeapPointReader extends PointReader {
+/** Utility class to read buffered points from in-heap arrays.
+ *
+ * @lucene.internal */
+public final class HeapPointReader extends PointReader {
private int curRead;
final List<byte[]> blocks;
final int valuesPerBlock;
@@ -30,7 +33,7 @@ final class HeapPointReader extends PointReader {
final byte[] scratch;
final boolean singleValuePerDoc;
- HeapPointReader(List<byte[]> blocks, int valuesPerBlock, int packedBytesLength, int[] ords, long[] ordsLong, int[] docIDs, int start, int end, boolean singleValuePerDoc) {
+ public HeapPointReader(List<byte[]> blocks, int valuesPerBlock, int packedBytesLength, int[] ords, long[] ordsLong, int[] docIDs, int start, int end, boolean singleValuePerDoc) {
this.blocks = blocks;
this.valuesPerBlock = valuesPerBlock;
this.singleValuePerDoc = singleValuePerDoc;
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/5e8db2e0/lucene/core/src/java/org/apache/lucene/util/bkd/HeapPointWriter.java
----------------------------------------------------------------------
diff --git a/lucene/core/src/java/org/apache/lucene/util/bkd/HeapPointWriter.java b/lucene/core/src/java/org/apache/lucene/util/bkd/HeapPointWriter.java
index 24d248b..e102651 100644
--- a/lucene/core/src/java/org/apache/lucene/util/bkd/HeapPointWriter.java
+++ b/lucene/core/src/java/org/apache/lucene/util/bkd/HeapPointWriter.java
@@ -24,18 +24,21 @@ import java.util.List;
import org.apache.lucene.util.ArrayUtil;
import org.apache.lucene.util.BytesRef;
-final class HeapPointWriter implements PointWriter {
- int[] docIDs;
- long[] ordsLong;
- int[] ords;
+/** Utility class to write new points into in-heap arrays.
+ *
+ * @lucene.internal */
+public final class HeapPointWriter implements PointWriter {
+ public int[] docIDs;
+ public long[] ordsLong;
+ public int[] ords;
private int nextWrite;
private boolean closed;
final int maxSize;
- final int valuesPerBlock;
+ public final int valuesPerBlock;
final int packedBytesLength;
final boolean singleValuePerDoc;
// NOTE: can't use ByteBlockPool because we need random-write access when sorting in heap
- final List<byte[]> blocks = new ArrayList<>();
+ public final List<byte[]> blocks = new ArrayList<>();
public HeapPointWriter(int initSize, int maxSize, int packedBytesLength, boolean longOrds, boolean singleValuePerDoc) {
docIDs = new int[initSize];
@@ -77,7 +80,7 @@ final class HeapPointWriter implements PointWriter {
nextWrite = other.nextWrite;
}
- void readPackedValue(int index, byte[] bytes) {
+ public void readPackedValue(int index, byte[] bytes) {
assert bytes.length == packedBytesLength;
int block = index / valuesPerBlock;
int blockIndex = index % valuesPerBlock;
@@ -85,7 +88,7 @@ final class HeapPointWriter implements PointWriter {
}
/** Returns a reference, in <code>result</code>, to the byte[] slice holding this value */
- void getPackedValueSlice(int index, BytesRef result) {
+ public void getPackedValueSlice(int index, BytesRef result) {
int block = index / valuesPerBlock;
int blockIndex = index % valuesPerBlock;
result.bytes = blocks.get(block);
@@ -138,7 +141,8 @@ final class HeapPointWriter implements PointWriter {
@Override
public PointReader getReader(long start, long length) {
assert start + length <= docIDs.length: "start=" + start + " length=" + length + " docIDs.length=" + docIDs.length;
- return new HeapPointReader(blocks, valuesPerBlock, packedBytesLength, ords, ordsLong, docIDs, (int) start, nextWrite, singleValuePerDoc);
+ assert start + length <= nextWrite: "start=" + start + " length=" + length + " nextWrite=" + nextWrite;
+ return new HeapPointReader(blocks, valuesPerBlock, packedBytesLength, ords, ordsLong, docIDs, (int) start, Math.toIntExact(start+length), singleValuePerDoc);
}
@Override
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/5e8db2e0/lucene/core/src/java/org/apache/lucene/util/bkd/MutablePointsReaderUtils.java
----------------------------------------------------------------------
diff --git a/lucene/core/src/java/org/apache/lucene/util/bkd/MutablePointsReaderUtils.java b/lucene/core/src/java/org/apache/lucene/util/bkd/MutablePointsReaderUtils.java
index 132ad3c..1c68478 100644
--- a/lucene/core/src/java/org/apache/lucene/util/bkd/MutablePointsReaderUtils.java
+++ b/lucene/core/src/java/org/apache/lucene/util/bkd/MutablePointsReaderUtils.java
@@ -26,13 +26,16 @@ import org.apache.lucene.util.Selector;
import org.apache.lucene.util.StringHelper;
import org.apache.lucene.util.packed.PackedInts;
-final class MutablePointsReaderUtils {
+/** Utility APIs for sorting and partitioning buffered points.
+ *
+ * @lucene.internal */
+public final class MutablePointsReaderUtils {
MutablePointsReaderUtils() {}
/** Sort the given {@link MutablePointValues} based on its packed value then doc ID. */
- static void sort(int maxDoc, int packedBytesLength,
- MutablePointValues reader, int from, int to) {
+ public static void sort(int maxDoc, int packedBytesLength,
+ MutablePointValues reader, int from, int to) {
final int bitsPerDocId = PackedInts.bitsRequired(maxDoc - 1);
new MSBRadixSorter(packedBytesLength + (bitsPerDocId + 7) / 8) {
@@ -88,9 +91,9 @@ final class MutablePointsReaderUtils {
}
/** Sort points on the given dimension. */
- static void sortByDim(int sortedDim, int bytesPerDim, int[] commonPrefixLengths,
- MutablePointValues reader, int from, int to,
- BytesRef scratch1, BytesRef scratch2) {
+ public static void sortByDim(int sortedDim, int bytesPerDim, int[] commonPrefixLengths,
+ MutablePointValues reader, int from, int to,
+ BytesRef scratch1, BytesRef scratch2) {
// No need for a fancy radix sort here, this is called on the leaves only so
// there are not many values to sort
@@ -127,9 +130,9 @@ final class MutablePointsReaderUtils {
/** Partition points around {@code mid}. All values on the left must be less
* than or equal to it and all values on the right must be greater than or
* equal to it. */
- static void partition(int maxDoc, int splitDim, int bytesPerDim, int commonPrefixLen,
- MutablePointValues reader, int from, int to, int mid,
- BytesRef scratch1, BytesRef scratch2) {
+ public static void partition(int maxDoc, int splitDim, int bytesPerDim, int commonPrefixLen,
+ MutablePointValues reader, int from, int to, int mid,
+ BytesRef scratch1, BytesRef scratch2) {
final int offset = splitDim * bytesPerDim + commonPrefixLen;
final int cmpBytes = bytesPerDim - commonPrefixLen;
final int bitsPerDocId = PackedInts.bitsRequired(maxDoc - 1);
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/5e8db2e0/lucene/core/src/java/org/apache/lucene/util/bkd/OfflinePointReader.java
----------------------------------------------------------------------
diff --git a/lucene/core/src/java/org/apache/lucene/util/bkd/OfflinePointReader.java b/lucene/core/src/java/org/apache/lucene/util/bkd/OfflinePointReader.java
index 17758c0..2861d59 100644
--- a/lucene/core/src/java/org/apache/lucene/util/bkd/OfflinePointReader.java
+++ b/lucene/core/src/java/org/apache/lucene/util/bkd/OfflinePointReader.java
@@ -27,8 +27,10 @@ import org.apache.lucene.store.IndexInput;
import org.apache.lucene.store.IndexOutput;
import org.apache.lucene.util.LongBitSet;
-/** Reads points from disk in a fixed-with format, previously written with {@link OfflinePointWriter}. */
-final class OfflinePointReader extends PointReader {
+/** Reads points from disk in a fixed-with format, previously written with {@link OfflinePointWriter}.
+ *
+ * @lucene.internal */
+public final class OfflinePointReader extends PointReader {
long countLeft;
final IndexInput in;
private final byte[] packedValue;
@@ -43,7 +45,7 @@ final class OfflinePointReader extends PointReader {
// File name we are reading
final String name;
- OfflinePointReader(Directory tempDir, String tempFileName, int packedBytesLength, long start, long length,
+ public OfflinePointReader(Directory tempDir, String tempFileName, int packedBytesLength, long start, long length,
boolean longOrds, boolean singleValuePerDoc) throws IOException {
this.singleValuePerDoc = singleValuePerDoc;
int bytesPerDoc = packedBytesLength + Integer.BYTES;
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/5e8db2e0/lucene/core/src/java/org/apache/lucene/util/bkd/OfflinePointWriter.java
----------------------------------------------------------------------
diff --git a/lucene/core/src/java/org/apache/lucene/util/bkd/OfflinePointWriter.java b/lucene/core/src/java/org/apache/lucene/util/bkd/OfflinePointWriter.java
index 87637ae..7e615a6 100644
--- a/lucene/core/src/java/org/apache/lucene/util/bkd/OfflinePointWriter.java
+++ b/lucene/core/src/java/org/apache/lucene/util/bkd/OfflinePointWriter.java
@@ -26,12 +26,14 @@ import org.apache.lucene.store.Directory;
import org.apache.lucene.store.IOContext;
import org.apache.lucene.store.IndexOutput;
-/** Writes points to disk in a fixed-with format. */
-final class OfflinePointWriter implements PointWriter {
+/** Writes points to disk in a fixed-with format.
+ *
+ * @lucene.internal */
+public final class OfflinePointWriter implements PointWriter {
final Directory tempDir;
- final IndexOutput out;
- final String name;
+ public final IndexOutput out;
+ public final String name;
final int packedBytesLength;
final boolean singleValuePerDoc;
long count;
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/5e8db2e0/lucene/core/src/java/org/apache/lucene/util/bkd/PointReader.java
----------------------------------------------------------------------
diff --git a/lucene/core/src/java/org/apache/lucene/util/bkd/PointReader.java b/lucene/core/src/java/org/apache/lucene/util/bkd/PointReader.java
index 90de0d1..0c31275 100644
--- a/lucene/core/src/java/org/apache/lucene/util/bkd/PointReader.java
+++ b/lucene/core/src/java/org/apache/lucene/util/bkd/PointReader.java
@@ -24,20 +24,22 @@ import org.apache.lucene.util.LongBitSet;
/** One pass iterator through all points previously written with a
* {@link PointWriter}, abstracting away whether points a read
- * from (offline) disk or simple arrays in heap. */
-abstract class PointReader implements Closeable {
+ * from (offline) disk or simple arrays in heap.
+ *
+ * @lucene.internal */
+public abstract class PointReader implements Closeable {
/** Returns false once iteration is done, else true. */
- abstract boolean next() throws IOException;
+ public abstract boolean next() throws IOException;
/** Returns the packed byte[] value */
- abstract byte[] packedValue();
+ public abstract byte[] packedValue();
/** Point ordinal */
- abstract long ord();
+ public abstract long ord();
/** DocID for this point */
- abstract int docID();
+ public abstract int docID();
/** Iterates through the next {@code count} ords, marking them in the provided {@code ordBitSet}. */
public void markOrds(long count, LongBitSet ordBitSet) throws IOException {
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/5e8db2e0/lucene/core/src/java/org/apache/lucene/util/bkd/PointWriter.java
----------------------------------------------------------------------
diff --git a/lucene/core/src/java/org/apache/lucene/util/bkd/PointWriter.java b/lucene/core/src/java/org/apache/lucene/util/bkd/PointWriter.java
index d19f6e5..0222d0e 100644
--- a/lucene/core/src/java/org/apache/lucene/util/bkd/PointWriter.java
+++ b/lucene/core/src/java/org/apache/lucene/util/bkd/PointWriter.java
@@ -23,8 +23,10 @@ import java.util.List;
/** Appends many points, and then at the end provides a {@link PointReader} to iterate
* those points. This abstracts away whether we write to disk, or use simple arrays
- * in heap. */
-interface PointWriter extends Closeable {
+ * in heap.
+ *
+ * @lucene.internal */
+public interface PointWriter extends Closeable {
/** Add a new point */
void append(byte[] packedValue, long ord, int docID) throws IOException;
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/5e8db2e0/lucene/core/src/test/org/apache/lucene/search/TestPointQueries.java
----------------------------------------------------------------------
diff --git a/lucene/core/src/test/org/apache/lucene/search/TestPointQueries.java b/lucene/core/src/test/org/apache/lucene/search/TestPointQueries.java
index 5ad71bf..73b2813 100644
--- a/lucene/core/src/test/org/apache/lucene/search/TestPointQueries.java
+++ b/lucene/core/src/test/org/apache/lucene/search/TestPointQueries.java
@@ -621,6 +621,9 @@ public class TestPointQueries extends LuceneTestCase {
int numDims = TestUtil.nextInt(random(), 1, PointValues.MAX_DIMENSIONS);
int sameValuePct = random().nextInt(100);
+ if (VERBOSE) {
+ System.out.println("TEST: sameValuePct=" + sameValuePct);
+ }
byte[][][] docValues = new byte[numValues][][];
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/5e8db2e0/lucene/core/src/test/org/apache/lucene/util/bkd/Test2BBKDPoints.java
----------------------------------------------------------------------
diff --git a/lucene/core/src/test/org/apache/lucene/util/bkd/Test2BBKDPoints.java b/lucene/core/src/test/org/apache/lucene/util/bkd/Test2BBKDPoints.java
index af2e463..e30168c 100644
--- a/lucene/core/src/test/org/apache/lucene/util/bkd/Test2BBKDPoints.java
+++ b/lucene/core/src/test/org/apache/lucene/util/bkd/Test2BBKDPoints.java
@@ -16,6 +16,7 @@
*/
package org.apache.lucene.util.bkd;
+import org.apache.lucene.index.CheckIndex;
import org.apache.lucene.store.Directory;
import org.apache.lucene.store.FSDirectory;
import org.apache.lucene.store.IOContext;
@@ -64,7 +65,10 @@ public class Test2BBKDPoints extends LuceneTestCase {
IndexInput in = dir.openInput("1d.bkd", IOContext.DEFAULT);
in.seek(indexFP);
BKDReader r = new BKDReader(in);
- r.verify(numDocs);
+ CheckIndex.VerifyPointsVisitor visitor = new CheckIndex.VerifyPointsVisitor("1d", numDocs, r);
+ r.intersect(visitor);
+ assertEquals(r.size(), visitor.getPointCountSeen());
+ assertEquals(r.getDocCount(), visitor.getDocCountSeen());
in.close();
dir.close();
}
@@ -101,7 +105,10 @@ public class Test2BBKDPoints extends LuceneTestCase {
IndexInput in = dir.openInput("2d.bkd", IOContext.DEFAULT);
in.seek(indexFP);
BKDReader r = new BKDReader(in);
- r.verify(numDocs);
+ CheckIndex.VerifyPointsVisitor visitor = new CheckIndex.VerifyPointsVisitor("2d", numDocs, r);
+ r.intersect(visitor);
+ assertEquals(r.size(), visitor.getPointCountSeen());
+ assertEquals(r.getDocCount(), visitor.getDocCountSeen());
in.close();
dir.close();
}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/5e8db2e0/lucene/core/src/test/org/apache/lucene/util/bkd/TestBKD.java
----------------------------------------------------------------------
diff --git a/lucene/core/src/test/org/apache/lucene/util/bkd/TestBKD.java b/lucene/core/src/test/org/apache/lucene/util/bkd/TestBKD.java
index 9eb1fd3..8b9b7a5 100644
--- a/lucene/core/src/test/org/apache/lucene/util/bkd/TestBKD.java
+++ b/lucene/core/src/test/org/apache/lucene/util/bkd/TestBKD.java
@@ -28,6 +28,7 @@ import org.apache.lucene.index.CorruptIndexException;
import org.apache.lucene.index.MergeState;
import org.apache.lucene.index.PointValues.IntersectVisitor;
import org.apache.lucene.index.PointValues.Relation;
+import org.apache.lucene.index.PointValues;
import org.apache.lucene.store.CorruptingIndexOutput;
import org.apache.lucene.store.Directory;
import org.apache.lucene.store.FilterDirectory;
@@ -1010,4 +1011,57 @@ public class TestBKD extends LuceneTestCase {
}
}
+ // Claims 16 bytes per dim, but only use the bottom N 1-3 bytes; this would happen e.g. if a user indexes what are actually just short
+ // values as a LongPoint:
+ public void testWastedLeadingBytes() throws Exception {
+ int numDims = TestUtil.nextInt(random(), 1, PointValues.MAX_DIMENSIONS);
+ int bytesPerDim = PointValues.MAX_NUM_BYTES;
+ int bytesUsed = TestUtil.nextInt(random(), 1, 3);
+
+ Directory dir = newFSDirectory(createTempDir());
+ int numDocs = 100000;
+ BKDWriter w = new BKDWriter(numDocs+1, dir, "tmp", numDims, bytesPerDim, 32, 1f, numDocs, true);
+ byte[] tmp = new byte[bytesUsed];
+ byte[] buffer = new byte[numDims * bytesPerDim];
+ for(int i=0;i<numDocs;i++) {
+ for(int dim=0;dim<numDims;dim++) {
+ random().nextBytes(tmp);
+ System.arraycopy(tmp, 0, buffer, dim*bytesPerDim+(bytesPerDim-bytesUsed), tmp.length);
+ }
+ w.add(buffer, i);
+ }
+
+ IndexOutput out = dir.createOutput("bkd", IOContext.DEFAULT);
+ long fp = w.finish(out);
+ out.close();
+
+ IndexInput in = dir.openInput("bkd", IOContext.DEFAULT);
+ in.seek(fp);
+ BKDReader r = new BKDReader(in);
+ int[] count = new int[1];
+ r.intersect(new IntersectVisitor() {
+
+ @Override
+ public void visit(int docID) {
+ count[0]++;
+ }
+
+ @Override
+ public void visit(int docID, byte[] packedValue) {
+ visit(docID);
+ }
+
+ @Override
+ public Relation compare(byte[] minPacked, byte[] maxPacked) {
+ if (random().nextInt(7) == 1) {
+ return Relation.CELL_CROSSES_QUERY;
+ } else {
+ return Relation.CELL_INSIDE_QUERY;
+ }
+ }
+ });
+ assertEquals(numDocs, count[0]);
+ in.close();
+ dir.close();
+ }
}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/5e8db2e0/lucene/core/src/test/org/apache/lucene/util/fst/TestFSTs.java
----------------------------------------------------------------------
diff --git a/lucene/core/src/test/org/apache/lucene/util/fst/TestFSTs.java b/lucene/core/src/test/org/apache/lucene/util/fst/TestFSTs.java
index 6b218cf..dcce285 100644
--- a/lucene/core/src/test/org/apache/lucene/util/fst/TestFSTs.java
+++ b/lucene/core/src/test/org/apache/lucene/util/fst/TestFSTs.java
@@ -228,7 +228,7 @@ public class TestFSTs extends LuceneTestCase {
final long value = lastOutput + TestUtil.nextInt(random(), 1, 1000);
lastOutput = value;
pairs.add(new FSTTester.InputOutput<>(terms[idx],
- outputs.newPair((long) idx, value)));
+ outputs.newPair((long) idx, value)));
}
new FSTTester<>(random(), dir, inputMode, pairs, outputs, false).doTest(true);
}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/5e8db2e0/lucene/sandbox/src/java/org/apache/lucene/document/NearestNeighbor.java
----------------------------------------------------------------------
diff --git a/lucene/sandbox/src/java/org/apache/lucene/document/NearestNeighbor.java b/lucene/sandbox/src/java/org/apache/lucene/document/NearestNeighbor.java
index 3b9f302..587c63f 100644
--- a/lucene/sandbox/src/java/org/apache/lucene/document/NearestNeighbor.java
+++ b/lucene/sandbox/src/java/org/apache/lucene/document/NearestNeighbor.java
@@ -26,7 +26,10 @@ import org.apache.lucene.geo.Rectangle;
import org.apache.lucene.index.PointValues.IntersectVisitor;
import org.apache.lucene.index.PointValues.Relation;
import org.apache.lucene.util.Bits;
+import org.apache.lucene.util.BytesRef;
import org.apache.lucene.util.SloppyMath;
+import org.apache.lucene.util.bkd.BKDReader.IndexTree;
+import org.apache.lucene.util.bkd.BKDReader.IntersectState;
import org.apache.lucene.util.bkd.BKDReader;
import static org.apache.lucene.geo.GeoEncodingUtils.decodeLatitude;
@@ -41,16 +44,16 @@ class NearestNeighbor {
static class Cell implements Comparable<Cell> {
final int readerIndex;
- final int nodeID;
final byte[] minPacked;
final byte[] maxPacked;
+ final IndexTree index;
/** The closest possible distance of all points in this cell */
final double distanceMeters;
- public Cell(int readerIndex, int nodeID, byte[] minPacked, byte[] maxPacked, double distanceMeters) {
+ public Cell(IndexTree index, int readerIndex, byte[] minPacked, byte[] maxPacked, double distanceMeters) {
+ this.index = index;
this.readerIndex = readerIndex;
- this.nodeID = nodeID;
this.minPacked = minPacked.clone();
this.maxPacked = maxPacked.clone();
this.distanceMeters = distanceMeters;
@@ -66,7 +69,7 @@ class NearestNeighbor {
double minLon = decodeLongitude(minPacked, Integer.BYTES);
double maxLat = decodeLatitude(maxPacked, 0);
double maxLon = decodeLongitude(maxPacked, Integer.BYTES);
- return "Cell(readerIndex=" + readerIndex + " lat=" + minLat + " TO " + maxLat + ", lon=" + minLon + " TO " + maxLon + "; distanceMeters=" + distanceMeters + ")";
+ return "Cell(readerIndex=" + readerIndex + " nodeID=" + index.getNodeID() + " isLeaf=" + index.isLeafNode() + " lat=" + minLat + " TO " + maxLat + ", lon=" + minLon + " TO " + maxLon + "; distanceMeters=" + distanceMeters + ")";
}
}
@@ -219,13 +222,21 @@ class NearestNeighbor {
List<BKDReader.IntersectState> states = new ArrayList<>();
// Add root cell for each reader into the queue:
+ int bytesPerDim = -1;
+
for(int i=0;i<readers.size();i++) {
BKDReader reader = readers.get(i);
+ if (bytesPerDim == -1) {
+ bytesPerDim = reader.getBytesPerDimension();
+ } else if (bytesPerDim != reader.getBytesPerDimension()) {
+ throw new IllegalStateException("bytesPerDim changed from " + bytesPerDim + " to " + reader.getBytesPerDimension() + " across readers");
+ }
byte[] minPackedValue = reader.getMinPackedValue();
byte[] maxPackedValue = reader.getMaxPackedValue();
- states.add(reader.getIntersectState(visitor));
+ IntersectState state = reader.getIntersectState(visitor);
+ states.add(state);
- cellQueue.offer(new Cell(i, 1, reader.getMinPackedValue(), reader.getMaxPackedValue(),
+ cellQueue.offer(new Cell(state.index, i, reader.getMinPackedValue(), reader.getMaxPackedValue(),
approxBestDistance(minPackedValue, maxPackedValue, pointLat, pointLon)));
}
@@ -236,12 +247,12 @@ class NearestNeighbor {
// TODO: if we replace approxBestDistance with actualBestDistance, we can put an opto here to break once this "best" cell is fully outside of the hitQueue bottom's radius:
BKDReader reader = readers.get(cell.readerIndex);
- if (reader.isLeafNode(cell.nodeID)) {
+ if (cell.index.isLeafNode()) {
//System.out.println(" leaf");
// Leaf block: visit all points and possibly collect them:
visitor.curDocBase = docBases.get(cell.readerIndex);
visitor.curLiveDocs = liveDocs.get(cell.readerIndex);
- reader.visitLeafBlockValues(cell.nodeID, states.get(cell.readerIndex));
+ reader.visitLeafBlockValues(cell.index, states.get(cell.readerIndex));
//System.out.println(" now " + hitQueue.size() + " hits");
} else {
//System.out.println(" non-leaf");
@@ -257,14 +268,23 @@ class NearestNeighbor {
continue;
}
+ BytesRef splitValue = BytesRef.deepCopyOf(cell.index.getSplitDimValue());
+ int splitDim = cell.index.getSplitDim();
+
+ // we must clone the index so that we we can recurse left and right "concurrently":
+ IndexTree newIndex = cell.index.clone();
byte[] splitPackedValue = cell.maxPacked.clone();
- reader.copySplitValue(cell.nodeID, splitPackedValue);
- cellQueue.offer(new Cell(cell.readerIndex, 2*cell.nodeID, cell.minPacked, splitPackedValue,
+ System.arraycopy(splitValue.bytes, splitValue.offset, splitPackedValue, splitDim*bytesPerDim, bytesPerDim);
+
+ cell.index.pushLeft();
+ cellQueue.offer(new Cell(cell.index, cell.readerIndex, cell.minPacked, splitPackedValue,
approxBestDistance(cell.minPacked, splitPackedValue, pointLat, pointLon)));
splitPackedValue = cell.minPacked.clone();
- reader.copySplitValue(cell.nodeID, splitPackedValue);
- cellQueue.offer(new Cell(cell.readerIndex, 2*cell.nodeID+1, splitPackedValue, cell.maxPacked,
+ System.arraycopy(splitValue.bytes, splitValue.offset, splitPackedValue, splitDim*bytesPerDim, bytesPerDim);
+
+ newIndex.pushRight();
+ cellQueue.offer(new Cell(newIndex, cell.readerIndex, splitPackedValue, cell.maxPacked,
approxBestDistance(splitPackedValue, cell.maxPacked, pointLat, pointLon)));
}
}