Depth limiting in GraphQL - Time & Space Complexity

Time Complexity: Depth limiting

O(b^d)

Understanding Time Complexity

When using GraphQL, queries can ask for nested data. Depth limiting controls how deep these nested requests go.

We want to understand how the time to run a query grows as the allowed depth increases.

Scenario Under Consideration

Analyze the time complexity of this GraphQL query with depth limiting.

query GetUserData($id: ID!, $depth: Int!) {
  user(id: $id) {
    name
    friends(depth: $depth) {
      name
      friends(depth: $depth - 1) {
        name
      }
    }
  }
}
    

This query fetches a user, their friends, and friends of friends up to a certain depth.

Identify Repeating Operations

Look for repeated actions in the query execution.

• Primary operation: Fetching friends at each depth level.
• How many times: Once per friend at each depth, repeated down to the depth limit.

How Execution Grows With Input

As depth increases, the number of friend lists fetched grows.

Input Size (depth)	Approx. Operations
1	Fetch user and direct friends only
2	Fetch user, friends, and friends of friends
3	Fetch user plus two levels of friends

Pattern observation: Each increase in depth multiplies the number of friend fetches roughly by the average number of friends.

Final Time Complexity

Time Complexity: O(b^d)

This means the work grows exponentially with depth, where b is average friends per user and d is the depth limit.

Common Mistake

[X] Wrong: "Increasing depth only adds a little more work, so it grows slowly."

[OK] Correct: Each depth level multiplies the number of friend fetches, so work grows much faster than just adding a few more fields.

Interview Connect

Understanding depth limiting helps you explain how nested queries impact performance and why limits are important in real apps.

Self-Check

What if we replaced friends with a field that returns a fixed small list regardless of depth? How would the time complexity change?

Practice

1.

What is the main purpose of depth limiting in GraphQL?

easy

A. To speed up the client-side rendering

B. To increase the depth of queries for more data

C. To limit the number of users accessing the server

D. To stop queries from going too deep and protect the server

Solution

1. Step 1: Understand what depth limiting controls

   Depth limiting restricts how deep a GraphQL query can go into nested fields.

2. Step 2: Identify the purpose of this restriction

   This prevents overly complex queries that can slow down or crash the server.

3. Final Answer:

   To stop queries from going too deep and protect the server -> Option D

4. Quick Check:

   Depth limiting = Protect server from deep queries [OK]

Hint: Depth limiting stops deep queries to keep server safe [OK]

Common Mistakes:

• Thinking depth limiting speeds up client rendering
• Confusing depth limiting with user access control
• Believing depth limiting increases query depth

2.

Which of the following is the correct way to set a maximum query depth of 5 in a GraphQL server using graphql-depth-limit?

const depthLimit = require('graphql-depth-limit');
const server = new ApolloServer({
  schema,
  validationRules: [ /* ??? */ ]
});

easy

A. validationRules: [depthLimit(5)]

B. validationRules: [depthLimit.max(5)]

C. validationRules: [depthLimit.setMaxDepth(5)]

D. validationRules: [depthLimit.limit(5)]

Solution

1. Step 1: Recall the usage of graphql-depth-limit

   The package exports a function called depthLimit that takes the max depth as an argument.

2. Step 2: Match the correct syntax

   The correct way is to pass depthLimit(5) inside validationRules array.

3. Final Answer:

   validationRules: [depthLimit(5)] -> Option A

4. Quick Check:

   depthLimit(5) sets max depth 5 [OK]

Hint: Use depthLimit(number) inside validationRules [OK]

Common Mistakes:

• Using non-existent methods like max or setMaxDepth
• Passing depthLimit without parentheses
• Placing depthLimit outside validationRules array

3.

Given this GraphQL query and a server with depth limit set to 3, what will happen?

{
  user {
    posts {
      comments {
        text
      }
    }
  }
}

medium

A. The query will succeed and return all comments' text

B. The query will return only user and posts without comments

C. The query will fail due to exceeding the depth limit

D. The query will return an empty response

Solution

1. Step 1: Calculate the query depth

   The query goes user (level 1) -> posts (level 2) -> comments (level 3) -> text (level 4). Depth is 4.

2. Step 2: Compare with the depth limit

   The server limits depth to 3, but query depth is 4, so it exceeds the limit.

3. Final Answer:

   The query will fail due to exceeding the depth limit -> Option C

4. Quick Check:

   Query depth 4 > limit 3 = fail [OK]

Hint: Count nested fields; if deeper than limit, query fails [OK]

Common Mistakes:

• Counting leaf fields as separate depth
• Assuming depth limit applies per field, not whole query
• Thinking partial data returns on depth limit exceed

4.

What is wrong with this GraphQL server setup code that tries to limit query depth?

const depthLimit = require('graphql-depth-limit');
const server = new ApolloServer({
  schema,
  validationRules: depthLimit(4)
});

medium

A. validationRules should be an array, not a single function

B. depthLimit should be called without arguments

C. schema must be inside validationRules

D. ApolloServer does not support validationRules

Solution

1. Step 1: Check the expected type of validationRules

   validationRules expects an array of functions, not a single function.

2. Step 2: Identify the mistake in the code

   The code passes depthLimit(4) directly, missing the array brackets.

3. Final Answer:

   validationRules should be an array, not a single function -> Option A

4. Quick Check:

   validationRules = [depthLimit(4)] [OK]

Hint: Wrap depthLimit call inside array for validationRules [OK]

Common Mistakes:

• Passing function directly instead of array
• Calling depthLimit without max depth argument
• Misplacing schema inside validationRules

5.

You want to allow queries up to depth 4 but block deeper ones. You also want to log a warning when a query exceeds the limit. Which approach correctly combines depth limiting with custom logging in a GraphQL server?

const depthLimit = require('graphql-depth-limit');
const { ApolloServer } = require('apollo-server');

const loggingDepthLimit = (maxDepth) => {
  return (context) => {
    const validationRule = depthLimit(maxDepth);
    return (validationContext) => {
      const errors = validationRule(validationContext);
      if (errors && errors.length > 0) {
        console.warn('Query depth exceeded:', errors);
      }
      return errors;
    };
  };
};

const server = new ApolloServer({
  schema,
  validationRules: [loggingDepthLimit(4)]
});

hard

A. depthLimit cannot be wrapped; this will cause runtime errors

B. This code correctly wraps depthLimit to log warnings on depth exceed

C. validationRules must be a single function, not an array

D. Logging should be done outside validationRules, this is incorrect

Solution

1. Step 1: Understand wrapping validation rules

   Validation rules are functions that can be wrapped to add behavior like logging.

2. Step 2: Analyze the custom logging wrapper

   The code creates a function that calls depthLimit and logs warnings if errors occur.

3. Step 3: Confirm usage in ApolloServer

   Passing the wrapped function inside an array to validationRules is correct.

4. Final Answer:

   This code correctly wraps depthLimit to log warnings on depth exceed -> Option B

5. Quick Check:

   Wrap validationRules to add logging = correct [OK]

Hint: Wrap depthLimit in function to add logging, pass in array [OK]

Common Mistakes:

• Assuming validationRules can't be wrapped
• Passing validationRules as single function instead of array
• Trying to log outside validationRules without access to errors