Efficiente bereking van plaats in top xxx

[Verwijderd]

Het gaat hier dus niet om het bouwen van een top 100 of het opsplitsen van de top 100 in pagina's

Op de pagina van de gebruiker staat vermeld op welke plek hij/zij staat in de top 100, opgebouwd uit het aantal punten dat een gebruiker heeft.

De query hiervoor is niet al te moeilijk:

code:

SELECT count(x) + 1 
FROM table 
WHERE aantal_punten > [aantal_punten_van_user]

Het probleem hiermee is dat het voor 100 of 10.000 gebruikers een niet al te zware query is.
Bij meer gebruikers is de query zwaarder naarmate de gebruiker lager in de ranglijst staat (er moeten meer rows ge-'count' worden).
Dit levert een gigantische load op de database op.

Tot gisteren cachte ik het resultaat van een gebruiker voor 3 minuten. Dit bleek niet meer afdoende.
Vandaag ben ik overgeschakeld op het cachen per aantal piunten.
Op die manier hoef ik de plek in de ranglijst maar eenmaal te bereken voor iedereen die 10, 20 ,30 (etc) punten heeft. (dit resultaat wordt ook gecached voor 3 minuten)
Dit levert echter nog steeds een CPU-gebruik van 40% op (op een dual CPU server)
Logischerwijs is dit onacceptabel.

Ik heb nu 2 mogelijkheden... deze plek in de ranglijst verwijderen van de site of het geheel zwaar optimaliseren.
De query gebruikt een index (resultaat EXPLAIN is in MySQL 'Using where; Using index').

Ik kan natuurlijk een ranglijst maken waar iedereen in voorkomt en ELKE gebruiker een update naar de juiste positie geven per x minuten. Ik vrees echter dt dit bij 10.000-en gebruikers nog veel zwaarder is.

Is mijn huidige manier een efficiente manier van berekenen van de plek van een gebruiker in de ranglijst? Of heeft iemand nog tips voor mij om e.e.a. efficienter aan te pakken (behalve het langer cachen van de resultaten)

[jvdmeer]

Ik zou het onder MS-SQL als volgt doen:
maak storedproc met volgende inhoud:
- maak lege tabel met identity kolom.
- vul deze middels een select * from x order by punten

Als de tabel te oud wordt, gooi je 'm weg en bouw je 'm opnieuw op. Zoals je ziet zit er bij dezemethode geen dure count(*) in per gebruiker.

/edit: op de SP na, zou dit binnen MySql ook moeten werken.

[ Voor 12% gewijzigd door jvdmeer op 13-01-2005 18:28 ]

[Verwijderd]

werkt misschien LIMIT (getal) om de load wat kleiner te maken, of probeer anders te zoeken dmv. een "simpelere" berekening?

[justmental]

Kun je niet een 'rownum' achtige oplossing gebruiken en zo voor iedereen in een keer de rank bepalen?

code:

mysql> SET @rownum := 0;
mysql> SELECT @rownum := @rownum + 1 AS rank, score
-> FROM t ORDER BY score DESC;

[T-MOB]

Misschien is het een idee om de rank te bepalen als er punten worden toegevoegd. Ik heb geen idee hoe (en hoe vaak) er punten worden toegekend. Maar het lijkt me dat dat minder vaak gebeurt dan het opvragen van de rank...

[Verwijderd]

jvdmeer, dat vind ik een interessante oplossing.
Ik heb er al wel eens aan gedacht maar nooit gekeken hoe zwaar zoiets zou zijn. Het nadeel wat je natuurlijk wel hebt is dat je de gehele user-tabel gaat sorteren en dan inserten. Bij (op dit moment) >100.000 users vraag ik me af of dit haalbaar is.
Ik ga er echter zeker eens naar kijken.

T-MOB schreef op donderdag 13 januari 2005 @ 19:02:
Misschien is het een idee om de rank te bepalen als er punten worden toegevoegd. Ik heb geen idee hoe (en hoe vaak) er punten worden toegekend. Maar het lijkt me dat dat minder vaak gebeurt dan het opvragen van de rank...

Maar na een tijdje is die plek niet meer correct omdat er natuurlijk ook op anderen wordt gestemd..

[grhmpf]

