How to organize search in microservice architecture?

Question

Software design

For example, I have two services: clients and orders, and a gateway that exposes the API.
I want to be able to send a request to the gate: give me all the orders of a client with the last name Ivanov, issued after November 25th.
The problem is this: the customer service knows the names, but does not know the dates of the orders. And the order service knows the dates, but does not know the last name (orders are associated with customers through the customer ID).
How to organize the search in this case?
I see three solutions:
1. Add a third service (search service) that knows both about orders and about clients (then it is not clear why the first two services are needed);
2. Add a third service that works, for example, with Elasticsearch, and the first two services periodically push indexes there;
3. From the gate, first search for all customers with the last name Ivanov, and then transfer their IDs to the order service and filter by date.
The third option seems the most reasonable, but my example is simple. If we add to the gate, for example, also sorting first by last name in ascending order, and then by order number in descending order, then it turns out that I should receive all orders that meet the search criteria at the gate and sort it in real time.
In short, how to organize search, sorting and paging in microservices?