Boolean column filtering patterns in PostgreSQL - Time & Space Complexity

Time Complexity: Boolean column filtering patterns

O(n)

Understanding Time Complexity

When we filter rows in a database using a true/false column, the time it takes can change as the table grows.

We want to know how the filtering time changes when the number of rows increases.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

SELECT *
FROM orders
WHERE is_paid = true;

-- or

SELECT *
FROM orders
WHERE is_paid;
    

This code selects all rows where the boolean column is_paid is true.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Scanning each row to check the boolean column.
• How many times: Once for every row in the table.

How Execution Grows With Input

As the number of rows grows, the database checks more rows one by one.

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 filter grows in a straight line as the table gets bigger.

Common Mistake

[X] Wrong: "Filtering by a boolean column is instant no matter the table size."

[OK] Correct: The database still checks each row unless there is a special index, so time grows with the number of rows.

Interview Connect

Understanding how filtering by boolean columns scales helps you explain query performance clearly and shows you know how databases handle data.

Self-Check

"What if we add an index on the boolean column? How would the time complexity change?"