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.