Block-Max Indexes

Storing an upper bound for every block of a postings list, and using it to skip without losing exactness. Why putting block maxima straight into WAND's pivot test is unsafe, Block-Max WAND with shallow and deep cursor movements, a proof of safety carried over from the lemma for MaxScore and WAND, a full trace on five Reuters lists, what skipping needs from the layout of an index, and what the block maxima cost and save on Reuters-21578 and on this site's index. Worked problems break the unsafe shortcut on a two-list example, work one block check by hand, and price the metadata.

In the previous article, WAND answered the Reuters query palladium platinum nickel bullion krugerrand by judging each postings list by one number, its largest contribution anywhere. For platinum that number is 11.8369. It is reached in story 1521, and the list's first four postings never contribute more than 6.7243. A bound that describes the best posting of a list is a poor description of most of the list. Can each stretch of a list carry its own bound, and can WAND use those bounds without losing the guarantee that it returns exactly the top $k$?

It can, with one change to the index and a careful change to the algorithm. A block-max index (Ding and Suel, 2011) cuts every postings list into blocks of a fixed number of postings and stores, for each block, the largest contribution among its postings. Block-Max WAND is WAND with a second test on those block maxima. The care is needed because the most obvious way to use the new numbers is wrong, as a five-posting example below shows.

Here is the route. First we define the index and look at what it adds to a layout that compressed indexes already have. Then we see the unsafe shortcut fail, state Block-Max WAND, trace it on the running example and prove it safe. Next comes what the method needs from the index and what the extra numbers cost. Finally we count postings scored and postings decoded on Reuters-21578 and on this site's index. The article assumes dynamic pruning with MaxScore and WAND: its setting, its notation, its safety lemma and its statement of WAND are used here without being repeated. The numbers are computed by tools/experiments/query-processing/block-max-indexes.py, which asserts on every query and every block size that the result equals the exhaustive top $k$.

One more number per block

Compressed postings lists are already stored in blocks. Skip pointers described the layout. Postings are packed in blocks of, say, 64 or 128, and a small table keeps the last docID of each block, so that an intersection can pass over a whole block without decoding it. Modern postings compression works the codes that fill the blocks. Ding and Suel add one entry to that table. In their words, the block-max index "stores the maximum impact score for each block of a compressed inverted list in uncompressed form".

Write $U_{t,j}$ for the block upper bound of block $j$ of the list of term $t$: the largest contribution $s_t(d)$ among the postings of that block. The list's upper bound $U_t$ of the previous article is the largest of its block bounds. With blocks of 4 postings, the five lists of the running example become:

List Block docIDs Last docID Block maximum
palladium 1 1467, 1521, 1792, 1795 1795 11.6261
palladium 2 8079 8079 10.8247
platinum 1 179, 260, 358, 400 400 6.7243
platinum 2 1467, 1521, 1792, 1795 1795 11.8369
platinum 3 2224, 3686, 5361, 7392 7392 11.1748
platinum 4 8079, 8515, 8567, 9254 9254 11.7725
platinum 5 9403, 9561, 9709 9709 10.8976
nickel 1 601, 1467, 1521, 2645 2645 11.4768
nickel 2 3192, 4071, 5209, 5876 5876 7.7317
nickel 3 6113, 6518, 7189, 7662 7662 11.9005
nickel 4 7820 7820 10.9351
bullion 1 351, 983, 2070, 2230 2230 10.6555
bullion 2 2442, 3773, 5605, 5637 5637 5.6283
bullion 3 5646, 6033, 6418, 8459 8459 9.2255
bullion 4 8515, 9403 9403 9.3763
krugerrand 1 2442, 5646 5646 5.5680

Some blocks are far below their list's bound. The second block of bullion tops out at 5.6283 against the list's 10.6555, and the second block of nickel at 7.7317 against 11.9005. Others are not: a block that holds a list's best posting has the list's bound.

The block table defines a block's range of docIDs without reference to its contents. Block $j$ covers the docIDs greater than the last docID of block $j - 1$ and at most its own last docID. Every docID up to the list's last one falls in the range of exactly one block, whether or not the list contains it. If the list does contain it, its posting is in that block. So for any docID $d$, the table alone gives a bound on $s_t(d)$: the maximum of the block whose range holds $d$, or zero if $d$ is beyond the list's last docID. Looking that block up needs no decoding. Ding and Suel call it a shallow movement, as against the deep movement of a cursor, which lands on a posting and must decode its block.

