Discussion: Semantics and complexity of GraphQL

[brysgo]

I found this paper pretty interesting and wanted to see what people thought. Is it worth trying to implement?

https://blog.acolyer.org/2018/05/21/semantics-and-complexity-of-graphql/?blogsub=confirming#subscribe-blog

[ivome]

I am not 100% sure if I understood the paper correctly, but I think this is roughly what this library does. The graphql-js library brings the query into the non-redundant ground-typed normal form, after that, the normalized query is passed to the validation rule which evaluates the cost of the query with a similar algorithm. What parts of the implementation did you want to change / add?

[brysgo]

@ivome - I was just trying to understand rather than change things. There are a bunch of different libraries that try to limit complexity of GraphQL queries, I'm trying to wrap my head around which approach is closest to being accurate.

[FluorescentHallucinogen]

@ivome

The full text of final version of this paper can be found here: https://dl.acm.org/citation.cfm?id=3186014

All I know is that the algorithm described in this paper compute the size of a GraphQL query result (response) without generating this result. The good thing: this algorithm is polynomial in the size of the data and the query/request.

Maybe @hartig and @jorgeperezrojas can explain more. 😉

[FluorescentHallucinogen]

@ivome PTAL at https://youtu.be/oNDmVLRKo_M and http://olafhartig.de/slides/GraphQLEurope2018OlafHartig.pdf.

[FluorescentHallucinogen]

See also apollographql/apollo-server#1310.

[hartig]

@ivome @brysgo I have added a few remarks regarding our paper/algorithm in the following comment apollographql/apollo-server#1310 (comment)

[brysgo]

@hartig - That is great! The formal outline of the algorithm is too foreign to me but I can't wait to take a look at the implementation your student put together. I think that this is an attack vector that our servers should protect against by default.

[ivome]

I just released a new version with some major changes. Most notably the concept of configurable estimators:

We can now create custom estimators that calculate the complexity on a per field basis. We can combine multiple estimators, defined default estimators that are applied to the whole schema etc.

@hartig Maybe the new architecture is of help to implement the scientific paper? But I think the current implementation is already pretty close to the described algorithm if I understood the paper correctly.

[FluorescentHallucinogen]

@ivome PTAL apollographql/apollo-server#1310 (comment).

[hartig]

@ivome Unfortunately, I do not have the time to take a look at your implementation. However, if you are using estimators, it cannot be an implementation of the algorithm introduced in our paper because our algorithm returns the exact size of the query results.

By the way, we have an implementation of the algorithm now. Take a look at: https://github.com/LiUGraphQL/graphql-result-size

Moreover, in the meantime I have also written an informal summary of the paper, including an example that demonstrates how the algorithm works:
http://blog.liu.se/olafhartig/2018/08/08/lightweight-summary-of-our-paper-semantics-and-complexity-of-graphql/

[ivome]

@hartig Thank you for the links and the information. I have written a detailed comment here as this thread already provides a little bit more context:

apollographql/apollo-server#1310 (comment)