Wählen Sie eine zufällige Zeile, aber mit Quoten

Question

Ich habe einen Datensatz mit Zeilen, die jeweils eine "Quoten"-Zahl zwischen 1 und 100 enthalten. Ich möchte dies auf möglichst effiziente Weise tun. Die Quoten addieren sich nicht unbedingt zu 100.

Ich habe ein paar Ideen gehabt.

a) Wählen Sie den gesamten Datensatz aus, addieren Sie dann alle Quoten und erzeugen Sie eine Zufallszahl zwischen 1 und dieser Zahl. Ziehen Sie dann in einer Schleife die Quoten von der Zahl ab, bis sie 0 ist.

Ich wollte die Auswirkungen auf die Datenbank so gering wie möglich halten und habe daher überlegt, ob ich nur die Zeilen auswählen sollte, die ich benötige.

b)

SELECT * FROM table WHERE (100*RAND()) < odds

Ich habe überlegt LIMIT 0,1

Aber wenn die Elemente die gleiche Wahrscheinlichkeit haben, wird nur eines von ihnen zurückgegeben

Alternativ kann man den gesamten Datensatz nehmen und einen Zufallswert daraus auswählen... aber dann werden die Quoten beeinflusst, da es ein Zufallswert mit Quoten und dann ein Zufallswert ohne Quoten wird, so dass die Quoten zugunsten der höheren Quoten geneigt werden (sogar noch mehr).

Ich denke, ich könnte order by odds ASC nimmt dann den gesamten Datensatz und wählt dann mit PHP eine zufällige Zeile mit der gleichen Quote wie der erste Datensatz (die niedrigste) aus.

Das scheint mir eine ungeschickte Lösung zu sein.

Hat jemand eine bessere Lösung? Wenn nicht, welche der oben genannten Lösungen ist die beste?

Answer 1

Fügen Sie Ihrer Tabelle einige Spalten hinzu, die die Auswahl erleichtern. Nehmen wir zum Beispiel an, Sie haben diese Zeilen

 X  2  
 Y  3
 Z  1

Wir fügen einige kumulative Werte hinzu

 Key Odds Start  End 
 X    2     0     1      // range 0->1, 2 values == odds
 Y    3     2     4      // range 2->4, 3 values == odds
 Z    1     5     5      // range 5->5, 1 value == odds

Start und Ende werden wie folgt gewählt. Die erste Zeile hat einen Startwert von Null. Nachfolgende Zeilen haben einen Anfang, der um eins größer ist als das vorherige Ende. Das Ende ist (Start + Quoten - 1).

Wählen Sie nun eine Zufallszahl R im Bereich 0 bis Max(End)

Select * from T where R >= T.Start and R <= T.End

Wenn die Datenbank hinreichend intelligent ist, können wir vielleicht in der Lage sein

 Select * from T where R >= T.Start and R <= (T.Start + T.Odds - 1)

Ich spekuliere, dass eine Endspalte mit einem Index die bessere Leistung bringen kann. Auch die Max(End) vielleicht irgendwo gespeichert und durch einen Trigger aktualisiert, wenn ncessary.

Die Aktualisierung von Start/Ende ist natürlich nicht ganz unproblematisch. Dies ist vielleicht nicht so schlimm, wenn entweder

• Der Tabelleninhalt ist stabil
• oder Einfügungen sind in irgendeiner Weise natürlich geordnet, so dass jede neue Zeile einfach an die alte höchste anschließt.

Answer 2

Ich habe es nicht ausprobiert, aber vielleicht so etwas wie dieses (mit ? eine Zufallszahl von 0 bis SUM(odds) - 1 )?

SET @prob := 0;

SELECT
  T.*,
  (@prob := @prob + T.odds) AS prob
FROM table T
WHERE prob > ?
LIMIT 1

Dies ist im Grunde das Gleiche wie Ihre Idee a), aber vollständig in einem (naja, technisch gesehen zwei, wenn man den Variablenaufbau mitzählt) SQL-Befehl.

Answer 3

Wenn Sie einen Index für die Quotenspalte und einen Primärschlüssel haben, wäre dies sehr effizient:

SELECT id, odds FROM table WHERE odds > 0

Die Datenbank müsste nicht einmal aus der Tabelle lesen, sie würde alles, was sie braucht, aus dem Quotenindex erhalten.

Dann wählen Sie einen Zufallswert zwischen 1 und der Anzahl der zurückgegebenen Zeilen.

Wählen Sie dann diese Zeile aus dem Array der zurückgegebenen Zeilen aus.

Wählen Sie schließlich die gesamte Zielzeile aus:

SELECT * FROM table WHERE id = ?

Dadurch wird eine gleichmäßige Verteilung zwischen allen Zeilen mit einem Quotenwert gewährleistet.

---

Alternativ können Sie die Quoten auch in eine andere Tabelle mit einem Autoinkrement-Primärschlüssel aufnehmen.

Odds
ID     odds
1      4
2      9
3      56
4      12

Speichern Sie den ID-Fremdschlüssel in der Haupttabelle anstelle des Quotenwerts, und indizieren Sie ihn.

Ermitteln Sie zunächst den Maximalwert. Dabei wird die Datenbank nicht berührt. Es wird der Index verwendet:

SELECT MAX(ID) FROM Odds

Ermittelt einen Zufallswert zwischen 1 und dem Höchstwert.

Wählen Sie dann den Datensatz aus.

SELECT * FROM table
JOIN Odds ON Odds.ID = table.ID
WHERE Odds.ID >= ?
LIMIT 1

Dies erfordert eine gewisse Wartung, wenn Sie dazu neigen, Odds-Werte zu löschen oder Einsätze zurückzunehmen, um die Verteilung gleichmäßig zu halten.

In dem Buch gibt es ein ganzes Kapitel über die Zufallsauswahl SQL-Antipatterns .

Answer 4

Was wäre, wenn Sie Ihren Code nehmen und eine ORDER BY RAND() y LIMIT 1 ?

SELECT * FROM table WHERE (100*RAND()) < odds ORDER BY RAND() LIMIT 1

Auf diese Weise wird auch bei mehreren gleichen Wahrscheinlichkeiten immer eine zufällige Reihenfolge angezeigt, und Sie nehmen nur den ersten Eintrag.

Answer 5

select * from table 
where id between 1 and 100 and ((id % 2) <> 0) 
order by NewId()