FETCH FIRST for SQL standard pagination in PostgreSQL - Time & Space Complexity

Time Complexity: FETCH FIRST for SQL standard pagination

O(n log n)

Understanding Time Complexity

When we use FETCH FIRST in SQL, we want to get a limited number of rows from a query.

We ask: How does the time to get these rows grow as the table gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following SQL query using FETCH FIRST.

SELECT *
FROM employees
ORDER BY employee_id
FETCH FIRST 10 ROWS ONLY;
    

This query fetches the first 10 employees sorted by their ID.

Identify Repeating Operations

Look for repeated work inside the query execution.

• Primary operation: Sorting the entire employees table by employee_id.
• How many times: The sorting happens once over all rows before fetching the first 10.

How Execution Grows With Input

As the number of employees grows, sorting takes more time.

Input Size (n)	Approx. Operations
10	About 10 log 10 operations
100	About 100 log 100 operations
1000	About 1000 log 1000 operations

Pattern observation: The work grows a bit faster than the number of rows because sorting takes more effort as data grows.

Final Time Complexity

Time Complexity: O(n log n)

This means the time to get the first 10 rows grows roughly like sorting all rows, which takes more time as the table gets bigger.

Common Mistake

[X] Wrong: "FETCH FIRST 10 means the database only looks at 10 rows, so time stays the same no matter the table size."

[OK] Correct: The database usually sorts all rows first to know which 10 come first, so it processes the whole table before returning results.

Interview Connect

Understanding how FETCH FIRST works helps you explain how databases handle limits and sorting efficiently, a useful skill for real projects and interviews.

Self-Check

What if we added an index on employee_id? How would the time complexity change?