Hur man returnerar slumpmässiga rader från en tabell - Federico Razzoli

Sist uppdaterad den 8 december 2019

Jag tror att detta är helt slumpmässigt, men jag kan ha fel

Att returnera slumpmässiga rader i en slumpmässig ordning från en relationsdatabas är ett mycket svårt problem. I den här artikeln kommer vi att se ett anti-mönster, vi kommer att diskutera varför problemet är så svårt och vi kommer att undersöka några ofullkomliga lösningar.

UPPDATERING: Vissa DBMS har stöd för TABLESAMPLE. Jag nämnde det inte eftersom jag fram till idag bara kände till SQL Server-implementationen, och jag anser inte att den är bra för att extrahera slumpmässiga rader (jag ska förklara varför). Men efter en fråga på Facebook av Daniël van Eeden gjorde jag lite efterforskningar och upptäckte att PostgreSQL-implementationen kan vara mycket mer lämplig. Jag ska mer läsa om det och prova det, och sedan kommer jag förmodligen att skriva en andra artikel om det. Hur som helst, MySQL och MariaDB har inte stöd för TABLESAMPLE.

Feltt sätt: ORDER BY RAND()

Många utvecklare tror att de kan göra det på det här sättet:

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

Detta är den enda fråga som gör exakt vad som förväntas. Om RAND()-funktionen är tillförlitligt slumpmässig returnerar den en slumpmässig uppsättning rader, där varje rad har samma chans att returneras.

Problemet är hur det fungerar under huven. För att beställa slumpmässiga värden måste man först skapa dem. För att skapa ett slumpmässigt värde för varje rad i en tabell måste ett DBMS läsa varje rad. Så DBMS kommer att göra en operation i två steg:

Kopiera raderna plus ett slumpmässigt värde till en tillfällig tabell, förhoppningsvis i minnet;
Ordna raderna i den tillfälliga tabellen.

Notera att denna detalj: förhoppningsvis i minnet. Beroende på DBMS kan det finnas skäl till att tabellen måste skapas på disk. Typiskt sett händer detta om tabellen är för stor. Gamla MySQL-versioner skapar också tillfälliga tabeller på disken om de innehåller TEXT eller BLOB kolumner.

Nödvändigt att säga att om tabellen är stor är detta en långsam operation som förbrukar en hel del resurser.

Varför tillhandahåller inte relationella DBMS ett inbyggt sätt att returnera slumpmässiga rader?

Relationella databaser är uppbyggda kring en gren av matematiken som kallas relationell algebra. Den är baserad på logik, eftersom den behandlar sant/fel-predikationer, och liknar mängdteorin, även om en relation är något mer komplext än en mängd, och det är inte matematiskt korrekt att se den som en tabell. Den här artikeln är ett bra exempel på vad jag menar, men det finns mer komplexa argument.

Trots att SQL inte är en exakt implementering av relationsmodellen används dess algebra som referens. Liksom alla grenar av matematiken har den en väldefinierad uppsättning operationer. Att hämta slumpmässiga tupler från en relation är definitivt inte en av dem.

Detta svar låter lite för teoretiskt, eller hur? ORDER BY och tabeller utan primärnyckel bryter också mot reglerna för relationsalgebra, men SQL stöder dem.

För databaser är dock snabbhet avgörande. Relationella DBMS är utformade för att utföra relationella operationer mycket snabbt. Det är uppenbart att en datastruktur som utformats för att optimera vissa operationer inte är optimerad för andra operationer. Relationella databaser är alltså inte optimerade för slumpmässiga sökningar.

Det borde vara uppenbart att det skulle vara långsamt att slinga över raderna för att välja några av dem slumpmässigt. Teoretiskt sett skulle det vara lika snabbt att läsa en slumpmässig rad med hjälp av ett index som att hitta en rad med hjälp av primärnyckelvärdet. Men då skulle olika rader ha olika chanser att väljas.

Ovanstående bild kommer från en Jeremy Coles GitHub repository, innodb_diagrams. Förr eller senare bör jag skriva om hans projekt för att analysera InnoDB-datastrukturer.

Det viktiga här är att ett index är ett träd vars noder är minnessidor. Bladnoderna innehåller faktiska data; de övre nivåerna innehåller endast information som behövs för att välja den kortaste vägen till den önskade bladnoden. Detaljer är inte viktiga i det här sammanhanget.

Debmssystemet skulle teoretiskt sett kunna välja en slumpmässig sida genom att utföra en rad slumpmässiga beslut: Ska jag gå till vänster eller till höger? Men då innehåller bladsidor ett variabelt antal rader. De kan till och med vara tomma. Så olika rader skulle ha olika chanser att väljas.

Resultatet ligger helt klart utanför DBMS avsedda användningsområden; och det kan vara långsamt eller fel, beroende på om ett index används eller inte. DBMS har med rätta valt att inte implementera denna funktion.

Vissa lösningar

Det finns inga perfekta lösningar. Det finns lösningar som kan vara acceptabla men som har nackdelar. Vi bör välja en från fall till fall.

Välja slumpmässigt från ett intervall

Denna lösning är tillämplig på tabeller som har en autoinkrementell primärnyckel. Den är lättast att genomföra, men en ”fragmenterad” primärnyckel orsakar problem.

Det går ut på att kontrollera minsta id, största id och generera ett slumpmässigt nummer i det intervallet:

Inte att förfrågningar med MIN() och MAX() på alla index, utan andra klausuler, är mycket snabba.

