Query planner bug with queries fetching fields nested in multiple unions

[tinnou]

Issue Description

When querying a field that is in a path of 2 or more unions, the query planner is not able to handle different selections and will aggressively collapse selections in fetches yielding an incorrect plan.

Steps to Reproduce

I built a minimum viable example unit test that reproduces building an incorrect plan.

Subgraph searchSubgraph schema:

type Query {
  search: [SearchResult]
}

union SearchResult = MovieResult | ArticleResult
union Section = EntityCollectionSection | GallerySection

type MovieResult @key(fields: "id") {
  id: ID!
  sections: [Section]
}

type ArticleResult @key(fields: "id") {
  id: ID!
  sections: [Section]
}

type EntityCollectionSection @key(fields: "id") {
  id: ID!
}

type GallerySection @key(fields: "id") {
  id: ID!
}

Subgraph artworkSubgraph schema:

type Query {
  me: String
}

type EntityCollectionSection @key(fields: "id") {
  id: ID!
  title: String
  artwork(params: String): String
}

type GallerySection @key(fields: "id") {
  id: ID!
  artwork(params: String): String
}

Executing the following query:

query Search($movieParams: String, $articleParams: String) {
  search {
    __typename
    ... on MovieResult {
      id
      sections {
        ... on EntityCollectionSection {
          id
          artwork(params: $movieParams)
        }
      }
    }
    ... on ArticleResult {
      id
      sections {
        ... on EntityCollectionSection {
          id
          artwork(params: $articleParams)
          title
        }
      }
    }
  }
}

The plan that is currently generated is as follow:

QueryPlan {
  Sequence {
    Fetch(service: "searchSubgraph") {
      {
        search {
          __typename
          ... on MovieResult {
            id
            sections {
              __typename
              ... on EntityCollectionSection {
                __typename
                id
              }
            }
          }
          ... on ArticleResult {
            id
            sections {
              __typename
              ... on EntityCollectionSection {
                __typename
                id
              }
            }
          }
        }
      }
    },
    Flatten(path: "search.@.sections.@") {
      Fetch(service: "artworkSubgraph") {
        {
          ... on EntityCollectionSection {
            __typename
            id
          }
        } =>
        {
          ... on EntityCollectionSection {
            artwork(params: $movieParams)
            title
          }
        }
      },
    },
  },
}

The problem here is the second fetch:

Fetch(service: "artworkSubgraph") {
        {
          ... on EntityCollectionSection {
            __typename
            id
          }
        } =>
        {
          ... on EntityCollectionSection {
            artwork(params: $movieParams)
            title
          }
        }
      },
    },
  },

You can see that the query plan merge the fields from the two selections on EntityCollectionSection from the original query. This is incorrect for two reasons:

1. the artwork field here accept different inputs based on the whether it's on a ArticleResult or a MovieResult
2. the title field is actually only requested in case of ArticleResult

Impact

Since this is a query planner bug I believe this will affect both v1 and v2 gateways.

Potential Fixes

We addressed this issue in our internal planner by having two separate parallel fetches one for each branch. Additionally, we made the flatten path support polymorphic types using a new syntax such that the execution can flatten the results back to the appropriate fragment.

Here is a snippet of the output of our query planner, (the full query plan is available in the unit test), note the | delimiter to hint on the concrete type, search.@|MovieResult:

 Parallel {
            Flatten(path: "search.@|MovieResult.sections.@") {
              Fetch(service: "artworkSubgraph") {
                {
                  ... on EntityCollectionSection {
                    __typename
                    id
                  }
                } =>
                {
                  ... on EntityCollectionSection {
                    artwork(params: $movieParams)
                  }
                }
              }
            }
            Flatten(path: "search.@|ArticleResult.sections.@") {
              Fetch(service: "artworkSubgraph") {
                {
                  ... on EntityCollectionSection {
                    __typename
                    id
                  }
                } =>
                {
                  ... on EntityCollectionSection {
                    title
                    artwork(params: $articleParams)
                  }
                }
              }
            }
          }

Link to Reproduction

https://github.com/apollographql/federation/compare/main...tinnou:union_planner_bug?expand=1

Reproduction Steps

No response

[samuelAndalon]

#2952 (comment)