OFFSET for pagination in SQL - Time & Space Complexity

Time Complexity: OFFSET for pagination

O(n)

Understanding Time Complexity

When using OFFSET for pagination, we want to know how the time to get results changes as the page number grows.

How does skipping rows affect the work the database does?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

SELECT *
FROM products
ORDER BY product_id
LIMIT 10 OFFSET 50;
    

This query fetches 10 products but skips the first 50 rows, simulating page 6 of results.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The database scans or reads rows up to the OFFSET number before returning the next rows.
• How many times: It processes all rows before the OFFSET plus the LIMIT rows to return.

How Execution Grows With Input

As the OFFSET number grows, the database must skip more rows before returning results.

Input Size (OFFSET)	Approx. Operations
10	Reads about 20 rows (10 skipped + 10 returned)
100	Reads about 110 rows (100 skipped + 10 returned)
1000	Reads about 1010 rows (1000 skipped + 10 returned)

Pattern observation: The work grows roughly linearly with the OFFSET value.

Final Time Complexity

Time Complexity: O(n)

This means the time to get results grows in direct proportion to how many rows you skip.

Common Mistake

[X] Wrong: "OFFSET just jumps to the page instantly, so time stays the same no matter the page."

[OK] Correct: The database still reads and skips rows before the OFFSET, so more skipping means more work.

Interview Connect

Understanding how OFFSET affects query time helps you write better pagination queries and explain performance in real projects.

Self-Check

"What if we replaced OFFSET with a WHERE clause filtering by an indexed column? How would the time complexity change?"