Comment implémenter la fonctionnalité "Mayor" de Foursquare - trouvez l'utilisateur avec le meilleur score au cours des N derniers jours?

Question

Dans Foursquare, l'utilisateur qui a obtenu le meilleur score pour une place au cours des N derniers jours se voit attribuer la mairie de ce lieu.

Quel est le moyen le plus efficace de mettre en œuvre cela?

Un utilisateur aurait pu vérifier dans des centaines d'endroits. Pour afficher tous les mairies qui appartiennent à un utilisateur, il serait nécessaire de passer en revue toutes ces centaines de places une par une et de vérifier s'il a le meilleur score au cours des 60 derniers jours pour chaque lieu - cela semble très inefficace.

Existe-t-il un code de magie SQL ou algorithmique pouvant exécuter la tâche rapidement?

MISE À JOUR: J'utilise MySQL et Django

Answer 1

je garderais le « courant majeur » dans la table de lieu, et mettre à jour de temps en temps. Exemple (Je ne sais pas si le modèle de données sont correctes):

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';