Random Weighted Choice in T-SQL

by

Dane’s answer includes a self joins in a way that introduces a square law. (n*n/2) rows after the join where there are n rows in the table.

What would be more ideal is to be able to just parse the table once.

DECLARE @id int, @weight_sum int, @weight_point int
DECLARE @table TABLE (id int, weight int)

INSERT INTO @table(id, weight) VALUES(1, 50)
INSERT INTO @table(id, weight) VALUES(2, 25)
INSERT INTO @table(id, weight) VALUES(3, 25)

SELECT @weight_sum = SUM(weight)
FROM @table

SELECT @weight_point = FLOOR(((@weight_sum - 1) * RAND() + 1))

SELECT
    @id = CASE WHEN @weight_point < 0 THEN @id ELSE [table].id END,
    @weight_point = @weight_point - [table].weight
FROM
    @table [table]
ORDER BY
    [table].Weight DESC

This will go through the table, setting @id to each record’s id value while at the same time decrementing @weight point. Eventually, the @weight_point will go negative. This means that the SUM 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 @id to itself (ignoring any IDs in the table).

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

DECLARE @id int, @weight_sum int, @weight_point int, @next_weight int, @row_count int
DECLARE @table TABLE (id int, weight int)

INSERT INTO @table(id, weight) VALUES(1, 50)
INSERT INTO @table(id, weight) VALUES(2, 25)
INSERT INTO @table(id, weight) VALUES(3, 25)

SELECT @weight_sum = SUM(weight)
FROM @table

SELECT @weight_point = ROUND(((@weight_sum - 1) * RAND() + 1), 0)

SELECT @next_weight = MAX(weight) FROM @table
SELECT @row_count   = COUNT(*)    FROM @table WHERE weight = @next_weight
SET @weight_point = @weight_point - (@next_weight * @row_count)

WHILE (@weight_point > 0)
BEGIN
    SELECT @next_weight = MAX(weight) FROM @table WHERE weight < @next_weight
    SELECT @row_count   = COUNT(*)    FROM @table WHERE weight = @next_weight
    SET @weight_point = @weight_point - (@next_weight * @row_count)
END

-- # Once the @weight_point is less than 0, we know that the randomly chosen record
-- # is in the group of records WHERE [table].weight = @next_weight

SELECT @row_count = FLOOR(((@row_count - 1) * RAND() + 1))

SELECT
    @id = CASE WHEN @row_count < 0 THEN @id ELSE [table].id END,
    @row_count = @row_count - 1
FROM
    @table [table]
WHERE
    [table].weight = @next_weight
ORDER BY
    [table].Weight DESC

More Related Contents:

  1. Random record from a database table (T-SQL)
  2. SQL Server: Examples of PIVOTing String data
  3. How do I create a unique constraint that also allows nulls?
  4. Using T-SQL, return nth delimited element from a string
  5. How do I get list of all tables in a database using TSQL?
  6. Get first day of week in SQL Server
  7. What is the significance of 1/1/1753 in SQL Server?
  8. Cannot truncate table because it is being referenced by a FOREIGN KEY constraint?
  9. Escape a string in SQL Server so that it is safe to use in LIKE expression
  10. Insert Update trigger how to determine if insert or update
  11. SQL time difference between two dates result in hh:mm:ss
  12. What is the best way to truncate a date in SQL Server?
  13. Dynamic SQL (passing table name as parameter)
  14. SQL Server: Difference between PARTITION BY and GROUP BY
  15. How do you truncate all tables in a database using TSQL?
  16. Understanding SQL Server LOCKS on SELECT queries
  17. SQL Server: How to select all days in a date range even if no data exists for some days
  18. SQL – The conversion of a varchar data type to a datetime data type resulted in an out-of-range value
  19. TSQL: How to convert local time to UTC? (SQL Server 2008)
  20. T-SQL Dynamic SQL and Temp Tables
  21. Find non-ASCII characters in varchar columns using SQL Server
  22. How can I determine in SQL Server if a dateTime range overlaps another
  23. How do you change the datatype of a column in SQL Server?
  24. SQL Server Query – groupwise multiplication
  25. Getting week number off a date in MS SQL Server 2005?
  26. How to reuse calculated columns avoiding duplicating the sql statement
  27. How do I move a table into a schema in T-SQL
  28. How to use RANK() in SQL Server
  29. How to wait for 2 seconds?
  30. What is the meaning of “#” in front of a table name in TSQL?

Leave a Comment