[MySQL] optimaliseren van deze select

[Genoil]

Dit komt eigenlijk uit een ander topic van gisteren, maar ik heb er nu een nieuwe vraag over:

Ik ben bezig met het (her-)schrijven van wat ik mijn 'hypertree' noem. Kort gezegd is het een soort boomstructuur waarbij elke 'node' niet alleen meedere 'childnodes' kan hebben, maar ook meerdere 'parentnodes'. Bijbehorende (SQL-) databasestructuur bevat aldus een node tabel (id, name) en een relation tabel (id, parent_id, child_id).

Ook al zijn er meerdere parents per node, over het algemeen loop ik de tree hierarchisch naar beneden af (behalve op de huidig door de user geselecteerde node). De query voor het verkrijgen van de child nodes op de node 'root' (id=1), is aldus:

SELECT node.* FROM node, relation WHERE relation.child_id = node.id AND relation.parent_id = 1

Ik heb een twee-koloms index gemaakt (genaamd parent_child) op de relation-table, met parent_id en child_id als kolommen.

De EXPLAIN resultaten van de query geven een read order weer van 1. relation, 2. node. De read op relation maakt gebruik van m'n key, is van type 'ref' (wat volgens de manual goed is, aangezien er niet echt veel matches zullen zijn per query?). De read op node is van type ALL (niet goed), gebruikt geen key. Dit is een redelijk stukje geoptimaliseerd, daar het aantal te scannen relations drastisch afneemt vanwege het gebruik van de index. Maar hij moet steeds ALLe nodes langs fietsen, (using where) Het heeft schijnbaar geen zin om naast de PRIMARY een extra index te bouwen op node.id, het blijft ALL.

Maak ik de query als volgt:

SELECT node.* FROM node, relation WHERE relation.child_id = node.id AND relation.parent_id = 1 ORDER BY node.object_id ASC, node.name ASC

(want dat wil ik nou eenmaal)

dan krijg ik ineens een andere read-volgorde: node, relation. De read op node word nog 'duurder', want hij doet een file-sort (die krijg ik ook niet weg, wat voor indices ik ook op object_id en name zet). Maar de read op relation word ook ineens anders. Waar de 'ref' column in het EXPLAIN resultaat in het eerste geval 'const' was, is het nu 'const, node.id' en het aantal rows dattie moet examinen is nog lager.

Vragen:

Is er nou echt geen mogelijkheid om de node tabel dusdanig te indexeren dat die voor deze queries niet de hele node tabel door hoeft te fietsen?

Wat betekent nou dat 'const, node.id'? Ik heb nu (als test) een relation tabel met 9 records, waarvan er 3 matchen aan bovenstaande queries. In de eerste query had ik in het EXPLAIN resultaat 3 examined rows, in de tweede query 1 examined row. Hoe moet ik dit nou precies rijmen?

Ik las ergens dat het indexeren van columns waarop gesorteerd moet worden ook kan helpen. Ik krijg echter geen resultaten. Hoe zit dat dan precies?

[Olaf van der Spek]

Welke index heb je op de node table?
Misschien is het handig describes van de tables (en misschien ook de explain) te posten.

[ACM]

Genoil schreef op 11 februari 2003 @ 18:57:
SELECT node.* FROM node, relation WHERE relation.child_id = node.id AND relation.parent_id = 1

Ik heb een twee-koloms index gemaakt (genaamd parent_child) op de relation-table, met parent_id en child_id als kolommen.

Twee varianten die je kan proberen:

code:

select node.* from relation join node on node.id = relation.child_id where relation.parent_id  = 1

Hierbij geef je expliciet op hoe je de node en relation tabel aan elkaar geknoopt wil hebben wat soms een ander query plan op zou mogen leveren.
Een andere:

code:

SELECT node.* FROM node, relation WHERE node.id = relation.child_id  AND relation.parent_id = 1

Je hebt kans dat de planner de node.id vs relation.child_id een beetje gek oppakt en daardoor niet de index denkt te kunnen gebruiken.

Verder is de explain zelf zinvol en de tabel beschrijving ook natuurlijk

[Genoil]

