Poslední aktualizace 8. prosince 2019
Vrácení náhodných řádků v náhodném pořadí z relační databáze je velmi těžký problém. V tomto článku si ukážeme antivzor, probereme, proč je tento problém tak těžký, a prozkoumáme některá nedokonalá řešení.
DOPLNĚNO: Některé DBMS podporují TABLESAMPLE. Nezmiňoval jsem se o něm, protože jsem do dneška znal jen implementaci SQL Serveru a nepovažuji ji za dobrou pro extrakci náhodných řádků (vysvětlím proč). Ale po dotazu Daniëla van Eedena na Facebooku jsem provedl průzkum a zjistil jsem, že implementace PostgreSQL by mohla být mnohem vhodnější. Budu o ní více číst a zkoušet ji, a pak o ní pravděpodobně napíšu druhý článek. Každopádně MySQL a MariaDB nepodporují TABLESAMPLE.
Špatný způsob: ORDER BY RAND()
Mnoho vývojářů si myslí, že to jde udělat tímto způsobem:
SELECT some_columns FROM some_table ORDER BY RAND() LIMIT 10;To je jediný dotaz, který dělá přesně to, co se očekává. Pokud je RAND() funkce spolehlivě náhodná, vrátí náhodnou množinu řádků, kde každý řádek má stejnou šanci být vrácen.
Problém je v tom, jak to funguje pod kapotou. Aby bylo možné náhodné hodnoty uspořádat, je třeba je nejprve vytvořit. Aby DBMS vytvořil náhodnou hodnotu pro každý řádek tabulky, musí každý řádek přečíst. DBMS tedy provede operaci ve dvou krocích:
- Zkopíruje řádky plus náhodnou hodnotu do dočasné tabulky, snad v paměti;
- Uspořádá řádky v dočasné tabulce.
Všimněte si, že tento detail: snad v paměti. V závislosti na DBMS mohou existovat důvody, proč je třeba tabulku vytvořit na disku. Typicky k tomu dochází, pokud je tabulka příliš velká. Starší verze MySQL také vytvářejí dočasné tabulky na disku, pokud obsahují TEXT nebo BLOB sloupce.
Není třeba dodávat, že pokud je tabulka velká, jedná se o pomalou operaci, která spotřebovává mnoho prostředků.
Proč relační DBMS neposkytují vestavěný způsob, jak vracet náhodné řádky?
Relační databáze jsou postaveny na odvětví matematiky zvaném relační algebra. Vychází z logiky, protože se zabývá predikáty pravda/nepravda; ans podobně jako teorie množin, i když relace je něco složitějšího než množina, a ani pohled na ni jako na tabulku není matematicky správný. Tento článek je pěkným příkladem toho, co mám na mysli, ale existují i složitější argumenty.
Přestože SQL není přesnou implementací relačního modelu, jeho algebra se používá jako referenční. Stejně jako všechna odvětví matematiky má dobře definovanou množinu operací. Získávání náhodných tuplů z relace mezi ně rozhodně nepatří.
Tato odpověď zní příliš teoreticky, že? ORDER BY a tabulky bez primárního klíče také porušují pravidla relační algebry, ale SQL je podporuje.
Pro databáze je však zásadní rychlost. Relační DBMS jsou navrženy tak, aby relační operace prováděly velmi rychle. Je zřejmé, že datová struktura navržená pro optimalizaci určitých operací není optimalizovaná pro jiné operace. Relační DBMS tedy nejsou optimalizovány pro náhodné vyhledávání.
Mělo by být zřejmé, že procházení řádků ve smyčce a náhodný výběr některých z nich by bylo pomalé. Teoreticky by načtení náhodného řádku pomocí indexu bylo stejně rychlé jako vyhledání řádku podle hodnoty primárního klíče. Pak by ale různé řádky měly různou šanci na výběr.
Výše uvedený obrázek pochází z repozitáře Jeremyho Colea na GitHubu, innodb_diagrams. Dříve nebo později bych měl napsat o jeho projektech na analýzu datových struktur InnoDB.
Důležité je, že index je strom, jehož uzly jsou paměťové stránky. Listové uzly obsahují skutečná data; vyšší úrovně obsahují pouze informace potřebné k výběru nejkratší cesty k požadovanému listovému uzlu. Podrobnosti nejsou v tomto kontextu důležité.
DBMS by teoreticky mohl vybrat náhodnou stránku provedením série náhodných rozhodnutí: Půjdu doleva nebo doprava? Pak ale listové stránky obsahují proměnlivý počet řádků. Mohly by být dokonce prázdné. Takže různé řádky by měly různou šanci být vybrány.
Výsledek je zjevně mimo zamýšlené případy použití DBMS; a může být pomalý nebo špatný, v závislosti na tom, zda se používá index nebo ne. DBMS se správně rozhodly tuto funkci neimplementovat.
Některá řešení
Neexistují dokonalá řešení. Existují řešení, která mohou být přijatelná, ale mají nevýhody. Měli bychom si vybrat případ od případu.
Náhodný výběr z rozsahu
Toto řešení je použitelné pro tabulky, které mají autoinkrementální primární klíč. Je nejjednodušší na implementaci, ale „fragmentovaný“ primární klíč způsobuje problémy.
Spočívá v kontrole minimálního id, maximálního id a vygenerování náhodného čísla v tomto rozsahu:
Ne že by dotazy s MIN() a MAX() na libovolný index, bez dalších klauzulí, byly velmi rychlé.
Výsledkem je skutečně náhodný řádek. Chceme-li vybrat více než jeden řádek, můžeme tento dotaz opakovat vícekrát. To nás vede ke dvěma nevýhodám:
- Pokud tuto operaci provádíme často, mohli bychom tento dotaz spustit mnohokrát.
- Není zaručeno, že stejný řádek nebude vybrán vícekrát. Pokud se tak stane, aplikace může dotaz zopakovat. Pokud je tabulka velká, je tato událost vzácná a můžeme ji ignorovat – pokud není
RAND()funkce nespolehlivá. Ale u malých tabulek to může být problém.
Také primární klíč může mít díry – jinými slovy, některá čísla mohou chybět. To je způsobeno mazáním a neúspěšnými transakcemi. Čísla nižší než maximální se znovu nepoužívají. Abychom tento problém obešli, můžeme použít dvě techniky:
Použití >=
Použijeme-li operátor >= v klauzuli WHERE, dotaz vždy vrátí řádek. Pokud vygenerované číslo není přítomno, použije se další. To ale znamená, že hodnoty bezprostředně za dírou budou mít větší šanci na výběr. Čím větší díra, tím větší šance.
Možná si myslíte, že by vás to nemělo zajímat, a pravděpodobně máte pravdu. Ale než se definitivně rozhodnete, zvažte možnost velké díry.
Snažíme se
Pokud dotaz nevrátí žádné řádky, můžeme dotaz prostě zopakovat. U velkých tabulek s jen několika malými dírami je to naprosto v pořádku. Ale u velkých tabulek s mnoha dírami nebo u velkých děr by tato technika mohla spotřebovat příliš mnoho prostředků
Prosím, nebuďte z toho příliš paranoidní. Jen si to trochu spočítejte. Jaký je poměr chybějících hodnot ve vaší tabulce? To vám řekne, kolikrát bude dotaz v průměru opakován.
Výběr více řádků
Chceme-li touto technikou vybrat více řádků, můžeme:
- Dotaz opakovat vícekrát;
- Nebo pro lepší výkon použít operátor
>=a použítLIMITvětší než jedna. Tím se však výsledky stanou mnohem méně náhodné.
Přenesení náhodného výběru na aplikaci
V nejjednodušší podobě spočívá tato technika v náhodném výběru bloku sousedících id. Aplikace náhodně vybere, které z nich použije, a pak vybere odpovídající řádky.
Předpokládejme, že chcete vybírat z bloků o 1000 hodnotách:
Čím větší je blok, tím více prostředků spotřebujete, tím náhodnější je výsledek. Aplikace má odpovědnost za výběr náhodných jedinečných existujících id z bloků, takže by nikdy nemělo být nutné dotaz opakovat.
Varianta MOD
Problémem této techniky je, že řádky jsou vraceny ze stejného bloku sousedících id. To by mohlo být zcela přijatelné, zejména pokud je blok velký. Pokud však není, mohli bychom přidat určitou složitost pro výběr bloku nesousedících řádků.
Záměrem této varianty je:
- Definovat makrobloky většinou nesousedících řádků;
- Náhodně vybrat jeden makroblok;
- Vrátit z něj blok.
K tomu můžeme vypočítat modul id a použít ho k náhodnému výběru výsledků. Můžeme například definovat indexovaný virtuální sloupec s výrazem jako (id MOD 4). Každý řádek bude mít hodnotu mezi 0 a 3. I když jsou v nich díry, řádky z těchto makrobloků budou většinou nesouvislé a měly by mít přibližně stejné číslo.
Aplikace by měla generovat náhodné číslo mezi 0 a 3. Poté pro výběr bloků z těchto makrobloků:
SET @block_size := 1000;SELECT id FROM some_table WHERE id_mod = FLOOR(RAND() * 3) ORDER BY id LIMIT @block_size;Podobným způsobem, jak realizovat tuto myšlenku, je použití oddílů, kde rozdělovací funkcí je modul id. To bych navrhoval pouze v případě, že by tabulce prospělo rozdělení z jiných důvodů.
Výběr techniky
Bloková technika provádí více dotazů ve srovnání s první technikou s operátorem >= a výsledek může být lepší nebo ne. Oproti variantě s opakováním by mohla spustit více nebo méně dotazů a výsledek je horší.
Všeobecně jsou blokové techniky lepší, pokud máme v primárním klíči díry.
Ukládání náhodných řad do mezipaměti
Předchozí metody jsou kompromisem: výkon versus lepší náhodnost, kdy rychlejší řešení jsou také složitější na implementaci. Pokud nepoužijeme antivzor ORDER BY RAND(), neměl by výběr náhodných řad způsobovat výkonnostní problémy. Ale co když ano?“
Mohli bychom do mezipaměti uložit několik náhodně seřazených id získaných pomocí některého z předchozích řešení. Mohli bychom použít takovýto dotaz (syntaxe MySQL):
Mohli bychom použít řady ve vzestupném nebo sestupném pořadí, náhodně. Nebo by je aplikace mohla zamíchat.
Problémy:
- Při přidání položky bychom měli náhodně vybrat, zda musí být vložena do řady a nahradit náhodnou položku.
- Při odstranění položky bychom ji měli odstranit ze všech řad. Měla by být nahrazena jinou náhodnou položkou.
- Možná budeme chtít pravidelně mazat nejstarší série a nahrazovat je novými, abychom zlepšili náhodnost v uživatelském prostředí.
Závěry
Jako obvykle, prosím, komentujte a dejte mi vědět, pokud v tomto článku objevíte chybu, pokud s něčím nesouhlasíte, řekněte mi svou osobní zkušenost, nebo pokud máte další nápady, které byste chtěli přidat.