Využití vícesloupcového indexu

Školení, která pořádám

Pokud máme v dotazu podmínku i = ? AND j = ? a máme definované indexy (i) a (j), tak je MySQL dokáže za určitých okolností využít oba. Výhodnější je ale nadefinovat jeden vícesloupcový index (i, j). Proč?

Řekněme, že je v tabulce tisíc záznamů, podmínku i = ? splní sto z nich, podmínku j = ? také sto z nich a průnik podmínek padesát záznamů. S jedním indexem se provede O(log(N)) porovnání (tedy řádově 4) a 50 operací se použije na vrácení vyhovujících záznamů, celkem tedy 54 operací. Při dvou indexech je potřeba strom indexů projít dvakrát (řádově 8 operací) a z vrácených množin je potřeba zjistit průnik (celkem 100 + 100 operací), celkem tedy 208 operací. Čím je průnik podmínek menší, tím se vícesloupcový index vyplatí více.

Někdy je ale podmínek tolik a jsou v tolika možných kombinacích, že definovat vícesloupcové indexy pro všechny kombinace by bylo kontraproduktivní. V tom případě je tedy možné se smířit s tím, že se dotaz nevyhodnotí nejefektivněji, ale aspoň o něco lépe než bez indexu. To nám prozradí příkaz EXPLAIN.

Jakub Vrána, Výuka, 18.12.2009, diskuse: 18 (nové: 0)

Diskuse

johno:

Doplnim, tu zohrava este velmi vyznamnu rolu selektivita indexu na konkretne hodnoty. Ak maju stlpce i a j stale rovnake hodnoty, tak mozem indexovat vsetkymi smermi a nepomozem si ani trochu. Zatial co ked mam stlpec i skoro-unikatny tak mi staci indexovanie i.

Jan Jadud:

@johno
ano to je pravda, to je v dosledku hashovacej funkcie a toho, ze pre podobne ~ rovnake hodnoty ide hash proste do rovnakeho bucketu.

Kazdopadne suhlasim s Jakubom, MySQL pri viacnosobnom indexe dokaze vyuzit prvu slozku a potom podla matches uz len porovna druhu zlozku.

Avsak niekedy je vhodne mat oba typy indexov, aj dvojity aj jednoduchy na oboch atributoch. Tu vsak teraz neviem s istotou povedat, pre ktory sa MySQL rozhodne. Jakub ty vies?

johno:

MySQL hashovaciu funkciu nepouziva (aspon nie implicitne), tam su B+ stromy, ale to je jedno.

Jednoduchy a dvojity je uplna zbytocnost, pretoze prefixove hladanie funguje. Ak mas index (i,j) automaticky je to indexom (i). Az na zopar specialnych pripadov ked sa pouzije covering index (teda selekt pri ktorom su potrebne len stlpce co su v indexe).

Jan Jadud:

Jo jasne, zabudol som ze MySQL robi s B+ stromami, pardon moja chyba. Co sa indexu tyka myslel som to tak ako to Jakub napisal v dalsom prispevku. Mat index (i,j) a (j) pretoze pri (i,j) sa druha suradnica pre index vyuzit neda, prva funguje aj ako samostatny index na (i) ako vravis ty, zle som to napisal v predoslom prispevku.

ikona Jakub Vrána OpenID:

Přesně jak píše johno. Hash indexy defaultně vytváří jen HEAP engine, u ostatních by bylo potřeba to ručně určit pomocí USING HASH. Se stejnými hodnotami se ale chovají špatně oba.

Pokud existuje index (i, j), může mít dobrý smysl definovat index (j), protože se použije pro dotazy neobsahující `i`, rozhodně ale nedává smysl definovat index (i).

johno:

