Federico Razzoli

Laatst bijgewerkt op 8 december 2019

Het teruggeven van willekeurige rijen in een willekeurige volgorde uit een relationele database is een zeer moeilijk probleem. In dit artikel zullen we een antipatroon zien, we zullen bespreken waarom dit probleem zo moeilijk is, en we zullen enkele onvolmaakte oplossingen bekijken.

UPDATE: Sommige DBMS’en ondersteunen TABLESAMPLE. Ik heb het niet genoemd omdat ik tot vandaag alleen de SQL Server implementatie kende, en ik beschouw het niet als goed voor het extraheren van willekeurige rijen (ik zal uitleggen waarom). Maar na een vraag op Facebook van Daniël van Eeden heb ik wat onderzoek gedaan, en ik ontdekte dat de PostgreSQL implementatie veel geschikter zou kunnen zijn. Ik zal er meer over lezen en uitproberen, en dan zal ik er waarschijnlijk een tweede artikel over schrijven. Hoe dan ook, MySQL en MariaDB ondersteunen geen TABLESAMPLE.

De verkeerde manier: ORDER BY RAND()

Veel ontwikkelaars denken dat ze het op deze manier kunnen doen:

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

Dit is de enige query die precies doet wat verwacht wordt. Als de RAND() functie betrouwbaar willekeurig is, geeft hij een willekeurige reeks rijen terug, waarbij elke rij dezelfde kans heeft om terug te komen.

Het probleem is hoe het onder de motorkap werkt. Om willekeurige waarden te ordenen, moet men ze eerst creëren. Om een willekeurige waarde te creëren voor elke rij in een tabel, moet een DBMS elke rij lezen. Dus het DBMS zal een operatie in twee stappen uitvoeren:

1. Kopieer de rijen plus een willekeurige waarde naar een tijdelijke tabel, hopelijk in het geheugen;
2. Orden de rijen in de tijdelijke tabel.

Merk op dat dit detail: hopelijk in het geheugen. Afhankelijk van het DBMS, kunnen er redenen zijn waarom de tabel op schijf moet worden aangemaakt. Typisch gebeurt dit als de tabel te groot is. Oude MySQL versies maken ook tijdelijke tabellen op schijf als ze TEXT of BLOB kolommen bevatten.

Nadeloos te zeggen, als de tabel groot is, is dit een langzame operatie die veel bronnen verbruikt.

Waarom bieden relationele DBMS’en geen ingebouwde manier om willekeurige rijen terug te geven?

Relationele databases zijn gebouwd rond een tak van wiskunde die relationele algebra wordt genoemd. Het is gebaseerd op logica, omdat het gaat over waar/onwaar predikaten; en vergelijkbaar met de verzamelingenleer, ook al is een relatie iets complexer dan een verzameling, en zelfs het zien als een tabel is wiskundig niet correct. Dit artikel is een mooi voorbeeld van wat ik bedoel, maar er zijn complexere argumenten.

Ondanks dat SQL geen precieze implementatie is van het relationele model, wordt de algebra ervan gebruikt als referentie. Zoals alle takken van wiskunde, heeft het een goed gedefinieerde reeks operaties. Het verkrijgen van willekeurige tupels uit een relatie hoort daar zeker niet bij.

Dit antwoord klinkt een beetje te theoretisch, nietwaar? ORDER BY en tabellen zonder primaire sleutel zijn ook in strijd met de regels van de relationele algebra, maar SQL ondersteunt ze.

Hoewel, voor databases is snelheid van vitaal belang. Relationele DBMS’en zijn ontworpen om zeer snel relationele bewerkingen uit te voeren. Het is duidelijk dat een gegevensstructuur die is ontworpen om bepaalde bewerkingen te optimaliseren, niet is geoptimaliseerd voor andere bewerkingen. Relationele DBMS’en zijn dus niet geoptimaliseerd voor willekeurig zoeken.

Het zou duidelijk moeten zijn dat het lussen over de rijen om er willekeurig enkele uit te kiezen, traag zou zijn. Theoretisch zou het lezen van een willekeurige rij met behulp van een index even snel zijn als het vinden van een rij op basis van de primaire sleutelwaarde. Maar dan zouden verschillende rijen verschillende kansen hebben om gekozen te worden.

