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