find 3rd max of salary in a large scale sql table

Question

one of my job interview questions was this. I answered with order by and he ask me even in trillion rows? I accepted my mistake and say I guess there is an option for MAX() maybe!!

in these questions:

Using LIMIT within GROUP BY to get N results per group?

SQL select nth member of group

the trillion rows not considered and performance is low.

but after many search I found that even answered questions are not right for large scale rows. anybody know what is the correct query?

MySQL and SQL Server are different DBMS, which one do you use and What have you tried so far to solve the problem? — Barbaros Özhan, Sep 21 '19 at 12:47
Well, if you could make the salary an indexed column, then it would be faster. — nice_dev, Sep 21 '19 at 12:52
This question is NOT about how to express a query to get the top n. The OP clearly knows how to do that. It is how to address the question of what to do about a trillion rows. — Gordon Linoff, Sep 21 '19 at 13:15

score 1 · Answer 1 · answered Sep 21 '19 at 12:45

1

ORDER BY is fine. You just want an index on the column.

If I had a table with a trillion rows and one of the columns was called salary, I would question the data model or implementation. In any case, it would be in a highly parallel database. Such databases tend to have their quirks, but there are usually methods to extract the value.

Of course, what the interviewer was looking for is more like:

select max(t.col)
from t
where t.column < (select max(t2.col)
                  from t t2
                  where t2.col < (select max(t3.col) from t)
                 );

This would scan the table three times and has no intermediate steps for aggregation or sorting. But in practice, there are likely to be other solutions depending on the database.

answered Sep 21 '19 at 12:45

Gordon Linoff

1,242,037
58
646
786

too long time for trillion rows – Hamid Shariati Sep 21 '19 at 13:13
@HamidShariati . . . I'm not sure what that comment is supposed to mean. Using an index is going to be quite fast. And the subquery requires scanning the table three times, which is much faster than actually sorting the data. – Gordon Linoff Sep 21 '19 at 13:14
but who whould use index for salary? – Hamid Shariati Sep 21 '19 at 13:15
2

@HamidShariati . . . Someone who wanted to find the third largest value. – Gordon Linoff Sep 21 '19 at 13:16

GMB · Answer 2 · 2019-09-21T12:50:12.093

0

This looks like a typical use case for window functions (if supported by the concerned RDBMS), so something like:

SELECT *
FROM (
    SELECT t.*, ROW_NUMBER() OVER(ORDER BY Salary DESC) rn
    FROM mytable t
) x 
WHERE rn = 3

This query would take advantage of an index on column Salary.

Bottom line : there is no way that you can get that result without scanning the whole table and ordering (or aggregating) the results. Indexing is the key to optimize that.

edited Sep 21 '19 at 12:50

answered Sep 21 '19 at 12:44

GMB

216,147
25
84
135

This doesn't actually address the issue with a trillion rows. It would still be doing a sort. – Gordon Linoff Sep 21 '19 at 12:47
Yes, any solution would require scanning + sorting or aggregating. – GMB Sep 21 '19 at 12:53

score 0 · Answer 3 · answered Sep 21 '19 at 12:49

0

In Mysql:-

  SELECT *
       FROM tblSalary t1
       WHERE ( n) = 
       ( 
       SELECT COUNT( t2.columnSalary )
       FROM tblSalary t2
       WHERE t2.columnSalary >= t1.columnSalary
       )

where (n) you can put any number to return highest salary..

answered Sep 21 '19 at 12:49

THE LIFE-TIME LEARNER

1,476
1
8
18

my server hanged in my session :-(. too long time query for trillion rows – Hamid Shariati Sep 21 '19 at 13:11

score 0 · Answer 4 · answered Sep 21 '19 at 15:38

0

according to the mysql documentation: https://dev.mysql.com/doc/refman/8.0/en/partitioning-info.html

I think partitioning is the best way for huge data

answered Sep 21 '19 at 15:38

Hamid Shariati

546
6
18

find 3rd max of salary in a large scale sql table

4 Answers4