DISTINCT ON for unique per group in PostgreSQL - Time & Space Complexity

Time Complexity: DISTINCT ON for unique per group

O(n log n)

Understanding Time Complexity

We want to understand how the time needed to run a query using DISTINCT ON changes as the data grows.

Specifically, how does finding one unique row per group scale with more rows?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

SELECT DISTINCT ON (category) category, item, price
FROM products
ORDER BY category, price DESC;
    

This query selects the most expensive item for each category from the products table.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Scanning all rows in the products table to group by category.
• How many times: Once over all rows, then sorting them by category and price.

How Execution Grows With Input

As the number of rows grows, the query must look at more data and sort more rows.

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 scanning take more time as data grows.

Final Time Complexity

Time Complexity: O(n log n)

This means the time grows a bit faster than the number of rows because sorting takes extra steps as data grows.

Common Mistake

[X] Wrong: "DISTINCT ON just picks one row per group instantly, so it runs in constant time regardless of data size."

[OK] Correct: The database must first scan and sort the data to find the unique rows per group, so the time depends on how many rows there are.

Interview Connect

Understanding how DISTINCT ON works helps you explain how databases handle grouping and sorting efficiently, a useful skill for real-world data tasks.

Self-Check

What if we added an index on the category and price columns? How would the time complexity change?

Practice

1. What does the DISTINCT ON clause do in PostgreSQL?

easy

A. It returns one unique row per specified group based on the first row in ORDER BY.

B. It removes all duplicate rows from the entire table.

C. It sorts the entire table without removing duplicates.

D. It groups rows and sums numeric columns automatically.

Solution

1. Step 1: Understand DISTINCT ON purpose

   DISTINCT ON returns only one row per group defined by the columns inside the parentheses.

2. Step 2: Role of ORDER BY with DISTINCT ON

   The row returned per group is the first row according to the ORDER BY clause.

3. Final Answer:

   It returns one unique row per specified group based on the first row in ORDER BY. -> Option A

4. Quick Check:

   DISTINCT ON = unique per group [OK]

Hint: DISTINCT ON picks first row per group using ORDER BY [OK]

Common Mistakes:

• Thinking DISTINCT ON removes all duplicates globally
• Ignoring ORDER BY affects which row is chosen
• Confusing DISTINCT ON with GROUP BY

2. Which of the following is the correct syntax to select the latest order per customer using DISTINCT ON?

easy

A. SELECT DISTINCT ON (customer_id) * FROM orders ORDER BY customer_id DESC;

B. SELECT DISTINCT ON customer_id * FROM orders ORDER BY order_date DESC;

C. SELECT DISTINCT ON (customer_id) * FROM orders ORDER BY customer_id, order_date DESC;

D. SELECT DISTINCT ON (order_date) * FROM orders ORDER BY customer_id DESC;

Solution

1. Step 1: Check DISTINCT ON syntax

   The correct syntax requires parentheses around the column(s) for DISTINCT ON, like DISTINCT ON (customer_id).

2. Step 2: Verify ORDER BY matches DISTINCT ON

   ORDER BY must start with the same columns as DISTINCT ON, here customer_id, then order by order_date DESC to get latest order.

3. Final Answer:

   SELECT DISTINCT ON (customer_id) * FROM orders ORDER BY customer_id, order_date DESC; -> Option C

4. Quick Check:

   Correct syntax = SELECT DISTINCT ON (customer_id) * FROM orders ORDER BY customer_id, order_date DESC; [OK]

Hint: Use parentheses with DISTINCT ON and match ORDER BY columns [OK]

Common Mistakes:

• Omitting parentheses around DISTINCT ON columns
• ORDER BY columns not starting with DISTINCT ON columns
• Using wrong columns in DISTINCT ON

3. Given the table sales with columns region, sale_date, and amount, what will this query return?

SELECT DISTINCT ON (region) region, sale_date, amount FROM sales ORDER BY region, sale_date DESC;

medium

A. One row per region with the latest sale_date.

B. One row per region with the earliest sale_date.

C. All rows sorted by region and sale_date descending.

