reuseFragments in QueryPlannerConfig not working as expected

[AneethAnand]

Problem statement

• The issue is exactly what has been explained here : Gateway(experimental): compress downstream requests via generated fragments apollo-server#3791

• For large queries (esp. ones that leverage many nested fragments), queries to subgraph services blows up astronomically because the gateway's query plan expands the query request. Above all since we enable APQ for the downstream request, we are repeatedly creating SHA for this expanded query string

• Following is the Query Plan, which uses some of the fragments (not all) from the query but still number of lines 20523 for 2000 lines of query

Existing Solution

QueryPlannerConfig.reuseQueryFragments or experimental_autoFragmentization did not help.

Code

  if (fragments && reuseQueryFragments) {
    // For all subgraph fetches we query `__typename` on every abstract types (see `FetchGroup.toPlanNode`) so if we want
    // to have a chance to reuse fragments, we should make sure those fragments also query `__typename` for every abstract type.
    fragments = addTypenameFieldForAbstractTypesInNamedFragments(fragments)
  } else {
    fragments = undefined;
  }

"addTypenameFieldForAbstractTypesInNamedFragments" -- adds typename not to the fragment but on the selection set.

Possible Solution

After I read through the code, I added "__typename" field to all fragments and then I saw reduction in the downstream query
From 20K to 1K

I would like to know your thoughts on how adding __typename reduces the subgraph request query?
Can it be automated in the queryPlan and then later prune those fields out from the result?
If you can give me few pointers I would also be happy to contribute back

[AneethAnand]

@trevor-scheer / @pcmanus
I have created a PR (#2463)
regarding the "Gateway was expanding all query fragments"

The issue I found is that query fragment as seen in the code below is used only if the selection set match exactly.

        if (optimizedSelection.equals(candidate.selectionSet)) {
          const fragmentSelection = new FragmentSpreadSelection(fieldBaseType, fragments, candidate.name);
          return new FieldSelection(this.field, selectionSetOf(fieldBaseType, fragmentSelection));
        }

However, there are scenarios where the query fragments a portion of the type and utilizes it in multiple places. Therefore, I have made some modifications to the aforementioned code.

      const schema = options?.schema;
      if(options?.autoFragmetize && schema && optimizedSelection.selections().length > 1) {
        const hash = createHash('sha256').update(optimizedSelection.toString()).digest('hex');
        const newFragment = new NamedFragmentDefinition(schema, fieldBaseType + hash, fieldBaseType, optimizedSelection);
        fragments.addIfNotExist(newFragment);
        const newFragmentSelection = new FragmentSpreadSelection(fieldBaseType, fragments, newFragment.name);
        return new FieldSelection(this.field, selectionSetOf(fieldBaseType, newFragmentSelection));
      }

My proposal is to automatically create a fragment for a selection set that did not exactly match any of the request defined fragments. I am also adding an option to QueryPlannerConfig.experimental_autoFragmentQuery to enable it.

export type QueryPlannerConfig = {
  /**
   * If enabled, the `FetchNode.operationDocumentNode` field in query plan will be populated with the AST
   * of the underlying operation (_on top_ of the "serialized" string `FetchNode.operation` which is always
   * present). This can used by specific gateway user code that needs read-only access to such AST in
   * order to save having to parse `FetchNode.operation`. Without this option, `FetchNode.operationDocumentNode`
   * will always be `undefined`.
   *
   * Enabling this option will make query plans use more memory and you should consider increasing the
   * query plan cache size (though `GatewayConfig.experimental_approximateQueryPlanStoreMiB`) if you enable it.
   *
   * Defaults to false (at least since 2.2; it temporarily defaulted to true before 2.2).
   */
  exposeDocumentNodeInFetchNode?: boolean;

  /**
   * Whether the query planner should try to reused the named fragments of the planned query in subgraph fetches.
   *
   * This is often a good idea as it can prevent very large subgraph queries in some cases (named fragments can
   * make some relatively small queries (using said fragments) expand to a very large query if all the spreads
   * are inline). However, due to architecture of the query planner, this optimization is done as an additional
   * pass on the subgraph queries of the generated plan and can thus increase the latency of building a plan.
   * As long as query plans are sufficiently cached, this should not be a problem, which is why this option is
   * enabled by default, but if the distribution of inbound queries prevents efficient caching of query plans,
   * this may become an undesirable trade-off and cand be disabled in that case.
   *
   * Defaults to true.
   */
  reuseQueryFragments?: boolean,

  **/**
   * Whether the query planner should try to automatically fragment queries that
   * are expanded during query to minimize the query size sent to subgraphs.
   */
  experimental_autoFragmentQuery?: boolean,**

  // Side-note: implemented as an object instead of single boolean because we expect to add more to this soon
  // enough. In particular, once defer-passthrough to subgraphs is implemented, the idea would be to add a
  // new `passthroughSubgraphs` option that is the list of subgraph to which we can pass-through some @defer
  // (and it would be empty by default). Similarly, once we support @stream, grouping the options here will
  // make sense too.
  incrementalDelivery?: {
    /**
     * Enables @defer support by the query planner.
     *
     * If set, then the query plan for queries having some @defer will contains some `DeferNode` (see `QueryPlan.ts`).
     *
     * Defaults to false (meaning that the @defer are ignored).
     */
    enableDefer?: boolean,
  }
}

[AneethAnand]

@trevor-scheer / @pcmanus
By merging the PR, we can achieve several improvements:

1. The subgraph query has become more concise. (20K subgraph query request becomes 1K)
2. The subgraph latency has improved by 1000ms for large queries.
3. Additionally, the improvement in query concision has led to better gateway infrastructure latency since we are using APQ (Automatic Persisted Queries), which means we don't have to hash the large 20k lines of query repeatedly.

[pcmanus]

I generally agree that we can and should improve our handling of fragments. In particular, there is cases where we ought to be able to reuse existing fragments but we don't and it's been on my todo list to better identify why and see if we can improve it.

That said, there is always going to be limitations on re-using the fragments of the original query, since only fragments whose full selection goes the same subgraph can ever be reused this way. So I agree we do need an additional strategy to automatic generate fragments to optimise repetitive subgraph queries.

Looking quickly at the PR, the strategy appears to check for re-used full sub-selections for each composite field/inline fragments. I'll admit that in a perfect world I'd love to be able to come up with a more fine-grained strategy, something that can handle sub-selections that only partly match, but it's certainly more involved, so starting experimenting with your strategy make sense. It clearly seem to help a lot in your case, though I'm curious to see how common such improvements is with this strategy, and it also looks like the strategy may be quite costly in term of query planning time so I'd like to try to better quantify the tradeoffs. That said, as the PR adds this as an opt-in and experimental feature, those questions don't necessarily have to block getting this in.

Long story short, I'll try to have a closer look at reviewing the PR soon (new week hopefully).

[AneethAnand]

@pcmanus I comprehended that dealing with sub-selections that partially match the selection set can be advantageous. However, this approach did not yield complete optimization as certain query fragments were already expanded before calling the optimization process, resulting in a lack of accuracy for some input fragments.

In the most recent update, I have incorporated code to address sub-selections and automatically fragmentize them if the feature is enabled. The modifications I made to the tests in operation.test.ts will demonstrate the advantages

} else if(options?.autoFragmetize && optimizedSelection && optimizedSelection.contains(candidate.selectionSet)) {
          // As mentioned in the above comment, we find any fragments that match some of the members of the optimizedSelection
          // If yes, repace part of the optimizedSelection with the existing fragment
          const fragmentedSelection = new FragmentSpreadSelection(fieldBaseType, fragments, candidate.name);
          // Get the remainder unmatched slections
          const selectionSetNotFragmented = optimizedSelection.minus(candidate.selectionSet);
          // Create a selection set that includes partly matched fragment and unmatched selections
          const modifiedSelection = new SelectionSet(fieldBaseType, fragments);
          modifiedSelection.add(fragmentedSelection);
          if(!selectionSetNotFragmented.isEmpty()) {
            for(const selection of selectionSetNotFragmented.selections()) {
              modifiedSelection.add(selection);
            }
          }
}

