Skip to content

Commit 19093fe

Browse files
gkeslerbbakerman
gkesler
authored and
bbakerman
committed
- performance improvements to a bleading findImplementations mechanizm.
`graphql.schema.SchemaUtil.findImplementations` method performs expensive O(n^2) search for object types that implement given interface. Executed at least twice per query this mechanizm significantly slows down query execution. Replaced with another mechanizm that indexes and groups object types by their implemented interfaces at the schema creation time and runtime needs are satisfied by simple O(1) lookup in a hash map. Our performance tests indicated up to 10x boost in query executio. n
1 parent 363d9a3 commit 19093fe

File tree

6 files changed

+94
-11
lines changed

6 files changed

+94
-11
lines changed

‎src/main/java/graphql/execution/FieldCollector.java‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -150,7 +150,7 @@ private boolean checkTypeCondition(FieldCollectorParameters parameters, GraphQLT
150150
}
151151

152152
if (conditionType instanceof GraphQLInterfaceType) {
153-
List<GraphQLObjectType> implementations = schemaUtil.findImplementations(parameters.getGraphQLSchema(), (GraphQLInterfaceType) conditionType);
153+
List<GraphQLObjectType> implementations = parameters.getGraphQLSchema().getImplementations((GraphQLInterfaceType)conditionType);
154154
return implementations.contains(type);
155155
} else if (conditionType instanceof GraphQLUnionType) {
156156
return ((GraphQLUnionType) conditionType).getTypes().contains(type);

‎src/main/java/graphql/introspection/Introspection.java‎

Lines changed: 1 addition & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -23,7 +23,6 @@
2323
import graphql.schema.GraphQLScalarType;
2424
import graphql.schema.GraphQLSchema;
2525
import graphql.schema.GraphQLUnionType;
26-
import graphql.schema.SchemaUtil;
2726
import graphql.schema.visibility.GraphqlFieldVisibility;
2827

2928
import java.util.ArrayList;
@@ -201,7 +200,7 @@ private static String print(Object value, GraphQLInputType type) {
201200
public static final DataFetcher possibleTypesFetcher = environment -> {
202201
Object type = environment.getSource();
203202
if (type instanceof GraphQLInterfaceType) {
204-
return new SchemaUtil().findImplementations(environment.getGraphQLSchema(), (GraphQLInterfaceType) type);
203+
return environment.getGraphQLSchema().getImplementations((GraphQLInterfaceType)type);
205204
}
206205
if (type instanceof GraphQLUnionType) {
207206
return ((GraphQLUnionType) type).getTypes();

‎src/main/java/graphql/schema/GraphQLSchema.java‎

Lines changed: 27 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -40,6 +40,7 @@ public class GraphQLSchema {
4040
private final Set<GraphQLType> additionalTypes;
4141
private final Set<GraphQLDirective> directives;
4242
private final GraphqlFieldVisibility fieldVisibility;
43+
private final Map<GraphQLOutputType, List<GraphQLObjectType>> byInterface;
4344

4445

4546
public GraphQLSchema(GraphQLObjectType queryType) {
@@ -59,14 +60,18 @@ public GraphQLSchema(GraphQLObjectType queryType, GraphQLObjectType mutationType
5960
assertNotNull(queryType, "queryType can't be null");
6061
assertNotNull(directives, "directives can't be null");
6162
assertNotNull(fieldVisibility, "fieldVisibility can't be null");
63+
64+
SchemaUtil schemaUtil = new SchemaUtil();
65+
6266
this.queryType = queryType;
6367
this.mutationType = mutationType;
6468
this.subscriptionType = subscriptionType;
6569
this.fieldVisibility = fieldVisibility;
6670
this.additionalTypes = additionalTypes;
6771
this.directives = new LinkedHashSet<>(Arrays.asList(Directives.IncludeDirective, Directives.SkipDirective));
6872
this.directives.addAll(directives);
69-
typeMap = new SchemaUtil().allTypes(this, additionalTypes);
73+
this.typeMap = schemaUtil.allTypes(this, additionalTypes);
74+
this.byInterface = schemaUtil.groupImplementations(this);
7075
}
7176

7277
public Set<GraphQLType> getAdditionalTypes() {
@@ -94,11 +99,31 @@ public GraphQLObjectType getObjectType(String typeName) {
9499
}
95100
return (GraphQLObjectType) graphQLType;
96101
}
97-
102+
103+
Map<String, GraphQLType> getTypeMap () {
104+
return typeMap;
105+
}
106+
98107
public List<GraphQLType> getAllTypesAsList() {
99108
return new ArrayList<>(typeMap.values());
100109
}
101110

111+
/**
112+
* Introduced to replace costly {@link graphql.schema.SchemaUtil#findImplementations(graphql.schema.GraphQLSchema, graphql.schema.GraphQLInterfaceType)}
113+
* method in order to avoid redundant indexing operation of O(n^2) complexity during query execution.
114+
* Indexing is performed at Schema creation by {@link graphql.schema.SchemaUtil#groupImplementations(graphql.schema.GraphQLSchema)}
115+
* This method just obtains results, which brings the complexity down to O(1)
116+
*
117+
* @param type interface type to obtain implementations of.
118+
* @return list of types implementing provided interface
119+
*/
120+
public List<GraphQLObjectType> getImplementations (GraphQLInterfaceType type) {
121+
List<GraphQLObjectType> implementations = byInterface.get(type);
122+
return (implementations == null)
123+
? Collections.emptyList()
124+
: new ArrayList<>(implementations);
125+
}
126+
102127
public GraphQLObjectType getQueryType() {
103128
return queryType;
104129
}

‎src/main/java/graphql/schema/SchemaUtil.java‎

Lines changed: 52 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -13,6 +13,7 @@
1313
import java.util.Set;
1414

1515
import static java.lang.String.format;
16+
import java.util.HashMap;
1617

1718
@Internal
1819
public class SchemaUtil {
@@ -150,7 +151,7 @@ private void collectTypesForInputObjects(GraphQLInputObjectType objectType, Map<
150151
}
151152

152153

153-
public Map<String, GraphQLType> allTypes(GraphQLSchema schema, Set<GraphQLType> additionalTypes) {
154+
Map<String, GraphQLType> allTypes(GraphQLSchema schema, Set<GraphQLType> additionalTypes) {
154155
Map<String, GraphQLType> typesByName = new LinkedHashMap<>();
155156
collectTypes(schema.getQueryType(), typesByName);
156157
if (schema.isSupportingMutations()) {
@@ -168,10 +169,57 @@ public Map<String, GraphQLType> allTypes(GraphQLSchema schema, Set<GraphQLType>
168169
return typesByName;
169170
}
170171

172+
/**
173+
* Indexes GraphQLObject types registered with the provided schema by implemented GraphQLInterface
174+
* Accelerates/simplifies collecting types that implement a certain interface
175+
* Provided to replace {@link #findImplementations(graphql.schema.GraphQLSchema, graphql.schema.GraphQLInterfaceType)}
176+
*
177+
* @see graphql.schema.GraphQLSchema#getImplementations(graphql.schema.GraphQLInterfaceType)
178+
*
179+
* @param schema
180+
* @return
181+
*/
182+
Map<GraphQLOutputType, List<GraphQLObjectType>> groupImplementations (GraphQLSchema schema) {
183+
Map<GraphQLOutputType, List<GraphQLObjectType>> result = new HashMap<>();
184+
for (GraphQLType type: schema.getAllTypesAsList()) {
185+
if (type instanceof GraphQLObjectType) {
186+
for (GraphQLOutputType intf: ((GraphQLObjectType)type).getInterfaces()) {
187+
List<GraphQLObjectType> myGroup = result.get(intf);
188+
if (myGroup == null) {
189+
result.put(intf, myGroup = new ArrayList<>());
190+
191+
}
192+
193+
myGroup.add((GraphQLObjectType)type);
194+
}
195+
}
196+
}
197+
198+
return result;
199+
}
200+
201+
/**
202+
* This method is deprecated due to performance degradation.
203+
*
204+
* Algorithm complexity: O(n^2), where n is number of registered GraphQLTypes
205+
* Indexing operation is performed twice per input document:
206+
* 1. during validation
207+
* 2. during execution
208+
*
209+
* Indexed all types at the schema creation, which brought complexity down to O(1)
210+
*
211+
* @see #groupImplementations(graphql.schema.GraphQLSchema)
212+
* @see graphql.schema.GraphQLSchema#getImplementations(graphql.schema.GraphQLInterfaceType)
213+
*
214+
* @param schema GraphQL schema
215+
* @param interfaceType an interface type to find implementations for
216+
* @return List of object types implementing provided interface
217+
* @deprecated
218+
*/
219+
@Deprecated
171220
public List<GraphQLObjectType> findImplementations(GraphQLSchema schema, GraphQLInterfaceType interfaceType) {
172-
Map<String, GraphQLType> allTypes = allTypes(schema, schema.getAdditionalTypes());
173221
List<GraphQLObjectType> result = new ArrayList<>();
174-
for (GraphQLType type : allTypes.values()) {
222+
for (GraphQLType type : schema.getAllTypesAsList()) {
175223
if (!(type instanceof GraphQLObjectType)) {
176224
continue;
177225
}
@@ -183,7 +231,7 @@ public List<GraphQLObjectType> findImplementations(GraphQLSchema schema, GraphQL
183231

184232

185233
void replaceTypeReferences(GraphQLSchema schema) {
186-
Map<String, GraphQLType> typeMap = allTypes(schema, schema.getAdditionalTypes());
234+
Map<String, GraphQLType> typeMap = schema.getTypeMap();
187235
for (GraphQLType type : typeMap.values()) {
188236
if (type instanceof GraphQLFieldsContainer) {
189237
resolveTypeReferencesForFieldsContainer((GraphQLFieldsContainer) type, typeMap);

‎src/main/java/graphql/validation/rules/PossibleFragmentSpreads.java‎

Lines changed: 1 addition & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -12,7 +12,6 @@
1212
import graphql.schema.GraphQLOutputType;
1313
import graphql.schema.GraphQLType;
1414
import graphql.schema.GraphQLUnionType;
15-
import graphql.schema.SchemaUtil;
1615
import graphql.validation.AbstractRule;
1716
import graphql.validation.ValidationContext;
1817
import graphql.validation.ValidationError;
@@ -74,7 +73,7 @@ private List<? extends GraphQLType> getPossibleType(GraphQLType type) {
7473
if (type instanceof GraphQLObjectType) {
7574
possibleConditionTypes = Collections.singletonList(type);
7675
} else if (type instanceof GraphQLInterfaceType) {
77-
possibleConditionTypes = new SchemaUtil().findImplementations(getValidationContext().getSchema(), (GraphQLInterfaceType) type);
76+
possibleConditionTypes = getValidationContext().getSchema().getImplementations((GraphQLInterfaceType)type);
7877
} else if (type instanceof GraphQLUnionType) {
7978
possibleConditionTypes = ((GraphQLUnionType) type).getTypes();
8079
} else {

‎src/test/groovy/graphql/schema/SchemaUtilTest.groovy‎

Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -67,6 +67,18 @@ class SchemaUtilTest extends Specification {
6767
then:
6868
types.keySet() == expected.keySet()
6969
}
70+
71+
def "group all types by implemented interface"() {
72+
when:
73+
Map<GraphQLType, List<GraphQLObjectType>> byInterface = new SchemaUtil().groupImplementations(starWarsSchema)
74+
75+
then:
76+
byInterface.size() == 1
77+
byInterface[characterInterface].size() == 2
78+
byInterface == [
79+
(characterInterface): [humanType, droidType]
80+
]
81+
}
7082

7183
def "using reference to input as output results in error"() {
7284
given:

0 commit comments

Comments
 (0)