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