povídky foto kultura ostatní stripy
facebook twitter
ASCII blog doomsday party

k47.cz

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íč.


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

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