Query rewrite rules in Elasticsearch: 2.3x faster wildcard scans

Want to get Elastic certified? Find out when the next Elasticsearch Engineer training is running! You can start a free cloud trial or try Elastic on your local machine now.

Lucene query rewrite rules make two string scan queries in Elasticsearch's columnar mode 2.3x and 1.6x faster. Both rules spot a query shape at runtime and swap in a cheaper implementation. For a wildcard query like *google*, that's a substring search in place of the automaton. A filter like SearchPhrase != '' can skip Zstd decompression, because it only needs string lengths that are sitting in an offset array.

Columnar mode is Elasticsearch's analytics-optimized columnar storage mode, built for scan-heavy workloads, like log analytics. In this mode, keyword fields don't get an inverted index by default, so term and wildcard queries scan doc values. DocValuesSkippers (zone maps) already trim how much data a scan touches, but these rewrites cut the cost of what's left. 

How Lucene's query rewrite mechanism works

In Lucene, every query has the option to implement a rewrite method that returns another query. This method returns a query with the same semantics but a different implementation. The query engine repeatedly calls the rewrite method until the returned query doesn’t change. This final query is the one that’s actually evaluated. Importantly, the rewrite can see the actual query arguments and specialize the implementation based on these.

For example, in a query looking for documents where a string field contains the value "foo", the rewrite method knows that the term we’re searching for is "foo". In theory, rewrite could replace the general query class with something specific to "foo". For example, the original query class ScanningBinaryDocValuesTermQuery could be replaced with FooQuery. Now this rule probably wouldn't be helpful, but it gives a sense for the level of specialization that’s achievable with rewrite rules.

Rewrite rules and query optimization in database systems

It's worth placing rewrite rules in the larger context of database systems. Lucene and Elasticsearch aren’t the first systems to use transformation rules to optimize queries. Most (or maybe all) database systems use some kind of rule system during query optimization. The most influential rewrite rule system was in IBM's Starburst database. This system's core contribution was extensibility; for example, it was possible to add new data types and storage methods, along with (most importantly to us) optimizer rewrite rules.

Each rule consisted of two parts:

1. A condition function: A predicate determining whether the rule applies to the current query graph.

2. An action function: The transformation that rewrites the query plan into a more optimal form.

A rule engine applied matching rules until a stopping condition was met.

Though Lucene's rewrite method is superficially different from these condition and action functions, it achieves the same goal. It checks whether certain conditions match, and if they do, it applies the rewrite by returning a new query. If conditions don’t match, the rewrite returns this, replacing the query with itself; that is, choosing not to apply the rule.

Why these rules live in Lucene, not the ES|QL query optimizer

Elasticsearch actually contains a separate rewrite rule system within the Elasticsearch Query Language (ES|QL) optimizer. This operates on the high-level structure of a query; for example, doing predicate pushdown to avoid unnecessary computation on documents that will be filtered out. But it’s still useful to have the rule system within Lucene. Since Lucene acts as the storage layer for ES|QL (and classic _search) queries, it’s easier to express rewrites that take advantage of the physical data format in Lucene rather than in a higher-level optimizer.

A query rewrite rule for wildcard queries: Simpler code, no automaton

Wildcard queries support the ? and * operators to match any character once or any character multiple times. These operators can appear any number of times in a wildcard query. As with regexes, to evaluate whether a string matches a wildcard query, we build an automaton from the query string and then use the string bytes to do state transitions through the automaton. This is relatively fast, but if you have to evaluate it for every document, the latency really adds up.

But maybe we don't always have to run an automaton. Consider a query like *foo*. How would you implement this if you were writing a simple query engine to find matching strings in a list of strings? Pretty much every programming language has the tool you want built in: a method that finds a substring within a given string. This function doesn't need a complicated automaton; it probably just consists of a couple of for loops.

Now of course we couldn't use this function to implement an arbitrary wildcard query, but we don't have to. The rule rewrite system isn't for the general form. It's for implementing special cases, and it can see the specific query. It knows that we’re looking for *foo* and realizes that this specific case doesn't require the heavyweight automaton machinery. And it can do the same for any query that starts and ends with a *, with some term in the middle.

