We may be able to implement this by wrapping the database layer.
If it can find a pagination index record covering a pagination, it would fall back to regular use of offsets. This is important, as we can't immediately rebuild the index every time a post is added/deleted - we can do it in the background using a Cron hook (which depends on #3958).

It's also important to consider different sort orders and filters that may be active. There may need to be more fields and more indexes for the index table.

We should also try and cache counts for particular paginations.