Federico Razzoli

Ultimo aggiornamento del 8 dicembre 2019

Ritornare righe casuali in ordine casuale da un database relazionale è un problema molto difficile. In questo articolo vedremo un antipattern, discuteremo perché questo problema è così difficile, ed esamineremo alcune soluzioni imperfette.

Aggiornamento: Alcuni DBMS supportano TABLESAMPLE. Non ne ho parlato perché fino ad oggi conoscevo solo l’implementazione di SQL Server, e non la considero buona per estrarre righe casuali (spiegherò perché). Ma dopo una domanda su Facebook di Daniël van Eeden ho fatto qualche ricerca, e ho scoperto che l’implementazione di PostgreSQL potrebbe essere molto più adatta. Lo leggerò e lo proverò, e poi probabilmente scriverò un secondo articolo su di esso. Comunque, MySQL e MariaDB non supportano TABLESAMPLE.

Il modo sbagliato: ORDER BY RAND()

Molti sviluppatori pensano di poterlo fare in questo modo:

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

Questa è l’unica query che fa esattamente ciò che ci si aspetta. Se la funzione RAND()è attendibilmente casuale, restituisce un insieme casuale di righe, dove ogni riga ha le stesse possibilità di essere restituita.

Il problema è come funziona sotto il cofano. Per ordinare i valori casuali, bisogna prima crearli. Per creare un valore casuale per ogni riga di una tabella, un DBMS deve leggere ogni riga. Quindi il DBMS farà un’operazione in due fasi:

1. Copia le righe più un valore casuale in una tabella temporanea, si spera in memoria;
2. Ordina le righe nella tabella temporanea.

Nota che questo dettaglio: si spera in memoria. A seconda del DBMS, ci potrebbero essere motivi per cui la tabella deve essere creata su disco. In genere, questo accade se la tabella è troppo grande. Le vecchie versioni di MySQL creano anche tabelle temporanee su disco se contengono TEXT o BLOB colonne.

Inutile dire che se la tabella è grande questa è un’operazione lenta che consuma molte risorse.

Perché i DBMS relazionali non forniscono un modo integrato per restituire righe casuali?

I database relazionali sono costruiti intorno a un ramo della matematica chiamato algebra relazionale. È basata sulla logica, perché si occupa di predicati vero/falso; è simile alla teoria degli insiemi, anche se una relazione è qualcosa di più complesso di un insieme, e anche vederla come una tabella non è matematicamente corretto. Questo articolo è un bell’esempio di ciò che intendo, ma ci sono argomenti più complessi.

Nonostante SQL non sia un’implementazione precisa del modello relazionale, la sua algebra è usata come riferimento. Come tutti i rami della matematica, ha un insieme ben definito di operazioni. Ottenere tuple a caso da una relazione non è sicuramente una di queste.

Questa risposta suona un po’ troppo teorica, vero? ORDER BY Anche le tabelle senza chiave primaria violano le regole dell’algebra relazionale, ma SQL le supporta.

Tuttavia, per i database, la velocità è vitale. I DBMS relazionali sono progettati per eseguire operazioni relazionali molto rapidamente. Ovviamente, una struttura di dati progettata per ottimizzare certe operazioni non è ottimizzata per altre operazioni. Quindi, i DBMS relazionali non sono ottimizzati per le ricerche casuali.

Dovrebbe essere ovvio che fare il looping sulle righe per sceglierne alcune in modo casuale sarebbe lento. Teoricamente, leggere una riga casuale usando un indice sarebbe veloce quanto trovare una riga in base al valore della chiave primaria. Ma allora, diverse righe avrebbero diverse possibilità di essere scelte.

L’immagine sopra è tratta da un repository GitHub di Jeremy Cole, innodb_diagrams. Prima o poi dovrei scrivere dei suoi progetti per analizzare le strutture dati InnoDB.

Quello che è importante qui è che un indice è un albero i cui nodi sono pagine di memoria. I nodi foglia contengono dati effettivi; i livelli superiori contengono solo informazioni necessarie per scegliere il percorso più breve verso il nodo foglia desiderato. I dettagli non sono importanti in questo contesto.

Il DBMS potrebbe teoricamente scegliere una pagina casuale eseguendo una serie di decisioni casuali: vado a sinistra o a destra? Ma poi, le pagine fogliare contengono un numero variabile di righe. Potrebbero anche essere vuote. Quindi, diverse righe avrebbero diverse possibilità di essere selezionate.

Il risultato è chiaramente al di fuori dei casi d’uso previsti dai DBMS; e può essere lento o sbagliato, a seconda che si usi o meno un indice. I DBMS hanno giustamente scelto di non implementare questa caratteristica.

Alcune soluzioni

Non ci sono soluzioni perfette. Ci sono soluzioni che possono essere accettabili ma hanno degli svantaggi. Dovremmo sceglierne una di caso in caso.

Scegliere a caso da un intervallo

Questa soluzione è applicabile alle tabelle che hanno una chiave primaria autoincrementale. È la più semplice da implementare, ma una chiave primaria “frammentata” causa problemi.

Consiste nel controllare l’id minimo, l’id massimo e generare un numero casuale in quell’intervallo:

Non che le query con MIN() e MAX() su qualsiasi indice, senza altre clausole, siano molto veloci.

Il risultato è una riga veramente casuale. Per scegliere più di una riga, possiamo ripetere questa query più volte. Questo ci porta a due inconvenienti:

