Rechercher des lignes où la séquence entière contient une sous-séquence donnée

9

Problème

Remarque: je me réfère aux séquences mathématiques , pas au mécanisme des séquences de PostgreSQL .

J'ai un tableau représentant des séquences d'entiers. La définition est:

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

Mon objectif est de trouver des lignes en utilisant une sous-séquence donnée. C'est-à-dire, les lignes où le sequencechamp est une séquence qui contient la sous-séquence donnée (dans mon cas, la séquence est ordonnée).

Exemple

Supposons que le tableau contienne les données suivantes:

+----+-------+------------+-------------------------------+
| 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}     |
+----+-------+------------+-------------------------------+

Donc, si la sous-séquence donnée est {12, 742, 225, 547}, je veux trouver la ligne 2.

De même, si la sous-séquence donnée est {3, 17, 25, 377}, je veux trouver la ligne 1 et la ligne 4.

Enfin, si la sous-séquence donnée l'est {12, 4, 3, 25, 377}, aucune ligne n'est renvoyée.

Enquêtes

Premièrement, je ne suis pas complètement certain que représenter des séquences avec un type de données de tableau est sage. Bien que cela semble approprié à la situation; Je crains que cela rend la manipulation plus compliquée. Il vaut peut-être mieux représenter les séquences différemment, en utilisant un modèle de relations avec une autre table.

De la même manière, je pense à étendre les séquences à l'aide de la unnestfonction tableau puis ajouter mes critères de recherche. Néanmoins, le nombre de termes dans la séquence étant variable, je ne vois pas comment faire cela.

Je sais qu'il est également possible de couper ma séquence en sous-séquence en utilisant la subarrayfonction de module intarray mais je ne vois pas en quoi cela me profite pour ma recherche.

Contraintes

Même si en ce moment mon modèle est encore en développement, la table est destinée à être composée de nombreuses séquences, entre 50 000 et 300 000 lignes. J'ai donc une forte contrainte de performance.

Dans mon exemple, j'ai utilisé des entiers relativement petits. En pratique, il est possible que ces nombres entiers deviennent beaucoup plus grands, jusqu'à déborder bigint. Dans une telle situation, je pense que le mieux est de stocker les nombres sous forme de chaînes (car il n'est pas nécessaire d'effectuer ces séquences d'opérations mathématiques). Cependant, en optant pour cette solution, cela rend impossible l'utilisation du module intarray , mentionné ci-dessus.

mlpo
la source
S'ils peuvent déborder, bigintvous devez les utiliser numericcomme type pour les stocker. C'est beaucoup plus lent et prend beaucoup plus de place cependant.
Craig Ringer
@CraigRinger Pourquoi utiliser numericet non une chaîne ( textpar exemple)? Je n'ai pas besoin d'effectuer d'opérations mathématiques sur mes séquences.
mlpo
2
Parce qu'il est plus compact et à bien des égards plus rapide que text, et vous empêche de stocker de fausses données non numériques. Cela dépend, si vous ne faites que des E / S, vous voudrez peut-être que le texte réduise le traitement des E / S.
Craig Ringer
@CraigRinger En effet, le type est plus cohérent. Concernant les performances, je testerai quand j'aurai trouvé un moyen de faire ma recherche.
mlpo
2
@CraigRinger Cela pourrait fonctionner si la commande n'a pas d'importance. Mais ici, les séquences sont ordonnées. Exemple: SELECT ARRAY[12, 4, 3, 17, 25, 377, 456, 25] @> ARRAY[12, 4, 3, 25, 377];retournera true, car la commande n'est pas prise en compte par cet opérateur.
mlpo

Réponses:

3

Si vous recherchez des améliorations significatives des performances de la réponse de dnoeth , envisagez d'utiliser une fonction C native et de créer l'opérateur approprié.

Voici un exemple pour les tableaux int4. ( Une variante de tableau générique et le script SQL correspondant ).

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

Vous pouvez maintenant filtrer des lignes comme celle-ci.

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

J'ai mené une petite expérience pour découvrir à quel point cette solution est plus rapide.

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"

Donc, c'est environ 16 fois plus rapide. Si cela ne suffit pas, vous pouvez ajouter la prise en charge des index GIN ou GiST, mais ce sera une tâche beaucoup plus difficile.

Slonopotamus
la source
Cela semble intéressant, mais j'utilise des chaînes ou le type numericpour représenter mes données car elles peuvent déborder bigint. Il pourrait être judicieux de modifier votre réponse pour qu'elle corresponde aux contraintes de la question. Quoi qu'il en soit, je ferai une performance comparative que je posterai ici.
mlpo
Je ne sais pas si c'est une bonne pratique de coller de gros blocs de code dans les réponses car elles sont censées être minimales et vérifiables. Une version de tableau générique de cette fonction est quatre fois plus longue et assez encombrante. Je l'ai également testé avec numericet textet l'amélioration variait de 20 à 50 fois selon la longueur des tableaux.
Slonopotamus
Oui, cependant il est nécessaire que les réponses répondent aux questions :-). Ici, il me semble qu'une réponse respectant les contraintes est intéressante (car cet aspect fait partie de la question). Néanmoins, il peut ne pas être nécessaire de proposer une version générique. Juste une version avec des chaînes ou numeric.
mlpo
Quoi qu'il en soit, j'ai ajouté la version pour les tableaux génériques car elle serait presque la même pour tout type de données de longueur variable. Mais si vous êtes vraiment préoccupé par les performances, vous devez vous en tenir aux types de données de taille fixe comme bigint.
Slonopotamus
J'aimerais beaucoup faire ça. Le problème est que certaines de mes séquences débordent bien au-delà bigint, il semble donc que je n'ai pas le choix. Mais si vous avez une idée, ça m'intéresse :).
mlpo
1

