主页 / dba / 问题 / 159213
Accepted
joanolo
Asked: 2016-12-27 12:27:58 +0800 CST

如何（最佳）从两个表（a，b）中获取（a.id，b.id）对的随机样本？

  • 772

假设我必须非常简单的表格

CREATE TABLE a(id integer PRIMARY KEY, 
       t timestamp default now(), 
       sensor_readings real[]);
CREATE TABLE b(id integer PRIMARY KEY, 
       t timestamp default now(), 
       sensor_readings real[]);

有一些关于他们的数据

INSERT INTO a(id) SELECT generate_series(    1,   100);
INSERT INTO b(id) SELECT generate_series(10001, 10100);

实际上，表 a 可能有大约 100_000 行，而表 b 大约有 50_000 行。在实践中，id 序列也可能有间隙（大约 %）。因此，笛卡尔积 axb 具有数十亿的基数。

我想随机抽取 1_000 个排序对（a.id，b.id）。我可以使用类似以下查询的内容：

SELECT  
    *
FROM
(
    SELECT
        *
    FROM
        (
        SELECT 
            a.id AS a_id, b.id AS b_id
        FROM
            a CROSS JOIN b
        ORDER BY
            random()
        ) AS s0
    LIMIT
        1000 
) AS s1
ORDER BY
    a_id, b_id ;

...但是一旦 a 或 b 上的行数增加（由于 CROSS JOIN 的增长），它就会变得非常低效。

有没有办法以最佳方式做与此等效的事情？也就是说，是否有一种实用的方法可以从a x b关系中获取随机行样本，而无需实际实例化它。

注意：对于 a.id 或 b.id 可以重复的事实没有限制。虽然这对 (a.id, b.id) 不能。

如果我试图用命令式语言对此进行编程，我很可能会使用循环并执行类似以下伪代码的操作（然后，请统计学家对其进行检查，以确保我真的采取了样本其中所有对具有相同的被选中概率）：

start with a result set equal to {} (empty set)
while size of result set < 1000
    Pick the id value from a random row from table a -> rand_id_a
    Pick the id value from a random row from table b -> rand_id_b
    If (rand_id_a, rand_id_b) not in result set
        append (rand_id_a, rand_id_b) to result set
    end if
end while
sort result set and return it

有没有办法在不求助于循环的情况下获得等效的结果？如果没有，是否有使用 plpgSQL 的有效方法？（或任何其他语言）

postgresql random

2 个回答

  1. Best Answer

    最佳解决方案取决于您的设置的确切定义。对于示例设置，这很简单：

    • 没有间隙的序列整数列。

    SELECT DISTINCT
           1 + trunc(random() * 100)::int AS a_id
     , 10001 + trunc(random() * 100)::int AS b_id
FROM   generate_series(1, 1100) g  -- enough excess to make up for possible dupes
LIMIT  1000;  -- only take 1000

    唯一有趣的问题：如何有效地折叠骗子。解决方案：让 Postgres 决定。只需使用DISTINCT.
    我们甚至根本不需要涉及表格。超级快。

    请注意，random()生成（根据文档）：

    0.0 <= x < 1.0 范围内的随机值

    因此，要准确1 + trunc(random() * 100)::int覆盖1到100之间的 ID 号。

    实际设置？

    您需要更具体地了解您的实际设置。假设每个表中至少有一个有效负载列，而不仅仅是 ID 列。

    CREATE TABLE a(a_id integer PRIMARY KEY, a text);
CREATE TABLE b(b_id integer PRIMARY KEY, b text);

INSERT INTO a(a_id, a)
SELECT g, 't' || g FROM generate_series(    1,   100) g;
INSERT INTO b(b_id, b)
SELECT g, 't' || g FROM generate_series(10001, 10100) g;

    询问：

    SELECT a.a_id, a.a, b.b_id, b.b
FROM  (
    SELECT DISTINCT
               1 + trunc(random() * 100)::int AS a_id  -- cover *whole* key space
         , 10001 + trunc(random() * 100)::int AS b_id  -- maybe add reserve for new rows
    FROM   generate_series(1, 1100) g
    LIMIT  1000
    ) ra
JOIN   a USING (a_id)
JOIN   b USING (b_id);

    真正随机、非常快且几乎与实际表大小无关。

    a(a_id)您所需要的只是和上的索引b(b_id)。或者可能是多列索引以允许仅索引扫描。

    该解决方案也适用于跳过调用的一些间隙nextval()，只要间隙不比island多多少，生成足够的组合来弥补间隙损失仍然非常便宜。（比使用大表的笛卡尔积或对整个大表进行排序要便宜得多ORDER BY random()。）只要确保生成足够的组合即可。

    SELECT a.a_id, a.a, b.b_id, b.b
FROM  (
    SELECT DISTINCT
               1 + trunc(random() * 100)::int AS a_id
         , 10001 + trunc(random() * 100)::int AS b_id
    FROM   generate_series(1, 1100) g  -- enough to cover dupes *and* gaps
    ) ra
JOIN   a USING (a_id)
JOIN   b USING (b_id)
LIMIT  1000;  -- LIMIT moves to outer query to cover gaps

    如果有多个空白，请从 95% 的时间足够的多个组合开始，并添加一个递归步骤以添加更多行（如果您不满足的话）。相关答案中有此解决方案的配方（针对单个表）。还有更多解释和变化：

    • 4

  2. 我想随机抽取 1000 个排序对（a.id，b.id）。

    它始终取决于随机的含义，但如果您要定义所需的行数，那么您可能需要扩展tsm_system_rows

    tsm_system_rows

    模块提供了表采样方法SYSTEM_ROWS，可以在SELECT命令的TABLESAMPLE子句中使用。

    此表采样方法接受一个整数参数，该参数是要读取的最大行数。生成的样本将始终包含那么多行，除非表不包含足够的行，在这种情况下会选择整个表。SYSTEM_ROWS 与内置的 SYSTEM 采样方法一样，执行块级采样，因此样本不是完全随机的，而是可能会受到聚类效应的影响，尤其是在仅请求少量行的情况下。

    首先安装扩展

    CREATE EXTENSION tsm_system_rows;

    然后你的查询，

    SELECT *
FROM a
CROSS JOIN b
TABLESAMPLE SYSTEM_ROWS(1000);

    这里重要的是它始终提供 1000 ROWS，这比我们可以说的要多random() <= 0.10，或者 for TABLESAMPLE BERNOULLI。

    如果那不是很好的nuff'

    如果你真的需要随机并且不能接受聚类的缺点，那么我会使用

    ORDER BY random()
LIMIT x;

    如果您需要修剪重复项

    修剪重复项（如果a.id和b.id不是UNIQUE）并保持结果集随机的唯一明智的方法是事先进行。这可能会变得很糟糕，因为TABLESAMPLE它还不能在虚拟表中工作，所以你必须创建一个临时表（它可能仍然存在于内存中）。害羞，你可以使用另一种既慢又丑的方法，但至少它不必编写

    SELECT *
FROM (
  SELECT DISTINCT ON(a.id, b.id) a.id, b.id
  FROM a
  CROSS JOIN b
) AS t
ORDER BY random()
FETCH FIRST 1000 ROWS ONLY;
    • 0

相关问题