How to reduce N-th highest salary query complexity in Mysql?

Question

I think sorting salary table data in desc and putting limit and offset like below query will give you result but sorting thousands of records will affect the performance also.

select salary from employee order by salary desc limit (n-1), 1;

So my question is how can I reduce the complexity here? Please help.

Answer 1

ORDER BY implies sorting. However, depending on the rest of the query and the available indexes, it may be possible for the Optimizer to skip the sort. (When ordering matters, use ORDER BY and let the Optimizer eliminate it when it can.)

OFFSET (the first number in a LIMIT with two numbers) is implemented by fetching all those rows and tossing them. Afterwards, the fetches the LIMIT rows ("1" in your case) to actually deliver to you. That is, OFFSET is not cheap and is not helped by an index.

If you need the 100th row of a list, based on some sort order, your query is optimal. Sorting "thousands" of rows is usually not a problem. ("Billions" would be a problem.)

A common mistake is to "paginate" using OFFSET:

SELECT ... ORDER BY .. LIMIT  0, 10  -- page 1
SELECT ... ORDER BY .. LIMIT 10, 10  -- page 2
SELECT ... ORDER BY .. LIMIT 20, 10  -- page 3
(etc)

This is "quadratic" performance. That is, not good.

If the sort cannot be avoided, then each of those queries will read the entire dataset.

If the Optimizer can use an index to avoid the sort, then the first query reads 10 rows; the second reads 20, then 30, etc. Notice how it gets slower and slower.

(The optimization of pagination involves "remembering where you left off".)

Is your query really about salaries and fetching only the nth and only doing it once? Or is that an over-simplification of the real use case? There may be other tricks if you show us the 'real' query.

Big-O:

Sort N rows: O(N*log N)
OFFSET N: O(N)
LIMIT N: O(N)
SELECT N rows: O(N)
Paginate all pages (P items per page) using Offset, worst case: O((N/P)NlogN)
Pagination with 'left off': O(N)