za tydzień, w sobotę, 13 stycznia adam buraczewski wygłosi wykład nt. "słonie pracują w stadzie".
tematyka obejmie wszystkie liczące się metody klastrowania postgresa: slony, pgpool, dblink, sequoia, postgres-r i inne.
wykład odbędzie się w gliwicach – jeśli będziecie w pobliżu – polecam. temat ciekawy, a adam ma kolosalną wiedzę. i umiejętność jej przekazania.

jest to zdecydowanie najbardziej rozpowszechniona metoda przechowywania drzew w bazach.
zakłada ona (zgodnie z naszymy podstawowymi założeniami), że każdy element ma tylko 1 element nadrzędny (lub go nie ma – gdy jest to element główny). dzięki temu całość można zapisać w jednej tabeli
:

$ CREATE TABLE categories (
    id        BIGSERIAL,
    parent_id INT8 REFERENCES categories (id),
    codename  TEXT NOT NULL DEFAULT '',
    PRIMARY KEY (id)
);
CREATE UNIQUE INDEX ui_categories_picn ON categories (parent_id, codename);

nasze testowe drzewo w tej tabeli będzie wyglądało tak:

# SELECT * FROM categories;
 id | parent_id |  codename
----+-----------+------------
  1 |    [null] | sql
  2 |         1 | postgresql
  3 |         1 | oracle
  4 |         2 | linux
  5 |         3 | solaris
  6 |         3 | linux
  7 |         3 | windows
  8 |         6 | glibc1
  9 |         6 | glibc2
(9 rows)

jak widać – same podstawowe danych, jedna tabelka, mała nadmiarowość. wygląda ok. a jak to odpytać?

1. pobranie listy elementów głównych (top-levelowych)

> SELECT * FROM categories where parent_id is null;

2. pobranie elementu bezpośrednio “nad" podanym elementem
dane wejściowe:

• ID : id elementu

SELECT p.* FROM categories c JOIN categories p ON c.parent_id = p.id WHERE c.id = [ID];

jeśli zapytanie nic nie zwróci – znaczy to, że dany element był “top-levelowy".

3. pobranie listy elementów bezpośrednio “pod" podanym elementem
dane wejściowe:

• ID : id elementu

> SELECT * FROM categories WHERE parent_id = [ID];

4. pobranie listy wszystkich elementów “nad" danym elementem (wylosowanym)
dane wejściowe:

• ID : id elementu

tu pojawia się problem. można to rozwiązać selectem z dużą ilością joinów (tyle joinów ile poziomów kategorii jest powyżej naszego elementu), albo zastosować rozwiązanie algorytmiczne:

1. pobierz dane dla aktualnego elementu: SELECT * FROM categories WHERE id = [ID];
2. jeśli parent_id dla aktualnego elementu jest inny niż NULL wykonaj:
   1. SELECT * FROM categories WHERE id = [aktualny.parent_id]
   2. ustaw aktualny na właśnie pobrany

jest to rozwiązanie typu z wieloma zapytaniami, ale rozwiązanie z joinami ma wszystkie wady zapytań z “metody wielu tabel" (nota bene tam też można było zastosować podejście algorytmiczne, realizowane w aplikacji klienckiej)

5. pobranie listy wszystkich elementów “pod" danym elementem (wylosowanym)
dane wejściowe:

• ID : id elementu

niestety – i tym razem zapisanie tego w postaci pojedynczego zapytania będzie problematyczne. w tym przypadku należy zastosować rozwiązanie rekurencyjne:

1. pobierz listę wszystkich elementów bezpośrednio pod podanym elementem (vide punkt 3)
2. dla każdego z elementów powtórz powyższy punkt
3. powtarzaj tak długo aż dojdziesz do sytuacji gdy już nie ma elementów poniżej.

6. sprawdzenie czy dany element jest “liściem" (czy ma pod-elementy)
dane wejściowe:

• ID : id elementu

>SELECT count(*) from categories WHERE parent_id = [ID];

jeśli zwróci 0 – to dany element jest liściem.

7. pobranie głównego elementu w tej gałęzi drzewa w której znajduje się dany (wylosowany) element

• ID : id elementu

