Shared types across subgraphs in GraphQL - Time & Space Complexity

Time Complexity: Shared types across subgraphs

O(n)

Understanding Time Complexity

When using shared types across subgraphs in GraphQL, it's important to understand how the execution time changes as the number of subgraphs and shared types grow.

We want to know how the system handles queries involving these shared types as the input size increases.

Scenario Under Consideration

Analyze the time complexity of this GraphQL schema snippet using shared types across subgraphs.

    type Product @key(fields: "id") {
      id: ID!
      name: String
      price: Float
    }

    extend type Review @key(fields: "id") {
      id: ID! @external
      product: Product @requires(fields: "productId")
    }
    

This snippet shows a shared type Product used in multiple subgraphs, with Review extending it by referencing Product.

Identify Repeating Operations

Look for repeated actions that affect performance.

• Primary operation: Resolving shared type fields across subgraphs during query execution.
• How many times: Once per query involving the shared type, and once per related entity that references it.

How Execution Grows With Input

As the number of entities referencing shared types grows, the operations increase proportionally.

Input Size (n)	Approx. Operations
10	About 10 resolutions of shared type fields
100	About 100 resolutions
1000	About 1000 resolutions

Pattern observation: The number of operations grows linearly with the number of entities referencing the shared type.

Final Time Complexity

Time Complexity: O(n)

This means the time to resolve shared types grows in direct proportion to how many related entities are queried.

Common Mistake

[X] Wrong: "Resolving shared types happens only once, so it doesn't affect performance much."

[OK] Correct: Each entity referencing the shared type triggers its own resolution, so the cost adds up with more entities.

Interview Connect

Understanding how shared types affect query execution helps you design efficient GraphQL schemas and anticipate performance as your data grows.

Self-Check

What if we cached shared type resolutions? How would that change the time complexity?

Practice

1. What is the main purpose of using @key in shared types across GraphQL subgraphs?

easy

A. To mark fields that uniquely identify an entity across subgraphs

B. To define a field as optional in the schema

C. To specify the data type of a field

D. To mark a field as deprecated

Solution

1. Step 1: Understand the role of @key

   The @key directive marks fields that uniquely identify an entity across subgraphs, enabling them to share the same type.

2. Step 2: Differentiate from other directives

   Other directives like @external or @deprecated serve different purposes, not unique identification.

3. Final Answer:

   To mark fields that uniquely identify an entity across subgraphs -> Option A

4. Quick Check:

   @key marks unique identifiers [OK]

Hint: Remember: @key means unique ID for shared types [OK]

Common Mistakes:

• Confusing @key with @external
• Thinking @key marks optional fields
• Assuming @key defines data types

2. Which of the following is the correct way to mark a field as coming from another subgraph in a shared type?

easy

A. Use @key directive on the field

B. Use @provides directive on the field

C. Use @requires directive on the field

D. Use @external directive on the field

Solution

1. Step 1: Identify the directive for external fields

   The @external directive marks fields that are owned by another subgraph but referenced in the current one.

2. Step 2: Differentiate from other directives

   @key marks unique identifiers, @requires and @provides relate to field dependencies, not external ownership.

3. Final Answer:

   Use @external directive on the field -> Option D

4. Quick Check:

   @external marks fields from other subgraphs [OK]

Hint: External fields use @external directive [OK]

Common Mistakes:

• Using @key instead of @external
• Confusing @requires with @external
• Not marking external fields at all

3. Given the following subgraph schema snippet:

type Product @key(fields: "id") {
  id: ID!
  name: String
  price: Float @external
}

Which statement is true about the price field?

medium

A. It is defined and owned by this subgraph

B. It is a unique identifier for Product

C. It is defined in another subgraph and referenced here

D. It is deprecated and should not be used

Solution

1. Step 1: Analyze the @external directive on price

   The @external directive means price is not owned here but comes from another subgraph.

2. Step 2: Understand the role of @key on id

   The id field is the unique identifier, so price is not an ID.

3. Final Answer:

   It is defined in another subgraph and referenced here -> Option C

4. Quick Check:

   @external means field is from another subgraph [OK]

Hint: Fields with @external come from other subgraphs [OK]

Common Mistakes:

• Thinking @external means field is owned here
• Confusing @key with @external
• Assuming @external means deprecated

4. Consider this subgraph type definition:

type User @key(fields: "userId") {
  userId: ID!
  email: String @external
  name: String
}

Which statement is true about the email field?

medium

A. It is defined in another subgraph and referenced here

B. The @key directive must include email field

C. The userId field cannot be used as a key

D. The name field must be marked @external

Solution

1. Step 1: Analyze the @external directive on email

   The @external directive means email is defined in another subgraph and referenced here.

2. Step 2: Differentiate from other fields

   userId is the @key field provided locally, name is owned locally (no directive).

3. Final Answer:

   It is defined in another subgraph and referenced here -> Option A

4. Quick Check:

   @external means field from another subgraph [OK]

Hint: @external means field from another subgraph [OK]

Common Mistakes:

• Thinking @external means owned locally
• Believing @key must include all fields
• Assuming all fields need @external

5. You have two subgraphs sharing a Book type. Subgraph A defines:

type Book @key(fields: "isbn") {
  isbn: ID!
  title: String
}

Subgraph B defines:

extend type Book @key(fields: "isbn") {
  isbn: ID! @external
  author: String
}

Which statement best describes how these shared types work together?

hard

A. Both subgraphs own isbn, causing a conflict

B. Subgraph A owns isbn and title, Subgraph B extends Book using isbn as key and adds author

C. Subgraph B owns isbn and author, Subgraph A only references isbn

D. Subgraph B cannot extend Book without redefining title

Solution

1. Step 1: Identify ownership of fields

   Subgraph A defines Book with isbn and title, so it owns these fields.

2. Step 2: Understand extension in Subgraph B

   Subgraph B extends Book, marking isbn as @external (owned by A) and adds author.

3. Step 3: Confirm no conflicts

   Using @key with the same field isbn allows both subgraphs to share the type without conflict.

4. Final Answer:

   Subgraph A owns isbn and title, Subgraph B extends Book using isbn as key and adds author -> Option B

5. Quick Check:

   Extension uses @external keys to share types [OK]

Hint: Extension uses @external keys to share types [OK]

Common Mistakes:

• Thinking both subgraphs own the same key field
• Believing extension requires redefining all fields
• Assuming conflicts occur with shared keys