Bringing speedups to top-k queries with many and/or high-frequency terms

Disjunctive queries (term_1 OR term_2 OR ... OR term_n) are extremely commonly used, thus they are getting a lot of attention when it comes to improving query evaluation efficiency. Apache Lucene has two main optimizations for evaluating disjunctive queries: BS1 on the one hand for exhaustive evaluation, and MAXSCORE and WAND on the other hand to compute top hits. Until recently, these two optimizations were never used together, but this changed in order to improve query performance, especially with many clauses and/or high-frequency clauses. See annotation FK on the chart below taken from Lucene's nightly benchmarks.

In Apache Lucene, queries are responsible for creating sorted streams of matching doc IDs. Implementing a disjunctive query boils down to taking N input queries that produce sorted streams of doc IDs and combining them into a merged sorted stream of doc IDs. The textbook approach to this problem consists of putting input streams into a min-heap data structure ordered by their current doc ID. This approach has been referred to as BooleanScorer2 (BS2) in Lucene.

While BS2 works nicely, it gets a bit of overhead from having to rebalance the heap every time that it needs to move to the next match. BS1 tries to reduce this overhead by splitting the doc ID space into windows of 2,048 documents. In every window, BS1 iterates through all matching doc IDs, one clause at a time. On every doc ID, it computes the index of this doc ID in the window, sets the corresponding bit in a bitset, and adds the current score to the corresponding index in a double[2048]. Iterating matches within the window, then consists of iterating bits of the bitset and looking up the score at the corresponding index in the double[2048]. This approach often runs faster with queries that have many clauses or high-frequency clauses.

These two approaches have been described in a 1997 paper called "Space Optimizations for Total Ranking" by Doug Cutting, the creator of Lucene. BS2 is called "Parallel Merge" in this paper and described in section 4.1, while BS1 is called "Block Merge" and described in section 4.2. These are arguably more descriptive names than BS1 and BS2. Note that the description of "Block Merge" in the paper is quite different from what it looks like in Lucene today, but the underlying idea is the same.

As the above chart shows, it only takes 8 terms before exhaustive evaluation runs faster than top-k optimizations, as the latter could not skip enough hits to compensate for their overhead. Worse, with 24 terms, trying to use top-k optimizations made the query run 2.5x slower compared to exhaustive evaluation.

However, the new evaluation logic for disjunctive queries that combines BS1 with MAXSCORE consistently outperformed both exhaustive evaluation and existing top-k evaluation for this set of queries.

This improvement is expected to ship in Lucene 9.8 and then in Elasticsearch in the near future. Basically, this means that query performance should get better when doing top-k searches over disjunctive queries, especially when:

• there are many clauses,
• and/or some clauses have a high frequency,
• and/or some clauses produce suboptimal score upper bounds.

Thanks for reading this blog — we hope you'll enjoy the query speedups! If you would like to learn more about optimizations for top-k query processing, check out this other blog where we describe how these optimizations were introduced in Elasticsearch 7.0/Lucene 8.0.