• Se questa operazione viene eseguita spesso, potremmo eseguire questa query molte volte.
• Non c’è garanzia che la stessa riga non venga selezionata più volte. Se questo accade, l’applicazione potrebbe riprovare la query. Se la tabella è grande, questo evento è raro e possiamo ignorarlo – a meno che la funzione RAND()sia inaffidabile. Ma per le piccole tabelle, questo può essere un problema.

Inoltre, una chiave primaria può avere dei buchi – in altre parole, alcuni numeri possono mancare. Questo è dovuto a cancellazioni e transazioni fallite. I numeri inferiori al massimo non vengono riutilizzati. Per aggirare questo problema, possiamo usare due tecniche.

Usando >=

Se usiamo l’operatore >= nella clausola WHERE, la query restituirà sempre una riga. Se il numero generato non è presente, verrà utilizzato il successivo. Ma questo significa che i valori immediatamente dopo un buco avranno più possibilità di essere selezionati. Più grande è il buco, più alte sono le possibilità.

Potreste pensare che non dovreste preoccuparvi di questo, e probabilmente avete ragione. Ma prima che la tua decisione sia definitiva, considera la possibilità di un grande buco.

Provando duramente

Se la query non restituisce alcuna riga, possiamo semplicemente riprovare. Per le grandi tabelle con pochi piccoli buchi, questo va perfettamente bene. Ma per le tabelle grandi con molti buchi, o buchi grandi, questa tecnica potrebbe consumare troppe risorse.

Non siate troppo paranoici su questo. Basta fare un po’ di conti. Qual è il rapporto dei valori mancanti nella vostra tabella? Questo ti dice quante volte la query verrà ripetuta, in media.

Selezione di più righe

Per selezionare più righe con questa tecnica, possiamo:

• Ripetere la query più volte;
• Oppure, per una migliore performance, usare l’operatore >= e usare un LIMIT maggiore di uno. Questo però rende i risultati molto meno casuali.

Spostando la scelta casuale all’applicazione

Nella sua forma più semplice, questa tecnica consiste nello scegliere casualmente un blocco di id contigui. L’applicazione sceglierà casualmente quali userà, e poi selezionerà le righe corrispondenti.

Supponiamo di voler scegliere tra blocchi di 1000 valori:

Più grande è il blocco, più risorse si consumano, più casuale è il risultato. L’applicazione ha la responsabilità di scegliere dai blocchi degli id unici casuali esistenti, quindi non dovrebbe mai esserci la necessità di riprovare una query.

La variante MOD

Un problema con questa tecnica è che le righe vengono restituite dallo stesso blocco di id contigui. Questo potrebbe essere perfettamente accettabile, specialmente se il blocco è grande. Ma se non lo è, potremmo aggiungere un po’ di complessità per selezionare un blocco di righe non contigue.

L’idea di questa variante è di:

• Definire macro-blocchi di righe per lo più non contigue;
• Scegliere casualmente un macro-blocco;
• Ritorna un blocco da esso.

Per fare questo, possiamo calcolare il modulo dell’id e usarlo per selezionare risultati casuali. Per esempio, possiamo definire una colonna virtuale indicizzata con un’espressione come (id MOD 4). Ogni riga avrà un valore tra 0 e 3. Anche se ci sono dei buchi, le righe di questi macroblocchi saranno per lo più non contigue e dovrebbero essere approssimativamente lo stesso numero.

L’applicazione dovrebbe generare un numero casuale tra 0 e 3. Poi, per selezionare i blocchi da questi macro-blocchi:

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

Un modo simile per implementare questa idea è usare le partizioni, dove la funzione di partizionamento è il modulo dell’id. Lo suggerirei solo se la tabella beneficerebbe del partizionamento per altre ragioni.

Scegliere una tecnica

La tecnica dei blocchi esegue più query rispetto alla prima con l’operatore >=, e il risultato potrebbe essere migliore o meno. Rispetto alla variante retry, questa potrebbe eseguire più o meno query, e il risultato è peggiore.

Generalmente, le tecniche a blocchi sono migliori se abbiamo dei buchi nella chiave primaria.

Caching delle serie casuali

I metodi precedenti sono un compromesso: prestazioni contro una migliore casualità, dove la soluzione più veloce è anche più complessa da implementare. Finché non usiamo l’antipattern ORDER BY RAND(), la selezione di righe casuali non dovrebbe causare problemi di prestazioni. Ma se così fosse?

Potremmo mettere in cache alcuni id ordinati in modo casuale ottenuti con una qualsiasi delle soluzioni precedenti. Potremmo usare una query come questa (sintassi MySQL):

Potremmo usare le serie in ordine crescente o decrescente, in modo casuale. Oppure l’applicazione potrebbe mischiarle.

Problemi:

• Quando un elemento viene aggiunto, dovremmo scegliere casualmente se deve essere inserito in una serie, sostituendo un elemento casuale.
• Quando un elemento viene cancellato, dovremmo cancellarlo da tutte le serie. Dovrebbe essere sostituito da un altro elemento casuale.
• Potremmo voler cancellare periodicamente le serie più vecchie e sostituirle con nuove, per migliorare la casualità nell’esperienza dell’utente.

Conclusioni

Come al solito, per favore commentate e fatemi sapere se individuate un errore in questo articolo, se non siete d’accordo su qualcosa, raccontatemi la vostra esperienza personale, o se avete altre idee da aggiungere.