{"action":"created","comment":{"url":"https://api.github.com/repos/apache/lucene-solr/pulls/comments/242148673","pull_request_review_id":185591504,"id":242148673,"node_id":"MDI0OlB1bGxSZXF1ZXN0UmV2aWV3Q29tbWVudDI0MjE0ODY3Mw==","diff_hunk":"@@ -0,0 +1,536 @@\n+/*\n+ * Licensed to the Apache Software Foundation (ASF) under one or more\n+ * contributor license agreements.  See the NOTICE file distributed with\n+ * this work for additional information regarding copyright ownership.\n+ * The ASF licenses this file to You under the Apache License, Version 2.0\n+ * (the \"License\"); you may not use this file except in compliance with\n+ * the License.  You may obtain a copy of the License at\n+ *\n+ *     http://www.apache.org/licenses/LICENSE-2.0\n+ *\n+ * Unless required by applicable law or agreed to in writing, software\n+ * distributed under the License is distributed on an \"AS IS\" BASIS,\n+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\n+ * See the License for the specific language governing permissions and\n+ * limitations under the License.\n+ */\n+package org.apache.lucene.codecs.lucene80;\n+\n+import java.io.DataInput;\n+import java.io.IOException;\n+\n+import org.apache.lucene.search.DocIdSetIterator;\n+import org.apache.lucene.store.IndexInput;\n+import org.apache.lucene.store.IndexOutput;\n+import org.apache.lucene.util.ArrayUtil;\n+import org.apache.lucene.util.BitSetIterator;\n+import org.apache.lucene.util.FixedBitSet;\n+import org.apache.lucene.util.RoaringDocIdSet;\n+\n+/**\n+ * Disk-based implementation of a {@link DocIdSetIterator} which can return\n+ * the index of the current document, i.e. the ordinal of the current document\n+ * among the list of documents that this iterator can return. This is useful\n+ * to implement sparse doc values by only having to encode values for documents\n+ * that actually have a value.\n+ * <p>Implementation-wise, this {@link DocIdSetIterator} is inspired of\n+ * {@link RoaringDocIdSet roaring bitmaps} and encodes ranges of {@code 65536}\n+ * documents independently and picks between 3 encodings depending on the\n+ * density of the range:<ul>\n+ *   <li>{@code ALL} if the range contains 65536 documents exactly,\n+ *   <li>{@code DENSE} if the range contains 4096 documents or more; in that\n+ *       case documents are stored in a bit set,\n+ *   <li>{@code SPARSE} otherwise, and the lower 16 bits of the doc IDs are\n+ *       stored in a {@link DataInput#readShort() short}.\n+ * </ul>\n+ * <p>Only ranges that contain at least one value are encoded.\n+ * <p>This implementation uses 6 bytes per document in the worst-case, which happens\n+ * in the case that all ranges contain exactly one document.\n+ *\n+ * \n+ * To avoid O(n) lookup time complexity, with n being the number of documents, two lookup\n+ * tables are used:  * A lookup table for block blockCache and index, and a rank structure\n+ * for DENSE block lookups.\n+ *\n+ * The lookup table is an array of {@code long}s with an entry for each block. It allows for\n+ * direct jumping to the block, as opposed to iteration from the current position and forward\n+ * one block at a time.\n+ *\n+ * Each long entry consists of 2 logical parts:\n+ *\n+ * The first 31 bits holds the index (number of set bits in the blocks) up to just before the\n+ * wanted block. The next 33 bits holds the offset into the underlying slice.\n+ * As there is a maximum of 2^16 blocks, it follows that the maximum size of any block must\n+ * not exceed 2^17 bits to avoid overflow. This is currently the case, with the largest\n+ * block being DENSE and using 2^16 + 32 bits, and is likely to continue to hold as using\n+ * more than double the amount of bits is unlikely to be an efficient representation.\n+ * The cache overhead is numDocs/1024 bytes.\n+ *\n+ * Note: There are 4 types of blocks: ALL, DENSE, SPARSE and non-existing (0 set bits).\n+ * In the case of non-existing blocks, the entry in the lookup table has index equal to the\n+ * previous entry and offset equal to the next non-empty block.\n+ *\n+ * The block lookup table is stored at the end of the total block structure.\n+ *\n+ *\n+ * The rank structure for DENSE blocks is an array of unsigned {@code short}s with an entry\n+ * for each sub-block of 512 bits out of the 65536 bits in the outer DENSE block.\n+ *\n+ * Each rank-entry states the number of set bits within the block up to the bit before the\n+ * bit positioned at the start of the sub-block.\n+ * Note that that the rank entry of the first sub-block is always 0 and that the last entry can\n+ * at most be 65536-512 = 65024 and thus will always fit into an unsigned short.\n+ *\n+ * The rank structure for a given DENSE block is stored at the beginning of the DENSE block.\n+ * This ensures locality and keeps logistics simple.\n+ *\n+ * @lucene.internal\n+ */\n+final class IndexedDISI extends DocIdSetIterator {\n+\n+  // jump-table time/space trade-offs to consider:\n+  // The block offsets and the block indexes could be stored in more compressed form with\n+  // two PackedInts or two MonotonicDirectReaders.\n+  // The DENSE ranks (128 shorts = 256 bytes) could likewise be compressed. As there is at least\n+  // 4096 set bits in DENSE blocks, there will be at least one rank with 2^12 bits, so it is\n+  // doubtful if there is much to gain here.\n+  \n+  private static final int BLOCK_SIZE = 65536;   // The number of docIDs that a single block represents\n+  static final int BLOCK_BITS = 16;\n+  private static final long BLOCK_INDEX_SHIFT = 33; // Number of bits to shift a lookup entry to get the index\n+  private static final long BLOCK_INDEX_MASK = ~0L << BLOCK_INDEX_SHIFT; // The index bits in a lookup entry\n+  private static final long BLOCK_LOOKUP_MASK = ~BLOCK_INDEX_MASK; // The offset bits in a lookup entry\n+\n+  private static final int RANK_BLOCK_SIZE = 512; // The number of docIDs/bits in each rank-sub-block within a DENSE block\n+  private static final int RANK_BLOCK_LONGS = 512/Long.SIZE; // The number of longs making up a rank-block (8)\n+  private static final int RANK_BLOCK_BITS = 9;\n+  private static final int RANKS_PER_BLOCK = BLOCK_SIZE / RANK_BLOCK_SIZE;\n+\n+  static final int MAX_ARRAY_LENGTH = (1 << 12) - 1;\n+\n+  private final long jumpTableOffset; // If -1, the use of jump-table is disabled\n+  private final long jumpTableEntryCount;\n+\n+  private static void flush(int block, FixedBitSet buffer, int cardinality, IndexOutput out) throws IOException {\n+    assert block >= 0 && block < 65536;\n+    out.writeShort((short) block);\n+    assert cardinality > 0 && cardinality <= 65536;\n+    out.writeShort((short) (cardinality - 1));\n+    if (cardinality > MAX_ARRAY_LENGTH) {\n+      if (cardinality != 65536) { // all docs are set\n+        final short[] rank = createRank(buffer);\n+        for (int i = 0 ; i < rank.length ; i++) {\n+          out.writeShort(rank[i]);\n+        }\n+        for (long word : buffer.getBits()) {\n+          out.writeLong(word);\n+        }\n+      }\n+    } else {\n+      BitSetIterator it = new BitSetIterator(buffer, cardinality);\n+      for (int doc = it.nextDoc(); doc != DocIdSetIterator.NO_MORE_DOCS; doc = it.nextDoc()) {\n+        out.writeShort((short) doc);\n+      }\n+    }\n+  }\n+\n+  // Creates a DENSE rank-entry (the number of set bits up to a given point) for the buffer.\n+  // One rank-entry for every 512 bits/8 longs for a total of 128 shorts.\n+  private static short[] createRank(FixedBitSet buffer) {\n+    final short[] rank = new short[128];\n+    final long[] bits = buffer.getBits();\n+    int bitCount = 0;\n+    for (int word = 0 ; word < 1024 ; word++) {\n+      if (word >> 3 << 3 == word) { // Every 8 longs\n+        rank[word >> 3] = (short)bitCount;\n+      }\n+      bitCount += Long.bitCount(bits[word]);\n+    }\n+    return rank;\n+  }\n+\n+  /**\n+   * Writes the docIDs from it to out, in logical blocks, one for each 65536 docIDs in monotonically\n+   * increasing gap-less order.\n+   * @param it  the document IDs.\n+   * @param out destination for the blocks.\n+   * @throws IOException if there was an error writing to out.\n+   */\n+  static void writeBitSet(DocIdSetIterator it, IndexOutput out) throws IOException {\n+    final long origo = out.getFilePointer(); // All jumps are relative to the origo\n+    int totalCardinality = 0;\n+    int blockCardinality = 0;\n+    final FixedBitSet buffer = new FixedBitSet(1<<16);\n+    long[] jumps = new long[ArrayUtil.oversize(100, Long.BYTES)];\n+    jumps[0] = out.getFilePointer()-origo; // First block starts at index 0\n+    int prevBlock = -1;\n+    int jumpBlockIndex = 0;\n+\n+    for (int doc = it.nextDoc(); doc != DocIdSetIterator.NO_MORE_DOCS; doc = it.nextDoc()) {\n+      final int block = doc >>> 16;\n+      if (prevBlock != -1 && block != prevBlock) {\n+        // Track offset+index from previous block up to current\n+        jumps = addJumps(jumps, out.getFilePointer()-origo, totalCardinality, jumpBlockIndex, prevBlock+1);\n+        jumpBlockIndex = prevBlock+1;\n+        // Flush block\n+        flush(prevBlock, buffer, blockCardinality, out);\n+        // Reset for next block\n+        buffer.clear(0, buffer.length());\n+        totalCardinality += blockCardinality;\n+        blockCardinality = 0;\n+      }\n+      buffer.set(doc & 0xFFFF);\n+      blockCardinality++;\n+      prevBlock = block;\n+    }\n+    if (blockCardinality > 0) {\n+      jumps = addJumps(jumps, out.getFilePointer()-origo, totalCardinality, jumpBlockIndex, prevBlock+1);\n+      flush(prevBlock, buffer, blockCardinality, out);\n+      buffer.clear(0, buffer.length());\n+      prevBlock++;\n+    }\n+    final int lastBlock = prevBlock == -1 ? 0 : prevBlock;\n+//    jumps = addJumps(jumps, out.getFilePointer(), totalCardinality, lastBlock, lastBlock+1);\n+    // NO_MORE_DOCS is stored explicitly\n+    buffer.set(DocIdSetIterator.NO_MORE_DOCS & 0xFFFF);\n+    flush(DocIdSetIterator.NO_MORE_DOCS >>> 16, buffer, 1, out);\n+    // offset+index jump-table stored at the end\n+    flushBlockJumps(jumps, lastBlock, out, origo);\n+  }\n+\n+  // Adds entries to the offset & index jump-table for blocks\n+  private static long[] addJumps(long[] jumps, long offset, long index, int startBlock, int endBlock) {\n+    jumps = ArrayUtil.grow(jumps, endBlock +1);\n+    final long jump = (index << BLOCK_INDEX_SHIFT) | offset;\n+    for (int b = startBlock; b < endBlock; b++) {\n+      jumps[b] = jump;\n+    }\n+    return jumps;\n+  }\n+\n+  // Flushes the offet & index jump-table for blocks. This should be the last data written to out\n+  private static void flushBlockJumps(long[] jumps, int blockCount, IndexOutput out, long origo) throws IOException {\n+    if (blockCount == 1) { // A single jump is just wasted space so we ignore that\n+      blockCount = 0;\n+    }\n+    for (int i = 0 ; i < blockCount ; i++) {\n+      out.writeLong(jumps[i]);\n+    }\n+    // The number of blocks are written as the last data in the IndexedDISI structure.\n+    // This makes it possible to infer the jumpTableOffset: lastPos - #blocks * Long.BYTES\n+    // As there are at most 32k blocks, the count is stored as a short\n+    out.writeShort((short) blockCount);\n+  }\n+\n+  /** The slice that stores the {@link DocIdSetIterator}. */\n+  private final IndexInput slice;\n+  private final long cost;\n+\n+  /**\n+   * @param in backing data.\n+   * @param offset starting offset for blocks in backing data.\n+   * @param length the number of bytes in the backing data.\n+   * @param cost normally the number of logical docIDs.\n+   */\n+  IndexedDISI(IndexInput in, long offset, long length, long cost) throws IOException {\n+    this(in.slice(\"docs\", offset, length), cost);\n+  }\n+\n+  /**\n+   * This constructor allows to pass the slice directly in case it helps reuse.\n+   * see eg. Lucene80 norms producer's merge instance.\n+   * @param slice backing data.\n+   * @param cost normally the number of logical docIDs.\n+   */\n+  IndexedDISI(IndexInput slice, long cost) throws IOException {\n+    this.slice = slice;\n+    this.cost = cost;\n+    origo = slice.getFilePointer();\n+    slice.seek(slice.length()-Short.BYTES);\n+    jumpTableEntryCount = slice.readShort();\n+    jumpTableOffset = jumpTableEntryCount <= 1 ? -1 :\n+        slice.getFilePointer()-Short.BYTES-jumpTableEntryCount*Long.BYTES;\n+    slice.seek(origo);\n+  }\n+\n+  private final long origo;\n+  private int block = -1;\n+  private long blockEnd;\n+  private long rankOrigoOffset = -1; // Only used for DENSE blocks\n+  private int nextBlockIndex = -1;\n+  Method method;\n+\n+  private int doc = -1;\n+  private int index = -1;\n+\n+  // SPARSE variables\n+  boolean exists;\n+\n+  // DENSE variables\n+  private long word;\n+  private int wordIndex = -1;\n+  // number of one bits encountered so far, including those of `word`\n+  private int numberOfOnes;\n+  // Used with rank for jumps inside of DENSE\n+  private int denseOrigoIndex;\n+\n+  // ALL variables\n+  private int gap;\n+\n+  @Override\n+  public int docID() {\n+    return doc;\n+  }\n+\n+  @Override\n+  public int advance(int target) throws IOException {\n+    final int targetBlock = target & 0xFFFF0000;\n+    if (block < targetBlock) {\n+      advanceBlock(targetBlock);\n+    }\n+    if (block == targetBlock) {\n+      if (method.advanceWithinBlock(this, target)) {\n+        return doc;\n+      }\n+      readBlockHeader();\n+    }\n+    boolean found = method.advanceWithinBlock(this, block);\n+    assert found;\n+    return doc;\n+  }\n+\n+  public boolean advanceExact(int target) throws IOException {\n+    final int targetBlock = target & 0xFFFF0000;\n+    if (block < targetBlock) {\n+      advanceBlock(targetBlock);\n+    }\n+    boolean found = block == targetBlock && method.advanceExactWithinBlock(this, target);\n+    this.doc = target;\n+    return found;\n+  }\n+\n+  private void advanceBlock(int targetBlock) throws IOException {\n+    final int blockIndex = targetBlock >> 16;\n+    // If the destination block is 2 blocks or more ahead, we use the jump-table.\n+    if (jumpTableOffset != -1L && blockIndex >= (block >> 16)+2 && blockIndex < jumpTableEntryCount) {\n+      // jumpTableOffset is calculated based on the given slice, so origo should not be added when seeking\n+      slice.seek(jumpTableOffset + Long.BYTES * blockIndex);\n+      final long jumpEntry = slice.readLong();\n+\n+      // Entries in the jumpTableOffset are calculated upon build, so origo should be added to get the correct offset\n+      final long offset = origo+jumpEntry & BLOCK_LOOKUP_MASK;\n+      final long index = jumpEntry >>> BLOCK_INDEX_SHIFT;\n+      this.nextBlockIndex = (int) (index - 1); // -1 to compensate for the always-added 1 in readBlockHeader\n+      slice.seek(offset);\n+      readBlockHeader();\n+      return;\n+    }\n+\n+    // Fallback to iteration of blocks\n+    do {\n+      slice.seek(blockEnd);\n+      readBlockHeader();\n+    } while (block < targetBlock);\n+  }\n+\n+  private void readBlockHeader() throws IOException {\n+    block = Short.toUnsignedInt(slice.readShort()) << 16;\n+    assert block >= 0;\n+    final int numValues = 1 + Short.toUnsignedInt(slice.readShort());\n+    index = nextBlockIndex;\n+    nextBlockIndex = index + numValues;\n+    if (numValues <= MAX_ARRAY_LENGTH) {\n+      method = Method.SPARSE;\n+      blockEnd = slice.getFilePointer() + (numValues << 1);\n+    } else if (numValues == 65536) {\n+      method = Method.ALL;\n+      blockEnd = slice.getFilePointer();\n+      gap = block - index - 1;\n+    } else {\n+      method = Method.DENSE;\n+      blockEnd = slice.getFilePointer() + RANKS_PER_BLOCK*Short.BYTES + (1 << 13);\n+      rankOrigoOffset = slice.getFilePointer();\n+      // Performance consideration: All rank (128 shorts) could be loaded up front, but that would be wasted if the\n+      // DENSE block is iterated in steps less than 512 bits. As the whole point of rank in DENSE is to speed up\n+      // large jumps, it seems counter-intuitive to have a non-trivial up-front cost as chances are only few of the\n+      // rank entries will be used.\n+      slice.seek(rankOrigoOffset + RANKS_PER_BLOCK*Short.BYTES); // Position at DENSE block bitmap start\n+      wordIndex = -1;\n+      numberOfOnes = index + 1;\n+      denseOrigoIndex = numberOfOnes;\n+    }\n+  }\n+\n+  @Override\n+  public int nextDoc() throws IOException {\n+    return advance(doc + 1);\n+  }\n+\n+  public int index() {\n+    return index;\n+  }\n+\n+  @Override\n+  public long cost() {\n+    return cost;\n+  }\n+\n+  enum Method {\n+    SPARSE {\n+      @Override\n+      boolean advanceWithinBlock(IndexedDISI disi, int target) throws IOException {\n+        final int targetInBlock = target & 0xFFFF;\n+        // TODO: binary search\n+        for (; disi.index < disi.nextBlockIndex;) {\n+          int doc = Short.toUnsignedInt(disi.slice.readShort());\n+          disi.index++;\n+          if (doc >= targetInBlock) {\n+            disi.doc = disi.block | doc;\n+            disi.exists = true;\n+            return true;\n+          }\n+        }\n+        return false;\n+      }\n+      @Override\n+      boolean advanceExactWithinBlock(IndexedDISI disi, int target) throws IOException {\n+        final int targetInBlock = target & 0xFFFF;\n+        // TODO: binary search\n+        if (target == disi.doc) {\n+          return disi.exists;\n+        }\n+        for (; disi.index < disi.nextBlockIndex;) {\n+          int doc = Short.toUnsignedInt(disi.slice.readShort());\n+          disi.index++;\n+          if (doc >= targetInBlock) {\n+            if (doc != targetInBlock) {\n+              disi.index--;\n+              disi.slice.seek(disi.slice.getFilePointer() - Short.BYTES);\n+              break;\n+            }\n+            disi.exists = true;\n+            return true;\n+          }\n+        }\n+        disi.exists = false;\n+        return false;\n+      }\n+    },\n+    DENSE {\n+      @Override\n+      boolean advanceWithinBlock(IndexedDISI disi, int target) throws IOException {\n+        final int targetInBlock = target & 0xFFFF;\n+        final int targetWordIndex = targetInBlock >>> 6;\n+\n+        // If possible, skip ahead using the rank cache\n+        rankSkip(disi, target);\n+\n+        for (int i = disi.wordIndex + 1; i <= targetWordIndex; ++i) {\n+          disi.word = disi.slice.readLong();\n+          disi.numberOfOnes += Long.bitCount(disi.word);\n+        }\n+        disi.wordIndex = targetWordIndex;\n+\n+        long leftBits = disi.word >>> target;\n+        if (leftBits != 0L) {\n+          disi.doc = target + Long.numberOfTrailingZeros(leftBits);\n+          disi.index = disi.numberOfOnes - Long.bitCount(leftBits);\n+          return true;\n+        }\n+\n+        // There were no set bits at the wanted position. Move forward until one is reached\n+        while (++disi.wordIndex < 1024) {\n+          // This could use the rank cache to skip empty spaces >= 512 bits, but it seems unrealistic\n+          // that such blocks would be DENSE\n+          disi.word = disi.slice.readLong();\n+          if (disi.word != 0) {\n+            disi.index = disi.numberOfOnes;\n+            disi.numberOfOnes += Long.bitCount(disi.word);\n+            disi.doc = disi.block | (disi.wordIndex << 6) | Long.numberOfTrailingZeros(disi.word);\n+            return true;\n+          }\n+        }\n+        // No set bits in the block at or after the wanted position.\n+        return false;\n+      }\n+\n+      @Override\n+      boolean advanceExactWithinBlock(IndexedDISI disi, int target) throws IOException {\n+        final int targetInBlock = target & 0xFFFF;\n+        final int targetWordIndex = targetInBlock >>> 6;\n+\n+        // If possible, skip ahead using the rank cache\n+        rankSkip(disi, target);\n+\n+        for (int i = disi.wordIndex + 1; i <= targetWordIndex; ++i) {\n+          disi.word = disi.slice.readLong();\n+          disi.numberOfOnes += Long.bitCount(disi.word);\n+        }\n+        disi.wordIndex = targetWordIndex;\n+\n+        long leftBits = disi.word >>> target;\n+        disi.index = disi.numberOfOnes - Long.bitCount(leftBits);\n+        return (leftBits & 1L) != 0;\n+      }\n+\n+\n+    },\n+    ALL {\n+      @Override\n+      boolean advanceWithinBlock(IndexedDISI disi, int target) throws IOException {\n+        disi.doc = target;\n+        disi.index = target - disi.gap;\n+        return true;\n+      }\n+      @Override\n+      boolean advanceExactWithinBlock(IndexedDISI disi, int target) throws IOException {\n+        disi.index = target - disi.gap;\n+        return true;\n+      }\n+    };\n+\n+    /** Advance to the first doc from the block that is equal to or greater than {@code target}.\n+     *  Return true if there is such a doc and false otherwise. */\n+    abstract boolean advanceWithinBlock(IndexedDISI disi, int target) throws IOException;\n+\n+    /** Advance the iterator exactly to the position corresponding to the given {@code target}\n+     * and return whether this document exists. */\n+    abstract boolean advanceExactWithinBlock(IndexedDISI disi, int target) throws IOException;\n+  }\n+\n+  /**\n+   * If the distance between the current position and the target is > 8 words, the rank cache will\n+   * be used to guarantee a worst-case of 1 rank-lookup and 7 word-read-and-count-bits operations.\n+   * Note: This does not guarantee a skip up to target, only up to nearest rank boundary. It is the\n+   * responsibility of the caller to iterate further to reach target.\n+   * @param disi standard DISI.\n+   * @param target the wanted docID for which to calculate set-flag and index.\n+   * @throws IOException if a DISI seek failed.\n+   */\n+  private static void rankSkip(IndexedDISI disi, int target) throws IOException {\n+    final int targetInBlock = target & 0xFFFF;       // Lower 16 bits\n+    final int targetWordIndex = targetInBlock >>> 6; // long: 2^6 = 64\n+\n+    // If the distance between the current position and the target is < 8 longs\n+    // there is no sense in using rank\n+    if (targetWordIndex - disi.wordIndex < RANK_BLOCK_LONGS) {\n+      return;\n+    }\n+\n+    // Resolve the rank as close to targetInBlock as possible (maximum distance is 8 longs)\n+    // Note: rankOrigoOffset is tracked on block open, so it is absolute (e.g. don't add origo)\n+    final int rankIndex = targetInBlock >> RANK_BLOCK_BITS; // 8 longs: 2^3 * 2^6 = 512\n+    disi.slice.seek(disi.rankOrigoOffset + rankIndex*Short.BYTES);","path":"lucene/core/src/java/org/apache/lucene/codecs/lucene80/IndexedDISI.java","position":null,"original_position":523,"commit_id":"5f425d3959ca7ce4ea7d9027eae6a37ded800b6b","original_commit_id":"951d302604bb37d2eeb90b360d4f48ec11ada927","user":{"login":"tokee","id":199454,"node_id":"MDQ6VXNlcjE5OTQ1NA==","avatar_url":"https://avatars1.githubusercontent.com/u/199454?v=4","gravatar_id":"","url":"https://api.github.com/users/tokee","html_url":"https://github.com/tokee","followers_url":"https://api.github.com/users/tokee/followers","following_url":"https://api.github.com/users/tokee/following{/other_user}","gists_url":"https://api.github.com/users/tokee/gists{/gist_id}","starred_url":"https://api.github.com/users/tokee/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/tokee/subscriptions","organizations_url":"https://api.github.com/users/tokee/orgs","repos_url":"https://api.github.com/users/tokee/repos","events_url":"https://api.github.com/users/tokee/events{/privacy}","received_events_url":"https://api.github.com/users/tokee/received_events","type":"User","site_admin":false},"body":"This is a hard one and I am not sure we can find a single solution that works best for all scenarios. And there are so many possibilities:\r\n\r\n1. Allocate a slice for DENSE-rank: We already use many slices.\r\n1. Make DENSE-rank and block-jump share the same slice. This thrashes the block-jump cache when a DENSE-rank lookup is needed, but not the other way as the need for skipping to a new block means that the DENSE block has been exhausted.\r\n1. Don't have a special slice for DENSE-rank. A DENSE block is about 2 * 8192 bytes, so jumps within the first half would not mean thrashing.\r\n1. Load all 128 shorts up front: Wasted if skips are < 512 docIDs or there is only a single (or possibly very few) lookups in the DENSE block.\r\n1. Increase `RANK_BLOCK_SIZE`: A fair suggestion as the current 1 rank/8 longs is somewhat arbitrary. The concrete choice comes down to how large the average advance is and we have little knowledge there (at least I don't). It is still \"only\" a mitigation of the potentially-wasted-overhead problem.\r\n1. Use heuristics: Load the 128 shorts on first advance within the DENSE block, if the advance is > `RANK_BLOCK_SIZE` and < X, where we choose X so that we guess there will only be a single advance (maybe 32768?). Makes the logic more complicated and branchy.\r\n1. Interleave the ranking with the bits. This would make the math more complicated and probably require division and/or hurt single-docID-stepping. I'll think a bit about this and see if there is a way to do it cleanly.","created_at":"2018-12-17T13:38:05Z","updated_at":"2018-12-17T13:38:05Z","html_url":"https://github.com/apache/lucene-solr/pull/525#discussion_r242148673","pull_request_url":"https://api.github.com/repos/apache/lucene-solr/pulls/525","author_association":"NONE","_links":{"self":{"href":"https://api.github.com/repos/apache/lucene-solr/pulls/comments/242148673"},"html":{"href":"https://github.com/apache/lucene-solr/pull/525#discussion_r242148673"},"pull_request":{"href":"https://api.github.com/repos/apache/lucene-solr/pulls/525"}},"in_reply_to_id":241784900},"pull_request":{"url":"https://api.github.com/repos/apache/lucene-solr/pulls/525","id":238061859,"node_id":"MDExOlB1bGxSZXF1ZXN0MjM4MDYxODU5","html_url":"https://github.com/apache/lucene-solr/pull/525","diff_url":"https://github.com/apache/lucene-solr/pull/525.diff","patch_url":"https://github.com/apache/lucene-solr/pull/525.patch","issue_url":"https://api.github.com/repos/apache/lucene-solr/issues/525","number":525,"state":"open","locked":false,"title":"LUCENE-8585: Index-time jump-tables for DocValues","user":{"login":"tokee","id":199454,"node_id":"MDQ6VXNlcjE5OTQ1NA==","avatar_url":"https://avatars1.githubusercontent.com/u/199454?v=4","gravatar_id":"","url":"https://api.github.com/users/tokee","html_url":"https://github.com/tokee","followers_url":"https://api.github.com/users/tokee/followers","following_url":"https://api.github.com/users/tokee/following{/other_user}","gists_url":"https://api.github.com/users/tokee/gists{/gist_id}","starred_url":"https://api.github.com/users/tokee/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/tokee/subscriptions","organizations_url":"https://api.github.com/users/tokee/orgs","repos_url":"https://api.github.com/users/tokee/repos","events_url":"https://api.github.com/users/tokee/events{/privacy}","received_events_url":"https://api.github.com/users/tokee/received_events","type":"User","site_admin":false},"body":"First complete attempt of LUCENE-8585, with all jump-tables at index-time and with the not-used-anymore lucene70 codec classes moved to backward-codecs.","created_at":"2018-12-12T14:43:48Z","updated_at":"2018-12-17T13:38:05Z","closed_at":null,"merged_at":null,"merge_commit_sha":"7ce04e77340d3e857ab57ba5a64795a3a17a2e54","assignee":null,"assignees":[],"requested_reviewers":[],"requested_teams":[],"labels":[],"milestone":null,"commits_url":"https://api.github.com/repos/apache/lucene-solr/pulls/525/commits","review_comments_url":"https://api.github.com/repos/apache/lucene-solr/pulls/525/comments","review_comment_url":"https://api.github.com/repos/apache/lucene-solr/pulls/comments{/number}","comments_url":"https://api.github.com/repos/apache/lucene-solr/issues/525/comments","statuses_url":"https://api.github.com/repos/apache/lucene-solr/statuses/5f425d3959ca7ce4ea7d9027eae6a37ded800b6b","head":{"label":"tokee:lucene8585_p1","ref":"lucene8585_p1","sha":"5f425d3959ca7ce4ea7d9027eae6a37ded800b6b","user":{"login":"tokee","id":199454,"node_id":"MDQ6VXNlcjE5OTQ1NA==","avatar_url":"https://avatars1.githubusercontent.com/u/199454?v=4","gravatar_id":"","url":"https://api.github.com/users/tokee","html_url":"https://github.com/tokee","followers_url":"https://api.github.com/users/tokee/followers","following_url":"https://api.github.com/users/tokee/following{/other_user}","gists_url":"https://api.github.com/users/tokee/gists{/gist_id}","starred_url":"https://api.github.com/users/tokee/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/tokee/subscriptions","organizations_url":"https://api.github.com/users/tokee/orgs","repos_url":"https://api.github.com/users/tokee/repos","events_url":"https://api.github.com/users/tokee/events{/privacy}","received_events_url":"https://api.github.com/users/tokee/received_events","type":"User","site_admin":false},"repo":{"id":161501238,"node_id":"MDEwOlJlcG9zaXRvcnkxNjE1MDEyMzg=","name":"lucene-solr-1","full_name":"tokee/lucene-solr-1","private":false,"owner":{"login":"tokee","id":199454,"node_id":"MDQ6VXNlcjE5OTQ1NA==","avatar_url":"https://avatars1.githubusercontent.com/u/199454?v=4","gravatar_id":"","url":"https://api.github.com/users/tokee","html_url":"https://github.com/tokee","followers_url":"https://api.github.com/users/tokee/followers","following_url":"https://api.github.com/users/tokee/following{/other_user}","gists_url":"https://api.github.com/users/tokee/gists{/gist_id}","starred_url":"https://api.github.com/users/tokee/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/tokee/subscriptions","organizations_url":"https://api.github.com/users/tokee/orgs","repos_url":"https://api.github.com/users/tokee/repos","events_url":"https://api.github.com/users/tokee/events{/privacy}","received_events_url":"https://api.github.com/users/tokee/received_events","type":"User","site_admin":false},"html_url":"https://github.com/tokee/lucene-solr-1","description":"Mirror of Apache Lucene + Solr","fork":true,"url":"https://api.github.com/repos/tokee/lucene-solr-1","forks_url":"https://api.github.com/repos/tokee/lucene-solr-1/forks","keys_url":"https://api.github.com/repos/tokee/lucene-solr-1/keys{/key_id}","collaborators_url":"https://api.github.com/repos/tokee/lucene-solr-1/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/tokee/lucene-solr-1/teams","hooks_url":"https://api.github.com/repos/tokee/lucene-solr-1/hooks","issue_events_url":"https://api.github.com/repos/tokee/lucene-solr-1/issues/events{/number}","events_url":"https://api.github.com/repos/tokee/lucene-solr-1/events","assignees_url":"https://api.github.com/repos/tokee/lucene-solr-1/assignees{/user}","branches_url":"https://api.github.com/repos/tokee/lucene-solr-1/branches{/branch}","tags_url":"https://api.github.com/repos/tokee/lucene-solr-1/tags","blobs_url":"https://api.github.com/repos/tokee/lucene-solr-1/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/tokee/lucene-solr-1/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/tokee/lucene-solr-1/git/refs{/sha}","trees_url":"https://api.github.com/repos/tokee/lucene-solr-1/git/trees{/sha}","statuses_url":"https://api.github.com/repos/tokee/lucene-solr-1/statuses/{sha}","languages_url":"https://api.github.com/repos/tokee/lucene-solr-1/languages","stargazers_url":"https://api.github.com/repos/tokee/lucene-solr-1/stargazers","contributors_url":"https://api.github.com/repos/tokee/lucene-solr-1/contributors","subscribers_url":"https://api.github.com/repos/tokee/lucene-solr-1/subscribers","subscription_url":"https://api.github.com/repos/tokee/lucene-solr-1/subscription","commits_url":"https://api.github.com/repos/tokee/lucene-solr-1/commits{/sha}","git_commits_url":"https://api.github.com/repos/tokee/lucene-solr-1/git/commits{/sha}","comments_url":"https://api.github.com/repos/tokee/lucene-solr-1/comments{/number}","issue_comment_url":"https://api.github.com/repos/tokee/lucene-solr-1/issues/comments{/number}","contents_url":"https://api.github.com/repos/tokee/lucene-solr-1/contents/{+path}","compare_url":"https://api.github.com/repos/tokee/lucene-solr-1/compare/{base}...{head}","merges_url":"https://api.github.com/repos/tokee/lucene-solr-1/merges","archive_url":"https://api.github.com/repos/tokee/lucene-solr-1/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/tokee/lucene-solr-1/downloads","issues_url":"https://api.github.com/repos/tokee/lucene-solr-1/issues{/number}","pulls_url":"https://api.github.com/repos/tokee/lucene-solr-1/pulls{/number}","milestones_url":"https://api.github.com/repos/tokee/lucene-solr-1/milestones{/number}","notifications_url":"https://api.github.com/repos/tokee/lucene-solr-1/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/tokee/lucene-solr-1/labels{/name}","releases_url":"https://api.github.com/repos/tokee/lucene-solr-1/releases{/id}","deployments_url":"https://api.github.com/repos/tokee/lucene-solr-1/deployments","created_at":"2018-12-12T14:39:12Z","updated_at":"2018-12-12T14:39:55Z","pushed_at":"2018-12-17T12:42:42Z","git_url":"git://github.com/tokee/lucene-solr-1.git","ssh_url":"git@github.com:tokee/lucene-solr-1.git","clone_url":"https://github.com/tokee/lucene-solr-1.git","svn_url":"https://github.com/tokee/lucene-solr-1","homepage":null,"size":378998,"stargazers_count":0,"watchers_count":0,"language":"Java","has_issues":false,"has_projects":true,"has_downloads":true,"has_wiki":false,"has_pages":false,"forks_count":0,"mirror_url":null,"archived":false,"open_issues_count":0,"license":null,"forks":0,"open_issues":0,"watchers":0,"default_branch":"master"}},"base":{"label":"apache:master","ref":"master","sha":"7e4555a2fdb863d6aac2f785116f8f13e51bf16b","user":{"login":"apache","id":47359,"node_id":"MDEyOk9yZ2FuaXphdGlvbjQ3MzU5","avatar_url":"https://avatars0.githubusercontent.com/u/47359?v=4","gravatar_id":"","url":"https://api.github.com/users/apache","html_url":"https://github.com/apache","followers_url":"https://api.github.com/users/apache/followers","following_url":"https://api.github.com/users/apache/following{/other_user}","gists_url":"https://api.github.com/users/apache/gists{/gist_id}","starred_url":"https://api.github.com/users/apache/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/apache/subscriptions","organizations_url":"https://api.github.com/users/apache/orgs","repos_url":"https://api.github.com/users/apache/repos","events_url":"https://api.github.com/users/apache/events{/privacy}","received_events_url":"https://api.github.com/users/apache/received_events","type":"Organization","site_admin":false},"repo":{"id":50229487,"node_id":"MDEwOlJlcG9zaXRvcnk1MDIyOTQ4Nw==","name":"lucene-solr","full_name":"apache/lucene-solr","private":false,"owner":{"login":"apache","id":47359,"node_id":"MDEyOk9yZ2FuaXphdGlvbjQ3MzU5","avatar_url":"https://avatars0.githubusercontent.com/u/47359?v=4","gravatar_id":"","url":"https://api.github.com/users/apache","html_url":"https://github.com/apache","followers_url":"https://api.github.com/users/apache/followers","following_url":"https://api.github.com/users/apache/following{/other_user}","gists_url":"https://api.github.com/users/apache/gists{/gist_id}","starred_url":"https://api.github.com/users/apache/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/apache/subscriptions","organizations_url":"https://api.github.com/users/apache/orgs","repos_url":"https://api.github.com/users/apache/repos","events_url":"https://api.github.com/users/apache/events{/privacy}","received_events_url":"https://api.github.com/users/apache/received_events","type":"Organization","site_admin":false},"html_url":"https://github.com/apache/lucene-solr","description":"Mirror of Apache Lucene + Solr","fork":false,"url":"https://api.github.com/repos/apache/lucene-solr","forks_url":"https://api.github.com/repos/apache/lucene-solr/forks","keys_url":"https://api.github.com/repos/apache/lucene-solr/keys{/key_id}","collaborators_url":"https://api.github.com/repos/apache/lucene-solr/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/apache/lucene-solr/teams","hooks_url":"https://api.github.com/repos/apache/lucene-solr/hooks","issue_events_url":"https://api.github.com/repos/apache/lucene-solr/issues/events{/number}","events_url":"https://api.github.com/repos/apache/lucene-solr/events","assignees_url":"https://api.github.com/repos/apache/lucene-solr/assignees{/user}","branches_url":"https://api.github.com/repos/apache/lucene-solr/branches{/branch}","tags_url":"https://api.github.com/repos/apache/lucene-solr/tags","blobs_url":"https://api.github.com/repos/apache/lucene-solr/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/apache/lucene-solr/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/apache/lucene-solr/git/refs{/sha}","trees_url":"https://api.github.com/repos/apache/lucene-solr/git/trees{/sha}","statuses_url":"https://api.github.com/repos/apache/lucene-solr/statuses/{sha}","languages_url":"https://api.github.com/repos/apache/lucene-solr/languages","stargazers_url":"https://api.github.com/repos/apache/lucene-solr/stargazers","contributors_url":"https://api.github.com/repos/apache/lucene-solr/contributors","subscribers_url":"https://api.github.com/repos/apache/lucene-solr/subscribers","subscription_url":"https://api.github.com/repos/apache/lucene-solr/subscription","commits_url":"https://api.github.com/repos/apache/lucene-solr/commits{/sha}","git_commits_url":"https://api.github.com/repos/apache/lucene-solr/git/commits{/sha}","comments_url":"https://api.github.com/repos/apache/lucene-solr/comments{/number}","issue_comment_url":"https://api.github.com/repos/apache/lucene-solr/issues/comments{/number}","contents_url":"https://api.github.com/repos/apache/lucene-solr/contents/{+path}","compare_url":"https://api.github.com/repos/apache/lucene-solr/compare/{base}...{head}","merges_url":"https://api.github.com/repos/apache/lucene-solr/merges","archive_url":"https://api.github.com/repos/apache/lucene-solr/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/apache/lucene-solr/downloads","issues_url":"https://api.github.com/repos/apache/lucene-solr/issues{/number}","pulls_url":"https://api.github.com/repos/apache/lucene-solr/pulls{/number}","milestones_url":"https://api.github.com/repos/apache/lucene-solr/milestones{/number}","notifications_url":"https://api.github.com/repos/apache/lucene-solr/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/apache/lucene-solr/labels{/name}","releases_url":"https://api.github.com/repos/apache/lucene-solr/releases{/id}","deployments_url":"https://api.github.com/repos/apache/lucene-solr/deployments","created_at":"2016-01-23T08:00:06Z","updated_at":"2018-12-17T12:03:25Z","pushed_at":"2018-12-17T12:42:46Z","git_url":"git://github.com/apache/lucene-solr.git","ssh_url":"git@github.com:apache/lucene-solr.git","clone_url":"https://github.com/apache/lucene-solr.git","svn_url":"https://github.com/apache/lucene-solr","homepage":null,"size":379877,"stargazers_count":2163,"watchers_count":2163,"language":"Java","has_issues":false,"has_projects":true,"has_downloads":true,"has_wiki":false,"has_pages":false,"forks_count":1637,"mirror_url":null,"archived":false,"open_issues_count":262,"license":null,"forks":1637,"open_issues":262,"watchers":2163,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/apache/lucene-solr/pulls/525"},"html":{"href":"https://github.com/apache/lucene-solr/pull/525"},"issue":{"href":"https://api.github.com/repos/apache/lucene-solr/issues/525"},"comments":{"href":"https://api.github.com/repos/apache/lucene-solr/issues/525/comments"},"review_comments":{"href":"https://api.github.com/repos/apache/lucene-solr/pulls/525/comments"},"review_comment":{"href":"https://api.github.com/repos/apache/lucene-solr/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/apache/lucene-solr/pulls/525/commits"},"statuses":{"href":"https://api.github.com/repos/apache/lucene-solr/statuses/5f425d3959ca7ce4ea7d9027eae6a37ded800b6b"}},"author_association":"NONE"}}
{"actor":{"display_login":"tokee"}}