oja sorrie hier dan:

code:

CREATE TABLE node (
  id int(10) unsigned NOT NULL auto_increment,
  name varchar(255) NOT NULL default '',
  object_class varchar(255) default NULL,
  object_id int(10) unsigned default NULL,
  PRIMARY KEY  (id),
) TYPE=MyISAM;

CREATE TABLE relation (
  id int(10) unsigned NOT NULL auto_increment,
  parent_id int(10) unsigned NOT NULL default '0',
  child_id int(10) unsigned NOT NULL default '0',
  depth int(10) unsigned NOT NULL default '0',
  PRIMARY KEY  (id),
  KEY parent_child (parent_id,child_id)
) TYPE=MyISAM;

(ben ze nu ook aan het omkitten naar InnoDB, maar dat heeft hier verder weinig mee van doen, toch?)

En de explains. Ik heb nu toevallig een nauwelijks gevulde database met 4 nodes (root met id=1 + 3 children) en 9 relaties, die de 3 resultaten van deze query oplevereb. De rest zijn cross-relaties tussen de children, die er verder niet veel toe doen.

code:

EXPLAIN SELECT node.* FROM node, relation WHERE relation.child_id = node.id AND relation.parent_id = 1

table    type  possible_keys  key           key_len  ref    rows  Extra  
relation ref   parent_child   parent_child  4        const  3     where used; Using index 
node     ALL   PRIMARY        NULL          NULL     NULL   4     where used

code:

EXPLAIN SELECT node.* FROM node, relation WHERE relation.child_id = node.id AND relation.parent_id = 1 
ORDER BY node.object_id ASC, node.name ASC

table    type  possible_keys  key           key_len  ref             rows  Extra
node     ALL   PRIMARY        NULL          NULL     NULL            4     Using filesort 
relation ref   parent_child   parent_child  8        const,node.id   1     where used; Using index

En de suggestties van ACM:

code:

select node.* from relation join node on node.id = relation.child_id where relation.parent_id  = 1

You have an error in your SQL syntax near 'on node.id = relation.child_id where relation.parent_id  = 1' at line 1

ik heb maar even een LEFT JOIN van gemaakt en dit levert mooie dingen op:

code:

explain select node.* from relation left join node on node.id = relation.child_id where relation.parent_id  = 1

table    type   possible_keys   key          key_len ref               rows Extra  
relation ref    parent_child    parent_child 4       const             3    where used; Using index 
node     eq_ref PRIMARY         PRIMARY      4       relation.child_id 1

ACM's laatse suggestie levert hetzelfde op al mijn eerste poging. Maar damn die eerste is uber-optimaal, max x examines per query waar x = het aantal children van een node!

Wanneer ik nou gaan ORDERen op bv ORDER by node.name ASC, krijg ik in het extra veld van de relation-row het volgende: "where used; Using index; Using temporary; Using filesort". Het lijkt wel alsof ik niet echt om temporaries en filesorts heen kan bij ORDERs. Maar waarom nou ineens in de relation-node? Of betekent dit dattie eerst alles doet zoals zonder de ORDER, en daarna ff een temp tabelletje met x joint-rows aanmaakt en die ff snel sorteert? Dat zou niet zo 'duur' zijn, toch?

Dit is leuk!

[ACM]

Mysql is niet echt een held met sorteren, zodra ie achterstevoren moet sorteren gebruikt ie bijv _altijd_ een filesort

En waarom mysql het nodig vindt een imho volledig legale join te weigeren is me een raadsel, zo werkt ie iig zeker weten in postgres en volgens mij staat ie zo in de specs, maar die ken ik niet uit mijn hoofd
Left join is namelijk niet helemaal hetzelfde als een gewone join.

[Genoil]

ACM schreef op 11 February 2003 @ 22:40:
Mysql is niet echt een held met sorteren, zodra ie achterstevoren moet sorteren gebruikt ie bijv _altijd_ een filesort

En waarom mysql het nodig vindt een imho volledig legale join te weigeren is me een raadsel, zo werkt ie iig zeker weten in postgres en volgens mij staat ie zo in de specs, maar die ken ik niet uit mijn hoofd
Left join is namelijk niet helemaal hetzelfde als een gewone join.

