Common query optimization patterns in PostgreSQL - Time & Space Complexity

Time Complexity: Common query optimization patterns

O(n + m)

Understanding Time Complexity

When we write database queries, some ways of asking questions take longer than others.

We want to understand how the time to get answers grows as the data gets bigger.

Scenario Under Consideration

Analyze the time complexity of this query pattern using indexes and joins.

SELECT orders.id, customers.name
FROM orders
JOIN customers ON orders.customer_id = customers.id
WHERE customers.region = 'North';
    

This query finds orders from customers in the 'North' region by joining two tables.

Identify Repeating Operations

Look for repeated work done by the database engine.

• Primary operation: Scanning the customers table to find matching regions.
• How many times: Once for each row in orders, then matching customers for each found order.

How Execution Grows With Input

As the number of customers and orders grows, the work increases.

Input Size (n)	Approx. Operations
10 customers, 50 orders	About 50 checks + matching customers
100 customers, 500 orders	About 500 checks + matching customers
1000 customers, 5000 orders	About 5000 checks + matching customers

Pattern observation: The work grows roughly in proportion to the number of customers and orders.

Final Time Complexity

Time Complexity: O(n + m)

This means the time grows roughly with the size of both tables involved.

Common Mistake

[X] Wrong: "Adding an index always makes the query instant."

[OK] Correct: Indexes help, but if the query scans many rows or joins large tables, it still takes time.

Interview Connect

Understanding how queries grow with data size helps you write better questions and explain your choices clearly.

Self-Check

"What if we added a filter on orders before the join? How would that change the time complexity?"