Subgraph definition in GraphQL - Time & Space Complexity

Time Complexity: Subgraph definition

O(n + m)

Understanding Time Complexity

When defining a subgraph in GraphQL, it is important to understand how the size of the data affects the work done.

We want to know how the time to process a subgraph grows as the data grows.

Scenario Under Consideration

Analyze the time complexity of the following subgraph definition.

    type Product @key(fields: "id") {
      id: ID!
      name: String
      reviews: [Review]
    }

    type Review {
      id: ID!
      content: String
      product: Product
    }
    

This defines a subgraph with products and their reviews linked together.

Identify Repeating Operations

Look for repeated data fetching or linking steps.

• Primary operation: Fetching each product and then fetching its list of reviews.
• How many times: For each product, the reviews are fetched, so the operation repeats for every product.

How Execution Grows With Input

As the number of products and reviews grows, the total work grows too.

Input Size (n products)	Approx. Operations
10	Fetch 10 products + their reviews
100	Fetch 100 products + their reviews
1000	Fetch 1000 products + their reviews

Pattern observation: The work grows roughly in proportion to the number of products and their reviews.

Final Time Complexity

Time Complexity: O(n + m)

This means the time grows linearly with the number of products (n) plus the number of reviews (m).

Common Mistake

[X] Wrong: "Fetching a subgraph is always constant time because it's just one query."

[OK] Correct: Even one query can fetch many items, so the time depends on how many products and reviews are included.

Interview Connect

Understanding how subgraph definitions affect data fetching helps you explain performance in real projects.

Self-Check

What if the reviews field was paginated? How would that change the time complexity?

Practice

1. What is the main purpose of defining a subgraph in a GraphQL architecture?

easy

A. To split a large graph into smaller, manageable parts

B. To increase the number of queries sent to the server

C. To combine multiple databases into one

D. To replace the need for a schema in GraphQL

Solution

1. Step 1: Understand the concept of subgraphs

   Subgraphs are used to divide a big graph into smaller parts for clarity and manageability.

2. Step 2: Identify the main purpose

   The main goal is to make data easier to manage and improve collaboration by splitting the graph.

3. Final Answer:

   To split a large graph into smaller, manageable parts -> Option A

4. Quick Check:

   Subgraphs = smaller parts [OK]

Hint: Subgraphs break big graphs into smaller pieces [OK]

Common Mistakes:

• Thinking subgraphs increase query count
• Confusing subgraphs with database merging
• Believing subgraphs replace schemas

2. Which of the following is the correct way to define a unique key for a subgraph entity using the @key directive?

easy

A. type Product @key(fields: id) { id: ID! name: String }

B. type Product @key(id) { id: ID! name: String }

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

D. type Product @key("id") { id: ID! name: String }

Solution

1. Step 1: Recall the syntax of the @key directive

   The @key directive requires the fields argument as a string specifying the unique key fields.

2. Step 2: Match the correct syntax

   type Product @key(fields: "id") { id: ID! name: String } correctly uses @key(fields: "id") with quotes around the field name.

3. Final Answer:

   type Product @key(fields: "id") { id: ID! name: String } -> Option C

4. Quick Check:

   @key(fields: "id") = correct syntax [OK]

Hint: Use quotes around fields in @key directive [OK]

Common Mistakes:

• Omitting quotes around field names
• Using @key without 'fields:' keyword
• Passing field name without string quotes

3. Given this subgraph definition:

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

What will happen if you query for { user { userID name } } in a federated setup?

medium

A. The query returns userID and name for the User entity correctly

B. The query fails because email is missing in the query

C. The query returns only userID but not name

D. The query returns an error due to missing @key directive

Solution

1. Step 1: Understand the @key directive role

   The @key directive marks userID as the unique identifier for User entities in the subgraph.

2. Step 2: Analyze the query fields

   The query requests userID and name, both defined in the User type, so it will succeed.

3. Final Answer:

   The query returns userID and name for the User entity correctly -> Option A

4. Quick Check:

   Query fields in schema = successful fetch [OK]

Hint: Query only requested fields defined in subgraph [OK]

Common Mistakes:

• Assuming all fields must be queried
• Confusing @key with required query fields
• Expecting error if some fields are omitted

4. Consider this subgraph schema:

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

Which of the following fixes the error in this subgraph definition?

Option A:

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

Option B:

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

Option C:

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

Option D:

type Product {
  sku: ID!
  name: String
  price: Float
}

medium

A. Change @key fields to "id" instead of "sku"

B. No change needed; the original schema is correct

C. Remove quotes around sku in @key directive

D. Remove the @key directive entirely

Solution

1. Step 1: Check the original @key syntax

   The original schema uses @key(fields: "sku") correctly with quotes around the field name.

2. Step 2: Verify field existence

   The field sku exists and matches the @key directive, so no error is present.

3. Final Answer:

   No change needed; the original schema is correct -> Option B

4. Quick Check:

   Correct @key syntax and matching field = no error [OK]

Hint: Quotes around fields in @key are required [OK]

Common Mistakes:

• Removing quotes around fields in @key
• Using a field name not present in the type
• Removing @key directive causing federation errors

5. You want to create a subgraph for an Orders service. Each Order has a unique orderID and a list of items. Which is the best way to define the subgraph schema to support federation and ensure uniqueness?

hard

A. type Order @key(fields: "orderID items") { orderID: ID! items: [String] }

B. type Order { orderID: ID! items: [String] }

C. type Order @key(fields: "items") { orderID: ID! items: [String] }

D. type Order @key(fields: "orderID") { orderID: ID! items: [String] }

Solution

1. Step 1: Identify the unique key for the Order entity

   The unique identifier is orderID, so it should be used in the @key directive.

2. Step 2: Check the correct @key usage

   Using @key(fields: "orderID") correctly marks orderID as the unique key for federation.

3. Final Answer:

   type Order @key(fields: "orderID") { orderID: ID! items: [String] } -> Option D

4. Quick Check:

   Unique key = orderID in @key [OK]

Hint: Use unique ID field in @key directive for subgraph entities [OK]

Common Mistakes:

• Omitting @key directive causing federation issues
• Using non-unique fields like items in @key
• Combining multiple fields incorrectly in @key