Federico Razzoli

Sidst opdateret den 8. december 2019

Det er et meget svært problem at returnere tilfældige rækker i en tilfældig rækkefølge fra en relationel database. I denne artikel vil vi se et anti-mønster, vi vil diskutere hvorfor dette problem er så svært, og vi vil undersøge nogle ufuldkomne løsninger.

UPDATE: Nogle DBMS’er understøtter TABLESAMPLE. Jeg nævnte det ikke, fordi jeg indtil i dag kun kendte SQL Server-implementeringen, og jeg mener ikke, at den er god til at udtrække tilfældige rækker (jeg vil forklare hvorfor). Men efter et spørgsmål på Facebook af Daniël van Eeden lavede jeg nogle undersøgelser, og jeg opdagede, at PostgreSQL-implementeringen kunne være meget mere egnet. Jeg vil mere læse om det og prøve det, og så vil jeg sandsynligvis skrive en anden artikel om det. Anyway, MySQL og MariaDB understøtter ikke TABLESAMPLE.

Den forkerte måde: ORDER BY RAND()

Mange udviklere tror, at de kan gøre det på denne måde:

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

Dette er den eneste forespørgsel, der gør præcis, hvad der forventes. Hvis RAND()-funktionen er pålideligt tilfældig, returnerer den et tilfældigt sæt rækker, hvor hver række har de samme chancer for at blive returneret.

Problemet er, hvordan det fungerer under motorhjelmen. For at bestille tilfældige værdier skal man først oprette dem. For at oprette en tilfældig værdi for hver række i en tabel, skal et DBMS læse hver række. Så DBMS’et vil foretage en operation i to trin:

1. Kopierer rækkerne plus en tilfældig værdi til en midlertidig tabel, forhåbentlig i hukommelsen;
2. Ordner rækkerne i den midlertidige tabel.

Bemærk, at denne detalje: forhåbentlig i hukommelsen. Afhængigt af DBMS’et kan der være grunde til, at tabellen skal oprettes på disken. Typisk sker dette, hvis tabellen er for stor. Gamle MySQL-versioner opretter også midlertidige tabeller på disken, hvis de indeholder TEXT eller BLOB kolonner.

Nødvendigt at sige, at hvis tabellen er stor, er dette en langsom operation, der bruger mange ressourcer.

Hvorfor har relationelle DBMS’er ikke en indbygget måde at returnere tilfældige rækker på?

Relationelle databaser er bygget op omkring en gren af matematikken kaldet relationel algebra. Den er baseret på logik, fordi den beskæftiger sig med sand/falsk-prædikater; og ligner mængdelæren, selv om en relation er noget mere komplekst end en mængde, og selv at se den som en tabel er ikke matematisk korrekt. Denne artikel er et fint eksempel på hvad jeg mener, men der er mere komplekse argumenter.

Selv om SQL ikke er en præcis implementering af den relationelle model, bruges dens algebra som reference. Som alle grene af matematikken har den et veldefineret sæt af operationer. At hente tilfældige tupler fra en relation er bestemt ikke en af dem.

Dette svar lyder en smule for teoretisk, ikke sandt? ORDER BY og tabeller uden en primær nøgle overtræder også reglerne i relationel algebra, men SQL understøtter dem.

Hvorom alting er, er hastighed afgørende for databaser. Relationelle DBMS’er er designet til at udføre relationelle operationer meget hurtigt. Det er indlysende, at en datastruktur, der er designet til at optimere visse operationer, ikke er optimeret til andre operationer. Relationelle DBMS’er er således ikke optimeret til tilfældige søgninger.

Det burde være indlysende, at det ville være langsomt at løbe gennem linjerne for at vælge nogle af dem tilfældigt. Teoretisk set ville det være lige så hurtigt at læse en tilfældig række ved hjælp af et indeks som at finde en række ved hjælp af primærnøgleværdien. Men så ville forskellige rækker have forskellige chancer for at blive valgt.

Overstående billede er fra et Jeremy Cole’s GitHub repository, innodb_diagrams. Før eller senere bør jeg skrive om hans projekter til analyse af InnoDB-datastrukturer.

Det vigtige her er, at et indeks er et træ, hvis knuder er hukommelsessider. Bladknuderne indeholder egentlige data; de øverste niveauer indeholder kun de oplysninger, der er nødvendige for at vælge den korteste vej til den ønskede bladknude. Detaljerne er ikke vigtige i denne sammenhæng.

DBMS’et kunne teoretisk set vælge en tilfældig side ved at udføre en række tilfældige beslutninger: Vil jeg gå til venstre eller til højre? Men så indeholder bladsiderne et variabelt antal rækker. De kunne endda være tomme. Så forskellige rækker ville have forskellige chancer for at blive valgt.

Resultatet ligger klart uden for DBMS’s tilsigtede anvendelsesområder; og det kan være langsomt eller forkert, afhængigt af om der bruges et indeks eller ej. DBMS’erne har med rette valgt ikke at implementere denne funktion.

Nogle løsninger

Der findes ingen perfekte løsninger. Der er løsninger, som kan være acceptable, men som har ulemper. Vi bør vælge en fra sag til sag.

Valg tilfældigt fra et interval

Denne løsning gælder for tabeller, der har en autoinkrementel primærnøgle. Den er den nemmeste at implementere, men en “fragmenteret” primær nøgle giver problemer.

Den består i at kontrollere det mindste id, det største id og generere et tilfældigt tal i dette interval:

Det er ikke sådan, at forespørgsler med MIN() og MAX() på et hvilket som helst indeks, uden andre klausuler, er meget hurtige.

