<p>How do you randomly select a table row in T-SQL based on an applied weight for all candidate rows?</p>

<p>For example, I have a set of rows in a table weighted at 50, 25, and 25 (which adds up to 100 but does not need to), and I want to select one of them randomly with a statistical outcome equivalent to the respective weight.</p>

[{'answer_id': 58459, 'author': 'Dane', 'author_id': 2929, 'author_profile': 'https://Stackoverflow.com/users/2929', 'pm_score': 3, 'selected': False, 'text': '<p>You simply need to sum the weights of all candidate rows, then choose a random point within that sum, then select the record that coordinates with that chosen point (each record is incrementally carrying an accumulating weight sum with it).</p>\n\n<pre><code>DECLARE @id int, @weight_sum int, @weight_point int\nDECLARE @table TABLE (id int, weight int)\n\nINSERT INTO @table(id, weight) VALUES(1, 50)\nINSERT INTO @table(id, weight) VALUES(2, 25)\nINSERT INTO @table(id, weight) VALUES(3, 25)\n\nSELECT @weight_sum = SUM(weight)\nFROM @table\n\nSELECT @weight_point = ROUND(((@weight_sum - 1) * RAND() + 1), 0)\n\nSELECT TOP 1 @id = t1.id\nFROM @table t1, @table t2\nWHERE t1.id &gt;= t2.id\nGROUP BY t1.id\nHAVING SUM(t2.weight) &gt;= @weight_point\nORDER BY t1.id\n\nSELECT @id\n</code></pre>\n'}, {'answer_id': 58995, 'author': 'Joel Coehoorn', 'author_id': 3043, 'author_profile': 'https://Stackoverflow.com/users/3043', 'pm_score': 2, 'selected': False, 'text': '<p>The <em>"incrementally carrying a an accumlating[sic] weight sum"</em> part is expensive if you have a lot of records.  If you also already have a wide range of scores/weights (ie: the range is wide enough that most records weights are unique.  1-5 stars probably wouldn\'t cut it), you can do something like this to pick a weight value. I\'m using VB.Net here to demonstrate, but this could easily be done in pure Sql as well:</p>\n\n<pre class="lang-vb prettyprint-override"><code>Function PickScore()\n    \'Assume we have a database wrapper class instance called SQL and seeded a PRNG already\n    \'Get count of scores in database\n    Dim ScoreCount As Double = SQL.ExecuteScalar("SELECT COUNT(score) FROM [MyTable]")\n    \' You could also approximate this with just the number of records in the table, which might be faster.\n\n    \'Random number between 0 and 1 with ScoreCount possible values\n    Dim rand As Double = Random.GetNext(ScoreCount) / ScoreCount\n\n    \'Use the equation y = 1 - x^3 to skew results in favor of higher scores\n    \' For x between 0 and 1, y is also between 0 and 1 with a strong bias towards 1\n    rand = 1 - (rand * rand * rand)\n\n    \'Now we need to map the (0,1] vector to [1,Maxscore].\n    \'Just find MaxScore and mutliply by rand\n    Dim MaxScore As UInteger = SQL.ExecuteScalar("SELECT MAX(Score) FROM Songs")\n    Return MaxScore * rand\nEnd Function\n</code></pre>\n\n<p>Run this, and pick the record with the largest score less than the returned weight.  If more than one record share that score, pick it at random.  The advantages here are that you don\'t have to maintain any sums, and you can tweak the probability equation used to suit your tastes.  But again, it works best with a larger distribution of scores.</p>\n'}, {'answer_id': 93328, 'author': 'ConcernedOfTunbridgeWells', 'author_id': 15401, 'author_profile': 'https://Stackoverflow.com/users/15401', 'pm_score': 2, 'selected': False, 'text': "<p>The way to do this with random number generators is to integrate the probabiliity density function.  With a set of discrete values you can calculate the prefix sum (sum of all values up to this one) and store it.  With this you select the minumum prefix sum (aggregate to date) value greater than the random number.  </p>\n\n<p>On a database the subsequent values after an insertion have to be updated.  If the relative frequency of updates and size of the data set doesn't make the cost of doing this prohibitive it means that the appropriate value can be obtained in from a single s-argable (predicate that can be resolved by an index lookup) query.</p>\n"}, {'answer_id': 454454, 'author': 'MatBailie', 'author_id': 53341, 'author_profile': 'https://Stackoverflow.com/users/53341', 'pm_score': 5, 'selected': True, 'text': "<p>Dane's answer includes a self joins in a way that introduces a square law. <code>(n*n/2)</code> rows after the join where there are n rows in the table.</p>\n<p>What would be more ideal is to be able to just parse the table once.</p>\n<pre><code>DECLARE @id int, @weight_sum int, @weight_point int\nDECLARE @table TABLE (id int, weight int)\n\nINSERT INTO @table(id, weight) VALUES(1, 50)\nINSERT INTO @table(id, weight) VALUES(2, 25)\nINSERT INTO @table(id, weight) VALUES(3, 25)\n\nSELECT @weight_sum = SUM(weight)\nFROM @table\n\nSELECT @weight_point = FLOOR(((@weight_sum - 1) * RAND() + 1))\n\nSELECT\n    @id = CASE WHEN @weight_point &lt; 0 THEN @id ELSE [table].id END,\n    @weight_point = @weight_point - [table].weight\nFROM\n    @table [table]\nORDER BY\n    [table].Weight DESC\n</code></pre>\n<p>This will go through the table, setting <code>@id</code> to each record's <code>id</code> value while at the same time decrementing <code>@weight</code> point.  Eventually, the <code>@weight_point</code> will go negative.  This means that the <code>SUM</code> of all preceding weights is greater than the randomly chosen target value. This is the record we want, so from that point onwards we set <code>@id</code> to itself (ignoring any IDs in the table).</p>\n<p>This runs through the table just once, but does have to run through the entire table even if the chosen value is the first record.  Because the average position is half way through the table (and less if ordered by ascending weight) writing a loop could possibly be faster...  (Especially if the weightings are in common groups):</p>\n<pre><code>DECLARE @id int, @weight_sum int, @weight_point int, @next_weight int, @row_count int\nDECLARE @table TABLE (id int, weight int)\n\nINSERT INTO @table(id, weight) VALUES(1, 50)\nINSERT INTO @table(id, weight) VALUES(2, 25)\nINSERT INTO @table(id, weight) VALUES(3, 25)\n\nSELECT @weight_sum = SUM(weight)\nFROM @table\n\nSELECT @weight_point = ROUND(((@weight_sum - 1) * RAND() + 1), 0)\n\nSELECT @next_weight = MAX(weight) FROM @table\nSELECT @row_count   = COUNT(*)    FROM @table WHERE weight = @next_weight\nSET @weight_point = @weight_point - (@next_weight * @row_count)\n\nWHILE (@weight_point &gt; 0)\nBEGIN\n    SELECT @next_weight = MAX(weight) FROM @table WHERE weight &lt; @next_weight\n    SELECT @row_count   = COUNT(*)    FROM @table WHERE weight = @next_weight\n    SET @weight_point = @weight_point - (@next_weight * @row_count)\nEND\n\n-- # Once the @weight_point is less than 0, we know that the randomly chosen record\n-- # is in the group of records WHERE [table].weight = @next_weight\n\nSELECT @row_count = FLOOR(((@row_count - 1) * RAND() + 1))\n\nSELECT\n    @id = CASE WHEN @row_count &lt; 0 THEN @id ELSE [table].id END,\n    @row_count = @row_count - 1\nFROM\n    @table [table]\nWHERE\n    [table].weight = @next_weight\nORDER BY\n    [table].Weight DESC\n</code></pre>\n"}, {'answer_id': 51090191, 'author': 'Shiroy', 'author_id': 1555435, 'author_profile': 'https://Stackoverflow.com/users/1555435', 'pm_score': 2, 'selected': False, 'text': '<p>If you need to do get a group of samples (say, you want to sample 50 rows from a collection of 5M rows) where each row has a column called <code>Weight</code> which is an <code>int</code> and where larger values means more weight, you can use this function:</p>\n\n<pre><code>SELECT * \nFROM \n(\n    SELECT TOP 50 RowData, Weight \n    FROM MyTable \n    ORDER BY POWER(RAND(CAST(NEWID() AS VARBINARY)), (1.0/Weight)) DESC\n) X \nORDER BY Weight DESC\n</code></pre>\n\n<p>The key here is using the POWER( ) function as illustrated <a href="https://stackoverflow.com/a/18282419/1555435">here</a></p>\n\n<p>A reference on the choice of a random function is <a href="https://learn.microsoft.com/en-us/previous-versions/sql/sql-server-2008-r2/ms189108(v=sql.105)" rel="nofollow noreferrer">here</a> and <a href="https://technet.microsoft.com/en-us/library/aa175776(v=sql.80).aspx" rel="nofollow noreferrer">here</a></p>\n\n<p>Alternatively you can use: </p>\n\n<pre><code>1.0 * ABS(CAST(CHECKSUM(NEWID()) AS bigint)) / CAST(0x7FFFFFFF AS INT) \n</code></pre>\n\n<p>You cast checksum as <code>BIGINT</code> instead of <code>INT</code> because of <a href="https://stackoverflow.com/questions/1045138/how-do-i-generate-random-number-for-each-row-in-a-tsql-select">this</a> issue:</p>\n\n<blockquote>\n  <p>Because checksum returns an int, and the range of an int is -2^31\n  (-2,147,483,648) to 2^31-1 (2,147,483,647), the abs() function can\n  return an overflow error if the result happens to be exactly\n  -2,147,483,648! The chances are obviously very low, about 1 in 4 billion, however we were running it over a ~1.8b row table every day,\n  so it was happening about once a week! Fix is to cast the checksum to\n  bigint before the abs.</p>\n</blockquote>\n'}]
['https://Stackoverflow.com/questions/58457', 'https://Stackoverflow.com', 'https://Stackoverflow.com/users/2929/']