Federico Razzoli

Ultima actualizare la 8 decembrie 2019

Returnarea de rânduri aleatorii într-o ordine aleatorie dintr-o bază de date relațională este o problemă foarte dificilă. În acest articol vom vedea un antipattern, vom discuta de ce această problemă este atât de grea și vom examina câteva soluții imperfecte.

UPDATE: Unele SGBD-uri suportă TABLESAMPLE. Nu am menționat-o pentru că până astăzi cunoșteam doar implementarea SQL Server și nu o consider bună pentru extragerea de rânduri aleatorii (voi explica de ce). Dar în urma unei întrebări pe Facebook a lui Daniël van Eeden am făcut câteva cercetări și am descoperit că implementarea PostgreSQL ar putea fi mult mai potrivită. O să mai citesc despre ea și o să o încerc, iar apoi probabil voi scrie un al doilea articol despre asta. Oricum, MySQL și MariaDB nu suportă TABLESAMPLE.

În mod greșit: ORDER BY RAND()

Mulți dezvoltatori cred că o pot face în acest mod:

SELECT some_columns FROM some_table ORDER BY RAND() LIMIT 10;

Aceasta este singura interogare care face exact ceea ce se așteaptă. Dacă funcția RAND() este aleatorie în mod fiabil, aceasta returnează un set aleatoriu de rânduri, unde fiecare rând are aceleași șanse de a fi returnat.

Problema este cum funcționează sub capotă. Pentru a ordona valori aleatoare, trebuie mai întâi să le creăm. Pentru a crea o valoare aleatorie pentru fiecare rând dintr-un tabel, un SGBD trebuie să citească fiecare rând. Deci, SGBD va face o operațiune în doi pași:

1. Copiază rândurile plus o valoare aleatorie într-un tabel temporar, sperăm că în memorie;
2. Ordonează rândurile din tabelul temporar.

Rețineți că acest detaliu: sperăm că în memorie. În funcție de SGBD, pot exista motive pentru care tabelul trebuie să fie creat pe disc. De obicei, acest lucru se întâmplă dacă tabelul este prea mare. Vechile versiuni MySQL creează, de asemenea, tabele temporare pe disc dacă acestea conțin TEXT sau BLOB coloane.

Nu mai este nevoie să spunem că, dacă tabelul este mare, aceasta este o operațiune lentă care consumă multe resurse.

De ce nu oferă SGBD-urile relaționale o modalitate integrată de a returna rânduri aleatorii?

Bazele de date relaționale sunt construite în jurul unei ramuri a matematicii numită algebră relațională. Ea se bazează pe logică, deoarece se ocupă de predicte adevărat/false; ans asemănătoare cu teoria seturilor, chiar dacă o relație este ceva mai complex decât un set, și chiar și considerând-o ca un tabel nu este corect din punct de vedere matematic. Acest articol este un exemplu frumos a ceea ce vreau să spun, dar există argumente mai complexe.

În ciuda faptului că SQL nu este o implementare precisă a modelului relațional, algebra sa este folosită ca referință. Ca toate ramurile matematicii, aceasta are un set bine definit de operații. Obținerea de tupluri aleatorii dintr-o relație nu este cu siguranță una dintre ele.

Acest răspuns sună un pic prea teoretic, nu-i așa? ORDER BY și tabelele fără cheie primară încalcă, de asemenea, regulile algebrei relaționale, dar SQL le suportă.

Cu toate acestea, pentru bazele de date, viteza este vitală. SGBD-urile relaționale sunt concepute pentru a efectua operații relaționale foarte rapid. Evident, o structură de date concepută pentru a optimiza anumite operații nu este optimizată pentru alte operații. Astfel, SGBD relaționale nu sunt optimizate pentru căutări aleatorii.

Ar trebui să fie evident că parcurgerea în buclă a rândurilor pentru a alege unele dintre ele în mod aleatoriu ar fi lentă. Teoretic, citirea unui rând aleatoriu folosind un index ar fi la fel de rapidă ca și găsirea unui rând după valoarea cheii primare. Dar atunci, rânduri diferite ar avea șanse diferite de a fi alese.

