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.
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.
Mutations are just top level fields, but with side effects; because they are fields, the client sends up a selection set with the mutation. This allows the client to receive whatever data it needs to refresh, as the response to the mutation.
GraphQL was originally designed for reads, but we added write support to solve the parallel problem we were having with writes: different clients wanted different data back from the server after they performed a write. GraphQL gave us that capability.