Time Complexity: Why NULL is not a value
O(n)
0
0
Why NULL is not a value in SQL - Performance Analysis
Understanding Time Complexity
When working with databases, NULL represents missing or unknown information, not a regular value.
We want to understand how operations involving NULL affect the time it takes to run queries.
Scenario Under Consideration
Analyze the time complexity of a query filtering rows with NULL checks.
SELECT *
FROM employees
WHERE department_id IS NULL;
This query finds all employees without a department assigned (NULL department_id).
Identify Repeating Operations
Look at what repeats when the database checks for NULL values.
- Primary operation: Scanning each row to test if the department_id is NULL.
- How many times: Once per row in the employees table.
How Execution Grows With Input
As the number of employees grows, the database must check more rows for NULL.
| Input Size (n) | Approx. Operations |
|---|---|
| 10 | 10 checks for NULL |
| 100 | 100 checks for NULL |
| 1000 | 1000 checks for NULL |
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 find NULL values grows linearly with the number of rows.
Common Mistake
[X] Wrong: "NULL is just another value, so checking for NULL is faster or simpler than other values."
[OK] Correct: NULL means unknown or missing, so the database must explicitly test each row, which takes time like any other check.
Interview Connect
Understanding how NULL affects query time helps you explain database behavior clearly and shows you know how data quality impacts performance.
Self-Check
"What if we added an index on department_id? How would that change the time complexity when checking for NULL?"