How to handle an offset greater than 2000 on SOQL without sorting by ID or date using the Salesforce Rest API

Right now I'm working on migrating a site from using an oracle database to use salesforce. For querying the data we are using the latest version of the salesforce rest API. Right now I'm facing a problem paginating results with an offset greater than 2000. I have seen quite a few questions on this topic but none of them seem to fit my problem.

So Here are the restrictions

I need to fetch the results on chunks of 20 records (that is the page size). I can't just get a bunch of results and then do some manual pagination because that would be out of scope for the project.
I can't do something like WHERE ID > lastIdIntheResults LIMIT 20 because I need to sort my results by Name, sorting by Id would break the order that the client expects.
Needs to be done using the REST API. I don't think there is a way to use queryMore function on the REST API.

So, do you have any suggestions?

Thanks

Solution

REST API's equivalent of SOAP API's queryMore is done: false and nextRecordsUrl: ... in the response.

https://developer.salesforce.com/docs/atlas.en-us.api_rest.meta/api_rest/dome_query.htm

Here's my data queried via https://workbench.developerforce.com -> Utilities -> Rest Explorer:

And then the next one would be

And to change the "chunk size" without LIMIT/OFFSET you can use a HTTP header: Sforce-Query-Options: batchSize=200