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

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>';

Answer 2

For a much better performance (specially on big tables), first index the weight column and use this query:

SELECT * FROM tbl WHERE id IN 
    (SELECT id FROM (SELECT id FROM tbl ORDER BY -LOG(1-RAND())/weight LIMIT x) t)

Two subqueries are used because MySQL doesn't support LIMIT in the first subquery yet.

On 40MB table the usual query takes 1s on my i7 machine and this one takes 0.04s.

Answer 3

<?php
/**
 * Demonstration of weighted random selection of MySQL database.
 */
$conn = mysql_connect('localhost', 'root', '');

// prepare table and data.
mysql_select_db('test', $conn);
mysql_query("drop table if exists temp_wrs", $conn);
mysql_query("create table temp_wrs (
    id int not null auto_increment,
    val varchar(16),
    weight tinyint,
    upto smallint,
    primary key (id)
)", $conn);
$base_data = array(    // value-weight pair array.
    'A' => 5,
    'B' => 3,
    'C' => 2,
    'D' => 7,
    'E' => 6,
    'F' => 3,
    'G' => 5,
    'H' => 4
);
foreach($base_data as $val => $weight) {
    mysql_query("insert into temp_wrs (val, weight) values ('".$val."', ".$weight.")", $conn);
}

// calculate the sum of weight.
$rs = mysql_query('select sum(weight) as s from temp_wrs', $conn);
$row = mysql_fetch_assoc($rs);
$sum = $row['s'];
mysql_free_result($rs);

// update range based on their weight.
// each "upto" columns will set by sub-sum of weight.
mysql_query("update temp_wrs a, (
    select id, (select sum(weight) from temp_wrs where id <= i.id) as subsum from temp_wrs i 
) b
set a.upto = b.subsum
where a.id = b.id", $conn);

$result = array();
foreach($base_data as $val => $weight) {
    $result[$val] = 0;
}
// do weighted random select ($sum * $times) times.
$times = 100;
$loop_count = $sum * $times;
for($i = 0; $i < $loop_count; $i++) {
    $rand = rand(0, $sum-1);
    // select the row which $rand pointing.
    $rs = mysql_query('select * from temp_wrs where upto > '.$rand.' order by id limit 1', $conn);
    $row = mysql_fetch_assoc($rs);
    $result[$row['val']] += 1;
    mysql_free_result($rs);
}

// clean up.
mysql_query("drop table if exists temp_wrs");
mysql_close($conn);
?>
<table>
    <thead>
        <th>DATA</th>
        <th>WEIGHT</th>
        <th>ACTUALLY SELECTED<br />BY <?php echo $loop_count; ?> TIMES</th>
    </thead>
    <tbody>
    <?php foreach($base_data as $val => $weight) : ?>
        <tr>
            <th><?php echo $val; ?></th>
            <td><?php echo $weight; ?></td>
            <td><?php echo $result[$val]; ?></td>
        </tr>
    <?php endforeach; ?>
    <tbody>
</table>

if you want to select N rows...

1. re-calculate the sum.
2. reset range ("upto" column).
3. select the row which $rand pointing.

previously selected rows should be excluded on each selection loop. where ... id not in (3, 5);

Answer 4

For others Googling this subject, I believe you can also do something like this:

SELECT strategy_id
FROM weighted_strategies AS t1 
WHERE (
   SELECT SUM(weight) 
   FROM weighted_strategies AS t2 
   WHERE t2.strategy_id<=t1.strategy_id
)>@RAND AND 
weight>0
LIMIT 1

The total sum of weights for all records must be n-1, and @RAND should be a random value between 0 and n-1 inclusive.

@RAND could be set in SQL or inserted as a integer value from the calling code.

The subselect will sum up all the preceeding records' weights, checking it it exceeds the random value supplied.

Answer 5

This guy asks the same question. He says the same as Frank, but the weightings don't come out right and in the comments someone suggests using ORDER BY -LOG(1.0 - RAND()) / Multiplier, which in my testing gave pretty much perfect results.

(If any mathematicians out there want to explain why this is correct, please enlighten me! But it works.)

The disadvantage would be that you couldn't set the weighting to 0 to temporarily disable an option, as you would end up dividing by zero. But you could always filter it out with a WHERE Multiplier > 0.

Answer 6

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);