org.apache.lucene.util.bkd

Class BKDWriter

java.lang.Object

org.apache.lucene.util.bkd.BKDWriter

All Implemented Interfaces:

Closeable, AutoCloseable

public class BKDWriter
extends Object
implements Closeable

Recursively builds a block KD-tree to assign all incoming points in N-dim space to smaller and smaller N-dim rectangles (cells) until the number of points in a given rectangle is <= config.maxPointsInLeafNode. The tree is partially balanced, which means the leaf nodes will have the requested config.maxPointsInLeafNode except one that might have less. Leaf nodes may straddle the two bottom levels of the binary tree. Values that fall exactly on a cell boundary may be in either cell.

The number of dimensions can be 1 to 8, but every byte[] value is fixed length.

This consumes heap during writing: it allocates a Long[numLeaves], a byte[numLeaves*(1+config.bytesPerDim)] and then uses up to the specified maxMBSortInHeap heap space for writing.

NOTE: This can write at most Integer.MAX_VALUE * config.maxPointsInLeafNode / config.bytesPerDim total points.

WARNING: This API is experimental and might change in incompatible ways in the next release.

Field Summary

Fields

Modifier and Type	Field and Description
static String	CODEC_NAME
protected BKDConfig	config BKD tree configuration
static float	DEFAULT_MAX_MB_SORT_IN_HEAP Default maximum heap to use, before spilling to (slower) disk
protected FixedBitSet	docsSeen
protected byte[]	maxPackedValue Maximum per-dim values, packed
protected byte[]	minPackedValue Minimum per-dim values, packed
protected long	pointCount
static int	VERSION_CURRENT
static int	VERSION_LEAF_STORES_BOUNDS
static int	VERSION_LOW_CARDINALITY_LEAVES
static int	VERSION_META_FILE
static int	VERSION_SELECTIVE_INDEXING
static int	VERSION_START

Constructor Summary

Constructors

Constructor and Description
BKDWriter(int maxDoc, Directory tempDir, String tempFileNamePrefix, BKDConfig config, double maxMBSortInHeap, long totalPointCount)

Method Summary

Modifier and Type	Method and Description
void	add(byte[] packedValue, int docID)
void	close()
Runnable	finish(IndexOutput metaOut, IndexOutput indexOut, IndexOutput dataOut) Writes the BKD tree to the provided IndexOutputs and returns a Runnable that writes the index of the tree if at least one point has been added, or null otherwise.
Runnable	merge(IndexOutput metaOut, IndexOutput indexOut, IndexOutput dataOut, List<MergeState.DocMap> docMaps, List<BKDReader> readers) More efficient bulk-add for incoming BKDReaders.
protected int	split(byte[] minPackedValue, byte[] maxPackedValue, int[] parentSplits) Pick the next dimension to split.
Runnable	writeField(IndexOutput metaOut, IndexOutput indexOut, IndexOutput dataOut, String fieldName, MutablePointValues reader) Write a field from a MutablePointValues.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

CODEC_NAME

public static final String CODEC_NAME

See Also:

Constant Field Values

VERSION_START

public static final int VERSION_START

See Also:

Constant Field Values

VERSION_LEAF_STORES_BOUNDS

public static final int VERSION_LEAF_STORES_BOUNDS

See Also:

Constant Field Values

VERSION_SELECTIVE_INDEXING

public static final int VERSION_SELECTIVE_INDEXING

See Also:

Constant Field Values

VERSION_LOW_CARDINALITY_LEAVES

public static final int VERSION_LOW_CARDINALITY_LEAVES

See Also:

Constant Field Values

VERSION_META_FILE

public static final int VERSION_META_FILE

See Also:

Constant Field Values

VERSION_CURRENT

public static final int VERSION_CURRENT

See Also:

Constant Field Values

DEFAULT_MAX_MB_SORT_IN_HEAP

public static final float DEFAULT_MAX_MB_SORT_IN_HEAP

Default maximum heap to use, before spilling to (slower) disk

See Also:

Constant Field Values

config

protected final BKDConfig config

BKD tree configuration

docsSeen

protected final FixedBitSet docsSeen

minPackedValue

protected final byte[] minPackedValue

Minimum per-dim values, packed

maxPackedValue

protected final byte[] maxPackedValue

Maximum per-dim values, packed

pointCount

protected long pointCount

Constructor Detail

BKDWriter

public BKDWriter(int maxDoc,
                 Directory tempDir,
                 String tempFileNamePrefix,
                 BKDConfig config,
                 double maxMBSortInHeap,
                 long totalPointCount)

Method Detail

add

public void add(byte[] packedValue,
                int docID)
         throws IOException

Throws:

IOException

writeField

public Runnable writeField(IndexOutput metaOut,
                           IndexOutput indexOut,
                           IndexOutput dataOut,
                           String fieldName,
                           MutablePointValues reader)
                    throws IOException

Write a field from a MutablePointValues. This way of writing points is faster than regular writes with add(byte[], int) since there is opportunity for reordering points before writing them to disk. This method does not use transient disk in order to reorder points.

Throws:

IOException

merge

public Runnable merge(IndexOutput metaOut,
                      IndexOutput indexOut,
                      IndexOutput dataOut,
                      List<MergeState.DocMap> docMaps,
                      List<BKDReader> readers)
               throws IOException

More efficient bulk-add for incoming BKDReaders. This does a merge sort of the already sorted values and currently only works when numDims==1. This returns -1 if all documents containing dimensional values were deleted.

Throws:

IOException

finish

public Runnable finish(IndexOutput metaOut,
                       IndexOutput indexOut,
                       IndexOutput dataOut)
                throws IOException

Writes the BKD tree to the provided IndexOutputs and returns a Runnable that writes the index of the tree if at least one point has been added, or null otherwise.

Throws:

IOException

close

public void close()
           throws IOException

Specified by:

close in interface Closeable

Specified by:

close in interface AutoCloseable

Throws:

IOException

split

protected int split(byte[] minPackedValue,
                    byte[] maxPackedValue,
                    int[] parentSplits)

Pick the next dimension to split.

Parameters:

minPackedValue - the min values for all dimensions

maxPackedValue - the max values for all dimensions

parentSplits - how many times each dim has been split on the parent levels

Returns:

the dimension to split