LIMIT and OFFSET pagination in PostgreSQL - Time & Space Complexity

Time Complexity: LIMIT and OFFSET pagination

O(n)

Understanding Time Complexity

When using LIMIT and OFFSET to paginate query results, it's important to understand how the time to get results changes as the page number grows.

We want to know how the query's work increases when we ask for later pages.

Scenario Under Consideration

Analyze the time complexity of the following query for pagination.

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

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

Identify Repeating Operations

Look for repeated work done by the database engine.

• Primary operation: Scanning and skipping rows up to the OFFSET value.
• How many times: The database reads through 1000 rows before returning 10 rows.

How Execution Grows With Input

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

Input Size (OFFSET n)	Approx. Operations
10	Reads about 10 rows
100	Reads about 100 rows
1000	Reads about 1000 rows

Pattern observation: The work grows roughly in direct proportion to the OFFSET number.

Final Time Complexity

Time Complexity: O(n)

This means the time to get results grows linearly as the OFFSET number increases.

Common Mistake

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

[OK] Correct: The database still has to scan and skip all rows before the OFFSET, so more OFFSET means more work.

Interview Connect

Understanding how LIMIT and OFFSET affect query time helps you explain performance trade-offs clearly and shows you know how databases handle pagination internally.

Self-Check

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