Why filtering behavior matters in PostgreSQL - Performance Analysis

Time Complexity: Why filtering behavior matters

O(n)

Understanding Time Complexity

When we run database queries, filtering helps us pick only the rows we want.

We want to know how filtering affects the time it takes to get results.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

SELECT *
FROM orders
WHERE order_date >= '2023-01-01'
  AND status = 'shipped';

This query selects all orders shipped since January 1, 2023, filtering rows by date and status.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Scanning each row in the orders table to check the filter conditions.
• How many times: Once for every row in the table (n times).

How Execution Grows With Input

As the number of orders grows, the database checks more rows to find matches.

Input Size (n)	Approx. Operations
10	About 10 row checks
100	About 100 row checks
1000	About 1000 row checks

Pattern observation: The work grows directly with the number of rows; more rows mean more checks.

Final Time Complexity

Time Complexity: O(n)

This means the time to run the query grows in a straight line with the number of rows to check.

Common Mistake

[X] Wrong: "Filtering always makes queries run faster regardless of data size."

[OK] Correct: Filtering still needs to look at each row to decide if it matches, so with more data, it takes more time.

Interview Connect

Understanding how filtering affects query time helps you write better queries and explain your choices clearly.

Self-Check

"What if we added an index on order_date and status? How would the time complexity change?"