What's the best way to get the 2nd largest element?

Question

What's the best way to get the 2nd largest element?

JChrisCompton

SSCommitted

Points: 1609
More actions
December 19, 2011 at 3:55 pm

#253678

I was asked by a friend "How do you get the second largest element in a table, without returning the largest?"
I said, 'my initial reaction is x'. Which made him happy because that's what he said in his job interview.
Now that I have a little time, I'm trying to figure out how to determine which of the options that occur to me are the 'best'
I wanted to figure out if I was right by looking at the query execution. Either I'm looking in the wrong place or you can't compare it that way.
I tried inserting thousands of rows, but I still get a zero second response.
I don't have a server that I can insert millions of rows on, except my local machine, and I wasn't sure the results would be comparable to a server result anyway.
So below I have created a table and I have the simple solution (which isn't allowed) and three additional tries at answering the problem.
I suspect that the simple solution is best because (with 1 table scan + 1 sort) it consumes the least resources, assuming that is true, what is the second best solution? (the interviewer said, 'okay, now what if you don't want to return the largest row' when my friend proposed using TOP 2)
so here's the code (with the create/fill/drop statements commented out)
/*create table tmp2nd(
pk int identity(1,1),
f1 int);
insert tmp2nd
select 1 union all
select 2 union all
select 3 union all
select 4 union all
select 5 union all
select 6 ;*/
-- Simplest solution, which ISN'T a valid answer to the question
SELECT TOP 2 f1
FROM tmp2nd
ORDER BY f1 DESC
-- First try
SELECT
TOP 1 f1
FROM tmp2nd
WHERE
f1 NOT IN (
SELECT
TOP 1 f1
FROM tmp2nd
ORDER BY f1 DESC)
ORDER BY f1 DESC
--Second try
SELECT
TOP 1 f1
FROM tmp2nd
WHERE
f1 != (
SELECT
TOP 1 f1
FROM tmp2nd
ORDER BY f1 DESC)
ORDER BY f1 DESC
--Third try
declare @topVal int
select @topVal = (SELECT TOP 1 f1 FROM tmp2nd ORDER BY f1 DESC)
SELECT TOP 1 f1
FROM tmp2nd
WHERE f1 != @topVal
ORDER BY f1 DESC
/*
drop table tmp2nd
*/
Is there a better solution than my three?
Thanks,
-Chris C.

Viewing 5 posts - 1 through 4 (of 4 total)

You must be logged in to reply to this topic. Login to reply

SQLRNNR SSC Guru Points: 281334 More actions · Answer 1

Try a windowed function ( such as ROW_NUMER()) in a cte. Order that windowed function by desc. Then select row_number 2 from that result set.

Play with it a bit and see if you can get it. If not post back and we can create a solution based on your needs.

Jason...AKA CirqueDeSQLeil
_______________________________________________
I have given a name to my pain...MCM SQL Server, MVP
SQL RNNR
Posting Performance Based Questions - Gail Shaw[/url]
Learn Extended Events

Michael Valentine Jones SSC Guru Points: 64818 More actions · Answer 2

SELECT TOP 1

a.f1

FROM

(

SELECT TOP 2

b.f1

FROM

tmp2nd b

ORDER BY

b.f1 ASC

) a

ORDER BY

a.f1 DESC

SQLRNNR SSC Guru Points: 281334 More actions · Answer 3

Nice answer Michael.

Jason...AKA CirqueDeSQLeil
_______________________________________________
I have given a name to my pain...MCM SQL Server, MVP
SQL RNNR
Posting Performance Based Questions - Gail Shaw[/url]
Learn Extended Events

Jeff Moden SSC Guru Points: 1004406 More actions · Answer 4

Michael Valentine Jones (12/19/2011)
SELECT TOP 1 a.f1 FROM ( SELECT TOP 2 b.f1 FROM tmp2nd b ORDER BY b.f1 ASC ) a ORDER BY a.f1 DESC

Heh... on of my favorites for "paging" code. 🙂 You left out @LinesPerPage = 1, @Page = 2. 😀

--Jeff Moden

RBAR is pronounced "ree-bar" and is a "Modenism" for Row-By-Agonizing-Row.
First step towards the paradigm shift of writing Set Based code:
________Stop thinking about what you want to do to a ROW... think, instead, of what you want to do to a COLUMN.

Change is inevitable... Change for the better is not.

Helpful Links:
How to post code problems
How to Post Performance Problems
Create a Tally Function (fnTally)