SQL Leetcode 176: Runtime of Second Highest Salary

Hi everyone!

Context and Approach:
I was working on SQL Leetcode #176: Second Highest Salary and I implemented it via a Subquery using the ranking window function. I thought this would be the best approach because I could theoretically find the n-th ranking by simply changing my WHERE condition.

Question:
I was wondering if anyone understand the differences in runtime between these solutions and why it is so
Screen Shot 2020-07-10 at 2.53.39 PM
The image above is where I use DENSE_RANK() because there is a corner case where there are more than one (n-1) higher ranks. This is the second fastest solution

Screen Shot 2020-07-10 at 2.53.19 PM
In this version, SELECT DISTINCT is used with plain-old RANK(). It is the slowest.

Screen Shot 2020-07-10 at 2.53.59 PM
This query combines SELECT DISTINCT As well as DENSE_RANK(). It is the fastest.

Why?

Thanks for posting a great question. A couple of things I noticed:

  • The runtime on Leetcode shows different numbers even if you run the same code a few times. The absolute runtime depends not only on algorithmic complexity but also on system configs and the state of your computer.

  • Your subqueries can compromise the algorithm runtime (your 1st and 3rd vs the 2nd) e.g. like using DISTINCT multiple times or when you don’t need it.

  • Keep your queries simpler if they don’t require complex solution. Your solution is unnecessarily complex (instead of creating ranks, you can create a view table and OFFSET by that the row_you_want -1). See the example code of one of the solutions:

SELECT
IFNULL(
(SELECT DISTINCT Salary
FROM Employee
ORDER BY Salary DESC
LIMIT 1 OFFSET 1),
NULL) AS SecondHighestSalary

or check this out (although this doesn't take care of NULL values): 

![Screen Shot 2020-07-13 at 10.21.25 PM|690x263](upload://aBAdXZGnFXkFuksLmBFrPp1Y2qS.png) 

In short, don't worry about the runtime complexity much but instead focus on writing simpler, neater, more understandable queries.