POST the filter, get a response back with the query to follow up with for the individual resources.
POST /complex
value1=something
value2=else
201 Created
Location https://example.com/complex/53301a34-92d3-447d-ac98-964e9a8b3989
It adds in some data expiration problems to be solved, but its reasonably RESTful.
This has RESTful aesthetics but it is a bit unpractical if a read-only query changes state on the server, as in creating the uuid-referenced resource.
There's no requirement in HTTP (or REST) to either create a resource or return a Location header.
For the purposes of caching etc, it's useful to have one, as well as cache controls for the query results, and there can be links in the result relative to the Location (eg a link href of "next" is relative to the Location).
Isn't this twice as slow? If your server was far away it would double load times?
The response to POST can return everything you need. The Location header that you receive with it will contain permanent link for making the same search request again via GET.
Pros: no practical limit on query size. Cons: permalink is not user-friendly - you cannot figure out what filters are applied without making the request.