从 PostgreSQL 表中按行权重随机选择一行。

Question

示例输入：

SELECT * FROM test;
 id | percent   
----+----------
  1 | 50 
  2 | 35   
  3 | 15   
(3 行记录)

您如何编写这样的查询，以便平均情况下，50% 的时间可以获取 id=1 的行，35% 的时间可以获取 id=2 的行，15% 的时间可以获取 id=3 的行？

我尝试了一些类似这样的语句：SELECT id FROM test ORDER BY p * random() DESC LIMIT 1，但其结果是错误的。在进行 10,000 次运行后，我得到了一个分布结果如下：{1=6293, 2=3302, 3=405}，但我期望的分布结果接近：{1=5000, 2=3500, 3=1500}。

有什么想法吗？

- Oleg Golovanov

---

你所说的“错误结果”是什么意思？ - Clodoaldo Neto

@Clodoaldo，在执行以上查询10k次后，我得到了以下结果（位置对应计数）：{1=6293，2=3302，3=405}，但我希望它们接近这样：{1=5000，2=3500，3=1500}。 - Oleg Golovanov

@OlegGolovanov 好的，查询功能正常，但是分配有问题。 - Craig Ringer

非常有趣的问题。感谢提问。将来值得更具体地说明像为什么某些东西“不起作用”或者产生“错误”的结果，但是除此之外……这是很好的思维食粮，谢谢。 - Craig Ringer

Answer 1

这应该就行了：

WITH CTE AS (
    SELECT random() * (SELECT SUM(percent) FROM YOUR_TABLE) R
)
SELECT *
FROM (
    SELECT id, SUM(percent) OVER (ORDER BY id) S, R
    FROM YOUR_TABLE CROSS JOIN CTE
) Q
WHERE S >= R
ORDER BY id
LIMIT 1;

子查询Q的结果如下：

1  50
2  85
3  100

我们只需在范围 [0, 100) 中生成一个随机数，并选择第一个行号在或超过该数字的行（使用 WHERE 子句）。我们使用公共表达式（WITH）确保随机数仅计算一次。

顺便说一下，SELECT SUM(percent) FROM YOUR_TABLE 允许您在 percent 中设置任何权重 - 它们不一定需要是百分比（即加起来等于100）。 [SQL Fiddle]

- Branko Dimitrijevic

---

这是一个比我写的更好、更快的查询；我们采用了相同的方法来解决问题，但你的解决方案比我使用嵌套窗口计算加权范围要高效得多。 - Craig Ringer

@BrankoDimitrijevic 啊 - 那么根据我最初的说法（删除CTE），我们可以使内部查询列列表为：id，sum(percent) over(order by id) S，random() R。 - John Fawcett

@BrankoDimitrijevic 你说得完全正确。我不知道为什么我没有尝试过 select id, random() from some_random_table，它会为每一行返回一个不同的 random() 值。使用 CTE 吧。谢谢！ - John Fawcett

@Branko 我的意思是 S，而不是百分比，我的错。S 必须是唯一的，并且保证按正确顺序排列（逻辑上，按 S 排序是有意义的）。编辑：除非百分比为零，在这种情况下，两个用户可能匹配（后者为 0%），如果我们按 S 排序，那么一个几乎没有机会的用户可能会获胜。而如果你两次都按 ID 排序，这种情况就不会发生，因为 0 总是会匹配他前面的用户。 - SamGoody

@SamGoody S 是一个运行总计。它遵循在 SUM ... ORDER BY ... 中指定的任何顺序。 - Branko Dimitrijevic

Answer 2

按 random() ^ (1.0 / p) 排序

来自 Efraimidis 和 Spirakis 描述的算法。

- Mechanic Wei

Answer 3

Branko的方案已经很好了（谢谢！）。不过，我想提供一个同样有效且更易于理解的替代方案（根据我的测试结果），也许可以更好地可视化。

让我们回顾一下。原始问题可能可以概括如下：

给定一个id映射和相对权重，创建一个查询，返回一个随机的id，但其概率与其相对权重成比例。

请注意，相对权重的重要性，而不是百分数。正如Branko在他的答案中指出的那样，使用相对权重可以适用于任何东西，包括百分数。

现在，考虑一些测试数据，我们将把它们放在一个临时表中：

CREATE TEMP TABLE test AS
SELECT * FROM (VALUES
    (1, 25),
    (2, 10),
    (3, 10),
    (4, 05)
) AS test(id, weight);

请注意，我使用的示例比原始问题 更加复杂，因为它的总和不方便地加起来等于100，并且相同的权重（20）被使用了多次（对于id 2和3），这很重要，稍后你会看到。

我们需要做的第一件事是将权重转换为0到1之间的概率，这只是一个简单的归一化过程（weight / sum(weights)）。

