[php/mysql] mptt performance, alternatief?

[Woef]

Voor het opslaan van hiërarchische database structuur leg ik de volgende gegevens vast:

• id
• parent_id
• level
• childs
• left (mptt)
• rigt (mptt)

Het bewerken van zo'n 10.000 rows is geen probleem, maar nu heb ik 200.000 records en dat gaat waarschijnlijk wel een 1.000.000 worden. Een insert duurt nu al meer dan 2 minuten. Omdat deze insert zo lang duurt en er ondertussen ook verschuivingen kunnen plaatsvinden raken de left en rigt van het mptt-model corrupt. Daar heb ik wel een leuke mysql functie voor geschreven die dit ’s nachts fijn kan oplossen maar die heeft ook al meer dan 5 uur nodig om dit te herstellen.
Doordat er indexen zitten op de left en right gezamenlijk en afzonderlijk nog op de lft zorgt een insert dus voor veel rekenkracht. Ik maak gebruik van Innodb zonder locking.

Zonder direct allerlei niet relevante gegevens te posten vroeg ik mij af of hoe iemand weet hoe ik dit structureel kan oplossen?

(op verzoek kan ik extra informatie geven, code, server specs etc).

[ Voor 0% gewijzigd door Woef op 30-06-2013 00:16 . Reden: aanpassing op index, op de right zit geen afzonderlijke index ]

[GlowMouse]

Is die 2 minuten onder concurrent load? Wat is de concurrency, en welke hardware is de bottleneck? Wat is de MySQL-versie?

Doordat er indexen zitten op de left en right gezamenlijk en afzonderlijk

Waarom ook afzonderlijk?

[Gomez12]

Past je dbase wel compleet in je geheugen? En idd, waarom en gezamelijke indexen en afzonderlijke? Afhankelijk van de volgorde zou je al 1 afzonderlijke weg kunnen halen zonder echte nadelen.

[Woef]

GlowMouse schreef op zondag 30 juni 2013 @ 00:11:
Is die 2 minuten onder concurrent load? Wat is de concurrency, en welke hardware is de bottleneck? Wat is de MySQL-versie?

[...]

Waarom ook afzonderlijk?

Kleine aanpassing gemaakt in starttopic, op de right zat geen afzonderlijke index, op de left wel, omdat ik daar op sorteer (is direct de sorteervolgorde).

Specs van de server zijn als volgt:

• DELL R620 CPU: ES-5640
• 2,5Ghz, 15M cache,
• 6C RAM: 4x 8Gb - 32Gb Storage:
• 2x 146Gb SAS 15K Storage 2x 900Gb SAS 10K
• Raid-Controller: PERC H710 Raid-Config: Raid 1 Power:
• OS: CentOS
• MySQL versie: 5.1.66
• Apache/2.2.15

Hoe zou ik kunnen zien wat de bottleneck is? Maar in pricipe zou het met deze specs best goed moeten lukken. Dus ik zat meer te denken aan een ander model dan het mptt of misschien doe ik iets anders niet goed.

[GlowMouse]

Ik mis info over die 2 min, wat is de concurrency? Heeft die H710 nog een goede batterij?

Wat is je InnoDB-configuratie?

[ Voor 16% gewijzigd door GlowMouse op 30-06-2013 00:45 ]

[Woef]

GlowMouse schreef op zondag 30 juni 2013 @ 00:44:
Ik mis info over die 2 min, wat is de concurrency? Heeft die H710 nog een goede batterij?

Wat is je InnoDB-configuratie?

Server is van december 2012. Maar kan batterij laten checken, is dit een bekend probleem?

Er wordt op dat moment live in gewerkt dus er zullen altijd bewerkingen en aanvragen binnenkomen die dezelfde tabel oproepen. En dat zijn er best veel in die twee minuten, kleine impressie van de totale database.
Questions sinds opstart: 41,145,294

• ø per uur: 441,573
• ø per minuut: 7,360
• ø per seconde: 123

InnoDB config:

