[DB Alg] Toevoegen/Verwijderen van nodes in Tree te langzaam

[gvanh]

Voor een database gebruik ik een centrale plaats voor het opslaan van de boom-structuur van alle objecten. Hierheen staan dus de verhoudingen tussen de objecten in de database opgeslagen. Hiervoor gebruik ik momenteel het "modified preorder tree traversal algorithm", omdat het belangrijk is dat ik een hele subtree met één query uit de database kan halen.

Het ophalen van gegevens werkt inderdaad vrij snel en direct ... daar in principe geen problemen.

Waar ik nu alleen tegenaan loop, is dat bij het toevoegen, verplaatsen of verwijderen van nodes uit de tree de operaties té veel tijd gaan innemen. En dan praat ik niet eens over belachelijk grote hoeveelheden van rijen ... momenteel heb ik een database draaien met een paar duizend (zeg 15.000).

Voor de duidelijkheid hier een versimpelde weergave van de tabel waar het om gaat:

MySQL:

CREATE TABLE `cms_objects` (
  `objectID` int(11) NOT NULL auto_increment,
  `caption` varchar(255) NOT NULL default '',
  `parentID` int(11) NOT NULL default '0',
  `lft` int(11) NOT NULL default '0',
  `rgt` int(11) NOT NULL default '0',
  `depth` int(11) NOT NULL default '0',
  PRIMARY KEY  (`cms_objectID`),
  KEY `lft` (`lft``),
  KEY `lft_2` (`lft`,`rgt`),
  KEY `parentID` (`parentID`),
  KEY `depth` (`depth`)
)

Bij het toevoegen van een node komt het neer op:

MySQL:

lft = lft + 2 WHERE lft > <plaats van invoegen>
rgt = rgt + 2 WHERE rgt > <plaats van invoegen>

Die twee queries duren naar mijn zin veel te lang. Bij het verplaatsen van een een nodes tegelijk krijg je dus al snel een stuk of 10 van dit soort queries ... als ze allemaal al 1 seconde duren, zit je al op 10 seconde. Dat vind ik erg lang voor een dergelijke operatie.

Is er een handiger manier om dit aan te pakken, of wellicht een heel andere boom-structuur waarmee je dit probleem ontwijkt?

[jvdmeer]

Index aanmaken?

[Janoz]

MWah, ik kan me voorstellen dat het juist de index is die ervoor zorgt dat de boel langzamer gaat.

Een oplossing heb ik verder niet. Het is sowieso altijd lastig om met boomstructuren te werken in standaard relationele databases. Je blijft altijd een tradeoff houden. In dit geval is dat goedkoper uitlezen tegenover dure inserts.

----edit

Ik zit even na te denken. Ik weet niet exact hoe het door jou gebruikte algoritme in elkaar steekt. Die left en right worden toch gebruikt als een soort ordening? Is het misschien een idee om er voor te zorgen dat die ordening wat ruimer is? Daarmee bedoel ik dat je er grote gaten tussen hebt. ipv dat ze telkens 1 hoger worden neem je 10. Bij het verplaatsen hoef je dan niet de hele tabel aan te passen maar neem je een waarde ertussen. Eventueel kun je incidenteel je left en right hernummeren.

[ Voor 43% gewijzigd door Janoz op 26-02-2007 17:27 ]

[gorgi_19]

Welke Database gebruik je hiervoor? SQL Server 2005 heeft namelijk CTE's, welke je kan gebruiken

[jvdmeer]

Ten eerste mis ik een index, nl. die op rgt. Misschien maakt dat nog uit.

Maar daarnaast (en dat zal wel aan mij liggen) zie ik even niet hoe je de data in dit geval snel kan opvragen.
Als ik je tabeldefinitie goed lees, zal je als een complete boom wilt tonen, hier niet uit de voeten kunnen met een enkele select. Terwijl dat qua snelheid vaak wel wenselijk is. Het lijkt alsof je iteratief meerdere selects uitvoert om alle data compleet te krijgen. Maar dat kan aan mij liggen.

Zou je met een klein voorbeeldje van bijv. vijf nodes aan kunnen geven wat de waarden van lft, rgt bepalen? ParentID en depth zijn wel duidelijk.

Zelf gebruik ik eerlijk gezegd een lelijke oplossing die altijd snel werkt en dat is het volledige pad naar een node compleet opnemen in het veld.
Bijv:

ID	Parent	order	pad	item
1	null	1		food
2	1	1	1	Fruit
3	2	1	11	Red
4	2	2	12	Yellow
5	3	1	111	Cherry
6	4	1	121	Banana
7	1	2	2	Meat
8	7	1	21	Beef
9	7	2	22	Pork

Op die manier kan je de varchar pad vergelijken met >'11' and <'12' om de rode vruchten te krijgen.

Met behulp van parent en order herbouw ik eventueel de structuur.

[Soultaker]

Kun je eens EXPLAIN op je update-query doen en het resultaat posten? Over welke database gaat het trouwens?

Verder zou je iets kunnen winnen door één query te doen in plaats van twee:

SQL:

UPDATE tabel
SET lft = CASE WHEN lft > index + 2 THEN lft + 2 ELSE lft END,
    rgt = CASE WHEN rgt < index + 2 THEN rgt + 2 ELSE rgt END

Effectief loop je hiermee de hele tabel door, en update je alle records. Dit is waarschijnlijk wel efficient omdat je toch al alle records moet updaten (ófwel rgt ófwel lft moet bijgewerkt worden; waarschijnlijk maakt allebei doen dan weinig uit). Het voordeel is dat je het gebruik van indices bespaart. De snelheidswinst zal wel minimaal zijn, maar toch.

[Janoz]

@jvdmeer: TS geeft aan dat hij het "modified preorder tree traversal algorithm" gebruikt. Dit werkt qua uitlezen een stuk efficienter dan de versie van jou. Een (sub)tree kan met 1 enkele select worden opgehaald. leuk leesvoer (2e hit bij google).

[whoami]

jvdmeer schreef op maandag 26 februari 2007 @ 18:12:
Ten eerste mis ik een index, nl. die op rgt. Misschien maakt dat nog uit.

Ja, het zal nog trager gaan, aangezien het probleem 'm hier bij update's / inserts zit.

Eigenlijk doe ik voor tree's meestal niks speciaals; gewoon de gegevens die ik wil mbhv 1 query uit m'n DB trekken, en m'n tree -structuur dan client-side opbouwen.

[ Voor 23% gewijzigd door whoami op 26-02-2007 20:33 ]

[jvdmeer]

Janoz schreef op maandag 26 februari 2007 @ 19:36:
@jvdmeer: TS geeft aan dat hij het "modified preorder tree traversal algorithm" gebruikt. Dit werkt qua uitlezen een stuk efficienter dan de versie van jou. Een (sub)tree kan met 1 enkele select worden opgehaald. leuk leesvoer (2e hit bij google).

Gaaf zeg, kijk eens welk voorbeeld ik gebruikt heb? Komt van dezelfde pagina af. Had alleen de link rechtsonder gemist wegens een vage popup.

whoami schreef op maandag 26 februari 2007 @ 19:40:
[...]
Ja, het zal nog trager gaan, aangezien het probleem 'm hier bij update's / inserts zit.

Ik maakte mijn opmerking over de index omdat de tweede update kijkt naar "WHERE rgt>". Door de index zou maar een beperkte set van records bekeken of aangepast te worden.

[gvanh]

Dank voor alle reacties hierboven. Huidige database is MySQL.

SELECT van hele boom kan inderdaad naar aanleiding van het geposte artikel in 1 query. Wat dat betreft ideaal. Ik zal nog 'ns wat proberen te rommelen met een index op de 'rgt' column ... maar wordt inderdaad waarschijnlijk langzamer. Ik zal ook proberen om de query in 1 keer te doen om te zien wat er dan gebeurt.

Als laatste vroeg ik me recentelijk af in hoeverre dezelfde opbouw in PostgreSQL sneller zou zijn. Ik heb beide databases tot mijn beschikking, maar eigenlijk nooit eerder iets met PostgreSQL gewerkt omdat het functioneel nooit nodig is geweest. Iemand ervaring met performance verschillen?

EDIT --- Zie net in de twee eerste resultaten in Google dat performance van MySQL in de meeste gevallen beter is dan PostgreSQL ... dus wat dat betreft is de overstap niet handig. Beide artikelen overigens uit 2005 ... is er recentelijk heel veel veranderd in de performance van postgreSQL?

[ Voor 17% gewijzigd door gvanh op 05-03-2007 15:01 . Reden: aanvulling. ]

[Not Pingu]

De MPTT methode heeft imho ook zijn nadelen. M.i. is het beter om alle treenodes in 1 query op te halen en deze dan aan de applicatiezijde te ordenen.

Hoe je dat het beste kunt doen, hangt af van wat voor tree je nodig hebt. Als het bijv. een binary tree is, kun je deze impliciet opslaan in je database dmv. een nummeringsysteem dat simpeler is dan MPTT en makkelijker te updaten.
De index*n methode geldt natuurlijk voor alle n-trees (waar je garandeert dat elke branch bestaat uit n nodes).

Ik kan uit het artikel over MPTT niet zo gauw opmaken of het bedoeld is voor n-trees of voor trees van verschillende branchgrootte.

[ Voor 71% gewijzigd door Not Pingu op 05-03-2007 18:36 ]

[chris]

Jammer dat je in MySQL geen recursieve subqueries hebt (toch?), dat zou je probleem oplossen. Ik denk dat je moet gaan kiezen voor snel uitlezen òf snel updaten. Snel uitlezen zou je eventueel nog kunnen optimaliseren op een ander niveau dan je database, bijvoorbeeld met caching.

Een andere mogelijkheid is om je tree (niet de inhoud van de nodes) buiten je database te halen. Je kan bijvoorbeeld met XML en gecompileerde XSLT een behoorlijke performance-winst halen. Hier heb je namelijk snelle updates en snelle reads.

Sterker nog, dit is volgens mij de enige oplossing die schaalt. Als je je data in een database opslaat, met gemiddeld x lagen diep en y childnodes, het aantal knopen is in de orde x^y. Aangezien je ze allemaal apart opslaat, moet je dus of zoveel records gaan updaten (uit de ts blijkt dit een probleem) of zoveel records gaan lezen (met veel of ingewikkelde queries).

[ Voor 26% gewijzigd door chris op 06-03-2007 02:30 ]

[gvanh]

Hmmm ... wat de zaken wellicht enigszins compliceert, is het feit dat de rechtenstructuur van het systeem ook is gebaseerd op de boomstructuur. Wanneer je voor een map instelt dat gebruiker A wel lees-rechten heeft, maar gebruiker B niet, dan geldt dat ook alles wat er onder die map hangt (tenzij op lager niveau specifiek anders is ingesteld).

Dat gegeven, in combinatie met de mogelijkheid om volledige trees met 1 query uit de database te halen, zorgt dat ik met 1 query datasets uit de database kan halen die voldoen aan de juiste permissie en een bepaalde (sub)structuur hebben. Dat heeft ook voordelen voor eventuele "LIMITS" ... want als je niet weet hoeveel resultaten van een dataset overblijven nadat deze gefilterd is op gebruikerspermissies, moet je dus eigenlijk altijd de volledige dataset uit de database halen en is de mogelijkheid tot het gebruik van MySQL's LIMIT vrijwel waardeloos ... dat heeft ook weer een forse negatieve impact op je snelheid (weet ik uit ervaring).

Wat dat betreft blijf ik bij voorkeur bij mijn huidige structuur en probeer ik snelheidswinst op een andere manier te bereiken (vooralsnog helaas onduidelijk hóe).

[beetle71]

Euh, ik zou als ik jou was even een paar (performance) testjes doen.
Ten eerste waarom een gecombineerde index op lft en rgt? Volgens mij voegt die weinig/niks toe, dan heb je meer aan een alleen rgt index.

Verder zou je nog eens kunnen proberen of het tabeltype van myISAM naar InnoDB omzetten hier performance winst haalt.
Daarnaast, waarom gebruik je zowel Parent-Child als MPTT? Ik kan me er wel iets bij voorstellen, soms is dat net even handiger om de ander te gebruiken, maar als je die (bijna) niet gebruikt zou ik daar de indexen van verwijderen. Scheelt weer bij het grootste deel van de updates dan.

[Not Pingu]

gvanh schreef op dinsdag 06 maart 2007 @ 10:31:
Hmmm ... wat de zaken wellicht enigszins compliceert, is het feit dat de rechtenstructuur van het systeem ook is gebaseerd op de boomstructuur. Wanneer je voor een map instelt dat gebruiker A wel lees-rechten heeft, maar gebruiker B niet, dan geldt dat ook alles wat er onder die map hangt (tenzij op lager niveau specifiek anders is ingesteld).

Je hoeft natuurlijk niet perse alles aan de databasekant af te vangen. Imho is ineens een iets te grote dataset ophalen minder erg dan veel afzonderlijke queries om maar niet teveel data binnen te krijgen. Het checken van de toegangsrechten kan natuurlijk heel goed aan applicatiezijde en ook nog eens veel sneller, omdat de dataset kleiner is.

[gvanh]

Euh, ik zou als ik jou was even een paar (performance) testjes doen.
Ten eerste waarom een gecombineerde index op lft en rgt? Volgens mij voegt die weinig/niks toe, dan heb je meer aan een alleen rgt index.

Verder zou je nog eens kunnen proberen of het tabeltype van myISAM naar InnoDB omzetten hier performance winst haalt.
Daarnaast, waarom gebruik je zowel Parent-Child als MPTT? Ik kan me er wel iets bij voorstellen, soms is dat net even handiger om de ander te gebruiken, maar als je die (bijna) niet gebruikt zou ik daar de indexen van verwijderen. Scheelt weer bij het grootste deel van de updates dan.

Ja ... da's wellicht een goed plan. InnoDB ga ik nu in een volgende versie sowieso implementeren om transactions te kunnen gebruiken (ik ben momenteel bezig met refactoring). De parentID houd ik bij omdat het in sommige queries erg handig blijkt om heel snel een parentID bij de hand te hebben. Bovendien heeft mijn huidige systeem heel af en toe wat kuren als het gaat om integriteit va de MPTT tree (ik vermoed dat dit te maken heeft met het niet correct omgaan met multi-user). M.b.v. de parent-child kan ik dan toch de structuur herstellen door de hele boom de her-indexeren.

Ik zal 'ns wat tests gaan doen met de lft and rgt indexen ... goede tip ... thanks. Overigens ... wanneer een update alleen een lft en rgt value verandert (maar b.v. de parentID ongemoeid laat) ... maakt het dan uit voor de performance of er een index zit op columns die niet veranderen?

Je hoeft natuurlijk niet perse alles aan de databasekant af te vangen. Imho is ineens een iets te grote dataset ophalen minder erg dan veel afzonderlijke queries om maar niet teveel data binnen te krijgen. Het checken van de toegangsrechten kan natuurlijk heel goed aan applicatiezijde en ook nog eens veel sneller, omdat de dataset kleiner is.

Nou ... het probleem is hier dat het dan niet gaat om een "iets" te grote dataset.

Voorbeeld: Je hebt een set objecten die allemaal voldoen aan bepaalde criteria. Bijvoorbeeld een overzicht met nieuwsberichten. Er zijn binnen de database 10.000 nieuwsberichten die voldoen aan de gestelde criteria. Maaarrrr, in je overzicht op de website wil je alleen de 10 laatst-toegevoegde laten zien waarvoor de bezoeker lees-permissie heeft.

Omdat je niet weet voor welke van de 10.000 nieuwsberichten de bezoeker permissie heeft, zou je dan dus de volledige set uit de DB moeten halen, en dan voor elk van de nieuwsberichten permissie moeten gaan checken.
Wanneer je die permissie al in je Query kan meegeven, is een simpele "ORDER BY date_toegevoegd DESC" en een "LIMIT 0,10" voldoende om maar een set van 10 te krijgen.

Moet heerlijk zeggen dat ik nooit veel tijd heb gestoken in het proberen van de eerste optie ... maar m'n gevoel zegt dat dat veel meer tijd kost.

[ Voor 30% gewijzigd door gvanh op 07-03-2007 13:43 . Reden: Aanvulling. ]