NULL in AND, OR, NOT logic in SQL - Time & Space Complexity

Time Complexity: NULL in AND, OR, NOT logic

O(n)

Understanding Time Complexity

We want to understand how SQL evaluates logical expressions involving NULL values.

How does the presence of NULL affect the number of checks the database performs?

Scenario Under Consideration

Analyze the time complexity of evaluating logical expressions with NULL.

SELECT * FROM table_name
WHERE (column1 = 10 AND column2 IS NULL)
   OR (column3 > 5 AND NOT (column4 = 20));
    

This query filters rows based on combined AND, OR, and NOT conditions that include NULL checks.

Identify Repeating Operations

Look at what happens for each row in the table.

• Primary operation: Evaluating logical conditions (AND, OR, NOT) including NULL checks.
• How many times: Once per row, for each condition in the WHERE clause.

How Execution Grows With Input

Each row requires checking all conditions once.

Input Size (n)	Approx. Operations
10	About 10 sets of condition checks
100	About 100 sets of condition checks
1000	About 1000 sets of condition 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 evaluate the query grows linearly with the number of rows.

Common Mistake

[X] Wrong: "NULL in logical expressions causes the query to run slower exponentially."

[OK] Correct: Each row is checked once; NULL just affects the logic result, not the number of checks.

Interview Connect

Understanding how NULL affects logical checks helps you reason about query performance and correctness in real databases.

Self-Check

"What if the query had nested subqueries with NULL checks? How would that affect time complexity?"