FIRST_VALUE and LAST_VALUE in PostgreSQL - Time & Space Complexity

Time Complexity: FIRST_VALUE and LAST_VALUE

O(n log n)

Understanding Time Complexity

We want to understand how the time to get the first or last value in a group grows as the data size increases.

How does the database handle these window functions when the input gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

SELECT
  department,
  employee_id,
  salary,
  FIRST_VALUE(salary) OVER (PARTITION BY department ORDER BY salary DESC) AS highest_salary,
  LAST_VALUE(salary) OVER (PARTITION BY department ORDER BY salary DESC ROWS BETWEEN UNBOUNDED PRECEDING AND UNBOUNDED FOLLOWING) AS lowest_salary
FROM employees;
    

This query finds the highest and lowest salary per department using FIRST_VALUE and LAST_VALUE window functions.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Scanning and ordering rows within each department group.
• How many times: Once per row, but ordering happens per group which depends on group size.

How Execution Grows With Input

As the number of rows grows, the database must sort each department's rows to find first and last values.

Input Size (n)	Approx. Operations
10	About 10 sorting steps within groups
100	Sorting grows, more steps per group
1000	Sorting cost increases roughly with n log n per group

Pattern observation: Sorting cost grows faster than the number of rows because ordering is needed per group.

Final Time Complexity

Time Complexity: O(n log n)

This means the time to compute first and last values grows a bit faster than the number of rows because sorting is involved.

Common Mistake

[X] Wrong: "FIRST_VALUE and LAST_VALUE just pick values instantly without extra work."

[OK] Correct: The database must order rows within each group first, which takes extra time especially as data grows.

Interview Connect

Understanding how window functions like FIRST_VALUE and LAST_VALUE scale helps you explain query performance clearly and shows you know how databases handle grouped data.

Self-Check

What if we removed the ORDER BY clause inside the window function? How would the time complexity change?

Practice

1. What does the FIRST_VALUE function do in PostgreSQL?

easy

A. Returns the first value in a sorted group of rows.

B. Returns the last value in a sorted group of rows.

C. Returns the average value of a column.

D. Returns the total count of rows.

Solution

1. Step 1: Understand the purpose of FIRST_VALUE

   FIRST_VALUE returns the first value in a sorted window or group of rows.

2. Step 2: Compare with other options

   Options B, C, and D describe different functions or aggregates, not FIRST_VALUE.

3. Final Answer:

   Returns the first value in a sorted group of rows. -> Option A

4. Quick Check:

   FIRST_VALUE = first value in sorted rows [OK]

Hint: FIRST_VALUE always picks the first row's value in order [OK]

Common Mistakes:

• Confusing FIRST_VALUE with LAST_VALUE
• Thinking it returns an aggregate like sum or count
• Ignoring the sorting order in the window

2. Which of the following is the correct syntax to get the last value of a column score ordered by date using LAST_VALUE in PostgreSQL?

easy

A. SELECT LAST_VALUE(score) FROM results ORDER BY date;

B. SELECT LAST_VALUE(score) OVER (ORDER BY date ROWS BETWEEN UNBOUNDED PRECEDING AND UNBOUNDED FOLLOWING) FROM results;

C. SELECT LAST_VALUE(score) OVER (PARTITION BY date) FROM results;

D. SELECT LAST_VALUE(score) OVER (ORDER BY date) FROM results;

Solution

1. Step 1: Understand LAST_VALUE default frame

   LAST_VALUE by default looks from current row to end, so it may not return the last value overall without framing.

2. Step 2: Use explicit window frame to get true last value

   Adding ROWS BETWEEN UNBOUNDED PRECEDING AND UNBOUNDED FOLLOWING ensures the entire partition is considered.

3. Final Answer:

   SELECT LAST_VALUE(score) OVER (ORDER BY date ROWS BETWEEN UNBOUNDED PRECEDING AND UNBOUNDED FOLLOWING) FROM results; -> Option B

4. Quick Check:

   LAST_VALUE needs full frame to get last value [OK]

Hint: Add full window frame to LAST_VALUE for correct last row [OK]

Common Mistakes:

• Omitting window frame causing wrong last value
• Using PARTITION BY incorrectly
• Using LAST_VALUE without OVER() clause

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

SELECT region, month, revenue, FIRST_VALUE(revenue) OVER (PARTITION BY region ORDER BY month) AS first_rev FROM sales ORDER BY region, month;

medium

A. The total revenue summed for each region.

B. The revenue of the last month for each region repeated on every row of that region.

C. The revenue of the first month for each region repeated on every row of that region.

D. The revenue of the current month only.

Solution

