Znajdź wiersze, w których sekwencja liczb całkowitych zawiera podsekwencję

9

Problem

Uwaga: mam na myśli sekwencje matematyczne , a nie mechanizm sekwencji w PostgreSQL .

Mam tabelę reprezentującą sekwencje liczb całkowitych. Definicja to:

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

Moim celem jest znalezienie wierszy przy użyciu podanego podsekwencji. To znaczy, wiersze, w których sequencepole jest sekwencją zawierającą podaną podsekwencję (w moim przypadku sekwencja jest uporządkowana).

Przykład

Załóżmy, że tabela zawiera następujące dane:

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

Więc jeśli podanym podsekwencją jest {12, 742, 225, 547}, chcę znaleźć wiersz 2.

Podobnie, jeśli podanym podsekwencją jest {3, 17, 25, 377}, chcę znaleźć wiersz 1 i wiersz 4.

Wreszcie, jeśli podanym podsekwencją jest {12, 4, 3, 25, 377}, to nie są zwracane wiersze.

Dochodzenia

Po pierwsze, nie jestem całkowicie pewien, czy sekwencje z tablicowym typem danych są mądre. Chociaż wydaje się to odpowiednie do sytuacji; Obawiam się, że utrudnia to obsługę. Być może lepiej jest inaczej reprezentować sekwencje, używając modelu relacji z inną tabelą.

W ten sam sposób myślę o rozszerzeniu sekwencji za pomocą unnestfunkcji tablicowej, a następnie dodaniu moich kryteriów wyszukiwania. Niemniej liczba zmiennych w sekwencji jest zmienna. Nie widzę, jak to zrobić.

Wiem, że można również przycinać sekwencję w podsekwencjach za pomocą subarrayfunkcji modułu intarray , ale nie widzę korzyści, jakie przyniosło mi to wyszukiwanie.

Ograniczenia

Nawet jeśli obecnie mój model jest wciąż rozwijany, tabela ma składać się z wielu sekwencji, od 50 000 do 300 000 wierszy. Mam więc silne ograniczenie wydajności.

W moim przykładzie użyłem stosunkowo małych liczb całkowitych. W praktyce możliwe jest, że te liczby całkowite staną się znacznie większe, aż do przepełnienia bigint. W takiej sytuacji najlepiej jest przechowywać liczby jako ciągi znaków (ponieważ nie jest konieczne wykonywanie tych sekwencji operacji matematycznych). Jednak wybranie tego rozwiązania uniemożliwia użycie wspomnianego wyżej modułu intarray .

mlpo
źródło
Jeśli mogą się przepełnić bigint, należy użyć ich numericjako typu do ich przechowywania. Jest o wiele wolniejszy i zajmuje znacznie więcej miejsca.
Craig Ringer
@CraigRinger Dlaczego warto korzystać, numerica nie ciąg znaków ( textna przykład)? Nie muszę wykonywać operacji matematycznych na moich sekwencjach.
mlpo
2
Ponieważ jest bardziej kompaktowy i pod wieloma względami szybszy niż text, i uniemożliwia przechowywanie fałszywych danych nienumerycznych. Zależy, jeśli wykonujesz tylko operacje we / wy, możesz chcieć, aby tekst ograniczył przetwarzanie operacji we / wy.
Craig Ringer
@CraigRinger Rzeczywiście, typ jest bardziej spójny. Jeśli chodzi o wydajność, przetestuję, kiedy znalazłem sposób na moje wyszukiwanie.
mlpo
2
@CraigRinger Może działać, jeśli kolejność nie ma znaczenia. Ale tutaj sekwencje są uporządkowane. Przykład: SELECT ARRAY[12, 4, 3, 17, 25, 377, 456, 25] @> ARRAY[12, 4, 3, 25, 377];zwróci true, ponieważ zamówienie nie jest uwzględniane przez tego operatora.
mlpo

Odpowiedzi:

3

Jeśli szukasz znaczących ulepszeń wydajności odpowiedzi dnoeth , rozważ użycie natywnej funkcji C i utworzenie odpowiedniego operatora.

Oto przykład tablic int4. ( Ogólny wariant tablicy i odpowiedni skrypt SQL ).

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

Teraz możesz filtrować takie wiersze.

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

Przeprowadziłem mały eksperyment, aby dowiedzieć się, o ile szybsze jest to rozwiązanie.

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"

Jest więc około 16 razy szybszy. Jeśli to nie wystarczy, możesz dodać obsługę indeksów GIN lub GiST, ale będzie to znacznie trudniejsze zadanie.

