DISTINCT for unique values in SQL - Time & Space Complexity

Time Complexity: DISTINCT for unique values

O(n)

Understanding Time Complexity

We want to understand how the time to find unique values changes as the data grows.

How does the work needed to get distinct results grow when there are more rows?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

SELECT DISTINCT city
FROM customers;

This query finds all unique city names from the customers table.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Scanning each row in the customers table to check the city value.
• How many times: Once for each row in the table.

How Execution Grows With Input

As the number of rows grows, the database must look at more city values to find unique ones.

Input Size (n)	Approx. Operations
10	About 10 checks to find unique cities
100	About 100 checks to find unique cities
1000	About 1000 checks to find unique cities

Pattern observation: The work grows roughly in direct proportion to the number of rows.

Final Time Complexity

Time Complexity: O(n)

This means the time to find unique cities grows linearly as the number of rows increases.

Common Mistake

[X] Wrong: "DISTINCT instantly returns unique values without scanning all rows."

[OK] Correct: The database must look at every row to know if a city is unique or repeated.

Interview Connect

Understanding how DISTINCT works helps you explain query performance clearly and shows you know how data size affects results.

Self-Check

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

Practice

1. What does the SQL keyword DISTINCT do in a query?

easy

A. It sorts the results in ascending order.

B. It returns only unique rows by removing duplicates.

C. It counts the number of rows in a table.

D. It updates duplicate rows with new values.

Solution

1. Step 1: Understand the purpose of DISTINCT

   The DISTINCT keyword is used to filter out duplicate rows in the result set, so only unique rows remain.

2. Step 2: Compare with other options

   Sorting is done by ORDER BY, counting by COUNT(), and updating by UPDATE statement, none of which are related to DISTINCT.

3. Final Answer:

   It returns only unique rows by removing duplicates. -> Option B

4. Quick Check:

   DISTINCT = unique rows [OK]

Hint: DISTINCT removes duplicates, showing only unique rows [OK]

Common Mistakes:

• Confusing DISTINCT with ORDER BY
• Thinking DISTINCT counts rows
• Assuming DISTINCT updates data

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

easy

A. SELECT DISTINCT city FROM Customers;

B. SELECT UNIQUE city FROM Customers;

C. SELECT city UNIQUE FROM Customers;

D. SELECT city FROM Customers DISTINCT;

Solution

1. Step 1: Recall correct DISTINCT syntax

   The correct syntax to get unique values is SELECT DISTINCT column_name FROM table_name.

2. Step 2: Check each option

   SELECT DISTINCT city FROM Customers; matches the correct syntax. The other options use incorrect keyword placement or invalid keywords.

3. Final Answer:

   SELECT DISTINCT city FROM Customers; -> Option A

4. Quick Check:

   Correct syntax uses DISTINCT after SELECT [OK]

Hint: Use SELECT DISTINCT column FROM table for unique values [OK]

Common Mistakes:

• Using UNIQUE instead of DISTINCT
• Placing DISTINCT after FROM
• Writing keywords in wrong order

3. Given the table Orders with a column Product containing values: ['Pen', 'Pen', 'Book', 'Notebook', 'Book'], what will the query SELECT DISTINCT Product FROM Orders; return?

medium

A. Pen, Book, Notebook

B. Pen, Book

C. Pen, Pen, Book, Notebook, Book

D. Notebook

Solution

1. Step 1: Identify duplicates in Product column

   The values are Pen (twice), Book (twice), and Notebook (once).

2. Step 2: Apply DISTINCT to remove duplicates

   DISTINCT returns each unique value once: Pen, Book, Notebook.

3. Final Answer:

   Pen, Book, Notebook -> Option A

4. Quick Check:

   DISTINCT removes duplicates, leaving unique values [OK]

Hint: DISTINCT returns each unique value once [OK]

Common Mistakes:

• Listing duplicates as separate rows
• Missing some unique values
• Confusing DISTINCT with COUNT

4. What is wrong with this query to get unique customer names from Customers table?
SELECT DISTINCT name, age FROM Customers;
Assuming you want unique names only.

medium

A. The query needs GROUP BY instead of DISTINCT.

B. DISTINCT cannot be used with multiple columns.

C. DISTINCT should be replaced with UNIQUE.

D. DISTINCT applies to all selected columns, so duplicates in name may remain if age differs.

Solution

1. Step 1: Understand how DISTINCT works with multiple columns

   DISTINCT treats the combination of all selected columns as one unit, so rows are unique only if all columns differ.

2. Step 2: Analyze the effect on name uniqueness

   If the same name appears with different ages, both rows appear because the combination is unique, not just the name.

3. Final Answer:

   DISTINCT applies to all selected columns, so duplicates in name may remain if age differs. -> Option D

4. Quick Check:

   DISTINCT on multiple columns = unique row combos [OK]

Hint: DISTINCT on multiple columns checks combined uniqueness [OK]

Common Mistakes:

• Thinking DISTINCT applies to each column separately
• Using UNIQUE keyword instead of DISTINCT
• Confusing DISTINCT with GROUP BY

5. You have a table Sales with columns Region and SalesPerson. You want to find all unique salespersons regardless of region. Which query gives the correct result?

hard

A. SELECT SalesPerson FROM Sales GROUP BY Region;

B. SELECT DISTINCT Region, SalesPerson FROM Sales;

C. SELECT DISTINCT SalesPerson FROM Sales;

D. SELECT UNIQUE SalesPerson FROM Sales;

Solution

1. Step 1: Identify the goal

   You want unique salespersons regardless of region, so only SalesPerson column matters.

2. Step 2: Choose query that returns unique SalesPerson values

   SELECT DISTINCT SalesPerson FROM Sales returns unique salespersons. SELECT DISTINCT Region, SalesPerson FROM Sales; returns unique pairs of Region and SalesPerson, which may repeat salespersons. SELECT SalesPerson FROM Sales GROUP BY Region; groups by Region, not SalesPerson, so it won't give unique salespersons. SELECT UNIQUE SalesPerson FROM Sales; uses UNIQUE which is invalid syntax.

3. Final Answer:

   SELECT DISTINCT SalesPerson FROM Sales; -> Option C

4. Quick Check:

   Use DISTINCT on the column you want unique values for [OK]

Hint: DISTINCT only on needed column for unique values [OK]

Common Mistakes:

• Selecting multiple columns with DISTINCT causing duplicates
• Using GROUP BY on wrong column
• Using UNIQUE keyword instead of DISTINCT