The BM25 contributions of the 1,038 postings of the Reuters list for oil (dots), the list's upper bound (dashed line) and the maxima of its 17 blocks of 64 postings (stepped line). Notice how little room there is between the steps and the dashed line: every block of 64 holds some short story in which the term scores close to the list's best, so even the lowest block maximum, 4.19 in the short last block, is nine tenths of the upper bound, 4.64, while the mean contribution of a posting is about 3.
The BM25 contributions of the 1,038 postings of the Reuters list for oil (dots), the list's upper bound (dashed line) and the maxima of its 17 blocks of 64 postings (stepped line). Notice how little room there is between the steps and the dashed line: every block of 64 holds some short story in which the term scores close to the list's best, so even the lowest block maximum, 4.19 in the short last block, is nine tenths of the upper bound, 4.64, while the mean contribution of a posting is about 3.

The shortcut that is not safe

WAND orders the cursors by docID and adds up list bounds until the sum exceeds $\theta$. The obvious improvement is to add up, in that loop, the maximum of the block each cursor is currently in. Ding and Suel (2011, section 3) warn that this "does not guarantee correctness", and a small example with whole-number contributions shows why.

List $a$ has the postings 2: 1, 3: 1, 6: 5, 7: 1 (docID: contribution), and list $b$ has 1: 4, 9: 4. With blocks of two postings, $a$ has the blocks (2, 3) with maximum 1 and (6, 7) with maximum 5, and $b$ has one block with maximum 4. The exhaustive scores are 4, 1, 1, 5, 1 and 4 for documents 1, 2, 3, 6, 7 and 9, so the top 1 is document 6 with score 5.

Run the shortcut with $k = 1$. Document 1 is scored first: 4, so $\theta = 4$. Now the cursor of $a$ is on document 2, in a block with maximum 1, and the cursor of $b$ is on document 9. In cursor order the sums of current block maxima are 1, which does not exceed 4, and then $1 + 4 = 5$, which does. The pivot is document 9. So the cursor of $a$ is moved to its first posting at or after 9, and the list is exhausted. Document 6 has been jumped over. Only $b$ remains, its bound 4 does not exceed $\theta$, and the shortcut returns document 1 with score 4. That is the wrong answer.

The error is in what the sum was taken to mean. The pivot test must bound the score of every document below the pivot. The maximum of the block that the cursor of $a$ is in bounds only the documents in that block's range, 2 and 3. Document 6 is below the pivot but in the next block, whose maximum is 5. A block maximum says nothing about documents outside its own range. The correct algorithm keeps the list bounds for choosing the pivot, where the claim is about a whole stretch of the list, and uses block maxima only for docIDs known to lie in the ranges of the blocks consulted.

Block-Max WAND

Here is the idea in one sentence: find the pivot as WAND does, then ask the block tables whether any document from the pivot up to the nearest block boundary could beat the threshold. If none could, jump past that boundary without decoding anything.

The algorithm follows Ding and Suel (2011, Algorithm 1) and the version in Tonellotto, Macdonald and Ounis (2018, Algorithm 3.3). It repeats these steps with the lists that are not exhausted.

  1. Order the lists by the docID under their cursor, and find the pivot position $p$ and the pivot $\pi$ exactly as in WAND, with the list bounds $U_t$ and with lists on the same docID kept in query order. If there is no pivot, stop. Then extend $p$ to include every later list whose cursor is also on $\pi$.
  2. For each list in positions 1 to $p$, look up the block whose range holds $\pi$. Let $\beta$ be the sum of the maxima of those blocks (a list with no docID as large as $\pi$ adds nothing), and let $e$ be the smallest of their last docIDs.
  3. If $\beta > \theta$ and every cursor in positions 1 to $p$ is on $\pi$: score $\pi$ in those lists, advance their cursors by one posting, and offer $\pi$ with its score.
  4. If $\beta > \theta$ and some cursor in those positions is below $\pi$: move one such cursor to its first posting at or after $\pi$, as WAND does.
  5. If $\beta \le \theta$: let $d'$ be the smaller of $e + 1$ and the docID under the cursor in position $p + 1$, if there is one. Choose a list in positions 1 to $p$ and move its cursor to its first posting at or after $d'$.