Resultatet er en virkelig tilfældig række. Hvis vi vil vælge mere end én række, kan vi gentage denne forespørgsel flere gange. Dette fører os til to ulemper:

• Hvis denne operation udføres ofte, kan vi køre denne forespørgsel mange gange.
• Der er ingen garanti for, at den samme række ikke bliver valgt flere gange. Hvis dette sker, kan programmet prøve forespørgslen igen. Hvis tabellen er stor, er denne hændelse sjælden, og vi kan ignorere den – medmindre RAND()funktionen er upålidelig. Men for små tabeller kan dette være et problem.

Der kan også være huller i en primærnøgle – med andre ord kan der mangle nogle tal. Dette skyldes sletninger og mislykkede transaktioner. Tal, der er lavere end det maksimale, genbruges ikke. For at omgå dette problem kan vi bruge to teknikker:

Anvendelse af >=

Hvis vi bruger operatoren >= i WHERE-klausulen, vil forespørgslen altid returnere en række. Hvis det genererede nummer ikke er til stede, vil det næste nummer blive brugt. Men det betyder, at værdier umiddelbart efter et hul vil have flere chancer for at blive valgt. Jo større hul, jo større chancer.

Du tænker måske, at du ikke bør bekymre dig om dette, og det har du sikkert ret i. Men før din beslutning er endelig, skal du overveje muligheden for et stort hul.

Trying hard

Hvis forespørgslen ikke returnerer nogen rækker, kan vi bare prøve igen. For store tabeller med kun et par små huller er dette helt fint. Men for store huller med mange huller, eller store huller, kan denne teknik forbruge for mange ressourcer.

Du skal ikke være for paranoid med hensyn til dette. Bare lav lidt matematik. Hvad er forholdet mellem manglende værdier i din tabel? Det fortæller dig, hvor mange gange forespørgslen vil blive forsøgt igen, i gennemsnit.

Selektion af flere rækker

For at vælge flere rækker med denne teknik kan vi:

• Og gentage forespørgslen flere gange;
• Og for bedre ydeevne kan du bruge >=-operatoren og bruge en LIMIT større end én. Dette gør dog resultaterne meget mindre tilfældige.

Flytning af det tilfældige valg til applikationen

I sin enkleste form består denne teknik i tilfældigt at vælge en blok af sammenhængende id’er. Applikationen vælger tilfældigt, hvilke den vil bruge, og vælger derefter de matchende rækker.

Sæt, at du vil vælge mellem blokke med 1000 værdier:

Desto større blok, jo flere ressourcer du bruger, jo mere tilfældigt er resultatet. Programmet har ansvaret for at vælge tilfældige unikke eksisterende id’er fra blokkene, så der bør aldrig være behov for at gentage en forespørgsel.

MOD-varianten

Et problem med denne teknik er, at rækkerne returneres fra den samme blok af sammenhængende id’er. Dette kan være helt acceptabelt, især hvis blokken er stor. Men hvis den ikke er det, kunne vi tilføje noget kompleksitet for at vælge en blok af ikke-sammenhængende rækker.

Ideen med denne variant er at:

• Definere makroblokke af for det meste ikke-sammenhængende rækker;
• Vælg tilfældigt en makroblok;
• Returnerer en blok fra den.

For at gøre dette kan vi beregne id’ets modulus og bruge det til at vælge tilfældige resultater. Vi kan f.eks. definere en indekseret virtuel kolonne med et udtryk som (id MOD 4). Hver række vil have en værdi mellem 0 og 3. Selv om der er huller, vil rækker fra disse makroblokke for det meste være ikke-sammenhængende, og de bør være omtrent det samme tal.

Programmet bør generere et tilfældigt tal mellem 0 og 3. Derefter skal der vælges blokke fra disse makroblokke:

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

En lignende måde at implementere denne idé på er at anvende partitioner, hvor partitionsfunktionen er id’ets modulus. Jeg vil kun foreslå dette, hvis tabellen ville have gavn af partitionering af andre grunde.

Valg af teknik

Blokteknikkerne kører flere forespørgsler sammenlignet med den første med >=-operatoren, og resultatet kan være bedre eller ej. Sammenlignet med retry-varianten kunne denne køre flere eller færre forespørgsler, og resultatet er dårligere.

Generelt er blokteknikkerne bedre, hvis vi har huller i primærnøglen.

Caching af tilfældige serier

De foregående metoder er en afvejning: ydeevne versus bedre tilfældighed, hvor hurtigere løsning også er mere kompleks at implementere. Så længe vi ikke bruger ORDER BY RAND() antipattern, bør udvælgelse af tilfældige rækker ikke give problemer med ydeevnen. Men hvad hvis det gør?

Vi kunne cache nogle tilfældigt sorterede id’er, der er opnået med en af de tidligere løsninger. Vi kunne bruge en forespørgsel som denne (MySQL-syntaks):

Vi kunne bruge serierne i stigende eller faldende rækkefølge, tilfældigt. Eller programmet kunne blande dem.

Problemer:

• Når et element tilføjes, skal vi vælge tilfældigt, om det skal indsættes i en serie og erstatte et tilfældigt element.
• Når et element slettes, skal vi slette det fra alle serier. Det bør erstattes af et andet tilfældigt emne.
• Vi kan med jævne mellemrum slette de ældste serier og erstatte dem med nye, for at forbedre tilfældigheden i brugeroplevelsen.

Konklusioner

Som sædvanlig er du velkommen til at kommentere og lade mig vide, hvis du opdager en fejl i denne artikel, hvis du er uenig i noget, fortælle mig din personlige erfaring, eller hvis du har flere ideer, der kan tilføjes.