• innodb adaptive hash index ON
• innodb additional mem pool size 1 MiB
• innodb autoextend increment 8
• innodb autoinc lock mode 1
• innodb buffer pool size 512 MiB
• innodb checksums ON
• innodb commit concurrency 0
• innodb concurrency tickets 500
• innodb data file path ibdata1:10M:autoextend
• innodb data home dir
• innodb doublewrite ON
• innodb fast shutdown 1
• innodb file io threads 4
• innodb file per table OFF
• innodb flush log at trx commit 1
• innodb flush method
• innodb force recovery 0
• innodb lock wait timeout 50
• innodb locks unsafe for binlog OFF
• innodb log buffer size 1 MiB
• innodb log file size 5 MiB
• innodb log files in group 2
• innodb log group home dir ./
• innodb max dirty pages pct 90
• innodb max purge lag 0
• innodb mirrored log groups 1
• innodb open files 300
• innodb rollback on timeout OFF
• innodb stats method nulls_equal
• innodb stats on metadata ON
• innodb support xa ON
• innodb sync spin loops 20
• innodb table locks ON
• innodb thread concurrency 8
• innodb thread sleep delay 10,000
• innodb use legacy cardinality algorithm ON

[ Voor 0% gewijzigd door Woef op 30-06-2013 01:00 . Reden: opmaak ]

[GlowMouse]

innodb buffer pool size 512 MiB
innodb log file size 5 MiB

dat is wat mager

[Woef]

GlowMouse schreef op zondag 30 juni 2013 @ 01:05:
[...]

dat is wat mager

buffer pool size heb ik een verzoek voor ingedient om dit aan te passen. Hier lees ik wel verschillende berichten over de een zegt 70 tot 80% van het totale geheugen en de ander zegt 10% meer dan de totale database grootte.

Net zoals de log files. Daar wordt ook wel van gezegd dan je die zo klein mogelijk moet houden?!

[krvabo]

Woef schreef op zondag 30 juni 2013 @ 00:22:
[...]

Kleine aanpassing gemaakt in starttopic, op de right zat geen afzonderlijke index, op de left wel, omdat ik daar op sorteer (is direct de sorteervolgorde).

Afgezien van de rest van de vragen even dit:
Index: (left, right)
Query: Where left = ?
-> gebruikt Index

Index: (left, right)
Query: Where right = ?
-> gebruikt Index niet

Index: (left, right), right
Query: Where right = ?
-> gebruikt Index 2
Query: Where left = ?
-> gebruikt Index 1

Dit is wel te zien door een EXPLAIN voor je query te gooien.

[ Voor 5% gewijzigd door krvabo op 30-06-2013 01:26 ]

[UltimateB]

De techniek die je gebruikt is ontwikkeld voor snel ophalen van data, maar relatief langzaam met het updaten van data. Om een node toe te voegen aan de boom moet afhankelijk van waar je de node insert een hoop updates gedaan worden. Een node boven aan (lft 1) moeten bijna alle rows geupdatet worden. Dit duurt wel even. Een parent/child model is misschien in handiger in deze situatie aangezien bij een insert dan minder rows geupdatet hoeven te worden. Maar dit heeft dan wel een negatief effect op de queries die een deel van boom moeten ophalen.

[ACM]

Er zijn een aantal afwegingen die zinvol zijn om te besluiten of Nested Set (wat jij gebruikt met je left/right) wel de juiste methode is.

Hoe diep is je boom? Als ie nergens dieper dan bijvoorbeeld 2 of 3 is, dan kan je overwegen om het er helemaal uit te halen en altijd met joins/subqueries te werken.

Hoeveel elementen zitten er onder de "root" van je boom? Als er veel elementen direct onder je root zit, kan je overwegen om per element een losse subtree en dus losse Nested Set te beginnen. Overigens kan dit ook helpen als er maar een stuk of 4 nodes onder je root zitten, je hoeft dan alsnog maar worst case 1/4e van je dataset aan te passen per keer.

Wat voor data wil je uit je boom hebben? Wil je altijd alle elementen voor heel eenvoudig te bepalen en eenduidige subtrees hebben? Dan kan je overwegen om ook je Nested Set (gedeeltelijk) overboord te zetten, maar elk element een "subtree id" mee te geven naast het parentid. Afhankelijk van het aantal nodes dat je ophaalt kan je dat ook in het geheugen van je applicatie weer op de juiste manier aan elkaar koppelen.

Ben je genoodzaakt om MySQL te blijven gebruiken? O.a. PostgreSQL kent recursieve querymogelijkheden. Dan zou je nested set niet nodig hebben, maar via recursieve SQL in een keer alle elementen onder parentid X op kunnen halen.

[Woef]

krvabo schreef op zondag 30 juni 2013 @ 01:24:
[...]

Afgezien van de rest van de vragen even dit:
Index: (left, right)
Query: Where left = ?
-> gebruikt Index

Index: (left, right)
Query: Where right = ?
-> gebruikt Index niet

