Sunday, July 6, 2008

Interesting SQL Query

Write a SQL query to compute the Nth Maximum Salary

Lets get started with an easy one.
Write a SQL query to compute the 2nd Maximum Salary

select Max(Salary)
from Employee
where Salary != (select Max(Salary) from Employee);

To see how it works, you need to understand how a nested query is executed:
First the innermost (nested) query is executed and its result is placed in a temporary table, then the outer query is executed which uses that result.

So if you have to find the 3rd Maximum Salary, you could extend the previous query by increasing one more level of nesting. And so on.

A more interesting and simpler way to find Nth maximum salary would be the following correlated subquery

select * from Employee E1 where
(N-1) = (select Count(Distinct(E2.Salary))
from Employee E2
where E2.Salary > E1.Salary );

Let us now see how this correlated query works:
For each tuple of table Employee, the inner query is executed once and
the result is now stored in some temporary form which is used by the
outer query.

Thus, this correlated query takes O(n*n) time (quadratic time) as compared to linear time {O(n+n) = O(n)} of nested queries but it is still better than nesting the query n number of times as that would result in cumbersome code. However, both would take equal time. :-)

The best way to understand the query is to dry run it on some sample data and some value for N

1 comment:

Anuj said...

That was an amazing code.. I could not however get how it really works.. will dig into it for sure..