drzewa w sql’u – wstęp

jakiś czas temu zainteresowała mnie metoda przechowywania wszelkiego rodzaju struktur drzewiastych w bazach danych.
dla wyjaśnienia – struktura drzewiasta jest to taki uporządkowany zbiór danych gdzie każdy element ma swój element nadrzędny, chyba, że jest elementem najwyższego rzędu.
dając przykłady z życia – drzewami są opisane wszelkiego rodzaju hierarchie – służbowe, kategorie (np. w sklepie internetowym), różnego rodzaju podziały. drzewami są też wiadomości na forach dyskusyjnych – a dokładniej – w drzewa są poukładane wątki z tych wiadomości.
ogólnie – struktury drzewiaste mają sporo zastosowań.
z tego powodu stały się one obiektem mojego zainteresowania, testów i badań. o struktury drzewiaste pytam potencjalnych pracowników na rozmowie kwalifikacyjnej.
w czasie swojej pracy z "drzewami" wyodrębniłem kilka metod które kiedyś już opisałem (link do http://www.dbf.pl/faq/tresc.html?rozdzial=1#o1_9), ale tu postaram się opisać je dokładniej i podając przy okazji wyniki pewnych testów na wydajność.
ze względu na obfitość materiału tekst ten podzielę na kilka wpisów: wstęp (to co czytacie), następnie po jednym wpisie na każdą z opisywanych metod, potem jakieś podsumowanie i na koniec kilka uwag praktycznych do wybranej przeze mnie metody.
ponieważ testowanie wydajności powinno odbywać się na sporych zestawach danych, a jednocześnie pokazywanie "o co mi chodzi" powinno być na możliwie małych ilościach – na potrzeby tego tematu przygotowałem 2 zupełnie różne zestawy danych:

1. małe drzewko w celach dydaktycznych:

to drzewko, zgodnie z konwencjami stosowanymi w tym dokumencie, ma następujące elementy:

  • sql
  • sql.oracle
  • sql.oracle.linux
  • sql.oracle.linux.glibc2
  • sql.oracle.linux.glibc1
  • sql.oracle.solaris
  • sql.oracle.windows
  • sql.postgresql
  • sql.postgresql.linux

2. spory zestaw danych  pobrany z katalogu dmoz – lista kategorii

dane z dmoza poddałem obróbce usuwając z nich znaki spoza zestawu A-Za-z0-9_, i ustawiając separator elementów drzewa na ".".
powstała lista elementów ma 478,870 elementów.
ścieżki z dmoz zawierają od 3 do 247 znaków, największe zagłębienie w drzewo jest w elemencie Regional.North_America.United_States.New_York.Localities.N.New_York_City.Brooklyn.Society_and_Culture.Religion.Christianity.Catholicism.Eastern_Rites.Maronite

w celu porównania wydajności różnych metod zapisu drzew będę testował następujące scenariusze testowe:

  1. pobranie listy elementów głównych (top-levelowych)
  2. pobranie elementu bezpośrednio "nad" podanym elementem
  3. pobranie listy elementów bezpośrednio "pod" podanym elementem
  4. pobranie listy wszystkich elementów "nad" danym elementem (wylosowanym)
  5. pobranie listy wszystkich elementów "pod" danym elementem (wylosowanym)
  6. sprawdzenie czy dany element jest "liściem" (czy ma pod-elementy)
  7. pobranie głównego elementu w tej gałęzi drzewa w której znajduje się dany (wylosowany) element

dodatkowo zostanie sprawdzona wielkość tabel i indeksów na założonej strukturze danych.

dla porównania – zapis w postaci takiej jak w pliku źródłowym zajmuje:
– tabela dmoz: 57,319,424 bajtów
– index pkey: 8,609,792 bajtów
– unikalny indeks ścieżki: 51,888,128 bajtów

tak więc – w ciągu najbliższego czasu będę pokazywał kolejne metody oraz wyniki ich testów.

dead space map

na postgresową listę patches został wysłany interesujący patch.
na razie nie wiadomo czy wejdzie do 8.3, czy może nie, na pewno nie jest jeszcze kompletny.
co robi?
panowie z ntt (taka japońska firma telekomunikacyjna) napisali obsługę dead space map. w skrócie – postgres ma przechowywać informację które ze stron danych w plikach wymagają vacuumowania, a które nie. dzięki temu nie trzeba będzie vacuumować np. całej tabeli a tylko te strony które uległy modyfikacji. ma to kolosalnie przyspieszyć vacuumowanie tabel które są spore, ale odbywa się na nich relatywnie mało update'ów i delete'ów. suuuuper! oby weszło do 8.3.

sun cluster obsługuje postgresa!

jak donosi devrim, wersja 3.2 oprogramowania sun cluster obsługuje klastrowanie postgresql'a – a przynajmniej zestawianie par active/passive przy pomocy dzielonej macierzy dyskowej. nie jest to w sumie nic ultra-przełomowego, ale dobrze wiedzieć, że sun dodaje obsługę postgresa do swoich narzędzi.

wordpress na postgresie

jak może wiecie wordpress od zawsze był na mysql'u.
dodatkowo – team wordpressa nigdy nie wykazał się chęcią modyfikacji kodu aby działał na innych platformach bazodanowych – w szczególności na postgresie. a byli pytani/proszeni przez ludzi z okolic core-teamu postgresa!
ostatnio przeczytałem na blogu drixtera, że aure zrobił nieoficjalny port wordpressa na postgresa. i to nie jakąś prehistoryczną wersję tylko 2.0.4! tak więc – zachęcam do testowania 🙂

tsearch poza contribem. w core’rze

rosyjski team (oleg i teodor) przysłał pierwszą wersję patcha przenoszącego tsearcha do podstawowego postgresa.
zmiana nie jest wielka – funkcjonalność pozostaje ta sama, ale przyjemniej się teraz konfiguruje, używa – no i nie trzeba sprawdzać czy contriby są poinstalowane 🙂
zmiany:

  • tabele pg_ts_* są teraz w schemie pg_catalog. wreszcie!
  • parsery, słowniki i konfiguracje są teraz częścią systemu postgresa – tak jak tabele, klasy operatorów itd. dzięki czemu są przyporządkowane do schemy – można mieć różne w różnych schemach – np. wybór różnych parserów przez autodetekcję locale – zależny od schemy!
  • wybór aktualnej konfiguracji tsearcha odbywa się przez ustawienie zmiennej postgresa (czyli tak jak np. shared_buffers czy inne)
  • zarządzanie konfiguracją tsearcha odbywa się teraz z użyciem poleceń sql'a (create i pochodne) a nie wyrażeń insert/update/delete. pozwala to na lepszą obsługę dumpów, tworzenia, kasowania i zarządzania zależnościami
  • psql umożliwi wyświetlanie konfiguracji systemu fts poprzez polecenia \d* (\dF dokładniej)
  • dodane z automatu wszystkie dostępne stemmery snowball'owe, oraz ich odpowiednie konfiguracje
  • poprawki związane ze zwalnianiem pamięci

ogólnie – krok w dobrą stronę.
patch jest na razie w wersji alfa, ale myślę, że do 8.3 wejdzie na pewno.
można już się zapoznać z aktualizowaną na bieżąco dokumentacją – na razie na stronach olega i teodora, ale już niedługo w standardowych doc'ach postgresa.
aha. informacyjnie – prace nad wdrożeniem tsearcha do core'a są sponsorowane przez enterprisedb – producenta wersji postgresql'a zmodyfikowanej w celu zachowania wiekszej kompatybilnosci z oracle'em.

enum

na grupie pgsql-patches trwa dyskusja nad nową wersją patcha dodającego enumy.
jest kilka argumentów przeciwko enumom jako takim, kilka przeciwko temu konkretnie patchowi i całkiem sporo za tym aby enumy tym patchem włączyć do postgresa!.
wszystko wskazuje na to, że w nowym postgresie (8.3?) będzie można:

CREATE TYPE mood AS ENUM ('sad', 'ok', 'happy');
CREATE TABLE person (
    name text,
    current_mood mood
);
INSERT INTO person VALUES ('Moe', 'happy');
SELECT * FROM person WHERE current_mood = 'happy';
 name | current_mood
------+--------------
 Moe  | happy
(1 row)

fajnie 🙂

jak dodać kolumnę do tabeli

teoretycznie dodanie kolumny do tabeli nie jest problemem. od daaaaaaaaaaaaaawna istnieje ALTER TABLE ADD COLUMN. czy jednak jest to zawsze bezproblemowe?
niestety nie.
otóż – dodanie pola do tabeli zakłada na nią (w całości) exclusive locka.
dla standardowego:

ALTER TABLE t ADD COLUMN c INT8;

to nie problem – taki ALTER trwa moment.
ale co jeśli robimy:

ALTER TABLE t ADD COLUMN c INT8 NOT NULL DEFAULT 123;

tu pojawia się problem.
po pierwsze – not null – wymusza sprawdzenie zawartości bazy.
po drugie – ważniejsze – wyspecyfikowanie "default" przy dodawaniu pola automatycznie wstawi wartość domyślną do wszystkich rekordów obecnie w tabeli.
zasadniczo – super. o to chodzi. ale jak sobie nałożymy na to fakt iż ALTER TABLE lockuje tabelę – oops. recepta na kłopoty.
w szczególności – mając tabelę typu kilka milionów rekordów, na której non stop ktoś pracuje (np. dosyć aktywny serwis www) – zrobienie na niej takiego ALTERa to realnie sprawę ujmując wyłączenie ta
beli i serwisu.
jak więc zrobić dodanie z wyspecyfikowaniem w sposób słuszny?
no cóż – trzeba robić to krokami:
po pierwsze:

ALTER TABLE t ADD COLUMN c INT8;

to się wykona błyskawicznie.
potem (ale jako oddzielne zapytanie!):

ALTER TABLE t ALTER COLUMN c SET DEFAULT 123;

to też pójdzie szybko bo niczego nam nie zaktualizuje. po prostu – nowo wstawiane rekordy będą miały defaulta.
teraz – trzeba zaktualizować starsze. najprościej:

UPDATE t SET c = 123 WHERE c IS NULL;

w szczególności – jak danych jest więcej niż mało (powiedzmy powyżej 100,000 rekordów), to warto rozbić to na kilka oddzielnych zapytań. np:

UPDATE t SET c = 123 WHERE c IS NULL AND id BETWEEN 1 AND 100000;
UPDATE t SET c = 123 WHERE c IS NULL AND id BETWEEN 100001 AND 200000;

itd.
oczywiście – nie można do tego celu użyć funkcji – cała idea tego rozbijania polega na tym by nie robić tego wszystkiego w jednej, olbrzymiej, transakcji!.
no i na koniec pozostaje:

ALTER TABLE t ALTER COLUMN c SET NOT NULL;

to chwilę potrwa – postgres musi sprawdzić dane, ale i tak jest to krótsze i mniej blokujęce niż robienie wszystkiego za jednym zamachem.
oczywiście w tej chwili ktoś może się odezwać i powiedzieć, że w bazie <xxx> to jest prostsze, nie trzeba nic rozbijać, bla bla bla. fakt. w postgresie też nie trzeba – to co pokazałem to jedynie hint jak obejść blokadę przy dodawaniu pól z wartościami domyślnymi przy sporych tabelkach. można to zrobić jednym zapytaniem. i też zadziała. po prostu czasem nie chcemy/nie możemy mieć locka na taki czas jaki jest potrzebny ALTERowi 🙂

tsearch i synonimy

od daaaaawna w postgresie jest dostępny świetny silnik wyszukiwania pełnotekstowego – tsearch.
ma on spore możliwości, ale jest dosyć trudny przy pierwszym podejściu – trzeba poświęcić z pół godziny na to by załapać o co chodzi, skonfigurować i używać.
natomiast jak już się zrozumie co i jak – można prosto robić nowe, ciekawe rzeczy. przykładowo – dodać własne słowniki synonimów. dokładną metodę zrobienia takiego słownika i dodania go do systemu wyszukującego przedstawił w swoim blogu magnus hagander – ja to przeczytałem i polecam każdemu kto chce zobaczyć jak zrobić ciekawe rzeczy w postgresie.

currval i problemy z selectami

jak może wiecie w postgresie jest funkcja currval() zwracająca ostatnio nadane id z podanej sekwencji.

rozpatrzmy prosty przypadek:

# create table test (id serial primary key, pole int4);
CREATE TABLE
# insert into test (pole) select * from generate_series(1, 10000);
INSERT 0 10000
# select count(*) from test;
 count
-------
 10000
(1 row)
# select currval('test_id_seq');
 currval
---------
   10000
(1 row)

wszystko wygląda ok. więc sprawdźmy jeszcze jeden insert mały:

# insert into test(pole) values (12313);
INSERT 0 1
# select currval('test_id_seq');
 currval
---------
   10001
(1 row)

nadal wszystko ok. i teraz:

# select * from test where id = currval('test_id_seq');
  id   | pole
-------+-------
 10001 | 12313
(1 row)
Time: 93.358 ms

działa, ale coś wolno, sprawdźmy:

# explain analyze select * from test where id = currval('test_id_seq');
                                            QUERY PLAN
--------------------------------------------------------------------------------------------------
 Seq Scan on test  (cost=0.00..200.02 rows=1 width=8) (actual time=64.375..64.379 rows=1 loops=1)
   Filter: (id = currval('test_id_seq'::regclass))
 Total runtime: 64.431 ms
(3 rows)

seq scan? sprawdźmy więc ręcznie podaną wartość:

# explain analyze select * from test where id = 10001;
                                                   QUERY PLAN
----------------------------------------------------------------------------------------------------------------
 Index Scan using test_pkey on test  (cost=0.00..8.02 rows=1 width=8) (actual time=0.029..0.033 rows=1 loops=1)
   Index Cond: (id = 10001)
 Total runtime: 0.086 ms
(3 rows)

hmm .. tu jest dobrze. skąd seq scan? aby nie przynudzać z każdym zapytaniem, powiem tyle, że nie jest to kwestia błędnych typów czy czegoś tak oczywistego. problemem jest zmienność funkcji.

dokładniej: funkcja currval() jest zadeklarowana jako “volatile" – co oznacza, że jej wynik ma prawo zmienić się w czasie pojedynczego skanu tabeli. tak jak np. random(). to oznacza, że nie można użyć jej jako dostarczyciela wartości i potem tą wartością przeszukać indeksy.

cóż więc można zrobić – no cóż. trzeba powiedzieć postgresowi, że interesuje nas tylko pierwsza zwrócona wartość currvala – idealnie do tego nadają się podzapytania:

# explain analyze select * from test where id = (select currval('test_id_seq'));
                                                   QUERY PLAN
----------------------------------------------------------------------------------------------------------------
 Index Scan using test_pkey on test  (cost=0.01..8.03 rows=1 width=8) (actual time=0.047..0.050 rows=1 loops=1)
   Index Cond: (id = $0)
   InitPlan
     ->  Result  (cost=0.00..0.01 rows=1 width=0) (actual time=0.010..0.012 rows=1 loops=1)
 Total runtime: 0.187 ms
(5 rows)

jak widać jest już zdecydowanie lepiej.

ile jest wart postgres

dziś jest dzień postgresql'owy, więc kolejna informacja o nim.

jest taki program: sloccount. służy do liczenia ilości linii kodu, oraz estymowaniu kosztów stworzenia programu.

odpaliłem go na źródłach postgresa 8.2. oto wynik:

Totals grouped by language (dominant language first):
ansic:       479298 (94.01%)
yacc:         14698 (2.88%)
sh:            7805 (1.53%)
lex:           5349 (1.05%)
perl:          2608 (0.51%)
asm:             65 (0.01%)
python:          12 (0.00%)
<br/>
Total Physical Source Lines of Code (SLOC)                = 509,835
Development Effort Estimate, Person-Years (Person-Months) = 139.26 (1,671.14)
 (Basic COCOMO model, Person-Months = 2.4 * (KSLOC**1.05))
Schedule Estimate, Years (Months)                         = 3.50 (41.95)
 (Basic COCOMO model, Months = 2.5 * (person-months**0.38))
Estimated Average Number of Developers (Effort/Schedule)  = 39.84
Total Estimated Cost to Develop                           = $ 18,812,337
 (average salary = $56,286/year, overhead = 2.40).
SLOCCount, Copyright (C) 2001-2004 David A. Wheeler
SLOCCount is Open Source Software/Free Software, licensed under the GNU GPL.
SLOCCount comes with ABSOLUTELY NO WARRANTY, and you are welcome to
redistribute it under certain conditions as specified by the GNU GPL license;
see the documentation for details.
Please credit this data as "generated using David A. Wheeler's 'SLOCCount'."