Home > OS >  Solution without LIMIT
Solution without LIMIT

Time:03-08

I have a table like this (from LeetCode):

requester_id accepter_id accept_date
1 2 2016/06/03
1 3 2016/06/08
2 3 2016/06/08
3 4 2016/06/09

Find the people who have the most friends and the most friends number.

Expected Output:

id num
3 3

I wrote this query for the answer and it works:

select a.f as "id", count(a.f) as "num"
from (
    select requester_id as f
    from requestaccepted
    union all
    select accepter_id as f
    from requestaccepted ) a
group by a.f
order by count(a.f) desc
limit 1;

I am not 100% convinced using limit 1 is the best solution.

What should be an alternative/better option?

CodePudding user response:

LIMIT 1 after ORDER BY is just fine to get a single winner:

SELECT a.id, count(*) AS num
FROM  (
   SELECT requester_id AS id FROM requestaccepted
   UNION ALL
   SELECT accepter_id  AS id FROM requestaccepted
   ) a
GROUP  BY a.id
ORDER  BY num DESC
LIMIT  1;

You get an arbitrary pick if there are multiple winners. You might add additional ORDER BY expressions to get a deterministic pick.

If you must avoid LIMIT / FETCH FIRST (really?) the window function row_number() is a (more expensive!) alternative:

SELECT id, num
FROM  (
   SELECT a.id, count(*) AS num
        , row_number() OVER (ORDER BY count(*) DESC) AS rn
   FROM  (
      SELECT requester_id AS id FROM requestaccepted
      UNION ALL
      SELECT accepter_id  AS id FROM requestaccepted
      ) a
   GROUP BY a.id
   ) sub
WHERE  rn = 1;

To get all IDs that tie for the win, just add WITH TIES. Must use standard SQL syntax FETCH FIRST 1 ROWS instead of the Postgres shortcut LIMIT 1 to add the clause.

SELECT a.id, count(*) AS num
FROM  (
   SELECT requester_id AS id FROM requestaccepted
   UNION ALL
   SELECT accepter_id  AS id FROM requestaccepted
   ) a
GROUP  BY a.id
ORDER  BY count(*) DESC
FETCH  FIRST 1 ROWS WITH TIES;

No additional ORDER BY expressions, that would resolve ties.

If you must avoid LIMIT / FETCH FIRST (really?) the window function rank() is a (more expensive!) alternative:

SELECT id, num
FROM  (
   SELECT a.id, count(*) AS num
       , rank() OVER (ORDER BY count(*) DESC) AS rnk
   FROM  (
      SELECT requester_id AS id FROM requestaccepted
      UNION ALL
      SELECT accepter_id  AS id FROM requestaccepted
      ) a
   GROUP  BY a.id
   ) sub
WHERE  rnk = 1
ORDER  BY id; -- optional

db<>fiddle here - with extended test case to show a tie

See:

CodePudding user response:

As you just need friends with highest count, you can directly get count of accepted id, and max of that will work.

select  id ,max(num) from
(
select accepter_id id ,count(*) num from requestaccepted
group by accepter_id 
) a

CodePudding user response:

Another interesting way could be using Join Lateral with Limit

Schema and insert statements:

 create table requestaccepted(requester_id int, accepter_id int, accept_date date);
 insert into requestaccepted values(1,  2,  '2016/06/03');
 insert into requestaccepted values(1,  3,  '2016/06/08');
 insert into requestaccepted values(2,  3,  '2016/06/08');
 insert into requestaccepted values(3,  4,  '2016/06/09');

Output:

 SELECT id,count(*)num
 FROM requestaccepted r
 JOIN LATERAL (VALUES(r.requester_id),(r.accepter_id)) s(id) ON TRUE
 group by id
 order by num desc
 Limit 1 

Output:

id num
3 3

db<>fiddle here

  • Related