MySQL, tags en performance

[GlowMouse]

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.

SQL:

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:

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:

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:

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:

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:

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:

$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:

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:

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:

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:

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]

[Wolfboy]

offtopic:
Hulde, ik vroeg me al af wanneer je dit topic zou starten

Een vraag waar ik al een tijdje mee in m'n hoofd zit, hoe goed zou het werken om een extra (of voor de veelgebruikte tag combinaties) 2 of meer niveau's diep te denormaliseren?

Als je toch al weet dat bepaalde tag combinaties vaak voorkomen, waarom niet die combinatie samen in een aparte tabel denormaliseren en daar een specifieke index voor maken

[edit]Ik mis even de informatie over hoeveel verschillende tags je hebt, dat heeft namelijk enorm veel invloed op de bovenstaande oplossing. Als je 10 tags voor 2 of 3 niveau's diep denormaliseert krijg je respectievelijk 45 en 120 combinaties.

Voer je datzelfde uit met 100 tags dan hebben we het opeens over 100, 4.950 en 161.700 combinaties.

[Voor 29% gewijzigd door Wolfboy op 11-10-2010 03:41]

[ACM]

Ik ben eigenlijk wel benieuwd hoe een database met intersect en/of geavanceerdere planningsmogelijkheden het doet met jouw 1e en 2e variant. Althans, een variant zonder straight_join dan, maar met een gewone inner join en laat de database maar uitzoeken welke variant ie het liefst doet.

Verder mis ik nog een variant, je kan namelijk ook iteratief een temporary table vullen met item-tag-informatie (van klein naar groot) en dan steeds met je (nieuwe) temporary table joinen tot je effectief de intersectie hebt opgebouwd. Dat kan wellicht voor weinig tags teveel overhead hebben, maar zorgt wel dat de join en sortering van je items-tabel voor je database een stuk eenvoudiger wordt.
En hier komt dan uiteraard SQL's INTERSECT-statement om de hoek kijken, dan zou je ditzelfde zonder expliciete temporary tables aan je database over kunnen laten.

[Voutloos]

Probeer methode 1 ook eens met een derived table welke enkel item_tags gebruikt om de set van item_id waardes te bepalen.

Dus:

SQL:

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

En zet van beide de explain hier neer. De subquery moet met een beetje creativiteit goede indexen kunnen gebruiken, en de buitenstenste query is zo sowieso al übersimpel.

[Voor 14% gewijzigd door Voutloos op 11-10-2010 19:51]

[GlowMouse]

Een vraag waar ik al een tijdje mee in m'n hoofd zit, hoe goed zou het werken om een extra (of voor de veelgebruikte tag combinaties) 2 of meer niveau's diep te denormaliseren?

Juist bij combinaties van veelgebruikte tags valt het voordeel weg, omdat dan methode 3 al snel zal zijn. In dit geval gaat het overigens om 3 site-tags (die aangeven of een artikel op de frontpage, games- of sportsite staan), en nog 59 categorie-tags.

ACM schreef op maandag 11 oktober 2010 @ 07:57:
En hier komt dan uiteraard SQL's INTERSECT-statement om de hoek kijken, dan zou je ditzelfde zonder expliciete temporary tables aan je database over kunnen laten.

MySQL kent alleen inner joins

_{in het weekend weer nieuwe benchmarkresultaten}

[Voor 3% gewijzigd door GlowMouse op 11-10-2010 23:19]

[Wolfboy]

GlowMouse schreef op maandag 11 oktober 2010 @ 23:19:
[...]

Juist bij combinaties van veelgebruikte tags valt het voordeel weg, omdat dan methode 3 al snel zal zijn. In dit geval gaat het overigens om 3 site-tags (die aangeven of een artikel op de frontpage, games- of sportsite staan), en nog 59 categorie-tags.

Zeker waar, al is het wel afhankelijk van het totaal aantal items dat je hebt. Bij heel veel items per tag zal het nog steeds een zware join worden.

MySQL kent alleen inner joins

Je kan het redelijk faken met EXISTS, geen idee of het helpt voor de performance overigens

_{in het weekend weer nieuwe benchmarkresultaten}

_{Welk weekend?}

[GlowMouse]

Ik zie nog niet hoe je zou intersecten. Exists gaat in ieder geval niet sneller zijn dan een join.

[ACM]

GlowMouse schreef op donderdag 23 december 2010 @ 21:15:
Ik zie nog niet hoe je zou intersecten.

Intersect kan niet in MySQL nee. Maar verder werkt het net zo simpel als Union.

Met EXISTS kan je het op zo'n soort manier aanpakken:

SQL:

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) 
...

Of met IN:

SQL:

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) 
...

[Voor 21% gewijzigd door ACM op 23-12-2010 21:31]

