Início / dba / Perguntas / 159213
Accepted
joanolo
Asked: 2016-12-27 12:27:58 +0800 CST

Como obter (otimamente) amostras aleatórias de pares (a.id, b.id) de duas tabelas (a, b)?

  • 772

Vamos supor que eu tenha tabelas muito simples

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[]);

com alguns dados sobre eles

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

Na realidade, a tabela a pode ter cerca de 100_000 linhas e a tabela b cerca de 50_000. Na prática, também, a sequência id pode ter lacunas (da ordem de alguns %). Assim, o produto cartesiano axb tem cardinalidade de bilhões.

Eu quero pegar uma amostra aleatória de 1_000 pares classificados (a.id, b.id). Eu posso usar algo como a seguinte consulta:

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 ;

... mas se tornaria extremamente ineficiente assim que o número de linhas em a ou b crescesse (devido ao crescimento do CROSS JOIN).

Existe alguma maneira de fazer algo equivalente a isso de maneira ideal? Ou seja, existe uma maneira prática de obter uma amostra aleatória de linhas da a x brelação sem realmente ter que instanciá-la.

NOTA: Não há limitação quanto ao fato de que a.id ou b.id podem ser repetidos. Embora o par (a.id, b.id) não possa.

Se eu estivesse tentando programar isso em uma linguagem imperativa, provavelmente usaria um loop e faria algo como o pseudocódigo a seguir (e, em seguida, verificaria por um estatístico, para ter certeza de que realmente peguei uma amostra onde todos os pares têm a mesma probabilidade de serem escolhidos):

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

Existe uma maneira de obter um resultado equivalente sem recorrer a loops? Se não, existe uma maneira eficiente de fazer isso usando plpgSQL? (ou qualquer outro idioma)

postgresql random

2 respostas

  1. Best Answer

    A melhor solução depende da definição exata de sua configuração. Para a configuração de exemplo, é trivial:

    • Colunas inteiras em série sem lacunas.

    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

    A única questão interessante: como dobrar dupes de forma eficiente. A solução: deixe o Postgres decidir. Basta usar DISTINCT.
    Nem precisamos envolver as tabelas. Super rápido.

    Observe que random()gera ( por documentação ):

    valor aleatório no intervalo 0,0 <= x < 1,0

    Portanto 1 + trunc(random() * 100)::int, para cobrir exatamente os números de identificação entre 1 e 100 .

    Configuração real?

    Você precisa ser mais específico sobre sua configuração real. Vamos supor que haja pelo menos uma coluna de carga útil em cada uma de suas tabelas, não apenas colunas de 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;

    Consulta:

    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);

    Verdadeiramente aleatório, muito rápido e quase independente do tamanho real da mesa.

    Tudo o que você precisa são índices em a(a_id)e b(b_id). Ou possivelmente índices de várias colunas para permitir varreduras somente de índice.

    A solução também funciona para alguns gaps de chamadas puladas nextval(), desde que não haja muito mais gaps do que ilhas , ainda é muito barato gerar combinações suficientes para cobrir perdas por gaps. ( Muito mais barato do que trabalhar com um produto cartesiano de tabelas grandes ou classificar tabelas grandes inteiras de ORDER BY random()qualquer maneira.) Apenas certifique-se de gerar combinações suficientes.

    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

    Com mais do que algumas lacunas , comece com um número de combinações que seja suficiente em 95% do tempo e adicione uma etapa recursiva para adicionar mais linhas se você ficar aquém. Existe uma receita para esta solução (para uma única tabela) na resposta relacionada. Também mais explicações e variações:

    • 4

  2. Eu quero pegar uma amostra aleatória de 1000 pares classificados (a.id, b.id).

    Sempre depende do que aleatório significa, mas se você estiver definindo a quantidade de linhas que deseja, provavelmente desejará a extensãotsm_system_rows

    tsm_system_rows

    O módulo fornece o método de amostragem de tabela SYSTEM_ROWS, que pode ser usado na cláusula TABLESAMPLE de um comando SELECT.

    Este método de amostragem de tabela aceita um único argumento inteiro que é o número máximo de linhas a serem lidas. A amostra resultante sempre conterá exatamente esse número de linhas, a menos que a tabela não contenha linhas suficientes, caso em que toda a tabela é selecionada. Assim como o método de amostragem SYSTEM integrado, SYSTEM_ROWS realiza amostragem em nível de bloco, de modo que a amostra não seja completamente aleatória, mas pode estar sujeita a efeitos de agrupamento, especialmente se apenas um pequeno número de linhas for solicitado.

    Primeiro instale a extensão

    CREATE EXTENSION tsm_system_rows;

    Então sua consulta,

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

    O importante aqui é que ele sempre fornece 1000 ROWS , o que é mais do que podemos dizer para random() <= 0.10, ou para TABLESAMPLE BERNOULLI.

    Se isso não é bom nuff'

    Se você realmente precisa de random e não pode aceitar a desvantagem de clustering, eu usaria

    ORDER BY random()
LIMIT x;

    Se você precisar eliminar duplicatas

    A única maneira sensata de eliminar duplicatas (se a.id, e b.idnão são UNIQUE) e manter o conjunto de resultados aleatório, é fazer isso de antemão. Isso pode ser desagradável porque TABLESAMPLEainda não funciona em tabelas virtuais, então você terá que criar uma tabela temporária (que ainda pode persistir na memória). Tímido disso, você pode usar o outro método que também é lento e feio, mas pelo menos não precisa escrever o

    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

relate perguntas