TopK is now Generally Available

A common pattern in application queries is "give me the best K rows" - leaderboards, recent activity feeds, or top-rated products. Formally, in SQL terms, that's any query combining ORDER BY with LIMIT without an OFFSET:

SELECT name
FROM leaderboard
WHERE country = 'US'
ORDER BY score
LIMIT 10;

Readyset has always been able to cache this kind of query, but the way we cached it was too memory-heavy. After several months of rework and rigorous testing, we're making the new and optimized approach Generally Available, and shipping a per-cache knob for tuning its memory/recompute tradeoff to your workload. This post walks through what changed, compares the two approaches, and how to configure the new approach to fit your use case for optimal performance.

A primer on Readyset

Readyset is a cache layer for MySQL and PostgreSQL: it sits in front of your database and serves your queries from an incrementally maintained cache, with no application changes.

A Readyset deployment has four moving parts:

• The client is your application, talking SQL.
• The adapter is the process the client connects to. It speaks the MySQL or PostgreSQL wire protocol, so the client can't tell it apart from the upstream database. For each query, the adapter decides whether to serve it from the cache or proxy it through to the upstream. It can also do some post-processing depending on the query shape.
• The server owns the cache itself: the dataflow graph (more on this below) and the state behind it. When the adapter has a cache hit, the server is what answers.
• The replicator bridges the upstream database and the server. It consumes the binlog (MySQL) or replication slot (PostgreSQL) and turns each row change into a write to the dataflow.

For the rest of this post, "Readyset" means the server, since that's where the TopK work lives.

The cache itself is a streaming Dataflow Graph, built per cached query. The root nodes of the graph are replicas of your base tables; the leaves, what we call reader nodes, contain the final result of the cache, indexed by the query's predicates (for the example above, country). In between roots and leaves sit inner nodes for each operation in the query: join, union, filter, aggregate, projection and so on.

Writes propagate through the graph as a stream. Inserts (we call them positives), deletes (negatives), and updates (a negative followed by a positive) arrive at the replicas at the root; each node processes the change and forwards results to its children; the result eventually reaches the reader, where it's ready to be served.

When an application issues a query whose key isn't yet present in the reader, Readyset triggers an upquery: the request walks back up the graph until it finds the required key. Upqueries can either find the keys in inner nodes or reach the root node, pull the relevant rows, and push them down to populate the reader. Upqueries are correct, but they're expensive: orders of magnitude slower than a cache hit, and something we go to lengths to avoid. They're a worst case inside Readyset - but they're still usually magnitudes faster than running the query against the upstream database, which is the alternative if the cache can't answer. So the goal is to keep useful keys serving traffic out of cache, and evict old keys to save memory only when the budget says we have to.

For a deeper dive into how the dataflow graph is built and maintained, Behind the magic: how Readyset speeds up queries with streaming dataflow is a good primer, and the streaming dataflow concept docs cover it in more depth. For another example of how a specific operator earns its own inner node, see our earlier post on window functions under the hood.

The old approach

Before the new TopK operator, queries with ORDER BY and LIMIT were cached as if the LIMIT weren't there. The reader held every row for each cached key, sorted by the ORDER BY columns. When the application issued the query, the adapter pulled the full sorted set out of the reader and returned the first K rows.

For the leaderboard query above, that means storing every score from every cached country, even though only the top 10 ever reach the user. For a country with millions of players, that's millions of cached rows per key. With a memory budget capped by your deployment, the reader can only hold a handful of keys at once - and every new country queried evicts an old one, which becomes another upquery the next time someone looks at it.

The throughput cost compounds quickly: more memory per key means fewer keys cached, which means more upqueries, which means lower throughput.

The new approach

The TopK node is a new kind of inner node that Readyset inserts in the graph whenever a query has the right shape. Instead of materializing every row per key, it only stores the top K rows per key. Positives that aren't better than the worst row currently held are discarded on arrival and are not propagated to the children nodes.

This new approach can skyrocket your Queries per Second (QPS) throughput through four key mechanisms:

• Massive Memory Reduction: Memory usage drops from storing every row per key to a small constant (K) per key, often a reduction of several orders of magnitude.
• Higher Cache Hit Rate: This memory efficiency allows the reader to hold far more keys resident, enabling Readyset to serve significantly more traffic directly from the cache.
• Minimized Upquery Overhead: The higher number of resident keys reduces key evictions, minimizing the need for slow 'upqueries' (cache misses), which are orders of magnitude slower than a cache hit.
• Eliminate Post-Processing Overhead: The adapter no longer performs extra work at query time; it can simply pull the already correct, limited result, serialize it, and return it to the client.

For most workloads this is a strict win. Positives are cheap: compare against the current worst row, keep or drop. Memory use drops from "every row matching the key" to a small constant (K) per key, often a reduction of several orders of magnitude, which allows the reader to hold far more keys resident and serves more traffic from cache.

The tradeoff shows up on negatives. If a row in the top K is deleted, the node now holds K-1 row, but it can't tell, without more information, whether the missing slot should be filled by a row that was previously discarded. To recover, the node issues a backfill: an upquery to its parent for that key, which pulls the full set, sorts it, and rebuilds the top K from scratch. Keep in mind that in this case, the upquery can be served from the parent and doesn't need to reach the base node, so most of the cost of this operation comes from sorting the result in memory and taking the top K records.

