Cursor-based pagination in GraphQL - Time & Space Complexity

Time Complexity: Cursor-based pagination

O(k)

Understanding Time Complexity

When using cursor-based pagination in GraphQL, we want to know how the time to get results changes as the data grows.

We ask: How does fetching pages with cursors scale with more data?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

query GetItems($first: Int, $after: String) {
  items(first: $first, after: $after) {
    edges {
      node {
        id
        name
      }
      cursor
    }
    pageInfo {
      endCursor
      hasNextPage
    }
  }
}
    

This query fetches a page of items after a given cursor, returning a limited number of results.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Retrieving and returning a fixed number of items (page size) after the cursor.
• How many times: The server scans or accesses items starting from the cursor position, up to the page size.

How Execution Grows With Input

Explain the growth pattern intuitively.

Input Size (n)	Approx. Operations
10	About 10 items fetched
100	About 10 items fetched
1000	About 10 items fetched

Pattern observation: The work grows linearly with the page size, not the total data size.

Final Time Complexity

Time Complexity: O(k)

This means the time depends mainly on the number of items requested per page, not the total number of items in the database.

Common Mistake

[X] Wrong: "Fetching a page with a cursor takes time proportional to the total number of items in the database."

[OK] Correct: Cursor-based pagination fetches only a limited number of items after the cursor, so time depends on page size, not total data size.

Interview Connect

Understanding cursor-based pagination time helps you explain efficient data fetching in real apps, showing you know how to handle large lists smoothly.

Self-Check

"What if the cursor is not indexed and the server must scan from the start each time? How would the time complexity change?"

Practice

1. What is the main purpose of cursor-based pagination in GraphQL?

easy

A. To fetch all data at once without limits

B. To sort data alphabetically

C. To fetch data in small parts using a cursor to mark position

D. To delete data from the database

Solution

1. Step 1: Understand pagination purpose

   Pagination is used to split large data into smaller parts for easier handling.

2. Step 2: Identify cursor role

   Cursor marks the position in the data to fetch the next part without overlap or missing items.

3. Final Answer:

   To fetch data in small parts using a cursor to mark position -> Option C

4. Quick Check:

   Cursor-based pagination = fetch data in parts [OK]

Hint: Cursor marks position to fetch next data chunk [OK]

Common Mistakes:

• Thinking pagination fetches all data at once
• Confusing cursor with sorting
• Assuming pagination deletes data

2. Which of the following is the correct way to request the first 5 items after a cursor in GraphQL?

easy

A. { items(fetch: 5, cursor: "cursor123") { edges { node } } }

B. { items(limit: 5, startAfter: "cursor123") { edges { node } } }

C. { items(take: 5, afterCursor: "cursor123") { edges { node } } }

D. { items(first: 5, after: "cursor123") { edges { node } } }

Solution

1. Step 1: Recall GraphQL cursor pagination syntax

   The standard uses first to limit items and after to specify the cursor.

2. Step 2: Match options with correct syntax

   { items(first: 5, after: "cursor123") { edges { node } } } uses first and after correctly; others use incorrect argument names.

3. Final Answer:

   { items(first: 5, after: "cursor123") { edges { node } } } -> Option D

4. Quick Check:

   Use first and after arguments [OK]

Hint: Use first and after arguments for cursor pagination [OK]

Common Mistakes:

• Using limit instead of first
• Using startAfter or afterCursor which are invalid
• Confusing argument names

3. Given this GraphQL query:
{ users(first: 3, after: "YXJyYXljb25uZWN0aW9uOjE=") { edges { node { id name } } pageInfo { hasNextPage endCursor } } }
What does the endCursor represent in the result?

medium

A. The cursor of the last item in the current page

B. The total number of items in the database

C. The cursor of the first item in the current page

D. The number of pages available

Solution

1. Step 1: Understand pageInfo fields

   endCursor marks the cursor of the last item returned in the current page.

2. Step 2: Differentiate from other fields

   hasNextPage shows if more pages exist; endCursor is not a count or first item cursor.

3. Final Answer:

   The cursor of the last item in the current page -> Option A

4. Quick Check:

   endCursor = last item cursor [OK]

Hint: endCursor points to last item fetched [OK]

Common Mistakes:

• Confusing endCursor with total count
• Thinking endCursor is first item cursor
• Assuming endCursor is page count

4. You wrote this GraphQL query for cursor pagination:
{ posts(first: 10, afterCursor: "abc123") { edges { node { title } } } }
Why does this query fail?

medium

A. The argument should be named after, not afterCursor

B. The first argument must be a string, not a number

C. The edges field is invalid in cursor pagination

D. The cursor value cannot be a string

Solution

1. Step 1: Check argument names for cursor pagination

   The correct argument to specify the cursor is after, not afterCursor.

2. Step 2: Validate other parts

   first accepts a number; edges is valid; cursor values are strings.

3. Final Answer:

   The argument should be named after, not afterCursor -> Option A

4. Quick Check:

   Use 'after' argument name [OK]

Hint: Use 'after' not 'afterCursor' for cursor argument [OK]

Common Mistakes:

• Using incorrect argument names
• Thinking first must be string
• Misunderstanding edges field usage

5. You want to fetch all comments in batches of 4 using cursor-based pagination. The first query is:
{ comments(first: 4) { edges { node { id text } } pageInfo { hasNextPage endCursor } } }
To fetch the next batch, which query should you use?

hard

A. { comments(limit: 4, after: "endCursor_value") { edges { node { id text } } } }

B. { comments(first: 4, after: "endCursor_value") { edges { node { id text } } pageInfo { hasNextPage endCursor } } }

C. { comments(last: 4, after: "endCursor_value") { edges { node { id text } } } }

D. { comments(first: 4, before: "endCursor_value") { edges { node { id text } } } }

Solution

1. Step 1: Understand how to continue pagination

   Use the after argument with the endCursor value from the previous page to fetch the next batch.

2. Step 2: Check argument correctness

   first: 4 limits to 4 items; after moves cursor forward; before or last are for backward pagination.

3. Final Answer:

   { comments(first: 4, after: "endCursor_value") { edges { node { id text } } pageInfo { hasNextPage endCursor } } } -> Option B

4. Quick Check:

   Use first and after with endCursor for next batch [OK]

Hint: Use first and after with endCursor to paginate forward [OK]

Common Mistakes:

• Using before instead of after for next page
• Using last instead of first for forward pagination
• Using limit instead of first argument