Encontre linhas onde a sequência inteira contém uma determinada subsequência

9

Problema

Nota: Refiro-me às seqüências matemáticas , não ao mecanismo de sequências do PostgreSQL .

Eu tenho uma tabela representando sequências de números inteiros. A definição é:

CREATE TABLE sequences
(
  id serial NOT NULL,
  title character varying(255) NOT NULL,
  date date NOT NULL,
  sequence integer[] NOT NULL,
  CONSTRAINT "PRIM_KEY_SEQUENCES" PRIMARY KEY (id)
);

Meu objetivo é encontrar linhas usando uma determinada subsequência. Ou seja, as linhas em que o sequencecampo é uma sequência que contém a subsequência especificada (no meu caso, a sequência é ordenada).

Exemplo

Suponha que a tabela contenha os seguintes dados:

+----+-------+------------+-------------------------------+
| id | title |    date    |           sequence            |
+----+-------+------------+-------------------------------+
|  1 | BG703 | 2004-12-24 | {1,3,17,25,377,424,242,1234}  |
|  2 | BG256 | 2005-05-11 | {5,7,12,742,225,547,2142,223} |
|  3 | BD404 | 2004-10-13 | {3,4,12,5698,526}             |
|  4 | BK956 | 2004-08-17 | {12,4,3,17,25,377,456,25}     |
+----+-------+------------+-------------------------------+

Portanto, se a subsequência especificada for {12, 742, 225, 547}, desejo encontrar a linha 2.

Da mesma forma, se a subsequência especificada for {3, 17, 25, 377}, desejo encontrar a linha 1 e a linha 4.

Por fim, se a subsequência especificada for {12, 4, 3, 25, 377}, não haverá linhas retornadas.

Investigações

Primeiro, não tenho certeza absoluta de que as seqüências com um tipo de dados de matriz sejam sábias. Embora isso pareça apropriado para a situação; Temo que isso torne o manuseio mais complicado. Talvez seja melhor representar as seqüências de maneira diferente, usando um modelo de relações com outra tabela.

Da mesma forma, penso em expandir as seqüências usando a unnestfunção array e, em seguida, adicionar meus critérios de pesquisa. No entanto, o número de termos na sequência sendo variável, não vejo como fazer isso.

Eu sei que também é possível cortar minha sequência em subsequência usando a subarrayfunção do módulo intarray , mas não vejo como isso me beneficia em minha pesquisa.

Restrições

Mesmo que, no momento, meu modelo ainda esteja sendo desenvolvido, a tabela deve ser composta de várias seqüências, entre 50.000 e 300.000 linhas. Então, eu tenho uma forte restrição de desempenho.

No meu exemplo, usei números inteiros relativamente pequenos. Na prática, é possível que esses números inteiros se tornem muito maiores, até transbordar bigint. Em tal situação, acho que o melhor é armazenar números como seqüências de caracteres (já que não é necessário executar essas seqüências de operações matemáticas). No entanto, ao optar por esta solução, isso torna impossível o uso do módulo intarray , mencionado acima.

mlpo
fonte
Se eles podem transbordar, bigintvocê deve usar numericcomo o tipo para armazená-los. É muito mais lento e ocupa muito mais espaço.
Craig Ringer
@CraigRinger Por que usar numerice não uma string ( textpor exemplo)? Não preciso executar operações matemáticas nas minhas seqüências.
mlpo 29/07
2
Porque é mais compacto e, em muitos aspectos, mais rápido que o textimpede de armazenar dados não numéricos falsos. Depende, se você estiver executando apenas E / S, poderá desejar que o texto reduza o processamento de E / S.
Craig Ringer
@ CraigRinger De fato, o tipo é mais consistente. Em relação ao desempenho, testarei quando tiver encontrado uma maneira de fazer minha pesquisa.
mlpo 29/07
2
@ CraigRinger Pode funcionar se o pedido não for importante. Mas aqui, as seqüências são ordenadas. Exemplo: SELECT ARRAY[12, 4, 3, 17, 25, 377, 456, 25] @> ARRAY[12, 4, 3, 25, 377];retornará true, porque o pedido não é considerado por este operador.
mlpo 29/07