Imaginea de mai sus provine dintr-un depozit GitHub al lui Jeremy Cole, innodb_diagrams. Mai devreme sau mai târziu ar trebui să scriu despre proiectele sale de analiză a structurilor de date InnoDB.

Ceea ce este important aici este că un index este un arbore ale cărui noduri sunt pagini de memorie. Nodurile de frunze conțin date reale; nivelurile superioare conțin doar informațiile necesare pentru a alege cea mai scurtă cale către nodul de frunze dorit. Detaliile nu sunt importante în acest context.

SGBD ar putea, teoretic, să aleagă o pagină aleatorie prin efectuarea unei serii de decizii aleatorii: voi merge la stânga sau la dreapta? Dar atunci, paginile frunză conțin un număr variabil de rânduri. Ele ar putea fi chiar goale. Deci, rânduri diferite ar avea șanse diferite de a fi selectate.

Rezultatul este în mod clar în afara cazurilor de utilizare prevăzute de SGBD-uri; și poate fi lent sau greșit, în funcție de utilizarea sau nu a unui index. SGBD-urile au ales pe bună dreptate să nu implementeze această caracteristică.

Câteva soluții

Nu există soluții perfecte. Există soluții care pot fi acceptabile, dar care au dezavantaje. Ar trebui să alegem una de la caz la caz.

Scoaterea aleatorie dintr-un interval

Această soluție este aplicabilă tabelelor care au o cheie primară autoincrementală. Este cea mai ușor de implementat, dar o cheie primară „fragmentată” cauzează probleme.

Consistă în verificarea id-ului minim, a id-ului maxim și generarea unui număr aleatoriu în acest interval:

Nu că interogările cu MIN() și MAX() pe orice index, fără alte clauze, sunt foarte rapide.

Rezultatul este un rând cu adevărat aleatoriu. Pentru a alege mai mult de un rând, putem repeta această interogare de mai multe ori. Acest lucru ne conduce la două dezavantaje:

• Dacă această operație este efectuată des, am putea executa această interogare de foarte multe ori.
• Nu există nicio garanție că același rând nu este selectat de mai multe ori. Dacă se întâmplă acest lucru, aplicația poate încerca din nou interogarea. Dacă tabelul este mare, acest eveniment este rar și îl putem ignora – cu excepția cazului în care funcția RAND() nu este fiabilă. Dar pentru tabelele mici, acest lucru poate fi o problemă.

De asemenea, o cheie primară poate avea găuri – cu alte cuvinte, unele numere pot lipsi. Acest lucru se datorează ștergerilor și tranzacțiilor eșuate. Numerele mai mici decât maximul nu sunt refolosite. Pentru a rezolva această problemă, putem folosi două tehnici.

Utilizarea >=

Dacă folosim operatorul >= în clauza WHERE, interogarea va returna întotdeauna un rând. În cazul în care numărul generat nu este prezent, va fi utilizat următorul. Dar acest lucru înseamnă că valorile imediat după o gaură vor avea mai multe șanse de a fi selectate. Cu cât gaura este mai mare, cu atât șansele sunt mai mari.

S-ar putea să credeți că nu ar trebui să vă pese de acest lucru și probabil că aveți dreptate. Dar înainte ca decizia dumneavoastră să fie definitivă, luați în considerare posibilitatea unei găuri mari.

Încercând din greu

Dacă interogarea nu returnează niciun rând, putem încerca din nou. Pentru tabelele mari, cu doar câteva găuri mici, acest lucru este perfect în regulă. Dar pentru găuri mari cu multe găuri, sau găuri mari, această tehnică ar putea consuma prea multe resurse.

Vă rugăm să nu fiți prea paranoici în această privință. Faceți doar niște calcule. Care este raportul de valori lipsă în tabelul dumneavoastră? Acest lucru vă spune de câte ori va fi reluată interogarea, în medie.

Selectarea mai multor rânduri

Pentru a selecta mai multe rânduri cu această tehnică, putem:

