LATERAL join for correlated subqueries in PostgreSQL - Time & Space Complexity

Time Complexity: LATERAL join for correlated subqueries

O(n)

Understanding Time Complexity

We want to understand how the time needed to run a LATERAL join with a correlated subquery changes as the data grows.

Specifically, how does the number of rows in the main table affect the total work done?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

SELECT a.id, b.val
FROM a
JOIN LATERAL (
  SELECT val
  FROM b
  WHERE b.a_id = a.id
  ORDER BY val DESC
  LIMIT 1
) b ON true;
    

This query finds, for each row in table a, the highest val from table b where b.a_id matches a.id.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: For each row in a, run a subquery on b to find matching rows.
• How many times: The subquery runs once per row in a.

How Execution Grows With Input

As the number of rows in a grows, the subquery runs more times, each searching b for matches.

Input Size (rows in a)	Approx. Operations
10	10 subqueries on b
100	100 subqueries on b
1000	1000 subqueries on b

Pattern observation: The total work grows roughly in direct proportion to the number of rows in a.

Final Time Complexity

Time Complexity: O(n)

This means the time to run the query grows linearly with the number of rows in the main table a.

Common Mistake

[X] Wrong: "The subquery runs just once, so the query is always fast regardless of data size."

[OK] Correct: The subquery runs once for each row in a, so if a has many rows, the total work adds up and takes longer.

Interview Connect

Understanding how correlated subqueries and LATERAL joins scale helps you write efficient queries and explain your reasoning clearly in interviews.

Self-Check

"What if the subquery inside the LATERAL join returned multiple rows instead of just one? How would that affect the time complexity?"