What kind of client are we talking about here? If you run a web app then all your queries will be predefined in the code which means that the only variables are just that, variables. If you are talking about other apps consuming your GraphQL API then yes, they can request whatever permutation they want. But realistically, what client that consumes your API would keep changing the shape of their request all the time? And if they do then just revoke their access. Abusive clients is not a problem exclusive to GraphQL.
SQL databases often have query caches for this reason.
I agree about DoS, but I figure that's going to require the usual defences around throttling. Ideally in the database, but most databases of any kind don't have workload partitioning.