T-SQL 中的随机加权选择

Question

如何根据所有候选行的应用权重在 T-SQL 中随机选择表行？

例如，我在表中有一组行的权重分别为 50、25 和 25（加起来为 100，但不是必须的），我想随机选择其中一个，其统计结果相当于相应的行重量。

Answer 1

Dane 的答案包括以引入平方律的方式进行自连接。 (n*n/2) 表中有 n 行的连接后的行。

更理想的是能够只解析一次表。

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), 0)

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

这将遍历表格，设置 @id 到每条记录的 id 值同时递减 @weight 观点。最终， @weight_point 将会变为负值。这意味着 SUM 所有先前权重的总和大于随机选择的目标值。这是我们想要的记录，所以从那时起我们就设定了 @id 到其自身（忽略表中的任何 ID）。

这仅运行一次表，但即使所选值是第一条记录，也必须运行整个表。因为平均位置是表格的一半（如果按权重升序排序则更少），所以编写循环可能会更快......（特别是如果权重位于公共组中）：

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
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), 0)

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

Answer 2

您只需对所有候选行的权重求和，然后在该和中选择一个随机点，然后选择与该所选点协调的记录（每个记录都递增地携带一个累积的权重和）。

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 = ROUND(((@weight_sum - 1) * RAND() + 1), 0)

SELECT TOP 1 @id = t1.id
FROM @table t1, @table t2
WHERE t1.id >= t2.id
GROUP BY t1.id
HAVING SUM(t2.weight) >= @weight_point
ORDER BY t1.id

SELECT @id

Answer 3

这 “增量地承载一个累积的[原文如此]重量总和” 如果你有很多记录，那么这部分就很昂贵。如果您也已经拥有广泛的分数/权重（即：范围足够宽，大多数记录权重都是唯一的。1-5 颗星可能不会削减它），您可以执行类似的操作来选择权重值。我在这里使用 VB.Net 进行演示，但这也可以在纯 Sql 中轻松完成：

Function PickScore()
    'Assume we have a database wrapper class instance called SQL and seeded a PRNG already
    'Get count of scores in database
    Dim ScoreCount As Double = SQL.ExecuteScalar("SELECT COUNT(score) FROM [MyTable]")
    ' You could also approximate this with just the number of records in the table, which might be faster.

    'Random number between 0 and 1 with ScoreCount possible values
    Dim rand As Double = Random.GetNext(ScoreCount) / ScoreCount

    'Use the equation y = 1 - x^3 to skew results in favor of higher scores
    ' For x between 0 and 1, y is also between 0 and 1 with a strong bias towards 1
    rand = 1 - (rand * rand * rand)

    'Now we need to map the (0,1] vector to [1,Maxscore].
    'Just find MaxScore and mutliply by rand
    Dim MaxScore As UInteger = SQL.ExecuteScalar("SELECT MAX(Score) FROM Songs")
    Return MaxScore * rand
End Function

运行此命令，并选择得分小于返回权重的最大分数的记录。如果有多个记录共享该分数，请随机选择它。这里的优点是您不必维护任何总和，并且可以调整用于满足您的口味的概率方程。但同样，它在分数分布较大的情况下效果最好。

Answer 4

使用随机数生成器实现此目的的方法是对概率密度函数进行积分。使用一组离散值，您可以计算前缀和（直到该值的所有值的总和）并存储它。这样，您可以选择大于随机数的最小前缀总和（截至日期的聚合）值。

在数据库上，插入后的后续值必须更新。如果更新的相对频率和数据集的大小不会导致执行此操作的成本过高，则意味着可以从单个 s-argable（可以通过索引查找解析的谓词）查询中获取适当的值。

Answer 5

如果您需要获取一组样本（例如，您想从 5M 行的集合中采样 50 行），其中每行都有一个名为 Weight 这是一个 int 如果值越大则权重越大，您可以使用此函数：

SELECT * 
FROM 
(
    SELECT TOP 50 RowData, Weight 
    FROM MyTable 
    ORDER BY POWER(RAND(CAST(NEWID() AS VARBINARY)), (1.0/Weight)) DESC
) X 
ORDER BY Weight DESC

这里的关键是使用 POWER( ) 函数，如图所示 这里

关于随机函数选择的参考是 这里 和 这里

或者您可以使用：

1.0 * ABS(CAST(CHECKSUM(NEWID()) AS bigint)) / CAST(0x7FFFFFFF AS INT) 

您将校验和投射为 BIGINT 代替 INT 因为 这 问题：

因为校验和返回INT，并且INT的范围为-2^31（-2,147,483,648）至2^31-1（2,147,483,647），如果结果恰好是-2,147,483,6483,6483,6483,6483,6483,6483,6483,6483,6483,64883,6483,6483,64883,6483,64883,6483,6483,64883,64883,6483,6483,6483,6483,6483,6483,6483,6483,6483,66488，呢这些机会显然很低，大约有40亿分之一，但是我们每天都在一个〜1.8B的行桌子上运行，因此每周发生一次！修复是在ABS之前将校验和施加到Bigint。