Als ik het goed begrijp hoef je alleen maar de top 100 van
"select distinct user, punten from users order by punten" in een tabel te hebben. Dus door die query te limiten vul je de top 100 tabel. Als punten geindexeerd is moet dat toch goed performen. Het nummertje 1 t/m 100 zet je er dan bij tijdens het printen van de results. Het enige probleem kan nog de sort zijn op punten, dus het hangt er vanaf hoe veel tol dat eist.

edit: en de tabel-vul-query doe je opnieuw na een update van punten van een user (of je checkt elke x minuten of de tabel opnieuw gevuld moet worden).

[ Voor 17% gewijzigd door grhmpf op 13-01-2005 19:22 ]

[T-MOB]

Verwijderd schreef op donderdag 13 januari 2005 @ 19:12:
Maar na een tijdje is die plek niet meer correct omdat er natuurlijk ook op anderen wordt gestemd..

Daar kun je toch voor corrigeren...

Je voegt de punten voor user X toe, vraagt de huidige rank en het nieuwe puntenaantal van deze user op. Vervolgens geef je alle users met een hogere rank maar een lager puntenaantal een -1 op hun rank. Met het aantal affected rows hoog je de rank van user X op. Lijkt me redelijk waterdicht.

[Janoz]

Waneer je een index op punten legt zal je initiele query een stuk sneller gaan lijkt me.

[justmental]

Janoz schreef op donderdag 13 januari 2005 @ 19:42:
Waneer je een index op punten legt zal je initiele query een stuk sneller gaan lijkt me.

Zal niet veel schelen omdat gemiddeld de helft van de tabel gelezen moet worden.
Dat wordt dus een grote range scan.
het ligt een beetje aan het aantal velden in de tabel of dit zin heeft.

[Janoz]

Nee hoor, doordat een index in boomvorm wordt opgeslagen kunnen hele stukken overgeslagen worden. Daardoor veranderd het zoeken naar het aantal van een O(n) naar een O(log(n)) operatie.

[Verwijderd]

T-mob, ik heb inderdaad een zelfde soort systeem bedacht vannacht.
Echter wilde ik gaan werken met een extra tabel (met punten, rank) om het aantal updates op de vrij grote user tabel niet te groot te laten worden EN omdat iedereen met puntenaantal X ook dezelfde rank heeft.

Iemand krijg x punten, dan geef je elke punten-rank-row die => oude aantal punten EN < nieuwe aantal punten een -1 op de rank. Omdat je max 10 punten kan geven update je hiermee maximaal 10 rows.

Janoz, ik heb een index op de punten (om precies te zijn op status, site, punten en in die volgorde is de where ook). Omdat het aantal punten voor een user niet uniek is wordt zo'n index IMO niet in een boomstructuur opgeslagen.

[edie]

Wat scheelt, is de +1 achter count(*) weghalen. Waarschijnlijk veroorzaakt dit ook je grote CPU load.

Ter verglijking:
10 miljoen records. ap is een variabele met een random waarde tussen 0 en 1000

code:

SELECT COUNT(*) + 1 AS aa FROM ranglijst WHERE aantal_punten > ap INTO CURSOR x

Duur: 11.093 seconden

code:

SELECT COUNT(*) AS aa FROM ranglijst WHERE aantal_punten > ap INTO CURSOR x

Duur: 0,738 seconden

[ACM]

Janoz schreef op donderdag 13 januari 2005 @ 20:14:
Nee hoor, doordat een index in boomvorm wordt opgeslagen kunnen hele stukken overgeslagen worden. Daardoor veranderd het zoeken naar het aantal van een O(n) naar een O(log(n)) operatie.

Er moet nog steeds gekeken worden hoeveel er dan groter waren en het lijkt me niet dat dat in een index goed bij te houden is
't Zoeken van de goede plek wordt idd O(log(n)), maar het tellen wordt dan n / 2 en geen log(n)

[ Voor 11% gewijzigd door ACM op 14-01-2005 13:18 ]

[ACM]

eddie19 schreef op vrijdag 14 januari 2005 @ 13:03:
Wat scheelt, is de +1 achter count(*) weghalen. Waarschijnlijk veroorzaakt dit ook je grote CPU load.

Draai de executie van die twee queries eens om?
Volgens mij maakt die +1 weinig uit, maar de caching van records wel