Este je mozne ze myslel InnoDB adaptive hash index (http://dev.mysql.com/doc/refman/5.1/en/innodb-adaptive-hash.html), ale nie som si isty.

Kajman_:

Je to trošku offtopic ale nedávno jsem narazil na to, že při dotazu na poslední (první) záznamy s tím, že potřebujeme jen občas něco vyfiltrovat se může vyplatit dát tu flitrovací podmínku do having místo where. Jde to asi po indexu (i když o tom explain mlčí), tak to rychle najde prvních pár. Jinak se použije where, které už ani ty vícesloupcové indexy pro seřazení a rychlý výběr v tomhle případě nevyužije.

Konkrétně na tabulce s 100k záznamy dotaz
SELECT SQL_NO_CACHE
       topic_id,
       topic_title,
       topic_poster,
       topic_views,
       topic_last_post_id,
       forum_id
FROM   minibb_topics
WHERE  forum_id != 30
ORDER  BY topic_last_post_id DESC
LIMIT  30
trvá 0,5s a když dám having místo where, tak 1ms. Having se u normálních db smí asi využít jen při groupování, ale mysql (testovány verze 5.0) to překousne.

PHX:

Mam otazku. Zalezi na poradi indexu a v dotazu. Myslim tim index(j,i) vs. index(i, j) s dotazy i=? AND j=? vs. j=? AND i=?

DIKY

Zdeněk Večeřa:

Nezáleží.

Jen je třeba myslet na to, že pokud nadefinuješ index(j, i), tak MySQL může samostatně (!) přistoupit pouze k prvnímu indexu, v tomto případě "j". Pokud tedy použiješ pouze jednu podmínku "WHERE i=?", tak se index nepoužije. Je třeba na to při návrhu myslet.

Jirka:

Vícesloupcový index je určitě užitečný, ale přesto nepokrývá vše. Nejsem si zcela jistý, ale myslím, že pro následující situaci řešení na MySQL neexistuje.

Máme obecně tabuli, kde je například 10 číselných sloupců označených A-J, nabývajících různých hodnot. Tyto sloupce mohou reprezentovat různé kritéria, například, věk, kód státu, okresu a města, pohlaví, výšku, atp...

V dotazu pak může být použit kterýkoliv ze sloupců samostatně a i v kombinaci s kterýmkoliv jiným (i více) sloupci.

Kombinací pro vícesloupcové indexi je hodně a tak nemožné touto cestou jít. A řešení pomocí MERGE operace u jednosloupcových indexů je zase extrémně pomalé.

Napadá někoho řešení této situace?

Díky, Jirka

Dolby:

Zajimavy problem, napadly me v podstate 2 cesty jak toto resit, dovolim si nastinit prvni z nich. Myslim, ze by to mohlo fungovat dobre.

1) pro kazde kriterium vytvorit jednu tabulku s jednoduchou strukturou KLIC + HODNOTA ATRIBUTU a nazvem vyjadrujicim nazev kriteria.

napr.
CREATE TABLE IF NOT EXISTS `attr_age` (
  `id` int(10) unsigned NOT NULL,
  `attr` varchar(255) NOT NULL,
  PRIMARY KEY  (`id`),
  KEY `attr` (`attr`)
) ENGINE=MyISAM DEFAULT CHARSET=utf8;

priklad tabulek pro jednotliva kriteria:
- attr_age
- attr_gender
- attr_city

2) filtrovaci dotazy pak skladat pomoci UNION
priklad query:

(SELECT id FROM attr_age  WHERE attr = '20')
UNION
(SELECT id FROM attr_gender  WHERE attr = 'female')
UNION
(SELECT id FROM attr_city  WHERE attr = 'Brno')

3) nastavit samozrejme v jednotlivych tabulkach vhodne datove typy, aby indexy byly co nejoptimalnejsi

4) napojeni na hlavni tabulku (napriklad 'user') s popisem primarniho klice udelat pres INNER JOIN, umoznuje to i limitovany vyber

priklad:
---------------------------
SELECT * FROM users
INNER JOIN (
(SELECT id FROM attr_age  WHERE attr = '20')
UNION
(SELECT id FROM attr_gender  WHERE attr = 'female')
UNION
(SELECT id FROM attr_city  WHERE attr = 'Brno')
LIMIT 1,1
) AS inn USING (id)
---------------------------

Verim, ze by to mohlo fungovat, ale chce to poradne otestovat na potrebnem mnozstvi zaznamu (nevim zda pozadujete 1K ci 100K atd..)

Jirka:

Dekuji za odpoved. Musim rici, ze me otevrela uplne novy pohled na problematiku. Celou dobu jsem se v ramci eliminovani z meho pohledu "slozitych operaci" jako je prave UNION, snazil vse drzet v jedne tabuli a nenapadlo me se na to takto podivat.

Jen pro doplneni: jde o tabuli, kde je cca 300k zaznamu s potencialem dale rust a radove desitky az stovky dotazu za minutu. To je duvod, proc hledam nejake elegantni a dostatecne robustni reseni.

Provedu export atributu do jednotlivych tabuli a provedu testy.

Jeste jednou dekuji za tip!

Jirka

Dolby:

Drzim palce pri optimalizaci, pokud bojujes jen s takovym trafficem (radove desitky az stovky dotazu za minutu) tak myslim tohle reseni bude fungovat velmi dobre, pokud si dobre naprogramujete skladani query podle vstupu.

Ssamozrejme take zalezi na rychlosti serveru, ale takova zatez je orpavdu v pohode. Budte rad, ze nemusite optimalizovat system s 2500 query/s :)

Jen dodam pro uplnost, ze druhe reseni, ktere me napadlo, je rozprostreni dat do radku v jedne tabulce, se specialnim formatem kdy v jednom sloupci je ulozena informace o jmenu i hodnote kriteria ("AGE:20"). A nasledne indexovani pres crc32 (uint), ale takova vec by chtela mnohem lepe zanalyzovat.

Jirka:

