Deduplication of deferred fields

[robrichard]

Context

depends on #64

This discussion is taking place with the assumption that we are moving forward with the proposal outlined in #64

Should fields that appear in both a deferred fragment and non-deferred fragment be duplicated?

Example A: Nested objects with overlapping deferred and non-deferred fields

{    
  f2 { a b c { d e f { h i } } }
  ... @defer {
    f2 { a b c { d e f { h j } } }
  }
}

Can we make this equivalent to this?

{  
  f2 { a b c { d e f { h i } } }
  ... @defer {
    f2 { c { f { j } } }
  }
}

Example B: Optimally deduplicating fields could depend on the order which data is resolved

This example shows that optimal deduplication cannot be done statically. If the first defer is resolved first, a.b.e.f can be removed from the second defer. If the second defer is resolved first, it cannot be removed, and the second defer can be removed entirely.

{
  a {
    b {
      c {
        d
      }
      ... @defer {
        e {
          f
        }
        potentiallySlowFieldA
      }
    }
  }
  ... @defer {
    a {
      b {
        e {
          f
        }
      }
    }
    g {
      h
    }
    potentiallySlowFieldB
  }
}

Options being considered

Some options conform to the constraints that are currently in place in this proposal and some recommend adjusting these constraints to better allow deduplication.

The current constraints are:

• Constraint 1: One payload is sent per path
• Constraint 2: Each payload corresponds to the defer directive(s) at the path specified by the payload
• Constraint 3: A payload is only sent once all of the data specified under the deferred fragment(s). Some of that data may be sent in prior payloads.

Additionally the following requirements must also be met

• Requirement 1: Clients must know when all fields that under deferred fragments at a given path are returned. Clients cannot render components associated with a deferred path until all of the fields are available.
• Requirement 2: If fields are deduplicated, resolvers for a given field must be called only once in the execution algorithm. In other words, the server must guarantee that deduplicated data refers to exactly the same object. See comment for explanation: Deduplication of deferred fields #65 (reply in thread)

Options that satisfy these constraints

Option 1 - No Deduplication

• Tradeoff - Fields that are both deferred and non-deferred will be repeated
• Tradeoff - adding deduplication in the future would be a breaking change without introducing a way for clients to opt in to this behavior

Option 2 - Spec algo doesn't deduplicate, deduplication optional

• Algorithm can be refined and added to the spec without breaking changes
• Tradeoff - Results are non deterministic. Different server implementations may give drastically different results.

Option 3: Spec algo deduplicates only from initial payload (and/or parent payloads), further deduplication optional

