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 sequence
campo é 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 unnest
funçã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 subarray
funçã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.
bigint
você deve usarnumeric
como o tipo para armazená-los. É muito mais lento e ocupa muito mais espaço.numeric
e não uma string (text
por exemplo)? Não preciso executar operações matemáticas nas minhas seqüências.text
impede 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.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.Respostas:
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 ).
Agora você pode filtrar linhas como esta.
Realizei um pequeno experimento para descobrir o quão mais rápida é essa solução.
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.
fonte
numeric
para representar meus dados, pois eles podem estourarbigint
. Pode ser bom editar sua resposta para corresponder às restrições da pergunta. Enfim, farei um desempenho comparativo que vou postar aqui.numeric
etext
e a melhoria variou de 20 a 50 vezes, dependendo do comprimento de matrizes.numeric
.bigint
.bigint
, então parece que não tenho escolha. Mas se você tem uma idéia, estou interessado :).Você pode encontrar facilmente a subsequência ao converter as matrizes em seqüências de caracteres e substituir os colchetes por vírgulas:
Faça o mesmo para a matriz que você está procurando e adicione uma inicial e final
%
:Agora você o compara usando
LIKE
:Editar:
Violino está trabalhando novamente.
Se as matrizes forem normalizadas em uma linha por valor, você poderá aplicar a lógica baseada em conjunto:
n
deve 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 :-)Finalmente conte o número de linhas com o mesmo manequim e verifique se é o número correto:
Tente um índice de seqüências (val, id, n).
fonte
TEXT
campo (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).25
existe duas vezesid=4
, isso é realmente possível? Quantas correspondências existem em média / máximo para uma sequência pesquisada?{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.