Tak jen poznatek z testování, UNION pro verzi OR a INNER JOIN pro verzi AND se zda vcelku efektivni, ale dalsi uskali se objevilo po pouziti ORDER BY na vysledku. Kdy je vysledek potreba vratit serazeny v poradi dle nejakeho konkretniho sloupce. Logicky je tedy v pripade INNER JOIN potreba operaci provadet na celem rozsahu vysledku, coz mohou byt o desitky tisic zaznamu a tudiz je to neefektivni a pomale. V pripade UNION by se asi mohlo pole dle ktereho se radi jeste objevit v kazde jednotlive tabuli atributu a radit uz v ramci provedeni UNION. To je ale asi vcelku narocne na updatovani vsech informaci a taky to neresi pripad s podminkou ve stylu AND.

Takze, kruh se uzavrel a jsem opet na zacatku...

Asi je cas se podivat, jake by to melo deseni napriklad na Oraclu nebo MSSQL.

Hezky den, Jirka

Dolby:

Trochu se v tom ztracim :)
Pokud chcete, vyhledavat podle konkrenti hodnoty kriteria, nevidim duvod proc by se podle teto hodnoty melo u radit.

Umim si to predstavit pri hledani rozsahu v danem kriteriu ("age IN (10,20)"), ale a razeni je pak trochu jiny problem nez samotne filtrovani.

Obecne se mi to reseni pres (INNER) JOIN vubec nezda, ani bych neveril ze to funguej spravne.

A hlavne - podminku OR vubec nepouzivejte, to uz si radeji dejte 2x UNION na stejnou tabulku, abyste vubec INDEX vyuzil. Operator OR je zabijak INDEXU :)

Jirka:

Ten vyznam OR byl pouze logický, kryz pouziju UNION na tri tabule atributu, tak vysledkem bude seznam id obsahujici vse co odpovida podmince u prvniho selectu + vse co odpovida podmince u truheho i tretiho selectu. Tzn. vysledky selectu se spoji a tak vznikne logicky soucet, proto jsem pouzil OR.

Kdezto pokud mistu spojeni vysledku trech tabuli atributu data select na prvni, pak inner join k druhe a jeste inner join k treti, pak budou ve vysledku pouze id, ktere odpovidaji podmince ve vsech trech tabulich atributu.

A duvod pro razeni - pokud vyberu nejaky konkretni seznam z tabule uzivatelu, napriklad, vsichny zeny ve veku 20 z Brna, bude jich radove stovky a ja bych chtel vysledek seradit napriklad podle posledni aktivity, nebo podle jmena.

Jirka

Jirka:

Jeste jedna vec, kterou jsem si uvedomil az kdyz jsem to ted otestoval, uvedene reseni je ekvivalent oparatoru OR pro jednotliva pole podminky. Napada me misto HAVING pozuit INNER JOIN i pro jednotlive tabule atributu, ve stylu:

SELECT attr_age.id FROM attr_age
INNER JOIN attr_gender ON attr_age.id=attr_gender.id AND attr_gender.attr='female'
INNER JOIN attr_city ON attr_age.id=attr_city.id AND attr_city.attr='Brno'
where attr_age.attr='20'
limit 0,10

A jeste tedy pripojit onu tabuli uzivatelu...

johno:

Mozno to vobec nechapem, ale uvedene riesenie mi pride skrabanie sa za pravym uchom lavou rukou.

Jednak sa duplikuju data = treba riesit synchronizaciu.

Dvak toto iste spravanie sa da dosiahnut pomocou self joinu a vytvorenim indexov na kazdom stlpci v povodnej tabulke. Idealne vzdy zlozeny index (napr. age, id) - aby slo o v selekte pouzit covering index.

SELECT * FROM users
INNER JOIN (
(SELECT id FROM users  WHERE age = 20)
UNION
(SELECT id FROM users  WHERE gender = 'female')
UNION
(SELECT id FROM users  WHERE city = 'Brno')
LIMIT 1,1
) AS inn USING (id)

Obavam sa, ze spomaleny merge_index bol hlavne preto, lebo indexy maju velmi slabu selektivitu (napr. gender) a podla komentara na http://dev.mysql.com/doc/refman/5.1/en/index-merge-optimization.html je to znama 'vlastnost'.

Ja by som teda skusil odstranit slabo selektivne indexy a pozrel ci sa to nezlepsi.

Vložit komentář

Používejte diakritiku. Vstup se chápe jako čistý text, ale URL budou převedeny na odkazy a PHP kód uzavřený do <?php ?> bude zvýrazněn. Pokud máte dotaz, který nesouvisí s článkem, zkuste raději diskusi o PHP, zde se odpovědi pravděpodobně nedočkáte.

Jméno: URL:

avatar © 2005-2018 Jakub Vrána. Publikované texty můžete přetiskovat pouze se svolením autora. Ukázky kódu smíte používat s uvedením autora a URL tohoto webu bez dalších omezení Creative Commons. Můžeme si tykat. Skripty předpokládají nastavení: magic_quotes_gpc=Off, magic_quotes_runtime=Off, error_reporting=E_ALL & ~E_NOTICE a očekávají předchozí zavolání mysql_set_charset. Skripty by měly být funkční v PHP >= 4.3 a PHP >= 5.0.