Step 5 is the new one. When the block maxima at the pivot do not add up to more than $\theta$, the pivot document cannot qualify. Neither can any document after it up to $e$, the first place where one of the blocks ends: all of those documents lie in the ranges of the same blocks. And no list beyond position $p$ can reach them before its own cursor position. So one cursor may jump to $d'$, which is always beyond the pivot. In WAND the same cursor could have moved only to the pivot. The version traced here moves the list with the largest upper bound among positions 1 to $p$, the counterpart of the choice by largest IDF that Ding and Suel describe. In the branch of step 4, Ding and Suel's listing moves the list to the docID after the pivot. We move it to the pivot, as WAND and the version of Tonellotto, Macdonald and Ounis do. A move beyond the pivot could pass a posting of a document that has just passed the block test, and the proof below needs that not to happen. Their algorithm also stops scoring a document partway when its partial score shows it cannot qualify. The version here scores in full, which keeps the proof short and changes no result.

The trace

With $k = 2$ and blocks of 4, the first nine steps score the same nine stories as WAND did, and the threshold reaches 31.2542. The column $\beta$ is the sum of block maxima of step 2.

Step Cursors: pal, pla, nic, bul, kru Pivot Sum of block maxima Action
1 1467 179 601 351 2442 179 6.7243 score 4.9434, enters
2 1467 260 601 351 2442 260 6.7243 score 6.5295, enters
3 1467 358 601 351 2442 351 10.6555 score 10.6555, enters
4 1467 358 601 983 2442 358 6.7243 score 4.0756, rejected
5 1467 400 601 983 2442 400 6.7243 score 6.7243, enters
6 1467 1467 601 983 2442 601 11.4768 score 5.2176, rejected
7 1467 1467 1467 983 2442 983 10.6555 score 6.3249, rejected
8 1467 1467 1467 2070 2442 1467 34.9398 score 31.2542, enters
9 1521 1521 1521 2070 2442 1521 34.9398 score 31.3290, enters
10 1792 1792 2645 2070 2442 2070 32.6550 move pla to the pivot
11 1792 2224 2645 2070 2442 2224 32.6550 move bul to the pivot
12 1792 2224 2645 2230 2442 2230 32.6550 move pla to the pivot
13 1792 3686 2645 2230 2442 2645 33.4978 move kru to the pivot
14 1792 3686 2645 2230 5646 2645 27.9298 ≤ $\theta$: move nic to 2646
15 1792 3686 3192 2230 5646 3192 24.1847 ≤ $\theta$: move nic to 3686
16 1792 3686 4071 2230 5646 3686 27.6278 ≤ $\theta$: move pla to 4071
17 1792 5361 4071 2230 5646 4071 24.1847 ≤ $\theta$: move nic to 5361
18 1792 5361 5876 2230 5646 5361 27.6278 ≤ $\theta$: move pla to 5638
19 1792 7392 5876 2230 5646 5876 27.7819 ≤ $\theta$: move nic to 5877
20 1792 7392 6113 2230 5646 6113 31.9507 move kru to the pivot
21 1792 7392 6113 2230 end 6113 31.9507 move bul to the pivot
22 1792 7392 6113 6418 end 6418 31.9507 move nic to the pivot
23 1792 7392 6518 6418 end 6518 31.9507 move bul to the pivot
24 1792 7392 6518 8459 end 7392 33.9000 move nic to the pivot
25 1792 7392 7662 8459 end 7662 34.4977 move pla to the pivot
26 1792 8079 7662 8459 end 8079 22.5972 ≤ $\theta$: move nic to 8080
27 1792 8079 end 8459 end 8459 20.9980 ≤ $\theta$: move pla to 8460
28 1792 8515 end 8459 end 8515 21.1488 ≤ $\theta$: move pla to 9255
29 1792 9403 end 8459 end 9403 20.2739 ≤ $\theta$: move pla to 9404
30 1792 9561 end 8459 end 9561 10.8976 ≤ $\theta$: move pla to 9710

Eleven of the thirty steps fail the block test. Step 14 is the first, and the second worked problem redoes it by hand. Between steps 14 and 18 the cursor of bullion stays on story 2230 while the pivots run from 2645 to 5361. Its second block, with maximum 5.6283, covers the docIDs up to 5637, and with it in the sum no pivot there can qualify. WAND, with bullion's list bound of 10.6555, had to move that cursor three times through the same stretch.

