Query complexity analysis in GraphQL - Time & Space Complexity

Time Complexity: Query complexity analysis

O(u + u * p + u * p * c)

Understanding Time Complexity

When we run a GraphQL query, the time it takes depends on how much data we ask for and how the query is structured.

We want to understand how the work grows as the query asks for more or deeper data.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

query {
  users {
    id
    name
    posts {
      title
      comments {
        text
      }
    }
  }
}
    

This query fetches a list of users, each user's posts, and each post's comments.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Fetching and processing lists of users, posts per user, and comments per post.
• How many times: For each user, we loop through their posts; for each post, we loop through its comments.

How Execution Grows With Input

Explain the growth pattern intuitively.

Input Size (n)	Approx. Operations
10 users, 5 posts each, 3 comments each	10 + (10*5) + (10*5*3) = 10 + 50 + 150 = 210
100 users, 5 posts each, 3 comments each	100 + (100*5) + (100*5*3) = 100 + 500 + 1500 = 2100
1000 users, 5 posts each, 3 comments each	1000 + (1000*5) + (1000*5*3) = 1000 + 5000 + 15000 = 21000

Pattern observation: The total work grows quickly as the number of users, posts, and comments increase, multiplying together.

Final Time Complexity

Time Complexity: O(u * p * c)

This means the time grows roughly by multiplying the number of users (u), posts per user (p), and comments per post (c).

Common Mistake

[X] Wrong: "The query time only depends on the number of users requested."

[OK] Correct: Because each user has multiple posts and each post has multiple comments, the total work multiplies, not just adds.

Interview Connect

Understanding how nested data affects query time helps you design efficient queries and explain your reasoning clearly in interviews.

Self-Check

"What if we added a new level of nested data, like likes on comments? How would the time complexity change?"

Practice

1. What is the main purpose of query complexity analysis in GraphQL?

easy

A. To measure how resource-heavy a query is before execution

B. To change the data returned by a query

C. To write queries faster

D. To store query results in cache

Solution

1. Step 1: Understand query complexity analysis

   It estimates how much work a query will cause the server to do before running it.

2. Step 2: Identify the main goal

   This helps prevent very heavy queries that slow down or crash the server.

3. Final Answer:

   To measure how resource-heavy a query is before execution -> Option A

4. Quick Check:

   Query complexity = resource estimation [OK]

Hint: Think: Why check query cost before running? To protect server [OK]

Common Mistakes:

• Confusing complexity analysis with caching
• Thinking it changes query results
• Assuming it speeds up query writing

2. Which of the following is a correct way to define a complexity rule in a GraphQL server?

easy

A. Adding a complexity function to field definitions

B. Writing complexity inside the GraphQL query itself

C. Using @complexity directive in the query

D. Setting complexity in the client application

Solution

1. Step 1: Recall where complexity rules are set

   Complexity rules are added in the server schema code, usually as functions on fields.

2. Step 2: Eliminate wrong options

   Complexity is not set inside queries, directives, or client apps.

3. Final Answer:

   Adding a complexity function to field definitions -> Option A

4. Quick Check:

   Complexity rules = server schema code [OK]

Hint: Complexity rules live on server fields, not in queries [OK]

Common Mistakes:

• Trying to add complexity in the query text
• Using non-existent directives for complexity
• Setting complexity on client side

3. Given this GraphQL query and complexity rules:

{ user { posts { comments } } }

If user has complexity 1, posts complexity 5, and comments complexity 2, what is the total complexity?

medium

A. 8

B. 15

C. 7

D. 10

Solution

1. Step 1: Identify field complexities

   user = 1, posts = 5, comments = 2.

2. Step 2: Calculate for nested fields

   Nested field complexities are multiplied: 1 x 5 x 2 = 10.

3. Final Answer:

   10 -> Option D

4. Quick Check:

   Nested fields multiply complexity = 1*5*2=10 [OK]

Hint: Multiply all nested field complexities: 1 x 5 x 2 = 10 [OK]

Common Mistakes:

• Adding all numbers without multiplication
• Ignoring nested field multiplication
• Choosing sum instead of product for nested fields

4. You wrote a complexity function for a field but your server crashes on some queries. What is a likely cause?

medium

A. The query is missing required fields

B. You forgot to add the field to the schema

C. The complexity function returns a non-numeric value

D. The client sent an invalid query syntax

Solution

1. Step 1: Understand complexity function requirements

   Complexity functions must return numbers representing cost.

2. Step 2: Identify crash cause

   If the function returns a string or undefined, the server cannot calculate total complexity and crashes.

3. Final Answer:

   The complexity function returns a non-numeric value -> Option C

4. Quick Check:

   Complexity function must return number [OK]

Hint: Ensure complexity functions return numbers only [OK]

Common Mistakes:

• Returning strings or null from complexity functions
• Ignoring schema registration of fields
• Blaming client query syntax for server crashes

5. You want to limit your GraphQL server to reject queries with complexity over 100. Which approach correctly implements this?

hard

A. Modify client queries to never exceed 100 complexity

B. Add a complexity rule that calculates total cost and rejects queries above 100

C. Use a directive in queries to mark complexity limits

D. Increase server timeout to handle heavy queries

Solution

1. Step 1: Understand server-side complexity limiting

   The server must calculate query complexity and reject queries exceeding the limit.

2. Step 2: Evaluate options

   Only adding a complexity rule on the server can enforce this limit automatically.

3. Final Answer:

   Add a complexity rule that calculates total cost and rejects queries above 100 -> Option B

4. Quick Check:

   Server enforces limits via complexity rules [OK]

Hint: Limit complexity on server, not client or query text [OK]

Common Mistakes:

• Trying to limit complexity from client side
• Using query directives which don't enforce limits
• Increasing timeout instead of limiting complexity