Package org.apache.lucene.util.bkd

Class BKDReader

java.lang.Object

org.apache.lucene.index.PointValues

org.apache.lucene.util.bkd.BKDReader

public final class BKDReader
extends PointValues

Handles intersection of an multi-dimensional shape in byte[] space with a block KD-tree previously written with BKDWriter.

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
protected static class	BKDReader.BKDReaderDocIDSetIterator	Reusable DocIdSetIterator to handle low cardinality leaves.
class	BKDReader.IndexTree	Used to walk the off-heap index.
static final class	BKDReader.IntersectState	Used to track all state for a single call to intersect(org.apache.lucene.index.PointValues.IntersectVisitor).

Nested classes/interfaces inherited from class org.apache.lucene.index.PointValues

PointValues.IntersectVisitor, PointValues.Relation

Field Summary

Fields

Modifier and Type	Field	Description
(package private) final BKDConfig	config
(package private) final int	docCount
(package private) final IndexInput	in
(package private) final int	leafNodeOffset
(package private) final byte[]	maxPackedValue
(package private) final long	minLeafBlockFP
(package private) final byte[]	minPackedValue
(package private) final int	numLeaves
(package private) final IndexInput	packedIndex
(package private) final long	pointCount
(package private) final int	version

Fields inherited from class org.apache.lucene.index.PointValues

MAX_DIMENSIONS, MAX_INDEX_DIMENSIONS, MAX_NUM_BYTES

Constructor Summary

Constructors

Constructor	Description
BKDReader(IndexInput metaIn, IndexInput indexIn, IndexInput dataIn)	Caller must pre-seek the provided IndexInput to the index location that BKDWriter.finish(org.apache.lucene.store.IndexOutput, org.apache.lucene.store.IndexOutput, org.apache.lucene.store.IndexOutput) returned.

Method Summary

Modifier and Type	Method	Description
private void	addAll(BKDReader.IntersectState state, boolean grown)	Fast path: this is called when the query box fully encompasses all cells under this node.
long	estimatePointCount(PointValues.IntersectVisitor visitor)	Estimate the number of points that would be visited by PointValues.intersect(org.apache.lucene.index.PointValues.IntersectVisitor) with the given PointValues.IntersectVisitor.
private long	estimatePointCount(BKDReader.IntersectState state, byte[] cellMinPacked, byte[] cellMaxPacked)
int	getBytesPerDimension()	Returns the number of bytes per dimension
int	getDocCount()	Returns the total number of documents that have indexed at least one point.
BKDReader.IntersectState	getIntersectState(PointValues.IntersectVisitor visitor)	Create a new BKDReader.IntersectState
byte[]	getMaxPackedValue()	Returns maximum value for each dimension, packed, or null if PointValues.size(org.apache.lucene.index.IndexReader, java.lang.String) is 0
(package private) long	getMinLeafBlockFP()
byte[]	getMinPackedValue()	Returns minimum value for each dimension, packed, or null if PointValues.size(org.apache.lucene.index.IndexReader, java.lang.String) is 0
int	getNumDimensions()	Returns how many dimensions are represented in the values
int	getNumIndexDimensions()	Returns how many dimensions are used for the index
private int	getTreeDepth()
void	intersect(PointValues.IntersectVisitor visitor)	Finds all documents and points matching the provided visitor.
private void	intersect(BKDReader.IntersectState state, byte[] cellMinPacked, byte[] cellMaxPacked)
boolean	isLeafNode(int nodeID)
private void	readCommonPrefixes(int[] commonPrefixLengths, byte[] scratchPackedValue, IndexInput in)
private int	readCompressedDim(IndexInput in)
(package private) int	readDocIDs(IndexInput in, long blockFP, BKDReader.BKDReaderDocIDSetIterator iterator)
private void	readMinMax(int[] commonPrefixLengths, byte[] minPackedValue, byte[] maxPackedValue, IndexInput in)
long	size()	Returns the total number of indexed points across all documents.
private void	visitCompressedDocValues(int[] commonPrefixLengths, byte[] scratchPackedValue, IndexInput in, BKDReader.BKDReaderDocIDSetIterator scratchIterator, int count, PointValues.IntersectVisitor visitor, int compressedDim)
private void	visitDocIDs(IndexInput in, long blockFP, PointValues.IntersectVisitor visitor)
(package private) void	visitDocValues(int[] commonPrefixLengths, byte[] scratchDataPackedValue, byte[] scratchMinIndexPackedValue, byte[] scratchMaxIndexPackedValue, IndexInput in, BKDReader.BKDReaderDocIDSetIterator scratchIterator, int count, PointValues.IntersectVisitor visitor)
(package private) void	visitDocValuesNoCardinality(int[] commonPrefixLengths, byte[] scratchDataPackedValue, byte[] scratchMinIndexPackedValue, byte[] scratchMaxIndexPackedValue, IndexInput in, BKDReader.BKDReaderDocIDSetIterator scratchIterator, int count, PointValues.IntersectVisitor visitor)
(package private) void	visitDocValuesWithCardinality(int[] commonPrefixLengths, byte[] scratchDataPackedValue, byte[] scratchMinIndexPackedValue, byte[] scratchMaxIndexPackedValue, IndexInput in, BKDReader.BKDReaderDocIDSetIterator scratchIterator, int count, PointValues.IntersectVisitor visitor)
void	visitLeafBlockValues(BKDReader.IndexTree index, BKDReader.IntersectState state)	Visits all docIDs and packed values in a single leaf block
private void	visitSparseRawDocValues(int[] commonPrefixLengths, byte[] scratchPackedValue, IndexInput in, BKDReader.BKDReaderDocIDSetIterator scratchIterator, int count, PointValues.IntersectVisitor visitor)
private void	visitUniqueRawDocValues(byte[] scratchPackedValue, BKDReader.BKDReaderDocIDSetIterator scratchIterator, int count, PointValues.IntersectVisitor visitor)

