Wedstrijd resultaten (rankings) met degrading scores

[CU2morO]

Ik schets voor jullie de volgende situatie:

Een wedstrijd heeft meerdere categorieën.
Teams kunnen aan 1 of meerdere categorieën meedoen
Er zijn 6 categorieën, maar niet iedere categorie hoeft aanwezig te zijn bij een wedstrijd

De link tussen een categorie en een team is een participatie. Dit is een rijke veel-op-veel relatie, waarbij de behaalde plaats genoteerd wordt

Voorbeeldje:
Team X is 3e geworden in de categorie 'time trial' van wedstrijd Y
Team X is 6e geworden in de categorie 'stunts' van wedstrijd Y

Hieraan is een punten systeem gekoppeld. Iedere behaalde participatie levert een bepaalde hoeveelheid punten op volgens een 'fading scale'. Dit houd in dat een eerste plaats die vorige week behaald is meer punten oplevert dan een eerste plaatst die vorig jaar behaald is.

Het gaat om een schaal van 2 jaar. Alle behaalde resultaten ouder dan dat leveren 0 punten op. De punten 'degradatie' is hardcoded door middel van modifiers over blokken van 8 weken.

Voorbeeldje:
1ste plaats geeft 15 punten.
De eerste 8 weken na het behalen geeft dit 15 punten
Na 8 weken is dit gezakt naar (15*0.835) punten
Na 16 weken is dit gezakt naar (15*0.546) punten
...etc.


Dit complexe systeem werkt aardig in mijn Rails applicatie (lees: PHP website, als je Rails niet kent) en ik kan vrij simpel en direct aan één team zijn huidige score vragen (of zijn score op een willekeurig tijdstip).
Met 1 query heb ik alle participaties en die kan ik stuk voor stuk om hun score vragen op basis van een tijdstip.

Het probleem dat ik echter heb zijn de ranking charts, notabene het belangrijkste deel van de website. Om te kijken welk team de hoogste score heeft, moet ik bovenstaande van ALLE teams uitrekenen. Dit is niet te doen on-the-fly en kost te veel tijd.

Aangezien de scores 1x per week bijgewerkt worden en niet continue, heb ik een lapmiddel geschreven waar ik zelf niet helemaal tevreden mee ben:

Als de beheerder in het weekend zijn scores heeft ingevoerd, kan hij een 'rankings indexer' starten die vervolgens voor ieder team de score gaat berekenen op basis van de laatste maandag van de week. Hiervoor worden per team, per categorie, per week records aangemaakt die ik vervolgens kan sorteren op score (puntenaantal) en in de juiste volgorde weergeven.


Vanwege de grootte van de dataset duurt deze wekelijkse index actie ongeveer 30-45 minuten. Nu is gezien de aard van de website dit geen ramp, maar ik zou het graag op een nettere manier opgelost zien. Een bijkomend probleem is nu dat er verschillende normalisatie regels overtreden worden (redundantie) om de performance reëel te houden.

Ik ben erg benieuwd hoe jullie dit probleem zouden aanpakken! Graag hoor ik jullie creatieve geesten hierover gebogen worden.


[EDIT]
Een schets van de orde van grootte binnen deze dataset:
5000 Teams
1500 Wedstrijden
6 Categorieën

[Knutselsmurf]

Die dataset lijkt mij niet zodanig groot dat de beschreven index-actie zo lang zou moeten duren.
Wellicht dat je database niet goed geoptimaliseerd is, bijvoorbeeld indeces.
Kan je wat meer informatie geven over de gebruikte database, je tabelindeling en de gebruikte indices?

[Niemand_Anders]

Stap 1: Doe zoveel mogelijk op de database zelf. Dus haal niet alle informatie op uit de database om vervolgens een berekening te doen en vervolgens alle data weg te gooien.

Probeer je fading scale zodanig te maken dat je deze doormiddel [1 - (aantal weken / 8 * fadingDescendingScore)] kunt berekenen. Gebruik voor de score een (aparte) column op je database. Vervolgens kun je de totaal score van een team berekenen door simpel alle fading scores op te tellen (select TeamID, sum(currentScore) from scores group by TeamID).

De indexer.php code zou dus eigenlijk alleen update statements moeten bevatten. Op het moment dat de fadingScore niet is te berekenen, zet deze dan in een eigen tabel join met deze tabel om dan alsnog de waarde te krijgen.

[Verwijderd]

Mijn kennis van databases reikt niet zo heel ver, maar misschien heb je er iets aan.
Kan je niet naast de score van een wedstrijd, ook de gewogen score van de wedstrijd opslaan, er is dan wel wat redundantie, maar zo hoef je alleen maar de hele zaak op te tellen, iets wat de DB engine voor je kan doen zonder over-the-top complexe queries te beschrijven. Punt is dan dat je eens in de zoveel tijd die gewogen scores moet hernieuwen, net zoals je nu doet met de totaalscore.

[CU2morO]

