LAG and LEAD for row comparison in PostgreSQL - Time & Space Complexity

Time Complexity: LAG and LEAD for row comparison

O(n)

Understanding Time Complexity

We want to understand how the time needed to run queries using LAG and LEAD changes as the data grows.

How does the number of rows affect the work done by these functions?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

SELECT
  id,
  value,
  LAG(value) OVER (ORDER BY id) AS prev_value,
  LEAD(value) OVER (ORDER BY id) AS next_value
FROM data_table;
    

This query compares each row's value with the previous and next rows based on the id order.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Scanning each row once and accessing neighboring rows.
• How many times: Once per row in the table.

How Execution Grows With Input

As the number of rows grows, the query processes each row once to find previous and next values.

Input Size (n)	Approx. Operations
10	About 10 operations
100	About 100 operations
1000	About 1000 operations

Pattern observation: The work grows directly with the number of rows, increasing steadily.

Final Time Complexity

Time Complexity: O(n)

This means the time to run the query grows in a straight line as the number of rows increases.

Common Mistake

[X] Wrong: "LAG and LEAD scan the whole table multiple times, so time grows much faster than the number of rows."

[OK] Correct: These functions only look at each row once and access neighbors directly, so they do not multiply the work by scanning repeatedly.

Interview Connect

Understanding how window functions like LAG and LEAD scale helps you explain query performance clearly and confidently in real situations.

Self-Check

"What if we added a PARTITION BY clause to the window functions? How would the time complexity change?"

Practice

1. What is the main purpose of the LAG function in PostgreSQL?

easy

A. To sort rows in ascending order

B. To access data from the next row in the same result set

C. To delete duplicate rows

D. To access data from a previous row in the same result set

Solution

1. Step 1: Understand LAG function behavior

   The LAG function returns the value from a previous row based on the current row's position.

2. Step 2: Compare with other options

   LEAD accesses the next row, sorting and deleting duplicates are unrelated to LAG.

3. Final Answer:

   To access data from a previous row in the same result set -> Option D

4. Quick Check:

   LAG = previous row data access [OK]

Hint: LAG looks backward, LEAD looks forward in rows [OK]

Common Mistakes:

• Confusing LAG with LEAD
• Thinking LAG sorts rows
• Assuming LAG deletes duplicates

2. Which of the following is the correct syntax to use LEAD to get the next row's salary ordered by employee_id?

easy

A. LEAD(salary) OVER (ORDER BY employee_id)

B. LEAD(salary ORDER BY employee_id)

C. LEAD(salary) ORDER BY employee_id

D. LEAD(ORDER BY salary) OVER (employee_id)

Solution

1. Step 1: Recall correct LEAD syntax

   The correct syntax uses LEAD(column) OVER (ORDER BY column) to specify the column and ordering.

2. Step 2: Check each option

   LEAD(salary) OVER (ORDER BY employee_id) matches the correct syntax; others misuse parentheses or clause order.

3. Final Answer:

   LEAD(salary) OVER (ORDER BY employee_id) -> Option A

4. Quick Check:

   LEAD(column) OVER (ORDER BY column) [OK]

Hint: LEAD/LAG need OVER with ORDER BY inside parentheses [OK]

Common Mistakes:

• Placing ORDER BY outside OVER clause
• Missing parentheses around ORDER BY
• Putting ORDER BY inside function parameters

3. Given the table sales with columns month and revenue, what will this query return?

SELECT month, revenue, LAG(revenue) OVER (ORDER BY month) AS prev_revenue FROM sales;

medium

A. Each row shows only current month revenue

B. Each row shows current month revenue and next month's revenue

C. Each row shows current month revenue and previous month's revenue

D. Query will cause a syntax error

Solution

1. Step 1: Understand LAG with ORDER BY month

   The LAG(revenue) returns the revenue from the previous month ordered by month.

2. Step 2: Interpret query output

   Each row shows current month revenue and previous month's revenue in prev_revenue. The first row's prev_revenue will be NULL.

3. Final Answer:

   Each row shows current month revenue and previous month's revenue -> Option C

4. Quick Check:

   LAG = previous row value [OK]

Hint: LAG returns previous row's value based on ORDER BY [OK]

Common Mistakes:

• Confusing LAG with LEAD
• Expecting next month's revenue instead
• Thinking query causes error

4. Identify the error in this query:

SELECT employee_id, salary, LEAD(salary) ORDER BY employee_id FROM employees;

medium

A. ORDER BY should be inside LEAD() function

B. Missing OVER() clause for LEAD function

C. LEAD cannot be used with salary column

D. employee_id must be in GROUP BY clause

Solution

1. Step 1: Check LEAD function syntax

   LEAD requires an OVER() clause to specify ordering and partitioning.

2. Step 2: Analyze query structure

   The query uses LEAD(salary) without OVER(), causing a syntax error.

3. Final Answer:

   Missing OVER() clause for LEAD function -> Option B

4. Quick Check:

   Window functions need OVER() [OK]

Hint: Always use OVER() with LEAD/LAG [OK]

Common Mistakes:

• Omitting OVER() clause
• Placing ORDER BY outside OVER()
• Confusing window functions with aggregates

5. You want to find all employees whose salary increased compared to the previous employee ordered by hire_date. Which query correctly uses LAG to achieve this?

hard

A. SELECT employee_id, salary FROM (SELECT employee_id, salary, LAG(salary) OVER (ORDER BY hire_date) AS prev_salary FROM employees) t WHERE salary > prev_salary;

B. SELECT employee_id, salary FROM employees WHERE salary > (SELECT LAG(salary) FROM employees ORDER BY hire_date);

C. SELECT employee_id, salary, LAG(salary) OVER (ORDER BY hire_date) AS prev_salary FROM employees WHERE salary > prev_salary;

D. SELECT employee_id, salary, LAG(salary) OVER (ORDER BY hire_date) AS prev_salary FROM employees HAVING salary > prev_salary;

Solution

1. Step 1: Understand LAG usage for filtering

   Window functions like LAG cannot be used directly in WHERE clause; use subquery or CTE to compute then filter.

2. Step 2: Analyze options

   SELECT employee_id, salary FROM (SELECT employee_id, salary, LAG(salary) OVER (ORDER BY hire_date) AS prev_salary FROM employees) t WHERE salary > prev_salary; correctly uses subquery. The second option's subquery LAG lacks OVER clause (syntax error). The third uses alias in WHERE (invalid). The fourth uses HAVING without GROUP BY (invalid).

3. Final Answer:

   SELECT employee_id, salary FROM (SELECT employee_id, salary, LAG(salary) OVER (ORDER BY hire_date) AS prev_salary FROM employees) t WHERE salary > prev_salary; -> Option A

4. Quick Check:

   Subquery to filter on window functions [OK]

Hint: Use subquery to filter on window function results [OK]

Common Mistakes:

• Using alias in WHERE clause
• Misusing HAVING without GROUP BY
• Incorrect subquery for LAG