How to send larger amounts of data to a stateless RESTful retrieval service

This seems quite a basic question so apologies if this has been asked before; please point me in the direction of any useful resources.

So I have a RESTful service to retrieve some data. However, the RESTful service requires a certain amount of data in order to do the retrieval. This data could be roughly summed up as "user context" data - information about the user (whether stored by the calling application or previously retrieved from another application) which the service needs to use to action the retrieval.

Since REST works semantically, the correct verb (HTTP method) to retrieve something is a GET request. Most example GET requests I have seen only use small amounts of data, and the data is passed on the URL. However once we get into the realm of services which require larger amounts of data to make the retrieval, it seems wrong to put all that information in the URL. Not only that, but there are known limits to URL length enforced by certain components (often 255 characters or so, IIRC).

Seemingly the options available are:

• Use POST to send the data in the request body. However, this is not semantic since we are not asking the service to update anything, only retrieve.
• Put the larger portion of information (in my case, the "user context") into an HTTP header. However, this "feels wrong" as headers should be used for headers, not data.
• Make multiple requests to send the data in multiple URLs. However this seems to break the stateless goal, as the service would have to maintain some kind of state to tie the requests together.
• Write the data to a database and then pass the service a key to retrieve the data from there. However this would result in the request not being self-contained and also introduce performance bottlenecks.

Is there another option? What's the best practice here?

If your goal is that you want to do some complex read operation, you want to pass a lot of data to do so and want to use an appropriate HTTP method these are probably your best 2 options:

1. Do a POST request to create a 'query resource', and then do a separate GET request to receive the result of that query.
2. Use the HTTP QUERY method, which is specifically designed for this purpose. QUERY is basically a POST-like method but it's intended for safe, idempotent read operations and supports a body. It's relatively new but most HTTP clients and servers accept any HTTP method known or unknown.

Option 1 effectively gives you a URL that you can re-use, link to and do GET operations on, which can be especially helpful in hypermedia applications. The drawback is that the server needs to remember more, it requires 2 http requests and you might need some kind of cleanup, which makes option 2 much easier to implement.