- java.lang.Object
-
- org.apache.lucene.misc.index.BPIndexReorderer
-
public final class BPIndexReorderer extends java.lang.Object
Implementation of "recursive graph bisection", also called "bipartite graph partitioning" and often abbreviated BP, an approach to doc ID assignment that aims at reducing the sum of the log gap between consecutive postings. While originally targeted at reducing the size of postings, this algorithm has been observed to also speed up queries significantly by clustering documents that have similar sets of terms together.This algorithm was initially described by Dhulipala et al. in "Compressing graphs and inverted indexes with recursive graph bisection". This implementation takes advantage of some optimizations suggested by Mackenzie et al. in "Tradeoff Options for Bipartite Graph Partitioning".
Typical usage would look like this:
LeafReader reader; // reader to reorder Directory targetDir; // Directory where to write the reordered index Directory targetDir = FSDirectory.open(targetPath); BPIndexReorderer reorderer = new BPIndexReorderer(); ForkJoinPool pool = new ForkJoinPool(Runtime.getRuntime().availableProcessors(), p -> new ForkJoinWorkerThread(p) {}, null, false); reorderer.setForkJoinPool(pool); reorderer.setFields(Collections.singleton("body")); CodecReader reorderedReaderView = reorderer.reorder(SlowCodecReaderWrapper.wrap(reader), targetDir); try (IndexWriter w = new IndexWriter(targetDir, new IndexWriterConfig().setOpenMode(OpenMode.CREATE))) { w.addIndexes(reorderedReaderView); } DirectoryReader reorderedReader = DirectoryReader.open(targetDir);
Note: This is a slow operation that consumes O(maxDoc + numTerms * numThreads) memory.
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description private class
BPIndexReorderer.BaseRecursiveAction
private class
BPIndexReorderer.ComputeBiasTask
private static class
BPIndexReorderer.ForwardIndex
A forward index.(package private) static class
BPIndexReorderer.ForwardIndexSorter
Use a LSB Radix Sorter to sort the (docID, termID) entries.private class
BPIndexReorderer.IndexReorderingTask
(package private) static interface
BPIndexReorderer.LongConsumer
static class
BPIndexReorderer.NotEnoughRAMException
Exception that is thrown when not enough RAM is available.private static class
BPIndexReorderer.PerThreadState
-
Field Summary
Fields Modifier and Type Field Description static int
DEFAULT_MAX_ITERS
Default maximum number of iterations per recursion level: 20.static int
DEFAULT_MIN_DOC_FREQ
Minimum required document frequency for terms to be considered: 4,096.static int
DEFAULT_MIN_PARTITION_SIZE
Minimum size of partitions.private java.util.Set<java.lang.String>
fields
private static int
FORK_THRESHOLD
Minimum problem size that will result in tasks being splitted.private java.util.concurrent.ForkJoinPool
forkJoinPool
private static float[]
LOG2_TABLE
private float
maxDocFreq
private int
maxIters
private int
minDocFreq
private int
minPartitionSize
private double
ramBudgetMB
private static int
TERM_IDS_BLOCK_SIZE
Block size for terms in the forward index
-
Constructor Summary
Constructors Constructor Description BPIndexReorderer()
Constructor.
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description private BPIndexReorderer.ForwardIndex
buildForwardIndex(Directory tempDir, java.lang.String postingsFileName, int maxDoc, int maxTerm)
Sorter.DocMap
computeDocMap(CodecReader reader, Directory tempDir)
Expert: Compute theSorter.DocMap
that holds the new doc ID numbering.private int[]
computePermutation(CodecReader reader, java.util.Set<java.lang.String> fields, Directory dir)
Compute a permutation of the doc ID space that reduces log gaps between consecutive postings.private static long
docRAMRequirements(int maxDoc)
(package private) static float
fastLog2(int i)
An approximate log() function in base 2 which trades accuracy for much better performance.private int
getParallelism()
(package private) static int
readMonotonicInts(DataInput in, int[] ints)
Decoding logic forwriteMonotonicInts(int[], int, DataOutput)
.CodecReader
reorder(CodecReader reader, Directory tempDir)
Reorder the givenCodecReader
into a reader that tries to minimize the log gap between consecutive documents in postings, which usually helps improve space efficiency and query evaluation efficiency.void
setFields(java.util.Set<java.lang.String> fields)
Sets the fields to use to perform partitioning.void
setForkJoinPool(java.util.concurrent.ForkJoinPool forkJoinPool)
Set theForkJoinPool
to run graph partitioning concurrently.void
setMaxDocFreq(float maxDocFreq)
Set the maximum document frequency for terms to be considered, as a ratio ofmaxDoc
.void
setMaxIters(int maxIters)
Set the maximum number of iterations on each recursion level, 20 by default.void
setMinDocFreq(int minDocFreq)
Set the minimum document frequency for terms to be considered, 4096 by default.void
setMinPartitionSize(int minPartitionSize)
Set the minimum partition size, when the algorithm stops recursing, 32 by default.void
setRAMBudgetMB(double ramBudgetMB)
Set the amount of RAM that graph partitioning is allowed to use.private static boolean
sorted(IntsRef intsRef)
Returns true if, and only if, the givenIntsRef
is sorted.private static long
termRAMRequirementsPerThreadPerTerm()
(package private) static void
writeMonotonicInts(int[] ints, int len, DataOutput out)
Simple bit packing that focuses on the common / efficient case when term IDs can be encoded on 16 bits.private int
writePostings(CodecReader reader, java.util.Set<java.lang.String> fields, Directory tempDir, DataOutput postingsOut)
-
-
-
Field Detail
-
TERM_IDS_BLOCK_SIZE
private static final int TERM_IDS_BLOCK_SIZE
Block size for terms in the forward index- See Also:
- Constant Field Values
-
FORK_THRESHOLD
private static final int FORK_THRESHOLD
Minimum problem size that will result in tasks being splitted.- See Also:
- Constant Field Values
-
DEFAULT_MIN_DOC_FREQ
public static final int DEFAULT_MIN_DOC_FREQ
Minimum required document frequency for terms to be considered: 4,096.- See Also:
- Constant Field Values
-
DEFAULT_MIN_PARTITION_SIZE
public static final int DEFAULT_MIN_PARTITION_SIZE
Minimum size of partitions. The algorithm will stop recursing when reaching partitions below this number of documents: 32.- See Also:
- Constant Field Values
-
DEFAULT_MAX_ITERS
public static final int DEFAULT_MAX_ITERS
Default maximum number of iterations per recursion level: 20. Higher numbers of iterations typically don't help significantly.- See Also:
- Constant Field Values
-
minDocFreq
private int minDocFreq
-
maxDocFreq
private float maxDocFreq
-
minPartitionSize
private int minPartitionSize
-
maxIters
private int maxIters
-
forkJoinPool
private java.util.concurrent.ForkJoinPool forkJoinPool
-
ramBudgetMB
private double ramBudgetMB
-
fields
private java.util.Set<java.lang.String> fields
-
LOG2_TABLE
private static final float[] LOG2_TABLE
-
-
Method Detail
-
setMinDocFreq
public void setMinDocFreq(int minDocFreq)
Set the minimum document frequency for terms to be considered, 4096 by default.
-
setMaxDocFreq
public void setMaxDocFreq(float maxDocFreq)
Set the maximum document frequency for terms to be considered, as a ratio ofmaxDoc
. This is useful because very frequent terms (stop words) add significant overhead to the reordering logic while not being very relevant for ordering. This value must be in (0, 1]. Default value is 1.
-
setMinPartitionSize
public void setMinPartitionSize(int minPartitionSize)
Set the minimum partition size, when the algorithm stops recursing, 32 by default.
-
setMaxIters
public void setMaxIters(int maxIters)
Set the maximum number of iterations on each recursion level, 20 by default. Experiments suggests that values above 20 do not help much. However, values below 20 can be used to trade effectiveness for faster reordering.
-
setForkJoinPool
public void setForkJoinPool(java.util.concurrent.ForkJoinPool forkJoinPool)
Set theForkJoinPool
to run graph partitioning concurrently.NOTE: A value of
null
can be used to run in the current thread, which is the default.
-
getParallelism
private int getParallelism()
-
setRAMBudgetMB
public void setRAMBudgetMB(double ramBudgetMB)
Set the amount of RAM that graph partitioning is allowed to use. More RAM allows running faster. If not enough RAM is provided, aBPIndexReorderer.NotEnoughRAMException
will be thrown. This is 10% of the total heap size by default.
-
setFields
public void setFields(java.util.Set<java.lang.String> fields)
Sets the fields to use to perform partitioning. Anull
value indicates that all indexed fields should be used.
-
writePostings
private int writePostings(CodecReader reader, java.util.Set<java.lang.String> fields, Directory tempDir, DataOutput postingsOut) throws java.io.IOException
- Throws:
java.io.IOException
-
buildForwardIndex
private BPIndexReorderer.ForwardIndex buildForwardIndex(Directory tempDir, java.lang.String postingsFileName, int maxDoc, int maxTerm) throws java.io.IOException
- Throws:
java.io.IOException
-
computeDocMap
public Sorter.DocMap computeDocMap(CodecReader reader, Directory tempDir) throws java.io.IOException
Expert: Compute theSorter.DocMap
that holds the new doc ID numbering. This is exposed to enable integration intoBPReorderingMergePolicy
,reorder(CodecReader, Directory)
should be preferred in general.- Throws:
java.io.IOException
-
reorder
public CodecReader reorder(CodecReader reader, Directory tempDir) throws java.io.IOException
Reorder the givenCodecReader
into a reader that tries to minimize the log gap between consecutive documents in postings, which usually helps improve space efficiency and query evaluation efficiency. Note that the returnedCodecReader
is slow and should typically be used in a call toIndexWriter.addIndexes(CodecReader...)
.- Throws:
BPIndexReorderer.NotEnoughRAMException
- if not enough RAM is providedjava.io.IOException
-
computePermutation
private int[] computePermutation(CodecReader reader, java.util.Set<java.lang.String> fields, Directory dir) throws java.io.IOException
Compute a permutation of the doc ID space that reduces log gaps between consecutive postings.- Throws:
java.io.IOException
-
sorted
private static boolean sorted(IntsRef intsRef)
Returns true if, and only if, the givenIntsRef
is sorted.
-
docRAMRequirements
private static long docRAMRequirements(int maxDoc)
-
termRAMRequirementsPerThreadPerTerm
private static long termRAMRequirementsPerThreadPerTerm()
-
fastLog2
static float fastLog2(int i)
An approximate log() function in base 2 which trades accuracy for much better performance.
-
writeMonotonicInts
static void writeMonotonicInts(int[] ints, int len, DataOutput out) throws java.io.IOException
Simple bit packing that focuses on the common / efficient case when term IDs can be encoded on 16 bits.- Throws:
java.io.IOException
-
readMonotonicInts
static int readMonotonicInts(DataInput in, int[] ints) throws java.io.IOException
Decoding logic forwriteMonotonicInts(int[], int, DataOutput)
. It should get auto-vectorized.- Throws:
java.io.IOException
-
-