SELECT with PostgreSQL-specific features - Time & Space Complexity

Time Complexity: SELECT with PostgreSQL-specific features

O(n log n)

Understanding Time Complexity

We want to understand how the time to run a SELECT query with PostgreSQL-specific features changes as the data grows.

Specifically, how does the query time grow when using features like window functions or DISTINCT ON?

Scenario Under Consideration

Analyze the time complexity of the following PostgreSQL query.

SELECT DISTINCT ON (category) 
  category, 
  product_name, 
  price, 
  ROW_NUMBER() OVER (PARTITION BY category ORDER BY price DESC) AS rank
FROM products
ORDER BY category, price DESC;

This query selects the most expensive product per category using DISTINCT ON and a window function.

Identify Repeating Operations

Look for repeated actions in the query execution.

• Primary operation: Scanning all rows in the products table.
• How many times: Once for the scan, then sorting and partitioning by category for the window function and DISTINCT ON.

How Execution Grows With Input

As the number of products grows, the query must process more rows and sort them.

Input Size (n)	Approx. Operations
10	About 10 rows scanned and sorted
100	About 100 rows scanned and sorted
1000	About 1000 rows scanned and sorted

Pattern observation: The work grows roughly in proportion to the number of rows because sorting and partitioning happen on all rows.

Final Time Complexity

Time Complexity: O(n log n)

This means the time grows a bit faster than the number of rows because sorting is involved.

Common Mistake

[X] Wrong: "Using DISTINCT ON or window functions makes the query run in constant time regardless of data size."

[OK] Correct: These features still require scanning and sorting the data, so the time grows with the number of rows.

Interview Connect

Understanding how PostgreSQL-specific features affect query time helps you explain your choices clearly and shows you know how databases handle data behind the scenes.

Self-Check

"What if we added an index on the category column? How would that change the time complexity?"

Practice

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

easy

A. It combines rows from two tables.

B. It restricts the number of rows returned by the query.

C. It removes duplicate rows from the result.

D. It sorts the rows in ascending order.

Solution

1. Step 1: Understand the purpose of LIMIT

   The LIMIT clause is used to specify the maximum number of rows to return from a query result.

2. Step 2: Compare with other options

   Sorting is done by ORDER BY, removing duplicates by DISTINCT, and combining tables by JOIN, so these are not correct.

3. Final Answer:

   It restricts the number of rows returned by the query. -> Option B

4. Quick Check:

   LIMIT = restrict rows [OK]

Hint: LIMIT caps rows returned, like a page size [OK]

Common Mistakes:

• Confusing LIMIT with ORDER BY
• Thinking LIMIT removes duplicates
• Mixing LIMIT with JOIN functionality

2. Which of the following is the correct syntax to select distinct city names from a table called customers?

easy

A. SELECT city FROM DISTINCT customers;

B. SELECT city DISTINCT FROM customers;

C. SELECT DISTINCT city FROM customers;

D. SELECT city FROM customers DISTINCT;

Solution

1. Step 1: Recall correct DISTINCT syntax

   In PostgreSQL, DISTINCT comes immediately after SELECT and before the column list.

2. Step 2: Validate each option

   SELECT DISTINCT city FROM customers; correctly places DISTINCT after SELECT. Options A, B, and D misuse DISTINCT placement causing syntax errors.

3. Final Answer:

   SELECT DISTINCT city FROM customers; -> Option C

4. Quick Check:

   SELECT DISTINCT = correct syntax [OK]

Hint: DISTINCT always follows SELECT keyword [OK]

Common Mistakes:

• Placing DISTINCT after column names
• Using DISTINCT after FROM clause
• Misordering keywords causing syntax errors

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

SELECT name FROM products ORDER BY price DESC LIMIT 2;

medium

A. The two products with the lowest prices.

B. An error because LIMIT cannot be used with ORDER BY.

C. All products sorted by price descending.

D. The two products with the highest prices.

Solution

1. Step 1: Understand ORDER BY with DESC

   ORDER BY price DESC sorts products from highest to lowest price.

2. Step 2: Apply LIMIT 2

   LIMIT 2 restricts the output to only the first two rows after sorting, so the two most expensive products.

3. Final Answer:

   The two products with the highest prices. -> Option D

4. Quick Check:

   ORDER BY DESC + LIMIT = top rows [OK]

Hint: ORDER BY DESC + LIMIT picks top items [OK]

Common Mistakes:

• Thinking LIMIT returns lowest prices
• Believing LIMIT causes syntax error with ORDER BY
• Ignoring DESC means descending order

4. Identify the error in this PostgreSQL query:

SELECT DISTINCT name, price FROM products LIMIT;

medium

A. LIMIT requires a number to specify how many rows to return.

B. DISTINCT cannot be used with multiple columns.

C. SELECT must include WHERE clause when using LIMIT.

D. The table name is missing.

Solution

1. Step 1: Check LIMIT usage

   LIMIT must be followed by a number indicating how many rows to return; here it is missing.

2. Step 2: Validate other parts

   DISTINCT can be used with multiple columns, WHERE is optional, and table name is present as products.

3. Final Answer:

   LIMIT requires a number to specify how many rows to return. -> Option A

4. Quick Check:

   LIMIT needs a number [OK]

Hint: Always put a number after LIMIT [OK]

Common Mistakes:

• Omitting number after LIMIT
• Thinking DISTINCT can't use multiple columns
• Assuming WHERE is mandatory with LIMIT

5. You want to get the third and fourth highest salaries from the employees table with column salary. Which query correctly achieves this in PostgreSQL?

hard

A. SELECT salary FROM employees ORDER BY salary DESC LIMIT 2 OFFSET 2;

B. SELECT salary FROM employees ORDER BY salary ASC LIMIT 2 OFFSET 3;

C. SELECT DISTINCT salary FROM employees LIMIT 2 OFFSET 3 ORDER BY salary DESC;

D. SELECT salary FROM employees LIMIT 2 OFFSET 2 ORDER BY salary DESC;

Solution

1. Step 1: Understand OFFSET and LIMIT

   OFFSET 2 skips the first two highest salaries, LIMIT 2 returns the next two rows.

2. Step 2: Check ORDER BY direction

   ORDER BY salary DESC sorts salaries from highest to lowest, so OFFSET 2 skips top two highest.

3. Step 3: Validate options

   SELECT salary FROM employees ORDER BY salary DESC LIMIT 2 OFFSET 2; correctly orders DESC, uses LIMIT 2 and OFFSET 2. SELECT salary FROM employees ORDER BY salary ASC LIMIT 2 OFFSET 3; orders ASC (wrong direction), C misplaces ORDER BY, D places ORDER BY after LIMIT (syntax error).

4. Final Answer:

   SELECT salary FROM employees ORDER BY salary DESC LIMIT 2 OFFSET 2; -> Option A

5. Quick Check:

   OFFSET skips rows, LIMIT picks next [OK]

Hint: Use OFFSET to skip, LIMIT to pick rows [OK]

Common Mistakes:

• Using ASC instead of DESC for highest values
• Placing ORDER BY after LIMIT
• Confusing OFFSET number with row count