When you are jumping large numbers of pages, you usually don't care about exact page boundaries.

For example, you could have a background process that slowly paginates through the table and saves off the page boundaries, which you can then use for jumping into. They will always be a bit off especially near the middle of the table, but that's probably okay.

There's lots of ways to do this fuzzy jumping that don't involve scanning the full table synchronously.