Respostas:

3

Se você estiver procurando por melhorias significativas de desempenho na resposta de dnoeth , considere usar uma função C nativa e criar o operador apropriado.

Aqui está um exemplo para matrizes int4. ( Uma variante de matriz genérica e o script SQL correspondente ).

Datum
_int_sequence_contained(PG_FUNCTION_ARGS)
{
    return DirectFunctionCall2(_int_contains_sequence,
                               PG_GETARG_DATUM(1),
                               PG_GETARG_DATUM(0));
}

Datum
_int_contains_sequence(PG_FUNCTION_ARGS)
{
    ArrayType  *a = PG_GETARG_ARRAYTYPE_P(0);
    ArrayType  *b = PG_GETARG_ARRAYTYPE_P(1);
    int         na, nb;
    int32      *pa, *pb;
    int         i, j;

    na = ArrayGetNItems(ARR_NDIM(a), ARR_DIMS(a));
    nb = ArrayGetNItems(ARR_NDIM(b), ARR_DIMS(b));
    pa = (int32 *) ARR_DATA_PTR(a);
    pb = (int32 *) ARR_DATA_PTR(b);

    /* The naive searching algorithm. Replace it with a better one if your arrays are quite large. */
    for (i = 0; i <= na - nb; ++i)
    {
        for (j = 0; j < nb; ++j)
            if (pa[i + j] != pb[j])
                break;

        if (j == nb)
            PG_RETURN_BOOL(true);
    }

    PG_RETURN_BOOL(false);
}
CREATE FUNCTION _int_contains_sequence(_int4, _int4)
RETURNS bool
AS 'MODULE_PATHNAME'
LANGUAGE C STRICT IMMUTABLE;

CREATE FUNCTION _int_sequence_contained(_int4, _int4)
RETURNS bool
AS 'MODULE_PATHNAME'
LANGUAGE C STRICT IMMUTABLE;

CREATE OPERATOR @@> (
  LEFTARG = _int4,
  RIGHTARG = _int4,
  PROCEDURE = _int_contains_sequence,
  COMMUTATOR = '<@@',
  RESTRICT = contsel,
  JOIN = contjoinsel
);

CREATE OPERATOR <@@ (
  LEFTARG = _int4,
  RIGHTARG = _int4,
  PROCEDURE = _int_sequence_contained,
  COMMUTATOR = '@@>',
  RESTRICT = contsel,
  JOIN = contjoinsel
);

Agora você pode filtrar linhas como esta.

SELECT * FROM sequences WHERE sequence @@> '{12, 742, 225, 547}'

Realizei um pequeno experimento para descobrir o quão mais rápida é essa solução.

CREATE TEMPORARY TABLE sequences AS
SELECT array_agg((random() * 10)::int4) AS sequence, g1 AS id
FROM generate_series(1, 100000) g1
  CROSS JOIN generate_series(1, 30) g2
GROUP BY g1;
EXPLAIN ANALYZE SELECT * FROM sequences
WHERE        translate(cast(sequence as text), '{}',',,')
 LIKE '%' || translate(cast('{1,2,3,4}'as text), '{}',',,') || '%'

"Seq Scan on sequences  (cost=0.00..7869.42 rows=28 width=36) (actual time=2.487..334.318 rows=251 loops=1)"
"  Filter: (translate((sequence)::text, '{}'::text, ',,'::text) ~~ '%,1,2,3,4,%'::text)"
"  Rows Removed by Filter: 99749"
"Planning time: 0.104 ms"
"Execution time: 334.365 ms"
EXPLAIN ANALYZE SELECT * FROM sequences WHERE sequence @@> '{1,2,3,4}'