Index: (left, right), right
Query: Where right = ?
-> gebruikt Index 2
Query: Where left = ?
-> gebruikt Index 1

Dit is wel te zien door een EXPLAIN voor je query te gooien.

Dus het is zodat als ik een index zet op left en right samen dat er geen losse index hoeft op left?

ACM schreef op zondag 30 juni 2013 @ 11:07:
Er zijn een aantal afwegingen die zinvol zijn om te besluiten of Nested Set (wat jij gebruikt met je left/right) wel de juiste methode is.

Hoe diep is je boom? Als ie nergens dieper dan bijvoorbeeld 2 of 3 is, dan kan je overwegen om het er helemaal uit te halen en altijd met joins/subqueries te werken.

Hoeveel elementen zitten er onder de "root" van je boom? Als er veel elementen direct onder je root zit, kan je overwegen om per element een losse subtree en dus losse Nested Set te beginnen. Overigens kan dit ook helpen als er maar een stuk of 4 nodes onder je root zitten, je hoeft dan alsnog maar worst case 1/4e van je dataset aan te passen per keer.

Wat voor data wil je uit je boom hebben? Wil je altijd alle elementen voor heel eenvoudig te bepalen en eenduidige subtrees hebben? Dan kan je overwegen om ook je Nested Set (gedeeltelijk) overboord te zetten, maar elk element een "subtree id" mee te geven naast het parentid. Afhankelijk van het aantal nodes dat je ophaalt kan je dat ook in het geheugen van je applicatie weer op de juiste manier aan elkaar koppelen.

Ben je genoodzaakt om MySQL te blijven gebruiken? O.a. PostgreSQL kent recursieve querymogelijkheden. Dan zou je nested set niet nodig hebben, maar via recursieve SQL in een keer alle elementen onder parentid X op kunnen halen.

Losse tree is inderdaad nog niet zo'n slecht idee. Er zitten op dit moment 10 direct onder de root. Dus dat zou ik kunnen overwegen. Nog niet aan gedacht. Maar voelt niet echt als een structurele oplossing aangezien ik nu 200.000 records heb en naar de 1.000.000 toe ga, zo niet meer.

Subtree_id is inderdaad een goed idee. Ga ik eens over nadenken. Is bijna net zo flexibel als je alles uit dezelfde diepte wilt hebben.

Ben niet genoodzaakt om mysql te gebruiken, maar heeft gezien mijn ervaring mysql wel de voorkeur. Ik ga eerst eens kijken naar subtree_id en aanpassingen in Innodb. Heb je daar nog advies voor? Zie Woef in "\[php/mysql] mptt performance, alternatief?"

[ACM]

Woef schreef op zondag 30 juni 2013 @ 14:00:
Dus het is zodat als ik een index zet op left en right samen dat er geen losse index hoeft op left?

Een losse index kost minder bytes per record en is daarmee in principe iets sneller uit te lezen. Maar een gecombineerde index is wel ook al partieel te gebruiken, dus het is daardoor over het algemeen niet enorm zinvol om nog die losse index te hanteren. Vooral omdat het weer extra werk kost voor je database om 'm bij te houden.

Losse tree is inderdaad nog niet zo'n slecht idee. Er zitten op dit moment 10 direct onder de root. Dus dat zou ik kunnen overwegen. Nog niet aan gedacht. Maar voelt niet echt als een structurele oplossing aangezien ik nu 200.000 records heb en naar de 1.000.000 toe ga, zo niet meer.

Nu moet je gemiddeld de helft van al je records aanpassen voor elke insert. Als je dat in 10-en hakt zijn wordt dat nog maar gemiddeld 1/20e. Dus dat kan wel degelijk zinvol zijn. Andere vormen van denormalisatie en/of partioneren van je boom zijn natuurlijk ook het overwegen waard.
Jij weet wat er in zit, wij niet. Dus we kunnen hooguit tips geven van manieren om er naar te kijken, jij zult er uiteindelijk de beste uit moeten pikken

Ben niet genoodzaakt om mysql te gebruiken, maar heeft gezien mijn ervaring mysql wel de voorkeur. Ik ga eerst eens kijken naar subtree_id en aanpassingen in Innodb. Heb je daar nog advies voor? Zie Woef in "\[php/mysql] mptt performance, alternatief?"

