183

Stack Overflow pagination uses page numbers instead of offsets, which points to some kind of LIMIT and OFFSET query. For 10 million questions, skipping to the last page should be really slow, but Stack Overflow manages to keep it fast.

Pagination on the homepage of SO

How does Stack Overflow keep pagination fast? Caching popular queries entirely and paginating in the application code? Using some database black magic?

23
  • 28
    Why should it be slow? If they are just getting the data of questions per page and can pass in a query with a narrow range there is no reason for it to take long.
    – Joe W
    Commented May 1, 2016 at 19:38
  • 1
    @JoeW how do they figure out what that range is?
    – TZHX
    Commented May 1, 2016 at 20:14
  • 3
    @TZHX The same way the determine what range to display on the page?
    – Joe W
    Commented May 1, 2016 at 20:15
  • 2
    @JoeW so, they need to do the ranking in some way, based on varying inputs (e.g. search terms) which takes time to compute. the further they need to go along the list, the slower it is when using the technologies that ms sql server (the database SO use) makes available (which Blender mentions in their post).
    – TZHX
    Commented May 1, 2016 at 20:20
  • They have the basic inputs and so they should be able to pull the results at the same speed for page 1 or page 100K since they know the search terms and how many posts per page.
    – Joe W
    Commented May 1, 2016 at 20:23
  • 4
    @JoeW: If you want to skip to page 100,000, the database needs to find the first 2,500,000 questions sorted by date and slice off the last 25. If you go to page 2, the database finds the first 50 questions sorted by date and slices off the last 25. The further back you go, the more time it takes.
    – Blender
    Commented May 1, 2016 at 20:30
  • Or it can search include the row number in the search as well. while it may not be the fastest search it does speed it up.
    – Joe W
    Commented May 1, 2016 at 20:31
  • 23
    "The further back you go, the more time it takes." - this makes no sense. Once you ask for a query to be sorted, all of the records have been loaded before you get to the pagination. So you already have an "in-memory" (maybe not really but that's unimportant) list of 2,500,000 records where accessing any 25 elements of it takes the same amount of time.
    – millimoose
    Commented May 2, 2016 at 3:44
  • 1
    Remember that you there is no way to sort incomplete data sets at all, and that a list of millions of items isn't honestly that big all things considered. And as you go through pages of said list, it can be grabbed from a cache, you don't need to rebuild it for every page view.
    – millimoose
    Commented May 2, 2016 at 3:45
  • 8
    @millimoose: Create a table with 10 million rows and test the performance impact of a large OFFSET. This isn't some obscure corner case, it's a common approach to pagination that just doesn't work the deeper you go.
    – Blender
    Commented May 2, 2016 at 3:52
  • 6
    @Blender I ran a query with 37,809,803 rows - 4 seconds to select the last 20 items. And my machine is far less powerful than what SE employs.
    – Rob Mod
    Commented May 2, 2016 at 4:36
  • @Blender Also, just out of curiosity, I was trying pages unlikely to be cached. For example: stackoverflow.com/questions/tagged/… which does indeed have a noticeable slow-down (a few seconds to load the results).
    – Rob Mod
    Commented May 2, 2016 at 4:41
  • 6
    @millimoose With an appropriate index, a DB engine can easily return the first (or last) n rows matching a certain condition without having to access the rest. In principle, indexing could also allow efficient retrieval of a chunk of rows from the middle of the sorted list, but this is more difficult (the query would need to depend purely on the index, with no extra filtering clauses) and not all database engines support it. (Off the top of my head, I'm not sure if the DB software used by SE supports anything like that, but I'd guess it probably doesn't.) Commented May 2, 2016 at 9:35
  • 2
    @IlmariKaronen - I should test this, but I strongly believe that what you describe can only happen when you never sort the query in question. Sorting invariably requires the entire result of the query, whether it's filtered by indexed columns or not, to be available in a form that makes random access possible.
    – millimoose
    Commented May 2, 2016 at 12:42
  • 2
    @millimoose check out the answer to this question, there's some complexity involved Commented May 2, 2016 at 22:40

1 Answer 1

156

Well, the whole process is pretty complicated, but I'll try and answer you without writing a post that's as many pages (see what I did there?) as the last Game of Thrones book.

Assumptions

For the sake of discussion, we'll all agree that pagination is basically a function of pageNumber * pageSize. That is, to get the current set of questions in a sorted list of n questions, you can multiply pageNumber by pageSize to offset the number of pages, and then add pageSize to return the current results. In our case, it's really (pageNumber - 1) * pageSize since page 1 is index 0.

In terms of sorting, you never have to completely sort the whole set to return the data. You can effectively only completely sort pageNumber * pageSize data to return the current page correctly sorted, with the rest of the data being partially sorted (such as in a Quick Sort 3 bucket implementation). Rather than sort everything and return the first n results of a set, you can fully sort only the first n results of a set and return those. Make sense? Good.

Also worth noting: the most expensive queries are always the middle pages. To get the last n pages is as cheap as getting the first n pages in a well-built system: just invert the sorting criteria. Getting pageNumber 1 by creation date descending is as easy as getting pageNumber n - 1 where n is the total page count by creation date ascending. This is an optimization that many sorting engines (database, search, etc.) employ, as do we.

Also, for the sake of this discussion, assume that a question is a post and vice versa since I'll use them interchangeably. Good? Good. OK, on to the fun stuff then.

Step 1: Tag Engine

We have a custom built .NET application called the Tag Engine which holds post IDs as well as metadata. Think of it as an inverted index that you can use to look up a post ID by its data (such as creation date, tags, score, etc).

Without overly simplifying the description, the Tag Engine is a .NET application that basically does set theory based on predicates. It takes sets of post IDs and intersects, unions, etc. with other sets of post IDs to get to a final result, which it can also sort in-memory based on meta data.

We query the Tag Engine with page number and page size and any predicates that limit the data (such as Site ID since the Tag Engine handles all network sites). It does in-memory set operations (like union and intersection), and then sorts the results, returning the relevant subset of post IDs.

The Tag Engine also caches the results (the larger set, not just the page you're asking for) and can short-circuit based on a cache key derived from a hash of the query (page number, page size, sorting, etc.) to quickly select a page from that particular cached result set. This helps immensely with performance.

Step 2: The Database

The Tag Engine does not contain the actual question data, just the ID and metadata. So, we take the result set of post IDs and query the SQL database for them. The query looks something like this:

Select p.*, pm.ViewCount, u.Id, u.ProfileImageUrl, ...
From Posts p
    Join PostMetadata pm On p.Id = pm.PostId
    Left Join Users u On p.LastActivityUserId = u.Id
Where p.Id In @Ids";

@Ids here is the list of IDs from the Tag Engine. A query like this brings back the actual post data for us to display. But we're not done yet.

Step 3: Semi-Redundant In-Memory Sort

As discussed above, the Tag Engine might return cached data (an optimization that helps it have awesome performance). However, by its nature, cached data is never guaranteed to be accurate (since it's a snapshot of the past state of things). By contrast, the database always has up-to-date, authoritative data. These sometimes conflict.

To solve this, we sort the resulting page of posts again in memory. This final step resolves the problem where the details of the posts on the given page (their metadata) may have changed in a way that the database can see but the Tag Engine cannot yet see due to caching.

This part isn't very exciting: it's basically an in-memory List<T>.Sort call passing in a function to determine equality. The equality function differs based on the page you're looking at: for Newest tab it compares post creation dates, but for Votes it compares score and answer votes, etc.

If we did not do this final step, posts might sometimes appear out of order on the page since they'd be sorted by the Tag Engine in a way that reflects their past values on things like score or last activity data, as opposed to their current values which the database returns.

Finally, we show you the list of questions!

10
  • 31
    You lost me on "you can sort only the first n results of a set". Are you refering to a selection algorithm (which doesn't require to sort the whole thing, but still looks at every item), or are you implying that the set is pre-sorted?
    – Bergi
    Commented May 2, 2016 at 20:26
  • 2
    If I understand step 3 correctly, we can blame caching if the first result on the second page is newer (hotter, etc) than the last result on the first page?
    – Bergi
    Commented May 2, 2016 at 20:28
  • 26
    Since you seem like a quick writer, if you could possibly help with the next Game of Thrones book, we'd all be very grateful. :-)
    – TylerH
    Commented May 3, 2016 at 14:04
  • 16
    @Bergi say we had a list of 100 integers. If one were to use a QuickSort3 algorithm to sort them from lowest to highest, but we only wanted to display the first 10, we could customize the algorithm to ignore the buckets with lower bound index > 10, which speeds up the algorithm substantially. Basically a form of selection algorithm. You have to traverse and look at all elements to know which ones are in the page, but you don't need to completely sort them all.
    – Haney Staff
    Commented May 3, 2016 at 14:30
  • >>Rather than sort everything and return the first n results of a set, you can sort only the first n results of a set and return those. << Wouldn't that give you perfectly sorted N results, but still with the possibillity that any item N+X having a smaller rank than any of the first N items (and thus being short on the wrong page)? Commented May 3, 2016 at 14:43
  • 2
    Ah you comment shows what you really meant. Please edit that into your question, no? Commented May 3, 2016 at 14:44
  • Yeah, it's not too clear, will update question.
    – Haney Staff
    Commented May 3, 2016 at 15:06
  • 3
    I think you left out some steps: 4) ..., 5) Profit!!! Commented May 3, 2016 at 16:59
  • 2
    "You can effectively only completely sort pageNumber * pageSize data" Actually no. You only completely sort the target range. The bits before that don't need to be fully sorted. Commented May 3, 2016 at 19:11
  • @Haney but in your sql Select p.*, pm.ViewCount, u.Id, u.ProfileImageUrl, ... From Posts p Join PostMetadata pm On p.Id = pm.PostId Left Join Users u On p.LastActivityUserId = u.Id Where p.Id In @Ids There is no filter like where score>3,not really understand how to just sort pagesize-1 * pagesize results,and get the sorted items.
    – Mr Lou
    Commented Apr 27, 2018 at 7:12

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .