[PHP/MySQL] Teveel queries bij recursieve functie

[Reveller]

Allereerst fijne dagen allemaal

Ik maak een veilingsite en heb o.a. de volgende (gedeeltelijke) tabel:

HTML:

----+-----------+-------------------
 id | parent_id | name
----+-----------+-------------------
  0 |           | Top
----+-----------+-------------------
  2 |  0        | Electronica
----+-----------+-------------------
  3 |  2        | Computers
----+-----------+-------------------
 21 |  2        | Mobiele Telefoons
----+-----------+-------------------
  6 |  3        | Desktops
----+-----------+-------------------
  7 |  3        | Laptops
----+-----------+-------------------
 33 |  6        | Dell
----+-----------+-------------------

De pagina browse.php haalt de categorien uit de database die de bezoeker wil zien. Bijvoorbeeld browse.php?id=2 haalt alle categorien op die onder electronica vallen en stuurt dus naar de browser:

HTML:

<li><a href="bowse.php?id=3">Computers</a>
<li><a href="bowse.php?id=21">Mobiele Telefoons</a>

Op dezelfde wijze retourneert browse.php?id=6:

HTML:

<li><a href="browse.php?id=33">Dell</a>

Ik wil nu graag aan de bezoeker tonen waar hij in de site zit. Hiertoe wil ik een cookie crumb trail maken. In het laatste geval zou deze er als volgt uitzien:

HTML:

<a href="browse.php?id=0">Top</a> > <a href="browse.php?id=2">Electronica</a> 
> <a href="browse.php?id=3">Computers</a> > Desktops

Ofwel in de browser:

HTML:

Top > Electronica > Computers > Desktops

Om deze trail te kunnen maken, heb ik een recursieve functie nodig, welke vanaf het gevraagde id (6 voor Desktops) in de boom omhoog loopt tot ie bij Top uitgekomen is.

Zoals ik het zie, heb ik voor bovenstaande trail (browse.php?id=6) 4 queries nodig:

PHP:

$id = $_GET[id]; /* $id is in dit voorbeeld 6 */

SELECT parent_id, name FROM categories WHERE id = 6 /* retourneert 3 en Desktops. 
3 Moet dan weer ingevuld worden in een nieuwe query */

SELECT parent_id, name FROM categories WHERE id = 3 /* 2, Computers */

SELECT parent_id, name FROM categories WHERE id = 2 /* 0, Electronica */

SELECT parent_id, name FROM categories WHERE id = 0 /* Top */

Dit vind ik veel te veel. Ik wil de site vooral snel houden, en nu spring ik van 1 naar in totaal 5 queries op browse.php. Bovendien wil ik later nog een statistiekentooltje bouwen (1 query), een "nieuwe producten" box op elke pagina (1 query) en nog een en ander. Zo zit ik al snel op 8, 9 queries per pagina.

Toen ben ik over dit probleem gaan nadenken, en de enige mogelijkheid die ik zie om die trail met maar 1 query te schrijven is om hem hardcoded in de database in te voeren. Ik zou dan bijvoorbeeld krijgen:

HTML:

----+-----------+-----------+---------------------------------------------
 id | parent_id | name      | trail
----+-----------+-----------+---------------------------------------------
  6 |  3        | Desktops  | <a href="browse.php?id=0">Top</a> > 
    |           |           | <a href="browse.php?id=2">Electronica</a> > 
    |           |           | <a href="browse.php?id=3">Computers</a> > 
    |           |           | Desktops
----+-----------+-----------+---------------------------------------------

Ik dacht, omdat er toch niet dagelijks categorien bij komen (niet eens wekelijks), en ik toch zelf de administratie verzorg, kan ik net zo goed wat tijd nemen om zo'n trail zelf ff uit te tikken. Op die manier haal ik in 1 query alle op.

Nadeel is wel dat wanneer de site WEL vaker geupdate zal moeten worden (en dat moet de toekomst uitwijzen) dat ik dat een hoop extra werk heb.

Mijn vragen zijn:
1) zijn jullie ook tegen soortgelijke performance problemen (te veel queries naar jouw zin) aangelopen en hoe heb je dit opgelost?
2) wat vind je van mijn oplossing? Welke voor/nadelen zie je?
3) heb je wellicht een andere oplossing waarmee ik met minder queries die trail kan maken?

[Woef]

Mijn vragen zijn:
1) zijn jullie ook tegen soortgelijke performance problemen (te veel queries naar jouw zin) aangelopen en hoe heb je dit opgelost?
2) wat vind je van mijn oplossing? Welke voor/nadelen zie je?
3) heb je wellicht een andere oplossing waarmee ik met minder queries die trail kan maken?

1,2) Ik controleerd het altijd aan de hand van de tijd dat een pagina gemaakt is. EN jou categorie methode vind ik ook vrij onlogisch of ligt dat aan mij?!

3) Misschien bij elke handeling cookie aanmaken. Indien cookie niet aangemaakt is dus als hij binnenkomt via deeplinking, dan wel die query's uitvoeren.

[chris]

Het zijn misschien wel veel queries, maar het werkt wel perfect. Je kan het wel hardcoded in je DB zetten, maar dan moet je wel zeker weten dat het een kleine tree worden (anders wordt de database al snel érg groot). Wat je ook kan doen, is queries gaan cachen. Maar dan zit je met een soortgelijk probleem, namelijk dat je alles moet gaan updaten op het moment dat je ergens iets wijzigt.

Wat ik persoonlijk ook een groot nadeel vindt, is dat op het moment dat je die html in de database opslaat. Stel dat je later ook nog een title-attribuut in je <a> wil, of je verandert de naam van browse.php, of, nog erger, je maakt óok een pda-versie.

Ik zou gewoon maar veel queries gaan doen, en deze cachen. Dit lijkt mij het best.

[edit]
ik kwam deze link tegen, zelf nog niet kunnen lezen, maar het lijkt wel interessant.

[edit2]
die link is echt super interessant, hiermee kan je met 1 query een hele tree uitlezen, en je kan ook met 1 query een hele parent-list opvragen. Echt heel mooi! Het nadeel is alleen dat het updaten van een tree heel lang kan duren bij een grote tree, maar in jouw geval lijkt met dit niet op te wegen tegen de kosten van de recursieve methode. Echt erg leuk om 's te lezen, niet zo makkelijk te begrijpen als recursie maar zeker de moeite waard.

[ Voor 32% gewijzigd door chris op 25-12-2003 23:18 ]

[Alex]

Je kunt natuurlijk ook je path opslaan bij het record.
Dat kost éénmaal iets meer queries, maar slecht eenmaal. Vervolgens vraag je het zo op:

code:

SELECT id, naam FROM categories WHERE id=IN(SELECT path FROM categories WHERE id=[Huidige pagina id])

Met wat PHP scripting heb je dan prachtig het hele rijtje

[chris]

Alex de Groot schreef op 25 december 2003 @ 22:46:
Je kunt natuurlijk ook je path opslaan bij het record.
Dat kost éénmaal iets meer queries, maar slecht eenmaal. Vervolgens vraag je het zo op:

code:

SELECT id, naam FROM categories WHERE id=IN(SELECT path FROM categories WHERE id=[Huidige pagina id])

Met wat PHP scripting heb je dan prachtig het hele rijtje

Leuk, maar het gaat hier over MySQL. MySQL is best tof soms, maar subqueries

[Alex]

chris schreef op 25 december 2003 @ 23:19:
[...]


Leuk, maar het gaat hier over MySQL. MySQL is best tof soms, maar subqueries

De code die ik liet zien werkt in MySQL.
Als je het toch moet gebruiken gebruik dan de handige IN()-functie die zeker te weten werkt.
ACM en andere P&W guru's verwijzen er vaak naar...

Probeer het eens, tisde enige manier om het voor elkaar te krijgen
Documentatie: http://www.mysql.com/doc/en/ANY_IN_SOME_subqueries.html

Mocht het niet werken vanwege een wat oudere MySQL doe het als volgt met 2 queries:

code:

SELECT path FROM categories WHERE id=[Huidige pagina id])
SELECT id, naam FROM categories WHERE FIND_IN_SET(id, [Result query 1, agescheiden door komma's]);

Zie ook: http://www.mysql.com/doc/en/String_functions.html

Thnx voor het ophalen van mijn kennis

[crisp]

je kan bij een update of insert die trail toch laten genereren; het is wel redundant data, maar ook een beetje caching...

[ProgrammerX]

crisp schreef op 26 december 2003 @ 01:36:
je kan bij een update of insert die trail toch laten genereren; het is wel redundant data, maar ook een beetje caching...

Ik vind dit nog de best tip tot nog toe

P.S. Ik dacht dat mysql trouwens vanaf versie 4 wel subqueries ondersteunde (heb eerlijk gezegd al een tijdje niet meer naar mysql gekeken hoor maar dit had ik ooit ergens gelezen)

[Alex]

crisp schreef op 26 december 2003 @ 01:36:
je kan bij een update of insert die trail toch laten genereren; het is wel redundant data, maar ook een beetje caching...

Je kunt hem natuurlijk ook volledige genereren, maar ik vond mijn oplossing iets schaalbaarder als je te maken gaat krijgen met wijzigingen in namen etc.

[chris]

ProgrammerX schreef op 26 december 2003 @ 02:44:
[...]


Ik vind dit nog de best tip tot nog toe

P.S. Ik dacht dat mysql trouwens vanaf versie 4 wel subqueries ondersteunde (heb eerlijk gezegd al een tijdje niet meer naar mysql gekeken hoor maar dit had ik ooit ergens gelezen)

MySQL ondersteunt vanaf versie 4.1 subqueries, en dit is momenteel nog een alpha, dacht ik. Maar topicstarter: lees dat artikeltje van hierboven eens, is een erg mooie manier om met bomen te werken, en je slaat geen onnodige data op.

[Reveller]

iedereen bedankt voor zijn reaktie tot nu toe. Ruben_Pruim - de tabel zoals ik hem heb is voor zover ik weet een standaard tabel om trees te bouwen in combinantie met een recursieve functie. Chris- ik ga dat artikel eens bekijken. Crisp - daar had ik ook aan zitten denken: om een script te schrijven dat die trail voor mij genereert en hem vervolgens in de database stopt. Door iets in dat script te veranderen (zoals browse.php naar surf.php), kan ik ineens alle trails in de dbase laten updaten...niet ideaal maar wel soort van snel

Het artikel over die Modified Preorder Tree Traversal had ik al eerder eens bekeken en het is een zeer goede manier, maar ik vraag me af of er mensen zijn die dat ook al werkelijk hebben toegepast.

Tot zover bedankt. Als mensen nog een andere mening over dit onderwerp hebben, etc. dan hoor ik dat nog graag!

[Knutselsmurf]

Zoietz heb ik zelf ook ooit gemaakt. Zelfs met redelijk complexe bomen. De queries waarmee je die recursieve lijst opbouwd, zijn zodanig eenvoudig, dat die vrij weing tijd kosten. De connectie met de database zal waarschijnlijk het meeste tijd kosten. Eventueel kun je de gegevens opslaan in een sessie.

Wat nog wel tijd scheelt, is als je een index zet op parent_id.
Om namelijk de inhoud van een subcategorie op te halen, zul je een query hebben als:

SQL:

SELECT * FROM tabel WHERE parent_id=694982

Door de index kun je met deze queries nog wel wat tijd besparen.

[Verwijderd]

Probeer eens de Modified Preorder Tree Traversal.

link naar artikel waarin het e.e.a. wordt uitgelegd :
http://www.sitepoint.com/article/1105/2

[Verwijderd]

hmmm

en iets als:

code:

SELECT           t1.id, t1.name, t2.id, t2.name, t3.id, t3.name
FROM              table AS t1
LEFT JOIN       table AS t2 ON t2.id = t1.parent_id
LEFT JOIN       table AS t3 ON t3.id = t2.parent_id
WHERE           t1.id = huidige_id

volgens mij krijg je dan iets als:

3, Computer, 2, Electronica, 0, Top

of zit ik helemaal verkeerd te denken...

[Verwijderd]

Wat je nodig hebt staat in het volgende artikel:
http://www.sitepoint.com/article/1105/1

Dit artikel legt uit hoe je het beste hierarchische data in een database kan opslaan. Heel fijn dat er ook wat voorbeeldqueries bijzitten

[zag dat ik niet goed had gelezen, deze url was al gegeven]

[ Voor 12% gewijzigd door Verwijderd op 26-12-2003 20:35 ]

[SchizoDuckie]

Als je je zo druk maakt om het aantal query's, waarom sleur je dan niet gewoon in 1x alle items van die tabel binnen, en maak je a.d.h. daarvan met php zo'n path?

[MisterData]

Als je even zoekt op GoT naar het cellco-model, een maand geleden ofzo hebben we dit namelijk al eens besproken

[ACM]

Als je het pad "naar de top" wilt hebben zijn er, volgens mij, twee handige methoden:
- Nested Set van Joe Celko (in sommige artikelen "modified pre order traversal" genoemd), met de zoekterm "nested set" en Celko kom je waarschijnlijk wel e.e.a. aan nuttige links tegen.
- Materialized Path. Daarbij sla je (bijv een tekstveld) het pad naar de node op, met bijv 1.3.15.212 etc.

Nadeel bij beide is dat het een rotwerk is om de boom te onderhouden. Verwijderen en verplaatsen van nodes zijn behoorlijk lastig bij de beide methoden en bij de Nested Set is het toevoegen ook al niet zo fijn.
Er is een methode (Nested Intervals wordt ie wel genoemd) die, in theorie, de problemen van Nested Set verhelpt. Maar die heeft in de praktijk het nadeel dat ie te weinig records kan verwerken, de praktische limieten ervan kan ik niet zo uit mijn hoofd oplepelen, 't kan zijn dat ie vooral in de diepte (in dit geval vast niet zo erg) beperkt is en in de breedte wel aardig wat nodes aan kan.
Materialized Path heeft als nadeel dat je nogal wat data opslaat die daardoor vrij sloom op te sporen kan zijn.

Btw, een potentiele oplossing met de Adjacency List (wat je nu gebruikt) is dat je in een cookie/sessie bijhoudt welke categorieen iemand al bezocht heeft en die allemaal tegelijk met een IN(cat1, cat2, ...) eruit trekt. Dat kleine groepje data is erg simpel met php in een logische volgorde zetten (of zelfs met je query, als je de volgorde al van te voren kan aangeven, dmv een CASE in de ORDER BY)

Ik vond dit nog wel een aardig overzicht trouwens:
http://www.scenic-route.com/program/db/lists.htm

[ Voor 5% gewijzigd door ACM op 27-12-2003 11:15 ]

[Reveller]

Papa Eend - dat is voor 10 recordsets nog wel te doen, maar wat als ik bij elke request, 1000 recordsets uit een database moet trekken? Heb niet heel veel verstand van mysql performance, maar denk dat dat toch echt niet gewenst is.

MisterData - bedankt voor de tip, ik ga er zodadelijk naar kijken

ACM - een goed uitgebreid en duidelijk verhaal, waar ik veel aan heb. Had zelf ook al aan cookie / sessie gedacht, maar wilde eerst wat meningen horen over het aantal queries voor ik daar verder mee zou gaan. Ik ga alles bekijken!

[Verwijderd]

Reveller schreef op 27 december 2003 @ 15:25:
Papa Eend - dat is voor 10 recordsets nog wel te doen, maar wat als ik bij elke request, 1000 recordsets uit een database moet trekken? Heb niet heel veel verstand van mysql performance, maar denk dat dat toch echt niet gewenst is.

MySQL 4 heeft ook nog zoiets als een query-cache. Je schrijft dat er niet eens wekelijks in die categorieën wordt gewijzigd. MySQL 4 zal dus een week lang met een vinger in z'n neus uit die cache staan te lepelen.

Verder is het ook nog een optie om zelf het pad te cachen. Het hele pad terug vanaf een eind-node sla je dan op.
Je kunt ervoor kiezen om een bepaalde tijd uit de cache te putten, of pas bij het aanpassen van de boom de betreffende items uit de cache te verwijderen.

Door slim te cachen is load op een database enorm te reduceren. Deze week nog bij een drukbezochte site uitgevoerd: op veel pagina's staan dingen als het totaal aantal records, de 10 meest recente en de 10 meest bezochte records vermeld. Door deze drie items slechts 1 minuut te cachen is de load van de db server meer dan gehalveerd.

[GraasGast]

Anders maak je er een Celko tree van? met left en right values. Dan kan je in 1 query je hele pad eruit halen:

code:

SELECT t1.id, t1.name
FROM categories AS t1, categories AS t2
WHERE t2.lft BETWEEN t1.lft AND t1.rgt
AND t2.rgt BETWEEN t1.lft AND t1.rgt
AND t2.id = 6