De bovenstaande afbeelding komt uit een GitHub repository van Jeremy Cole, innodb_diagrams. Vroeg of laat moet ik schrijven over zijn projecten om InnoDB-datastructuren te analyseren.

Wat hier belangrijk is, is dat een index een boom is waarvan de nodes geheugenpagina’s zijn. De bladknooppunten bevatten werkelijke gegevens; de bovenste niveaus bevatten alleen informatie die nodig is om de kortste weg naar het gewenste bladknooppunt te kiezen. Details zijn in dit verband niet belangrijk.

Het DBMS zou theoretisch een willekeurige pagina kunnen kiezen door een reeks willekeurige beslissingen uit te voeren: ga ik naar links of naar rechts? Maar dan bevatten bladzijden een variabel aantal rijen. Ze kunnen zelfs leeg zijn. Dus verschillende rijen zouden verschillende kansen hebben om geselecteerd te worden.

Het resultaat ligt duidelijk buiten de beoogde gebruikssituaties van DBMS’en; en het kan langzaam of verkeerd zijn, afhankelijk van of er een index wordt gebruikt of niet. De DBMS’en hebben er terecht voor gekozen deze functie niet te implementeren.

Enkele oplossingen

Er zijn geen perfecte oplossingen. Er zijn oplossingen die aanvaardbaar kunnen zijn, maar nadelen hebben. We moeten van geval tot geval een oplossing kiezen.

Kies willekeurig uit een reeks

Deze oplossing is van toepassing op tabellen die een auto-incrementele primaire sleutel hebben. Het is het gemakkelijkst te implementeren, maar een “gefragmenteerde” primaire sleutel geeft problemen.

Het bestaat uit het controleren van het minimum id, het maximum id, en het genereren van een willekeurig getal in die range:

Niet dat queries met MIN() en MAX() op elke index, zonder andere clausules, erg snel zijn.

Het resultaat is een echt willekeurige rij. Om meer dan één rij te kiezen, kunnen we deze query meerdere keren herhalen. Dit brengt ons op twee nadelen:

• Als deze bewerking vaak wordt uitgevoerd, kunnen we deze query heel vaak uitvoeren.
• Er is geen garantie dat dezelfde rij niet meerdere keren wordt geselecteerd. Als dit gebeurt, kan de toepassing de query opnieuw proberen. Als de tabel groot is, is deze gebeurtenis zeldzaam en kunnen we het negeren – tenzij de RAND()functie onbetrouwbaar is. Maar voor kleine tabellen kan dit een probleem zijn.

Ook kan een primaire sleutel gaten hebben – met andere woorden, sommige getallen kunnen ontbreken. Dit is het gevolg van verwijderingen en mislukte transacties. Nummers lager dan het maximum worden niet hergebruikt. Om dit probleem te omzeilen, kunnen we twee technieken gebruiken.

Gebruik van >=

Als we de operator >= in de WHERE-clausule gebruiken, zal de query altijd een rij retourneren. Als het gegenereerde nummer niet aanwezig is, zal het volgende worden gebruikt. Maar dit betekent dat waarden direct na een gat meer kans hebben om geselecteerd te worden. Hoe groter het gat, hoe groter de kans.

Je denkt misschien dat je je hier niets van moet aantrekken, en je hebt waarschijnlijk gelijk. Maar voordat uw beslissing definitief is, overweeg de mogelijkheid van een groot gat.

Hard proberen

Als de query geen rijen retourneert, kunnen we het gewoon opnieuw proberen. Voor grote tabellen met slechts een paar kleine gaten, is dit perfect in orde. Maar voor grote gaten met veel gaten, of grote gaten, zou deze techniek te veel resources kunnen verbruiken.

Doe hier niet te paranoïde over. Doe gewoon wat wiskunde. Wat is de verhouding van ontbrekende waarden in uw tabel? Dit vertelt u hoe vaak de query gemiddeld opnieuw zal worden geprobeerd.

Meerdere rijen selecteren

