I am working on a REST API that potentially could return a lot of data, and one solution to limit the size of responses that I am considering is including paging in the returned data. So we return say the first 1000 results, and paging.
A problem is that it can cost a lot to find those first 1000 results. So when the client requests second page, the obvious thing to do is once again find those first 1000 results, and then search for the second set of 1000 that will actually be returned. And the more previous pages there are, the worse it gets.
Are there other better ways how REST APIs implement pagination?
Edit: to explain why I'd need to find the first 1000 again. The problem is that out of 10'000 results that match the query, the user could have viewing rights only for 5. And rights checks are the expensive part, too. So without saving this info somewhere somehow, it isn't possible to know where to even begin search for the 'next page'.
This isn't an API design issue, it's a data model issue. The fact that you can't query for data the authenticated user is able to view has nothing to do with your API.
That said, consider using cursor based paging instead of count + page number. Which - as an aside - is exactly why is useful to provide the client with simple next / prev links instead of expecting the client to construct the paged link themselves.
If your paging data included the count of results wanted + the last result of the last page, you could construct a query that could just get the next N rows, do the expensive permission check, and then keep fetching until you found the number of results needed.