1. Step 1: Analyze FIRST_VALUE with PARTITION and ORDER BY

   FIRST_VALUE(revenue) OVER (PARTITION BY region ORDER BY month) returns the first revenue value per region ordered by month.

2. Step 2: Understand output per row

   For each row in a region, the first month's revenue is repeated as first_rev.

3. Final Answer:

   The revenue of the first month for each region repeated on every row of that region. -> Option C

4. Quick Check:

   FIRST_VALUE repeats first row's value per partition [OK]

Hint: FIRST_VALUE repeats first sorted value per group [OK]

Common Mistakes:

• Thinking it returns last value instead
• Assuming it sums or aggregates
• Ignoring PARTITION BY effect

4. You wrote this query but it returns unexpected results:

SELECT employee_id, salary, LAST_VALUE(salary) OVER (ORDER BY employee_id) AS last_sal FROM employees;

What is the likely cause?

medium

A. LAST_VALUE cannot be used without PARTITION BY clause.

B. ORDER BY employee_id is invalid in window functions.

C. salary column must be aggregated with SUM before LAST_VALUE.

D. LAST_VALUE needs a window frame to include all rows; default frame causes wrong output.

Solution

1. Step 1: Recall LAST_VALUE default frame behavior

   By default, LAST_VALUE looks from current row to end, so it may not return the last row's value overall.

2. Step 2: Identify missing window frame

   Without specifying ROWS BETWEEN UNBOUNDED PRECEDING AND UNBOUNDED FOLLOWING, the last value is not the last row's value.

3. Final Answer:

   LAST_VALUE needs a window frame to include all rows; default frame causes wrong output. -> Option D

4. Quick Check:

   LAST_VALUE requires full frame for correct last row [OK]

Hint: Add full frame to LAST_VALUE to fix wrong results [OK]

Common Mistakes:

• Assuming ORDER BY alone fixes LAST_VALUE
• Thinking PARTITION BY is mandatory
• Trying to aggregate salary before LAST_VALUE

5. You want to find the first and last sale amount for each customer ordered by sale date. Which query correctly returns both values per customer in PostgreSQL?

hard

A. SELECT customer_id, sale_date, sale_amount, FIRST_VALUE(sale_amount) OVER (PARTITION BY customer_id ORDER BY sale_date), LAST_VALUE(sale_amount) OVER (PARTITION BY customer_id ORDER BY sale_date ROWS BETWEEN UNBOUNDED PRECEDING AND UNBOUNDED FOLLOWING) FROM sales;

B. SELECT customer_id, sale_date, sale_amount, FIRST_VALUE(sale_amount), LAST_VALUE(sale_amount) FROM sales GROUP BY customer_id;

C. SELECT customer_id, sale_date, sale_amount, FIRST_VALUE(sale_amount) OVER (ORDER BY sale_date), LAST_VALUE(sale_amount) OVER (ORDER BY sale_date) FROM sales;

D. SELECT customer_id, sale_date, sale_amount, MIN(sale_amount) OVER (PARTITION BY customer_id), MAX(sale_amount) OVER (PARTITION BY customer_id) FROM sales;

Solution

1. Step 1: Use FIRST_VALUE with PARTITION and ORDER BY

   FIRST_VALUE(sale_amount) OVER (PARTITION BY customer_id ORDER BY sale_date) gets first sale per customer.

2. Step 2: Use LAST_VALUE with full window frame

   LAST_VALUE needs ROWS BETWEEN UNBOUNDED PRECEDING AND UNBOUNDED FOLLOWING to get last sale per customer.

3. Step 3: Check other options

   SELECT customer_id, sale_date, sale_amount, FIRST_VALUE(sale_amount), LAST_VALUE(sale_amount) FROM sales GROUP BY customer_id; lacks OVER() and ORDER BY, C lacks PARTITION BY, D uses MIN/MAX which is different.

4. Final Answer:

   SELECT customer_id, sale_date, sale_amount, FIRST_VALUE(sale_amount) OVER (PARTITION BY customer_id ORDER BY sale_date), LAST_VALUE(sale_amount) OVER (PARTITION BY customer_id ORDER BY sale_date ROWS BETWEEN UNBOUNDED PRECEDING AND UNBOUNDED FOLLOWING) FROM sales; -> Option A

5. Quick Check:

   Combine FIRST_VALUE and LAST_VALUE with proper framing [OK]

Hint: Use full frame for LAST_VALUE with PARTITION and ORDER BY [OK]

Common Mistakes:

• Omitting window frame for LAST_VALUE
• Using aggregate functions instead of window functions
• Not partitioning by customer_id