"Seq Scan on sequences  (cost=0.00..5752.01 rows=282 width=36) (actual time=0.178..20.792 rows=251 loops=1)"
"  Filter: (sequence @@> '{1,2,3,4}'::integer[])"
"  Rows Removed by Filter: 99749"
"Planning time: 0.091 ms"
"Execution time: 20.859 ms"

Portanto, é cerca de 16 vezes mais rápido. Se não for suficiente, você poderá adicionar suporte aos índices GIN ou GiST, mas isso será uma tarefa muito mais difícil.

Slonopotamus
fonte
Parece interessante, no entanto, eu uso seqüências de caracteres ou o tipo numericpara representar meus dados, pois eles podem estourar bigint. Pode ser bom editar sua resposta para corresponder às restrições da pergunta. Enfim, farei um desempenho comparativo que vou postar aqui.
mlpo 4/08/15
Não tenho certeza se é uma boa prática colar grandes blocos de código nas respostas, pois elas devem ser mínimas e verificáveis. Uma versão genérica da matriz dessa função é quatro vezes mais longa e bastante complicada. Também já testado com numerice texte a melhoria variou de 20 a 50 vezes, dependendo do comprimento de matrizes.
Slonopotamus
Sim, porém é necessário que as respostas respondam às perguntas :-). Aqui, parece-me que uma resposta que cumpre as restrições é interessante (porque esse aspecto faz parte da pergunta). No entanto, pode não ser necessário propor uma versão genérica. Apenas uma versão com strings ou numeric.
Mlp
De qualquer forma, adicionei a versão para matrizes genéricas, pois seria quase a mesma para qualquer tipo de dados de tamanho variável. Mas se você está realmente preocupado com o desempenho, deve usar tipos de dados de tamanho fixo como bigint.
Slonopotamus
Eu adoraria fazer isso. O problema é que algumas das minhas seqüências transbordam muito além bigint, então parece que não tenho escolha. Mas se você tem uma idéia, estou interessado :).
mlpo
1

Você pode encontrar facilmente a subsequência ao converter as matrizes em seqüências de caracteres e substituir os colchetes por vírgulas:

translate(cast(sequence as varchar(10000)), '{}',',,')

{1,3,17,25,377,424,242,1234} -> ',1,3,17,25,377,424,242,1234,'

Faça o mesmo para a matriz que você está procurando e adicione uma inicial e final %:

'%' || translate(cast(searchedarray as varchar(10000)), '{}',',,') || '%'

{3, 17, 25, 377} -> '%,3,17,25,377,%'

Agora você o compara usando LIKE:

WHERE        translate(cast(sequence      as varchar(10000)), '{}',',,')
 LIKE '%' || translate(cast(searchedarray as varchar(10000)), '{}',',,') || '%'

Editar:

Violino está trabalhando novamente.

Se as matrizes forem normalizadas em uma linha por valor, você poderá aplicar a lógica baseada em conjunto:

CREATE TABLE sequences
( id int NOT NULL,
  n int not null,
  val numeric not null
);

insert into sequences values(  1, 1,1     );
insert into sequences values(  1, 2,3     );
insert into sequences values(  1, 3,17    );
insert into sequences values(  1, 4,25    );
insert into sequences values(  1, 5,377   );
insert into sequences values(  1, 6,424   );
insert into sequences values(  1, 7,242   );
insert into sequences values(  1, 8,1234  );
insert into sequences values(  2, 1,5     );
insert into sequences values(  2, 2,7     );
insert into sequences values(  2, 3,12    );
insert into sequences values(  2, 4,742   );
insert into sequences values(  2, 5,225   );
insert into sequences values(  2, 6,547   );
insert into sequences values(  2, 7,2142  );
insert into sequences values(  2, 8,223   );
insert into sequences values(  3, 1,3     );
insert into sequences values(  3, 2,4     );
insert into sequences values(  3, 3,12    );
insert into sequences values(  3, 4,5698  );
insert into sequences values(  3, 5,526   );          
insert into sequences values(  4, 1,12    );
insert into sequences values(  4, 2,4     );
insert into sequences values(  4, 3,3     );
insert into sequences values(  4, 4,17    );
insert into sequences values(  4, 5,25    );
insert into sequences values(  4, 6,377   );
insert into sequences values(  4, 7,456   );
insert into sequences values(  4, 8,25    );
insert into sequences values(  5, 1,12    );
insert into sequences values(  5, 2,4     );
insert into sequences values(  5, 3,3     );
insert into sequences values(  5, 4,17    );
insert into sequences values(  5, 5,17    );
insert into sequences values(  5, 6,25    );
insert into sequences values(  5, 7,377   );
insert into sequences values(  5, 8,456   );
insert into sequences values(  5, 9,25    );

