graphql-go / graphql / 1967

87%

master: 96%

Build Type

Pull #747

circleci

Committed by Patrik Hermansson

Commit Message

plan: plan abstract-field selections lazily to avoid exponential blow-up

PlanQuery eagerly expanded every possible type of every Interface/Union
field at plan time (planMergedFieldChildren looped schema.PossibleTypes
and planned each). Because an expanded type's sub-selection can contain
further abstract fields, this compounds to O(possibleTypes ^ nesting
depth): a deeply-nested polymorphic query on a large schema (~100+
implementers) takes minutes to plan and never returns — even when the
request resolves to an empty result, since planning is data-independent.

This already contradicted the documented design ("abstract returns
lazily plan per-concrete-type at execute time, cached on
abstractAlternatives"). Make it actually lazy: planMergedFieldChildren
leaves abstract alternatives unplanned, and completePlannedAbstractValue
plans (and caches) the concrete type's sub-selection the first time that
type is encountered at runtime, guarded by a mutex since fields resolve
concurrently. Object returns are still planned eagerly (single type, no
fan-out).

Plan time for abstract fields is now proportional to the types a request
actually resolves rather than schema_size ^ depth. Object/leaf planning
and execution results are unchanged.

Adds plan_blowup_test.go: a regression guard (deeply-nested abstract
selection must plan within a deadline), a correctness test, and a
benchmark. Without the fix the guard does ~16^12 units of work and times
out; with it, PlanQuery is ~constant-time (6 allocs/op) regardless of
depth.

Co-Authored-By: Claude Opus 4.8 <noreply@anthropic.com>

Pull Request Pull Request #747: new plan abstract-field selections lazily to avoid exponential blow-up

Coverage Stats

23 of 23 new or added lines in 1 file covered. (100.0%)

1 existing line in 1 file now uncovered.

8492 of 9755 relevant lines covered (87.05%)

1298.61 hits per line