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?

Practice

1. What does the SQL clause FETCH FIRST 5 ROWS ONLY do in a query?

easy

A. Limits the query result to only the first 5 rows.

B. Skips the first 5 rows and returns the rest.

C. Returns all rows except the first 5.

D. Sorts the rows by the first 5 columns.

Solution

1. Step 1: Understand FETCH FIRST clause

   The clause FETCH FIRST 5 ROWS ONLY limits the number of rows returned by the query to 5.

2. Step 2: Effect on query result

   This means only the first 5 rows from the result set will be returned, no more.

3. Final Answer:

   Limits the query result to only the first 5 rows. -> Option A

4. Quick Check:

   FETCH FIRST limits rows = A [OK]

Hint: FETCH FIRST means limit rows returned, not skip [OK]

Common Mistakes:

• Confusing FETCH FIRST with OFFSET
• Thinking FETCH FIRST sorts rows automatically
• Assuming FETCH FIRST removes rows instead of limiting

2. Which of the following is the correct syntax to get the first 10 rows from a table named employees in PostgreSQL?

easy

A. SELECT * FROM employees FETCH 10 ROWS;

B. SELECT * FROM employees FETCH FIRST 10 ROWS ONLY;

C. SELECT * FROM employees LIMIT FIRST 10;

D. SELECT * FROM employees TOP 10;

Solution

1. Step 1: Recall correct FETCH FIRST syntax

   The standard SQL syntax to limit rows is FETCH FIRST n ROWS ONLY. PostgreSQL supports this.

2. Step 2: Check each option

   SELECT * FROM employees FETCH FIRST 10 ROWS ONLY; uses correct syntax. Options A, B, and D are invalid in PostgreSQL.

3. Final Answer:

   SELECT * FROM employees FETCH FIRST 10 ROWS ONLY; -> Option B

4. Quick Check:

   Correct FETCH FIRST syntax = C [OK]

Hint: Use FETCH FIRST n ROWS ONLY for standard limit [OK]

Common Mistakes:

• Using LIMIT FIRST instead of FETCH FIRST
• Using TOP keyword which is SQL Server syntax
• Omitting ROWS ONLY after FETCH FIRST

3. Given the table products with columns id and price, what will this query return?

SELECT id FROM products ORDER BY price DESC FETCH FIRST 3 ROWS ONLY;

medium

A. All products sorted by price descending.

B. The 3 products with the lowest prices.

C. The 3 products with the highest prices.

D. Syntax error due to FETCH FIRST usage.

Solution

1. Step 1: Analyze ORDER BY clause

   The query orders products by price in descending order, so highest prices come first.

2. Step 2: Apply FETCH FIRST 3 ROWS ONLY

   This limits the output to only the first 3 rows after sorting, i.e., top 3 highest priced products.

3. Final Answer:

   The 3 products with the highest prices. -> Option C

4. Quick Check:

   ORDER BY DESC + FETCH FIRST = top rows [OK]

Hint: ORDER BY DESC + FETCH FIRST = top N highest [OK]

Common Mistakes:

• Ignoring ORDER BY and thinking it returns random rows
• Confusing DESC with ASC order
• Assuming FETCH FIRST causes syntax error

4. Identify the error in this query:

SELECT name FROM customers FETCH FIRST 5 ROWS;

medium

A. Missing ORDER BY clause before FETCH FIRST.

B. No error; query is valid.

C. FETCH FIRST cannot be used without OFFSET.

D. Incorrect FETCH FIRST syntax; missing 'ONLY'.

Solution

1. Step 1: Check FETCH FIRST syntax

   The correct syntax requires ROWS ONLY after the number, so it should be FETCH FIRST 5 ROWS ONLY.

2. Step 2: Verify other parts

   ORDER BY is recommended but not mandatory. OFFSET is not required. So the error is missing 'ONLY'.

3. Final Answer:

   Incorrect FETCH FIRST syntax; missing 'ONLY'. -> Option D

4. Quick Check:

   FETCH FIRST needs ROWS ONLY [OK]

Hint: FETCH FIRST must end with ROWS ONLY [OK]

Common Mistakes:

• Omitting 'ONLY' after FETCH FIRST clause
• Thinking ORDER BY is mandatory with FETCH FIRST
• Confusing FETCH FIRST with OFFSET usage

5. You want to show page 3 of a product list with 10 items per page, sorted by created_at ascending. Which query correctly uses FETCH FIRST and OFFSET for this pagination?

hard

A. SELECT * FROM products ORDER BY created_at ASC OFFSET 20 ROWS FETCH FIRST 10 ROWS ONLY;

B. SELECT * FROM products ORDER BY created_at ASC FETCH FIRST 10 ROWS OFFSET 20 ROWS ONLY;

C. SELECT * FROM products ORDER BY created_at ASC FETCH FIRST 30 ROWS ONLY;

D. SELECT * FROM products ORDER BY created_at ASC OFFSET 10 ROWS FETCH FIRST 10 ROWS ONLY;

Solution

1. Step 1: Calculate OFFSET for page 3

   Each page has 10 items, so page 3 starts at row 21. OFFSET is zero-based, so OFFSET = (3-1)*10 = 20.

2. Step 2: Use FETCH FIRST to limit rows per page

   FETCH FIRST 10 ROWS ONLY limits the result to 10 rows for the page.

3. Step 3: Check query syntax order

   OFFSET must come before FETCH FIRST. SELECT * FROM products ORDER BY created_at ASC OFFSET 20 ROWS FETCH FIRST 10 ROWS ONLY; correctly orders OFFSET then FETCH FIRST.

4. Final Answer:

   SELECT * FROM products ORDER BY created_at ASC OFFSET 20 ROWS FETCH FIRST 10 ROWS ONLY; -> Option A

5. Quick Check:

   OFFSET before FETCH FIRST for pagination [OK]

Hint: OFFSET = (page-1)*size; FETCH FIRST = page size [OK]

Common Mistakes:

• Swapping OFFSET and FETCH FIRST order
• Using FETCH FIRST without OFFSET for pages >1
• Incorrect OFFSET calculation for page number