• Repeta interogarea de mai multe ori;
• Sau, pentru o performanță mai bună, folosiți operatorul >= și folosiți un LIMIT mai mare decât unu. Acest lucru face însă ca rezultatele să fie mult mai puțin aleatorii.

Mutarea alegerii aleatorii către aplicație

În forma sa cea mai simplă, această tehnică constă în alegerea aleatorie a unui bloc de id-uri contigue. Aplicația va alege aleatoriu pe care le va folosi și apoi va selecta rândurile corespunzătoare.

Să presupunem că doriți să alegeți din blocuri de 1000 de valori:

Cu cât blocul este mai mare, cu atât mai multe resurse consumate, cu atât mai aleatoriu este rezultatul. Aplicația are responsabilitatea de a alege aleatoriu id-uri unice și existente din blocuri, astfel încât nu ar trebui să fie niciodată nevoie să se reia o interogare.

Varianta MOD

O problemă cu această tehnică este că rândurile sunt returnate din același bloc de id-uri contigue. Acest lucru ar putea fi perfect acceptabil, mai ales dacă blocul este mare. Dar dacă nu este, am putea adăuga o anumită complexitate pentru a selecta un bloc de rânduri necontinue.

Ideea acestei variante este de a:

• Defini macro-blocuri de rânduri în mare parte necontinue;
• Alege la întâmplare un macro-bloc;
• Întoarce un bloc din acesta.

Pentru a face acest lucru, putem calcula modulul id-ului și îl putem folosi pentru a selecta rezultate aleatorii. De exemplu, putem defini o coloană virtuală indexată cu o expresie ca (id MOD 4). Fiecare rând va avea o valoare între 0 și 3. Chiar dacă există găuri, rândurile din aceste macroblocuri vor fi în cea mai mare parte necontinue și ar trebui să aibă aproximativ același număr.

Aplicația ar trebui să genereze un număr aleatoriu între 0 și 3. Apoi, pentru a selecta blocuri din aceste macro-blocuri:

SET @block_size := 1000;SELECT id FROM some_table WHERE id_mod = FLOOR(RAND() * 3) ORDER BY id LIMIT @block_size;

O modalitate similară de a implementa această idee este de a utiliza partiții, unde funcția de partiționare este modulul lui id. Aș sugera acest lucru numai dacă tabelul ar beneficia de partiționare din alte motive.

Salegerea unei tehnici

Tehnicile de blocuri execută mai multe interogări în comparație cu prima cu operatorul >=, iar rezultatul ar putea fi mai bun sau nu. În comparație cu varianta de reluare, aceasta ar putea rula mai multe sau mai puține interogări, iar rezultatul este mai prost.

În general, tehnicile de bloc sunt mai bune dacă avem găuri în cheia primară.

Caching random series

Metodele anterioare sunt un compromis: performanță versus o mai bună aleatoritate, unde soluția mai rapidă este și mai complexă de implementat. Atâta timp cât nu folosim antipatternul ORDER BY RAND(), selectarea seriilor aleatoare nu ar trebui să cauzeze probleme de performanță. Dar ce se întâmplă dacă da?

Am putea pune în cache niște id-uri sortate aleatoriu obținute cu oricare dintre soluțiile anterioare. Am putea folosi o interogare de genul acesta (sintaxa MySQL):

Am putea folosi seriile în ordine crescătoare sau descrescătoare, în mod aleatoriu. Sau aplicația ar putea să le amestece.

Probleme:

• Când un element este adăugat, ar trebui să alegem aleatoriu dacă trebuie să fie inserat într-o serie, înlocuind un element aleatoriu.
• Când un element este șters, ar trebui să-l ștergem din toate seriile. Ar trebui să fie înlocuit cu un alt element aleatoriu.
• Am putea dori să ștergem periodic cele mai vechi serii și să le înlocuim cu altele noi, pentru a îmbunătăți caracterul aleatoriu al experienței utilizatorului.

Concluzii

Ca de obicei, vă rog să comentați și să mă anunțați dacă observați o greșeală în acest articol, dacă nu sunteți de acord cu ceva, dacă îmi spuneți experiența dvs. personală sau dacă aveți mai multe idei de adăugat.