EXPLAIN output reading in PostgreSQL - Time & Space Complexity

Time Complexity: EXPLAIN output reading

O(n)

Understanding Time Complexity

When we run a query in PostgreSQL, EXPLAIN helps us see how the database plans to get the data.

We want to understand how the work grows as the data grows.

Scenario Under Consideration

Analyze the time complexity of this EXPLAIN output for a simple SELECT query.

EXPLAIN SELECT * FROM employees WHERE department_id = 5;

This query fetches all employees in department 5, and EXPLAIN shows how PostgreSQL plans to do it.

Identify Repeating Operations

Look at what the database does repeatedly to find matching rows.

• Primary operation: Scanning rows in the employees table.
• How many times: Once for each row until matches are found.

How Execution Grows With Input

As the number of employees grows, the work to find matches grows too.

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 roughly in direct proportion to the number of rows.

Final Time Complexity

Time Complexity: O(n)

This means the time to run the query grows linearly as the table gets bigger.

Common Mistake

[X] Wrong: "EXPLAIN output always shows the exact time the query will take."

[OK] Correct: EXPLAIN shows the plan and estimated costs, not the exact time, which depends on data and indexes.

Interview Connect

Understanding EXPLAIN output helps you talk about how queries work and how they scale, a useful skill in real projects.

Self-Check

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

Practice

1. What does the EXPLAIN command in PostgreSQL primarily show?

easy

A. How PostgreSQL plans to execute a query

B. The exact data returned by the query

C. The syntax errors in the query

D. The database schema structure

Solution

1. Step 1: Understand the purpose of EXPLAIN

   EXPLAIN shows the query plan, which is how PostgreSQL intends to run the query.

2. Step 2: Differentiate from other commands

   It does not show actual data or errors, only the plan.

3. Final Answer:

   How PostgreSQL plans to execute a query -> Option A

4. Quick Check:

   EXPLAIN = query plan [OK]

Hint: EXPLAIN = query plan, not data or errors [OK]

Common Mistakes:

• Thinking EXPLAIN shows query results
• Confusing EXPLAIN with syntax error checks
• Assuming EXPLAIN shows database schema

2. Which of the following is the correct syntax to get the query plan for SELECT * FROM users; in PostgreSQL?

easy

A. EXPLAIN SELECT * FROM users;

B. EXPLAIN ANALYZE users SELECT *;

C. EXPLAIN FROM users SELECT *;

D. ANALYZE EXPLAIN SELECT * FROM users;

Solution

1. Step 1: Recall correct EXPLAIN syntax

   The correct syntax is EXPLAIN followed by the query.

2. Step 2: Check each option

   EXPLAIN SELECT * FROM users; matches the correct syntax. Others mix keywords incorrectly.

3. Final Answer:

   EXPLAIN SELECT * FROM users; -> Option A

4. Quick Check:

   EXPLAIN + query = correct syntax [OK]

Hint: EXPLAIN always precedes the query [OK]

Common Mistakes:

• Placing ANALYZE before EXPLAIN
• Using FROM before SELECT incorrectly
• Mixing keywords in wrong order

3. Given the EXPLAIN output below for SELECT * FROM orders WHERE customer_id = 5;, what does the line Index Scan using idx_customer_id on orders indicate?

medium

A. PostgreSQL is scanning the entire orders table

B. PostgreSQL is using an index to find matching rows

C. PostgreSQL is performing a sequential scan

D. PostgreSQL is creating a new index during query

Solution

1. Step 1: Understand 'Index Scan' meaning

   An Index Scan means PostgreSQL uses an index to quickly find rows matching the condition.

2. Step 2: Compare with other scan types

   Sequential scan means scanning all rows, which is not the case here.

3. Final Answer:

   PostgreSQL is using an index to find matching rows -> Option B

4. Quick Check:

   Index Scan = use index [OK]

Hint: 'Index Scan' means index used, not full table scan [OK]

Common Mistakes:

• Confusing Index Scan with Sequential Scan
• Thinking index is created during query
• Assuming full table scan always happens

4. You run EXPLAIN ANALYZE SELECT * FROM products WHERE price > 100; but get an error saying "relation 'products' does not exist." What is the likely cause?

medium

A. EXPLAIN ANALYZE cannot be used with WHERE clauses

B. The query syntax is incorrect for EXPLAIN ANALYZE

C. The table 'products' does not exist in the current database

D. You forgot to commit the transaction

Solution

1. Step 1: Analyze the error message

   The error says the table 'products' does not exist, meaning PostgreSQL cannot find it.

2. Step 2: Check other options

   EXPLAIN ANALYZE works with WHERE clauses and the syntax is correct. Committing transaction is unrelated.

3. Final Answer:

   The table 'products' does not exist in the current database -> Option C

4. Quick Check:

   Relation not found = missing table [OK]

Hint: Check table existence if 'relation does not exist' error appears [OK]

Common Mistakes:

• Assuming EXPLAIN ANALYZE disallows WHERE
• Blaming syntax when table is missing
• Thinking commit affects table visibility

5. You want to optimize a slow query. The EXPLAIN ANALYZE output shows a Seq Scan on a large table with a filter on a column. What is the best next step to improve performance?

hard

A. Drop the table and recreate it

B. Rewrite the query without the filter

C. Increase the work_mem setting

D. Create an index on the filtered column

Solution

1. Step 1: Understand Seq Scan impact

   A Seq Scan reads all rows, which is slow on large tables when filtering.

2. Step 2: Use index to speed filtering

   Creating an index on the filtered column lets PostgreSQL quickly find matching rows, avoiding full scan.

3. Final Answer:

   Create an index on the filtered column -> Option D

4. Quick Check:

   Seq Scan slow? Add index [OK]

Hint: Seq Scan slow? Add index on filter column [OK]

Common Mistakes:

• Removing filter instead of indexing
• Changing memory settings without indexing
• Dropping table unnecessarily