Methods inherited from class org.apache.lucene.index.PointValues

estimateDocCount, getDocCount, getMaxPackedValue, getMinPackedValue, size

Methods inherited from class java.lang.Object

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

Field Details

leafNodeOffset

final int leafNodeOffset

config

final BKDConfig config

numLeaves

final int numLeaves

in

final IndexInput in

minPackedValue

final byte[] minPackedValue

maxPackedValue

final byte[] maxPackedValue

pointCount

final long pointCount

docCount

final int docCount

version

final int version

minLeafBlockFP

final long minLeafBlockFP

packedIndex

final IndexInput packedIndex

Constructor Details

BKDReader

public BKDReader(IndexInput metaIn,
 IndexInput indexIn,
 IndexInput dataIn)
          throws IOException

Caller must pre-seek the provided IndexInput to the index location that BKDWriter.finish(org.apache.lucene.store.IndexOutput, org.apache.lucene.store.IndexOutput, org.apache.lucene.store.IndexOutput) returned. BKD tree is always stored off-heap.

Throws:

IOException

Method Details

getMinLeafBlockFP

long getMinLeafBlockFP()

getTreeDepth

private int getTreeDepth()

intersect

public void intersect(PointValues.IntersectVisitor visitor)
               throws IOException

Description copied from class: PointValues

Finds all documents and points matching the provided visitor. This method does not enforce live documents, so it's up to the caller to test whether each document is deleted, if necessary.

Specified by:

intersect in class PointValues

Throws:

IOException

estimatePointCount

public long estimatePointCount(PointValues.IntersectVisitor visitor)

Description copied from class: PointValues

Estimate the number of points that would be visited by PointValues.intersect(org.apache.lucene.index.PointValues.IntersectVisitor) with the given PointValues.IntersectVisitor. This should run many times faster than PointValues.intersect(IntersectVisitor).

Specified by:

estimatePointCount in class PointValues

addAll

private void addAll(BKDReader.IntersectState state,
 boolean grown)
             throws IOException

Fast path: this is called when the query box fully encompasses all cells under this node.

Throws:

IOException

getIntersectState

public BKDReader.IntersectState getIntersectState(PointValues.IntersectVisitor visitor)

Create a new BKDReader.IntersectState

visitLeafBlockValues

public void visitLeafBlockValues(BKDReader.IndexTree index,
 BKDReader.IntersectState state)
                          throws IOException

Visits all docIDs and packed values in a single leaf block

Throws:

IOException

visitDocIDs

private void visitDocIDs(IndexInput in,
 long blockFP,
 PointValues.IntersectVisitor visitor)
                  throws IOException

Throws:

IOException

readDocIDs

int readDocIDs(IndexInput in,
 long blockFP,
 BKDReader.BKDReaderDocIDSetIterator iterator)
        throws IOException

Throws:

IOException

visitDocValues

