Idea: Cost function on fields, to allow ballpark analysis of query complexity about graphql-spec HOT 8 CLOSED

One can provide reasonably faithful cost estimations for evaluating a graph query, if the average branching factors of edge types (i.e. fields) can be calculated from the contents of the data store.

In case of the Star Wars example, if you have a query like
hero { name friends { name } }
then you can estimate the number of friends expected to be retrieved by calculating the average branching factor for friends which is (4+1+3+4+1+4+3)/7 = 2.85 in case of the Star Wars knowledge base. One can further customize this estimate for friends edges running between specific types of nodes.

In case of nested queries, like
{ hero { name friends { name appearsIn friends { name } } } }
one can estimate the size of the expected result set by a sum-product.
The result set is expected to contain

• H nodes for heros, plus
• H * F nodes by navigating along friends from each hero (where F=2.85 above), plus
• H * F * A nodes by further navigating along appearsIn from each of the previous nodes.

We described this estimate 10 years ago in an academic paper, so better estimates are likely to exist since then.

(I am new to GraphQL as a language, sorry if I misused its terminology - or gave a far too academic answer...)

from graphql-spec.

I think this would be an awesome project for someone to start up if anyone in the community is looking for ideas.

from graphql-spec.

I just found out that this has been implemented in Sangria:

http://sangria-graphql.org/learn/#query-complexity-analysis

To that end, it might not be necessary to define it in the spec, and leave it up to implementations instead.

from graphql-spec.

I think this provides too narrow a view of how the cost might be calculated. For instance, the cost would at least depend on the arguments in a lot of cases, like of a paginated field (e.g. users(first: $count)). The cost might also depend on other similar selections, which might even re-use the same data, e.g. when using dataloader to batch load and cache datastore queries.

Trying to calculate the cost of a query before it is made can actually be quite difficult, so another possible approach would be to use time as the unit of cost, where a timeout would be used to abort expensive queries.

I think it should just be an implementation detail.

from graphql-spec.

This is great additional context and insight, thanks!

from graphql-spec.

I wouldn't put faith in cost estimations that rely on averages with respect to branching factors. The average might be very low but if you are trying to protect against abuse, then you really want to pay attention the upper bound on the branch factor.

Also, be careful about calculating the cost of queries that require server-side filtering, since they could scan a large number of objects and return very few results. The cost of a request isn't always about the amount of data that is returned.

Maybe this discussion can be moved to the graphql-js repo, since it doesn't seem like something to standardize in the graphql spec.

from graphql-spec.

Here's an interesting package that does a pretty good cost analysis for graphql queries: https://github.com/pa-bru/graphql-cost-analysis

from graphql-spec.

Closing this aging issue.

Seems like the consensus is that field cost alone is not always enough to estimate a query’s cost. Different approaches by different libraries indicate that there are many useful approaches with different trade offs, so there is not much to incorporate into the spec to account for this

from graphql-spec.