Time Complexity: WHERE with IS NULL and IS NOT NULL
O(n)
0
0
WHERE with IS NULL and IS NOT NULL in SQL - Time & Space Complexity
Understanding Time Complexity
We want to understand how the time to run a query changes when we use conditions that check for NULL values.
Specifically, how does checking for NULL or NOT NULL affect the work the database does?
Scenario Under Consideration
Analyze the time complexity of the following code snippet.
SELECT *
FROM employees
WHERE manager_id IS NULL;
SELECT *
FROM employees
WHERE manager_id IS NOT NULL;
This code finds all employees who either have no manager or do have a manager.
Identify Repeating Operations
Identify the loops, recursion, array traversals that repeat.
- Primary operation: The database scans each row in the employees table to check the manager_id column.
- How many times: Once for every row in the table.
How Execution Grows With Input
As the number of employees grows, the database must check more rows for NULL or NOT NULL.
| Input Size (n) | Approx. Operations |
|---|---|
| 10 | 10 checks |
| 100 | 100 checks |
| 1000 | 1000 checks |
Pattern observation: The number of checks grows directly with the number of rows.
Final Time Complexity
Time Complexity: O(n)
This means the time to run the query grows in a straight line as the table gets bigger.
Common Mistake
[X] Wrong: "Checking for NULL is faster because NULL is special and fewer rows match."
[OK] Correct: The database still looks at every row to decide if the value is NULL or not, so it does the same amount of work.
Interview Connect
Understanding how conditions like IS NULL affect query time helps you explain how databases handle data filtering efficiently.
Self-Check
"What if we add an index on the manager_id column? How would the time complexity change?"