A Set Has More Ways to Go Wrong Than a Row
The last lesson ended by suggesting you cache a list of identifiers and cache the rows separately. This lesson is about why that split matters, and about the thing result set is usually hired to fix.
A result set is derived from many rows and from the query that selected them, so two different kinds of change can make it wrong: a member changing, and the membership changing.
The Problem It Is Usually Hired For
The database has no way to jump to the hundred thousandth row of an ordered result. OFFSET is defined as skip this many rows, and skipping means producing them, so the work is proportional to the depth and not to the page size.
That makes the whole result set look like the obvious answer. It is worth checking against the alternative first, because the slowness here is a property of the question.
The script is at scripts/labs/resultset/pagination.py, and it runs against the same real PostgreSQL as the previous lesson.
OFFSET went from 0.02 milliseconds at the first page to 16.44 at row 250,000, which is 913 times slower for the same twenty rows. Keyset measured 0.02 milliseconds at every depth.
At the first page the two are identical, which is why this problem is invisible in testing. If the flat line is available, the cache was solving a problem that did not need to exist.
A B-tree index is ordered, so finding where a key begins is a descent through a few levels. Caching makes the discarded work happen once instead of every time. Keyset means it never happens at all.
What Keyset Costs
It suits infinite scroll and next-page links, and it cannot serve a numbered pager, because there is no way to know where page 500 starts without counting. Look at how deep your users actually go before defending that capability.
This race is far from rare. On any list ordered by something new rows can land in the middle of, it happens whenever the data changes while somebody is reading. Keyset fixes this too: an insert earlier in the order does not move the boundary.
What Caching a Set Actually Does
The freezing is the primary effect and the performance is a side effect. Reading it that way round makes it much easier to decide when the technique is right, and it is exactly what somebody paging through search results expects.
Result set is usually sold as a performance fix and its most defensible use is a correctness fix: giving one user a stable view while they page.
What to Store, and the Count Nobody Times
Storing ids keeps entries small, lets rows be shared between result sets, and separates a membership change from a content change.
Multiply by the number of distinct result sets before choosing. One search per user per filter combination is a large number, and storing rows instead of ids is the difference between a cache that fits in memory and one that evicts constantly.
The Invalidation Nobody Catches
Every invalidation scheme built around watching the rows in a set misses this case entirely, and it is the most common one on any list that grows. A is not a fallback here, it is the only thing that catches it.
An expensive set is exactly the case where a refill stall is most visible, because the query that has to run is the one you cached for being slow. Combine this with single flight, or every concurrent request at expiry starts its own rebuild.
Matching the Symptom to the Fix
Most of what sends people to result set has a cheaper answer that involves no staleness, no memory and no second system.
Only the last branch is a result set caching problem, and reaching it means you have established that the plan is good, the depth is not the issue, and the count is separate. That is a much smaller set of situations than the technique is usually applied to.
Quick Check
Knowledge Check
4 questions - Score 80% to pass
Page 5,000 of a listing is slow with LIMIT 20 OFFSET 100000. Measured against keyset pagination, what happens?
What is the primary effect of caching a result set?
You invalidate a cached search result whenever any row in it is updated. What case does that miss?
A listing page is slow. Where should you look first?
