[MySQL] Boomstructuur

[Verwijderd]

Beste tweakers,
ik zit al weken met een probleem, waar ik geen goede "howto" voor kan vinden.

Ik beheer een vrienden netwerk site, die werkt met "levels":
- level 1: alleen vrienden kunnen je profiel zien.
- level 2: vrienden van vrienden + vrienden kunnen je profiel zien.
- level 3: vrienden van vrienden van vrienden + vrienden van vrienden + vrienden kunnen je profiel zien.
- level 4: iedereen kan je profiel zien.

de netwerk tabel ziet er zo uit:

code:

network (
  user int(10) NOT NULL default '0',
  friend int(10) NOT NULL default '0'
)

als voorbeeld:

code:

user | friend
---------------
  1   |    3
  3   |    5
  7   |    8
  3   |    7


1 (ik) -> 3 (level 1) -> 5 (level 2)
                      -> 7 (level 2) -> 8 (level 3)

nu wil ik checken of iemand toegang mag krijgen tot een pagina, de gebruiker moet binnen het level 3 zitten, op het moment gebruik ik deze query (die 30 seconden lang duurt ):

(hier probeert user:2 te connecten naar de pagina van user:3)

code:

SELECT 1 
FROM network AS t1 
INNER JOIN network AS t2 
   ON (t1.friend = t2.user) 
INNER JOIN network AS t3 
   ON (t2.friend = t3.user)
WHERE t1.user = 2
   AND (t1.friend = 3 OR 
        t2.friend = 3 OR 
        t3.friend = 3)
LIMIT 0,1

daarna doe ik een mysql_num_rows, en als er >= 1 row is, geef ik toegang.
iemand enig idee hoe ik deze query, of desnoods mijn hele structuur kan verbeteren om mijn snelheid te verhogen?

Thomas

[Verwijderd]

Weet je zeker dat het aan je query ligt? Ik heb bovenstaande even nagemaakt in PostgreSQL (ik heb hier geen MySQL) en de query is binnen een seconde klaar. Zelfs als de persoon 10.000 vriendjes heeft duurt het nog maar 3 seconden.

[beetle71]

heb je wel indexen aangemaakt op je user en friends velden? Wat ook nog zou kunnen helpen is je query anders opbouwen. (maar misschien dat mysql dat zelf nu al eruit optimaliseert)

code:

SELECT 1 
FROM network AS t1 
INNER JOIN network AS t2 
   ON (t1.friend = t2.user and t2.friend=3) 
INNER JOIN network AS t3 
   ON (t2.friend = t3.user and t3.friend=3)
WHERE t1.user = 2
   AND t1.friend = 3 
LIMIT 0,1

Zet anders eens 'explain' voor je query en vertel(=post) hier het result daarvan.

[ Voor 10% gewijzigd door beetle71 op 27-02-2005 20:11 ]

[Verwijderd]

Verwijderd schreef op zondag 27 februari 2005 @ 19:57:
Weet je zeker dat het aan je query ligt? Ik heb bovenstaande even nagemaakt in PostgreSQL (ik heb hier geen MySQL) en de query is binnen een seconde klaar. Zelfs als de persoon 10.000 vriendjes heeft duurt het nog maar 3 seconden.

in de table zitten op het moment 150.000 connecties, de connectie die ik daarnet uitprobeerde (user 2) zou 1500 resultaten hebben als ik hem niet zou limit-en.

[ Voor 3% gewijzigd door Verwijderd op 27-02-2005 20:14 ]

[Verwijderd]

code:

id  select_type  table  type  possible_keys  key  key_len  ref  rows  Extra  
1   SIMPLE        t1     ALL NULL NULL NULL NULL 151810 Using where 
1   SIMPLE        t2     ALL NULL NULL NULL NULL 151810 Using where 
1   SIMPLE        t3     ALL NULL NULL NULL NULL 151810 Using where

[ACM]

beetle71 schreef op zondag 27 februari 2005 @ 20:10:
heb je wel indexen aangemaakt op je user en friends velden? Wat ook nog zou kunnen helpen is je query anders opbouwen. (maar misschien dat mysql dat zelf nu al eruit optimaliseert)

code:

SELECT 1 
FROM network AS t1 
INNER JOIN network AS t2 
   ON (t1.friend = t2.user and t2.friend=3) 
