Tags waren eerst te vinden bij blogs, maar zijn inmiddels ook te zien op nieuwssites en op fora als GoT. Voor elke combinatie van tags moet er een lijst met artikels getoond kunnen worden die op tijd gesorteerd is, en dat is lastig voor een databaseserver. Ik wil een aantal opties bekijken en hoop dat er andere users zijn met betere ideeën. Eenvoudig gezegd zijn er voor een databaseserver bij een genormaliseerde database twee opties:
1) ga alle artikels op datum gesorteerd af, en kijk welke er van de genoemde tags zijn voorzien
2) pak voor elke tag de artikels die de betreffende tag hebben, pak de intersectie, sorteer die op datum
Bij veelvoorkomende tagcombinaties zal de eerste methode sneller zijn, bij tags die slechts enkele keren zijn gebruikt, is de tweede methode in het voordeel. Omdat de query optimizer in MySQL hier geen rekening mee houdt, moet de logica in de applicatie zitten. Denormalisatie kan daarbij veel helpen.
Ik vergelijk MySQL met zoeksoftware Sphinx. Sphinx is tegenwoordig realtime te updaten, zodat er geen verschillen optreden ten opzichte van een pure MySQL-situatie om op tag te zoeken, is te benaderen als ware het een MySQL-server, hoewel er ook een PHP API is die iets meer flexibiliteit biedt bij het zoeken, en is bovendien gratis. Wel ontbreekt een rechtenchecksysteem, zodat het geen oplossing is bij shared hosting.
Ik ga uit van de volgende situatie:
- reads komen veel vaker voor dan writes; denormaliseren is dus niet erg
- ik beperk me tot MySQL met getweakte InnoDB storage engine zonder query cache (ik gebruik MySQL 5.1.50 met xtradb 1.0.6-10.2-89)
- het testsysteem bevat een Xeon 3070 (Conroe 2.66 GHz) met 2GB geheugen en 7200rpm sata disk (tijdens de benchmarks wordt van de disk niet of nauwelijks gelezen)
- de testdata komt van (frontpage|games|sport).fok.nl; als tags heb ik de sites en de categorieën waarop/waarin het artikel staat. Elk artikel heeft daarom minimaal twee tags. De verdeling is erg scheef, want de tag die aangeeft dat een artikel op frontpage.fok.nl voorkomt, zal heel veel vaker gekoppeld zijn aan een artikel dan de tag die aangeeft dat het gaat om een muziekgerelateerd artikel.
- de connectie met MySQL staat al open, die met Sphinx niet; dat zal voor veel sites ook de standaardsituatie zijn; connecten naar sphinx blijkt overigens niet van grote invloed op de meetresultaten
- ik benchmark met php en singlethreaded
De testdata heb ik omgezet in deze lay-out.
De tabel items_tags heeft een covering index.
Dat er een koppeling tussen tag en tag_id bestaat, is niet zo interessant. Ik bekijk daarom alleen de eerste twee tabellen.
Aantal records:
items: 285389
items_tags 580218
Methoden
Ik heb zelf vijf methoden geselecteerd om gegeven een stel tag_ids de bijbehorende headers gesorteerd op tijd op te vragen:
methode 1
methode 2
gelijk aan methode 1 als er naar meerdere tags gezocht wordt, draai anders deze query:
Deze methode maakt gebruik van de denormalisatie van timestamp als er op één tag wordt gezocht. Hij kan in 1x de 10 gezochte rijen opzoeken.
methode 3
gelijk aan methode 2 als er één tag gezocht wordt, anders:
kijk anders eerst welke tag het minst voorkomt:
Stel dat 1 het minst vaak voorkomt, draai dan deze query:
Deze methode maakt ook gebruik van de denormalisatie van timestamp als er op meerdere tags wordt gezocht. Hij gaat bij de minstvoorkomende tag alle artikels af op volgorde van tijdstip, en stopt zodra hij 10 artikels heeft gevonden die ook alle overige tags aan zich gekoppeld hebben.
methode 4
maak verbinding met Sphinx via mysql_connect, en draai deze query (de AND lijkt vreemd, maar werkt goed bij een multi value attribute veld):
methode 5
maak verbinding met Sphinx via de meegeleverde API.
methode ACM1
Hier hangt de subquery af van i.itemid, zodat een groot aantal items zorgt voor een groot aantal uit te voeren subqueries.
methode ACM2
De joins worden door MySQL herschreven naar het type unique_subquery. Het gevolg is dat er voor elk item een index look-up plaatsvindt. Een groot aantal items zorgt voor een groot aantal uit te voeren index look-ups.
methode Voutloos
Deze methode lijkt op methode 1, alleen wordt de header nu niet meegenomen bij de binnenste query. In de binnenste query wordt een sorteerstap uitgevoerd, die nu vaker in het geheugen uitgevoerd kan worden
methode ACM/cariolive23
MySQL bepaalt hier zelf de optimale joinvolgorde. Vaak wordt er op t1, t2 of t3 gejoined, zodat de sortering op timestamp handmatig gedaan moet worden.
Benchmarkresultaten
Allereerst de single-tag look-up gesorteerd op timestamp. Elk van de 62 tags vraag ik precies één keer op, en de tijd die ze daar in totaal over doen, wordt gemeten. Om de resultaten tussen single/multi-tagzoekopdrachten te vergelijken, schaal ik de resultaten naar de situatie waarin ik 1000x een zoekopdracht uitvoer (totale tijd * 1000/62).
Methode 1: 60 s
Methode 2/3: 113 ms
Methode 4/5: 10.5 s
ACM1: 961 s
ACM2: 830 s
Voutloos: 24 s
ACM/cariolive23: 10 s
Daarna de double-tag resultaten. Hierbij laat ik 1 tag corresponderen met een site (frontpage/sport/games), en 1 tag met een categorie. Elke combinatie vraag ik precies één keer op, en de tijd die ze daar in totaal over doen, wordt gemeten. Om de resultaten tussen single/multi-tagzoekopdrachten te vergelijken, schaal ik de resultaten naar de situatie waarin ik 1000x een zoekopdracht uitvoer (totale tijd * 1000/(62^2)).
Methode 1/2: 31 s
Methode 3: 709 ms
Methode 4/5: 400 ms
ACM1: 40 s
ACM2: 35 s
Voutloos: 4,5 s
ACM/cariolive23: 482 ms
Tot slot de random-tag resultaten. Ik genereer uniform een willekeurig natuurlijk getal n, 1<=n<=5, daarna genereer ik precies n tag_id's uniform willekeurig tussen 1 en 62, niet noodzakelijkerwijs verschillend. Elke methode krijgt dezelfde tags te verwerken, en dat herhaal ik 1000 keer en ik meet de totale tijd.
Methode 1: 64 s
Methode 2: 177 ms
Methode 3: 119 ms
Methode 4/5: 11 s
ACM1: 996 s
ACM2: 852 s
Voutloos: 24 s
ACM/cariolive23: 10 s
Conclusies
- Denormaliseren helpt bij één tag, maar bij meerdere tags moet er wat extra logica in de applicatie zitten.
- Een gewone inner join is erg snel wanneer denormalisatie niet direct helpt
- IN is iets sneller dan EXISTS, maar omdat de subqueries per item worden uitgevoerd, is de methode erg traag
- Sphinx is makkelijk te gebruiken, maar bij dit simpele werk even snel als een inner join
- De manier van verbinden naar Sphinx maakt niet uit.
Als er users met andere goede ideeën komen, zal ik die in de OP verwerken.
1) ga alle artikels op datum gesorteerd af, en kijk welke er van de genoemde tags zijn voorzien
2) pak voor elke tag de artikels die de betreffende tag hebben, pak de intersectie, sorteer die op datum
Bij veelvoorkomende tagcombinaties zal de eerste methode sneller zijn, bij tags die slechts enkele keren zijn gebruikt, is de tweede methode in het voordeel. Omdat de query optimizer in MySQL hier geen rekening mee houdt, moet de logica in de applicatie zitten. Denormalisatie kan daarbij veel helpen.
Ik vergelijk MySQL met zoeksoftware Sphinx. Sphinx is tegenwoordig realtime te updaten, zodat er geen verschillen optreden ten opzichte van een pure MySQL-situatie om op tag te zoeken, is te benaderen als ware het een MySQL-server, hoewel er ook een PHP API is die iets meer flexibiliteit biedt bij het zoeken, en is bovendien gratis. Wel ontbreekt een rechtenchecksysteem, zodat het geen oplossing is bij shared hosting.
Ik ga uit van de volgende situatie:
- reads komen veel vaker voor dan writes; denormaliseren is dus niet erg
- ik beperk me tot MySQL met getweakte InnoDB storage engine zonder query cache (ik gebruik MySQL 5.1.50 met xtradb 1.0.6-10.2-89)
- het testsysteem bevat een Xeon 3070 (Conroe 2.66 GHz) met 2GB geheugen en 7200rpm sata disk (tijdens de benchmarks wordt van de disk niet of nauwelijks gelezen)
- de testdata komt van (frontpage|games|sport).fok.nl; als tags heb ik de sites en de categorieën waarop/waarin het artikel staat. Elk artikel heeft daarom minimaal twee tags. De verdeling is erg scheef, want de tag die aangeeft dat een artikel op frontpage.fok.nl voorkomt, zal heel veel vaker gekoppeld zijn aan een artikel dan de tag die aangeeft dat het gaat om een muziekgerelateerd artikel.
- de connectie met MySQL staat al open, die met Sphinx niet; dat zal voor veel sites ook de standaardsituatie zijn; connecten naar sphinx blijkt overigens niet van grote invloed op de meetresultaten
- ik benchmark met php en singlethreaded
De testdata heb ik omgezet in deze lay-out.
SQL:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| CREATE TABLE `items` ( `item_id` int(10) unsigned NOT NULL AUTO_INCREMENT, `userId` mediumint(8) unsigned NOT NULL DEFAULT '0', `header` varchar(150) NOT NULL DEFAULT '', `body` text NOT NULL, `timestamp` int(11) unsigned NOT NULL DEFAULT '0', PRIMARY KEY (`item_id`), KEY (`timestamp`) ) ENGINE=InnoDB; CREATE TABLE `items_tags` ( `item_id` int(10) unsigned NOT NULL, `tag_id` int(10) unsigned NOT NULL, `timestamp` int(10) unsigned NOT NULL, UNIQUE KEY (`item_id`,`tag_id`), KEY (`tag_id`,`timestamp`,`item_id`) ) ENGINE=InnoDB; CREATE TABLE `tags` ( `tag_id` int(10) unsigned NOT NULL AUTO_INCREMENT, `tag` varchar(60) NOT NULL, `count` mediumint(8) unsigned NOT NULL, PRIMARY KEY (`tag_id`), UNIQUE KEY `tag` (`tag`) ) ENGINE=InnoDB; |
De tabel items_tags heeft een covering index.
Dat er een koppeling tussen tag en tag_id bestaat, is niet zo interessant. Ik bekijk daarom alleen de eerste twee tabellen.
Aantal records:
items: 285389
items_tags 580218
Methoden
Ik heb zelf vijf methoden geselecteerd om gegeven een stel tag_ids de bijbehorende headers gesorteerd op tijd op te vragen:
methode 1
SQL:
1
2
3
4
5
6
7
| SELECT i.header FROM items i JOIN items_tags it USING(item_id) WHERE it.tag_id IN(1,2,3) GROUP BY i.item_id HAVING count(*) = 3 ORDER BY i.timestamp DESC LIMIT 10 |
methode 2
gelijk aan methode 1 als er naar meerdere tags gezocht wordt, draai anders deze query:
SQL:
1
2
3
4
5
| SELECT i.header FROM items i JOIN items_tags it USING(item_id) WHERE it.tag_id = 1 ORDER BY it.timestamp DESC LIMIT 10 |
Deze methode maakt gebruik van de denormalisatie van timestamp als er op één tag wordt gezocht. Hij kan in 1x de 10 gezochte rijen opzoeken.
methode 3
gelijk aan methode 2 als er één tag gezocht wordt, anders:
kijk anders eerst welke tag het minst voorkomt:
SQL:
1
2
3
| SELECT tag_id FROM tags WHERE count=( SELECT MIN(count) FROM tags WHERE tag_id IN(1,2,3) ) LIMIT 1 |
Stel dat 1 het minst vaak voorkomt, draai dan deze query:
SQL:
1
2
3
4
5
6
7
| SELECT i.header FROM items_tags it STRAIGHT_JOIN items i ON(i.item_id=it.item_id) STRAIGHT_JOIN items_tags it1 ON(it1.tag_id=2 AND it.item_id=it1.item_id) STRAIGHT_JOIN items_tags it2 ON(it2.tag_id=3 AND it.item_id=it2.item_id) WHERE it.tag_id=1 ORDER BY it.timestamp DESC LIMIT 10 |
Deze methode maakt ook gebruik van de denormalisatie van timestamp als er op meerdere tags wordt gezocht. Hij gaat bij de minstvoorkomende tag alle artikels af op volgorde van tijdstip, en stopt zodra hij 10 artikels heeft gevonden die ook alle overige tags aan zich gekoppeld hebben.
methode 4
maak verbinding met Sphinx via mysql_connect, en draai deze query (de AND lijkt vreemd, maar werkt goed bij een multi value attribute veld):
SQL:
1
2
3
4
| SELECT header FROM test1 WHERE tags = 1 AND tags = 2 AND tags = 3 ORDER BY timestamp DESC LIMIT 10 |
methode 5
maak verbinding met Sphinx via de meegeleverde API.
PHP:
1
2
3
4
5
6
7
8
9
| $cl = new SphinxClient(); $cl->SetServer('localhost', 3307); $cl->SetMatchMode( SPH_MATCH_ALL ); $cl->SetLimits( 0, 10 ); $cl->SetSortMode( SPH_SORT_EXPR, 'timestamp'); $cl->SetFilter('tags', array(1)); $cl->SetFilter('tags', array(2)); $cl->SetFilter('tags', array(3)); $res = $cl->Query('', 'indexnaam'); |
methode ACM1
SQL:
1
2
3
4
5
6
7
| SELECT header FROM items i WHERE EXISTS(select * from items_tags t where tagid = 1 and t.itemid = i.itemid) AND EXISTS(select * from items_tags t where tagid = 2 and t.itemid = i.itemid) AND EXISTS(select * from items_tags t where tagid = 3 and t.itemid = i.itemid) LIMIT 10 |
Hier hangt de subquery af van i.itemid, zodat een groot aantal items zorgt voor een groot aantal uit te voeren subqueries.
methode ACM2
SQL:
1
2
3
4
5
6
| SELECT header FROM items i WHERE itemid IN (select itemid from items_tags t where tagid = 1) AND itemid IN (select itemid from items_tags t where tagid = 2) AND itemid IN (select itemid from items_tags t where tagid = 3) |
De joins worden door MySQL herschreven naar het type unique_subquery. Het gevolg is dat er voor elk item een index look-up plaatsvindt. Een groot aantal items zorgt voor een groot aantal uit te voeren index look-ups.
methode Voutloos
SQL:
1
2
3
4
5
6
7
8
9
10
11
| SELECT i.header FROM items i INNER JOIN ( SELECT item_id FROM items_tags it WHERE it.tag_id IN(1,2,3) GROUP BY it.item_id HAVING count(*) = 3 ) selected_items USING (item_id) ORDER BY i.timestamp DESC LIMIT 10 |
Deze methode lijkt op methode 1, alleen wordt de header nu niet meegenomen bij de binnenste query. In de binnenste query wordt een sorteerstap uitgevoerd, die nu vaker in het geheugen uitgevoerd kan worden
methode ACM/cariolive23
SQL:
1
2
3
4
5
6
7
8
| SELECT header FROM items i JOIN items_tags t1 USING(item_id) JOIN items_tags t2 USING(item_id) JOIN items_tags t3 USING(item_id) WHERE t1.tag=1 AND t2.tag=2 AND t3.tag=3 ORDER BY i.timestamp DESC LIMIT 10 |
MySQL bepaalt hier zelf de optimale joinvolgorde. Vaak wordt er op t1, t2 of t3 gejoined, zodat de sortering op timestamp handmatig gedaan moet worden.
Benchmarkresultaten
Allereerst de single-tag look-up gesorteerd op timestamp. Elk van de 62 tags vraag ik precies één keer op, en de tijd die ze daar in totaal over doen, wordt gemeten. Om de resultaten tussen single/multi-tagzoekopdrachten te vergelijken, schaal ik de resultaten naar de situatie waarin ik 1000x een zoekopdracht uitvoer (totale tijd * 1000/62).
Methode 1: 60 s
Methode 2/3: 113 ms
Methode 4/5: 10.5 s
ACM1: 961 s
ACM2: 830 s
Voutloos: 24 s
ACM/cariolive23: 10 s
Daarna de double-tag resultaten. Hierbij laat ik 1 tag corresponderen met een site (frontpage/sport/games), en 1 tag met een categorie. Elke combinatie vraag ik precies één keer op, en de tijd die ze daar in totaal over doen, wordt gemeten. Om de resultaten tussen single/multi-tagzoekopdrachten te vergelijken, schaal ik de resultaten naar de situatie waarin ik 1000x een zoekopdracht uitvoer (totale tijd * 1000/(62^2)).
Methode 1/2: 31 s
Methode 3: 709 ms
Methode 4/5: 400 ms
ACM1: 40 s
ACM2: 35 s
Voutloos: 4,5 s
ACM/cariolive23: 482 ms
Tot slot de random-tag resultaten. Ik genereer uniform een willekeurig natuurlijk getal n, 1<=n<=5, daarna genereer ik precies n tag_id's uniform willekeurig tussen 1 en 62, niet noodzakelijkerwijs verschillend. Elke methode krijgt dezelfde tags te verwerken, en dat herhaal ik 1000 keer en ik meet de totale tijd.
Methode 1: 64 s
Methode 2: 177 ms
Methode 3: 119 ms
Methode 4/5: 11 s
ACM1: 996 s
ACM2: 852 s
Voutloos: 24 s
ACM/cariolive23: 10 s
Conclusies
- Denormaliseren helpt bij één tag, maar bij meerdere tags moet er wat extra logica in de applicatie zitten.
- Een gewone inner join is erg snel wanneer denormalisatie niet direct helpt
- IN is iets sneller dan EXISTS, maar omdat de subqueries per item worden uitgevoerd, is de methode erg traag
- Sphinx is makkelijk te gebruiken, maar bij dit simpele werk even snel als een inner join
- De manier van verbinden naar Sphinx maakt niet uit.
Als er users met andere goede ideeën komen, zal ik die in de OP verwerken.
[ Voor 13% gewijzigd door GlowMouse op 10-01-2011 21:58 ]