PostgreSQL中基于权重抽取N个不同抽奖获奖者的实现问题

问题分析 #

你需要从raffle_tickets表中按用户总购票数的权重，抽取N个不重复的用户作为获奖者，插入raffle_winners表。原方案存在两个核心问题：

• 单个random()值只能匹配一个用户区间，LIMIT N无法实现多用户抽取
• 基于cross join generate_series的方案是有放回抽样，会产生重复用户，违反raffle_winners的唯一约束

最优解决方案（高效加权无放回抽样） #

使用指数分布加权排序的方式实现无放回抽样，既保证权重占比，又不会重复抽取用户，适合大数据集场景。

完整SQL代码：

WITH users_and_weights AS (
    -- 计算指定抽奖下每个用户的总购票数（权重）
    SELECT 
        user_id,
        SUM(num_tickets) AS weight
    FROM 
        raffle_tickets
    WHERE
        raffle_id = $1
    GROUP BY
        user_id
),
user_probabilities AS (
    -- 计算每个用户的中奖概率（权重/总票数）
    SELECT
        user_id,
        weight,
        weight::FLOAT / SUM(weight) OVER () AS probability
    FROM users_and_weights
),
selected_winners AS (
    -- 基于指数分布加权排序，抽取前N个用户（N为该抽奖的最大获奖人数）
    SELECT
        user_id,
        probability
    FROM user_probabilities
    ORDER BY -ln(random()) / weight
    LIMIT (SELECT num_max_winners FROM raffles WHERE id = $1)
)
-- 插入获奖者数据，处理并发重复插入问题
INSERT INTO raffle_winners (user_id, raffle_id, probability)
SELECT user_id, $1, probability
FROM selected_winners
ON CONFLICT (raffle_id, user_id) DO NOTHING;

代码说明

1. users_and_weights：按用户分组，统计每个用户在指定抽奖中的总购票数作为权重，GROUP BY确保每个用户唯一。
2. user_probabilities：计算每个用户的中奖概率，即用户总票数占该抽奖总票数的比例。
3. selected_winners：利用-ln(random()) / weight排序，权重越高的用户，该值越大，排序后取前N个即可实现加权无放回抽样。
4. INSERT语句：将结果插入获奖者表，ON CONFLICT子句避免并发场景下因重复抽取导致的插入失败。

备选方案（精确累积概率无放回抽样） #

如果需要严格遵循累积概率的无放回抽取逻辑（适合小数据集），可以使用递归CTE实现每次抽取后重新计算剩余用户的概率：

WITH RECURSIVE weighted_draw AS (
    -- 初始步骤：计算所有用户的权重和总权重
    SELECT
        user_id,
        SUM(num_tickets) AS weight,
        SUM(num_tickets) OVER () AS total_weight,
        1 AS draw_round
    FROM raffle_tickets
    WHERE raffle_id = $1
    GROUP BY user_id

    UNION ALL

    -- 递归步骤：排除已抽中用户，重新计算剩余用户的权重和总权重
    SELECT
        uw.user_id,
        uw.weight,
        SUM(uw.weight) OVER () AS total_weight,
        wd.draw_round + 1 AS draw_round
    FROM weighted_draw wd
    JOIN (
        SELECT user_id, SUM(num_tickets) AS weight
        FROM raffle_tickets
        WHERE raffle_id = $1
        GROUP BY user_id
    ) uw ON uw.user_id NOT IN (SELECT user_id FROM weighted_draw WHERE draw_round = wd.draw_round)
    WHERE wd.draw_round < (SELECT num_max_winners FROM raffles WHERE id = $1)
),
draw_results AS (
    -- 生成随机数并计算累积概率区间
    SELECT
        user_id,
        weight::FLOAT / total_weight AS probability,
        draw_round,
        random() AS rnd,
        SUM(weight::FLOAT / total_weight) OVER (PARTITION BY draw_round ORDER BY user_id) AS cum_prob,
        SUM(weight::FLOAT / total_weight) OVER (PARTITION BY draw_round ORDER BY user_id) - (weight::FLOAT / total_weight) AS prev_cum_prob
    FROM weighted_draw
),
selected_winners AS (
    -- 匹配随机数对应的用户，确保每个用户只被选中一次
    SELECT DISTINCT ON (user_id)
        user_id,
        probability
    FROM draw_results
    WHERE rnd BETWEEN prev_cum_prob AND cum_prob
    ORDER BY user_id, draw_round
)
INSERT INTO raffle_winners (user_id, raffle_id, probability)
SELECT user_id, $1, probability
FROM selected_winners
ON CONFLICT (raffle_id, user_id) DO NOTHING;

代码说明

递归CTE会逐轮抽取用户，每轮排除已抽中的用户并重新计算剩余用户的概率，确保每一次抽取都基于当前剩余用户的权重占比，适合对抽样逻辑要求严格的小数据集场景。

内容的提问来源于stack exchange，提问作者Pirulax