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

Aperta
  • Qualcosa non va?
#4,627 5 commenti 5 reazioni 0 assegnatari Vedi su GitHub

I maintainer di solito rispondono entro 1 giorno

Nessuno ha ancora preso questa issue.

Valutazione

Difficoltà
5/5
Tempo stimato
Più di una settimana
Idoneità per principianti
28/100
Tipo di issue
Funzionalità
Chiarezza
Da chiarire
Stato di attività
Tranquilla
Stack tecnologico
graphql, typescript
Ambito
api, backend-api-design

Direzione di ricerca

Inizia leggendo il percorso di esecuzione indicato nella discussione: executeFields, executeField, completeValue, completeObjectValue e completeListValue. Confronta questo comportamento con graphql-spec#1039, graphql-spec#985, Cardinal e Grafast. Il lavoro sarebbe completato quando un maintainer avrà deciso se l’esecuzione breadth-first debba rientrare in graphql-js e sarà definito l’ambito dell’implementazione.

Scritto dal modello di indicizzazione a partire dal testo della issue.

Descrizione

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.

Lingua principale
TypeScript
Stelle
20.3k
Fork
2.1k
Merge medio
6h 51m
PR unite (30g)
117

Preparare l'ambiente

Come iniziare

  1. Leggi tutta la issue e poi la guida ai contributi del progetto.
  2. Commenta sulla issue per dire che te ne occupi tu — evita che due persone facciano lo stesso lavoro.
  3. Fai un fork del repository e lavora su un branch.
  4. Apri una pull request che faccia riferimento al numero della issue.

Altre issue di graphql/graphql-js

Tutte le issue di graphql/graphql-js

Issue simili

Altre issue su TypeScript

Ricevi le nuove issue nella tua casella

Un breve riepilogo di issue GitHub adatte ai principianti.