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?"

Practice

1. Which of the following is the best reason to create an index on a column in PostgreSQL?

easy

A. To speed up searches on that column

B. To reduce the size of the database

C. To automatically backup the data

D. To encrypt the data in that column

Solution

1. Step 1: Understand what an index does

   An index helps the database find rows faster by creating a quick lookup structure.

2. Step 2: Match the purpose to the options

   Only speeding up searches matches the purpose of an index; other options are unrelated.

3. Final Answer:

   To speed up searches on that column -> Option A

4. Quick Check:

   Index = Speed up search [OK]

Hint: Indexes speed up searches, not storage or encryption [OK]

Common Mistakes:

• Thinking indexes reduce database size
• Confusing indexes with backups
• Assuming indexes encrypt data

2. Which of the following is the correct syntax to check the query plan in PostgreSQL?

easy

A. EXPLAIN SELECT * FROM users;

B. DESCRIBE SELECT * FROM users;

C. PLAN SELECT * FROM users;

D. SHOW PLAN SELECT * FROM users;

Solution

1. Step 1: Recall the command to view query plans

   PostgreSQL uses EXPLAIN to show how it will run a query.

2. Step 2: Compare options to the correct command

   Only EXPLAIN SELECT * FROM users; is valid syntax for query plans.

3. Final Answer:

   EXPLAIN SELECT * FROM users; -> Option A

4. Quick Check:

   EXPLAIN = Query plan check [OK]

Hint: Use EXPLAIN before your query to see the plan [OK]

Common Mistakes:

• Using SHOW PLAN which is invalid
• Trying PLAN or DESCRIBE which are not PostgreSQL commands
• Missing the EXPLAIN keyword

3. Consider the query:
SELECT id, name FROM employees WHERE department = 'Sales';
Which optimization pattern does this query follow?

medium

A. Using a JOIN to combine tables

B. Using ORDER BY to sort results

C. Using a subquery to filter data

D. Selecting only needed columns instead of *

Solution

1. Step 1: Analyze the SELECT clause

   The query selects only 'id' and 'name', not all columns with '*'.

2. Step 2: Identify the optimization pattern

   Selecting only needed columns reduces data transfer and improves speed.

3. Final Answer:

   Selecting only needed columns instead of * -> Option D

4. Quick Check:

   Selective columns = Better performance [OK]

Hint: Avoid SELECT *; pick only columns you need [OK]

Common Mistakes:

• Confusing JOIN usage with column selection
• Thinking ORDER BY is always an optimization
• Assuming subqueries are used here

4. You have this query:
SELECT * FROM orders WHERE order_date = '2023-01-01';
It runs slowly. Which fix will likely improve performance?

medium

A. Change SELECT * to SELECT COUNT(*)

B. Add an index on the order_date column

C. Remove the WHERE clause

D. Use GROUP BY order_date

Solution

1. Step 1: Identify the cause of slowness

   Query filters on order_date but may scan all rows without an index.

2. Step 2: Apply optimization by indexing

   Adding an index on order_date lets PostgreSQL find matching rows faster.

3. Final Answer:

   Add an index on the order_date column -> Option B

4. Quick Check:

   Index on filter column = Faster query [OK]

Hint: Index columns used in WHERE for faster filtering [OK]

Common Mistakes:

• Removing WHERE loses filtering purpose
• Changing SELECT * to COUNT(*) changes result, not speed
• Using GROUP BY without aggregation is incorrect

5. You want to optimize a query that joins two large tables on a column and filters by a date range. Which combination of patterns will best improve performance?

hard

A. Use subqueries instead of JOINs; do not filter by date

B. Select all columns with *; avoid indexes to save space

C. Create indexes on join columns and filter columns; use EXPLAIN to check plan

D. Add ORDER BY on join column; remove WHERE clause

Solution

1. Step 1: Identify key optimization needs

   Joining large tables and filtering by date needs indexes on join and filter columns.

2. Step 2: Use EXPLAIN to verify query plan

   Checking the plan helps confirm indexes are used and query is efficient.

3. Final Answer:

   Create indexes on join columns and filter columns; use EXPLAIN to check plan -> Option C

4. Quick Check:

   Indexes + EXPLAIN = Best optimization [OK]

Hint: Index join and filter columns; verify with EXPLAIN [OK]

Common Mistakes:

• Selecting all columns wastes resources
• Avoiding indexes slows queries
• Removing WHERE loses filtering benefits