LATERAL subqueries in PostgreSQL - Time & Space Complexity

Time Complexity: LATERAL subqueries

O(n * m)

Understanding Time Complexity

When using LATERAL subqueries in PostgreSQL, it is important to understand how the query's execution time changes as the data grows.

We want to know how the number of operations increases when the input tables get bigger.

Scenario Under Consideration

Analyze the time complexity of the following query using a LATERAL join.

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

This query finds the most recent order for each customer by joining each customer to their latest order using a LATERAL subquery.

Identify Repeating Operations

Look for repeated actions in the query.

• Primary operation: For each customer, the database runs a subquery to find their latest order.
• How many times: Once per customer, so the number of times equals the number of customers.

How Execution Grows With Input

The query runs the subquery once for each customer. If there are more customers, the total work grows proportionally.

Input Size (customers)	Approx. Operations
10	10 subqueries
100	100 subqueries
1000	1000 subqueries

Pattern observation: The total work increases directly with the number of customers.

Final Time Complexity

Time Complexity: O(n * m)

This means the query's execution time grows linearly with the number of customers and the cost of finding the latest order per customer.

Common Mistake

[X] Wrong: "The LATERAL subquery runs only once for the whole query."

[OK] Correct: The LATERAL subquery runs separately for each row from the main table, so it repeats as many times as there are customers.

Interview Connect

Understanding how LATERAL subqueries scale helps you write efficient queries and explain their performance clearly in real situations.

Self-Check

"What if we replaced the LATERAL subquery with a simple JOIN on orders without LIMIT? How would the time complexity change?"

Practice

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

easy

A. To allow a subquery to reference columns from tables listed before it in the FROM clause

B. To create a temporary table that lasts only for the duration of the query

C. To optimize the query by parallelizing subqueries automatically

D. To enforce foreign key constraints between tables

Solution

1. Step 1: Understand the role of LATERAL

   LATERAL allows a subquery to access columns from tables that appear earlier in the FROM clause.

2. Step 2: Compare with other options

   The other options describe different features unrelated to LATERAL's purpose.

3. Final Answer:

   To allow a subquery to reference columns from tables listed before it in the FROM clause -> Option A

4. Quick Check:

   LATERAL = subquery uses previous table columns [OK]

Hint: LATERAL lets subqueries see earlier tables in FROM [OK]

Common Mistakes:

• Thinking LATERAL creates temporary tables
• Confusing LATERAL with query parallelism
• Assuming LATERAL enforces constraints

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

easy

A. SELECT * FROM table1, (SELECT * FROM table2 WHERE table2.id = table1.id) sub;

B. SELECT * FROM table1 JOIN LATERAL table2 ON table2.id = table1.id;

C. SELECT * FROM table1 CROSS JOIN LATERAL (SELECT * FROM table2 WHERE table2.id = table1.id) sub;

D. SELECT * FROM table1 LATERAL JOIN table2 ON table2.id = table1.id;

Solution

1. Step 1: Identify correct LATERAL syntax

   The correct syntax uses CROSS JOIN LATERAL with a subquery in parentheses and an alias.

2. Step 2: Check each option

   SELECT * FROM table1, (SELECT * FROM table2 WHERE table2.id = table1.id) sub; misses LATERAL keyword causing reference error; SELECT * FROM table1 JOIN LATERAL table2 ON table2.id = table1.id; uses JOIN LATERAL incorrectly without parentheses; SELECT * FROM table1 LATERAL JOIN table2 ON table2.id = table1.id; has invalid syntax.

3. Final Answer:

   SELECT * FROM table1 CROSS JOIN LATERAL (SELECT * FROM table2 WHERE table2.id = table1.id) sub; -> Option C

4. Quick Check:

   Correct LATERAL syntax = SELECT * FROM table1 CROSS JOIN LATERAL (SELECT * FROM table2 WHERE table2.id = table1.id) sub; [OK]

Hint: Use CROSS JOIN LATERAL with subquery in parentheses [OK]

Common Mistakes:

• Omitting LATERAL keyword
• Not aliasing the subquery
• Using LATERAL without parentheses

3. Given tables users(id, name) and orders(user_id, amount), what does this query return?

SELECT u.name, o.total FROM users u CROSS JOIN LATERAL (SELECT SUM(amount) AS total FROM orders WHERE user_id = u.id) o;

medium

A. Each user with the total amount of their orders

B. All users joined with all orders without filtering

C. Only users who have orders, with their order totals

D. Syntax error due to missing GROUP BY

Solution

1. Step 1: Analyze the LATERAL subquery

   The subquery sums orders per user using user_id = u.id, so it calculates total per user.

2. Step 2: Understand CROSS JOIN LATERAL effect

   It runs the subquery for each user, returning their name and total order amount, including users with zero orders (total will be NULL).

3. Final Answer:

   Each user with the total amount of their orders -> Option A

4. Quick Check:

   LATERAL sums orders per user = Each user with the total amount of their orders [OK]

Hint: LATERAL runs subquery per row, here summing orders per user [OK]

Common Mistakes:

• Thinking it returns all orders without grouping
• Assuming only users with orders appear
• Confusing CROSS JOIN LATERAL with INNER JOIN

4. Identify the error in this query using LATERAL:

SELECT t1.id, t2.val FROM table1 t1 JOIN LATERAL (SELECT val FROM table2 WHERE table2.ref = t1.id) t2;

medium

A. Missing alias for the LATERAL subquery

B. JOIN LATERAL requires CROSS keyword

C. Subquery must return only one column

D. No error; query is correct

Solution

1. Step 1: Check alias usage

   The subquery is aliased as t2, so no issue there.

2. Step 2: Verify JOIN LATERAL syntax

   JOIN LATERAL without CROSS is valid syntax in PostgreSQL; CROSS JOIN LATERAL is one form, but JOIN LATERAL alone is allowed as INNER JOIN LATERAL.

3. Step 3: Confirm subquery column count

   Subquery returns one column 'val', which is acceptable.

4. Final Answer:

   No error; query is correct -> Option D

5. Quick Check:

   JOIN LATERAL syntax without CROSS is valid = No error [OK]

Hint: JOIN LATERAL without CROSS is valid syntax [OK]

Common Mistakes:

• Using JOIN LATERAL without CROSS
• Forgetting subquery alias
• Expecting subquery to return multiple columns

5. You want to list each customer with their top 2 most expensive orders using LATERAL. Which query correctly achieves this?

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

hard

A. The query misses GROUP BY on customers

B. This query correctly lists each customer with their top 2 orders

C. LATERAL cannot be used with LIMIT inside subqueries

D. The query will return only customers with at least 2 orders

Solution

1. Step 1: Understand LATERAL with LIMIT

   The subquery selects top 2 orders per customer by ordering and limiting results.

2. Step 2: Check if query returns all customers

   CROSS JOIN LATERAL runs subquery per customer; if no orders, no rows for that customer appear.

3. Step 3: Confirm correctness

   The query correctly lists each customer with up to 2 highest orders; no syntax or logic errors.

4. Final Answer:

   This query correctly lists each customer with their top 2 orders -> Option B

5. Quick Check:

   LATERAL with LIMIT works for top N per row [OK]

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

Common Mistakes:

• Thinking GROUP BY is needed here
• Believing LATERAL disallows LIMIT
• Assuming all customers appear even without orders