Slonopotamus
źródło
Brzmi interesująco, jednak używam albo ciągów znaków, albo typu, numericaby przedstawić moje dane, ponieważ mogą się przepełnić bigint. Może być dobrze edytować odpowiedź, aby dopasować ją do ograniczeń pytania. W każdym razie zrobię przedstawienie porównawcze, które opublikuję tutaj.
mlpo
Nie jestem pewien, czy dobrą praktyką jest wklejanie dużych bloków kodu do odpowiedzi, ponieważ powinny one być minimalne i weryfikowalne. Ogólna wersja tablicowa tej funkcji jest czterokrotnie dłuższa i dość kłopotliwa. Testowałem go również z, numerica textulepszenie wahało się od 20 do 50 razy, w zależności od długości macierzy.
Slonopotamus,
Tak, jednak konieczne jest, aby odpowiedzi zawierały odpowiedzi na pytania :-). Tutaj wydaje mi się, że odpowiedź zgodna z ograniczeniami jest interesująca (ponieważ ten aspekt jest częścią pytania). Niemniej jednak zaproponowanie wersji ogólnej może nie być konieczne. Po prostu wersja z ciągami znaków lub numeric.
mlpo
W każdym razie dodałem wersję dla tablic ogólnych, ponieważ byłaby ona prawie taka sama dla każdego typu danych o zmiennej długości. Ale jeśli naprawdę zależy Ci na wydajności, powinieneś pozostać przy typach danych o stałym rozmiarze, takich jak bigint.
Slonopotamus
Z przyjemnością bym to zrobił. Problem polega na tym, że niektóre moje sekwencje przepełniają się znacznie dalej bigint, więc wydaje się, że nie mam wyboru. Ale jeśli masz pomysł, jestem zainteresowany :).
mlpo
1

Możesz łatwo znaleźć podsekwencję, gdy rzucisz tablice na ciągi i zastąpisz nawiasy klamrowe przecinkami:

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

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

Zrób to samo dla tablicy, której szukasz, i dodaj wiodące i końcowe %:

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

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

Teraz porównujesz za pomocą LIKE:

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

Edytować:

Fiddle znów działa.

Jeśli tablice są znormalizowane w jednym wierszu na wartość, można zastosować logikę opartą na zestawie:

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

nmusi być sekwencyjny, bez duplikatów, bez przerw. Teraz przyłącz się do wspólnych wartości i wykorzystaj fakt, że sekwencje są sekwencyjne :-)

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;

Na koniec policz liczbę wierszy tym samym manekinem i sprawdź, czy jest to poprawna liczba:

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

Wypróbuj indeks sekwencji (val, id, n).

dnoeth
źródło
Później zastanawiałem się nad tym rozwiązaniem. Ale widzę kilka problemów, które wydają się dość uciążliwe: po pierwsze obawiam się, że to rozwiązanie jest bardzo nieefektywne, musimy rzucić każdą tablicę każdego wiersza przed wykonaniem wzorca wyszukiwania. Można rozważyć przechowywanie sekwencji w TEXTpolu ( varcharmoim zdaniem zły pomysł, sekwencje mogą być długie, ponieważ liczby, więc rozmiar jest raczej nieprzewidywalny), aby uniknąć rzucania; ale nadal nie jest możliwe użycie indeksów w celu poprawy wydajności (ponadto użycie pola ciągu niekoniecznie wydaje się rozsądne, patrz komentarz @CraigRinger powyżej).
mlpo
@mlpo: Jakie są Twoje oczekiwania dotyczące wydajności? Aby móc korzystać z indeksu, należy znormalizować sekwencję w jednym wierszu na wartość, zastosować podział relacyjny i na końcu sprawdzić, czy kolejność jest poprawna. W twoim przykładzie 25istnieje dwa razy id=4, czy to faktycznie jest możliwe? Ile dopasowań istnieje w średniej / maksimum dla szukanej sekwencji?
dnoeth
Sekwencja może zawierać kilka razy tę samą liczbę. Na przykład {1, 1, 1, 1, 12, 2, 2, 12, 12, 1, 1, 5, 4}jest całkiem możliwe. Jeśli chodzi o liczbę dopasowań, zwykle uważa się, że użyte podsekwencje ograniczają liczbę wyników. Jednak niektóre sekwencje są bardzo podobne i czasami interesujące może być użycie krótszej sekwencji, aby uzyskać więcej wyników. Szacuję, że liczba dopasowań w większości przypadków wynosi od 0 do 100. Zawsze istnieje możliwość, że czasami podsekwencja pasuje do wielu sekwencji, gdy jest krótka lub bardzo powszechna.
mlpo
@mlpo: Dodałem rozwiązanie oparte na zestawie i byłbym bardzo zainteresowany porównaniem wydajności :-)
dnoeth
@ypercube: To był tylko szybki dodatek, aby zwrócić bardziej znaczący wynik :-) Ok, to okropne, zmienię to. l
dnoeth