A vastly more performant algorithm for GraphQL field selection merging
Update: I am grateful how well this article was received within the GraphQL community. The algorithm has been implemented in multiple GraphQL server implementations. I published it in Sep 2019 and opened a PR for Sangria GraphQL to add the algorithm as an experimental query validation. Shortly after GraphQL Weekly and Meta For Developers featured this article and by the end of 2021, it was implemented in GraphQL Java and became the default algorithm in Sangria.
On to the article:
Working on a challenging problem is rewarding, especially if you can make progress and share the results. So, without further ado:
I developed an algorithm that significantly improves the runtime performance of the GraphQL validation Field Selection Merging.
What are you talking about?
Let me backtrack a bit: I work as an engineer at XING in the team that is responsible for the development of XING One, a GraphQL proxy for the frontend to access the vast XING-backend landscape. It has been a success in the company, as backend and frontend developers have welcomed it as a sustainable way to enable and accelerate product development. The team is great, and it has been exciting to see the service grow and have an impact.
One of the selling points of GraphQL, and consequently also XING One, is the decoupling of frontend and backend development, which it generally also delivers on.
But sometimes you find a fly in the ointment. For us, one of these flies has been the bad asymptotic runtime complexity of a query validation rule called OverlappingFieldsCanBeMerged. It ensures the validity of queries when multiple field selections have the same output-name.
If multiple field selections with the same response names are encountered during execution, the field and arguments to execute and the resulting value should be unambiguous. Therefore any two field selections which might both be encountered for the same object are only valid if they are equivalent.
[https://graphql.github.io/graphql-spec/June2018/#sec-Field-Selection-Merging]
Unfortunately, the runtime of the algorithm in the reference implementation grows quickly with the number of fragments in the query. As we rely heavily on fragments, due to a modular frontend paradigm, this became an issue for us. We had to limit the number of fragments and repeated output-names that a query can contain. But soon we saw a team wanting to push beyond those limits.
You would imagine that such a problem in a specification and implementation released by a big company (Facebook) and used by others (Twitter) would have been solved already. We are using the Sangria implementation of GraphQL but all implementations that we checked follow the algorithm given by Facebook’s reference implementation graphql-js. It has some optimizations but runtime still blows up with the number of fragments. Here is the code as of the time of this article.
The workaround that seems to be commonly used by bigger GraphQL users is Prepared Queries; they do the validation beforehand and store the queries on the server. But Prepared Queries also have costs and we would prefer not to be forced to use them just because of validation performance:
- They are a serious implementation effort
- They introduce further coupling between backend and frontend: The queries that a frontend makes have to be prepared on the GraphQL server
That led us to dedicate a focused time-box where I could, with the support of the team, concentrate on finding a solution to the original performance problem.
Give me some numbers.
To showcase the improvement that the algorithm laid out in this article can provide, let us have a look at some benchmarks that have been used during the development of the algorithm. They measure the validation rule within the query validation framework of Sangria and have been prepared to discover the shortcomings of the existing algorithm, so they are not representative of real-world performance — if you need that, you need to conduct your own benchmarks.
Nonetheless, they give a good idea of what can go wrong with the old algorithm and how the new one handles these cases. Notice the logarithmic timescale, otherwise the runtime of the new algorithm would show up as a straight horizontal line in some of the graphs.
The old algorithm deals really badly with multiple fragments that are spread in the same selection-set. In the first benchmark we select different fields with different output-names. In the second example we select the same fields with the same output-names. Constructing these detrimental queries is straightforward. They look like this:
Query 101 fragment mergeIdenticalFields1 on Query {
02 viewer { xingId { firstName LastName } }
03 }
04 fragment mergeIdenticalFields2 on Query {
05 viewer { xingId { firstName LastName } }
06 }
07 [...]
08
09 query MultipleFragmentsSameNames {
10 ...mergeIdenticalFields1
11 ...mergeIdenticalFields2
12 [...]
13 }
Repeating a selection in the same selection-set without using fragments is also not ideal.
This benchmark was made to ensure that a particular property of the algorithm does not blow up the runtime. The algorithm includes a condition that compares fields based on their parent types and the benchmark constructs one deep branch of selections where on each level a fragment is spread and abstract and concrete parent types are present. Why this is important to test will become clear later on.
How does it work?
The ideas behind the new algorithm:
1. Minimize recursive branching by utilizing subset relationships
2. Turn requirements of pair-wise conflict-freedom in a set of fields into uniqueness requirements of a property in the set
3. Efficiently reuse already computed results
Let us start with the original algorithm, as given by the GraphQL specification, and transform it, all the while reasoning that it will stay correct.
Listing 1Formal Specification
* Let set be any selection set defined in the GraphQL document.
* FieldsInSetCanMerge(set) must be true.
FieldsInSetCanMerge(set):
1) Let fieldsForName be the set of selections with a given
response name in set including visiting fragments and inline
fragments.
2) Given each pair of members fieldA and fieldB in fieldsForName:
a) SameResponseShape(fieldA, fieldB) must be true.
b) If the parent types of fieldA and fieldB are equal or if
either is not an Object Type:
1) fieldA and fieldB must have identical field names.
2) fieldA and fieldB must have identical sets of arguments.
3) Let mergedSet be the result of adding the selection set
of fieldA and the selection set of fieldB.
4) FieldsInSetCanMerge(mergedSet) must be true.
SameResponseShape(fieldA, fieldB):
1) Let typeA be the return type of fieldA.
2) Let typeB be the return type of fieldB.
3) If typeA or typeB is Non-Null.
a) If typeA or typeB is nullable, return false.
b) Let typeA be the nullable type of typeA
c) Let typeB be the nullable type of typeB
4) If typeA or typeB is List.
a) If typeA or typeB is not List, return false.
b) Let typeA be the item type of typeA
c) Let typeB be the item type of typeB
d) Repeat from step 3.
5) If typeA or typeB is Scalar or Enum.
a) If typeA and typeB are the same type return true,
otherwise return false.
6) If typeA or typeB is not a composite type, return false.
7) Let mergedSet be the result of adding the selection
set of fieldA and the selection set of fieldB.
8) Let fieldsForName be the set of selections with a given
response name in mergedSet including visiting fragments
and inline fragments.
9) Given each pair of members subfieldA and subfieldB in
fieldsForName:
a) If SameResponseShape(subfieldA, subfieldB) is false,
return false.
10) Return true.
As a prerequisite let us assume that the set of effective selection sets at a field (“including visiting fragments and inline fragments”) can either be precomputed or derived during the algorithm. In our implementation the set of effective selection-sets for a field is precomputed and deduplicated by a single pass over the query at the beginning of the validation.
To better see the recursive structure, let us break out [Listing 1, FieldsInSetCanMerge 2.b.1–2] and [Listing 1, SameResponseShape 1–6] into helper methods that implement the requirements. Let us also turn the specification into a pseudo-code implementation. For brevity we drop the “return true” statements at the end of functions.
Listing 2
01 FieldsInSetCanMerge(set):
02 for fieldsForName in groupSelectionsByOutputName(set)
03 for fieldA and fieldB in fieldsForName
04 SameResponseShape(fieldA, fieldB)
05 If the parent types of fieldA and fieldB are equal or if
06 either is not an Object Type:
07 requireSameNameAndArguments(fieldA, fieldB)
08 mergedSet = mergeSelections(fieldA, fieldB)
09 FieldsInSetCanMerge(mergedSet)
10
11 SameResponseShape(fieldA, fieldB):
12 requireSameOutputTypeShape(fieldA, fieldB)
13 mergedSet = mergeSelections(fieldA, fieldB)
14 for fieldsForName in groupSelectionsByOutputName(mergedSet)
15 for subfieldA and subfieldB in fieldsForName
16 SameResponseShape(subfieldA, subfieldB)These are two recursive functions where the first one calls the other at every level of recursion. The recursive calls are in iterations over pairs of fields in sets, which introduces a quadratic blowup.
Our first milestone will be to turn the two branching functions into independent recursions by reasoning about subset relationships over recursive calls.
But first, let us turn [Listing 2, SameResponseShape] into a function that works on a set of fields. If you take a closer look at [Listing 2, 2–4] and [Listing 2, 14–16], you will notice that they look exactly the same. That allows us to reorder: We call SameResponseShape directly on a set of fields and move the grouping by output-name and the iteration over pairs of members into the function itself. To signify the changed behavior let us call the new function SameResponseShapeByName.
Listing 3
01 FieldsInSetCanMerge(set):
02 SameResponseShapeByName(set)
03 for fieldsForName in groupSelectionsByOutputName(set)
04 for fieldA and fieldB in fieldsForName
05 If the parent types of fieldA and fieldB are equal or if
06 either is not an Object Type:
07 requireSameNameAndArguments(fieldA, fieldB)
08 mergedSet = mergeSelections(fieldA, fieldB)
09 FieldsInSetCanMerge(mergedSet)
10
11 SameResponseShapeByName(set):
12 for fieldsForName in groupSelectionsByOutputName(set)
13 for fieldA and fieldB in fieldsForName
14 requireSameOutputTypeShape(fieldA, fieldB)
15 mergedSet = mergeSelections(fieldA, fieldB)
16 SameResponseShapeByName(mergedSet)Now, that we have two functions working on sets of fields, it is easier to reason about subset relationships over calls. The extra call to SameResponseShapeByName in [Listing 3, 2] is always for the same set of fields as FieldsInSetCanMerge received itself. But SameResponseShapeByName in [Listing 3, 16] also does a recursive call. The set of calls with mergedSet in [Listing 3, 9] is always a subset of the set of calls with the mergedSet in [Listing 3, 16]. They are both constructed the same way from the initial set, only [Listing 3, 5–6] does introduce an extra condition and excludes some pairings from the next recursion level.
This means the added recursive calls to SameResponseShapeByName from FieldsInSetCanMerge do not find any new conflicts, as the calls are also already done by SameResponseShapeByName in [Listing 3, 16] itself. We can run both recursions independently from each other without losing conflicts or adding conflicts that we did not find before. The toplevel function is now FieldsInSetCanMerge and we introduce a new function SameForCommonParentsByName that does the recursive check that was previously done in FieldsInSetCanMerge.
Listing 401 FieldsInSetCanMerge(set):
02 SameResponseShapeByName(set)
03 SameForCommonParentsByName(set)
04
05 SameForCommonParentsByName(set):
06 for fieldsForName in groupSelectionsByOutputName(set)
07 for fieldA and fieldB in fieldsForName
08 If the parent types of fieldA and fieldB are equal or if
09 either is not an Object Type:
10 requireSameNameAndArguments(fieldA, fieldB)
11 mergedSet = mergeSelections(fieldA, fieldB)
12 SameForCommonParentsByName(mergedSet)
13
14 SameResponseShapeByName(set):
15 for fieldsForName in groupSelectionsByOutputName(set)
16 for fieldA and fieldB in fieldsForName
17 requireSameOutputTypeShape(fieldA, fieldB)
18 mergedSet = mergeSelections(fieldA, fieldB)
19 SameResponseShapeByName(mergedSet)
This already improves upon the performance of the original specification as it avoids some unnecessary recursive calls and simplifies the recursive structure, which helps us in further reasoning about the algorithm.
The next milestone will be to get rid of the iterations over pairs of fields from sets of fields. We will transform the recursive call further, avoiding the iteration over pairs of fields, and then apply step 2 of our outline of performance improvements and also check the requirements on a set of fields directly.
Lemma 1
Given a set of fields F and a covering set of subsets S:
We have:
Here is why this is true:
1. Every comparison, that is made in the function, is solely the result of two fields (which may be the same field) being in the same argument-set.
2. Every recursive call is made on a set of fields that is the result of merging the selections of two fields in the argument-set.
3. On the left-hand side as well as on the right-hand side all pairs of fields from F will be in one of the argument-sets and there are no additional pairings.
For reference here is the current version of SameResponseShapeByName in a new listing.
Listing 501 SameResponseShapeByName(set):
02 for fieldsForName in groupSelectionsByOutputName(set)
03 for fieldA and fieldB in fieldsForName
04 requireSameOutputTypeShape(fieldA, fieldB)
05 mergedSet = mergeSelections(fieldA, fieldB)
06 SameResponseShapeByName(mergedSet)
Lemma 1 allows us to change the recursive step of SameResponseShapeByName into working on the whole merged set of sets of selections for each name. The pairwise merged selections of fields in fieldsForName in [Listing 5, 5] constitute a covering set of subsets of the set that is obtained by merging the selections of all fields in fieldsForName in [Listing 4, 2].
Listing 6
01 SameResponseShapeByName(set):
02 for fieldsForName in groupSelectionsByOutputName(set)
03 for fieldA and fieldB in fieldsForName
04 requireSameOutputTypeShape(fieldA, fieldB)
05 mergedSet = mergeSelections(fieldsForName)
06 SameResponseShapeByName(mergedSet)Now we are finally in a state that allows us to turn the pair-wise comparison in [Listing 6, 4] into a uniqueness property of the output-type-shape in each set fieldsForName.
Listing 7
01 SameResponseShapeByName(set):
02 for fieldsForName in groupSelectionsByOutputName(set)
03 requireSameOutputTypeShape(fieldsForName)
04 mergedSet = mergeSelections(fieldsForName)
05 SameResponseShapeByName(mergedSet)It is easy to implement a representation for the output-type-shape that allows checking uniqueness in a set of fields in O(n).
Let us do something similar for SameForCommonParentsByName.
Lemma 2
Given a set of fields F and a covering set of subsets S:
We have:
This is true by similar reasoning as Lemma 1. For reference here is the current version of SameForCommonParentsByName in a new listing.
Listing 801 SameForCommonParentsByName(set):
02 for fieldsForName in groupSelectionsByOutputName(set)
03 for fieldA and fieldB in fieldsForName
04 If the parent types of fieldA and fieldB are equal or if
05 either is not an Object Type:
06 requireSameNameAndArguments(fieldA, fieldB)
07 mergedSet = mergeSelections(fieldA, fieldB)
08 SameForCommonParentsByName(mergedSet)
Rewriting the recursive call and the requirement is a bit more complicated in this case, as we have the additional condition in [Listing 8, 4–5].
We will have to understand which set of fields this condition will compare to each other. There are two cases: the parent type of the field could be a concrete Object type or it could be an abstract type, i.e. an Interface or a Union; for the purpose of the condition there is no difference between these.
It compares the fields, that could potentially (now or in future schema evolution) have a common parent. An abstract type could be a common parent with any other type, so fields with abstract parents are compared to all other fields. Fields with concrete parents are only compared to fields with the same concrete parent and fields with any abstract parent.
Our goal is to construct the minimum number of groups of fields in fieldsForName in [Listing 8, 2] such that for each pair of fields that passes the condition in [Listing 8, 4–5], there exists a set in groups that contains both fields and for each one that does not pass, there does not exist such a set in groups. By applying Lemma 2 we will then rewrite the recursion to work on those groups instead. As the condition is symmetric and reflexive, we will be able to construct the groups.
As two fields with concrete parent types cannot be in the same group, the minimum number of groups will be constructed by merging the set of fields with the same concrete parent type with the set of fields with abstract parent types for each concrete parent type. Should there be only fields with abstract parent types, we can directly return them in one group.
Listing 901 groupByCommonParents(set):
02 abstractGroup = all fields with abstract parents in set
03 concreteGroups = group fields by concrete parents in set
04 if empty(concreteGroups)
05 groups = [set]
06 else
07 groups = concreteGroups
08 for group in groups
09 group := merge(group, abstractGroup)
10 return groups
This time let us rewrite the recursive step using Lemma 2 and the pair-wise comparisons in SameForCommonParentsByName in one step and also include the previous functions to conclude this set of transformations.
Listing 1001 FieldsInSetCanMerge(set):
02 SameResponseShapeByName(set)
03 SameForCommonParentsByName(set)
04
05 SameResponseShapeByName(set):
06 for fieldsForName in groupSelectionsByOutputName(set)
07 requireSameOutputTypeShape(fieldsForName)
08 mergedSet = mergeSelections(fieldsForName)
09 SameResponseShapeByName(mergedSet)
10
11 SameForCommonParentsByName(set):
12 for fieldsForName in groupSelectionsByOutputName(set)
13 for fieldsForParentsin groupByCommonParents(fieldsForName)
14 requireSameNameAndArguments(fieldsForParents)
15 mergedSet = mergeSelections(fieldsForParents)
16 SameForCommonParentsByName(mergedSet)
17
18 groupByCommonParents(set):
19 abstractGroup = all fields with abstract parents in set
20 concreteGroups = group fields by concrete parents in set
21 if empty(concreteGroups)
22 groups = [set]
23 else
24 groups = concreteGroups
25 for group in groups
26 group := merge(group, abstractGroup)
27 return groups
By having gotten rid of the pair-wise comparisons and recursions we have significantly reduced the complexity of these functions. However, we still have a problem: grouping by possibly common parent types in [Listing 10, groupByCommonParents] can result in the fields with abstract parent types being part of multiple comparison groups for a set of fields. This will multiply the recursive calls for them and potentially compare the same child selections multiple times. One such situation was tested by the benchmark “Deep Branch With Abstract And Concrete Parent Types”. We can remedy it by efficiently reusing already computed results.
In the last version of these functions, each step operates on a set-of-fields. And we took care to minimize recursive branching on sets-of-fields in the construction of the algorithm. This gives us the perfect opportunity for fine-grained caching of each step by the set-of-fields that it operates on. It is beneficial to build a linked structure of caches as presented here instead of always retrieving the cache object for the next set of fields, as one cache entry holds results for multiple functions.
Listing 1101 cache: Map from FieldSet to CacheEntry = new empty map
02
03 FieldsInSetCanMerge(set):
04 cacheEntry = GetOrCreateCacheEntry(set)
05 cacheEntry.SameResponseShapeByName()
06 cacheEntry.SameForCommonParentsByName()
07
08 GetOrCreateCacheEntry(set):
09 find a CacheEntry in cache or create and store a new one
10
11 class CacheEntry:
12 // the set of fields that this cache entry is for
13 set: FieldSet
14
15 //Functions on a set of fields are cached, also those
16 //helper functions that compute potentially shared results
17 cacheGroupSelectionsByOutputNames: List of CacheEntry = null
18 cacheGroupByCommonParents: List of CacheEntry = null
19 cacheMergeSelections: CacheEntry = null
20 didRequireSameResponseShape: Boolean = false
21 didRequireSameNameAndArguments: Boolean = false
22 didCallSameResponseShapeByName: Boolean = false
23 didCallSameForCommonParentTypes: Boolean = false
24
25 SameResponseShapeByName():
26 if didCallSameResponseShapeByName return
27 didCallSameResponseShapeByName = true
28 for fieldsForName in this.groupSelectionsByOutputName()
29 fieldsForName.requireSameOutputTypeShape()
30 mergedSet = fieldsForName.mergeSelections()
31 mergedSet.SameResponseShapeByName()
32
33 SameForCommonParentsByName():
34 if didRequireSameResponseShape return
35 didCallSameForCommonParentTypes = true
36 for fieldsForName in this.groupSelectionsByOutputName()
37 for fieldsForParentsin fieldsForName.groupByCommonParents()
38 fieldsForParents.requireSameNameAndArguments()
39 mergedSet = fieldsForParents.mergeSelections()
40 mergedSet.SameForCommonParentsByName()
41
42 groupByCommonParents():
43 if cacheGroupByCommonParents != null
44 return cacheGroupByCommonParents
45 abstractGroup = all fields with abstract parents in this.set
46 concreteGroups = group fields by concrete parents in this.set
47 if empty(concreteGroups)
48 groups = [this]
49 else
50 groups = concreteGroups
51 for group in groups
52 group := merge(group, abstractGroup)
53 group := GetOrCreateCacheEntry(group)
54 cacheGroupByCommonParents := groups
55 return groups
This is the final algorithm. For an actual implementation have a look at our Sangria fork and the pull request to get the algorithm into the mainline. Should you notice any problem with the algorithm as presented here, or have any questions, I would be happy to hear from you.
