Author: Kevin Feasel

Aaron Bertrand takes life one page at a time:

Many web applications and APIs implement pagination to control how much data is returned or displayed. Many paging solutions suffer from the linear scaling problem (often referred to as O(n)), meaning the amount of work increases as you get into higher page numbers. If a user has ever clicked “next page” or “last page” and your CPUs caught on fire, you may have been a victim of linear scaling. Are there any creative solutions that will achieve constant-time performance (O(1))?

Aaron’s answer is interesting, particularly if you’re able to define the valid set of filters. At a prior job, I was responsible for filtering of arbitrary combinations of 30+ different columns across multiple dimensions and a fact table in a warehouse. That was a royal pain. The best we could do was run the query once, using ROW_NUMBER() to capture the sort order, and then store that ordering in a specialized table with an identifier token that was a hash of the incoming session info, and cache that data for a pre-set amount of time—which, if I remember correctly, was 5 minutes. Somewhat similar to what Aaron shows but much more ephemeral and it caused the first load to be consistently slower while making subsequent paging activities much faster.