Inefficient query planning with interface entities

[CodingContraption]

Describe the bug

It appears that under certain conditions, the query planner creates an inefficient route that results in more requests than necessary.

To Reproduce

Steps to reproduce the behavior:

1. Setup services 5 services:

Graph 1

extend schema 
    @link(url: "https://specs.apollo.dev/federation/v2.3", import: ["@key", "@extends", "@requires"])

type Query {
    item: Item
}

interface Item @key(fields:"id") @extends {
    id: ID
    prop: String
}

type Product implements Item @key(fields:"id") @extends {
    id: ID
    prop: String
}

type Service implements Item @key(fields:"id") @extends {
    id: ID
    prop: String
}

Graph 2

extend schema 
    @link(url: "https://specs.apollo.dev/federation/v2.3", import: ["@key", "@external", "@requires"])

interface Item @key(fields:"id") {
    id: ID
    new: String
}

type Product implements Item @key(fields:"id") {
    id: ID
    new: String
}

type Service implements Item @key(fields:"id") {
    id: ID
    new: String
}

Graph 3

    extend schema 
        @link(url: "https://specs.apollo.dev/federation/v2.3", import: ["@key", "@external", "@interfaceObject"])

    type Item @key(fields:"id") @interfaceObject {
        id: ID
        interfaceObj: String
        offer: Offer
    }

    type Offer @key(fields:"id", resolvable: false) {
        id: ID
    }

Graph 4

    extend schema 
        @link(url: "https://specs.apollo.dev/federation/v2.3", import: ["@key", "@external", "@interfaceObject"])

    type Offer @key(fields:"id") {
        id: ID
        text: String
        retailer: Retailer
    }

    type Retailer @key(fields:"id", resolvable: false) {
        id: ID
    }

Graph 5

    extend schema 
        @link(url: "https://specs.apollo.dev/federation/v2.3", import: ["@key", "@external", "@interfaceObject"])

    type Retailer @key(fields:"id") {
        id: ID
        name: String
    }

2. Submit request:

query ExampleQuery {
  item {
    __typename
    id
    offer {
      text
      retailer {
        name
      }
    }
  }
}

3. Look at the query plan

Expected behavior

I expect the query to resolve the Item from graph-1, and then call graph-3 to fetch the other fields from the entity and continue from there like normal.

The expected behaviour can be achieved with this reproduction path, by changing graph-2's Item definition from

interface Item @key(fields:"id") {

to

interface Item {

While this 'fixes' the issue seemingly, I would expect it to have the same query plan even with the @key directive on the interface.

Query plan:

QueryPlan {
  Sequence {
    Fetch(service: "subgraph-1") {
      {
        item {
          __typename
          id
        }
      }
    },
    Flatten(path: "item") {
      Fetch(service: "subgraph-3") {
        {
          ... on Item {
            __typename
            id
          }
        } =>
        {
          ... on Item {
            offer {
              __typename
              id
            }
          }
        }
      },
    },
    Flatten(path: "item.offer") {
      Fetch(service: "subgraph-4") {
        {
          ... on Offer {
            __typename
            id
          }
        } =>
        {
          ... on Offer {
            text
            retailer {
              __typename
              id
            }
          }
        }
      },
    },
    Flatten(path: "item.offer.retailer") {
      Fetch(service: "subgraph-5") {
        {
          ... on Retailer {
            __typename
            id
          }
        } =>
        {
          ... on Retailer {
            name
          }
        }
      },
    },
  },
}

Output

When executing the query, the query plan will query the item from graph-1, but then make a hop to graph-2 to resolve the item to a concrete type and then back to graph-3 to resolve it back to an interface, before querying the offer from graph-3 using the returned Item interface.

An interesting sidenote is that this issue is only triggered when the request includes at least 2 other subgraphs being requested. If you omit retailer from the request, the query plan works as expected again.

Query plan:

QueryPlan {
  Sequence {
    Fetch(service: "subgraph-1") {
      {
        item {
          __typename
          id
        }
      }
    },
    Parallel {
      Sequence {
        Flatten(path: "item") {
          Fetch(service: "subgraph-2") {
            {
              ... on Item {
                __typename
                id
              }
            } =>
            {
              ... on Item {
                __typename
                ... on Product {
                  __typename
                  id
                }
                ... on Service {
                  __typename
                  id
                }
              }
            }
          },
        },
        Flatten(path: "item") {
          Fetch(service: "subgraph-3") {
            {
              ... on Product {
                __typename
                id
              }
              ... on Service {
                __typename
                id
              }
            } =>
            {
              ... on Item {
                offer {
                  __typename
                  id
                }
              }
            }
          },
        },
      },
      Flatten(path: "item") {
        Fetch(service: "subgraph-3") {
          {
            ... on Item {
              __typename
              id
            }
          } =>
          {
            ... on Item {
              offer {
                __typename
                id
              }
            }
          }
        },
      },
    },
    Flatten(path: "item.offer") {
      Fetch(service: "subgraph-4") {
        {
          ... on Offer {
            __typename
            id
          }
        } =>
        {
          ... on Offer {
            retailer {
              __typename
              id
            }
            text
          }
        }
      },
    },
    Flatten(path: "item.offer.retailer") {
      Fetch(service: "subgraph-5") {
        {
          ... on Retailer {
            __typename
            id
          }
        } =>
        {
          ... on Retailer {
            name
          }
        }
      },
    },
  },
}

Desktop (please complete the following information):

• OS: MacOS
• Version 15.5

Additional context

Router version: 1.60.1, 2.3.0 (reproduced locally with rover dev 0.33.0)