如何在PostgreSQL中获取随机笛卡尔积？

Question

我有两个表，custassets和tags。为了生成一些测试数据，我想在一个多对多的表中执行INSERT INTO和SELECT，以从每个表中获取随机行（这样来自一个表的随机主键将与第二个表的随机主键配对）。令我惊讶的是，这并不像我最初想的那么容易，所以我要坚持下去以便自我学习。

这是我的第一次尝试。我选择10个custassets和3个tags，但在每种情况下都是相同的。我可以接受第一个表被固定，但我想随机分配标签。

SELECT
    custassets_rand.id custassets_id,
    tags_rand.id tags_rand_id
FROM
    (
        SELECT id FROM custassets WHERE defunct = false ORDER BY RANDOM() LIMIT 10
    ) AS custassets_rand
,
    (
        SELECT id FROM tags WHERE defunct = false ORDER BY RANDOM() LIMIT 3
    ) AS tags_rand

这将产生：

custassets_id | tags_rand_id 
---------------+--------------
          9849 |         3322  }
          9849 |         4871  } this pattern of tag PKs is repeated
          9849 |         5188  }
         12145 |         3322
         12145 |         4871
         12145 |         5188
         17837 |         3322
         17837 |         4871
         17837 |         5188
....

接下来我尝试了以下方法：在SELECT列列表中执行第二个RANDOM()调用。然而，这种方法更糟糕，因为它选择一个单一的标签主键并坚持使用它。

SELECT
    custassets_rand.id custassets_id,
    (SELECT id FROM tags WHERE defunct = false ORDER BY RANDOM() LIMIT 1) tags_rand_id
FROM
    (
        SELECT id FROM custassets WHERE defunct = false ORDER BY RANDOM() LIMIT 30
    ) AS custassets_rand

结果：

 custassets_id | tags_rand_id 
---------------+--------------
         16694 |         1537
         14204 |         1537
         23823 |         1537
         34799 |         1537
         36388 |         1537
....

使用脚本语言很容易实现，我相信可以通过存储过程或临时表轻松完成。但我能否仅使用INSERT INTO SELECT来实现呢？

我曾考虑使用随机函数选择整数主键，但不幸的是，两个表的主键都存在增量序列中的空缺（因此可能会选择每个表中的空行）。否则这样做就没问题了！

- halfer

---

感谢所有评论的人 - 如果我能决定，我会给几个赞！:-) - halfer

Answer 1

请注意，您所寻找的并不是笛卡尔积，它会产生n*m行; 而是一个随机的1:1关联，它会产生GREATEST(n,m)行。

要生成真正随机的组合，只需要对较大的集合随机化rn：

SELECT c_id, t_id
FROM  (
   SELECT id AS c_id, row_number() OVER (ORDER BY random()) AS rn
   FROM   custassets
   ) x
JOIN   (SELECT id AS t_id, row_number() OVER () AS rn FROM tags) y USING (rn);

如果任意的组合已经足够好了，那么这种方法更快（尤其对于大表格）：

SELECT c_id, t_id
FROM   (SELECT id AS c_id, row_number() OVER () AS rn FROM custassets) x
JOIN   (SELECT id AS t_id, row_number() OVER () AS rn FROM tags) y USING (rn);

如果两个表中的行数不匹配，并且您不想失去较大表中的行，请使用取模运算符 % 连接多个次数的来自较小表的行：

SELECT c_id, t_id
FROM  (
   SELECT id AS c_id, row_number() OVER () AS rn
   FROM   custassets -- table with fewer rows
   ) x
JOIN  (
   SELECT id AS t_id, (row_number() OVER () % small.ct) + 1 AS rn
   FROM   tags
       , (SELECT count(*) AS ct FROM custassets) AS small
   ) y USING (rn);

窗口函数在 PostgreSQL 8.4 版本中被引入。

- Erwin Brandstetter

---

Erwin，感谢您的详细回答 - 非常感谢。现在我还应该查找WITH和USING！</brainmelt> :) - halfer

@halfer: 不用担心，两者都很容易理解。CTE基本上是可以多次使用的子查询，而“USING（rn）”基本上是“ON x.rn = y.rn”的简称。不过，它们之间存在一些细微的差别。只需按照我的链接进行操作即可。 - Erwin Brandstetter

Answer 2

WITH a_ttl AS (
    SELECT count(*) AS ttl FROM custassets c),
b_ttl AS (
    SELECT count(*) AS ttl FROM tags),
rows AS (
    SELECT gs.*
      FROM generate_series(1,
           (SELECT max(ttl) AS ttl FROM
              (SELECT ttl FROM a_ttl UNION SELECT ttl FROM b_ttl) AS m))
           AS gs(row)),
tab_a_rand AS (
    SELECT custassets_id, row_number() OVER (order by random()) as row
      FROM custassets),
tab_b_rand AS (
    SELECT id, row_number() OVER (order by random()) as row
      FROM tags)
SELECT a.custassets_id, b.id
  FROM rows r
  JOIN a_ttl ON 1=1 JOIN b_ttl ON 1=1
  LEFT JOIN tab_a_rand a ON a.row = (r.row % a_ttl.ttl)+1
  LEFT JOIN tab_b_rand b ON b.row = (r.row % b_ttl.ttl)+1
 ORDER BY 1,2;

