k47.cz  — každý den dokud se vám to nezačne líbit
výběr foto Praha povídky kultura
TECH ▞▞ kolo | twitter RSS

MySQL: rychlý výběr náhodného záznamu

9. 3. 2011 (před 8 lety) — k47 (CC by-nc-sa) (♪)

Pro­jekt vtipy.k47.cz je celkem jed­no­du­chá da­ta­báze vtipů, MySQL, 23000 zá­znamů. Na hlavní stránce se zob­ra­zuje ně­ko­lik ná­hod­ných vtipů. To vypadá docela nor­málně, nic pře­kva­pi­vého, žejo. Právě že ne, s vý­bě­rem ná­hod­ného zá­znamu je to slo­ži­tější. Hlavně rych­lost je pro­ble­ma­tická.


Pro­blém: Po­tře­bu­jeme získat jeden nebo ně­ko­lik ná­hod­ných zá­znamů z da­ta­báze. Nej­jed­no­dušší řešení může vy­pa­dat zhruba takto:

SELECT * FROM entry ORDER BY RAND() LIMIT 1

Fun­guje vý­borně, pokud je zá­znamů málo. Ale stačí, aby ta­bulka měla ně­ko­lik tisíc řádků, a dotaz začne pomalu vraž­dit da­ta­bázi.

MySQL v tomto pří­padě pro každý řádek vy­ge­ne­ruje ná­hodné číslo, pak všechny řádky seřadí podle tohoto čísla a pak vybere počet řádků uve­dený v klau­zuli LIMIT. A to zna­mená n-krát vy­ge­ne­ro­vat ná­hodné číslo a pak n log(n) po­rov­nání. Dotaz v ta­bulce s 25.000 řádky trval kolem 10 vteřin, což má k po­u­ži­tel­nosti na webu daleko. Na malých datech, řek­něme ta­bulce se sto řádky se žádné ci­telné zpo­ma­lení ne­pro­jeví, ale s na­růs­ta­jí­cími daty se rych­lost stává ne­pře­ko­na­tel­ným pro­blé­mem.

Řešení je na­snadě: když nejvíc času zabírá ge­ne­ro­vání ná­hod­ných čísel, jejich řazení a výběr jedno z nich, sta­čilo by vý­po­čet ná­hod­ného prvku pře­nést do ří­dí­cího skriptu a pak si ho vybrat jedním do­ta­zem pomocí LIMITOFFSET.

Pak by to vy­pa­dalo nějak takto (po­u­žito dibi):

$count = dibi::fetchSingle('SELECT count(*) FROM entry');
$randomOffset = rand(0, $count - 1);
$entry = dibi::fetch('SELECT * FROM entry LIMIT 1 OFFSET %i', $randomOffset);

První dotaz v pří­padě MyISAM trvá kon­stantní dobu, pro­tože se čte z me­ta­dat ta­bulky; v pří­padě InnoDB je jeho doba li­ne­ární, pro­tože se sku­tečně musí spo­čí­tat všechny řádky jeden za druhým, ale zase když se ta­bulka mění jenom zřídka, může být načten z query cache. I přesto, že se pro­vádí dva dotazy, ve vý­sledku jsou mnohem rych­lejší než před­chozí va­ri­anta. Na stej­ných datech se trvá 0.1 až 0.2 vte­řiny, což je sice 100x rych­leji a stěží po­střeh­nu­telné, ale pořád je tu místo pro zlep­šení.

Da­ta­bá­zové stroje pro­vádí nej­rych­lejší výběry podle indexu, nej­lépe uni­kát­ního indexu nebo pri­már­ního klíče, tak proč toho ne­vy­u­žít? Pro­blém je v tom, že i když známe horní i dolní hra­nici sloupce id (ce­lo­čí­selný pri­mární klíč), nic ne­za­ru­čuje, že zrovna ne­tre­fíme ně­ja­kou díru, která zů­stala např. po sma­za­ném řádku. To je pro­blém, pro­tože musíme za­ru­čit, že hod­noty v id budou na­va­zo­vat. Takže při sma­zání nebo vlo­žení řádku musíme pro­vést pře­tří­dění, tak­zvaně ta­bulku se­tře­pat. Což je další zátěž (zvlášť, když je s ostat­ními ta­bul­kami pro­vá­zána cizími klíči) a záleží, jestli se čas­těji vybírá ná­hodný řádek nebo jestli se vklá­dají data.

Takže pokud je jisté, že pri­mární klíč id začíná od 1, končí číslem count(*) a ne­ob­sa­huje žádné díry, můžeme pro­vést ná­sle­du­jící skript

$count = dibi::fetchSingle('SELECT count(*) FROM entry');
$randomId = rand(1, $count);
$entry = dibi::fetch('SELECT * FROM entry WHERE id = $randomId');

Dotaz přes slou­pec s in­de­xem na mém stroji na stej­ných datech trval méně než 0.001 vte­řiny, což je další sto­ná­sobné zrych­lení a zpož­dění se už nedá po­střeh­nout. Ale zase je otázka jestli, můžeme za­ru­čit, že v id nejsou žádné díry.

Pokud to ne­mů­žeme za­ru­čit, můžeme zkom­bi­no­vat po­slední dvě řešení: pro­ve­deme výběr podle pri­már­ního klíče, když tre­fíme díru (druhý dotaz nic ne­vrátí), vy­be­reme ná­hodný záznam přes offset, který nikdy ne­selže.

V pří­padě vtipů, kdy je da­ta­báze prak­ticky ne­měnná, je ide­ální výběr přes pri­mární klíč.

píše k47 & hosté, ascii@k47.cz