21

示例输入：

从测试中选择*；
 编号 | 百分   
----+------------
  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}。

有任何想法吗？

4

6 回答 6

24

这应该可以解决问题：

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 小提琴]

于 2012-10-23T23:11:48.667 回答
9

ORDER BY random() ^ (1.0 / p)

来自 Efraimidis 和 Spirakis 描述的算法。

于 2017-10-10T11:02:21.267 回答
4

Branko 接受的解决方案很棒（谢谢！）。但是，我想提供一个性能相同的替代方案（根据我的测试），并且可能更易于可视化。

让我们回顾一下。最初的问题也许可以概括如下：

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

注意强调相对权重，而不是百分比。正如布兰科在他的回答中指出的那样，使用相对权重适用于任何事情，包括百分比。

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

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 的概率，这无非是一个简单的归一化（权重 / 总和（权重））：

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

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

表现

上面的查询非常高效。即使在我的普通机器上，PostgreSQL 在 WSL1 实例中运行（太可怕了！），执行速度也相对较快：

     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

窗口功能框架

值得注意的是，上面的技术是使用带有非标准 frame 的窗口函数ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW。这是处理某些权重可能重复的事实所必需的，这就是为什么我首先选择具有重复权重的测试数据！

于 2020-05-23T08:39:09.203 回答
2

您提出的查询似乎有效；请参阅此 SQLFiddle 演示。但是，它会产生错误的分布；见下文。

为了防止 PostgreSQL 优化子查询，我将它包装在一个VOLATILESQL 函数中。PostgreSQL 无法知道您是否打算为外部查询的每一行运行一次子查询，因此如果您不强制它变为 volatile，它只会执行一次。另一种可能性 - 尽管查询计划器将来可能会优化 - 是让它看起来是一个相关的子查询，就像这个使用永远为真 where 子句的黑客一样，像这样：http ://sqlfiddle.com/# !12/3039b/9

猜测一下（在您更新以解释它为什么不起作用之前）您的测试方法有问题，或者您将其用作外部查询中的子查询，而 PostgreSQL 注意到它不是相关的子查询并执行它一次，就像在这个例子中一样。.

更新：产生的分布不是你所期望的。这里的问题是您通过获取多个样本来扭曲分布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, percent, previous_percent) 然后使用它创建两个运行的权重总和，用作范围括号；然后
  • 取一个随机值，将其缩放到权重范围，然后选择一个权重在目标括号内的值
于 2012-10-23T22:44:09.187 回答
1

这里有一些东西供你玩：

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 子句。

请注意，只有当您以正确的方式订购餐桌时，它才会起作用。

于 2012-10-23T22:52:09.503 回答
1

根据 Branko Dimitrijevic 的回答，我编写了这个查询，通过使用分层窗口函数的总和percent（与 a 不同ROLLUP），它可能会更快，也可能不会更快。

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,则可能更可取，因为它避免了必须先对数据进行排序。

我还尝试了 Mechanic Wei 的回答（显然如本文所述），这在性能方面似乎很有希望，但经过一些测试，分布似乎已关闭：

SELECT id
FROM test
ORDER BY random() ^ (1.0/percent)
LIMIT 1
于 2018-08-31T02:40:19.147 回答