[cariolive23]

Waarom gebruik je een STRAIGHT_JOIN ? Ik zie nergens een resultaat van EXPLAIN waarin is te zien dat MySQL een verkeerd queryplan gebruikt en dat je MySQL met een STRAIGHT_JOIN wel de juiste kant opstuurt.

Zonder EXPLAIN wordt optimaliseren ook vrijwel onmogelijk...

[Wolfboy]

cariolive23 schreef op vrijdag 24 december 2010 @ 10:55:
Waarom gebruik je een STRAIGHT_JOIN ? Ik zie nergens een resultaat van EXPLAIN waarin is te zien dat MySQL een verkeerd queryplan gebruikt en dat je MySQL met een STRAIGHT_JOIN wel de juiste kant opstuurt.

Zonder EXPLAIN wordt optimaliseren ook vrijwel onmogelijk...

Lijkt me redelijk logisch. Hij zoekt eerst de cardinaliteit van de tags op dus een straight join zou het beste plan moeten geven

[GlowMouse]

cariolive23 schreef op vrijdag 24 december 2010 @ 10:55:
Waarom gebruik je een STRAIGHT_JOIN ? Ik zie nergens een resultaat van EXPLAIN waarin is te zien dat MySQL een verkeerd queryplan gebruikt en dat je MySQL met een STRAIGHT_JOIN wel de juiste kant opstuurt.

Zonder EXPLAIN wordt optimaliseren ook vrijwel onmogelijk...

Ik neem aan dat je weet hoe MySQL werkt, en op de eerste methode na zijn de execution plans triviaal. Bij de eerste methode zie je dat MySQL zelf de artikels die tag 1, 2, óf 3 heeft moet sorteren op item_id, vervolgens kijkt wat precies 3x voorkomt, en vervolgens weer moet sorteren op timestamp. Als één (of meer) van je tags erg vaak voor komt, zal de eerste sorteerstap relatief veel tijd kosten.
Ik gebruik STRAIGHT_JOIN omdat ik weet welke tag het minst voorkomt. De verwachting is dan dat wanneer je de artikels bij die tag sorteert, en vervolg wegstreept welke artikels niet tevens de andere twee tags hebben, je sneller klaar bent dan wanneer je begint met een meer voorkomende tag omdat je dan meer moet wegstrepen. Aangezien MySQL geen skewness-informatie beschikbaar heeft bij indices, kan ik betere beslissingen nemen dan MySQL.
_{binnen een week nieuwe resultaten}

[cariolive23]

GlowMouse schreef op vrijdag 24 december 2010 @ 11:58:
Ik gebruik STRAIGHT_JOIN omdat ik weet welke tag het minst voorkomt.

Als het goed is, weet MySQL dit ook en kiest MySQL dus automatisch voor het beste queryplan. STRAIGHT_JOIN heb je nodig wanneer MySQL volledig de mist in gaat, de verkeerde keuzes maakt. STRAIGHT_JOIN is dus niet meer dan een workaround. Het zou mij enigszins verbazen wanneer je dit hier nodig hebt, vandaar dat ik ook vraag naar de resultaten van EXPLAIN.

ANALYZE doet wonderen.

[GlowMouse]

De OP is bijgewerkt met alle nieuwe ideeën.

Voutloos schreef op maandag 11 oktober 2010 @ 19:49:
Probeer methode 1 ook eens met een derived table welke enkel item_tags gebruikt om de set van item_id waardes te bepalen.

Dus:

SQL:

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

En zet van beide de explain hier neer. De subquery moet met een beetje creativiteit goede indexen kunnen gebruiken, en de buitenstenste query is zo sowieso al übersimpel.

Hier het execution plan van methode 1 en van jouw methode wanneer er 2 tags zijn (bij 1 of 3 tags ziet het er ook zo uit):

Je ziet dat hij de middelste query ook hier niet efficiënt uit kan voeren. Het voordeel wordt behaald doordat de header nu niet meegenomen wordt bij de sorteerstap in de binnenste query.

[cariolive23]

In de gewijzigde OP heb je het 2x over de performance van een RIGHT JOIN. Deze gebruik je echter in geen enkel voorbeeld, je laat er niets van zien. Bedoel je soms een INNER JOIN (die je ook als JOIN mag noteren in de SQL) of zie ik iets over het hoofd?

[GlowMouse]

cariolive23 schreef op maandag 10 januari 2011 @ 18:15:
In de gewijzigde OP heb je het 2x over de performance van een RIGHT JOIN. Deze gebruik je echter in geen enkel voorbeeld, je laat er niets van zien. Bedoel je soms een INNER JOIN (die je ook als JOIN mag noteren in de SQL) of zie ik iets over het hoofd?

Dat is een foutje inderdaad, aangepast.