void visitDocValues(int[] commonPrefixLengths,
 byte[] scratchDataPackedValue,
 byte[] scratchMinIndexPackedValue,
 byte[] scratchMaxIndexPackedValue,
 IndexInput in,
 BKDReader.BKDReaderDocIDSetIterator scratchIterator,
 int count,
 PointValues.IntersectVisitor visitor)
             throws IOException

Throws:

IOException

visitDocValuesNoCardinality

void visitDocValuesNoCardinality(int[] commonPrefixLengths,
 byte[] scratchDataPackedValue,
 byte[] scratchMinIndexPackedValue,
 byte[] scratchMaxIndexPackedValue,
 IndexInput in,
 BKDReader.BKDReaderDocIDSetIterator scratchIterator,
 int count,
 PointValues.IntersectVisitor visitor)
                          throws IOException

Throws:

IOException

visitDocValuesWithCardinality

void visitDocValuesWithCardinality(int[] commonPrefixLengths,
 byte[] scratchDataPackedValue,
 byte[] scratchMinIndexPackedValue,
 byte[] scratchMaxIndexPackedValue,
 IndexInput in,
 BKDReader.BKDReaderDocIDSetIterator scratchIterator,
 int count,
 PointValues.IntersectVisitor visitor)
                            throws IOException

Throws:

IOException

readMinMax

private void readMinMax(int[] commonPrefixLengths,
 byte[] minPackedValue,
 byte[] maxPackedValue,
 IndexInput in)
                 throws IOException

Throws:

IOException

visitSparseRawDocValues

private void visitSparseRawDocValues(int[] commonPrefixLengths,
 byte[] scratchPackedValue,
 IndexInput in,
 BKDReader.BKDReaderDocIDSetIterator scratchIterator,
 int count,
 PointValues.IntersectVisitor visitor)
                              throws IOException

Throws:

IOException

visitUniqueRawDocValues

private void visitUniqueRawDocValues(byte[] scratchPackedValue,
 BKDReader.BKDReaderDocIDSetIterator scratchIterator,
 int count,
 PointValues.IntersectVisitor visitor)
                              throws IOException

Throws:

IOException

visitCompressedDocValues

private void visitCompressedDocValues(int[] commonPrefixLengths,
 byte[] scratchPackedValue,
 IndexInput in,
 BKDReader.BKDReaderDocIDSetIterator scratchIterator,
 int count,
 PointValues.IntersectVisitor visitor,
 int compressedDim)
                               throws IOException

Throws:

IOException

readCompressedDim

private int readCompressedDim(IndexInput in)
                       throws IOException

Throws:

IOException

readCommonPrefixes

private void readCommonPrefixes(int[] commonPrefixLengths,
 byte[] scratchPackedValue,
 IndexInput in)
                         throws IOException

Throws:

IOException

intersect

private void intersect(BKDReader.IntersectState state,
 byte[] cellMinPacked,
 byte[] cellMaxPacked)
                throws IOException

Throws:

IOException

estimatePointCount

private long estimatePointCount(BKDReader.IntersectState state,
 byte[] cellMinPacked,
 byte[] cellMaxPacked)

getMinPackedValue

public byte[] getMinPackedValue()

Description copied from class: PointValues

Returns minimum value for each dimension, packed, or null if PointValues.size(org.apache.lucene.index.IndexReader, java.lang.String) is 0

Specified by:

getMinPackedValue in class PointValues

getMaxPackedValue

public byte[] getMaxPackedValue()

Description copied from class: PointValues

Returns maximum value for each dimension, packed, or null if PointValues.size(org.apache.lucene.index.IndexReader, java.lang.String) is 0

Specified by:

getMaxPackedValue in class PointValues

getNumDimensions

public int getNumDimensions()

Description copied from class: PointValues

Returns how many dimensions are represented in the values

Specified by:

getNumDimensions in class PointValues

getNumIndexDimensions

public int getNumIndexDimensions()

Description copied from class: PointValues

Returns how many dimensions are used for the index

Specified by:

getNumIndexDimensions in class PointValues

getBytesPerDimension

public int getBytesPerDimension()

Description copied from class: PointValues

Returns the number of bytes per dimension

Specified by:

getBytesPerDimension in class PointValues

size

public long size()

Description copied from class: PointValues

Returns the total number of indexed points across all documents.

Specified by:

size in class PointValues

getDocCount

public int getDocCount()

Description copied from class: PointValues

Returns the total number of documents that have indexed at least one point.

Specified by:

getDocCount in class PointValues

isLeafNode

public boolean isLeafNode(int nodeID)