Why depth-first GraphQL execution plateaus
Shopify’s GraphQL data layer serves deeply nested commerce queries that scale geometrically—for example, fetching 250 products with 250 variants each. When we analyzed request traces, we found an unexpected bottleneck: a large share of request time wasn’t spent on I/O at all. It was spent running field resolvers that assembly the response.
Conventional GraphQL engines traverse the request document depth-first: they resolve a product in a list, descend into all of its child variants, then move on to the next product and repeat. This bias toward depth-based recursion carries hidden costs that amplify with the breadth of the resolved data. We built a new execution engine—GraphQL Cardinal—that runs breadth-first instead, resolving each field once across a set of objects rather than once per object. In our largest list-heavy tests, this delivered roughly 15x faster execution with 90% less memory.
Depth, breadth, and what actually scales
- Depth is the static size of a request document: how many fields are selected and how they nest. This dimension is fixed; even a “very large” document has only a few hundred fields.
- Breadth is the dynamic width of resolved data: how many objects come back across list fields. This dimension is highly variable, ranging into hundreds of thousands of objects.
In a depth-first model, field execution time grows linearly with breadth. Each product’s subtree is processed independently, so the cost of 100 products is simply 100 times the cost of one. Nested list structures like product-with-variants therefore become progressively more expensive as payloads grow—not because of data volume, but because of how many times field resolvers are invoked.
Three hidden costs of depth-first traversal
Linear scale with no amortization
Depth-based traversal gives the engine no opportunity to amortize CPU-bound processing across sibling subtrees. Stack profiles of a query resolving 100 products, each with 100 variants, show distinct “column” patterns—each column is the slice of time spent walking a single product’s subtree. These columns are independent and do not share work; production time scales linearly with all the repetitions.
Field-level overhead repeated per object
Every GraphQL field execution carries a cost beyond the resolver itself: engine internals, authorization, instrumentation. Even trivial work adds up. An empty field-level tracing hook on 1K fields ran about 10% slower in our stack—simply wrapping the field created overhead. These per-field costs are small enough to evade common profiling frames but multiply across every field of every object in a depth-first pass.
Lazy dataloader promises impose memory and CPU pressure
Dataloaders solve N+1 I/O problems by pooling lookups, but each lazy field allocates a promise and registers a callback. In our stack, resolving 1K lazy fields through a graphql-batch workflow with no I/O ran roughly 2.5x slower than equivalent non-lazy fields. The promise allocations create Garbage Collector pressure and force the engine to backtrack into already-processed subtrees when batch loads resolve later.
The breadth-first alternative
What if each field resolver ran once per request document instead of once per object? In that model, a resolver would receive a set of objects and return a mapped set of results. That is the core idea behind Cardinal. It’s similar in spirit to Airbnb’s batched resolvers, but we make breadth batching a native engine function rather than wrapping depth-first traversal in dataloaders against the grain.
The theoretical payoff is straightforward. If every field has even a tiny platform overhead, depth-first pays it depth×breadth times; breadth-first pays it only depth times. A simple model illustrates the scaling difference:
- Five fields (depth) across 1,000 objects (breadth):
- depth-first: 5,000 resolver calls
- breadth-first: 5 resolver calls
Lazy promises behave the same way. Depth-first constructs and resolves 5,000 promises; breadth-first constructs 5. Chaining one .then on each lazily resolved value compounds the gap: 10,000 callbacks versus 10. As reproducibility grows, the breadth-first model removes the largest dimension from being a multiplicative factor on platform overhead.
Cardinal in practice
Cardinal is a standalone execution wrapper built on the static GraphQL primitives we already rely on (schemas, ASTs, and similar). The proof-of-concept algorithm is available as graphql-breadth_exec. Using it, the execution model runs each field once with an aggregated breadth of objects. Resolvers see a collection of items and return a collection of results; fields that share I/O can bind an entire object set to a single promise rather than building one promise per item.
In early experiments feeding flat JSON with 5K fields through both Cardinal and GraphQL Ruby, Cardinal showed roughly 15x faster CPU-bound execution and 90% less memory. Repetition drives the benefit: on a 7-deep object subtree with a single list item, depth-first wins by a small margin—negligible when the work happens once. With two list items, breadth-first pulls ahead, and the lead grows sharply with each additional repetition. A single field backed by dataloader promises shows an even larger gap.
Production tests fetching product-variant payloads of varying sizes confirmed the gains translate end to end: Cardinal saved over four seconds at P50 on our largest test queries. Profiles show Cardinal spends comparable time on I/O and data staging as conventional execution, but field resolution time and associated garbage collection drop dramatically.
Not every request benefits equally from breadth-first execution. Queries with little list repetition see negligible difference. But for the high-cardinality patterns our merchants rely on, moving field execution out of a depth-first recursion—one that multiplied all per-field platform costs by the breadth of the data—turned out to be the single largest lever we could pull.
Inside Cardinal's breadth execution
Cardinal's breadth-first engine follows a three-phase pipeline: build an execution tree, plan bottom-up, then execute top-down. The execution tree is built eagerly from the request's statically-resolvable AST and relies on two primitives: scopes (typed closures holding many fields) and fields (a return type plus zero-to-many child scopes). Abstract positions that can't be resolved statically are omitted and built lazily once the parent field resolves its objects. One intentional constraint: the tree can only be navigated upward, never down.
After tree building, a bottom-up planning pass runs—heavily inspired by Grafast. During this phase each field may inspect its ancestors and register preloads or planning notes that influence parent execution strategies. Cardinal offers this lookbehind pass as an alternative to lookahead, since lookahead can't make informed decisions about unresolved abstracts below it.
Execution then starts with a root object and an empty hash as its result data. Each scope holds a set of objects and their mapped results, both initially empty. Field resolvers run only once per field, receiving the scope's complete set of objects and returning a mapped set of results:
The resolved data is keyed into the scope's results to establish list groupings and create fresh result hashes for each object:
Finally, all resolved objects and their corresponding result hashes are flat-mapped into the next scope as its objects and results. Algorithmically this step can merge with building results so the resolved field data is traversed only once:
Merged sets show where breadth really pays off. Generations end with the next scope holding a flat mapping of all objects and results assembled before it—flat sets are fast to process and amortize setup work across subtrees:
The response tree is assembled as a side effect of execution. Result hashes get keyed in-place and passed down by reference across scopes, shaped during the next generation. Passing flat sets this way is the core advantage: CPU-bound work cycles get shared across list elements.
Error handling and the engine
Breadth execution lacks the subtree concept that depth-based execution uses to track error paths or bubble exceptions. Consequently, breadth generally runs to completion—failed mutation fields are the only exception and always terminate early. Rescued errors are inlined into the response tree, and a depth traversal pass at the end locates and reports error positions. This is less surgical than depth-based handling, but since fewer than 1% of Shopify's API traffic produces non-validation errors, the tradeoff favors optimizing the success path.
The engine itself is enqueue-driven rather than recursive. That design avoids the deep stack traces GraphQL is known for and trims memory usage considerably. Cardinal's main execution loop initially fit on a single line of code.
The migration path
Adopting breadth execution was harder than building it. Shopify's core monolith was built around the traditional "receive and return one" field resolver interface, while breadth requires "receive and return many." Bridging that gap required an incremental strategy.
Shopify started with an interpreter that let the Cardinal engine puppet GraphQL Ruby's runtime sequence for legacy fields. This interpreter wasn't expected to be faster—it still ran legacy field resolvers individually—but it allowed the existing stack to run while legacy resolvers were swapped out incrementally for faster breadth replacements. After passing the entire core test suite, the interpreter showed a slight speed advantage on list-heavy queries by eliminating some GraphQL Ruby redundancies, at the cost of higher memory usage. Collaboration with Claude AI improved the interpreter's memory efficiency by 40%; at rollout, it was slightly lighter and faster at list repetitions, with visible gains on list-heavy queries and no field resolver changes required.
Field-level tracers that instrument performance and schema metrics also scaled linearly under depth execution. In breadth mode they run only once per field selection, making them dramatically cheaper. The adaptation required only minor adjustments—field timings capture a single duration per breadth resolver and average it across resolved objects, which effectively matched how the data was already being reported.
With the Cardinal engine now running Shopify's core stack, the focus has shifted to migrating legacy field resolvers to breadth-first execution. This introduces its own set of challenges: safely translating and rolling out tens of thousands of new field implementations. The tooling built around this effort includes a library of Claude AI skills for accelerating breadth translations, a shadow verifier that checks migrated fields against their legacy counterparts, a benchmark suite for studying query performance, and burndown and migration tracking metrics.
The migration is ongoing. Many field resolver translations are straightforward; the harder cases involve fields sharing a query or relying on nuanced early-return strategies that need careful matching. So far, every regression traced back to a translation mistake—no non-error scenario has shown breadth-based execution to be fundamentally worse.
What's next
Everything achieved so far uses synchronous Ruby-native language features. Shopify sees async patterns and lower-level C language bindings as major unexplored opportunities for the Cardinal engine.
Shopify is publishing this work as an open letter to the GraphQL community. The point of reference is the official spec, which states that conformance requirements expressed as algorithms can be fulfilled "in any way as long as the perceived result is equivalent." Rubyists can experiment with Cardinal's concepts in GraphQL Ruby's new execution module, developed in collaboration with Shopify.
For the graphql-js community—which defines the de facto standard implementation—Shopify offers two benchmarks highlighting breadth-first potential relative to the language resources running it. While cross-language and cross-JIT comparisons are inherently difficult, the results suggest the approach warrants further investigation.