niestety – jedyną słuszną metodą jest użycie algorytmu z punktu 4 i pobranie ostatniego elementu (takiego dla którego algorytm się kończy, bo parent_id jest NULLem.

podstawową zaletą tego rozwiązania jest to, że stała struktura tabel jest w stanie przechowywać dowolną ilość danych w drzewie – niezależnie od ilości elementów czy poziomów zagłębień.
wadami jest głównie konieczność korzystania z pewnych rozwiązań algorytmicznych zamiast użycia zapytań bazodanowych.

część z was pewnie kiedyś zaprojektowała system gdzie był przechowywany numer nip.
numer nip jaki jest każdy wie – 10 cyfr, rozdzielonych myślnikami. zasadniczo – myślniki są nieważne. ale czasem ktoś (klient, urząd skarbowy, ktokolwiek) czepia się jak mu się np. nip zmieni z 522-186-96-44 na 522-18-69-644. niby ten sam. ale nie taki sam.
z tego powodu nip powinno się przechowywać w postaci takiej jak user podał.
ale – czy wyszukując nip mamy pewność, że wiemy w jakiej postaci "myślnikowej" dane są wpisane? a co jeśli mamy wpisane "522-186-96-44", a szukamy "522-18-69-644"?
czyli do wyszukiwania przydałoby się aby pamiętać bez myślników.
najprostszą wersją jest zrobienie dwóch kolumn: nip_original, nip_search. ale to jest brzydkie.
ładniej można zrobić to poprzez np. coś takiego:
mamy tabelkę:

create table test (id serial primary key, nip text not null, nazwa text not null);

i na niej zakładamy indeks w ten sposób:

create unique index test_idx on test (regexp_replace(nip, '[^0-9]', '', 'g'));

po czym sprawdzamy:

# explain analyze select * from test where regexp_replace(nip, '[^0-9]', '', 'g') = '1234567890';
                                                   QUERY PLAN
----------------------------------------------------------------------------------------------------------------
 Index Scan using test_idx on test  (cost=0.00..8.29 rows=1 width=54) (actual time=0.167..0.167 rows=0 loops=1)
   Index Cond: (regexp_replace(nip, '[^0-9]'::text, ''::text, 'g'::text) = '1234567890'::text)
 Total runtime: 0.261 ms
(3 rows)

super.
teraz .. dobrze by było jakby dało się wyszukiwać prefixowo – aby np. w aplikacji się "podpowiadało" samo – po wpisaniu kolejnych cyfr.
aby to zrobić musimy sięgnąć po tzw. index opclass (uwaga – to jest konieczne tylko jeśli wasze locale jest inne niż C – ale pewnie jest inne):

drop index test_idx;
create unique index test_idx on test (regexp_replace(nip, '[^0-9]', '', 'g') text_pattern_ops);

no i test:

# explain analyze select * from test where regexp_replace(nip, '[^0-9]', '', 'g') like '1234%';
                                                                                     QUERY PLAN
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 Bitmap Heap Scan on test  (cost=13.40..922.28 rows=500 width=54) (actual time=0.240..0.457 rows=7 loops=1)
   Filter: (regexp_replace(nip, '[^0-9]'::text, ''::text, 'g'::text) ~~ '1234%'::text)
   ->  Bitmap Index Scan on test_idx  (cost=0.00..13.27 rows=500 width=0) (actual time=0.162..0.162 rows=7 oops=1)
         Index Cond: ((regexp_replace(nip, '[^0-9]'::text, ''::text, 'g'::text) ~>=~ 1234'::text) AND (regexp_replace(nip, '[^0-9]'::text, ''::text, 'g'::text) ~<~ '1235'::text))
 Total runtime: 0.593 ms
(5 rows)

wow.
co prawda trzeba za każdym razem pisać tego regexp_replace'a.
czy na pewno trzeba? nie. wystarczy zrobić wrappera widokiem:

# create view test_view as select *, regexp_replace(nip, '[^0-9]', '', 'g') as search_nip from test;

i potem:

# explain analyze select * from test_view where search_nip like '123%';
                                                                                    QUERY PLAN
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 Bitmap Heap Scan on test  (cost=13.40..923.53 rows=500 width=54) (actual time=0.375..7.384 rows=96 loops=1)
   Filter: (regexp_replace(nip, '[^0-9]'::text, ''::text, 'g'::text) ~~ '123%'::text)
   ->  Bitmap Index Scan on test_idx  (cost=0.00..13.27 rows=500 width=0) (actual time=0.199..0.199 rows=96 loops=1)
         Index Cond: ((regexp_replace(nip, '[^0-9]'::text, ''::text, 'g'::text) ~>=~ '123'::text) AND (regexp_replace(nip, '[^0-9]'::text, ''::text, 'g'::text) ~<~ '124'::text))
 Total runtime: 88.251 ms

super. działa. wyszukuje niezależnie od minusów, dane trzymamy tylko raz, mamy searcha prefixowego. czego chcieć więcej?