Er zijn veel tunables, maar de meesten zullen je geen gigantische verschillen opleveren. De bufferpool op een goede grootte instellen is inderdaad wel belangrijk. Wat een goede waarde is zul je wel zelf moeten bepalen.
Het heeft geen zin om een bufferpool van 25GB te maken als je database in totaal 1GB groot is, dus dan is die 110% van je datagrootte zinvol om aan te houden. Als je database echter veel groter is dan die 32GB aan RAM-geheugen die je hebt en je server doet alleen MySQL met InnoDB... dan is de tip van 70-80% relevant

[DexterDee]

Hoeveel niveau's diep heb je maximaal nodig? Als je dit tot een redelijk maximum kan beperken, dan kun je in plaats van spanning tree andere technieken gebruiken die schaalbaarder zijn in het schrijven en toch het lezen efficiënt houden.

Een techniek die ik met succes heb toegepast op een grote (1 miljoen+) nested dataset is de volgende (ik weet de officiële naam van het algoritme niet):

de nesting van je datastructuur leg je per record vast in vooraf gedefinieerde niveauvelden.

1, null, null -> root node [1]
1, 1, null -> child node van root node [1.1]
1, 1, 1 -> child van child node [1.1.1]
2, null, null -> tweede root node [2]

Delen van de boom kunnen eenvoudig en zonder subqueries opgevraagd worden. Alle niveauvelden kunnen in één index waardoor elk niveau vanuit de index op te vragen is. Ik heb dit model succesvol toegepast op een datamodel van 10 niveaus diep.

[GlowMouse]

Woef schreef op zondag 30 juni 2013 @ 01:14:
[...]

Net zoals de log files. Daar wordt ook wel van gezegd dan je die zo klein mogelijk moet houden?!

5 MB is veel te klein en zorgt voor veel meer disk i/o omdat writes minder goed gecombineerd kunnen worden.

http://www.mysqlperforman...ood-innodb-log-file-size/

[Verwijderd]

Is een mptt model hier eigenlijk wel nodig ?

mptt is in het geval van veel inserts/updates niet altijd het handigste model, zeker niet bij grote datasets.

Recentelijk kwam ik het model tegen die gebruik maakt van een closure table en dit lijkt me voor dit soort gevallen toch wel vrij handig

http://karwin.blogspot.nl...-with-closure-tables.html

[Zoijar]

DexterDee schreef op zondag 30 juni 2013 @ 16:12:
Een techniek die ik met succes heb toegepast op een grote (1 miljoen+) nested dataset is de volgende (ik weet de officiële naam van het algoritme niet):

Volgens mij is dat David Chandler's "algoritme". Rust alleen helaas patent op dus beetje uitkijken. http://www.google.com/patents/US6480857

---

Het is duidelijk dat als je veel inserts doet mptt om te beginnen een slechte keuze is. Lees zoiets http://www.slideshare.net...es-and-hierarchies-in-sql en probeer iets te vinden dat betere theoretische insert performance heeft. Je database settings aanpassen gaat dit nooit oplossen. Zoals je zelf al opmerkt schaalt mptt niet naar veel inserts in grote data.

[Verwijderd]

Zoijar schreef op maandag 01 juli 2013 @ 17:58:
[...]

Volgens mij is dat David Chandler's "algoritme". Rust alleen helaas patent op dus beetje uitkijken. http://www.google.com/patents/US6480857

Dit klinkt eigenlijk meer als een path-model ... wat best goed werkt behalve dat je dan de referentiele integriteit zelf in de gaten moet houden.

[Kettrick]

Voor de oplossing van je huidige probleem niet echt behulpzaam, maar als je al overweegt om een andere techniek te gebruiken kan je ook naar een graph database kijken. Hoewel ik nog weinig productie ervaring heb ben ik aardig onder de indruk van wat Neo4j doet op dit gebied

[Verwijderd]

Kettrick schreef op maandag 01 juli 2013 @ 18:15:
Voor de oplossing van je huidige probleem niet echt behulpzaam, maar als je al overweegt om een andere techniek te gebruiken kan je ook naar een graph database kijken. Hoewel ik nog weinig productie ervaring heb ben ik aardig onder de indruk van wat Neo4j doet op dit gebied

Dit kan inderdaad voor bepaalde problemen een oplossing zijn ... helaas heeft de TS nog niet echt vemeld wat nu precies het doel is van zijn opzet, dus dat is nogal lastig om te beoordelen of het uberhaupt logisch is om het in een tree / nested set te verwerken.

[Woef]

Bedankt voor jullie reacties, ik ben begonnen met het aanpassen van de innodb buffer pool size en de
innodb log file size. Ik houd jullie op de hoogte of dit voor mij de oplossing is.