您可以在 SQL Fiddle 上测试此查询。

- vyegorov

---

哇，如果 Erwin 的解决方案让我的大脑过热，那么这个解决方案就让它坍塌成黑洞了！非常出色的努力，还有一个 SQLfiddle；谢谢加一。 - halfer

Answer 3

这里提供一种不同的方法来随机从2个表中选择一个组合，假设两个表a和b都有主键id。这些表不需要具有相同的大小，并且第二行是独立于第一行选择的，对于测试数据可能并不那么重要。

SELECT * FROM a, b 
 WHERE a.id = (
    SELECT id 
    FROM a 
    OFFSET (
        SELECT random () * (SELECT count(*) FROM a)
    ) 
    LIMIT 1) 
 AND b.id = (
    SELECT id 
    FROM b 
    OFFSET (
        SELECT random () * (SELECT count(*) FROM b)
        ) 
    LIMIT 1);

两个表进行测试，一个表大小为7000行，另一个表大小为10万行，结果：立即返回。如果要返回多个结果，您需要反复调用查询 - 增加LIMIT并将x.id =更改为x.id IN将会产生（aA，aB，bA，bB）的结果模式。

- user unknown

Answer 4

在关系型数据库使用这么多年之后，我很困扰的是似乎没有很好的跨数据库处理方式。MSDN文章http://msdn.microsoft.com/en-us/library/cc441928.aspx提供了一些有趣的想法，但当然那不是PostgreSQL。即使如此，他们的解决方案也需要单次扫描，而我认为应该能够在不扫描的情况下完成。

我可以想象几种可能在选择时不需要扫描的方法，但这将涉及创建另一个表，将您表的主键映射到随机数（或稍后随机选择的线性序列，从某些方面来看实际上可能更好），当然，这也可能存在问题。

我意识到这可能是一个无用的评论，我只是觉得我需要发泄一下。

- JayC

---

嘿，好吧，如果答案是“不可能”，那就可以了 :)。我们会看看其他的答案。 - halfer

实际上，我也想看看其他的答案。我的意思并不是说这个答案不可能存在，只是指出特定解决方案似乎需要大量设置或接近全表扫描，因此不太好。我必须承认，我不确定你的查询有什么问题。 - JayC

现代的大多数RDBMS都支持窗口函数（MySQL是不光彩的例外）。这里的所有答案基本上在MSSQL、Oracle和PostgreSQL中都可以使用。 - Erwin Brandstetter

Answer 5

如果您只想從每一方獲取一組隨機行，可以使用偽隨機數生成器。我會使用類似以下的代碼：

select *
from (select a.*, row_number() over (order by NULL) as rownum -- NULL may not work, "(SELECT NULL)" works in MSSQL
      from a
     ) a cross join
     (select b.*,  row_number() over (order by NULL) as rownum
      from b
     ) b
where a.rownum <= 30 and b.rownum <= 30

这是在执行笛卡尔积，假设a和b至少各有30行，则返回900行。

然而，我理解你的问题是要获取随机组合。再次强调，我会采用伪随机方法。

select *
from (select a.*, row_number() over (order by NULL) as rownum -- NULL may not work, "(SELECT NULL)" works in MSSQL
      from a
     ) a cross join
     (select b.*,  row_number() over (order by NULL) as rownum
      from b
     ) b
where modf(a.rownum*107+b.rownum*257+17, 101) < <some vaue>

这让您可以在任意行之间获取组合。

- Gordon Linoff

---

谢谢回复；是的，我需要随机组合（为了清晰起见，我已经在问题中添加了有问题的结果集）。我尝试了您的第二个查询，但我不确定Postgres（8.4）是否支持OVER。那是仅限于MSSQL Server的关键字吗？ - halfer

@halfer：窗口函数（包括row_number()）在Postgres 8.4中得到支持。但是，OVER (ORDER BY NULL)只是噪音，可以简化为OVER ()。无论哪种方法都不适合产生随机结果。您将获得一个实现特定的、任意的顺序，大多数情况下与行输入的顺序相同。 - Erwin Brandstetter

@ErwinBrandstetter - 谢谢。我彻底搜索了“postgresql over”，但可能错过了它——也许“over”是一个太常见的词！我不熟悉这组函数，所以我会详细阅读它们。 - halfer

窗口子句中的order by的目的是生成任意顺序的序列。其他值肯定可以包括在内。伪随机数生成器的行为会像“第n个”选择而不是“前n个”选择，因此即使有真正的排序，也可能会产生伪随机结果。 - Gordon Linoff

高登，多谢啦。PG 抱怨 modf，所以我自己加了一个 % 函数，并且带有一个 LIMIT 50，效果很好。你说的伪随机性是对的——我试过用 ORDER BY RANDOM()，结果查询在我取消之后还运行了很多分钟！（我的两张表分别有 50k 和 5k 行）。而且我的使用场景也不需要真正的随机性。 - halfer

Answer 6

仅使用随机函数的笛卡尔积似乎运行得相当不错。简单易懂...

-- Cartesian product
-- EXPLAIN ANALYZE
INSERT INTO dirgraph(point_from,point_to,costs)
SELECT p1.the_point , p2.the_point, (1000*random() ) +1
FROM allpoints p1
JOIN allpoints p2 ON random() < 0.002
        ;

- wildplasser