INNER JOIN network AS t3 
   ON (t2.friend = t3.user and t3.friend=3)
WHERE t1.user = 2
   AND t1.friend = 3 
LIMIT 0,1

Zet anders eens 'explain' voor je query en vertel(=post) hier het result daarvan.

Dat is geen andere opbouw, dat is een andere query (AND ipv OR ineens).

vziw is MySQL niet zo'n ster in het optimaliseren van dit soort queries, maar wellicht dat er nog een index op de friend en user-velden van die tabel mist. Zo niet, dan kan het sneller zijn om drie losse queries uit te voeren of om drie queries met union aan elkaar te koppelen.
Zeker als het vaak voorkomt dat de vrienden de pagina's van andere vrienden willen bekijken, dan zou ik de niveau's apart nemen.

Overigens kan je ook een tabel erbij maken waar je de "afstand" van users tot (alle verbonden) andere users bijhoudt en je op die manier in 1 tabel op kan zoeken of iemand zich maximaal op niveau 3 bevindt.

[Verwijderd]

Zo niet, dan kan het sneller zijn om drie losse queries uit te voeren of om drie queries met union aan elkaar te koppelen.

zou je hier misschien een voorbeeld van willen geven?

Overigens kan je ook een tabel erbij maken waar je de "afstand" van users tot (alle verbonden) andere users bijhoudt en je op die manier in 1 tabel op kan zoeken of iemand zich maximaal op niveau 3 bevindt.

zo'n tabel zou dan miljoenen rows krijgen, word mysql dan niet helemaal gek?

[ACM]

Verwijderd schreef op zondag 27 februari 2005 @ 20:22:
zou je hier misschien een voorbeeld van willen geven?

Van een union? Dat is vrij simpel hoor:

SQL:

SELECT count(*) FROM network n1 WHERE n1.user = X AND n1.friend = Y
UNION
 SELECT count(*)
    FROM network n1 
              JOIN network n2 ON n1.friend = n2.user
    WHERE n1.user = X AND n2.friend = Y
UNION
 SELECT count(*)
    FROM network n1 
              JOIN network n2 ON n1.friend = n2.user
              JOIN network n3 ON n2.friend = n3.user
    WHERE n1.user = X AND n3.friend = Y

Precies de queries die je anders voor de losse checks zou gebruiken, maar dan even rekening er mee houdend dat het union-statement alle records achter elkaar gooit uit de losse queries.

zo'n tabel zou dan miljoenen rows krijgen, word mysql dan niet helemaal gek?

Dat hoeft helemaal geen probleem te zijn hoor. Zeker als je oneindige dieptes zou willen toestaan wordt het een keuze tussen meer opslag en trage(re) queries, vaak is de opslag goedkoper en makkelijker toe te staan dan trage(re) queries.

Bij 1000 users die gemiddeld met 10 anderen een connectie hebben is het 10.000 (worst/best/average case) vs 1.000.000 (worst case, maar kan minder zijn) records. Wat in een binaire zoekboom al neerkomt op 13a14 stappen vs 19a20 stappen.

Voor de 2niveau-query moet je echter zoeken naar alle directe koppelingen met user X en daarvan bekijken of die weer een directe koppeling met Y hebben. Dus je moet gemiddeld al 10+100 records afzoeken en die elk 13a14 stappen in je index kosten. Dus je moet 110x 13a14 stappen vs 1x 19a20 stappen zetten in de index. Voor elk niveau dieper kan je een 1 voor die 110 plakken...

Opslag van de tabel zal iets van 3 integers van elk 4 bytes * aantal records zijn. Dus in de orde van grootte van 120KB vs 1MB. Hoe groter de directe-connectiegraad hoe kleiner het verschil.

Voordeel van zo'n methode is dus dat het aanzienlijk sneller zoekt, mits de hogere i/o-belasting geen grote problemen oplevert (als het dan ineens grotendeels niet meer in het geheugen van de db past, ipv helemaal wel). Nadeel is dat het meer onderhoud vergt om die grote tabel bij te houden en je waarschijnlijk die grote tabel er bij moet hebben ipv uitsluitend die grote tabel kan gebruiken.

[ACM]

Verwijderd schreef op zondag 27 februari 2005 @ 20:13:
in de table zitten op het moment 150.000 connecties, de connectie die ik daarnet uitprobeerde (user 2) zou 1500 resultaten hebben als ik hem niet zou limit-en.

