How smart is readyset in deciding when to recalculate the cache?

[selforganized]

Say I have a query:

SELECT * FROM table1 ORDER BY score LIMIT 10

If I update the score of a row in table1, it may or may not change the result of the above query.

Does readyset recalculate the cache of the above query every time table1 is changed? Or is it smart enough to figure out that the cache only needs to be recalculated if the top 10 ordering by score is changed?

For example, if an update to table1 only moves the 14th-ranked record up to the 12th position, does readyset recalculate the query cache?

[alanamarzoev]

Nope! The updated row gets sent to the TopK node, and the TopK node realizes that the value is outside the TopK node and discards it without requiring an expensive TopK calculation. In general, we only have to recalculate the TopK state if an element that was previously in the TopK is deleted. @dfwilbanks395 can go into greater depth if need be :)

[selforganized]

That's great! How is the TopK node implemented? Do you use some probabilistic data structure like count-min sketch?

If you do, how do you deal with overcounting or other counting errors inherent in probabilistic data structures?

If you don't, wouldn't that make the TopK node as big as table1 itself? That'd kinda negate the benefit of having a cache.

[glittershark]

That's great! How is the TopK node implemented? Do you use some probabilistic data structure like count-min sketch?

Essentially, the way nodes in ReadySet work is that when writes (inserts, updates, or deletes) are applied to base tables, those writes flow to all child nodes as "deltas", which are either positive, which means a row should be added, or negative, which means a row should be deleted (updates are just a positive followed by a negative). Those nodes then apply those deltas to their current state, and produce the difference of that state as a new set of deltas which flow down the graph to their child nodes (including the reader node, which provides the full result set for the query).

For example, let's say we have a topk node with k = 3, ordering by column index 0 ascending, and the current state of that node looks like [[1], [2], [4]]. If that node were to receive the delta Positive([3]), it would produce the deltas [Positive([3]), Negative([4])] as its output.

The tricky part there is how to deal with negative deltas which bring us below k records - since we're only materializing the top k, we have to be able to backfill records somehow if we ever drop below k. In that case, the topk node is able to do a lookup to its parent node to backfill. In simpler cases (including your example query), that parent node either is the base table node itself, or is a node like a filter or project node which we can transparently query through to the base table, so we don't have to materialize the full result set, but in more complex cases (such as a join above the topk) we do have to materialize the full result set there so the topk can backfill...

wouldn't that make the TopK node as big as table1 itself?

...which brings me to the other big thing we do to cut down on memory usage in cases like these, which is partial materialization. Imagine you've got a prepared statement like:

SELECT * FROM posts WHERE author_id = ? ORDER BY created_at DESC LIMIT 10;

where ? is a to-be-supplied parameter in a query. In that case, we're actually able to only materialize the result sets for the values of author_id that're queried for (and only do work to keep those result sets up-to-date). To support this, the topk node can be grouped by a different set of columns than it's sorted by, and we use that to group by the partial key for the query (author_id in this case, though partial keys can be compound).

As a side note, you don't have to use prepared statements - or even query parameters - to take advantage of partial materialization. There's a rewrite pass which runs on each query that automatically replaces literal values in supported locations with parameters.

In case you're curious, all the code for the topk operator itself is here