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 sequence
pole 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ą unnest
funkcji 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ą subarray
funkcji 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 .
bigint
, należy użyć ichnumeric
jako typu do ich przechowywania. Jest o wiele wolniejszy i zajmuje znacznie więcej miejsca.numeric
a nie ciąg znaków (text
na przykład)? Nie muszę wykonywać operacji matematycznych na moich sekwencjach.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.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.Odpowiedzi:
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 ).
Teraz możesz filtrować takie wiersze.
Przeprowadziłem mały eksperyment, aby dowiedzieć się, o ile szybsze jest to rozwiązanie.
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.
źródło
numeric
aby 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.numeric
atext
ulepszenie wahało się od 20 do 50 razy, w zależności od długości macierzy.numeric
.bigint
.bigint
, więc wydaje się, że nie mam wyboru. Ale jeśli masz pomysł, jestem zainteresowany :).Możesz łatwo znaleźć podsekwencję, gdy rzucisz tablice na ciągi i zastąpisz nawiasy klamrowe przecinkami:
Zrób to samo dla tablicy, której szukasz, i dodaj wiodące i końcowe
%
:Teraz porównujesz za pomocą
LIKE
:Edytować:
Fiddle znów działa.
Jeśli tablice są znormalizowane w jednym wierszu na wartość, można zastosować logikę opartą na zestawie:
n
musi być sekwencyjny, bez duplikatów, bez przerw. Teraz przyłącz się do wspólnych wartości i wykorzystaj fakt, że sekwencje są sekwencyjne :-)Na koniec policz liczbę wierszy tym samym manekinem i sprawdź, czy jest to poprawna liczba:
Wypróbuj indeks sekwencji (val, id, n).
źródło
TEXT
polu (varchar
moim 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).25
istnieje dwa razyid=4
, czy to faktycznie jest możliwe? Ile dopasowań istnieje w średniej / maksimum dla szukanej sekwencji?{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.