Dat is ook zoiets... Je selecteert van die directe verbinding (niveau 1) ook nog alle 2e en 3e niveau connecties! Dus een flinke extra hoeveelheid gegevens om uit te pluizen, ook dat verdwijnt met de union of het in losse queries uit elkaar trekken.

Verwijderd schreef op zondag 27 februari 2005 @ 20:19:

code:

id  select_type  table  type  possible_keys  key  key_len  ref  rows  Extra  
1   SIMPLE        t1     ALL NULL NULL NULL NULL 151810 Using where 
1   SIMPLE        t2     ALL NULL NULL NULL NULL 151810 Using where 
1   SIMPLE        t3     ALL NULL NULL NULL NULL 151810 Using where

possible_keys NULL... Je hebt helemaal geen indices?
CREATE INDEX network_user ON network(user);
CREATE INDEX network_friend ON network(friend);

En kijk dan nog eens hoe snel het gaat?

[Verwijderd]

0.076652 seconden
ontzettend bedankt

is er trouwens verschil tussen: CREATE INDEX network_user ON network(user,friend);
en beide apart?

[ Voor 71% gewijzigd door Verwijderd op 27-02-2005 20:59 ]

[ACM]

Ja, je krijgt dan een index waarin je eerst op user en dan op friend kan zoeken, maar als er dus relatief veel friends per user zijn en je vooral zoekt naar user-friend combinaties ipv "alle friends van user X", dan zal het nog weer wat vlotter gaan.
Je kan niet zoeken naar alle user's die X als friend hebben (dus where friend = X), maar wel naar where user = X en where user = X and friend = Y. Als je dingen van de laatste structuur hebt is die multi-column index vaak wat sneller, hoewel het wel weer van de vulling en grootte van de index afhangt e.d.

[Verwijderd]

nog een vraagje, de UNION query geeft alleen c1 terug als ik hem via mysql_fetch_assoc fetch.

code:

SELECT count(*) AS c1 FROM network n1 WHERE n1.user = $user AND n1.friend = $friend
                    UNION
                     SELECT count(*) AS c2
                        FROM network n1 
                                  JOIN network n2 ON n1.friend = n2.user
                        WHERE n1.user = $user AND n2.friend = $friend
                    UNION
                     SELECT count(*) AS c3
                        FROM network n1 
                                  JOIN network n2 ON n1.friend = n2.user
                                  JOIN network n3 ON n2.friend = n3.user
                        WHERE n1.user = $user AND n3.friend = $friend

code:

Array ( [c1] => 1)

waarom?

[Janoz]

Een union plaatst resultaten onder elkaar, niet naast elkaar. Je zult deze resultaten moeten ophalen door 3x te fetchen.

[Verwijderd]

PHP:

while ($fetched = mysql_fetch_assoc ($query))
{
    $amount[] = $fetched;
}
        
print_r ($amount);

zo doe ik het toch goed, of niet? toch krijg ik alleen c1 terug.

code:

Array ( [0] => Array ( [c1] => 0 ) )

[ Voor 7% gewijzigd door Verwijderd op 28-02-2005 15:50 ]

[LordLarry]

Je kan ook de boomstructuur op een andere manier opslaan zodat het met een enkele query over oneindig veel lagen werkt. Zie [rml]LordLarry in "[ SQL] alle childs vanaf parent selectere..."[/rml]

[ Voor 31% gewijzigd door LordLarry op 28-02-2005 16:32 ]

[Verwijderd]

laat maar, kheb hm:

code:

SELECT COUNT(`n1`.`friend`) AS `amount` FROM friend_network n1 WHERE n1.user = $user AND n1.friend = $friend
                    UNION
                     SELECT COUNT(`n1`.`friend`) AS `amount`
                        FROM friend_network n1 
                                  JOIN friend_network n2 ON n1.friend = n2.user
                        WHERE n1.user = $user AND n2.friend = $friend
                    UNION
                     SELECT COUNT(`n1`.`friend`) AS `amount`
                        FROM friend_network n1 
                                  JOIN friend_network n2 ON n1.friend = n2.user
                                  JOIN friend_network n3 ON n2.friend = n3.user
                        WHERE n1.user = $user AND n3.friend = $friend

bedankt voor de hulp allemaal!