I'd suggest that you be wary of going down the route of making your API too flexible. It becomes very difficult to scale up a service that provides flexibility.
Imagine a simple case where you're storing hundreds of records of users, and providing the flexibility to order by any field on the user, and of course, you're paginating those results. Now, scale up; you're storing tens of millions of those same record... how do you quickly retrieve the first ten records ordered by their e-mail address field? Same thing, ordered by their last name. Same thing, ordered by their country. Did you just create database indexes to support each of those use cases? Ugh.
In my opinion, a REST API (well, any API) should be limited to supporting only the business use-cases it is designed to implement. I wouldn't want to build a "Linq/SQL" type of interface, because then I have to support all the weird queries people will come up, and still meet my requirements to scale over time. Don't provide this kind of flexibility unless the value it gives your product is absolutely incredible, because, the headaches it provides could be equally incredible.
> Imagine a simple case where you're storing hundreds of records of users, and providing the flexibility to order by any field on the user...
You don't have to allow ordering by any field. You can define a list of fields that you can order by, and only allow those. I don't see the problem with doing that. But if you must allow ordering by any field...
> Did you just create database indexes to support each of those use cases? Ugh.
...then yes, you would need to do that.
I think the cool thing about GraphQL (at least from my understanding) is it doesn't necessarily give you full power to query data in any arbitrary way from the client--it just provides a more flexible interface for defining what data you want returned from the API and how you want that data structured. It doesn't necessarily have to be a 1:1 mapping of your DB schema, and in most cases I don't think it should be.
This is a great sum-up of a point I often find myself making a lot when explaining GraphQL. GraphQL is only capable of doing exactly what the server-side developer lets it. Order-by is a really great example. We can sort by only the things that make sense to sort by, and often at Facebook we're sorting by heuristics like "sort my friends by how likely I am to send them a message" when loading the friends in a typeahead for chat, and this idea of "message send likelihood" is not exposed as a field.
Imagine a simple case where you're storing hundreds of records of users, and providing the flexibility to order by any field on the user, and of course, you're paginating those results. Now, scale up; you're storing tens of millions of those same record... how do you quickly retrieve the first ten records ordered by their e-mail address field? Same thing, ordered by their last name. Same thing, ordered by their country. Did you just create database indexes to support each of those use cases? Ugh.
In my opinion, a REST API (well, any API) should be limited to supporting only the business use-cases it is designed to implement. I wouldn't want to build a "Linq/SQL" type of interface, because then I have to support all the weird queries people will come up, and still meet my requirements to scale over time. Don't provide this kind of flexibility unless the value it gives your product is absolutely incredible, because, the headaches it provides could be equally incredible.