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?"

Practice

1. What does the LIMIT clause do in a PostgreSQL query?

easy

A. It sorts the rows in ascending order.

B. It controls how many rows the query returns.

C. It skips a number of rows before returning results.

D. It groups rows based on a column.

Solution

1. Step 1: Understand the role of LIMIT

   The LIMIT clause restricts the number of rows returned by a query to a specified count.

2. Step 2: Differentiate from OFFSET

   OFFSET skips rows, but LIMIT controls the count of rows returned after skipping.

3. Final Answer:

   It controls how many rows the query returns. -> Option B

4. Quick Check:

   LIMIT = row count control [OK]

Hint: LIMIT sets max rows returned, OFFSET skips rows first [OK]

Common Mistakes:

• Confusing LIMIT with OFFSET
• Thinking LIMIT sorts rows
• Assuming LIMIT groups rows

2. Which of the following is the correct syntax to get 10 rows starting from the 6th row in PostgreSQL?

easy

A. SELECT * FROM table LIMIT 10 OFFSET 5;

B. SELECT * FROM table LIMIT 5 OFFSET 10;

C. SELECT * FROM table LIMIT 6 OFFSET 10;

D. SELECT * FROM table OFFSET 10 LIMIT 6;

Solution

1. Step 1: Understand OFFSET and LIMIT order

   OFFSET 5 skips first 5 rows, LIMIT 10 returns next 10 rows.

2. Step 2: Check syntax correctness

   PostgreSQL allows LIMIT then OFFSET; LIMIT 10 OFFSET 5 is correct.

3. Final Answer:

   SELECT * FROM table LIMIT 10 OFFSET 5; -> Option A

4. Quick Check:

   LIMIT 10 OFFSET 5 = 10 rows after skipping 5 [OK]

Hint: Use LIMIT first, then OFFSET for correct syntax [OK]

Common Mistakes:

• Swapping LIMIT and OFFSET values
• Using OFFSET larger than total rows
• Incorrect order of LIMIT and OFFSET

3. Given the table employees with 15 rows ordered by id, what rows will this query return?

SELECT * FROM employees ORDER BY id LIMIT 5 OFFSET 10;

medium

A. Rows with id 11 to 15

B. Rows with id 6 to 10

C. Rows with id 1 to 5

D. Rows with id 10 to 14

Solution

1. Step 1: Understand OFFSET 10

   OFFSET 10 skips the first 10 rows (id 1 to 10).

2. Step 2: LIMIT 5 after skipping

   LIMIT 5 returns the next 5 rows, which are id 11 to 15.

3. Final Answer:

   Rows with id 11 to 15 -> Option A

4. Quick Check:

   OFFSET 10 + LIMIT 5 = rows 11-15 [OK]

Hint: OFFSET skips, LIMIT picks next rows [OK]

Common Mistakes:

• Counting OFFSET as inclusive
• Mixing row numbers with id values
• Assuming OFFSET starts at 1

4. Identify the error in this query:

SELECT * FROM products LIMIT OFFSET 5 10;

medium

A. LIMIT and OFFSET order is reversed.

B. OFFSET value must come before LIMIT value.

C. Syntax error: LIMIT must have a number before OFFSET.

D. No error, query is valid.

Solution

1. Step 1: Analyze LIMIT and OFFSET syntax

   LIMIT must be followed by a number, then OFFSET with its number.

2. Step 2: Check given query

   Query has 'LIMIT OFFSET 5 10' which is invalid syntax; LIMIT lacks a number before OFFSET.

3. Final Answer:

   Syntax error: LIMIT must have a number before OFFSET. -> Option C

4. Quick Check:

   LIMIT needs number before OFFSET [OK]

Hint: Always put LIMIT number before OFFSET number [OK]

Common Mistakes:

• Writing OFFSET before LIMIT number
• Omitting numbers after LIMIT or OFFSET
• Assuming order doesn't matter

5. You want to display page 3 of a product list, showing 20 products per page. Which query correctly uses LIMIT and OFFSET?

hard

A. SELECT * FROM products LIMIT 40 OFFSET 20;

B. SELECT * FROM products LIMIT 60 OFFSET 20;

C. SELECT * FROM products LIMIT 20 OFFSET 60;

D. SELECT * FROM products LIMIT 20 OFFSET 40;

Solution

1. Step 1: Calculate OFFSET for page 3

   Page 3 means skipping first 2 pages: 2 * 20 = 40 rows to skip.

2. Step 2: Set LIMIT to page size

   LIMIT is number of rows per page, so LIMIT 20.

3. Step 3: Form the query

   Use LIMIT 20 OFFSET 40 to get page 3 products.

4. Final Answer:

   SELECT * FROM products LIMIT 20 OFFSET 40; -> Option D

5. Quick Check:

   Page 3 offset = 40, limit = 20 [OK]

Hint: OFFSET = (page-1)*page_size, LIMIT = page_size [OK]

Common Mistakes:

• Using OFFSET as page number
• Swapping LIMIT and OFFSET values
• Calculating OFFSET incorrectly