Kep het ff opgezocht. Je mag in MySQL geen a JOIN b ON doen, dan moet je gewoon a JOIN b WHERE doen. Maarja dan haal ik niet zo'n goed resultaat met EXPLAIN (zelfde als mijn 1e). HECK, het werkt

Ik ben nu ook een beetje aan het prutsen met InnoDB en FOREIGN KEYs. volgens mij heb ik em nu wel zo optimaal mogelijk:

code:

CREATE TABLE relation (
  id int(10) unsigned NOT NULL auto_increment,
  parent_id int(10) unsigned default NULL,
  child_id int(10) unsigned default NULL,
  depth int(10) unsigned default NULL,
  PRIMARY KEY  (id),
  KEY parent_child (parent_id,child_id),
  KEY child_parent (child_id,parent_id),
  FOREIGN KEY (parent_id) REFERENCES node (id) ON DELETE CASCADE,
  FOREIGN KEY (child_id) REFERENCES node (id) ON DELETE CASCADE
) TYPE=InnoDB;

[SJR]

Genoil schreef op 11 February 2003 @ 23:13:
Kep het ff opgezocht. Je mag in MySQL geen a JOIN b ON doen, dan moet je gewoon a JOIN b WHERE doen. Maarja dan haal ik niet zo'n goed resultaat met EXPLAIN (zelfde als mijn 1e). HECK, het werkt

Hmm... waar heb je dat gevonden? Bij oudere versies van MySQL is het inderdaad zo dat alleen LEFT (RIGHT/etc) JOINs een ON conditie ondersteunen en een INNER JOIN niet. Dit is echter een aantal versies geleden al verholpen, en een "a [INNER] JOIN b ON a.c=b.c" werkt hier gewoon. Bedoel je misschien dat het wel werkt, maar dat MySQL er niet voor optimaliseert?

[Olaf van der Spek]

Ik denk dat je inner erbij moet zetten. Zonder inner mag je geen join-conditie gebruiken (maak ik op uit deze posts).
Maar in de manual staat vrij duidelijk precies wat wel en niet mag.

Kun je die filesort niet voorkomen door in de query aan te geven dat het om een klein resultaat gaat?

[ Voor 23% gewijzigd door Olaf van der Spek op 12-02-2003 11:10 ]

[Glock]

Het lijkt wel alsof ik niet echt om temporaries en filesorts heen kan bij ORDERs.

jawel hoor, alleen ben je genoodzaakt om zelf een sorting tabel bij te houden.
In principe doe je nu van te voren wat mysql bij het uitvoeren van de query zou doen. Het is rete snel met zo'n sorting tabel maar je moet maar wel zin hebben om je query klein beetje aan te passen

edit:
Of je moet gewoon net zoals op GoT hierzo heel veel geheugen toekennen aan MySQL hoewel dat af en toe nog steeds niet genoeg geheugen is

Edit 2:
En nog eventjes een voorbeeldquery uit m'n forum om het maar eventjes wat duidelijker te maken wat ik precies bedoel, ben em hierboven nog niet tegengekomen.

code:

SELECT p.post_time, p.post_text, u.user_name, u.user_sig, u.user_title
FROM posts_sort s
LEFT JOIN posts p ON p.post_id = s.post_id
LEFT JOIN users u ON u.user_id = p.post_user
WHERE s.post_topic = 1
ORDER BY s.post_id LIMIT 0,50

Edit 3:
Dan ook nog maar de tabel structuur erbij

Posts:

code:

CREATE TABLE posts (
  post_id int(10) unsigned NOT NULL default '0',
  .........
  post_text text NOT NULL,
  PRIMARY KEY  (post_id)
) TYPE=MyISAM;

Posts_Sort:

code:

CREATE TABLE posts_sort (
  post_id int(10) unsigned NOT NULL auto_increment,
  post_topic int(10) unsigned NOT NULL default '0',
  PRIMARY KEY  (post_id),
  KEY post_topic (post_topic,post_id)
) TYPE=MyISAM;

