关于SQL Server：T-SQL中的随机加权选择

Random Weighted Choice in T-SQL

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

例如，我在表中有一组行，权重分别为50、25和25(总计为100，但不需要)，我想随机选择其中的一行，其统计结果等于各自重量。

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

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

这仅在表中运行一次，但是即使选择的值是第一条记录，也必须在整个表中运行。因为平均位置在表格的一半位置(如果按权重递增排序则更少)，编写循环可能会更快...(特别是如果权重在同一组中)：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

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

您只需要对所有候选行的权重求和，然后在该总和中选择一个随机点，然后选择与该选定点进行协调的记录(每个记录将逐渐累积一个累加的权重之和)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

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

如果您有很多记录，"逐渐增加一个累加的总和"部分会很昂贵。如果您还已经拥有广泛的得分/权重范围(即：范围足够大，大多数记录的权重都是唯一的。1-5星可能不会削减)，则可以执行类似的操作来选择权重值。我在这里使用VB.Net进行演示，但这也可以在纯Sql中轻松完成：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

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

运行此命令，然后选择得分最高且小于返回重量的记录。如果多于一个记录共享该分数，则随机选择它。这样做的好处是您不必保持任何和，并且可以调整用于满足自己口味的概率方程。但同样，它在分数分布较大时效果最佳。

使用随机数生成器执行此操作的方法是集成概率密度函数。使用一组离散值，您可以计算前缀总和(直到该总和的所有值的总和)并将其存储。这样，您可以选择大于随机数的最小前缀总和(迄今为止的值)值。

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

如果您需要获取一组样本(例如，您要从5M行的集合中采样50行)，其中每一行都有一个名为Weight的列，该列为int，并且值越大表示权重越大，您可以使用此功能：

1
2
3
4
5
6
7
8

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	1.0 * ABS(CAST(CHECKSUM(NEWID()) AS bigint)) / CAST(0x7FFFFFFF AS INT)

由于此问题，您将校验和转换为BIGINT而不是int：

Because checksum returns an int, and the range of an int is -2^31
(-2,147,483,648) to 2^31-1 (2,147,483,647), the abs() function can
return an overflow error if the result happens to be exactly
-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,
so it was happening about once a week! Fix is to cast the checksum to
bigint before the abs.