NTH_VALUE function in SQL - Time & Space Complexity

Time Complexity: NTH_VALUE function

O(n log n)

Understanding Time Complexity

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

Specifically, how does the number of rows affect the work done by this function?

Scenario Under Consideration

Analyze the time complexity of the following SQL query using NTH_VALUE.

SELECT employee_id,
       department_id,
       salary,
       NTH_VALUE(salary, 3) OVER (PARTITION BY department_id ORDER BY salary DESC) AS third_highest_salary
FROM employees;
    

This query finds the third highest salary in each department for every employee row.

Identify Repeating Operations

Look for repeated work inside the query.

• Primary operation: For each department, the query orders all salaries and finds the 3rd highest.
• How many times: This ordering and value retrieval happens once per department, but the result is shown for every employee in that department.

How Execution Grows With Input

As the number of employees grows, the work to order salaries in each department grows too.

Input Size (n)	Approx. Operations
10	Ordering small groups, quick retrieval
100	More sorting per department, more rows to process
1000	Sorting larger groups, more repeated retrievals

Pattern observation: The sorting work grows faster than the number of rows because sorting is more costly than just scanning.

Final Time Complexity

Time Complexity: O(n log n)

This means the time grows a bit faster than the number of rows because sorting is involved.

Common Mistake

[X] Wrong: "NTH_VALUE just picks a value directly, so it runs in constant time regardless of data size."

[OK] Correct: The function needs to sort the data within each partition first, which takes more time as data grows.

Interview Connect

Understanding how window functions like NTH_VALUE scale helps you explain query performance clearly and shows you know what happens behind the scenes.

Self-Check

What if we changed the PARTITION BY clause to remove it? How would the time complexity change?

Practice

1. What does the SQL function NTH_VALUE(column, n) do when used with an OVER() clause?

easy

A. Returns the maximum value in the column.

B. Returns the total count of rows in the table.

C. Returns the value at the nth position in the ordered set of rows.

D. Returns the first value in the column without ordering.

Solution

1. Step 1: Understand the function purpose

   The NTH_VALUE function is designed to return a value from a specific position (n) in an ordered set of rows.

2. Step 2: Recognize the role of OVER()

   The OVER() clause defines how rows are ordered and grouped, which is essential for NTH_VALUE to pick the correct nth value.

3. Final Answer:

   Returns the value at the nth position in the ordered set of rows. -> Option C

4. Quick Check:

   NTH_VALUE returns nth value in order [OK]

Hint: NTH_VALUE picks the nth row's value after ordering [OK]

Common Mistakes:

• Confusing NTH_VALUE with aggregate functions like COUNT or MAX
• Ignoring the ordering inside OVER() clause
• Assuming it returns the nth row without ordering

2. Which of the following is the correct syntax to get the 3rd highest salary using NTH_VALUE in SQL?

easy

A. SELECT NTH_VALUE(salary, 3) OVER (PARTITION BY salary) FROM employees;

B. SELECT NTH_VALUE(salary, 3) FROM employees ORDER BY salary DESC;

C. SELECT NTH_VALUE(3, salary) OVER (ORDER BY salary DESC) FROM employees;

D. SELECT NTH_VALUE(salary, 3) OVER (ORDER BY salary DESC) FROM employees;

Solution

1. Step 1: Check the function parameters

   The correct order is NTH_VALUE(column, n), so salary first, then 3.

2. Step 2: Verify the OVER clause

   Ordering by salary descending (ORDER BY salary DESC) ensures the highest salaries come first, so the 3rd highest is the 3rd row.

3. Final Answer:

   SELECT NTH_VALUE(salary, 3) OVER (ORDER BY salary DESC) FROM employees; -> Option D

4. Quick Check:

   Syntax: NTH_VALUE(column, n) OVER (ORDER BY col DESC) [OK]

Hint: NTH_VALUE(column, n) needs OVER with ORDER BY for ranking [OK]

Common Mistakes:

• Swapping parameters inside NTH_VALUE
• Missing OVER() clause or ORDER BY inside it
• Using PARTITION BY incorrectly without ORDER BY

