MySQL: Select Random Entry, but Weight Towards Cer

Question

I've got a MySQL table with a bunch of entries in it, and a column called "Multiplier." The default (and most common) value for this column is 0, but it could be any number.

What I need to do is select a single entry from that table at random. However, the rows are weighted according to the number in the "Multiplier" column. A value of 0 means that it's not weighted at all. A value of 1 means that it's weighted twice as much, as if the entry were in the table twice. A value of 2 means that it's weighted three times as much, as if the entry were in the table three times.

I'm trying to modify what my developers have already given me, so sorry if the setup doesn't make a whole lot of sense. I could probably change it but want to keep as much of the existing table setup as possible.

I've been trying to figure out how to do this with SELECT and RAND(), but don't know how to do the weighting. Is it possible?

Answer 1

SELECT * FROM tablename ORDER BY -LOG(RAND()) / Multiplier;

Is the one which gives you the correct distribution.

SELECT * FROM tablename ORDER BY (RAND() * Multiplier);

Gives you the wrong distribution.

For example, there are two entries A and B in the table. A is with weight 100 while B is with weight 200. For the first one (exponential random variable), it gives you Pr(A winning) = 1/3 while the second one gives you 1/4, which is not correct. I wish I can show you the math. However I do not have enough rep to post relevant link.

Answer 2

While I realise this is an question on MySQL, the following may be useful for someone using SQLite3 which has subtly different implementations of RANDOM and LOG.

SELECT * FROM table ORDER BY (-LOG(abs(RANDOM() % 10000))/weight) LIMIT 1;

weight is a column in table containing integers (I've used 1-100 as the range in my table).

RANDOM() in SQLite produces numbers between -9.2E18 and +9.2E18 (see SQLite docs for more info). I used the modulo operator to get the range of numbers down a bit.

abs() will remove the negatives to avoid problems with LOG which only handles non-zero positive numbers.

LOG() is not actually present in a default install of SQLite3. I used the php SQLite3 CreateFunction call to use the php function in SQL. See the PHP docs for info on this.

Answer 3

Well, I would put the logic of weights in PHP:

<?php
    $weight_array = array(0, 1, 1, 2, 2, 2);
    $multiplier = $weight_array[array_rand($weight_array)];
?>

and the query:

SELECT *
FROM `table`
WHERE Multiplier = $multiplier
ORDER BY RAND()
LIMIT 1

I think it will work :)

Answer 4

Whatever you do, it is giong to be terrible because it will involve: * Getting the total "weights" for all columns as ONE number (including applying the multiplier). * Getting a random number between 0 and that total. * Getting all entries and runing them along, deducting the weight from the random number and choosing the one entry when you run out of items.

In average you will run along half the table. Performance - unless the table is small, then do it outside mySQL in memory - will be SLOW.