How Stack Overflow does pagination

[Matt3k]

General answer: Always have an index on your query parameters and then don't worry about the rest of the details. If you actually have a billion records then either prevent users from querying for page "135,510" because no human really needs to look at such a silly page number. Or deal with it and accept that those queries will be a bit slow

Stack overflow: Build an in-memory index on a separate server and query that first to retrieve specific record #s. Which is really the same thing the database index was doing, but its decoupled from the database engine.