3. Given the table Scores with columns student and score, what will this query return?

SELECT student, score, NTH_VALUE(score, 2) OVER (ORDER BY score DESC) AS second_highest FROM Scores;

medium

A. Each row shows the student's score and the 2nd highest score overall repeated.

B. Each row shows the student's score and their own 2nd highest score.

C. The query returns only the row with the 2nd highest score.

D. The query returns an error because NTH_VALUE needs PARTITION BY.

Solution

1. Step 1: Understand the window function without PARTITION

   Since there is no PARTITION BY, the entire table is treated as one group ordered by score descending.

2. Step 2: Effect of NTH_VALUE(score, 2) OVER (ORDER BY score DESC)

   This returns the 2nd highest score value from the whole table, repeated for every row.

3. Final Answer:

   Each row shows the student's score and the 2nd highest score overall repeated. -> Option A

4. Quick Check:

   NTH_VALUE without PARTITION repeats nth value for all rows [OK]

Hint: Without PARTITION, NTH_VALUE repeats same nth value for all rows [OK]

Common Mistakes:

• Thinking NTH_VALUE filters rows to nth only
• Assuming PARTITION BY is mandatory
• Confusing NTH_VALUE with ROW_NUMBER or RANK

4. Identify the error in this SQL query:

SELECT employee_id, NTH_VALUE(salary, 1) OVER (PARTITION BY department_id) FROM employees;

medium

A. Missing ORDER BY clause inside OVER() causes error.

B. NTH_VALUE cannot be used with PARTITION BY.

C. The function parameters are in wrong order.

D. No error; query is correct.

Solution

1. Step 1: Check the OVER() clause requirements

   NTH_VALUE requires an ORDER BY clause inside OVER() to define the row order for nth value selection.

2. Step 2: Identify missing ORDER BY

   The query uses PARTITION BY but lacks ORDER BY, which causes a syntax error.

3. Final Answer:

   Missing ORDER BY clause inside OVER() causes error. -> Option A

4. Quick Check:

   NTH_VALUE needs ORDER BY in OVER() [OK]

Hint: Always include ORDER BY inside OVER() with NTH_VALUE [OK]

Common Mistakes:

• Omitting ORDER BY inside OVER()
• Thinking PARTITION BY alone orders rows
• Swapping function parameters

5. You want to find the 2nd earliest order date for each customer in the Orders table with columns customer_id and order_date. Which query correctly uses NTH_VALUE to achieve this?

hard

A. SELECT customer_id, order_date, NTH_VALUE(order_date, 2) FROM Orders GROUP BY customer_id;

B. SELECT customer_id, order_date, NTH_VALUE(order_date, 2) OVER (PARTITION BY customer_id ORDER BY order_date ASC) AS second_earliest FROM Orders;

C. SELECT customer_id, order_date, NTH_VALUE(order_date, 2) OVER (ORDER BY customer_id, order_date ASC) AS second_earliest FROM Orders;

D. SELECT customer_id, NTH_VALUE(order_date, 2) FROM Orders ORDER BY order_date ASC;

Solution

1. Step 1: Use PARTITION BY to group by customer

   To find the 2nd earliest order per customer, partition rows by customer_id.

2. Step 2: Order each partition by order_date ascending

   Ordering by order_date ASC ensures earliest dates come first.

3. Step 3: Apply NTH_VALUE to get 2nd earliest date

   NTH_VALUE with n=2 picks the 2nd row's order_date in each partition.

4. Final Answer:

   SELECT customer_id, order_date, NTH_VALUE(order_date, 2) OVER (PARTITION BY customer_id ORDER BY order_date ASC) AS second_earliest FROM Orders; -> Option B

5. Quick Check:

   Partition by customer, order by date ASC, NTH_VALUE(2) [OK]

Hint: Partition by group, order ascending, then NTH_VALUE(n) [OK]

Common Mistakes:

• Missing PARTITION BY to group customers
• Ordering by wrong columns or descending order
• Using NTH_VALUE without OVER() clause