SQL: selezionare una riga a caso, ma tenendo conto di un peso

Sto usando MySQL. Ho un tavolo che sembra così:

id: primary key content: varchar weight: int 

Quello che voglio fare è selezionare casualmente una riga da questa tabella, ma tenendo conto del peso. Ad esempio, se ho 3 righe:

 id, content, weight 1, "some content", 60 2, "other content", 40 3, "something", 100 

La prima fila ha il 30% di probabilità di essere selezionata, la seconda fila ha il 20% di possibilità di essere selezionata, e la terza fila ha il 50% di possibilità di essere selezionata.

C’è un modo per farlo? Se devo eseguire 2 o 3 query non è un problema.

Ho provato la soluzione di van e, sebbene funzioni, non è veloce.

La mia soluzione

Il modo in cui risolvo questo problema è il mantenimento di una tabella separata e collegata per la ponderazione. La struttura di base della tabella è simile a questa:

 CREATE TABLE `table1` ( `id` int(11) UNSIGNED AUTO_INCREMENT PRIMARY KEY, `name` varchar(100), `weight` tinyint(4) NOT NULL DEFAULT '1', ); CREATE TABLE `table1_weight` ( `id` bigint(20) UNSIGNED AUTO_INCREMENT PRIMARY KEY, `table1_id` int(11) NOT NULL ); 

Se ho un record in table1 con un peso di 3, quindi creo 3 record in table1_weight , collegato a table1 tramite il campo table1_id . Qualunque sia il valore del weight in table1 , è il numero di record collegati che creo in table1_weight .

analisi

Su un set di dati con 976 record in table1 con un peso totale di 2031 e quindi 2031 record in table1_weight , ho eseguito i seguenti due SQL:

1) Una versione della soluzione di van

 SELECT t.* FROM table1 t INNER JOIN ( SELECT t.id, SUM(tt.weight) AS cum_weight FROM table1 t INNER JOIN table1 tt ON tt.id <= t.id GROUP BY t.id) tc ON tc.id = t.id, ( SELECT SUM(weight) AS total_weight FROM table1) tt, ( SELECT RAND() AS rnd) r WHERE r.rnd * tt.total_weight <= tc.cum_weight ORDER BY t.id ASC LIMIT 1 

2) Unirsi a un tavolo secondario per la ponderazione

 SELECT t.* FROM table1 t INNER JOIN table1_weight w ON w.table1_id = t.id ORDER BY RAND() LIMIT 1 

SQL 1 richiede costantemente 0,4 secondi.

SQL 2 richiede tra 0,01 e 0,02 secondi.

Conclusione

Se la velocità di selezione di un record casuale ponderato non è un problema, allora la singola tabella SQL suggerita da van va bene e non ha il sovraccarico di mantenere una tabella separata.

Se, come nel mio caso, un tempo di selezione breve è fondamentale, allora consiglierei il metodo a due tabelle.

PS Questo è il mio primo post StackOverflow e mi ci sono voluti anni, quindi spero che qualcuno lo troverà utile!

Questo funziona in MSSQL e sono sicuro che dovrebbe essere ansible cambiare un paio di parole chiave per farlo funzionare anche in MySQL (forse anche più bello):

 SELECT TOP 1 t.* FROM @Table t INNER JOIN (SELECT t.id, sum(tt.weight) AS cum_weight FROM @Table t INNER JOIN @Table tt ON tt.id <= t.id GROUP BY t.id) tc ON tc.id = t.id, (SELECT SUM(weight) AS total_weight FROM @Table) tt, (SELECT RAND() AS rnd) r WHERE r.rnd * tt.total_weight <= tc.cum_weight ORDER BY t.id ASC 

L'idea è di avere un peso cumulativo per ogni riga (subselect-1), quindi trovare la posizione del RAND spanning () in questo intervallo cumulativo.

Un approccio semplice (evitando join o subquery) consiste nel moltiplicare il peso di un numero casuale compreso tra 0 e 1 per produrre un peso temporaneo da ordinare per:

 SELECT t.*, RAND() * t.weight AS w FROM table t ORDER BY w DESC LIMIT 1 

Per capire questo, considera che RAND() * 2x sarà un valore maggiore di RAND() * x circa due terzi delle volte. Di conseguenza, nel corso del tempo ogni riga dovrebbe essere selezionata con una frequenza proporzionale al suo peso relativo (ad esempio una riga con il peso 100 sarà selezionata circa 100 volte più spesso di una riga con il peso 1, ecc.).

Aggiornamento: questo metodo non produce infatti le distribuzioni corrette , quindi per ora non utilizzarlo! (vedi i commenti sotto). Penso che ci dovrebbe essere ancora un metodo semplice simile a quello sopra che funzionerà, ma per ora il metodo più complesso di seguito, che coinvolge i join, potrebbe essere migliore. Lascio questa risposta perché: (a) c’è una discussione pertinente nei commenti qui sotto, e (b) se / quando avrò una possibilità, cercherò di risolverlo.

Questo sembra funzionare, ma non sono sicuro della matematica che c’è dietro.

 SELECT RAND() / t.weight AS w, t.* FROM table t WHERE t.weight > 0 ORDER BY 1 LIMIT 1 

La mia ipotesi sul perché funzioni è che l’ordine ascendente cerca i risultati più piccoli e dividendo per il peso per i pesi più alti il ​​risultato casuale è raggruppato più strettamente vicino allo zero.

L’ho testato (in realtà lo stesso algoritmo in postgresql) con 209000 query su 3000 righe e la rappresentazione del peso è risultata corretta.

i miei dati di input:

 select count(*),weight from t group by weight count | weight -------+-------- 1000 | 99 1000 | 10 1000 | 100 (3 rows) 

i miei risultati:

 jasen=# with g as ( select generate_series(1,209000) as i ) ,r as (select ( select t.weight as w FROM t WHERE t.weight > 0 ORDER BY ( random() / t.weight ) + (gi*0) LIMIT 1 ) from g) select rw, count(*), rw*1000 as expect from r group by rw; w | count | expect -----+-------+-------- 99 | 98978 | 99000 10 | 10070 | 10000 100 | 99952 | 100000 (3 rows) 

Il +(gi*0) non ha alcun effetto sul risultato aritmetico ma è richiesto un riferimento esterno per forzare il pianificatore a rivalutare la sotto-selezione per ciascuna delle righe di input 209K prodotte in g

Forse questo:

 SELECT * FROM  T JOIN (SELECT FLOOR(MAX(ID)*RAND()) AS ID FROM 
) AS x ON T.ID >= x.ID LIMIT 1;

O questo:

 SELECT * FROM tablename WHERE somefield='something' ORDER BY RAND() LIMIT 1 

Non ricordo come RND () in mysql, ma qui esempio di lavoro per MSSQL:

 SELECT TOP(1) (weight +RAND ()) r, id, content, weight FROM Table ORDER BY 1 DESC 

Se TOP (1) non è applicabile, è sufficiente recuperare il primo record dal set di risultati totale.