D. An error because ORDER BY does not match DISTINCT ON.

Solution

1. Step 1: Analyze DISTINCT ON and ORDER BY

   DISTINCT ON (region) picks one row per region. ORDER BY region, sale_date DESC orders rows by region and then newest sale_date first.

2. Step 2: Determine which row is chosen per group

   The first row per region after ordering is the one with the latest sale_date, so that row is returned.

3. Final Answer:

   One row per region with the latest sale_date. -> Option A

4. Quick Check:

   Latest per group = One row per region with the latest sale_date. [OK]

Hint: ORDER BY controls which row DISTINCT ON picks per group [OK]

Common Mistakes:

• Assuming earliest date instead of latest
• Thinking all rows are returned
• Believing syntax error due to ORDER BY

4. Identify the error in this query that tries to get the earliest login per user:

SELECT DISTINCT ON (user_id) user_id, login_time FROM logins ORDER BY login_time ASC;

medium

A. login_time cannot be selected with DISTINCT ON.

B. ORDER BY cannot use ASC with DISTINCT ON.

C. DISTINCT ON requires GROUP BY clause.

D. DISTINCT ON columns must match the first columns in ORDER BY.

Solution

1. Step 1: Check DISTINCT ON and ORDER BY columns

   DISTINCT ON (user_id) requires ORDER BY to start with user_id as the first column.

2. Step 2: Identify mismatch in ORDER BY

   ORDER BY only has login_time ASC, missing user_id first, causing error.

3. Final Answer:

   DISTINCT ON columns must match the first columns in ORDER BY. -> Option D

4. Quick Check:

   ORDER BY start matches DISTINCT ON [OK]

Hint: ORDER BY must start with DISTINCT ON columns [OK]

Common Mistakes:

• Ignoring ORDER BY column order
• Adding unnecessary GROUP BY
• Thinking ASC/DESC causes error

5. You have a table messages with columns chat_id, message_id, and sent_at. You want to get the most recent message per chat. Which query correctly achieves this?

hard

A. SELECT DISTINCT ON (message_id) chat_id, message_id, sent_at FROM messages ORDER BY sent_at DESC;

B. SELECT DISTINCT ON (chat_id) chat_id, message_id, sent_at FROM messages ORDER BY chat_id, sent_at DESC;

C. SELECT chat_id, MAX(sent_at) FROM messages GROUP BY chat_id;

D. SELECT chat_id, message_id, sent_at FROM messages WHERE sent_at = MAX(sent_at) GROUP BY chat_id;

Solution

1. Step 1: Understand requirement for most recent message per chat

   We want one row per chat_id with the latest sent_at.

2. Step 2: Check each option

   SELECT DISTINCT ON (chat_id) chat_id, message_id, sent_at FROM messages ORDER BY chat_id, sent_at DESC; uses DISTINCT ON (chat_id) with ORDER BY chat_id, sent_at DESC, which returns the latest message per chat. SELECT DISTINCT ON (message_id) chat_id, message_id, sent_at FROM messages ORDER BY sent_at DESC; uses DISTINCT ON (message_id), which is unique per message, not per chat. SELECT chat_id, MAX(sent_at) FROM messages GROUP BY chat_id; returns only chat_id and max sent_at, missing message_id. SELECT chat_id, message_id, sent_at FROM messages WHERE sent_at = MAX(sent_at) GROUP BY chat_id; has invalid syntax mixing WHERE and GROUP BY incorrectly.

3. Final Answer:

   SELECT DISTINCT ON (chat_id) chat_id, message_id, sent_at FROM messages ORDER BY chat_id, sent_at DESC; -> Option B

4. Quick Check:

   Latest per group with DISTINCT ON = SELECT DISTINCT ON (chat_id) chat_id, message_id, sent_at FROM messages ORDER BY chat_id, sent_at DESC; [OK]

Hint: DISTINCT ON with ORDER BY picks latest per group easily [OK]

Common Mistakes:

• Using DISTINCT ON on wrong column
• Trying GROUP BY without selecting all columns
• Incorrect WHERE with aggregate functions