fix(composition): Use a priority queue instead of a stack for satisfiability

[sachindshinde]

This PR updates satisfiability logic to use a (heap-based) priority queue instead of a stack to store validation state, where a state is higher priority if it has less possible subgraph paths. This is because supergraphs with high connectivity can lead to states with many possible subgraph paths for a supergraph path, and repeatedly processing such states can cause an explosion in possible subgraph paths in the worst case. To avoid this explosion, we prioritize supergraph paths with fewer possible subgraph paths, and this helps us reach more types using smaller states in practice. Loop detection then prevents us from having to consider the larger states to begin with.

[changeset-bot[bot]]

🦋 Changeset detected

Latest commit: 252cc9ccc9b10e2b9abe00ca305e82f9cfb30607

The changes in this PR will be included in the next version bump.

This PR includes changesets to release 7 packages

Name	Type
@apollo/composition	Patch
@apollo/gateway	Patch
@apollo/federation-internals	Patch
@apollo/query-planner	Patch
@apollo/query-graphs	Patch
@apollo/subgraph	Patch
apollo-federation-integration-testsuite	Patch

Not sure what this means? Click here to learn what changesets are.

Click here if you're a maintainer who wants to add another changeset to this PR

[svc-apollo-docs]

⚠️ Docs preview not attached to branch

The preview was not built because the PR's base branch version-2.10 is not in the list of sources.

An Apollo team member can comment one of the following commands to dictate which branch to attach the preview to:

• !docs set-base-branch version-0.x
• !docs set-base-branch main

Build ID: 549ed4f49f804d0d3a73b682

[codesandbox-ci[bot]]

This pull request is automatically built and testable in CodeSandbox.

To see build info of the built libraries, click here or the icon next to each commit SHA.