Skip to content

Fixed validation, planning and execution time growing quadratically and exponentially #640

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Open
xperiandri wants to merge 5 commits into
base: parser-dos-fixes
Choose a base branch
from
Open

Fixed validation, planning and execution time growing quadratically and exponentially #640

Show file tree
Hide file tree
Changes from 1 commit
Commits
Show all changes
5 commits
Select commit Hold shift + click to select a range
7863e19
Fixed validation and planning time growing quadratically and exponent…
xperiandri Oct 3, 2026
ffc0633
Fixed the remaining exponential and quadratic paths of planning, exec…
xperiandri Oct 10, 2026
fbb5585
Fixed the review findings of planning, execution and validation harde…
xperiandri Oct 10, 2026
2703771
Kept the first filter of a path filtered differently under different …
xperiandri Oct 10, 2026
c64acb4
Matched on `null` instead of calling `isNull` in the selection path
xperiandri Oct 10, 2026
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
Next Next commit
Fixed validation and planning time growing quadratically and exponent… 
…ially

Planning a field under an interface or a union planned its selection set again for every possible type of every abstract field above it, so the work grew exponentially with the nesting: `{ node { child { … } } }` nested 30 deep under an interface with three implementations never finished. Several validation rules were quadratic or exponential in the size of the document as well.

Planning:
- The plan of a field's selection set is reused for the same field, return type and includer
- The includer of a selection is built once for its directives and the includer of its parent, so that covariant implementations reuse the plans under them too
- Fragments are looked up by name, and the fields of a selection set are collected and merged through an index by identifier

Validation:
- The field selection merging rule compares each pair of fields once, as graphql-js does, and stops after the error limit
- The unused variable rule collects the variables of an operation in one iterative pass
- The operation name uniqueness rule counts operations in one pass and ignores fragments
- The fragment spread target rule and the incremental delivery rules look fragments up by name
- The subscription root field rule follows only the fragments that validation inlines
- `SelectionInfoContext.FragmentDefinitions` is replaced by `Fragments`, by name

Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
  • Loading branch information
@xperiandri @claude
xperiandri and claude committed Oct 3, 2026
commit 7863e198ffc890f73b80b2e7bfc6ac4241550701
7 changes: 7 additions & 0 deletions RELEASE_NOTES.md
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -337,3 +337,10 @@
* **Breaking Change** `Parser.parse` and `Parser.tryParse` now reject a document whose braces, brackets and parentheses, outside of strings and comments, are nested deeper than `DocumentLimitsDefaults.MaxNestingDepth` (128), with a syntax error giving the line and column of the first one too deep. Deeper documents used to overflow the stack, which terminated the process
* Fixed parsing time growing exponentially with the nesting of list types in variable definitions: a 100-deep `[[…Int…]]` never finished parsing
* Fixed `Parser.tryParse` throwing `OverflowException`, and so an HTTP server answering with an unhandled exception, for an integer out of the range of 64-bit integers; it is now a syntax error
* **Breaking Change** `SelectionInfoContext.FragmentDefinitions` was replaced by `Fragments`, the fragment definitions that validation inlines, by name
* Fixed query planning time growing exponentially with the nesting of fields under an interface or a union, with the number of its possible types as the base: the selection set of a field is now planned once for each type it can return instead of once for each possible type of every abstract field above it
* Fixed query planning time growing quadratically with the number of fields, fragment spreads and deferred fragments of a selection set
* Fixed the field selection merging rule taking exponential time on nested fields that share a response name. Like graphql-js, it now compares each pair of fields once, and so reports each conflict once, and it stops after `DocumentLimitsDefaults.MaxValidationErrors` errors
* Fixed the unused variable rule searching the document once for every variable
* Fixed validation time growing quadratically with the number of operations and of fragment spreads
* Fixed the operation name uniqueness rule counting a fragment with the same name as an operation
Loading