• Algorithm can be refined and added to the spec without breaking changes
• Tradeoff - Results are non deterministic. Different server implementations may give drastically different results. An approach that deduplicates using static query rewriting will not give the same results as a server that follows the spec algorithm. (Details in comment: Deduplication of deferred fields #65 (comment))
• Tradeoff - This may not be possible to satisfy Requirement 2 in the spec algorithm without adding memory overhead via result caching.

Option 4: Full deduplication

• Tradeoff - This is likely not possible without adding algorithmic complexity or memory overhead to the spec algorithm.

Options that adjust the above constraints:

Option 5: (@IvanGoncharov's proposal: details in comment #65 (comment))

• Constraint 1 is removed, multiple payloads can be sent with the same path
• Full deduplication is achieved by sending payloads with shared data separately
• Requirement 1 is achieved by adding a "completed" boolean to indicate when all data for a given defer path has been sent
• Tradeoff: payloads are sent to the client before they are actionable

Option 6: (@benjie's proposal - details in spec edits graphql/graphql-spec@d0a2f95)

• Constraint 2 is removed, payloads can be sent with paths that do not correspond to a defer directive.
• Constraint 1 is removed. The data for a given defer directive will be sent over multiple payloads
• Partial deduplication is achieved by sending payloads with shared data separately. Results are the same as a server that statically rewrites queries
• Requirement 1 is achieved by sending a "completed" payload to indicate when all data for a given defer path has been sent
• Tradeoff: payloads are sent to the client before they are actionable

[IvanGoncharov]

I think query B should get the following response:

  {
    data: {
      a: {
        b: {
          c: {
            d: "d-data"
          }
        }
    },
    hasNext: true,
  }

  {
    incremental: [
      {
        path: [],
        completed: false,
        data: { 
          a: {
           b: {
            e: {
              f: "f-data"
            }
          }
        }
      }
    ],
    hasNext: true,
  }

  {
    incremental: [
      {
        path: ['a', 'b'],
        completed: true,
        data: {
          potentiallySlowFieldA: "potentiallySlowFieldA-data"
        }
      },
      {
        path: [],
        completed: true,
        data: {
          g: { h: "h-data" },
          potentiallySlowFieldB: "potentiallySlowFieldB-data"
        }
      }
    ],
    "hasNext": false
  }

So basically:

1. top-level @defer always wins, and data ships under its path. Similar to how the initial response always wins.
2. to not block other connected defers, "common parts" can be shipped earlier.
3. we reuse completed, which we plan to use for @stream anyway.

[mjmahone]

One thing that worries me here is getting 3 deferred payloads when there are only 2 deferred paths.

IMO de-duplication of data in deferred responses is less important than guaranteeing the expected number of payloads (I'd rather see more duplicated data in fewer payloads than vice versa).

[yaacovCR]

I'd rather see more duplicated data in fewer payloads than vice versa

Would it be possible for you to make more explicit why fewer payloads would be better?

During the meeting, I suggested that sending partial fragments as they complete might be something "off" by default but that clients could potentially "opt into" via an argument possibly after the initial release.

But then we tried to drill down into why a client would or would not want this behavior. The plus seems to be that the client might receive data faster if the data transfer was not held up by the slower field, while the minus seemed less well defined to me, best I understood was that it might be confusing.

So why exactly would you prefer fewer payloads? Ivan made the point that because we are planning on allowing de duplication, clients will have to be applying payloads as patches, and so basically what this change means is that patch delivery/application can be decoupled from fragment completion. Is that still confusing if we write it clearly in the spec?

Is there another minus?

[yaacovCR]

To answer my own question, depending on how granular the payloads are allowed to be, sending partial fragments could involve significantly more tree traversals of the initial data when applying patches.

Imagine a world in which each field is allowed to be sent individually, for example.

[IvanGoncharov]

@yaacovCR

Imagine a world in which each field is allowed to be sent individually, for example.

One thing to not forget in this discussion is that the server can inline any fields in the initial payload or top-level defer. So the server can choose to optimize corner cases, e.g. fields that resolved sync will be "inlined", which means we discussing only "async" fields.

Moreover, the server is forced to split payloads only to remove deduplication in all other cases, a server can batch as many fields as possible.
Any other splitting is optional and we can experiment with different strategies without changing the spec or client code.

To answer my own question, depending on how granular the payloads are allowed to be, sending partial fragments could involve significantly more tree traversals of the initial data when applying patches.

Let's evaluate the complexity of merging operations for two payloads:

Payload A (duplicated)

{
  incremental: [
    {
      path: ['a', 'b'],
      completed: true,
      data: {
        a: {
         b: {
          e: {
            f: "f-data"
          }
        },
        potentiallySlowFieldA: "potentiallySlowFieldA-data"
      }
    },
    {
      path: [],
      completed: true,
      data: {
        a: {
         b: {
          e: {
            f: "f-data"
          }
        }
        g: {
          h: "h-data"
        },
        potentiallySlowFieldB: "potentiallySlowFieldA-data"
      }
    }
  ]
}

Payload B (de-duplicated)

{
  incremental: [
    {
      path: [],
      completed: false,
      data: { 
        a: {
         b: {
          e: {
            f: "f-data"
          }
        }
      }
    },
    {
      path: ['a', 'b'],
      completed: true,
      data: {
        potentiallySlowFieldA: "potentiallySlowFieldA-data"
      }
    },
    {
      path: [],
      completed: true,
      data: {
        g: {
          h: "h-data"
        },
        potentiallySlowFieldB: "potentiallySlowFieldB-data"
      }
    }
  ]
}

In both cases, "incremental items" are merged into a single response tree.
Let's count the number of searches in maps (main complexity of JSON merging):

1. Every item in path is one search in a map.
   a. 2 + 0 = 2
   b. 0 + 2 + 0 = 2
2. Every key inside data is one search in a map
   a. 5 + 7 = 12
   b. 4 + 1 + 3 = 8

So, as a result, we have 14 vs 10 in favor of deduplicated payload.

Moreover, after we introduce pending (which is planned) and replace path with id implementation can maintain cache with id as key and reference to subtree as a value.
The cost of lookup in this cache is equal to one search in a map which is always faster than traversing the path (except for an empty path).
This caching optimization will widen the gap even more since the cost of splitting one payload into two is always 1 search in a map, and it doesn't matter how long is the path.

[yaacovCR]

We need to evaluate the benefit/cost of deduplication separately than the benefit/cost of sending incomplete fragments. It's the latter that may carry extra tree traversal costs, even when using id, depending on how granular the updates are.

[benjie]

I don't think we need to go for maximal deduplication. The example query B, in my opinion, should stay effectively as-is, the two @defer's being evaluated independently. This slightly more complex query that adds a.b.c { d } to the root-level @defer would work out the same as the Example B query - the "sibling" (different path, but they're both deferred "children" of the original payload) @defers would not be de-duplicated against each other.

 {
   a {
     b {
       c {
         d
       }
       ... @defer {
         e {
           f
         }
         potentiallySlowFieldA
       }
     }
   }
   ... @defer {
     a {
       b {
+        c {
+          d
+        }
         e {
           f
         }
       }
     }
     g {
       h
     }
     potentiallySlowFieldB
   }
 }

[robrichard]

At the Jan 30 2023 defer/stream wg meeting we discussed an option where there is both no deduplication and one incremental payload per path. This can be achieved by merging deferred fields under different deferred paths together to optimize the result. The trade-off with this approach is that a deferred fragments at one path could be blocked by fields in a deferred fragment on a different path. This tradeoff was deemed unacceptable and this option is no longer being considered.

[Keweiqu]

Apologize for being late to the conversation. Wondering if we've considered reliability aspect of dedup. Wondering if we may potentially introduce ambiguous incremental payload that client is unsure how to merge due to partial errors, now that we are trimming the data.

[Keweiqu]

@IvanGoncharov's example from the WG meeting gave me this idea.

Example query

query {
  ... @defer {
    list {
      item {
        id
      }
    }
    ... @defer {
      list {
        item {
          id
          value
        }
      }
    }
  } 
}

Suppose without defers, the response is something like

data {
  list [
    item {id: 1, value: 10},
    item {id: 2, value: 20},
    item {id: 3, value: 30},
    item {id: 4, value: 40},
  ]
}

One situation that would cause ambiguity is this --

// first defer
data {
  list [
    item {id: 2},
    item {id: 3},
    item {id: 4},
  ]
}
// second defer
data {
  list [
    item {value: 10},
    item {value: 20},
    item {value: 30},
    item {value: 40}
  ]
}

In the example, for some reason the first "list" field resolution doesn't have id:1, we can potentially resolve it by checking the errors field. However, we can't guarantee that this will be a hard error surfaced to GraphQL. In practice range queries to the backend usually comes with the partial list without error information on individual items. Thoughts? CC @mjmahone

[yaacovCR]

I see!

It sounds like you would prefer that the following be returned for the query above:

// first defer
data {
  list [
    item {id: 2},
    item {id: 3},
    item {id: 4},
  ]
}
// second defer
data {
  list [
    item {id: 1, value: 10},
    item {id: 2, value: 20},
    item {id: 3, value: 30},
    item {id: 4, value: 40}
  ]
}

But then list.item.1.id is 2 in the first deferred payload and 1 in the second payload, such that merging both of these results is impossible.

The server MUST instead return:

// first defer
data {
  list [
    null,
    item {id: 2},
    item {id: 3},
    item {id: 4},
  ]
}
// second defer
data {
  list [
    item {id: 1, value: 10},
    item {id: 2, value: 20},
    item {id: 3, value: 30},
    item {id: 4, value: 40}
  ]
}

@Keweiqu --- I seem to remember there something being specific about Meta's graphql implementation where nulls are not returned in a list, but are dropped => is that right?

In any case, there is a very similar scenario (perhaps that's in fact what you meant) -- let's say the problem is not that one item in the list sometimes errors, but rather that the list changes, with items dropped. This is indeed problematic, as there is nothing the server can really do to track this.

This is from the RFC for defer/stream, although I can't see a place where language addressing this made it into the spec:

The GraphQL spec does not currently support object identification or consistency. It is currently possible for the same object to be returned in multiple places in a query. If that object changes while the resolvers are running, the query could return inconsistent results. @defer/@stream does not increase the likelihood of this, as the server still attempts to resolve everything as fast as it can. The only difference is some results can be returned to the client sooner. This proposal does not attempt to address this issue.

So as mentioned above, this is a problem, not limited to incremental delivery, but perhaps more common in that case.

And -- at least with respect to list member consistency, one solution could definitely be for clients to always request a key such as an id field for every object. And, as above, deduplication would break that solution.

But the overall problem of data consistency during the lifetime of a GraphQL request still seems less than solved even if we forbid deduplication.

Would love to hear more from you and others about detecting data inconsistency.... seems like a place where "live" operations would certainly come in handy....

[yaacovCR]

I guess any data loader use would solve n+1 and also help with consistency?

[Keweiqu]

I seem to remember there something being specific about Meta's graphql implementation where nulls are not returned in a list, but are dropped => is that right?

This is indeed the case with Meta that we just throw away nulls in the list, and the reason for me coming up with this example. Although as you pointed out this is fundamentally a consistency issue so this has the potential of affecting any typical web servers.

As you referenced, I think dedup would exacerbate the problem of ambiguity in practice, but agree it didn't introduce a new problem.

[robrichard]

@Keweiqu is it correct to say the issue here is that many clients rely on a field like id for global object identification, and removing that field via deduplication could be dangerous if there is the possibility of returning inconsistent results?

Here's another example:

{
  blogPost {
    content
    mostRecentComment {
      id
      content
      author {
        id
        name
      }
    }
    ... defer {
      mostRecentComment {
        id
        author {
          id
          name
          bio
        }
      }
    }
  }
}

If a new comment is placed before the mostRecentComment field is resolved during execution of the deferred fragment, it's not possible for a client to understand the data changed because the id fields were deduplicated.

You might get this result for the above query:

{
  "data": {
    "blogPost": {
      "content": "This is my blog post!",
      "mostRecentComment": {
        "id": "6",
        "content": "This is my comment!",
        "author": {
          "id": "1",
          "name": "Kewei"
        }
      }
    }
  }
}
{
  "incremental": [
    {
      "path": ["blogPost"],
      "data": {
        "mostRecentComment": {
          "author": {
            // bio is not for the author that was returned in the previous payload!
            "bio": "Bio about Rob"
          }
        }
      }
    }
  ]
}

If the id fields were not deduplicated, the client would know the results from the initial payload were stale. When the id fields are deduplicated it's impossible to tell if it's safe to merge with previous payloads.

[robrichard]

In @yaacovCR's implementation only leaf fields were deduplicated. So for example this query:

Example A

query ExampleA {
  hero {
    nestedObject {
      id
    }
    ... @defer {
      nestedObject {
        id
      }
    }
  }
}

would return the following result

[
  {
    "data": { "hero": { "nestedObject": { "id": "1" } } },
    "hasNext": true
  },
  {
    "incremental": [{ "data": { "nestedObject": {} }, "path": ["hero"] }],
    "hasNext": false
  }
]

I've iterated on this to add deduplication of non-leaf fields. Since there is no pre-execution analysis in either graphql-js or the spec algorithms, my approach was to return a unique symbol as fields are resolved indicating to the parent object that they have been deduplicated. If all subfields were deduped, the parent object can also be deduped. My implementation is here: https://github.com/robrichard/graphql-js/compare/mask-parent-base...robrichard:graphql-js:mask-parent?expand=1

With this update, the ExampleA query above would return the following result:

{
  "data": { "hero": { "nestedObject": { "id": "1" } } },
  "hasNext": false
}

But if nestedObject were to return null, the subfields would never be collected by the execution algorithm, meaning we wouldn't have an opportunity to determine if the object can be deduplicated or not. In that case, the result would be:

[
  {
    "data": { "hero": { "nestedObject": null } },
    "hasNext": true
  },
  {
    "incremental": [{ "data": { "nestedObject": null }, "path": ["hero"] }],
    "hasNext": false
  }
]

Another option is we treat nestedObject as a leaf field when null and determine that it can be deduplicated it because it's also outside of the defer. But since the actual leaf fields were never analyzed it would cause objects without completely overlapping fields to be deduplicated.

Example B

query ExampleB {
  hero {
    nestedObject {
      id
    }
    ... @defer {
      nestedObject { 
        name
      }
    }
  }
}

Result:

{
  "data": { "hero": { "nestedObject": null } },
  "hasNext": false
}

In either case, the result is determined by the data returned by the resolver and would not be the same as an algorithm that statically rewrites the query. This same scenario would also exist for list fields that are null or empty.

[yaacovCR]

I have become less and less convinced that deduplication of any fields is "worth it."

graphql states that it "gives clients the power to ask for exactly what they need and nothing more" but that can be read as a reference to no extraneous data, not necessarily deduplication.

Advanced clients can rewrite queries to avoid deduplication, which may be a better solution.

I would even continue for advocate both for no inlining and for no deduplication, empowering incremental delivery without a cache....

[mjmahone]

@yaacovCR I think this point of view makes a lot of sense to me, and fits well with my mental model of what GraphQL the Spec (and graphql-js the reference implementation) tries to achieve. I know people have different views on what the purpose of the spec is, but here's mine.

The way I view GraphQL is as a tree-access-over-graph language: it states what fields must be available to look up, at any point in a tree response. JSON-shaped responses are one way to structure the tree, and they're convenient to use in explanatory text as they're close to WYSIWYG (what-you-see-is-what-you-get). But the JSON shape of the response is not what defines GraphQL. You can have your response include more information, be formatted differently, etc. so long as the accessors for the given (query + fragments) shape provide the same behavior as what you'd get for the reference implementation. It's just in the reference implementation, the accessors are json accessors.

As such, so long as it's the case that when a defer is completed the accessors have access to the same shape of information as the spec requires, then said accessor is compliant. In that view, IMO, it's better for the spec to describe and include all the data in exactly the shape of the deferred fragment, while allowing optimizations in the wire protocol so long as, to the person working with the response their idioms are identical to what they'd have in the spec.

This is also why I'm excited about graphql-over-http becoming a strong specification in its own right: it defines one well-defined transport protocol that any server/client pair ought to be able to implement. I would also not be opposed to graphql-over-http specifying de-duplication for defer, or creating an optimized-graphql-over-http specification that can be used with "smart" clients. At Meta we've kind-of gone this route, where we have multiple wire protocols powering the same client hitting the same server, where we can swap the transport and client parse layers out as a cohesive "unit".

[yaacovCR]

Just to clarify one bit of the above, in terms of unidirectional data flow from a server to a client, the pair must agree on:

• (1) a data serialization format, e.g. JSON, protobuf, etc
• (2) a shared concept of the model of the incremental response, i.e. whether
  • (a) the client must retain the entire response data and apply updates (potentially enabling deduplication within the patches against the initial results or even each other) OR
  • (b) the client is free to discard all initial data OR
  • (c) the client must retain some partial data according to some concept of staleness OR
  • (d) ?
• (3) a connection method, i.e. HTTP(S), SSE, WS, etc

It's number (2) that enables to 'optimized' portion of your proposed optimized-graphql-over-http wire protocol.

IMO, it's better for the spec to describe and include all the data in exactly the shape of the deferred fragment, while allowing optimizations in the wire protocol so long as, to the person working with the response their idioms are identical to what they'd have in the spec.

I agree that this makes the spec much cleaner! But seeing that we would want to specify it somewhere, and that (2) is orthogonal to (3), I imagine we would want a central location for the optimized-graphql specification so as to avoid competing optimized-graphql-over-http, optimized-graphql-over-sse, optimized-graphql-over-ws. I think optimized-graphql should have its own home => perhaps even an appendix within the graphql-spec!

Initially, I thought that a model-free main spec would have a downside: i.e. that the response model have to be uniform across an entire operation.

Meaning, let's say that we want to support different incremental models, sometimes retaining data, sometimes not, and we want to vary it on a fragment/field basis via @defer or other directive arguments. One might suggest that if we don't introduce the incremental model into the spec text at all, we would never be able to add directive arguments that alter it.

But on further reflection, I think we should be able to introduce non-specified arguments on specified directives to control this behavior, (with the arguments non-specified within graphql-spec but specified within optimized-graphql. We do run into a potential namespace problem, however, as there may be an eventual argument name clash between the specifications. But that should be rare with coordination between the groups managing graphql-spec and our hypothetical optimized-graphql specification.

Two thoughts, however:
(1) in terms of the graphql-js implementation, it looks like we are trying to make sure that our server engine produces some degree of optimized-graphql initially, as practically speaking, the optimization may be significantly more expensive if we produce unoptimized-graphql and then later optimize it. This seems reasonable! But I for one am ok with releasing defer/stream now as the de-optimized version we have.
(2) in terms of 'real-time' graphql, on the other hand, that potentially requires 2-way communication, the shared data model might be too critical to leave out of the main specification.

[benjie]

Releasing defer/stream without some form of deduplication could be a massive security problem, opening the doors to significant request amplification leading to denial of service. I'm not concerned with smart clients that can already statically rewrite their queries in the ways we've established to reduce the unnecessary data they receive, I'm concerned about naïve or adversarial clients that deliberately amplify the payloads with minimal input to cause issues on the server/network.

Further, the GraphQL spec already deduplicates selection sets via field merging. In my proposal, all I'm saying is that we should extend this existing field merging over the defer/stream boundary such that fields that are both deferred and not-deferred will only show in the non-deferred part of the payload (and similar in nested parent/child defers) - it's an extension of GraphQL's existing behaviour to this new incremental delivery paradigm rather than a radical deduplication of everything possible (which I don't think we should push for).

[robrichard]

@benjie couldn't an adversarial client bypass any deduplication efforts trivially with field aliasing?

[yaacovCR]

I'm not convinced that deduplication is the only/right answer to the concern of request amplification....

I think employing the existing joint tooling by client/server to analyze and limit operation cost as well as client tooling that "rewrites" operations/results might be the more straightforward solution.

Overall, as @robrichard notes, the calculated cost of a deferred fragment could be equivalent to aliasing all of those fields...

This especially does not seem as critical now that we are merging defers.

Basically, I wonder if we are able to actually release v17 with these -- still experimental! -- directives and get them in the hands of actual users, we might be better able to reason about the security concerns and how best they are mitigated....

[benjie]

Those spec edits are out of date now; here's the same queries against my latest proposal: #65 (comment)

[benjie]

Here's a really really early version of my latest proposal - the "no overlapping branches" proposal:

graphql/graphql-spec#1018

There are many more details within the PR, but highlights:

No overlapping branching.
No duplicate delivery of leaves -> solves @Keweiqu's issue (fully reconcilable final object), and also reduces the risk of response amplification that I raised a couple months ago.
No complex WeakMap/similar caching shenanigans.
No issues with nulls (assuming we're treating @defer and @stream as null boundaries) in theory, though I've not fully written out the text around that yet.
No query rewriting.
No look-ahead.
Consistent delivery of fragments.

Example A

{    
  f2 { a b c { d e f { h i } } }
  ... @defer {
    f2 { a b c { d e f { h j } } }
  }
}

Example Result:

[
  {
    "data": {
      "f2": {
        "a": "a",
        "b": "b",
        "c": {
          "d": "d",
          "e": "e",
          "f": { "h": "h", "i": "i" }
        }
      }
    },
    "pending": [{ "path": ["f2", "c", "f"], "id": "0" }],
    "hasNext": true
  },
  {
    "incremental": [
      { "path": ["f2", "c", "f"], "data": { "j": "j" } }
    ],
    "completed": [{ "id": "0" }],
    "hasNext": false
  }
]

Example A2

{    
  f2 { a b c { d e f { h i } } }
  ... @defer {
    MyFragment: __typename
    f2 { a b c { d e f { h j } } }
  }
}

Example Result:

[
  {
    "data": {
      "f2": {
        "a": "a",
        "b": "b",
        "c": {
          "d": "d",
          "e": "e",
          "f": { "h": "h", "i": "i" }
        }
      }
    },
    "pending": [{ "path": [], "id": "0" }],
    "hasNext": true
  },
  {
    "incremental": [
      { "path": [], "data": { "MyFragment": "Query" } }
      { "path": ["f2", "c", "f"], "data": { "j": "j" } }
    ],
    "completed": [{ "id": "0" }],
    "hasNext": false
  }
]

Example B

{
  a {
    b {
      c {
        d
      }
      ... @defer {
        e {
          f
        }
        potentiallySlowFieldA
      }
    }
  }
  ... @defer {
    a {
      b {
        e {
          f
        }
      }
    }
    g {
      h
    }
    potentiallySlowFieldB
  }
}

Example Result:

[
  {
    "data": {
      "a": { "b": { "c": { "d": "d" } } }
    },
    "pending": [
      { "path": [], "id": "0" },
    ],
    "hasNext": true
  },
  {
    "incremental": [
      {
        "path": [],
        "data": {
          "g": { "h": "h" },
          "potentiallySlowFieldB": "potentiallySlowFieldB"
        }
      }
      {
        "path": ["a", "b"],
        "data": {
          "e": { "f": "f" },
          "potentiallySlowFieldA": "potentiallySlowFieldA"
        }
      }
    ],
    "completed": [{ "id": "0" }],
    "hasNext": false
  }
]

Example C

{
  firstObject {
    secondObject {
      ... @defer {
        thirdObject {
          fourthObject {
            fieldA
            fieldB
          }
        }
      }
    }
    ... @defer {
      secondObject {
        thirdObject {
          fourthObject {
            fieldA
          }
          ... @defer {
            fourthObject {
              fieldA
              fieldC
            }
          }
        }
      }
    }
  }
}

Example Result

[
  {
    "data": {
      "firstObject": {
        "secondObject": {}
      }
    },
    "pending": [
      { "path": ["firstObject", "secondObject"], "id": "0" }
    ],
    "hasNext": true
  },
  {
    "incremental": [
      {
        "path": ["firstObject", "secondObject"],
        "data": {
          "thirdObject": {
            "fourthObject": { "fieldA": "fieldA", "fieldB": "fieldB" }
          }
        }
      }
    ],
    "completed": [{ "id": "0" }],
    "pending": [{ "path": ["firstObject", "secondObject", "thirdObject", "fourthObject"], "id": "1" }],
    "hasNext": true
  },
  {
    "incremental": [
      {
        "path": ["firstObject", "secondObject", "thirdObject", "fourthObject"],
        "data": {
          "fieldC": "fieldC"
        }
      }
    ],
    "completed": [{ "id": "1" }],
    "hasNext": false
  }
]

[robrichard]

I opened a spec PR on top of @benjie's proposal that updates it to batch fields by @defer path instead of the entire @defer level:

graphql/graphql-spec#1020

All of the benefits mentioned above are preserved:

No overlapping branching.
No duplicate delivery of leaves
Reduces the risk of response amplification
No complex WeakMap/similar caching shenanigans.
No query rewriting.
No look-ahead.
Consistent delivery of fragments.

Additionally, the path returned in the pending objects will always point to the path of the @defer, and there will always be at most one pending/complete per path. I believe this change allows clients can use this object to determine if a @defer was inlined or not instead of relying entirely on a __typename field.

Here are the same examples as above, updated for my proposed adjustments

Example A

{    
  f2 { a b c { d e f { h i } } }
  ... @defer {
    f2 { a b c { d e f { h j } } }
  }
}

Example Result:

[
  {
    "data": {
      "f2": {
        "a": "a",
        "b": "b",
        "c": {
          "d": "d",
          "e": "e",
          "f": { "h": "h", "i": "i" }
        }
      }
    },
    "pending": [{ "path": [], "id": "0" }],
    "hasNext": true
  },
  {
    "incremental": [
      { "path": ["f2", "c", "f"], "data": { "j": "j" } }
    ],
    "completed": [{ "id": "0" }],
    "hasNext": false
  }
]

Example A2

{    
  f2 { a b c { d e f { h i } } }
  ... @defer {
    MyFragment: __typename
    f2 { a b c { d e f { h j } } }
  }
}

Example Result:

[
  {
    "data": {
      "f2": {
        "a": "a",
        "b": "b",
        "c": {
          "d": "d",
          "e": "e",
          "f": { "h": "h", "i": "i" }
        }
      }
    },
    "pending": [{ "path": [], "id": "0" }],
    "hasNext": true
  },
  {
    "incremental": [
      { "path": [], "data": { "MyFragment": "Query" } }
      { "path": ["f2", "c", "f"], "data": { "j": "j" } }
    ],
    "completed": [{ "id": "0" }],
    "hasNext": false
  }
]

Example B

{
  a {
    b {
      c {
        d
      }
      ... @defer {
        e {
          f
        }
        potentiallySlowFieldA
      }
    }
  }
  ... @defer {
    a {
      b {
        e {
          f
        }
      }
    }
    g {
      h
    }
    potentiallySlowFieldB
  }
}

Example Result when potentiallySlowFieldA completes first:

[
  {
    "data": {
      "a": { "b": { "c": { "d": "d" } } }
    },
    "pending": [
      { "path": [], "id": "0" },
      { "path": ["a", "b"], "id": "1" },
    ],
    "hasNext": true
  },
  {
    "incremental": [
      { "path": ["a", "b"], "data": { "potentiallySlowFieldA": "potentiallySlowFieldA" } },
      // e is returned in a separate incremental data because there is overlap with other defer paths
      { "path": ["a", "b"], "data": { "e": { "f": "f" } } }
    ],
    "completed": [{ "id": "1" }]
    "hasNext": true
  },
  {
    "incremental": [
      { "path": [], "data": { "g": { "h": "h" }, "potentiallySlowFieldB": "potentiallySlowFieldB" } }
    ],
   "completed": [{ "id": "0" }]
    "hasNext": false
  }
]

Example Result when potentiallySlowFieldB completes first:

[
  {
    "data": {
      "a": { "b": { "c": { "d": "d" } } }
    },
    "pending": [
      { "path": [], "id": "0" },
      { "path": ["a", "b"], "id": "1" }
    ],
    "hasNext": true
  },
  {
    "incremental": [
      { "path": [], "data": { "g": { "h": "h" }, "potentiallySlowFieldB": "potentiallySlowFieldB" } },
      // e is returned in a separate incremental data because there is overlap with other defer paths
      { "path": ["a", "b"], "data": { "e": { "f": "f" } } }
    ],
    "completed": [{ "id": "0" }]
    "hasNext": true
  },
  {
    "incremental": [
      { "path": ["a", "b", "potentiallySlowFieldA"], "data": "potentiallySlowFieldA" }
    ],
   "completed": [{ "id": "1" }]
    "hasNext": false
  }
]

Example C

{
  firstObject {
    secondObject {
      ... @defer {
        thirdObject {
          fourthObject {
            fieldA
            fieldB
          }
        }
      }
    }
    ... @defer {
      secondObject {
        thirdObject {
          fourthObject {
            fieldA
          }
          ... @defer {
            fourthObject {
              fieldA
              fieldC
            }
          }
        }
      }
    }
  }
}

Example Result

[
  {
    "data": {
      "firstObject": {
        "secondObject": {}
      }
    },
    "pending": [
      { "path": ["firstObject", "secondObject"], "id": "0" },
      { "path": ["firstObject"], "id": "1" }
    ],
    "hasNext": true
  },
  {
    "incremental": [
      {
        "path": ["firstObject", "secondObject"],
        "data": {
          "thirdObject": { "fourthObject": { "fieldA": "fieldA", "fieldB": "fieldB" } }
        }
      }
    ],
    "completed": [{ "id": "0" }, { "id": "1" }],
    "pending": [{ "path": ["firstObject", "secondObject", "thirdObject", "fourthObject"], "id": "2" }],
    "hasNext": true
  },
  {
    "incremental": [
      {
        "path": ["firstObject", "secondObject", "thirdObject", "fourthObject"],
        "data": { "fieldC": "fieldC" }
      }
    ],
    "completed": [{ "id": "2" }],
    "hasNext": false
  }
]

Example D

query ExampleD {
  me {
    ... @defer {
      list {
        item {
          id
        }
      }
    }
  ...@defer {
    me {
      list {
        item {
          value
        }
      }
    }
  }
}

Example Result

[
  {
    "data": { "me": {} },
    "pending": [
      { "path": [], "id": 0 },
      { "path": ["me"], "id": 1 }
    ],
    "hasNext": true
  },
  {
    "incremental": [
      {
        "path": ["me"],
        "data": { "list": [{ "item": {} }, { "item": {} }, { "item": {} }] }
      },
      // in this case "id" resolves before value
      { "path": ["me", "list", "item", 0], "data": { "id": 1 } },
      { "path": ["me", "list", "item", 1], "data": { "id": 2 } },
      { "path": ["me", "list", "item", 2], "data": { "id": 3 } }
    ],
    "completed": [{ "id": 1 }],
    "hasNext": true
  },
  {
    "incremental": [
      { "path": ["me", "list", "item", 0], "data": { "value": "Foo" } },
      { "path": ["me", "list", "item", 1], "data": { "value": "Bar" } },
      { "path": ["me", "list", "item", 2], "data": { "value": "Baz" } }
    ],
    "completed": [{ "id": 0 }],
    "hasNext": false
  }
]

[glasser]

Is it necessary that each data object only has one key? For example, in the first version of the responses for Example B, would this be allowed for the second chunk?

  {
    "incremental": [
      { "path": ["a", "b"], "data": { "e": { "f": "f"}, "potentiallySlowFieldA": "potentiallySlowFieldA" } }
    ],
    "completed": [{ "id": "1" }]
    "hasNext": true
  },

[robrichard]

My algorithm doesn't combine them. In the case of overlapping fields in separate defers, the objects returned in incremental are the same, but may be returned in different responses depending on when the non-overlapping fields are ready.

[glasser]

In that example, these fields were from the same defer, right?

It seems fine for the algorithm to not produce them, but consumers should be OK receiving them combined and not assume that they are separate as in the example, right?

[robrichard]

In that example e { f } overlaps in both defers.

Combining or not combining them would also have implications on null bubbling.

[robrichard]

This has been addressed by the new response format described in #69

Deferred fields are no longer duplicated in this response format