k47.cz
foto Praha výběr povídky kulturatwitter FB


9. 3. 2011

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

       

Projekt vtipy.k47.cz je celkem jednoduchá databáze vtipů, MySQL, 23000 záznamů. Na hlavní stránce se zobrazuje několik náhodných vtipů. To vypadá docela normálně, nic překvapivého, žejo. Právě že ne, s výběrem náhodného záznamu je to složitější. Hlavně rychlost je problematická.


Problém: Potřebujeme získat jeden nebo několik náhodných záznamů z databáze. Nejjednodušší řešení může vypadat zhruba takto:

SELECT * FROM entry ORDER BY RAND() LIMIT 1

Funguje výborně, pokud je záznamů málo. Ale stačí, aby tabulka měla několik tisíc řádků, a dotaz začne pomalu vraždit databázi.

MySQL v tomto případě pro každý řádek vygeneruje náhodné číslo, pak všechny řádky seřadí podle tohoto čísla a pak vybere počet řádků uvedený v klauzuli LIMIT. A to znamená n-krát vygenerovat náhodné číslo a pak n log(n) porovnání. Dotaz v tabulce s 25.000 řádky trval kolem 10 vteřin, což má k použitelnosti na webu daleko. Na malých datech, řekněme tabulce se sto řádky se žádné citelné zpomalení neprojeví, ale s narůstajícími daty se rychlost stává nepřekonatelným problémem.

Řešení je nasnadě: když nejvíc času zabírá generování náhodných čísel, jejich řazení a výběr jedno z nich, stačilo by výpočet náhodného prvku přenést do řídícího skriptu a pak si ho vybrat jedním dotazem pomocí LIMIT a OFFSET.

Pak by to vypadalo nějak takto (použ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á konstantní dobu, protože se čte z metadat tabulky; v případě InnoDB je jeho doba lineární, protože se skutečně musí spočítat všechny řádky jeden za druhým, ale zase když se tabulka mění jenom zřídka, může být načten z query cache. I přesto, že se provádí dva dotazy, ve výsledku jsou mnohem rychlejší než předchozí varianta. Na stejných datech se trvá 0.1 až 0.2 vteřiny, což je sice 100x rychleji a stěží postřehnutelné, ale pořád je tu místo pro zlepšení.

Databázové stroje provádí nejrychlejší výběry podle indexu, nejlépe unikátního indexu nebo primárního klíče, tak proč toho nevyužít? Problém je v tom, že i když známe horní i dolní hranici sloupce id (celočíselný primární klíč), nic nezaručuje, že zrovna netrefíme nějakou díru, která zůstala např. po smazaném řádku. To je problém, protože musíme zaručit, že hodnoty v id budou navazovat. Takže při smazání nebo vložení řádku musíme provést přetřídění, takzvaně tabulku setřepat. Což je další zátěž (zvlášť, když je s ostatními tabulkami provázána cizími klíči) a záleží, jestli se častěji vybírá náhodný řádek nebo jestli se vkládají data.

Takže pokud je jisté, že primární klíč id začíná od 1, končí číslem count(*) a neobsahuje žádné díry, můžeme provést následují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 sloupec s indexem na mém stroji na stejných datech trval méně než 0.001 vteřiny, což je další stonásobné zrychlení a zpoždění se už nedá postřehnout. Ale zase je otázka jestli, můžeme zaručit, že v id nejsou žádné díry.

Pokud to nemůžeme zaručit, můžeme zkombinovat poslední dvě řešení: provedeme výběr podle primárního klíče, když trefíme díru (druhý dotaz nic nevrátí), vybereme náhodný záznam přes offset, který nikdy neselže.

V případě vtipů, kdy je databáze prakticky neměnná, je ideální výběr přes primární klíč.


vstoupit do diskuze    sdílet na facebooku, twitteru, google+

publikováno 9. 3. 2011

příbuzné články:
Hromadný update v jednom SQL dotazu
Kdy vám SQL_CALC_FOUND_ROWS zabije databázi
Jednoduché problémy mívají většinou složité řešení
Data positive
Konvertor exportů návštěvních knih Blueboard do SQL
Pravidelná dvojrozměrná data v MySQL

sem odkazují:
Pěkně uleželé ležáky

píše k47 & NEVERYOUNG, kontakt: ascii@k47.cz