Vous pouvez facilement trouver la sous-séquence lorsque vous convertissez les tableaux en chaînes et remplacez les accolades par des virgules:

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

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

Faites de même pour le tableau que vous recherchez et ajoutez un début et une fin %:

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

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

Maintenant, vous le comparez en utilisant LIKE:

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

Éditer:

Fiddle travaille à nouveau.

Si les tableaux sont normalisés en une ligne par valeur, vous pouvez appliquer une logique basée sur un ensemble:

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

ndoit être séquentiel, pas de doublons, pas de lacunes. Rejoignez maintenant des valeurs communes et exploitez le fait que les séquences sont séquentielles :-)

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;

Enfin, comptez le nombre de lignes avec le même mannequin et vérifiez si c'est le bon numéro:

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

Essayez un index sur les séquences (val, id, n).

dnoeth
la source
J'ai également envisagé cette solution par la suite. Mais je vois plusieurs problèmes qui semblent assez gênants: tout d'abord, j'ai peur que cette solution soit très inefficace, il faut transtyper chaque tableau de chaque ligne avant de faire un motif de recherche. Il est possible d'envisager de stocker des séquences dans un TEXTchamp ( varcharc'est une mauvaise idée à mon avis, les séquences peuvent être longues, comme les nombres, donc la taille est plutôt imprévisible), pour éviter le cast; mais il n'est toujours pas possible d'utiliser des index pour améliorer les performances (en outre utiliser un champ string ne semble pas forcément judicieux, voir commentaire de @CraigRinger ci-dessus).
mlpo
@mlpo: Quelle est votre attente de performance? Pour pouvoir utiliser un index, vous devez normaliser la séquence en une ligne par valeur, appliquer une division relationnelle et enfin vérifier si l'ordre est correct. Dans votre exemple 25existe deux fois id=4, est-ce réellement possible? Combien de correspondances existent en moyenne / maximum pour une séquence recherchée?
dnoeth
Une séquence peut contenir plusieurs fois le même numéro. Par exemple, {1, 1, 1, 1, 12, 2, 2, 12, 12, 1, 1, 5, 4}c'est tout à fait possible. Concernant le nombre de correspondances, les sous-séquences utilisées sont normalement censées limiter le nombre de résultats. Cependant, certaines séquences sont très similaires, et il peut parfois être intéressant d'utiliser une sous-séquence plus courte pour obtenir plus de résultats. J'estime que le nombre de correspondances pour la majorité des cas est compris entre 0 et 100. Avec toujours la possibilité qu'occasionnellement la correspondance de sous-séquences avec beaucoup de séquences soit courte ou très courante.
mlpo
@mlpo: J'ai ajouté une solution basée sur un ensemble et je serais très intéressé par une comparaison des performances :-)
dnoeth
@ypercube: C'était juste un ajout rapide pour retourner un résultat plus significatif :-) Ok, c'est horrible, je vais le changer.l
dnoeth