On this small query the gain is slight:

Method Postings scored Blocks decoded (of 16) Postings decoded (of 53)
Exhaustive 53 16 53
MaxScore 39 14 47
WAND 13 13 48
Block-Max WAND 13 12 45

Both forms of WAND score the same 13 postings, because here the list bounds were already enough to reject everything after the two best stories. The block maxima save one step and one block. The last two columns count something the previous article did not: a cursor that lands in a block must decode it, even if it then scores nothing there. WAND scores a quarter of the postings and decodes nine tenths of them. That gap is the subject of the section after the proof.

Proof that Block-Max WAND is safe

Theorem. Block-Max WAND, as stated above and with any choice of list in steps 4 and 5, ends with the heap holding exactly the top $k$ matching documents with their exact scores.

Proof. We check the three conditions of the safety lemma of the previous article, following its proof for WAND. As there, a cursor passes a posting when it moves beyond it, and skips it when it does so in a step that scores nothing (steps 4 and 5 here).

Fact A holds as before. Step 3 scores $\pi$ only when every cursor in positions 1 to $p$ is on $\pi$. Position 1 holds the smallest cursor, so all cursors are at or beyond $\pi$, and after the step all are strictly beyond it: the extension in step 1 put every cursor that was on $\pi$ among positions 1 to $p$. So offers strictly increase, which is condition 1, and every document offered so far is smaller than the docID under every cursor.

Fact B, extended. Suppose a skip moves a list from docID $c$ to its first posting at or after a target $g$, where $g = \pi$ in step 4 and $g = d'$ in step 5. Let $d$ be a document with $c \le d < g$. Then the contributions to $d$ from postings that no cursor has passed sum to at most $\theta$. There are two cases.

  • $d < \pi$. This is the case of WAND. An unpassed posting of $d$ lies in a list whose cursor is at or before $d$, hence below $\pi$, hence before the position at which the sum of list bounds first exceeded $\theta$. (The extension of $p$ only added lists whose cursor is on $\pi$.) The bounds of the lists before that position sum to at most $\theta$.
  • $\pi \le d < d'$, which can happen only in step 5. An unpassed posting of $d$ lies in a list whose cursor is at or before $d$. Since $d$ is below $d'$, and $d'$ is at most the docID under the cursor in position $p + 1$, that list is in positions 1 to $p$. For each such list, $d$ lies in the range of the block looked up in step 2: $d$ is at least $\pi$, which is beyond the last docID of the block before it, and $d \le d' - 1 \le e$, which is at most that block's last docID. So the list's contribution to $d$ is at most that block's maximum. Summing over the lists in positions 1 to $p$, the unpassed contributions to $d$ are at most $\beta$, and $\beta \le \theta$ in step 5.

Fact C holds as before: when the algorithm stops, no pivot exists, so the bounds of all lists that are not exhausted sum to at most $\theta$.

With these three facts the rest of the argument is word for word that of WAND. Take a matching document that is never offered exactly. Either it has a posting skipped at some first moment, when all its postings are still unpassed and Fact B gives $S(d) \le \theta$. Or it has none skipped, is never offered, and satisfies $S(d) \le \theta$ at the stop by Fact C. In both cases every document accepted earlier is smaller, by Fact A. That is condition 3. An offer that is not exact misses a posting that was skipped earlier, at a moment when $S(d) \le \theta$, so its sum is at most $\theta$ and it is not accepted. That is condition 2. $\blacksquare$

The proof asks one thing of the stored block numbers: each must be at least the largest contribution in its block. It need not be equal. A block maximum may be rounded up, or replaced by any larger number, and the result stays exact. Only the amount of skipping suffers. That freedom is what makes the metadata cheap, as measured below.

What skipping needs from the index

A pruning algorithm is only as good as the operations its index supports. Four requirements can be read off the algorithm.

Moving to a docID without reading what lies between. Every step 4 and step 5 is a jump to "the first posting at or after $g$". In a list stored as gaps this requires the last docID of each block, which is the skip data of skip pointers, and the position where each block starts. The Elias–Fano representation offers the same operation from its upper bits, without a separate table.

