napisałem ostatnio o kolejnych testach jakie robili kolesie z tweakers.net.
bluszcz wtedy skomentował, że chciałby zobaczyć testy postgresa z soliddb lub choćby falconem, a nie z kiepskawym innodb.
prosił i ma 🙂 blog mysql performance przeprowadził testy innodb, myisam i falcona. właśnie pod kątem skalowalności. efekt – ogólna, praktycznie całkowita porażka falcona.
przykłady wykres wyników jednego z testów wygląda tak:

przy czym uwaga: nie wybrałem takiego na którym falcon wyszedł najgorzej. są takie wykresy gdzie linia od wydajności falcona "leży" na osi.
do tego dochodzi jeszcze takie jedno zdanie:
"… Falcon cannot handle LIMIT properly …" (wyjęte z kontekstu, ale sens niezmieniony).
czekam teraz aż ktoś pokaże testy z soliddb. wtedy też na pewno ja zaprezentuję.

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.