If you want to be purely restful, you'd POST your request with all the parameters, which would create a new query resource, and then return the query resource ID. You would then make a second GET request with just the query ID.

The GET would be cacheable because they query would be repeatable and idempotent. In theory you'd never have to make the POST more than once unless you are creating a new query, which would make a new ID.