ndeve ser seqüencial, sem duplicatas, sem lacunas. Agora junte-se a valores comuns e explore o fato de que seqüências são seqüenciais :-)

with searched (n,val) as (
  VALUES
   ( 1,3  ),
   ( 2,17 ),
   ( 3,25 ),
   ( 4,377)
)
select seq.id, 
   -- this will return the same result if the values from both tables are in the same order
   -- it's a meaningless dummy, but the same meaningless value for sequential rows 
   seq.n - s.n as dummy,
   seq.val,
   seq.n,
   s.n 
from sequences as seq join searched as s
on seq.val = s.val
order by seq.id, dummy, seq.n;

Finalmente conte o número de linhas com o mesmo manequim e verifique se é o número correto:

with searched (n,val) as (
  VALUES
   ( 1,3  ),
   ( 2,17 ),
   ( 3,25 ),
   ( 4,377)
)
select distinct seq.id
from sequences as seq join searched as s
on seq.val = s.val
group by 
   seq.id,
   seq.n - s.n
having count(*) = (select count(*) from searched)
;

Tente um índice de seqüências (val, id, n).

não
fonte
Eu também considerei essa solução depois. Mas vejo vários problemas que parecem bastante incômodos: antes de tudo, receio que essa solução seja muito ineficiente, precisamos converter cada matriz de cada linha antes de fazer um padrão de pesquisa. É possível considerar o armazenamento de seqüências em um TEXTcampo ( varcharé uma má ideia, na minha opinião, as seqüências podem ser longas, conforme os números, de modo que o tamanho é bastante imprevisível), para evitar a conversão; mas ainda não é possível usar índices para melhorar o desempenho (além disso, usar um campo de string não parece necessariamente criterioso, consulte o comentário de @CraigRinger acima).
mlpo 29/07
@mlpo: Qual é a sua expectativa de desempenho? Para poder usar um índice, você deve normalizar a sequência em uma linha por valor, aplicar uma Divisão Relacional e, finalmente, verificar se a ordem está correta. No seu exemplo 25existe duas vezes id=4, isso é realmente possível? Quantas correspondências existem em média / máximo para uma sequência pesquisada?
Dnoeth 29/07
Uma sequência pode conter várias vezes o mesmo número. Por exemplo, {1, 1, 1, 1, 12, 2, 2, 12, 12, 1, 1, 5, 4}é bem possível. Em relação ao número de correspondências, as subseqüências usadas normalmente são consideradas limitadoras do número de resultados. No entanto, algumas seqüências são muito semelhantes e às vezes pode ser interessante usar uma subsequência mais curta para obter mais resultados. Eu estimo que o número de correspondências para a maioria dos casos esteja entre 0 e 100. Sempre com a possibilidade de que ocasionalmente a subsequência corresponda a muitas sequências quando é curta ou muito comum.
mlpo 29/07
@mlpo: Eu adicionei uma solução baseada em conjunto e eu estaria muito interessado em alguma comparação de desempenho :-)
dnoeth
@ypercube: Este foi apenas um add rápido para retornar um resultado mais significativo :-) Ok, é horrível, eu vou mudar it.l
dnoeth