Decoding one block at a time. A cursor that lands in a block must decode it to find its posting. If blocks could not be decoded independently, a jump would save comparisons and no decoding. Block-max indexes reuse the blocks that block codes already have (Tonellotto, Macdonald and Ounis, 2018, section 3.4), and they inherit its grain. That grain limits what can be saved: a method may score a tenth of the postings and still decode most of the blocks, if the postings it needs are spread one to a block.

A bound per block that can be read without decoding. This is the block-max table itself. It must sit outside the compressed block, next to the last docIDs.

A scoring function that is known when the bound is written. A stored maximum contribution is the maximum under one ranking function with fixed parameters. Change $k_1$ or $b$, or the collection statistics behind the IDF, and the stored numbers are no longer the true maxima. Apache Lucene, which adopted Block-Max WAND in version 8.0 in March 2019, avoided fixing the function. Grand, Muir, Ferenczi and Lin (2020) describe what it stores instead. For each block it keeps the pairs of term frequency and document length that could yield the block's best score under any function that grows with the frequency and shrinks with the length. It discards a pair when another has at least its frequency and at most its length, and computes the block bound from the surviving pairs at query time. Those pairs are kept in the skip data, at several levels, so that a query can pass over groups of blocks at once. The format documentation of Lucene 9.9 lists them as the competitive frequency and norm entries of the skip data (Apache Software Foundation, 2023).

Updates add a fifth consideration that this article only names. Block boundaries and block maxima describe a list as it was written. An index that grows in immutable segments, the subject of updating an index, writes them once per segment and rewrites them when segments merge.

Later work varies each of these choices. Dimopoulos, Nepomnyachiy and Suel (2013) apply block maxima to MaxScore as well as to WAND and report a further factor of two in speed over the first paper's best results with acceptable space overheads. Mallia, Ottaviano, Porciani, Tonellotto and Venturini (2017) let the blocks vary in size. They define the error of a block as the sum, over its postings, of the difference between the block maximum and the posting's own score, and choose the block boundaries of each list to make the total error small for a given number of blocks. They also compress the block table, with Elias–Fano for the boundary docIDs and quantized maxima, and report that the resulting method outperforms Block-Max WAND "by a factor of roughly 2×" (section 1).

Measured on Reuters-21578

The queries are the 1,500 headline queries of the previous article: 30 samples of 50 headlines, seeds 0 to 29, with BM25 and $k = 10$ unless stated. Counts are sums over a sample's queries divided by the exhaustive count, and the tables give the median over the 30 samples with the quartiles in brackets. The first table counts postings scored.

Method Postings scored
MaxScore 11.7% [10.8, 12.3]
WAND 9.7% [9.2, 10.2]
Block-Max WAND, blocks of 8 6.0% [5.8, 6.4]
Block-Max WAND, blocks of 16 7.0% [6.7, 7.4]
Block-Max WAND, blocks of 32 7.8% [7.4, 8.1]
Block-Max WAND, blocks of 64 8.3% [7.9, 8.7]
Block-Max WAND, blocks of 128 8.8% [8.3, 9.2]
Block-Max WAND, blocks of 64, maxima rounded up to 8 bits 8.6% [8.2, 9.1]

Block maxima help at every block size, and smaller blocks help more: blocks of 64 take WAND's 9.7 percent to 8.3, and blocks of 8 take it to 6.0. The gain is modest on this collection, and the figure above shows why. A block of 64 Reuters postings nearly always contains a posting that scores close to the list's best. Averaged over the lists that have more than one block, a block's maximum is 0.92 of its list's bound at blocks of 64, and 0.81 at blocks of 8:

Block size Lists with two or more blocks Mean of block maximum / list maximum
8 6,009 0.81
16 4,082 0.86
32 2,625 0.90
64 1,603 0.92
128 933 0.94

The last row of the first table rounds every block maximum up to a multiple of 0.0689, so that it fits in 8 bits (255 steps reach the largest contribution in the index, 17.5572). The top 10 is still exact on every query, as the proof promised, and the share scored rises from 8.3 to 8.6 percent.

For other values of $k$, with blocks of 64:

$k$ Block-Max WAND, blocks of 64
1 1.8% [1.7, 2.0]
10 8.3% [7.9, 8.7]
100 26.6% [26.2, 27.4]
1,000 70.7% [70.2, 71.3]

Each figure is below the WAND column of the table in the previous article, measured on the same queries, by between 0.3 and 2.2 points.

Postings decoded