Om meerdere rijen met deze techniek te selecteren, kunnen we:

• De query meerdere keren herhalen;
• Of, voor betere prestaties, de >= operator gebruiken en een LIMIT groter dan één gebruiken. Dit maakt de resultaten echter veel minder willekeurig.

De willekeurige keuze naar de toepassing verplaatsen

In zijn eenvoudigste vorm bestaat deze techniek uit het willekeurig kiezen van een blok aaneengesloten id’s. De toepassing kiest willekeurig welke ze zal gebruiken, en selecteert dan de overeenkomende rijen.

Voorstel dat u wilt kiezen uit blokken van 1000 waarden:

Hoe groter het blok, hoe meer middelen u verbruikt, hoe willekeuriger het resultaat is. De applicatie heeft de verantwoordelijkheid om willekeurige unieke bestaande id’s uit de blokken te kiezen, zodat het nooit nodig zou moeten zijn om een query opnieuw te proberen.

De MOD-variant

Een probleem met deze techniek is dat de rijen worden geretourneerd uit hetzelfde blok van aaneengesloten id’s. Dit kan volkomen aanvaardbaar zijn, vooral als het blok groot is. Maar als dat niet het geval is, kunnen we wat complexiteit toevoegen om een blok van niet-aaneengesloten rijen te selecteren.

Het idee van deze variant is:

• Maak macro-blokken van meestal niet-aaneengesloten rijen;
• Kies willekeurig één macro-blok;
• Retourneer een blok daaruit.

Om dit te doen, kunnen we de modulus van de id berekenen, en deze gebruiken om willekeurige resultaten te kiezen. We kunnen bijvoorbeeld een geïndexeerde virtuele kolom definiëren met een uitdrukking als (id MOD 4). Elke rij zal een waarde tussen 0 en 3 hebben. Zelfs als er gaten zijn, zullen de rijen van deze macro-blokken meestal niet aaneengesloten zijn en moeten ze ongeveer hetzelfde getal zijn.

De applicatie moet een willekeurig getal genereren tussen 0 en 3. Om vervolgens blokken uit deze macro-blokken te selecteren:

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

Een soortgelijke manier om dit idee uit te voeren is het gebruik van partities, waarbij de partitioneringsfunctie de modulus van de id is. Ik zou dit alleen voorstellen als de tabel om andere redenen baat zou hebben bij partitionering.

Kiezen van een techniek

De bloktechnieken voeren meer query’s uit in vergelijking met de eerste met de >= operator, en het resultaat zou beter kunnen zijn of niet. Vergeleken met de retry-variant zou deze meer of minder queries kunnen uitvoeren, en het resultaat is slechter.

In het algemeen zijn de bloktechnieken beter als we gaten in de primaire sleutel hebben.

Caching random series

De vorige methoden zijn een tradeoff: performance versus betere randomness, waarbij snellere oplossingen ook complexer zijn om te implementeren. Zolang we het ORDER BY RAND() antipatroon niet gebruiken, zou het selecteren van willekeurige rijen geen prestatieproblemen mogen opleveren. Maar wat als dat wel zo is?

We zouden een aantal willekeurig gesorteerde id’s kunnen cachen, verkregen met een van de voorgaande oplossingen. We zouden een query als deze kunnen gebruiken (MySQL syntaxis):

We zouden de reeksen in oplopende of aflopende volgorde kunnen gebruiken, willekeurig. Of de applicatie zou ze kunnen schudden.

Problemen:

• Wanneer een item wordt toegevoegd, moeten we willekeurig kiezen of het moet worden ingevoegd in een reeks, ter vervanging van een willekeurig item.
• Wanneer een item wordt verwijderd, moeten we het verwijderen uit alle reeksen. Het moet worden vervangen door een ander willekeurig item.
• We willen misschien periodiek de oudste series verwijderen en vervangen door nieuwe, om de willekeurigheid in de gebruikerservaring te verbeteren.

Conclusies

Zoals gewoonlijk, geef commentaar en laat het me weten als je een fout in dit artikel ziet, als je het ergens niet mee eens bent, vertel me je persoonlijke ervaring, of als je meer ideeën hebt om toe te voegen.