Resultatet är en verkligt slumpmässig rad. För att välja mer än en rad kan vi upprepa denna fråga flera gånger. Detta leder oss till två nackdelar:

Om denna operation utförs ofta kan vi köra denna fråga många gånger.
Det finns ingen garanti för att samma rad inte väljs flera gånger. Om detta inträffar kan programmet försöka göra om frågan på nytt. Om tabellen är stor är denna händelse sällsynt och vi kan ignorera den – om inte RAND()funktionen är opålitlig. Men för små tabeller kan detta vara ett problem.

Den primära nyckeln kan också ha hål – med andra ord kan vissa siffror saknas. Detta beror på raderingar och misslyckade transaktioner. Nummer som är lägre än maxgränsen återanvänds inte. För att komma runt det här problemet kan vi använda två tekniker:

Användning av >=

Om vi använder >=-operatorn i WHERE-klausulen kommer frågan alltid att returnera en rad. Om det genererade numret inte finns kommer nästa nummer att användas. Men detta innebär att värden omedelbart efter ett hål kommer att ha större chans att väljas ut. Ju större hål, desto större chanser.

Du kanske tänker att du inte borde bry dig om detta, och du har förmodligen rätt. Men innan ditt beslut är slutgiltigt bör du överväga möjligheten av ett stort hål.

Trying hard

Om frågan inte returnerar några rader kan vi bara göra ett nytt försök. För stora tabeller med bara några små hål är detta helt okej. Men för stora hål med många hål, eller stora hål, kan denna teknik förbruka för mycket resurser.

Var snäll och var inte alltför paranoid om detta. Gör bara några beräkningar. Hur stor är andelen saknade värden i din tabell? Detta talar om för dig hur många gånger frågan kommer att försöka igen, i genomsnitt.

Välja flera rader

För att välja flera rader med den här tekniken kan vi:

Välja frågan flera gånger;
Och, för bättre prestanda, använda >=-operatorn och använda ett LIMIT större än ett. Detta gör dock resultaten mycket mindre slumpmässiga.

Förflytta det slumpmässiga valet till applikationen

I sin enklaste form består den här tekniken i att slumpmässigt välja ett block av sammanhängande id:er. Applikationen väljer slumpmässigt vilka den ska använda och väljer sedan de matchande raderna.

Antag att du vill välja från block med 1000 värden:

Desto större block, desto mer resurser förbrukar du och desto mer slumpmässigt blir resultatet. Programmet har ansvaret för att välja slumpmässiga unika existerande id:n från blocken, så det bör aldrig finnas behov av att göra om en fråga.

MOD-varianten

Ett problem med den här tekniken är att raderna returneras från samma block av sammanhängande id:n. Detta kan vara helt acceptabelt, särskilt om blocket är stort. Men om det inte är det kan vi lägga till en viss komplexitet för att välja ett block av icke sammanhängande rader.

Tanken med denna variant är att:

Definiera makroblock av mestadels icke sammanhängande rader;
Välja slumpmässigt ett makroblock;
Returnera ett block från det.

För att göra detta kan vi beräkna id:s modul och använda den för att välja slumpmässiga resultat. Vi kan till exempel definiera en indexerad virtuell kolumn med ett uttryck som (id MOD 4). Varje rad kommer att ha ett värde mellan 0 och 3. Även om det finns hål kommer rader från dessa makroblock för det mesta att vara icke sammanhängande och de bör vara ungefär lika många.

Programmet bör generera ett slumpmässigt tal mellan 0 och 3. För att sedan välja block från dessa makroblock:

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

Ett liknande sätt att genomföra denna idé är att använda partitioner, där partitioneringsfunktionen är id:s modulus. Jag skulle bara föreslå detta om tabellen skulle gynnas av partitionering av andra skäl.

Välja en teknik

Blockteknikerna kör fler frågor jämfört med den första med operatören >=, och resultatet kan vara bättre eller inte. Jämfört med retry-varianten kan denna köra fler eller färre frågor, och resultatet är sämre.

Generellt sett är blockteknikerna bättre om vi har hål i primärnyckeln.

Cachelagring av slumpmässiga serier

De tidigare metoderna är en avvägning: prestanda kontra bättre slumpmässighet, där snabbare lösning också är mer komplicerad att genomföra. Så länge vi inte använder ORDER BY RAND() antipattern bör valet av slumpmässiga rader inte orsaka prestandaproblem. Men vad händer om det gör det?

Vi skulle kunna cacha några slumpmässigt sorterade id:n som erhållits med någon av de tidigare lösningarna. Vi skulle kunna använda en fråga som denna (MySQL-syntax):

Vi skulle kunna använda serierna i stigande eller fallande ordning, slumpmässigt. Eller så skulle programmet kunna blanda dem.

Problem:

När ett objekt läggs till ska vi välja slumpmässigt om det ska läggas in i en serie och ersätta ett slumpmässigt objekt.
När ett objekt tas bort ska vi ta bort det från alla serier. Den bör ersättas av ett annat slumpmässigt objekt.
Vi kanske vill radera de äldsta serierna med jämna mellanrum och ersätta dem med nya, för att förbättra slumpmässigheten i användarupplevelsen.

Slutsatser

Som vanligt är du välkommen att kommentera och meddela mig om du upptäcker ett fel i den här artikeln, om du inte håller med om något, berätta om dina personliga erfarenheter eller om du har fler idéer att lägga till.