Edit 4:
Ja, ik ben lekker bezig
Ook nog maar de EXPLAIN erbij (Een topic van 25003 posts, standaard MySQL 4 installatie, Athlon XP 1800+, 512 MB Geheugen, Windows XP)

code:

s ref post_topic post_topic 4 const 25003 where used; Using index 
p eq_ref PRIMARY PRIMARY 4 s.post_id 1   
u eq_ref PRIMARY PRIMARY 4 p.post_user 1

Benodigde tijd: 0.00150299072266 sec. (windows he )

[ Voor 100% gewijzigd door Glock op 12-02-2003 11:46 ]

[Genoil]

OlafvdSpek schreef op 12 February 2003 @ 10:54:
Ik denk dat je inner erbij moet zetten. Zonder inner mag je geen join-conditie gebruiken (maak ik op uit deze posts).
Maar in de manual staat vrij duidelijk precies wat wel en niet mag.

Kun je die filesort niet voorkomen door in de query aan te geven dat het om een klein resultaat gaat?

Inderdaad het werkt wel met INNER JOIN. Maar het is gewoon niet zo optimaal als een LEFT JOIN. Ik wou dat ik het snapte..

Hoe geeft ik dat dan in de query aan dat het resultaat klein is? En strikt genomen hoeft het resultaat niet klein te zijn, in principe is mogelijk duizenden nodes onder 1 parent te hangen natuurlijk...

@ laatste poster:
Als je zo'n sorting tabel bijhoudt, wanneer werk je die dan bij? Daarnaast moet ik sorteren per niveau in de tree, en nodes kunnen op verschillende niveau's op verschillende gesorteerde plaatsen terecht komen...dus dat wordt pittig denk ik

[Glock]

Genoil schreef op 12 februari 2003 @ 11:55:
@ laatste poster:
Als je zo'n sorting tabel bijhoudt, wanneer werk je die dan bij? Daarnaast moet ik sorteren per niveau in de tree, en nodes kunnen op verschillende niveau's op verschillende gesorteerde plaatsen terecht komen...dus dat wordt pittig denk ik

Die werk je bij wanneer je een nieuw record invoegd. Het is niks anders als een tabel waarbij hetgene waarop moet worden gesorteerd in een aparte tabel word bijgehouden. Doordat de tabel nu geen andere velden bevat wat niet relevant is voor het sorteren heb je dus bij het sorteren ook minder geheugen nodig. En het aantal tree's en niveau's maakt allemaal niet uit, een opzet valt altijd prima te bedenken.

[Genoil]

Glock schreef op 12 februari 2003 @ 12:25:
[...]

Die werk je bij wanneer je een nieuw record invoegd. Het is niks anders als een tabel waarbij hetgene waarop moet worden gesorteerd in een aparte tabel word bijgehouden. Doordat de tabel nu geen andere velden bevat wat niet relevant is voor het sorteren heb je dus bij het sorteren ook minder geheugen nodig. En het aantal tree's en niveau's maakt allemaal niet uit, een opzet valt altijd prima te bedenken.

oja tis natuurlijk niet meer dan een tabel die even groot is als de moeder-tabel, met 1 numeriek veld die de gesorteerde plek aangeeft (ongeacht de complexiteit van je ORDER). maar als ik dan een tree heb met duizenden nodes, worden de bewerkingsacties op de tree wel weer een stukje trager. Maarja daar zijn er altijd veel minder van dan lees-acties. bedankt voor de tip!

[Olaf van der Spek]

Genoil schreef op 12 februari 2003 @ 11:55:
Hoe geeft ik dat dan in de query aan dat het resultaat klein is? En strikt genomen hoeft het resultaat niet klein te zijn, in principe is mogelijk duizenden nodes onder 1 parent te hangen natuurlijk...

SQL_SMALL_RESULT, a MySQL-specific option, can be used with GROUP BY or DISTINCT to tell the optimiser that the result set will be small. In this case, MySQL will use fast temporary tables to store the resulting table instead of using sorting. In MySQL Version 3.23 this shouldn't normally be needed.

Maar ik weet dus niet zeker of dit werkt.