jpountz commented on a change in pull request #525: LUCENE-8585: Index-time jump-tables for DocValues URL: https://github.com/apache/lucene-solr/pull/525#discussion_r247271502
########## File path: lucene/core/src/java/org/apache/lucene/codecs/lucene80/IndexedDISI.java ########## @@ -0,0 +1,626 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one or more + * contributor license agreements. See the NOTICE file distributed with + * this work for additional information regarding copyright ownership. + * The ASF licenses this file to You under the Apache License, Version 2.0 + * (the "License"); you may not use this file except in compliance with + * the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package org.apache.lucene.codecs.lucene80; + +import java.io.DataInput; +import java.io.IOException; + +import org.apache.lucene.search.DocIdSetIterator; +import org.apache.lucene.store.IndexInput; +import org.apache.lucene.store.IndexOutput; +import org.apache.lucene.store.RandomAccessInput; +import org.apache.lucene.util.ArrayUtil; +import org.apache.lucene.util.BitSetIterator; +import org.apache.lucene.util.FixedBitSet; +import org.apache.lucene.util.RoaringDocIdSet; + +/** + * Disk-based implementation of a {@link DocIdSetIterator} which can return + * the index of the current document, i.e. the ordinal of the current document + * among the list of documents that this iterator can return. This is useful + * to implement sparse doc values by only having to encode values for documents + * that actually have a value. + * <p>Implementation-wise, this {@link DocIdSetIterator} is inspired of + * {@link RoaringDocIdSet roaring bitmaps} and encodes ranges of {@code 65536} + * documents independently and picks between 3 encodings depending on the + * density of the range:<ul> + * <li>{@code ALL} if the range contains 65536 documents exactly, + * <li>{@code DENSE} if the range contains 4096 documents or more; in that + * case documents are stored in a bit set, + * <li>{@code SPARSE} otherwise, and the lower 16 bits of the doc IDs are + * stored in a {@link DataInput#readShort() short}. + * </ul> + * <p>Only ranges that contain at least one value are encoded. + * <p>This implementation uses 6 bytes per document in the worst-case, which happens + * in the case that all ranges contain exactly one document. + * + * + * To avoid O(n) lookup time complexity, with n being the number of documents, two lookup + * tables are used: A lookup table for block offset and index, and a rank structure + * for DENSE block index lookups. + * + * The lookup table is an array of {@code int}-pairs, with a pair for each block. It allows for + * direct jumping to the block, as opposed to iteration from the current position and forward + * one block at a time. + * + * Each int-pair entry consists of 2 logical parts: + * + * The first 32 bit int holds the index (number of set bits in the blocks) up to just before the + * wanted block. The maximum number of set bits is the maximum number of documents, which is < 2^31. + * + * The next int holds the offset in bytes into the underlying slice. As there is a maximum of 2^16 + * blocks, it follows that the maximum size of any block must not exceed 2^15 bytes to avoid + * overflow (2^16 bytes if the int is treated as unsigned). This is currently the case, with the + * largest block being DENSE and using 2^13 + 36 bytes. + * + * The cache overhead is numDocs/1024 bytes. + * + * Note: There are 4 types of blocks: ALL, DENSE, SPARSE and non-existing (0 set bits). + * In the case of non-existing blocks, the entry in the lookup table has index equal to the + * previous entry and offset equal to the next non-empty block. + * + * The block lookup table is stored at the end of the total block structure. + * + * + * The rank structure for DENSE blocks is an array of byte-pairs with an entry for each + * sub-block (default 512 bits) out of the 65536 bits in the outer DENSE block. + * + * Each rank-entry states the number of set bits within the block up to the bit before the + * bit positioned at the start of the sub-block. + * Note that that the rank entry of the first sub-block is always 0 and that the last entry can + * at most be 65536-2 = 65634 and thus will always fit into an byte-pair of 16 bits. + * + * The rank structure for a given DENSE block is stored at the beginning of the DENSE block. + * This ensures locality and keeps logistics simple. + * + * @lucene.internal + */ +final class IndexedDISI extends DocIdSetIterator { + + // jump-table time/space trade-offs to consider: + // The block offsets and the block indexes could be stored in more compressed form with + // two PackedInts or two MonotonicDirectReaders. + // The DENSE ranks (default 128 shorts = 256 bytes) could likewise be compressed. But as there is + // at least 4096 set bits in DENSE blocks, there will be at least one rank with 2^12 bits, so it + // is doubtful if there is much to gain here. + + private static final int BLOCK_SIZE = 65536; // The number of docIDs that a single block represents + + private static final int DENSE_BLOCK_LONGS = BLOCK_SIZE/Long.SIZE; // 1024 + public static final byte DEFAULT_DENSE_RANK_POWER = 9; // Every 512 docIDs / 8 longs + + static final int MAX_ARRAY_LENGTH = (1 << 12) - 1; + + private static void flush( + int block, FixedBitSet buffer, int cardinality, byte denseRankPower, IndexOutput out) throws IOException { + assert block >= 0 && block < 65536; + out.writeShort((short) block); + assert cardinality > 0 && cardinality <= 65536; + out.writeShort((short) (cardinality - 1)); + if (cardinality > MAX_ARRAY_LENGTH) { + if (cardinality != 65536) { // all docs are set + if (denseRankPower != -1) { + final byte[] rank = createRank(buffer, denseRankPower); + out.writeBytes(rank, rank.length); + } + for (long word : buffer.getBits()) { + out.writeLong(word); + } + } + } else { + BitSetIterator it = new BitSetIterator(buffer, cardinality); + for (int doc = it.nextDoc(); doc != DocIdSetIterator.NO_MORE_DOCS; doc = it.nextDoc()) { + out.writeShort((short) doc); + } + } + } + + // Creates a DENSE rank-entry (the number of set bits up to a given point) for the buffer. + // One rank-entry for every {@code 2^denseRankPower} bits, with each rank-entry using 2 bytes. + // Represented as a byte[] for fast flushing and mirroring of the retrieval representation. + private static byte[] createRank(FixedBitSet buffer, byte denseRankPower) { + final int longsPerRank = 1 << (denseRankPower-6); + final int rankMark = longsPerRank-1; + final int rankIndexShift = denseRankPower-7; // 6 for the long (2^6) + 1 for 2 bytes/entry + final byte[] rank = new byte[DENSE_BLOCK_LONGS >> rankIndexShift]; + final long[] bits = buffer.getBits(); + int bitCount = 0; + for (int word = 0 ; word < DENSE_BLOCK_LONGS ; word++) { + if ((word & rankMark) == 0) { // Every longsPerRank longs + rank[word >> rankIndexShift] = (byte)(bitCount>>8); + rank[(word >> rankIndexShift)+1] = (byte)(bitCount & 0xFF); + } + bitCount += Long.bitCount(bits[word]); + } + return rank; + } + + /** + * Writes the docIDs from it to out, in logical blocks, one for each 65536 docIDs in monotonically increasing + * gap-less order. DENSE blocks uses {@link #DEFAULT_DENSE_RANK_POWER} of 9 (every 512 docIDs / 8 longs). + * The caller must keep track of the number of jump-table entries (returned by this method) as well as the + * denseRankPower (9 for this method) and provide them when constructing an IndexedDISI for reading. + * @param it the document IDs. + * @param out destination for the blocks. + * @throws IOException if there was an error writing to out. + * @return the number of jump-table entries following the blocks, -1 for no entries. + * This should be stored in meta and used when creating an instance of IndexedDISI. + */ + static short writeBitSet(DocIdSetIterator it, IndexOutput out) throws IOException { + return writeBitSet(it, out, DEFAULT_DENSE_RANK_POWER); + } + + /** + * Writes the docIDs from it to out, in logical blocks, one for each 65536 docIDs in monotonically + * increasing gap-less order. + * The caller must keep track of the number of jump-table entries (returned by this method) as well as the + * denseRankPower and provide them when constructing an IndexedDISI for reading. + * @param it the document IDs. + * @param out destination for the blocks. + * @param denseRankPower for {@link Method#DENSE} blocks, a rank will be written every {@code 2^denseRankPower} docIDs. + * Values < 7 (every 128 docIDs) or > 15 (every 32768 docIDs) disables DENSE rank. + * Recommended values are 8-12: Every 256-4096 docIDs or 4-64 longs. + * {@link #DEFAULT_DENSE_RANK_POWER} is 9: Every 512 docIDs. + * This should be stored in meta and used when creating an instance of IndexedDISI. + * @throws IOException if there was an error writing to out. + * @return the number of jump-table entries following the blocks, -1 for no entries. + * This should be stored in meta and used when creating an instance of IndexedDISI. + */ + static short writeBitSet(DocIdSetIterator it, IndexOutput out, byte denseRankPower) throws IOException { + final long origo = out.getFilePointer(); // All jumps are relative to the origo + if (denseRankPower < 7 || denseRankPower > 15) { + denseRankPower = -1; // Disabled + } + int totalCardinality = 0; + int blockCardinality = 0; + final FixedBitSet buffer = new FixedBitSet(1<<16); + int[] jumps = new int[ArrayUtil.oversize(1, Integer.BYTES*2)]; + int prevBlock = -1; + int jumpBlockIndex = 0; + + for (int doc = it.nextDoc(); doc != DocIdSetIterator.NO_MORE_DOCS; doc = it.nextDoc()) { + final int block = doc >>> 16; + if (prevBlock != -1 && block != prevBlock) { + // Track offset+index from previous block up to current + jumps = addJumps(jumps, out.getFilePointer()-origo, totalCardinality, jumpBlockIndex, prevBlock+1); + jumpBlockIndex = prevBlock+1; + // Flush block + flush(prevBlock, buffer, blockCardinality, denseRankPower, out); + // Reset for next block + buffer.clear(0, buffer.length()); + totalCardinality += blockCardinality; + blockCardinality = 0; + } + buffer.set(doc & 0xFFFF); + blockCardinality++; + prevBlock = block; + } + if (blockCardinality > 0) { + jumps = addJumps(jumps, out.getFilePointer()-origo, totalCardinality, jumpBlockIndex, prevBlock+1); + totalCardinality += blockCardinality; + flush(prevBlock, buffer, blockCardinality, denseRankPower, out); + buffer.clear(0, buffer.length()); + prevBlock++; + } + final int lastBlock = prevBlock == -1 ? 0 : prevBlock; // There will always be at least 1 block (NO_MORE_DOCS) + // Last entry is a SPARSE with blockIndex == 32767 and the single entry 65535, which becomes the docID NO_MORE_DOCS + // To avoid creating 65K jump-table entries, only a single entry is created pointing to the offset of the + // NO_MORE_DOCS block, with the jumpBlockIndex set to the logical EMPTY block after all real blocks. + jumps = addJumps(jumps, out.getFilePointer()-origo, totalCardinality, lastBlock, lastBlock+1); + buffer.set(DocIdSetIterator.NO_MORE_DOCS & 0xFFFF); + flush(DocIdSetIterator.NO_MORE_DOCS >>> 16, buffer, 1, denseRankPower, out); + // offset+index jump-table stored at the end + return flushBlockJumps(jumps, lastBlock+1, out, origo); + } + + // Adds entries to the offset & index jump-table for blocks + private static int[] addJumps(int[] jumps, long offset, int index, int startBlock, int endBlock) { + assert offset < Integer.MAX_VALUE : "Logically the offset should not exceed 2^30 but was >= Integer.MAX_VALUE"; + jumps = ArrayUtil.grow(jumps, (endBlock+1)*2); + for (int b = startBlock; b < endBlock; b++) { + jumps[b*2] = index; + jumps[b*2+1] = (int) offset; + } + return jumps; + } + + // Flushes the offet & index jump-table for blocks. This should be the last data written to out + // This method returns the blockCount for the blocks reachable for the jump_table or -1 for no jump-table + private static short flushBlockJumps(int[] jumps, int blockCount, IndexOutput out, long origo) throws IOException { + if (blockCount == 2) { // Jumps with a single real entry + NO_MORE_DOCS is just wasted space so we ignore that + blockCount = 0; + } + for (int i = 0 ; i < blockCount ; i++) { + out.writeInt(jumps[i*2]); // index + out.writeInt(jumps[i*2+1]); // offset + } + // As there are at most 32k blocks, the count is a short + // The jumpTableOffset will be at lastPos - (blockCount * Long.BYTES) + return (short)blockCount; + } + + /** The slice that stores the {@link DocIdSetIterator}. */ + private final IndexInput slice; + private final int jumpTableEntryCount; + private final byte denseRankPower; + private final RandomAccessInput jumpTable; // Skip blocks of 64K bits + private final byte[] denseRankTable; + private final long cost; + + /** + * This constructor always creates a new blockSlice and a new jumpTable from in, to ensure that operations are + * independent from the caller. + * See {@link #IndexedDISI(IndexInput, RandomAccessInput, int, byte, long)} for re-use of blockSlice and jumpTable. + * @param in backing data. + * @param offset starting offset for blocks in the backing data. + * @param length the number of bytes holding blocks and jump-table in the backing data. + * @param jumpTableEntryCount the number of blocks covered by the jump-table. + * This must match the number returned by {@link #writeBitSet(DocIdSetIterator, IndexOutput, byte)}. + * @param denseRankPower the number of docIDs covered by each rank entry in DENSE blocks, expressed as {@code 2^denseRankPower}. + * This must match the power given in {@link #writeBitSet(DocIdSetIterator, IndexOutput, byte)} + * @param cost normally the number of logical docIDs. + */ + IndexedDISI(IndexInput in, long offset, long length, int jumpTableEntryCount, byte denseRankPower, long cost) throws IOException { + this(createBlockSlice(in,"docs", offset, length, jumpTableEntryCount), + createJumpTable(in, offset, length, jumpTableEntryCount), + jumpTableEntryCount, denseRankPower, cost); + } + + /** + * This constructor allows to pass the slice and jumpTable directly in case it helps reuse. + * see eg. Lucene80 norms producer's merge instance. + * @param blockSlice data blocks, normally created by {@link #createBlockSlice}. + * @param jumpTable table holding jump-data for block-skips, normally created by {@link #createJumpTable}. + * @param jumpTableEntryCount the number of blocks covered by the jump-table. + * This must match the number returned by {@link #writeBitSet(DocIdSetIterator, IndexOutput, byte)}. + * @param denseRankPower the number of docIDs covered by each rank entry in DENSE blocks, expressed as {@code 2^denseRankPower}. + * This must match the power given in {@link #writeBitSet(DocIdSetIterator, IndexOutput, byte)} + * @param cost normally the number of logical docIDs. + */ + IndexedDISI(IndexInput blockSlice, RandomAccessInput jumpTable, int jumpTableEntryCount, byte denseRankPower, long cost) throws IOException { + this.slice = blockSlice; + this.jumpTable = jumpTable; + this.jumpTableEntryCount = jumpTableEntryCount; + this.denseRankPower = denseRankPower < 7 || denseRankPower > 15 ? -1 : denseRankPower; Review comment: same here, should we fail values that make little sense instead? ---------------------------------------------------------------- This is an automated message from the Apache Git Service. To respond to the message, please log on GitHub and use the URL above to go to the specific comment. For queries about this service, please contact Infrastructure at: us...@infra.apache.org With regards, Apache Git Services --------------------------------------------------------------------- To unsubscribe, e-mail: dev-unsubscr...@lucene.apache.org For additional commands, e-mail: dev-h...@lucene.apache.org
