Discussion: Breadth-first execution as an alternative to depth-first traversal

Open
  • Is something wrong?
#4,627 5 comments 5 reactions 0 assignees View on GitHub

Maintainers usually reply within 1 day

Nobody has claimed this yet.

Assessment

Difficulty
5/5
Estimated time
Over a week
Newbie friendliness
28/100
Issue type
Feature
Clarity
Needs clarification
Activity status
Quiet
Tech stack
graphql, typescript
Domain
api, backend-api-design

Research direction

Start by reading the execution path named in the discussion: executeFields, executeField, completeValue, completeObjectValue, and completeListValue. Compare that behavior with graphql-spec#1039, graphql-spec#985, Cardinal, and Grafast. Done would require a maintainer decision on whether breadth-first execution belongs in graphql-js and a defined implementation scope.

Written by the indexing model from the issue text.

Description

Shopify recently published Shopify's journey to faster breadth-first GraphQL execution, which presents detailed benchmarks comparing depth-first and breadth-first execution strategies for high-cardinality list queries. The article specifically references graphql-js as the spec implementation that established the depth-first pattern.

Their findings are significant: for large list queries (e.g. 250 products × 250 variants), breadth-first execution achieved up to 15× faster execution with 90% less memory in their production Ruby stack. The core insight is that depth-first traversal multiplies per-field overhead (resolver setup, instrumentation, promise allocation) by the number of list items, while breadth-first execution resolves each field once across all objects at a given depth level.

The depth-first pattern in graphql-js

The current execution model in executeFields → executeField → completeValue → completeObjectValue → executeFields is recursive per-object. When completeListValue processes a list, each item independently descends its full subtree before the next item is touched. There is no cross-item field batching at any level — each object gets its own recursive resolution chain.

For a query like:

{
  products(first: 1000) {
    title
    variants(first: 100) {
      price
    }
  }
}

This results in 1,000 calls to the title resolver, 1,000 calls to the variants resolver, and 100,000 calls to the price resolver — each with its own field-level overhead. A breadth-first engine would make 1 + 1 + 1 = 3 resolver invocations (each receiving the full set of objects at that level).

Existing work

This builds on prior discussion in #4024 and the broader ecosystem:

Questions for the community
  1. Has there been consideration of exploring breadth-first execution within graphql-js itself, given its role as the reference implementation?
  2. Would a breadth-first execution mode (opt-in or otherwise) be in scope for this project, or is this better suited to alternative executors like Grafast?
  3. The spec changes in graphql/graphql-spec#1039 (collected fields) and graphql/graphql-spec#985 (relaxed parallel execution) seem to lay groundwork for this. Are there spec-level concerns that would block a breadth-first approach in the reference implementation?

The napkin math from the article and its production results are compelling. Curious to hear the maintainers' perspective on whether this execution model has a place in graphql-js, or if the reference implementation intentionally mirrors the spec's depth-first algorithmic description.

Dominant language
TypeScript
Stars
20.3k
Forks
2.1k
Avg merge
6h 51m
Merged PRs (30d)
117

Getting set up

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

More from graphql/graphql-js

All issues in graphql/graphql-js

Similar issues

More TypeScript issues

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.