Ordinamento casuale ripetibile

Un ordinamento casuale ripetibile è tale che, fornendo un certo token, si ottiene sempre lo stesso ordinamento, con gli oggetti in ordine pseudo-casuale. Il token diventa così un identificatore di quello specifico ordine risultante. A token diversi corrispondono ordini diversi.

SQL Server

In SQL Server la funzione chiave per ottenere questo risultato è la funzione RAND(). Essa genera un valore casuale tra 0 e 1, e può essere controllata passando un intero che svolge il ruolo di seme della sequenza pseudo-casuale. Se non si fornisce un seme, si continua con la sequenza attuale.

Problema: RAND() come colonna di una query

Usare la funzione RAND() nella lista di campi restituiti da una query fa sì che tutte le righe abbiano lo stesso valore, sia che si specifichi un seme sia che non lo si faccia.

Secondo Panda, il valore viene calcolato una sola volta e incluso nella tabella, anziché essere ricalcolato ad ogni riga.

Soluzione: introdurre entropia tramite il seme

Niente ci vieta di inizializzare la sequenza pseudo-casuale con un seme che varia ad ogni riga. Questo introduce entropia nel sistema, in quantità pari all'entropia presente nel seme usato.

Ciò significa che, di caso in caso, bisogna valutare cosa usare come seme. Gli ID numerici in generale non sono una buona scelta, perché solitamente sono interi ordinati e quasi sempre contigui. Un tipo di dato a più alta entropia è la stringa di testo: in questo caso è possibile usare una funzione di hash (come CHECKSUM() o MD5()) per trasformare la stringa in un intero e usarla quindi come seme.

Nota sull'entropia

Se è vero che stringhe di testo più lunghe hanno una maggiore entropia, non è sempre vero che passare alla funzione di hash una stringa composta dalla concatenazione di più campi aumenti l'entropia e renda quindi "più casuale" l'ordinamento. Ad esempio, in una tabella con un titolo e una descrizione, "Titolo - Descrizione" non ha, di solito, più entropia del solo Titolo o della sola Descrizione, perché se due oggetti hanno un titolo diverso è raro che la descrizione non sia diversa anch'essa.

Anche se non è proprio corretto, possiamo dire che l'entropia è proporzionale alla quantità di informazione. Se ci fossero molti casi di oggetti con lo stesso titolo che possono essere discriminati grazie alla descrizione, allora aggiungere la descrizione aumenterebbe l'entropia.

Problema: perdita di controllo sull'output

Se la funzione RAND() viene inizializzata con una componente variabile legata alla riga, ogni riga avrà come risultato un valore diverso. A noi però interessa ottenere ordinamenti diversi, e identificarli con un parametro semplice (un intero).

Soluzione: modificare il seme con una componente parametrica

Se al risultato della funzione di hash applichiamo un'altra trasformazione parametrica (anche una semplice addizione), otteniamo un seme controllabile, il cui valore dipende dalla riga e dal valore di un parametro.

Modello di query finale

   SELECT
       *, RAND(CHECKSUM(tabella.campo) + 1341) AS Random
   FROM tabella
   ORDER BY Random;