WITH p AS ( -- probability
    SELECT *,
        weight::NUMERIC / sum(weight) OVER () AS probability
    FROM test
),
cp AS ( -- cumulative probability
    SELECT *,
        sum(p.probability) OVER (
            ORDER BY probability DESC
            ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
        ) AS cumprobability
    FROM p
)
SELECT
    cp.id,
    cp.weight,
    cp.probability,
    cp.cumprobability - cp.probability AS startprobability,
    cp.cumprobability AS endprobability
FROM cp
;

这将导致以下输出：

 id | weight | probability | startprobability | endprobability
----+--------+-------------+------------------+----------------
  1 |     25 |         0.5 |              0.0 |            0.5
  2 |     10 |         0.2 |              0.5 |            0.7
  3 |     10 |         0.2 |              0.7 |            0.9
  4 |      5 |         0.1 |              0.9 |            1.0

上面的查询在我们的需求上做了比严格必要更多的工作，但我发现这样可视化相对概率是有帮助的，并且这使得选择id的最终步骤变得微不足道。

SELECT id FROM (queryabove)
WHERE random() BETWEEN startprobability AND endprobability;

现在，让我们通过测试来将其全部组合起来，以确保查询返回符合预期分布的数据。我们将使用generate_series()函数随机生成一百万个数字：

WITH p AS ( -- probability
    SELECT *,
        weight::NUMERIC / sum(weight) OVER () AS probability
    FROM test
),
cp AS ( -- cumulative probability
    SELECT *,
        sum(p.probability) OVER (
            ORDER BY probability DESC
            ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
        ) AS cumprobability
    FROM p
),
fp AS ( -- final probability
    SELECT
        cp.id,
        cp.weight,
        cp.probability,
        cp.cumprobability - cp.probability AS startprobability,
        cp.cumprobability AS endprobability
    FROM cp
)
SELECT *
FROM fp
CROSS JOIN (SELECT random() FROM generate_series(1, 1000000)) AS random(val)
WHERE random.val BETWEEN fp.startprobability AND fp.endprobability
;

这将产生类似以下输出的结果：

 id | count  
----+--------
 1  | 499679 
 3  | 200652 
 2  | 199334 
 4  | 100335 

如您所见，这完美地跟踪了预期的分布。

性能

上述查询性能相当高。即使在我的平均机器上，使用运行在WSL1实例中的PostgreSQL（可怕！），执行速度也相对较快：

     count | time (ms)
-----------+----------
     1,000 |         7
    10,000 |        25
   100,000 |       210
 1,000,000 |      1950 

生成测试数据的适应性

在为单元/集成测试生成测试数据时，我经常使用上述查询的变体。其想法是生成随机数据，以近似跟踪现实世界中的概率分布。

在这种情况下，我发现计算开始和结束分布并将结果存储在表格中非常有用，只需要 一次 计算：

CREATE TEMP TABLE test AS
WITH test(id, weight) AS (VALUES
    (1, 25),
    (2, 10),
    (3, 10),
    (4, 05)
),
p AS ( -- probability
    SELECT *, (weight::NUMERIC / sum(weight) OVER ()) AS probability
    FROM test
),
cp AS ( -- cumulative probability
    SELECT *,
        sum(p.probability) OVER (
            ORDER BY probability DESC
            ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
        ) cumprobability
    FROM p
)
SELECT
    cp.id,
    cp.weight,
    cp.probability,
    cp.cumprobability - cp.probability AS startprobability,
    cp.cumprobability AS endprobability
FROM cp
;

我可以反复使用这些预先计算的概率，从而提高性能和简化使用。

我甚至可以将所有内容封装在一个函数中，在需要获取随机id的时候随时调用该函数：

CREATE OR REPLACE FUNCTION getrandomid(p_random FLOAT8 = random())
RETURNS INT AS
$$
    SELECT id
    FROM test
    WHERE p_random BETWEEN startprobability AND endprobability
    ;
$$
LANGUAGE SQL STABLE STRICT

窗口函数帧

值得注意的是，上述技术使用了一个带有非标准框架ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW的窗口函数。这是必要的，以处理一些权重可能重复的情况，这也是我选择测试数据中包含重复权重的原因！

- Demian Martinez

---

嘿，这个怎么扩展才能选择N个不同的条目（在这种情况下是从测试表中选择）？ 如果可能的话，我想立即将选择插入另一个表中。 - Pirulax

Answer 4

您提出的查询似乎有效；请参见this SQLFiddle demo。但它创建了错误的分布；请参见下文。

为了防止PostgreSQL优化子查询，我将其包装在一个VOLATILE SQL函数中。 PostgreSQL无法知道您打算让子查询针对外部查询的每一行运行一次，因此如果您不强制将其设置为易失性，则只会执行一次。另一个可能性-虽然是查询规划器未来可能会优化的可能性-是使其看起来像是相关的子查询，就像这个使用始终为真的where子句的hack一样，如此：http://sqlfiddle.com/#!12/3039b/9 猜测（在您更新以解释为什么它不起作用之前），您的测试方法可能有误，或者您正在将其用作外部查询中的子查询，PostgreSQL注意到它不是相关子查询并只执行一次，就像在this example中一样。