The following pseudo-code shows the pattern. At the top, we have the generic WildcardQuery. It has two notable fields: the query string (for example, *foo*) and the automaton built for that query. The matches method checks whether the field value for a given docId is a match by using it to evaluate the state transitions of the automaton. More interestingly, its rewrite method checks whether the query matches our special case. We show this with a regex that checks whether the query string starts with a *, has any non-*characters at least once, and then ends in a *. If so, we return the special case as a ContainsQuery and pass in the inner query string (since it doesn't care about the *s). The ContainsQuery then just does a simple contains check to see whether the term bytes are somewhere within the value bytes.

class WildcardQuery(query, automaton, docValues):

    boolean matches(docId):
        value = docValues.loadValue(docId)
return automaton.matches(value)

    Query rewrite():
if query matches r"^\*[^*]+\*$":
return ContainsQuery(query[1:-1], docValues)
return self


class ContainsQuery(term, docValues):

    boolean matches(docId):
        value = docValues.loadValue(docId)
return value.contains(term)

Benchmarking the wildcard rewrite on ClickBench Q20

The wildcard rewrite is straightforward, but does it actually work? Yes, we can use the ClickBench benchmark, which has several queries of this form. Query 20 (Q20) is FROM hits | WHERE URL LIKE "*google*" | STATS count = COUNT(*). It's exactly the query shape that this rule matches: a string match against the wildcard query *google*. And since the query is just counting, we can see exactly how well this technique works. It turns out to be quite effective. Q20 saw a 1.75x improvement on median latency of hot query times, with no filter cache. All benchmarks in this post were run on an Intel Core i9-13900H.

Adding SIMD to the substring search: 1.75x to 2.3x

But can we do better? Yes, switching to a simple contains check opens up a new possibility. Instead of using the two for loops, we can swap scalar logic for single instruction, multiple data (SIMD) logic. Elasticsearch uses the Panama vector API (see our post on SIMD in Elasticsearch), which lets us implement the contains check in SIMD. This works particularly well for longer strings that can take advantage of the wide SIMD registers; for strings under 24 characters, we still use the scalar approach. With this change, we saw another 1.32x improvement, resulting in a total speedup of 2.3x over the automaton-based approach.

A query rewrite rule for empty strings: Less data, no decompression

One benefit of Lucene-based rules is that they’re low level and can fit to the data format. That’s the case for this rule, which applies to string data. 

How columnar storage encodes string data

In Elasticsearch's standard mode, string values are stored by document; this is a row-major format. But in columnar mode, unsurprisingly, the data is stored in columnar-major format. A column of string data is stored in chunks. Each chunk contains many string values and consists of an array of integer offsets and a (Zstd-compressed) blob of the strings' bytes. For a string at index i, offsets[i] points to the offset in the decompressed byte blob where the string starts. So the length of string i can be computed from offset[i+1]-offsets[i]. (There's a dummy extra offset at the end, so we can easily compute the length of the last string). The following diagram shows how a chunk with the strings ‘Feta’, ‘Asiago’, ‘’, ‘Stilton’, and ‘Brie’ is encoded.

Why a term query has to decompress the chunk

Now that we understand the columnar format, let's get back to query optimization. First, consider a term query for the query foo. We’re looking for documents where a given string field exactly matches the string foo. So how do we implement this on a string column in the above format? The algorithm is straightforward:

docId = 0
for chunk in chunks:
    bytes = zstd_decompress(chunk.bytes)
for i in range(len(chunk.offsets) - 1):
        value = bytes[chunk.offsets[i] : chunk.offsets[i+1]]
if value == term:
yield docId
        docId++

The bottleneck is the Zstd decompression step. But there's not much we can do about that; if we want to check the bytes, we have to decompress the chunks. But remember, we aren't trying to optimize the general case, we’re looking for special cases. (In reality, you don't just try to think up special cases. These optimizations came about by first running a useful query, realizing that it could be faster, and then looking for ways to improve it.)

Rewriting the empty string query as a length check

One special case we found that’s worth improving is a query for the term "". Admittedly, it's a silly term, but empty strings are all over the place. Since they're rarely useful, we usually filter them out with a query like term != "". Thankfully, this is a query we can optimize.

Consider the above algorithm for the empty string term. The line if value == term is a bit weird; we’re asking Does this value equal the empty string? We can do that, but there are no bytes to compare, so the check unwinds:

1. We only need to know whether the value has length 0.

2. If we only need the length, we don't need to look up the value in the decompressed chunk.

3. If we never look up a value, we don't need any bytes from the chunk at all.

4. If we need no bytes from the chunk, we don't need to decompress it.

All we need are the lengths, and those live in the offsets array. It's compressed, too, but with cheap integer compression rather than Zstd, which is much faster.

With this realization, we can rewrite empty string term queries. The one new operation we need is docValues.loadLength(docId), which reads directly from the offset array without touching the compressed bytes. After the previous example, this should look familiar. The most interesting part is TermEqualsQuery.rewrite; it finds the empty string special case and replaces the query with the simpler version that only checks the length.

class TermEqualsQuery(term, docValues):

    boolean matches(docId):
        value = docValues.loadValue(docId)  # requires Zstd decompression
return value == term

    Query rewrite():
if term == "":
return LengthEqualsQuery(0, docValues)
return self


class LengthEqualsQuery(queryLen, docValues):

    boolean matches(docId):
        length = docValues.loadLength(docId)  # reads only from offset array
return length == queryLen

Benchmarking the empty string rewrite: 1.6x faster

Now let's see how this stacks up. There aren't any pure-scan ClickBench queries that use this rule as directly as Q20 does for the previous rule, so we'll make our own. Consider the query: FROM hits | WHERE SearchPhrase != '' | STATS count(*). On this query, we see a 1.6x speedup, which is a great improvement for a fairly uncomplicated change. Better yet, ES|QL can take advantage of loadLength directly. Any time that ES|QL accesses a string's BYTE_LENGTH, without needing the string itself, the request uses this same specialized length loading to avoid unnecessary decompression.

What makes a good query rewrite rule

The two rules covered here follow the same shape: identify that a query is a special case, and then swap it for a cheaper implementation. But they reduce cost in different ways. 

The underlying pattern is worth noting: finding a query that leaves performance on the table, finding a special case that can be optimized, and swapping in a cheaper implementation. The hard parts are finding queries that uncover these opportunities for optimization and then identifying the special cases. The actual fix is often relatively straightforward, as both rules here show. Our work on columnar mode has provided many opportunities to run interesting queries and hunt down exactly these kinds of wins.

That's also why extensibility in a rule system is so important. These rules can't be built into a database from the start; they're found through an incremental discovery process. Lucene's rewrite system makes that practical. As columnar mode grows to handle new workloads, rules like these will keep emerging.

To try columnar mode and the optimizations described in this article, use Elastic Cloud Serverless or Elasticsearch 9.5 or later, where columnar mode is available as a technical preview.