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

[Cellule]

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:

• GraphQL Cardinal — Shopify's breadth-first execution engine (Ruby)
• Grafast — A planning-based TypeScript executor using breadth-first resolution
• The spec itself permits alternative execution algorithms as long as the perceived result is equivalent

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 Replace ExecuteSelectionSet with ExecuteCollectedFields graphql-spec#1039 (collected fields) and Removed parallel execution requirement for merging fields 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.

[yaacovCR]

We are hopeful in due time to support the entire golden path initiative championed by @benjie :

Some links:

• The GraphQL Golden Path Initiative graphql-wg#1887
• https://github.com/graphql/golden-path-wg
• https://graphql.org/conf/2026/schedule/0466574bdb1df2c888e087738a0248f8/?name=Keynote:%20Creating%20a%20Golden%20Path%20for%20GraphQL%20-%20Benjie%20Gillam,%20Graphile
• https://guild.host/presentations/discussion-with-benjie-cyhe4w

Breadth-first execution as an implementation of batch-by-default resolution/execution would definitely be a step in the golden direction.

Specifically for graphql-js, I have begun exploring how to best arrange for execution pipeline customization. The current Executor /IncrementalExecutor class (like Parser and other internal classes) while technically importable/accessible and allowing for customization, is not covered by semver and I think in any case requires architectural changes to do what I think needs to be done.

The general shape I am leaning towards is to provide methods by which fields are dropped from the current waterfall execution pipeline and merged in to the partial result afterwards synchronously/asynchronously as needed. This should cover BOTH batch execution but potentially also schema sharding/stitching so that support for composite schemas can be native to our own executor pipeline. The merge would include results/errors as well as incremental delivery entitires like new deferred fragments, execution groups, streams, etc.

I am thinking this could be an initial part of a broader rearchitecture which removes execution plumbing from GraphQLSchema so that our schema builder no longer has functional circular dependencies (i.e. depends on execution details, looking at you GraphQLResolveInfo) so that different "modules" of graphql-js are truly independent, and also allow the ExecutableSchema portion to be type-safe.

So, basically, I think this is a great idea, part of an eventual long-term rearchitecturing that would be amazing.

I'm not saying that this feature needs to be wait for that re-architecture! Just laying out here the ultimate vision and broad support for this major change as well as other even more major changes.

We are looking for volunteers!

[gmac]

Shopify article author here, and glad to see the question. This is exactly the conversation we wanted to kick off within the community.

So, some food for thought: we were coming from GraphQL Ruby, which is a notoriously overwrought build of GraphQL. We also had a heavy production stack. So while the basic napkin math should hold, your field-level overhead costs will almost certainly vary by app/language and will grossly change performance returns. For example, Node/graphql-js is a lot faster than anything in Ruby. For basic list scales (tens to hundreds), Cardinal running breadth-first makes us very similar to what GraphQL-JS does out of the box… the Node JIT is just a lot faster than what we have in Ruby, and GraphQL-JS is considerably leaner than what we were running. That said, the breadth-first algorithmic advantages are very real: scaling set sizes up into the thousands, Cardinal can still start to pull ahead of GraphQL-JS despite Ruby’s language disadvantages; it just takes some runway. I think if you put breadth-first processing directly into JavaScript, it’s likely that you’d see similar results, although relative margins would vary.

I’d also call out that it’s worth reflecting on your actual scale needs. At hundreds of reps we’re saving a couple milliseconds per field, which is nice but not a banner achievement. Where this really matters is when you start resolving into the thousands (or tens of thousands!). If that wasn’t within your scale target to begin with, then this probably wasn’t ever going to dramatically change your story.

All that said, we’re really only talking about pure CPU-bound performance above, and that’s an incomplete story on its own in GraphQL. Honestly, the fact that you have to bolt on dataloader to compensate for GraphQL’s default execution model is a total hack that we’ve accepted at face value for over a decade now, and I struggle to answer why. I’ve also never heard anyone say a good thing about what dataloaders/promises do for their code patterns and memory efficiencies. Some of the best practical outcomes we’ve had going breadth-first are from pushing devs into the pit of success by making N+1s truly a factor of negligence (versus a casual mistake), and pruning lazy promises down to one per field selection (versus one per field instance). So I do hope “batched by default” makes it into the golden path as a native function of the engine versus a dataloader preset.

[gmac]

Open-sourced at GraphQL Conf today: https://github.com/gmac/graphql-breadth-js