Как реализовать функцию «мэра» Foursquare - найдите пользователь с наивысшим баллом в последние n дней?

Question

В Foursquare пользователь, который имеет самый высокий балл для места в последние N Days, награжден мэссией этого места.

Какой самый эффективный способ реализации этого?

Пользователь мог проверить на сотни мест. Чтобы отобразить все мОся, которые принадлежат пользователю, необходимо было бы пройти через все те сотни мест один за другим и проверять, есть ли у него самый высокий балл за последние 60 дней для каждого места - это звучит очень неэффективным.

Есть ли какая-то SQL или алгоритмическая магия, которая могла бы быстро выполнить задачу?

Обновление: я использую mysql и django

Answer 1

Я бы держал «текущий майор» в таблице места, и время от времени обновлял это время. Пример (я понятия не имею, если модель данных верна):

drop table place;
create table place(name varchar(20) primary key, major varchar(20));
insert into place values('NY', null), ('LA', null);
create index idx_p_m on place(major);

drop table visits;
create table visits(user varchar(20), place varchar(20), points int, day int);
create index idx_v_p on visits(place, day desc);
insert into visits values
  ('Ben', 'NY', 1, 100), 
  ('Ben', 'LA', 3, 102), 
  ('Joe', 'NY', 2, 103), 
  ('Joe', 'LA', 1, 104);

-- just to prove this is efficient  
explain  select user from visits v where v.place = 'NY' 
  and day > 90
  group by user 
  order by sum(points) desc 
  limit 1;

update place p set major = 
  (select user from visits v where p.name = v.place 
  and day > 90
  group by user 
  order by sum(points) desc 
  limit 1);

select * from place where major = 'Joe';
select * from place where name = 'LA';