Scoring a posting is one cost, and decoding the block it sits in is another. The second table counts the postings in every block that some cursor landed in, as a share of all the postings of the query's terms. Blocks here are an accounting device, since the lists of the experiment are not compressed, but the count is what a block-compressed index would have to decode. A block counts when a cursor first rests on a posting in it, so a list's first block always counts. A jump past a list's end decodes nothing, and looking up a block maximum decodes nothing.

Block size MaxScore WAND Block-Max WAND
8 27.0% [25.3, 28.1] 50.6% [48.9, 52.3] 38.7% [37.1, 39.9]
16 34.0% [32.3, 34.9] 62.4% [60.8, 64.0] 53.4% [52.6, 55.0]
32 42.5% [40.9, 43.9] 74.0% [72.9, 75.5] 68.5% [67.1, 69.8]
64 52.9% [51.5, 54.2] 84.0% [82.3, 85.1] 81.4% [79.6, 82.2]
128 64.1% [62.7, 65.6] 90.8% [89.9, 91.9] 89.8% [88.2, 90.7]

This is the more sobering table. With blocks of 64, WAND scores 9.7 percent of the postings and decodes 84 percent of them, and Block-Max WAND scores 8.3 percent and decodes 81 percent. Reuters has 10,788 stories, and the long lists of a headline query hold a posting every few stories, so a jump of a few hundred docIDs still lands in the next block or the one after. MaxScore decodes far less than either, about half, although it scores more. It consults its non-essential lists only for the candidates that the essential lists propose, and the long lists of common words are the non-essential ones. The pattern is not peculiar to this collection. Ding and Suel (2011, Table 2) report that on TREC GOV2 WAND evaluated under 5 percent of the documents that exhaustive evaluation scored. It still decoded 6.3 million of the 9.4 million integers per query, and Block-Max WAND decoded 2.6 million.

What the table of maxima costs

Each block needs its last docID, 14 bits for 10,788 stories, and its maximum. Over the whole index:

Block size Blocks in the index Bits per posting, 32-bit maxima Bits per posting, 8-bit maxima
8 110,629 7.01 3.35
16 68,059 4.31 2.06
32 47,362 3.00 1.44
64 37,446 2.37 1.14
128 32,789 2.08 0.99

Against postings that compress to between 7 and 9 bits each, these are large additions, and blocks of 8, which prune best, would double the index. Most of the cost is an artifact of a small collection. Of the 29,187 lists, 27,584 fit in one block of 64, and a list of one block gains nothing from a block maximum, since it equals the list's bound. The third worked problem prices the table for the long lists alone. Ding and Suel report the other end of the scale: on GOV2, with blocks of 64 and 32 bits per maximum, the block maxima added about 400 megabytes to a compressed index of 8,759.

DocID order

Ding and Suel found that assigning docIDs so that similar pages are adjacent helped Block-Max WAND most of all the methods they compared. On their TREC 2006 queries its mean time fell from 27.9 to 8.89 milliseconds after reordering (their Tables 1 and 3). Their explanation is that reordering makes the scores inside a block more alike, so block maxima sit closer to typical contributions.

Reuters can be tested only in the other direction, by destroying the weak order that filing sequence gives it. The docIDs were shuffled with 30 seeds, the lists rebuilt, and the 50 queries of seed 0 run again:

Method Filing order Random order, median [quartiles] of 30
WAND 10.5% 10.1% [10.1, 10.2]
Block-Max WAND, blocks of 64 8.7% 8.5% [8.5, 8.7]
Block-Max WAND, blocks of 16 7.4% 7.4% [7.3, 7.4]

Shuffling changes almost nothing, and what it changes goes slightly the other way. A reading consistent with this is that filing order does not group stories by the things that set a BM25 contribution, a story's length and the term's frequency in it, so there was no smoothness inside blocks to destroy. This experiment therefore neither confirms nor contradicts the paper's finding. It shows only that an order which helps compression a little, as the compression article measured, need not help block maxima.

This site's index

On the 320 evaluation queries of this site's search, with the BM25F contributions and the fixed set of 679 pages described in the previous article, at $k = 10$:

Query set WAND Block-Max WAND, blocks of 64 Blocks of 16 Blocks of 8
title 37.6% 37.2% 33.6% 30.5%
known-item 25.5% 24.9% 23.0% 21.2%
topical 24.0% 23.3% 21.9% 20.1%

