WHERE with IN list in SQL - Time & Space Complexity

Time Complexity: WHERE with IN list

O(n * m)

Understanding Time Complexity

We want to understand how the time to run a SQL query changes when using a WHERE clause with an IN list.

Specifically, how does the number of values inside the IN list affect the work the database does?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

SELECT *
FROM employees
WHERE department_id IN (10, 20, 30, 40, 50);
    

This query selects all employees who belong to any of the listed departments.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Checking each row's department_id against the IN list values.
• How many times: Once for each row in the employees table.

How Execution Grows With Input

As the number of rows grows, the database checks more rows. Also, as the IN list grows, each check takes longer.

Input Size (rows)	IN List Size	Approx. Operations
10	5	About 50 checks (10 rows x 5 values)
100	5	About 500 checks
1000	5	About 5000 checks

Pattern observation: The total checks grow with both the number of rows and the size of the IN list.

Final Time Complexity

Time Complexity: O(n * m)

This means the work grows with the number of rows (n) times the number of values in the IN list (m).

Common Mistake

[X] Wrong: "The IN list size does not affect performance because it's just a simple check."

[OK] Correct: Each value in the IN list is checked against every row, so a bigger list means more checks and more work.

Interview Connect

Understanding how the IN list size affects query time helps you write efficient queries and explain your reasoning clearly in interviews.

Self-Check

"What if the IN list is replaced by a subquery that returns many values? How would the time complexity change?"

Practice

1. What does the SQL clause WHERE column_name IN (value1, value2, value3) do?

easy

A. It selects rows where column_name matches any value in the list.

B. It updates rows with values in the list.

C. It deletes rows not matching the list.

D. It creates a new table with listed values.

Solution

1. Step 1: Understand the IN clause purpose

   The IN clause checks if a column's value matches any value inside the parentheses list.

2. Step 2: Identify the effect on row selection

   Rows with the column value equal to any listed value are selected; others are ignored.

3. Final Answer:

   It selects rows where column_name matches any value in the list. -> Option A

4. Quick Check:

   WHERE with IN filters rows by listed values [OK]

Hint: IN checks if value matches any in the list [OK]

Common Mistakes:

• Thinking IN updates or deletes rows
• Confusing IN with creating tables
• Assuming IN matches all values at once

2. Which of the following is the correct syntax to select rows where status is either 'active', 'pending', or 'closed'?

easy

A. SELECT * FROM orders WHERE status = IN ('active', 'pending', 'closed');

B. SELECT * FROM orders WHERE status IN ('active', 'pending', 'closed');

C. SELECT * FROM orders WHERE status IN 'active', 'pending', 'closed';

D. SELECT * FROM orders WHERE status IN ('active' 'pending' 'closed');

Solution

1. Step 1: Check correct use of IN syntax

   The correct syntax is column_name IN (value1, value2, ...) without an equals sign.

2. Step 2: Identify correct punctuation and parentheses

   Values must be inside parentheses and separated by commas.

3. Final Answer:

   SELECT * FROM orders WHERE status IN ('active', 'pending', 'closed'); -> Option B

4. Quick Check:

   IN syntax = column IN (values) [OK]

Hint: No '=' before IN; use commas inside parentheses [OK]

Common Mistakes:

• Using '=' before IN
• Missing commas between values
• Omitting parentheses around values

3. Given the table employees with column department, what rows will this query return?

SELECT * FROM employees WHERE department IN ('HR', 'Sales');

medium

A. Rows where department is 'HR' or 'Sales'.

B. Rows where department is 'HR' only.

C. Rows where department is not 'HR' or 'Sales'.

D. All rows regardless of department.

Solution

1. Step 1: Understand the IN filter on department

   The query filters rows where department matches any value in ('HR', 'Sales').

2. Step 2: Determine which rows match

   Only rows with department 'HR' or 'Sales' are returned; others are excluded.

3. Final Answer:

   Rows where department is 'HR' or 'Sales'. -> Option A

4. Quick Check:

   IN filters rows matching listed values [OK]

Hint: IN returns rows matching any listed value [OK]

Common Mistakes:

• Thinking it returns rows not in the list
• Assuming it returns only one value
• Confusing IN with NOT IN

4. Identify the error in this SQL query:

SELECT * FROM products WHERE category IN 'Electronics', 'Toys', 'Books';

medium

A. Incorrect table name.

B. Using IN instead of = operator.

C. Missing parentheses around the list of values.

D. Missing commas between values.

Solution

1. Step 1: Check syntax of IN clause

   The list of values after IN must be enclosed in parentheses.

2. Step 2: Identify missing parentheses

   The query has values listed without parentheses, causing syntax error.

3. Final Answer:

   Missing parentheses around the list of values. -> Option C

4. Quick Check:

   IN requires parentheses around values [OK]

Hint: Always put parentheses around IN value list [OK]

Common Mistakes:

• Omitting parentheses around values
• Using IN with equals sign
• Forgetting commas between values

5. You want to select customers from the orders table whose country is either 'USA', 'Canada', or 'Mexico', but exclude those with status 'cancelled'. Which query correctly uses WHERE with IN and excludes cancelled orders?

hard

A. SELECT * FROM orders WHERE country IN 'USA', 'Canada', 'Mexico' AND status != 'cancelled';

B. SELECT * FROM orders WHERE country IN ('USA', 'Canada', 'Mexico') OR status != 'cancelled';

C. SELECT * FROM orders WHERE country = IN ('USA', 'Canada', 'Mexico') AND status != 'cancelled';

D. SELECT * FROM orders WHERE country IN ('USA', 'Canada', 'Mexico') AND status != 'cancelled';

Solution

1. Step 1: Use IN correctly for country filter

   The country column must be checked with IN ('USA', 'Canada', 'Mexico') without equals sign.

2. Step 2: Exclude cancelled orders with AND condition

   Use AND status != 'cancelled' to exclude those rows.

3. Final Answer:

   SELECT * FROM orders WHERE country IN ('USA', 'Canada', 'Mexico') AND status != 'cancelled'; -> Option D

4. Quick Check:

   IN filters list, AND excludes cancelled [OK]

Hint: Use AND to combine IN filter and exclusion [OK]

Common Mistakes:

• Using OR instead of AND causing wrong results
• Adding '=' before IN
• Omitting parentheses around IN values