Fast mysql zufällige gewichtete Wahl auf große Datenbank

Question

Ich baue eine Website, wo ich zufällig gewichteten Datensatz aus der Datenbank wählen muss.

Es gibt einen snipped von Code in SQL : select one row randomly, but taking into account a weight

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

Es funktioniert auf kleine Stichprobe von Datensätzen in Ordnung.

Wenn ich fast 1 Million Datensätze anwende, wird es langsam (1,3 - 1,8 Sekunden) auf meinem lokalen Rechner, und ich nehme an, dass ich noch länger auf noch größeren Sets nehmen würde.

Wie könnte es optimiert werden? Gibt es bessere Möglichkeiten, einen gewichteten Datensatz nach dem Zufallsprinzip auszuwählen?

Mein Versuch wäre es, die Gewichte regelmäßig zu berechnen, sie in einer separaten Tabelle zu speichern, die Zufallszahl programmatisch zu wählen und nach dem nächsten Datensatz zu dieser Nummer zu suchen.

Answer 1

Sie können die Daten basierend auf dem Gewicht partitionieren und dann nach dem Zufallsprinzip eine Partition auswählen.

die Partition Bestimmen Sie zu verwenden: O (n)

SELECT Weight, FLOOR(RAND()*COUNT(*)) as Target 
FROM test 
GROUP BY Weight 
ORDER BY RAND()*(Weight)*count(Weight)/100 DESC 
LIMIT 1; 

verwenden, um Gewicht und Ziel aus vorherigen Abfrage zu bekommen Ergebnis: O (log (n))

SELECT test.* 
FROM test 
WHERE Weight = $Weight 
LIMIT $Target, 1 

Test-it:

CREATE TABLE `test` (
    `Id` bigint(20) unsigned NOT NULL AUTO_INCREMENT, 
    `Weight` int(11) NOT NULL, 
    PRIMARY KEY (`Id`), 
    KEY `Weight` (`Weight`) 
) ENGINE=InnoDB DEFAULT CHARSET=utf8 COLLATE=utf8_unicode_ci; 


insert into test (Weight) (select FLOOR(RAND()*1000)); 

Lauf 20 mal 1 Million Testreihen zu erstellen:

insert into test (Weight) select FLOOR(rand()*1000) as Weight from test; 

Die erste Abfrage wird wegen der GROUP BY in O (n) ausgeführt. Wenn Sie eine zweite Tabelle verwalten, die die Anzahl für jedes Gewicht protokolliert, können Sie die Protokollierung (n) der Laufzeit durchführen.

Auf meiner Datenbank mit 8.000.000 Zeilen in der Testtabelle die erste Abfrage läuft in (6.089 s) und den zweiten in (0.001 s)

Answer 2

Zuerst bekommen die Summe aller Gewichte, so dass Sie die Wahrscheinlichkeit für jede Zeile berechnen können so ausgewählt auf die Fliege.

SELECT SUM(weight) FROM t; 

Ich werde die Summe Betrag annimmt, ist über einen MySQL-Variable mit dem Namen @TOTAL_WEIGHT

SELECT t.* 
FROM t 
WHERE RAND() <= (weight/@TOTAL_WEIGHT) 
ORDER BY RAND() 
LIMIT 1; 

Es gibt eine Chance, dass dies durch die gesamte Tabelle geht und immer noch keine Übereinstimmung finden, in In diesem Fall würden Sie wahrscheinlich nur eine weitere Abfrage ausführen, um eine zufällige Zeile zu erhalten.