MySQL: Select Random Entry, but Weight Towards Certain Entries

Question

I'm sick of waiting for my developers to fix this, so I decided to ask you guys. I'm trying to modify what they've 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 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'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?

I would appreciate any help.

Answer 1

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.

Answer 2

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 3

Don't use 0, 1 and 2 but 1, 2 and 3. Then you can use this value as a multiplier:

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

Answer 4

The result of the pseudo-code (rand(1, num) % rand(1, num)) will get more toward 0 and less toward num. Subtract the result from num to get the opposite.

So if my application language is PHP, it should look something like this:

$arr = mysql_fetch_array(mysql_query(
    'SELECT MAX(`Multiplier`) AS `max_mul` FROM tbl'
));
$MaxMul = $arr['max_mul']; // Holds the maximum value of the Multiplier column

$mul = $MaxMul - ( rand(1, $MaxMul) % rand(1, $MaxMul) );

mysql_query("SELECT * FROM tbl WHERE Multiplier=$mul ORDER BY RAND() LIMIT 1");

Explanation of the code above:

1. Fetch the highest value in the Multiplier column
2. calculate a random Multiplier value (weighted toward the maximum value in the Multiplier column)
3. Fetch a random row which has that Multiplier value

It's also achievable merely by using MySQL.

Proving that the pseudo-code (rand(1, num) % rand(1, num)) will weight toward 0: Execute the following PHP code to see why (in this example, 16 is the highest number):

$v = array();

for($i=1; $i<=16; ++$i)
    for($k=1; $k<=16; ++$k)
        isset($v[$i % $k]) ? ++$v[$i % $k] : ($v[$i % $k] = 1);

foreach($v as $num => $times)
        echo '<div style="margin-left:', $times  ,'px">
              times: ',$times,' @ num = ', $num ,'</div>';