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

Practice

1. What is the main purpose of using a LATERAL join in PostgreSQL?

easy

A. To run a subquery for each row of the main table using that row's data

B. To join two tables without any condition

C. To create a temporary table for all rows at once

D. To speed up queries by caching results

Solution

1. Step 1: Understand what LATERAL join does

   A LATERAL join allows a subquery to use columns from the current row of the main query.

2. Step 2: Identify the main purpose

   This means the subquery runs once per row, using that row's data to produce related results.

3. Final Answer:

   To run a subquery for each row of the main table using that row's data -> Option A

4. Quick Check:

   LATERAL join = per-row subquery execution [OK]

Hint: LATERAL runs subqueries per row using that row's data [OK]

Common Mistakes:

• Thinking LATERAL joins all rows at once
• Confusing LATERAL with regular JOIN
• Assuming LATERAL speeds up queries by caching

2. Which of the following is the correct syntax to use a LATERAL join in PostgreSQL?

easy

A. SELECT a.id, b.value FROM table_a a JOIN (SELECT value FROM table_b WHERE b.a_id = a.id) b ON true;

B. SELECT a.id, b.value FROM table_a a JOIN LATERAL (SELECT value FROM table_b WHERE b.a_id = a.id) b ON true;

C. SELECT a.id, b.value FROM table_a a LEFT JOIN LATERAL table_b b ON b.a_id = a.id;

D. SELECT a.id, b.value FROM table_a a CROSS JOIN table_b b WHERE b.a_id = a.id;

Solution

1. Step 1: Identify correct LATERAL syntax

   LATERAL must be explicitly stated before the subquery or table function to allow referencing outer query columns.

2. Step 2: Check each option

   SELECT a.id, b.value FROM table_a a JOIN LATERAL (SELECT value FROM table_b WHERE b.a_id = a.id) b ON true; correctly uses JOIN LATERAL with a subquery referencing outer alias 'a'. SELECT a.id, b.value FROM table_a a JOIN (SELECT value FROM table_b WHERE b.a_id = a.id) b ON true; misses LATERAL keyword. SELECT a.id, b.value FROM table_a a LEFT JOIN LATERAL table_b b ON b.a_id = a.id; uses LATERAL but tries to join a table directly without subquery syntax. SELECT a.id, b.value FROM table_a a CROSS JOIN table_b b WHERE b.a_id = a.id; uses CROSS JOIN without LATERAL, so no correlation.

3. Final Answer:

   SELECT a.id, b.value FROM table_a a JOIN LATERAL (SELECT value FROM table_b WHERE b.a_id = a.id) b ON true; -> Option B

4. Quick Check:

   Correct LATERAL syntax includes keyword before subquery [OK]

Hint: LATERAL keyword must precede subquery to access outer columns [OK]

Common Mistakes:

• Omitting LATERAL keyword before subquery
• Using regular JOIN without correlation
• Trying to join tables directly without subquery

3. Given the tables:
users(id, name)
orders(id, user_id, amount)
What will this query return?

SELECT u.name, o.amount FROM users u JOIN LATERAL (SELECT amount FROM orders WHERE user_id = u.id ORDER BY amount DESC LIMIT 1) o ON true;

medium

A. Users with all their orders listed

B. All orders with user names repeated

C. Syntax error due to missing ON condition

D. Each user with their highest order amount

Solution

1. Step 1: Understand the LATERAL subquery

   The subquery selects the highest order amount per user by ordering descending and limiting to 1.

2. Step 2: Analyze the JOIN LATERAL effect

   For each user row, the subquery runs and returns that user's top order amount, joining on true to include all users with orders.

3. Final Answer:

   Each user with their highest order amount -> Option D

4. Quick Check:

   LATERAL subquery returns top order per user [OK]

Hint: LATERAL runs subquery per user to get top order [OK]

Common Mistakes:

• Thinking it returns all orders per user
• Assuming syntax error due to ON true
• Confusing join with CROSS JOIN

4. Identify the error in this query:

SELECT u.name, o.amount FROM users u JOIN LATERAL (SELECT amount FROM orders WHERE user_id = u.id ORDER BY amount DESC LIMIT 1) o;

medium

A. Subquery cannot reference outer query columns

B. Incorrect alias usage for orders table

C. Missing ON clause after LATERAL join

D. ORDER BY not allowed in subqueries

Solution

1. Step 1: Check JOIN syntax

   Every JOIN requires an ON clause or USING clause to specify join condition.

2. Step 2: Verify the query

   The query uses JOIN LATERAL but omits ON clause, causing syntax error.

3. Final Answer:

   Missing ON clause after LATERAL join -> Option C

4. Quick Check:

   JOIN must have ON or USING clause [OK]

Hint: Always add ON clause after JOIN LATERAL [OK]

Common Mistakes:

• Forgetting ON clause after JOIN LATERAL
• Thinking subquery can't use outer columns
• Believing ORDER BY is disallowed in subqueries

5. You want to list each customer with their two most recent orders using LATERAL join. Which query correctly achieves this?

hard

A. SELECT c.name, o.order_id FROM customers c JOIN LATERAL (SELECT order_id FROM orders WHERE customer_id = c.id ORDER BY order_date DESC LIMIT 2) o ON true;

B. SELECT c.name, o.order_id FROM customers c JOIN orders o ON o.customer_id = c.id ORDER BY o.order_date DESC LIMIT 2;

C. SELECT c.name, o.order_id FROM customers c CROSS JOIN LATERAL orders o WHERE o.customer_id = c.id LIMIT 2;

D. SELECT c.name, o.order_id FROM customers c LEFT JOIN LATERAL (SELECT order_id FROM orders WHERE customer_id = c.id ORDER BY order_date ASC LIMIT 2) o ON true;

Solution

1. Step 1: Understand the requirement

   We want two most recent orders per customer, so order by order_date DESC and limit 2 in subquery.

2. Step 2: Check each option

   SELECT c.name, o.order_id FROM customers c JOIN LATERAL (SELECT order_id FROM orders WHERE customer_id = c.id ORDER BY order_date DESC LIMIT 2) o ON true; uses JOIN LATERAL with correct ordering and limit, joining on true to include all customers with orders. SELECT c.name, o.order_id FROM customers c JOIN orders o ON o.customer_id = c.id ORDER BY o.order_date DESC LIMIT 2; limits total rows, not per customer. SELECT c.name, o.order_id FROM customers c CROSS JOIN LATERAL orders o WHERE o.customer_id = c.id LIMIT 2; uses CROSS JOIN LATERAL incorrectly without subquery. SELECT c.name, o.order_id FROM customers c LEFT JOIN LATERAL (SELECT order_id FROM orders WHERE customer_id = c.id ORDER BY order_date ASC LIMIT 2) o ON true; orders ASC, which gives oldest orders, not recent.

3. Final Answer:

   SELECT c.name, o.order_id FROM customers c JOIN LATERAL (SELECT order_id FROM orders WHERE customer_id = c.id ORDER BY order_date DESC LIMIT 2) o ON true; -> Option A

4. Quick Check:

   LATERAL with ORDER BY DESC and LIMIT 2 per customer [OK]

Hint: Use LATERAL with ORDER BY DESC and LIMIT for top N per row [OK]

Common Mistakes:

• Limiting total rows instead of per customer
• Ordering ascending instead of descending
• Using CROSS JOIN LATERAL without subquery