T-SQLのランダム加重選択

Question

すべての候補行の適用ウェイトに基づいて、T-SQLのテーブル行をランダムに選択しますか？

たとえば、テーブルに50,25、および25の重みを付けた行を設定しています（これは100になりますが、必ずしも必要ではありません）。統計結果を使用してランダムに1つを選択しますそれぞれの重量に等しい。

Answer 1

デーンの答えには、正方形の法則を導入する方法で自己結合が含まれています。 (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 

これは同時に@weightポイントをデクリメントしながら、各レコードのid値に@idを設定し、テーブルを通過します。結局、@weight_pointは負になります。これは、すべての先行重みのSUMがランダムに選択された目標値よりも大きいことを意味します。これは私たちが望むレコードなので、その点からは@idをそれ自身に設定しました（テーブル内のどのIDも無視します）。

これはテーブルを1回だけ実行しますが、選択した値が最初のレコードであってもテーブル全体を実行する必要があります。平均位置はテーブルの途中であり（昇順の場合は少ない）、ループを書く方が速くなる可能性があります（特に重み付けが共通のグループの場合）：

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

「インクリメンタルに運ぶaccumlating [原文]重量合計」は、レコードをたくさん持っている場合一部が高価です。あなたがすでに広い範囲のスコア/ウェイトを持っている場合（つまり、範囲が広くてほとんどのレコードウェイトが一意です.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

乱数生成器でこれを行う方法は、確率密度関数を統合することです。離散値のセットを使用すると、接頭辞の合計（これまでのすべての値の合計）を計算して保存することができます。これで、乱数より大きいminum prefix接頭辞（date to aggregate）値を選択します。

データベースでは、挿入後の後続の値を更新する必要があります。更新の相対頻度とデータセットのサイズがこの処理を実行するコストを高くしない場合は、単一のs-argable（索引参照で解決できる述語）問合せから適切な値を取得できることを意味します。