[ Voor 34% gewijzigd door ACM op 14-01-2005 13:20 ]

[edie]

ACM schreef op vrijdag 14 januari 2005 @ 13:19:
[...]


Draai de executie van die twee queries eens om?
Volgens mij maakt die +1 weinig uit, maar de caching van records wel

Omdraaien, twee verschillende random waardes, het maakt allemaal niets uit. De +1 is gewoon veel langzamer.

[Verwijderd]

eddie19 schreef op vrijdag 14 januari 2005 @ 13:31:
[...]

Omdraaien, twee verschillende random waardes, het maakt allemaal niets uit. De +1 is gewoon veel langzamer.

Maar je krijgt maar 1 record terug.
Zoveel zou het toch niet uit moeten maken of je count(*) terugkrijgt of count(*) + 1 ?
In mijn test (er werden 45.000 rows doorlopen) scheelt het niet in tijd of ik de +1 wel of niet doe..

[Zoijar]

Verwijderd schreef op vrijdag 14 januari 2005 @ 12:22:
Omdat het aantal punten voor een user niet uniek is wordt zo'n index IMO niet in een boomstructuur opgeslagen.

Overigens worden non unique indices ook als boom/index opgeslagen, alleen een iets minder efficiente versie, omdat je wat linear zoek overhead hebt, en dat de block grootte niet constant is...

[edie]

Verwijderd schreef op vrijdag 14 januari 2005 @ 13:37:
[...]


Maar je krijgt maar 1 record terug.
Zoveel zou het toch niet uit moeten maken of je count(*) terugkrijgt of count(*) + 1 ?
In mijn test (er werden 45.000 rows doorlopen) scheelt het niet in tijd of ik de +1 wel of niet doe..

Nou, bij mijn test is FoxPro maakte het dus wel degelijk uit. Net getest in MS-SQL Server 2000 en het maakt daar iig niks uit (17milj. records, 6 seconden).

Het verschil tussen FoxPro en SQL Server is ook duidelijk. FoxPro doet het in minder dan 1 seconde, SQL Server heeft er 6 voor nodig.

[Verwijderd]

Ik heb nu de volgende tabel:

code:

CREATE TABLE `user_top` (
  `punten` int(10) unsigned NOT NULL default '0',
  `rank` int(10) unsigned NOT NULL default '0',
  PRIMARY KEY  (`kudos_rec`,`site`(3))
) TYPE=InnoDB;

Als er gestemd wordt doe ik de volgende 2 queries:

code:

INSERT IGNORE INTO user_top(punten, rank)
SELECT [user_punten+gegeven_punten], rank
FROM    user_top
WHERE   punten < [user_punten+gegeven_punten] AND
ORDER BY punten DESC 
LIMIT 1

Mocht er in de tabel nog geen row zijn met de aantal punten van deze user wordt hij geinsert, anders niet (sneller dan eerst een select en zo nodig een insert?)

Daarna zorg ik ervoor dat iedereen die ik voorbij ben gegaan door de verkregen punten een plaats daalt:

code:

UPDATE  user_top
SET     rank = rank + 1
WHERE   punten < [user_punten+gegeven_punten] AND 
punten >=  [user_punten]

Ik heb het nu testdraaien en moet er nog rekening mee gaan houden wat er gebeurt als een gebruikersprofiel (tijdelijk) gesloten wordt e.d.
Maar dit ziet er volgens mij redelijk netjes uit.

Het opvragen van de rank is nu een simpele query op een PK ipv een zware count

[ Voor 16% gewijzigd door Verwijderd op 14-01-2005 17:11 . Reden: create table toegevoegd ]

[.oisyn]

ACM schreef op vrijdag 14 januari 2005 @ 13:18:
[...]

Er moet nog steeds gekeken worden hoeveel er dan groter waren en het lijkt me niet dat dat in een index goed bij te houden is

Het is zeker wel goed bij te houden, maar of een db index dat ook laat ik in het midden. Je moet per node in de boom opslaan hoeveel records er in totaal onder die node zitten. Dan is het gewoon zoeken naar de juiste locatie, en terwijl je dat doet steeds het aantal records onder de linker of rechter child (afhankelijk van of je het aantal records kleiner of groter dan je key wilt hebben, en alleen mits je daar niet naartoe gaat) bij elkaar optellen. O(log n) dus.