Knutselsmurf schreef op donderdag 20 augustus 2009 @ 23:50:
Die dataset lijkt mij niet zodanig groot dat de beschreven index-actie zo lang zou moeten duren.
Wellicht dat je database niet goed geoptimaliseerd is, bijvoorbeeld indeces.
Kan je wat meer informatie geven over de gebruikte database, je tabelindeling en de gebruikte indices?

Het is allemaal nog vrij jong en ik heb nog geen uitgebreide performance tests gedaan. Daardoor heb ik naast de default primary keys (IDs) nog geen extra indexen aangelegd.

Het gaat om een mysql 5.0 database.

Verwijderd schreef op vrijdag 21 augustus 2009 @ 10:00:
Mijn kennis van databases reikt niet zo heel ver, maar misschien heb je er iets aan.
Kan je niet naast de score van een wedstrijd, ook de gewogen score van de wedstrijd opslaan, er is dan wel wat redundantie, maar zo hoef je alleen maar de hele zaak op te tellen, iets wat de DB engine voor je kan doen zonder over-the-top complexe queries te beschrijven. Punt is dan dat je eens in de zoveel tijd die gewogen scores moet hernieuwen, net zoals je nu doet met de totaalscore.

Dat is juist wat ik probeer te voorkomen. Die redundantie en de nood voor een 'update' actie iedere x dagen.
Daarnaast heeft de score die jij in de database (bij een participatie?) op wil schrijven geen betekenis zonder de juiste context in de vorm van een tijdstip. Dat is echter niet het probleem. Op de logica laag kan ik prima aan een participatie vragen hoeveel punten hij waard is op dit moment.

Daarnaast wil ik ook trends e.d. volgen, dus ik wil ook weten wat de score 2 maanden geleden was, en of ik beter / slechter ben geworden

Niemand_Anders schreef op vrijdag 21 augustus 2009 @ 09:47:
Stap 1: Doe zoveel mogelijk op de database zelf. Dus haal niet alle informatie op uit de database om vervolgens een berekening te doen en vervolgens alle data weg te gooien.

Probeer je fading scale zodanig te maken dat je deze doormiddel \[1 - (aantal weken / 8 * fadingDescendingScore)] kunt berekenen. Gebruik voor de score een (aparte) column op je database. Vervolgens kun je de totaal score van een team berekenen door simpel alle fading scores op te tellen (select TeamID, sum(currentScore) from scores group by TeamID).

De indexer.php code zou dus eigenlijk alleen update statements moeten bevatten. Op het moment dat de fadingScore niet is te berekenen, zet deze dan in een eigen tabel join met deze tabel om dan alsnog de waarde te krijgen.

Ik vrees idd dat dat ook een beetje het probleem is. De database queries zelf zorgen niet voor de lange wachttijd. Rails / Ruby is gewoon niet zo netjes met 'grote' datasets (1000+ records) en het in één keer verwerken hiervan.

Misschien moet ik wel mijn toevlucht zoeken naar een slimme stored procedure die dezelfde logica uitvoert, maar dan op database niveau.

[ Voor 71% gewijzigd door CU2morO op 21-08-2009 11:21 ]

[CU2morO]

Ik heb het opgelost door gebruik te maken van een stored function in MYSQL:

code:

DELIMITER $$

CREATE
    FUNCTION degraded_score(p INTEGER, b BOOLEAN, dC DATE, dR DATE) RETURNS DOUBLE
    DETERMINISTIC
    BEGIN
    DECLARE dMod DOUBLE;
    SET dMod = (2 - (FLOOR(ABS(DATEDIFF(dC, dR)) / 56) * 0.1538) );
    SET dMod = IF(dMod < 0,0,dMod);
    
    RETURN dMod * IF(b,5,1) * (CASE p WHEN 1 THEN 15 WHEN 2 THEN 12 WHEN 3 THEN 9 WHEN 4 THEN 7 WHEN 5 THEN 6 WHEN 6 THEN 5 WHEN 7 THEN 4 WHEN 8 THEN 3 WHEN 9 THEN 2 WHEN 10 THEN 1 ELSE 0 END);

    END$$

DELIMITER ;

Een overzicht maken van alle teams uitgezet tegen de categorieën krijg ik op deze manier:

code:

SELECT t.name, cat.name, SUM(degraded_score(p.place, c.bonus, c.date, NOW())) AS score
FROM participations p, teams t, contests c, contest_categories cc, categories cat
WHERE p.concat_id = cc.id AND p.team_id = t.id AND cc.contest_id = c.id AND cc.category_id = cat.id
GROUP BY cc.category_id, p.team_id
ORDER BY cat.id, score DESC

Op deze manier kan alles on the fly in acceptabele tijd opgehaald worden en kan het hele rankings indexer verhaal de deur uit.

Wat ik nu nog zoek is een manier om de 'trend' weer te geven. Hoeveel plaatsen is een team omhoog/omlaag gegaan sinds vorige week. (Zelfde query, met NOW() vervangen door NOW() - 1 week).

Iemand een idee hoe ik bovenstaande functie kan uitbreiden om dit toe te staan?