Dictionary Compression in Materialize

Materialize computes and then continually maintains the results of your SQL, as the underlying data change. One consequence is that it needs to keep quite a lot of data live and ready to go at a moment's notice. Naively, this translates to quite a lot of memory-grade storage, which isn't cheap and doesn't seem to be heading that way any time soon.

One remedy is compression, where we change the representation of the data to something more compact, without messing up the qualitative properties of the existing storage. There is a long tradition of compression in columnar databases, where the goal is generally throughput: move through all the data as efficiently as possible. Materialize's superpowers lie in its ability to avoid full scans, and to directly access and respond to rows that have changed. This complicates the adoption of existing columnar techniques (nothing is impossible, just complicated).

Fortunately, there are a few techniques that do adopt well, one of which is dictionary compression. This technique notices values that are common within a column, stashes them on the side, and replaces uses of them by something as short as a byte. Where your database may record a status as one of "preparing", "shipped", "delivered", and "unknown", the dictionary coder can replace each of these with four distinct bytes. Even if you also have a long tail of less popular terms, or typo things, the common values can be factored out.

In this post we'll explain how this works in Materialize!

Materialize represents a row of each table by a sequence of tagged values. Each tag is a byte that indicates how to interpret what follows (e.g. "text" or "int64"). The values that follow each tag are represented by a number of bytes determined by the tag: text will have a length and then some bytes; an int64 is likely just eight bytes. Things are more interesting in practice, where we often sneak the length into the tag (e.g. the number of non-zero bytes in the int64), and put things like "null" and "zero" as tags rather than values.

The main unlock for dictionary compression is that we do not use all of the 256 bytes as tags. We only use ~128 of them, plus or minus, and really should probably be using fewer (they seemed free at the time). These unused tags are available to represent other values. Delightfully, the other values they represent can be determined at runtime as a function of data in the column. We could use the available ~128 of them for the ~128 most popular values in the column, reduce the footprint, and be heroes.

Appropriating the tag bytes does not disrupt Materialize's row representation, which stays the backbone of random access to changed data. It is almost for free, and does not require the sequential compression that columnar engines use (though, it won't achieve the same compression rates either).

Before we can celebrate the win, we have to identify the popular values in each column. Moreover, we kinda-sorta have to do this as we load the data; waiting until after is too late.

We use a technique called a Misra-Gries summary, one of the early streaming algorithms. The algorithm is presented with a sequence of elements, and is tasked with finding a bounded set of elements that occur frequently. Given a limit of k, it certainly finds all elements that occur at least n/k times, and probably does a decent job with other rather frequent elements.

Misra-Gries works by maintaining a tentative count for at most k items, and when presented with items either

1. increments the count if the item is present, or
2. introduces the item if absent and there is room for it, or
3. decrements the count of all existing items, dropping any whose count reaches zero.

We only have space for ~128 items in the tag space, but use a larger buffer to get a more accurate read on the most frequent items.

We build dictionaries for each column, cutting over to using the dictionaries once we've seen enough elements. We continue to collect statistics about the rest of the values in the columns, as the data lifecycle involves a log-structured merge-tree, which will revisit and re-encode the data in the future.

The results of compression are fundamentally an empirical quantity.

Materialize runs an internal installation for our "context graph": a live knowledge graph designed to support agentic workflow. It supports several use cases, whose workloads manifest roughly ~1TB of live state.

We compared the vanilla instance that we run today with instances that enable dictionary compression, on three instance sizes that start comparable and then halve twice.

The main call-out is that the peak memory halved, without penalizing the hydration time. This allows you to cut the resources by 2x, but doing this increases the hydration time (there are half the cores, if nothing else). Attempting to halve it again results in a failure loop where the resources (including the backing disk) cannot fit the compressed data, and the savings cease.

This raises a practical concern: if the efficacy of compression changes, as your data evolve, how does this present? An operational system rarely gets full credit for being cheap 95% of the time and offline the other 5%. Swap provides an insurance policy, but no points for guessing how deep the instances above are already into swap (the "OOM" above is actually "OOD").

Compression of in-memory indexes seems to work great!