Mutolsó frissítés: 2019. december 8
Véletlenszerű sorok véletlenszerű sorrendben történő visszaadása egy relációs adatbázisból nagyon nehéz probléma. Ebben a cikkben megnézünk egy antipatternt, megvitatjuk, hogy miért olyan nehéz ez a probléma, és megvizsgálunk néhány tökéletlen megoldást.
UPDATE: Egyes DBMS-ek támogatják a TABLESAMPLE. Azért nem említettem, mert eddig csak az SQL Server implementációját ismertem, és azt nem tartom jónak véletlenszerű sorok kinyerésére (majd elmagyarázom, miért). De Daniël van Eeden Facebookon feltett kérdése után némi kutatást végeztem, és rájöttem, hogy a PostgreSQL implementáció sokkal alkalmasabb lehet. Még többet fogok olvasni róla és kipróbálni, és akkor valószínűleg írok egy második cikket róla. Egyébként a MySQL és a MariaDB nem támogatja a TABLESAMPLE.
A rossz út: ORDER BY RAND()
Sok fejlesztő úgy gondolja, hogy így is meg tudja csinálni:
SELECT some_columns FROM some_table ORDER BY RAND() LIMIT 10;Ez az egyetlen lekérdezés, ami pontosan azt csinálja, amit elvárunk. Ha a RAND() függvény megbízhatóan véletlenszerű, akkor egy véletlenszerű sorhalmazt ad vissza, ahol minden sornak ugyanolyan esélye van a visszatérésre.
A probléma az, hogy hogyan működik a motorháztető alatt. A véletlen értékek rendezéséhez előbb létre kell hozni őket. Ahhoz, hogy egy táblázat minden sorához véletlen értéket hozzon létre, a DBMS-nek minden sort be kell olvasnia. Tehát a DBMS egy kétlépéses műveletet hajt végre:
- A sorok és egy véletlen érték másolása egy ideiglenes táblába, remélhetőleg a memóriában;
- A sorok rendezése az ideiglenes táblában.
Megjegyzem ezt a részletet: remélhetőleg a memóriában. A DBMS-től függően lehetnek olyan okok, amelyek miatt a táblát a lemezen kell létrehozni. Tipikusan ez akkor történik, ha a tábla túl nagy. A MySQL régi verziói is létrehoznak ideiglenes táblákat a lemezen, ha azok TEXT vagy BLOB oszlopokat tartalmaznak.
Mondanom sem kell, hogy ha a tábla nagy, ez egy lassú művelet, amely sok erőforrást fogyaszt.
Miért nem biztosítanak a relációs DBMS-ek beépített módot a véletlenszerű sorok visszaadására?
A relációs adatbázisok a matematika egy relációs algebra nevű ágára épülnek. Ez a logikán alapul, mert igaz/hamis predikátumokkal foglalkozik; ans hasonló a halmazelmélethez, még akkor is, ha egy reláció valami összetettebb, mint egy halmaz, és még táblázatnak tekinteni sem matematikailag helyes. Ez a cikk egy szép példa arra, hogy mire gondolok, de vannak ennél összetettebb érvek is.
Mindamellett, hogy az SQL nem a relációs modell pontos megvalósítása, az algebráját referenciaként használják. Mint a matematika minden ágának, ennek is van egy jól definiált műveletsora. A véletlenszerű tuplik kinyerése egy relációból biztosan nem tartozik ezek közé.
Ez a válasz egy kicsit túl elméletinek hangzik, igaz? ORDER BY és az elsődleges kulcs nélküli táblák szintén sértik a relációs algebra szabályait, de az SQL támogatja őket.
Az adatbázisok esetében azonban a sebesség létfontosságú. A relációs DBMS-eket úgy tervezték, hogy nagyon gyorsan végezzenek relációs műveleteket. Nyilvánvaló, hogy egy bizonyos műveletek optimalizálására tervezett adatszerkezet nem optimalizált más műveletekre. Tehát a relációs DBMS-ek nem optimalizáltak véletlenszerű keresésre.
Az nyilvánvalónak kell lennie, hogy a sorok körbejárása néhány sor véletlenszerű kiválasztása érdekében lassú lenne. Elméletileg egy véletlenszerű sor kiolvasása egy index segítségével ugyanolyan gyors lenne, mint egy sor keresése az elsődleges kulcs értéke alapján. De akkor a különböző sorok különböző eséllyel kerülnének kiválasztásra.
A fenti kép Jeremy Cole egyik GitHub-tárából származik, innodb_diagrams. Előbb-utóbb írnom kellene az InnoDB adatstruktúrákat elemző projektjeiről.
Az itt fontos, hogy az index egy fa, amelynek csomópontjai memóriaoldalak. A levélcsomópontok tényleges adatokat tartalmaznak, a felsőbb szintek csak a kívánt levélcsomóponthoz vezető legrövidebb út kiválasztásához szükséges információkat tartalmazzák. A részletek ebben a kontextusban nem fontosak.
A DBMS elméletileg véletlenszerű lapot választhat egy sor véletlenszerű döntés végrehajtásával: balra vagy jobbra megyek? De akkor a levéloldalak változó számú sort tartalmaznak. Akár üresek is lehetnek. Így a különböző sorok különböző eséllyel kerülnének kiválasztásra.
Az eredmény egyértelműen kívül esik a DBMS-ek tervezett felhasználási esetein; és lassú vagy rossz lehet, attól függően, hogy indexet használunk-e vagy sem. A DBMS-ek helyesen döntöttek úgy, hogy nem implementálják ezt a funkciót.
Egyes megoldások
Tökéletes megoldások nincsenek. Vannak olyan megoldások, amelyek elfogadhatóak lehetnek, de vannak hátrányaik. Esetről esetre kell választanunk.
Véletlenszerű választás egy tartományból
Ez a megoldás olyan táblákra alkalmazható, amelyek autoincrementális elsődleges kulccsal rendelkeznek. Ez a legkönnyebben megvalósítható, de egy “töredezett” elsődleges kulcs problémákat okoz.
Ez abból áll, hogy ellenőrizzük a minimális id-t, a maximális id-t, és egy véletlen számot generálunk ebben a tartományban:
Nem úgy, hogy a MIN() és MAX() bármely indexre vonatkozó, egyéb záradékok nélküli lekérdezések nagyon gyorsak.
Az eredmény egy valóban véletlen sor. Ha egynél több sort szeretnénk kiválasztani, akkor ezt a lekérdezést többször is megismételhetjük. Ez két hátrányhoz vezet:
- Ha ezt a műveletet gyakran végezzük, akkor sokszor lefuttathatjuk ezt a lekérdezést.
- Nincs garancia arra, hogy nem ugyanazt a sort választjuk ki többször. Ha ez megtörténik, az alkalmazás megismételheti a lekérdezést. Ha a táblázat nagy, ez az esemény ritka, és figyelmen kívül hagyhatjuk – kivéve, ha a
RAND()függvény megbízhatatlan. De kis táblák esetében ez problémát jelenthet.
Az elsődleges kulcs is lehet lyukas – más szóval, egyes számok hiányozhatnak. Ez a törlések és a sikertelen tranzakciók miatt van. A maximumnál alacsonyabb számok nem kerülnek újrafelhasználásra. Ennek a problémának a kiküszöbölésére két technikát használhatunk.
A >=
Ha a WHERE záradékban a >= operátort használjuk, a lekérdezés mindig egy sort fog visszaadni. Ha a generált szám nincs meg, akkor a következő számot fogja használni. Ez azonban azt jelenti, hogy a közvetlenül egy lyuk után következő értékeknek több esélyük lesz a kiválasztásra. Minél nagyobb a lyuk, annál nagyobb az esélye.
Azt gondolhatja, hogy ezzel nem kellene törődnie, és valószínűleg igaza is van. De mielőtt végleges döntést hozna, gondoljon a nagy lyuk lehetőségére.
Keményen próbálkozunk
Ha a lekérdezés nem ad vissza sorokat, akkor egyszerűen újrapróbálkozhatunk. Nagy tábláknál, ahol csak néhány kisebb lyuk van, ez tökéletesen megfelel. De nagy lyukaknál sok lyukkal, vagy nagy lyukaknál ez a technika túl sok erőforrást emészthet fel.
Kérem, ne legyen túl paranoiás ezzel kapcsolatban. Csak csinálj egy kis matekot. Mennyi a hiányzó értékek aránya a táblázatodban? Ez megmondja, hogy átlagosan hányszor kell újrapróbálni a lekérdezést.
Második sorok kiválasztása
A több sor kiválasztásához ezzel a technikával:
- Másodszor is megismételhetjük a lekérdezést;
- Vagy a jobb teljesítmény érdekében használjuk a
>=operátort és használjunk egynél nagyobbLIMITértéket. Ez azonban sokkal kevésbé teszi véletlenszerűvé az eredményeket.
A véletlenszerű választás áthelyezése az alkalmazásba
Ez a technika legegyszerűbb formájában abból áll, hogy véletlenszerűen kiválasztunk egy összefüggő id-kből álló blokkot. Az alkalmazás véletlenszerűen választja ki, hogy melyiket használja, majd kiválasztja a megfelelő sorokat.
Tegyük fel, hogy 1000 értékből álló blokkokból akarunk választani:
Minél nagyobb a blokk, annál több erőforrást fogyasztunk, annál véletlenszerűbb az eredmény. Az alkalmazás felelőssége, hogy a blokkokból véletlenszerűen egyedi, létező azonosítókat válasszon ki, így soha nem lehet szükség a lekérdezés megismétlésére.
A MOD változat
Ezzel a technikával az a probléma, hogy a sorok ugyanabból az egybefüggő azonosítókból álló blokkból kerülnek vissza. Ez teljesen elfogadható lehet, különösen, ha a blokk nagy. De ha nem az, akkor némi bonyolultságot adhatnánk a nem összefüggő sorokból álló blokk kiválasztásához.
Ez a változat lényege:
- Makroblokkok definiálása többnyire nem összefüggő sorokból;
- Véletlenszerűen kiválasztunk egy makroblokkot;
- visszaadunk belőle egy blokkot.
Ezért kiszámíthatjuk az id modulusát, és azt használhatjuk a véletlenszerű eredmények kiválasztására. Például definiálhatunk egy indexelt virtuális oszlopot egy olyan kifejezéssel, mint (id MOD 4). Minden sor 0 és 3 közötti értéket fog kapni. Még ha vannak is lyukak, az ilyen makroblokkokból származó sorok többnyire nem lesznek egybefüggőek, és megközelítőleg azonos számnak kell lenniük.
Az alkalmazásnak 0 és 3 közötti véletlen számot kell generálnia. Ezután a blokkok kiválasztásához ezekből a makroblokkokból:
SET @block_size := 1000;SELECT id FROM some_table WHERE id_mod = FLOOR(RAND() * 3) ORDER BY id LIMIT @block_size;Az ötlet megvalósításának hasonló módja a partíciók használata, ahol a partícionáló függvény az id modulusa. Ezt csak akkor javasolnám, ha a tábla más okokból profitálna a partícionálásból.
A technika kiválasztása
A blokkos technikák több lekérdezést futtatnak az elsőhöz képest a >= operátorral, és az eredmény lehet jobb vagy nem. A retry változathoz képest ez több vagy kevesebb lekérdezést futtathat, és az eredmény rosszabb lehet.
A blokk technikák általában jobbak, ha lyukak vannak az elsődleges kulcsban.
Véletlenszerű sorozatok tárolása
Az előző módszerek kompromisszumot jelentenek: teljesítmény kontra jobb véletlenszerűség, ahol a gyorsabb megoldás megvalósítása is bonyolultabb. Amíg nem használjuk a ORDER BY RAND() antipatternt, a véletlenszerű sorok kiválasztása nem okozhat teljesítményproblémákat. De mi van, ha mégis?
Megtehetnénk néhány véletlenszerűen rendezett id-t, amelyeket az előző megoldások bármelyikével kaptunk. Használhatnánk egy ilyen lekérdezést (MySQL szintaxis):
A sorokat növekvő vagy csökkenő sorrendben, véletlenszerűen használhatnánk. Vagy az alkalmazás keverhetné őket.
Problémák:
- Az elem hozzáadásakor véletlenszerűen kell választanunk, hogy be kell-e illesztenünk egy sorozatba, egy véletlenszerű elemet helyettesítve.
- Az elem törlésekor törölnünk kell az összes sorozatból. Egy másik véletlenszerű elemmel kell helyettesíteni.
- A legrégebbi sorozatokat időnként törölhetjük, és újakkal helyettesíthetjük, hogy javítsuk a véletlenszerűséget a felhasználói élményben.
Következtetések
Amint mindig, kérjük, kommenteljen, és tudassa velem, ha hibát észlel ebben a cikkben, ha nem ért egyet valamivel, mondja el személyes tapasztalatait, vagy ha további ötleteket szeretne hozzátenni.