Over-fetching and under-fetching problems in GraphQL - Time & Space Complexity

Time Complexity: Over-fetching and under-fetching problems

O(n * m)

Understanding Time Complexity

When using GraphQL, it's important to see how the amount of data requested affects performance.

We want to know how fetching too much or too little data changes the work the server does.

Scenario Under Consideration

Analyze the time complexity of this GraphQL query fetching user data and their posts.

query GetUsersWithPosts($limit: Int) {
  users(limit: $limit) {
    id
    name
    posts {
      id
      title
    }
  }
}
    

This query gets a list of users and for each user, it fetches all their posts.

Identify Repeating Operations

Look for repeated actions in the query.

• Primary operation: Fetching each user and then fetching all posts for that user.
• How many times: For each user (n times), fetch their posts (m times per user).

How Execution Grows With Input

As the number of users and posts grows, the work grows too.

Input Size (users n, posts per user m)	Approx. Operations
10 users, 5 posts each	About 10 * 5 = 50 fetches
100 users, 5 posts each	About 100 * 5 = 500 fetches
100 users, 50 posts each	About 100 * 50 = 5000 fetches

Pattern observation: The total work grows by multiplying users and posts per user.

Final Time Complexity

Time Complexity: O(n * m)

This means the work grows with both the number of users and the number of posts each user has.

Common Mistake

[X] Wrong: "Fetching more fields or nested data doesn't affect performance much."

[OK] Correct: Every extra nested list means more data to fetch and process, which can multiply the work and slow things down.

Interview Connect

Understanding how data fetching scales helps you design better queries and APIs that are fast and efficient.

Self-Check

What if we added a filter to fetch only posts from the last month? How would that change the time complexity?