The TopK node only kicks in when Readyset can pin K to a concrete value during cache-creation time, which means a literal value of K (LIMIT 10, for example). The one case where we fallback to the old approach is when the query has a parameterized limit (LIMIT ?), where the value isn't known at cache-creation time; meaning that the reader node keeps all the rows in memory and the adapter is responsible for applying the LIMIT clause at cache-read time.

The buffer, and tuning it

To avoid paying the cost of backfills on every negative, the TopK node keeps a small buffer of extra rows past K. A negative against the visible top K just promotes a row from the buffer; a backfill is only triggered when the buffer itself drains.

How much buffer is the right amount depends on your workload - specifically, on how often writes hit rows that are currently in the top K. Some workloads almost never touch the top K (think append-only event logs ordered by time, where new rows rarely displace anything important); others hammer it (think leaderboards where the same hot accounts churn constantly). A bigger buffer means fewer backfills but more rows kept in memory; a smaller buffer means more memory headroom and more keys but more backfill traffic.

As of this release, the buffer size is configurable per cache via a new TOPK_BUFFER_MULTIPLIER option on CREATE CACHE:

CREATE CACHE WITH (TOPK_BUFFER_MULTIPLIER = 4)
    FROM SELECT id, score
    FROM leaderboard
    WHERE country = ?
    ORDER BY score DESC
    LIMIT 10;

The multiplier controls the buffer directly: the TopK node keeps K * multiplier rows of buffer past the visible top K, for K + (K * multiplier) rows per key in total. Setting TOPK_BUFFER_MULTIPLIER = 0 removes the buffer entirely - per-key memory is at its minimum, but every negative against the top K triggers a backfill. Omitting the option preserves the default, which is equivalent to multiplier = 1 (a buffer the same size as K, so 2K rows total).

To check how frequently your TopK nodes issue backfills, there are metrics in place to track this. Using Prometheus, search for the following key readyset_domain_topk_backfill_requests and you'll see a breakdown of how many backfills fired per cache_name which is either auto-generated or specified by you when creating the cache.

How much does the buffer actually help?

To make this less hand-wavy, we ran an experiment: cache an ORDER BY ... LIMIT K query, drive a mixed insert/delete workload against the underlying table, and count how many backfills the TopK node triggers as a function of TOPK_BUFFER_MULTIPLIER. The two lines on each plot are two different delete-key distributions - that is, how we pick which row each delete targets. "Uniform" picks the row uniformly at random from the table. "Skewed" picks from the rows currently in or near the top K (the "hot zone") most of the time, and uniformly elsewhere the rest.

Experiment parameters:

• K = 10 (the LIMIT on the cached query)
• Initial table size: 2,000 rows
• Operations per run: 50,000
• Churn rate: 1.0 (one delete per insert, so the table size stays steady while we fire as many deletes as possible)
• Skew: 0.8 (probability of picking from the hot zone in the "skewed" distribution; the remaining 0.2 falls back to uniform)
• Each (distribution, multiplier) cell averaged over 2

The skewed line collapses by nearly two orders of magnitude going from multiplier = 0 to multiplier = 1, and the uniform line is essentially flat at zero past multiplier = 1. Beyond that, the linear scale stops being informative; the same data on a symlog axis is more revealing:

A few things stand out:

• The default (multiplier = 1) is a strong default. Backfills drop from ~135 to ~2 (uniform) and from ~1150 to ~27 (skewed) just by enabling any buffer at all. If you're not sure what to set, don't set anything; the default (1) is good enough.
• The skewed workload benefits much more from a larger buffer. At multiplier = 4 the uniform case is already at zero backfills, but the skewed case still sees a handful. By multiplier = 16, both are at zero.
• Backfills don't tell the whole cost story. Larger buffers mean more rows held per key, and the operator does slightly more work per write. In our measurements, total elapsed time grew by a few percent between multiplier = 0 and multiplier = 16. That's small, but it's not free.

A reasonable starting heuristic: leave the default in place. If you're caching a known-hot-zone workload (leaderboards, anything ordered by frequently-updated metrics), bump the multiplier to 4 or 8. If you have many keys with very large groups and your writes rarely touch the visible top K, you can shrink the buffer (or set it to 0) to free memory for more cached keys.

Trying it out

Going GA means TopK is on by default. Upgrade Readyset to this release and any cached query whose plan supports it will use the TopK operator automatically - no flags, no CREATE CACHE changes, no application changes. Existing caches are upgraded in place the next time they're rebuilt.

The only reason to touch anything is if you want to tune the buffer for a specific cache. Add WITH (TOPK_BUFFER_MULTIPLIER = N) to CREATE CACHE (or recreate an existing cache with it) if your workload sits at one of the extremes - a known hot-zone workload like a leaderboard, where a larger multiplier (4 or 8) cuts down on backfills; or a wide-key, low-churn workload, where 0 frees up memory for more cached keys.

If your workload has leaderboards, feeds, "top N per group" queries, or anything else with ORDER BY ... LIMIT K, this release should pay for itself.