LAG function for previous row access in SQL - Time & Space Complexity

Time Complexity: LAG function for previous row access

O(n)

Understanding Time Complexity

We want to understand how the time it takes to run a query using the LAG function changes as the data grows.

Specifically, how does accessing the previous row affect performance when the table gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

SELECT 
  employee_id, 
  salary, 
  LAG(salary, 1) OVER (ORDER BY employee_id) AS previous_salary
FROM employees;
    

This query retrieves each employee's salary and the salary of the previous employee based on employee_id order.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Scanning each row in the employees table once.
• How many times: Once per row, to compute the current and previous salary.

How Execution Grows With Input

As the number of employees grows, the query processes each row one time.

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: "Using LAG makes the query run twice as slow because it looks back at previous rows."

[OK] Correct: The LAG function accesses the previous row efficiently during a single pass, so it does not double the work.

Interview Connect

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

Self-Check

"What if we added a PARTITION BY clause to the LAG function? How would that affect the time complexity?"

Practice

1. What does the SQL LAG function do?

easy

A. Returns the value from the next row in the result set

B. Calculates the sum of all previous rows

C. Returns the value from the previous row in the result set

D. Filters rows based on a condition

Solution

1. Step 1: Understand the purpose of LAG

   The LAG function is used to access data from a previous row relative to the current row in a query result.

2. Step 2: Compare options with definition

   Returns the value from the previous row in the result set correctly states that LAG returns the previous row's value. Other options describe different functions or behaviors.

3. Final Answer:

   Returns the value from the previous row in the result set -> Option C

4. Quick Check:

   LAG = previous row value [OK]

Hint: LAG looks backward one row by default [OK]

Common Mistakes:

• Confusing LAG with LEAD (next row)
• Thinking LAG sums values
• Assuming LAG filters rows

2. Which of the following is the correct syntax to use LAG to get the previous salary ordered by employee ID?

easy

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

B. LAG(salary) BY employee_id

C. LAG(salary) ORDER employee_id

D. LAG(salary) PARTITION BY employee_id

Solution

1. Step 1: Recall LAG syntax

   LAG requires an OVER clause with ORDER BY to define the row order for previous row access.

2. Step 2: Match syntax with options

   LAG(salary) OVER (ORDER BY employee_id) correctly uses OVER (ORDER BY employee_id). The other options misuse syntax or keywords.

3. Final Answer:

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

4. Quick Check:

   LAG syntax = LAG() OVER (ORDER BY ...) [OK]

Hint: Always use OVER with ORDER BY for LAG [OK]

Common Mistakes:

• Omitting OVER clause
• Using PARTITION BY without ORDER BY
• Incorrect keyword order

3. Given the table Employees with columns id and salary, what will this query return?

SELECT id, salary, LAG(salary) OVER (ORDER BY id) AS prev_salary FROM Employees;

Assuming data:
id | salary
1 | 5000
2 | 6000
3 | 5500

medium

A. [{id:1, salary:5000, prev_salary:NULL}, {id:2, salary:6000, prev_salary:5000}, {id:3, salary:5500, prev_salary:6000}]

B. [{id:1, salary:5000, prev_salary:5000}, {id:2, salary:6000, prev_salary:6000}, {id:3, salary:5500, prev_salary:5500}]

C. [{id:1, salary:5000, prev_salary:6000}, {id:2, salary:6000, prev_salary:5500}, {id:3, salary:5500, prev_salary:NULL}]

D. [{id:1, salary:5000, prev_salary:NULL}, {id:2, salary:6000, prev_salary:NULL}, {id:3, salary:5500, prev_salary:NULL}]

Solution

1. Step 1: Understand LAG with ORDER BY id

   LAG(salary) returns the salary from the previous row ordered by id. For id=1, no previous row exists, so NULL is returned.

2. Step 2: Apply LAG to each row

   Row 1: prev_salary = NULL
   Row 2: prev_salary = salary of id=1 = 5000
   Row 3: prev_salary = salary of id=2 = 6000

3. Final Answer:

   [{id:1, salary:5000, prev_salary:NULL}, {id:2, salary:6000, prev_salary:5000}, {id:3, salary:5500, prev_salary:6000}] -> Option A

4. Quick Check:

   LAG returns previous row's value or NULL if none [OK]

Hint: First row prev value is always NULL [OK]

Common Mistakes:

• Assuming first row has previous value
• Mixing up current and previous rows
• Ignoring ORDER BY effect

4. Identify the error in this query:

SELECT id, salary, LAG(salary) ORDER BY id AS prev_salary FROM Employees;

medium

A. AS alias must come before LAG

B. ORDER BY cannot be used inside LAG

C. LAG cannot be used with salary column

D. Missing OVER() clause for LAG function

Solution

1. Step 1: Check LAG function syntax

   LAG requires an OVER() clause to specify ordering. The query uses ORDER BY without OVER(), which is invalid.

2. Step 2: Confirm correct syntax

   The correct syntax is LAG(salary) OVER (ORDER BY id). The query misses OVER(), causing a syntax error.

3. Final Answer:

   Missing OVER() clause for LAG function -> Option D

4. Quick Check:

   LAG needs OVER() with ORDER BY [OK]

Hint: LAG always needs OVER() clause [OK]

Common Mistakes:

• Using ORDER BY without OVER()
• Placing alias before function
• Misunderstanding LAG usage

5. You want to find the difference between each employee's salary and the previous employee's salary ordered by id. Which query correctly calculates this difference?

hard

A. SELECT id, salary, LAG(salary) - salary OVER (ORDER BY id) AS diff FROM Employees;

B. SELECT id, salary, salary - LAG(salary) OVER (ORDER BY id) AS diff FROM Employees;

C. SELECT id, salary, salary - LAG(salary) FROM Employees ORDER BY id;

D. SELECT id, salary, salary - LAG(salary) PARTITION BY id AS diff FROM Employees;

Solution

1. Step 1: Understand the goal

   We want to subtract the previous salary from the current salary, ordered by id.

2. Step 2: Check each option's correctness

   SELECT id, salary, salary - LAG(salary) OVER (ORDER BY id) AS diff FROM Employees; correctly uses LAG(salary) OVER (ORDER BY id) and subtracts it from salary.
   SELECT id, salary, LAG(salary) - salary OVER (ORDER BY id) AS diff FROM Employees; reverses subtraction order.
   SELECT id, salary, salary - LAG(salary) FROM Employees ORDER BY id; misses OVER clause.
   SELECT id, salary, salary - LAG(salary) PARTITION BY id AS diff FROM Employees; misuses PARTITION BY without OVER.

3. Final Answer:

   SELECT id, salary, salary - LAG(salary) OVER (ORDER BY id) AS diff FROM Employees; -> Option B

4. Quick Check:

   Difference = current - previous salary using LAG [OK]

Hint: Use LAG with OVER and subtract current minus previous [OK]

Common Mistakes:

• Forgetting OVER() clause
• Subtracting in wrong order
• Misusing PARTITION BY without OVER