No list of this index has more than 679 postings, so blocks of 64 divide the longest list into eleven, and block maxima of that size add almost nothing to WAND. Smaller blocks recover a few points. For an index of this size the honest conclusion, on these measurements, is that term bounds do most of what can be done and block bounds are not worth their table.

Postings scored are still not seconds. In one run of the Python script on a shared machine, WAND took about 25 milliseconds per Reuters query and Block-Max WAND about 36, although the second scored fewer postings. Each of its steps does WAND's work and then looks up a block in every list up to the pivot. The measured speeds of real implementations are in the papers: Ding and Suel (2011, Table 1) report 225.7 milliseconds per query for exhaustive evaluation, 77.6 for WAND and 27.9 for Block-Max WAND on their TREC 2006 queries over GOV2. Grand and his coauthors (2020) report that the Lucene implementation improved Lucene's own benchmark by a factor of 3 to 7.

What is proved here, what is cited, what the experiment shows

Proved on this page. That Block-Max WAND as stated returns exactly the top $k$ with exact scores, for any valid block bounds, including bounds rounded up; and, by example, that using the maxima of the cursors' current blocks in the pivot test does not.

Cited. The block-max index and the algorithm, from Ding and Suel (2011), whose paper says of its key step that the proof "should be obvious" and gives none; the version of the algorithm in Tonellotto, Macdonald and Ounis (2018); Lucene's design, from Grand and his coauthors (2020) and the Lucene documentation; every time in milliseconds and every count on GOV2; the variable-sized blocks of Mallia and his coauthors (2017), which were not implemented here.

Measured. Postings scored, postings decoded and the size of the block table, on Reuters-21578 and on this site's index, with the top $k$ asserted equal to the exhaustive one on every query, block size and $k$. Both collections are small. On them block maxima save about a seventh of what WAND scores at blocks of 64, and little decoding.

Worked problems

The first problem is posed on the two constructed lists of the section on the unsafe shortcut, the second on the running example, and the third on the Reuters index. The script recomputes every number.

Problem 1 (the correct algorithm on the example that broke the shortcut). Run Block-Max WAND with $k = 1$ on list $a$ (2: 1, 3: 1, 6: 5, 7: 1) and list $b$ (1: 4, 9: 4), with blocks of two postings.

Solution. It returns document 6 with score 5, after scoring two postings. The list bounds are $U_a = 5$ and $U_b = 4$. The block table of $a$ has last docIDs 3 and 7 with maxima 1 and 5, and that of $b$ has last docID 9 with maximum 4.

Step Cursors $a$, $b$ Pivot (by list bounds) Blocks consulted $\beta$ Action
1 2, 1 1 ($b$: $4 > -\infty$) $b$: block 1 4 score document 1: 4; $\theta = 4$
2 2, 9 2 ($a$: $5 > 4$) $a$: block 1 1 $1 \le 4$: $d' = \min(3 + 1, 9) = 4$; move $a$ to its first posting at or after 4, document 6
3 6, 9 6 ($a$: $5 > 4$) $a$: block 2 5 $5 > 4$ and the cursor is on the pivot: score document 6: 5; $\theta = 5$
4 7, 9 9 ($a$: 5, then $a + b$: $9 > 5$) $a$: none, $b$: block 1 4 $4 \le 5$: $d' = 9 + 1 = 10$; move $a$ past its end
5 end, 9 none ($b$: $4 \le 5$) stop

At step 2 the shortcut and the correct algorithm look at the same block of $a$, with maximum 1. The shortcut concluded that $a$ could add at most 1 to any document before document 9. The correct algorithm concludes only that documents 2 and 3 are out, and moves $a$ to document 4 or later, where it finds document 6. At step 4, list $a$ has no docID as large as the pivot, so it adds nothing to $\beta$. Plain WAND returns the same answer after scoring four postings. It also scores documents 2 and 3, since $U_a = 5$ exceeds the threshold of 4 when the cursor reaches document 2, and equals but does not exceed 5 only after document 6.

Problem 2 (one block check by hand). At step 14 of the trace the cursors are on 1792 (palladium), 3686 (platinum), 2645 (nickel), 2230 (bullion) and 5646 (krugerrand), and $\theta = 31.2542$. Find the pivot, the blocks consulted, $\beta$, and the movement.