Please let me know your thoughts
In the latest commit. I have added code to handle sub-selection and auto fragmetize if its enabled.

[AneethAnand]

I generally agree that we can and should improve our handling of fragments. In particular, there is cases where we ought to be able to reuse existing fragments but we don't and it's been on my todo list to better identify why and see if we can improve it.

That said, there is always going to be limitations on re-using the fragments of the original query, since only fragments whose full selection goes the same subgraph can ever be reused this way. So I agree we do need an additional strategy to automatic generate fragments to optimise repetitive subgraph queries.

Looking quickly at the PR, the strategy appears to check for re-used full sub-selections for each composite field/inline fragments. I'll admit that in a perfect world I'd love to be able to come up with a more fine-grained strategy, something that can handle sub-selections that only partly match, but it's certainly more involved, so starting experimenting with your strategy make sense. It clearly seem to help a lot in your case, though I'm curious to see how common such improvements is with this strategy, and it also looks like the strategy may be quite costly in term of query planning time so I'd like to try to better quantify the tradeoffs. That said, as the PR adds this as an opt-in and experimental feature, those questions don't necessarily have to block getting this in.

Long story short, I'll try to have a closer look at reviewing the PR soon (new week hopefully).

were you able review the code, any suggestions ?

[pcmanus]

@AneethAnand: very sorry I wasn't able to get to this earlier. I did just now leave some comment, though one thing that happened since my last comment is #2497: the code for reusing existing fragments is a lot more capable now, and this may help the initial issue that this issue was created for (meaning: yes, reuseFragments was not working reliably, but it should).

That said, as mentioned previously, there is still room for creating new fragments when none can genuinely be reused, so I'm still ok with your PR as an experiment. But the code from #2497 conflicts quite a bit with said PR so it will need a rebase, and some of the things in the current PR are no longer necessary (because #2497 handles them). As I mentioned in the PR, I'm happy to help with the rebase if necessary.

[AneethAnand]

@pcmanus I will incorporate your comments and reply. Thanks!

[AneethAnand]

@pcmanus I really need your help rebasing my changes with yours.

I am not sure what the following function does. As you know I am trying to auto fragment, if we dont find a matching fragment. Not sure how do I differentiate between if the current selection set has a matching fragment or not.

const optimized = this.tryOptimizeSubselectionWithFragments({
        parentType: fieldBaseType,
        subSelection: optimizedSelection,
        fragments,
        // We can never apply a fragments that has directives on it at the field level (but when those are expanded,
        // their type condition would always be preserved due to said applied directives, so they will always
        // be handled by `InlineFragmentSelection.optimize` anyway).
        fragmentFilter: (f) => f.appliedDirectives.length === 0,
      });

Can you please help with the rebase?

[AneethAnand]

@pcmanus With all your latest changes for "reUse" fragments , we still see query being expanded, though it has improved to some extent.

For example like I mentioned above 1000 lines of incoming query is now 7K lines in the Query Plan
Query:

QueryPlan:

Now that I am not sure how can I apply auto fragment and make it efficient like I did before with your new changes. I believe you have moved from dfs to bfs based approach not sure when can I apply auto fragment.

Can you please help me here with some suggestions?