更新：生成的分布不符合您的预期。问题在于，通过对random()进行多次采样，您正在使分布偏斜；您需要进行单次采样。

此查询生成正确的分布（SQLFiddle）：

WITH random_weight(rw) AS (SELECT random() * (SELECT sum(percent) FROM test))
 SELECT id
FROM (                   
  SELECT 
    id,
    sum(percent) OVER (ORDER BY id),
    coalesce(sum(prev_percent) OVER (ORDER BY id),0) FROM (
      SELECT 
        id,
        percent,
        lag(percent) OVER () AS prev_percent
      FROM test
    ) x
) weighted_ids(id, weight_upper, weight_lower)
CROSS JOIN random_weight
WHERE rw BETWEEN weight_lower AND weight_upper;

性能可谓是极差。它使用了两个嵌套的窗口集。我所做的是：

• 创建（id，百分比，先前百分比），然后使用它来创建两个权重的运行总和，这些权重用作范围括号；然后
• 取一个随机值，将其缩放到权重范围内，然后选择具有目标括号内权重的值。

- Craig Ringer

---

看起来你证明它没有起作用。3 的出现率为 4%，而实际应为 15%。 - digitaljoel

@digitaljoel 说得好。我假设他们有用的“不起作用”是一个问题，即未关联子查询优化在一组中产生相同的结果，而不是意外的分布。嗯。 试图在大脑中挖掘旧的概率讲座。 - Craig Ringer

@digitaljoel 知道了，问题是随机数的多重采样。 - Craig Ringer

Answer 5

这里有一些东西让你玩耍：

select t1.id as id1
  , case when t2.id is null then 0 else t2.id end as id2
  , t1.percent as percent1
  , case when t2.percent is null then 0 else t2.percent end as percent2 
from "Test1" t1 
  left outer join "Test1" t2 on t1.id = t2.id + 1
where random() * 100 between t1.percent and 
  case when t2.percent is null then 0 else t2.percent end;

基本上执行左外连接，这样您就有两列可以应用between子句。

请注意，只有在正确排序表格的情况下才能正常工作。

- Darren

---

你知道吗，如果你在表中包含一个“牺牲”行（0,0），那么你就可以直接使用内连接，而不必使用烦人的case语句了。这会极大地简化查询。 - Darren

Answer 6

基于Branko Dimitrijevic的回答，我编写了这个查询，使用分层窗口函数（类似于ROLLUP）可能会更快地使用percent的总和。

WITH random AS (SELECT random() AS random)
SELECT id FROM (
    SELECT id, percent,
    SUM(percent) OVER (ORDER BY id) AS rank,
    SUM(percent) OVER () * random AS roll
    FROM test CROSS JOIN random
) t WHERE roll <= rank LIMIT 1

如果顺序不重要，SUM(percent) OVER (ROWS UNBOUNDED PRECEDING) AS rank, 可能更可取，因为它避免了必须先对数据进行排序的步骤。

我也尝试了机械师Wei的答案（如此论文所述），在性能方面似乎非常有前途，但经过一些测试，分布似乎有问题：

SELECT id
FROM test
ORDER BY random() ^ (1.0/percent)
LIMIT 1

- Santo Guevarra

Answer 7

从这篇论文中可以看出，我们需要计算random() ^ (-1.0 / p)（负一）的值。

ORDER BY RANDOM() ^ ( -1.0 / p )

SQLFiddle 的示例将给您：

id  percent  freq
1   40       0.39795 
2   30       0.29540 
3   20       0.20635
4   10       0.10030

完整代码

---

模式

CREATE TABLE test
    (id integer, percent integer)
;
    
INSERT INTO test
    (id, percent)
VALUES
    (1, 40),
    (2, 30),
    (3, 20),
    (4, 10)
;

CREATE OR REPLACE FUNCTION get_random_row() RETURNS integer AS $SQL$
    SELECT id
    FROM test
    ORDER BY RANDOM() ^ ( -1.0 / percent )
    LIMIT 1
$SQL$ LANGUAGE sql VOLATILE;

查询

SELECT id, count(id)/10000.0 AS freq
FROM (
  SELECT get_random_row()
  FROM generate_series(1,10000)
) x(id)
GROUP BY id
ORDER BY 2;

- Stefan Falk

Answer 8

非常老的问题，但我发现这种非常简单的方法，所以对某人可能仍然有帮助。

SELECT id
FROM test
WHERE percent > 0
ORDER BY -log(random()) / percent

log(random()) 创建了一个0-1之间的对数分布。 -log(random()) 确保随机数(random())的较小值（接近0）产生较大的输出值。 通过 percent 进行除法可以根据权重偏置分布。具有较高 percent 的行在排序时通常会出现较低（更负）的值。

此查询的结果分布相当准确 http://sqlfiddle.com/#!17/3cac7/1

id  freq
3   0.147
2   0.3559
1   0.4971

- stepandel