Solution. In cursor order the lists are palladium (1792), bullion (2230), nickel (2645), platinum (3686) and krugerrand (5646). The list bounds sum to 11.6261, then $11.6261 + 10.6555 = 22.2816$, then $22.2816 + 11.9005 = 34.1821 > \theta$. So the pivot list is nickel and the pivot is story 2645. No later cursor is on 2645.

The blocks whose ranges hold 2645 are, from the block table: block 2 of palladium (docIDs above 1795 up to 8079, maximum 10.8247), block 2 of bullion (above 2230 up to 5637, maximum 5.6283), and block 1 of nickel (up to 2645, maximum 11.4768). Then

$$\beta = 10.8247 + 5.6283 + 11.4768 = 27.9298 \le 31.2542.$$

Story 2645 cannot qualify, and neither can any story up to the smallest of the last docIDs, $e = \min(8079, 5637, 2645) = 2645$. The cursor in the next position is on 3686, so $d' = \min(2646, 3686) = 2646$. The list with the largest bound among the three is nickel, and its cursor moves to its first posting at or after 2646, story 3192. Here the block test saved little distance, because the pivot was the last docID of nickel's block. What it saved was the work: WAND at the same point had a pivot it could not reject and moved bullion's cursor to story 3773, decoding a block whose best posting contributes 5.6283.

Problem 3 (pricing the table). For blocks of 64 on the Reuters index, how many bits per posting does a table of 14-bit last docIDs and 32-bit maxima cost if it is kept only for lists longer than one block?

Solution. About 0.79 bits per posting of those lists. Of the 29,187 lists, 27,584 have at most 64 postings. For them the dictionary's list bound is the block maximum and no table is needed. The other 1,603 lists hold 573,263 postings in 9,862 blocks. At $14 + 32 = 46$ bits a block the table takes 9,862 times 46 bits, which is 453,652 bits, or 0.79 bits per posting. With 8-bit maxima, safe by the remark after the proof, it is $9{,}862 \times 22 / 573{,}263 = 0.38$ bits. The figure of 2.37 bits in the table above charged all 37,446 blocks of the index, most of them the single block of a short list.

What we have learned

A block-max index stores, beside each block's last docID, an upper bound on the contributions in the block. A block bound limits only the documents in its block's range, so it cannot replace the list bound when WAND chooses a pivot. Block-Max WAND keeps WAND's pivot and adds a check on the blocks that hold the pivot, and when the check fails it jumps past the nearest block boundary. The safety lemma covers it with one added case, and it holds for any stored numbers that are at least the true maxima. On Reuters-21578 with blocks of 64 it scored 8.3 percent of the postings against WAND's 9.7, at a cost of 0.79 bits per posting of the long lists. It decoded nearly as many blocks as WAND did.

That last observation points at the layout of the lists themselves: what is saved depends on how postings are packed and how cheaply a cursor can land in the middle of a list. The next article, Modern Postings Compression, works the block codes and the Elias–Fano representation that current indexes are built from.

References

  • Apache Software Foundation (2023). Apache Lucene 9.9.0 API documentation: Lucene99PostingsFormat. https://lucene.apache.org/core/9_9_0/core/org/apache/lucene/codecs/lucene99/Lucene99PostingsFormat.html record · 4 pages
  • Dimopoulos, C., Nepomnyachiy, S., and Suel, T. (2013). Optimizing top-k document retrieval strategies for block-max indexes. In Proceedings of WSDM 2013, 113–122. record
  • Ding, S., and Suel, T. (2011). Faster top-k document retrieval using block-max indexes. In Proceedings of SIGIR 2011, 993–1002. record · 3 pages
  • Grand, A., Muir, R., Ferenczi, J., and Lin, J. (2020). From MaxScore to Block-Max WAND: The story of how Lucene significantly improved query evaluation performance. In Advances in Information Retrieval (ECIR 2020), Part II, Lecture Notes in Computer Science 12036, 20–27. Springer. record
  • Mallia, A., Ottaviano, G., Porciani, E., Tonellotto, N., and Venturini, R. (2017). Faster BlockMax WAND with variable-sized blocks. In Proceedings of SIGIR 2017, 625–634. record
  • Tonellotto, N., Macdonald, C., and Ounis, I. (2018). Efficient query processing for scalable web search. Foundations and Trends in Information Retrieval, 12(4–5), 319–500. record · 4 pages