Wpisy z kategorii 'sql'

Podzapytania w INSERT

Napisano wrzesień 3, 2009 * Komentarze (0)

Taki typowy problem: tabela zawierająca pole, pozwalające użytkownikowi na dowolne ustalanie kolejności rekordów. Prawie każda aplikacja ma coś tego typu. W jednej z moich aplikacji była to płaska lista kategorii:

  1. CREATE TABLE kategorie (
  2. id INT NOT NULL AUTO_INCREMENT,
  3. nazwa VARCHAR(255),
  4. position INT,
  5. PRIMARY KEY(id));

Dodanie rekordu do tej tablicy ma domyślnie umieścić go na końcu listy. Często spotykanym (i bardzo kiepskim) rozwiązaniem jest użycie dwóch zapytań: SELECT, który odczytuje aktualną wartość pola position oraz INSERT, który dodaje nowy rekord. A czy da się to zrobić jednym zapytaniem? Pierwszy pomysł jest następujący:

  1. INSERT INTO kategorie(nazwa, position) VALUES (
  2. :nazwa, (SELECT IFNULL(MAX(position) + 1, 1) FROM kategorie)
  3. )

Fajny pomysł, prawda? Ma tylko tą drobną wadę, że nie działa.. próba jego uruchomienia skończy się komunikatem:

#1093 - You can't specify target table 'kategorie' for update in FROM clause

Jak to obejść? Najlepiej podzapytaniem:

  1. INSERT INTO kategorie(nazwa, position) VALUES (
  2. :nazwa, (
  3. SELECT IFNULL(x, 1) FROM (SELECT MAX(position)+1 AS x FROM kategorie) AS subQuery
  4. ))

Ładnie, prawda? Opakowanie podzapytania w następne podzapytanie rozwiązuje zadanie. Niestety - tylko dla MySQL w wersji 5.0+. Użycie go na serwerze 4.1 kończy się tym samym komunikatem, co poprzednie… Szczerze mówiąc - nie chciało mi się kombinować. Spłodziłem coś takiego:

  1. INSERT INTO kategorie(nazwa, position) VALUES (:nazwa, 0);
  2. UPDATE kategorie
  3. INNER JOIN (SELECT MAX(position)+1 AS x FROM kategorie) AS subQuery
  4. SET position = x
  5. WHERE position = 0;

Proste? Proste.

Obsługa drzew w SQL - część 2 - Model ścieżki zmaterializowanej

Napisano lipiec 15, 2009 * Komentarze (0)

W poprzednim wpisie pokazałem typowe podejście do zagadnienia drzew w SQL (notabene: nazywa się on modelem sąsiedztwa), omówiłem też jego podstawowe wady (i zalety) i obiecałem opisać inne podejście - pozbawione wad modelu sąsiedztwa.
Drzewiasta struktura danych
Jeśli przyjrzysz się przykładowemu drzewu, który chcemy zapisać w bazie danych, można zauważyć, że położenie w drzewie można także opisać jako listę wszystkich węzłów nadrzęnych danego węzła. Taka lista nosi nazwę “ścieżki”, i zapisuje się ją licząc od najstarszego rodzica aż po bieżący węzeł. Przykładowo, ścieżka dla węzła “4″ ma postać: “1,2,4″, a dla węzła “11″ - “1,3,10,11″. Dodatkowo, przyda się kolumna informująca, na jakim poziomie znajduje się dany węzeł względem początku drzewa (teoretycznie można tą informację wyciągnąć z długości ścieżki - ale takie zadanie jest, niestety, nierelacyjne, a co za tym idzie - bardzo obciążające dla bazy)

W bazie danych może to wyglądać tak:

table tree_mpath:
id	mpath	level	data
1	1	0	...
2	1,2	1	...
3	1,3	1	...
4	1,2,4	2	...
5	1,2,4,5	3	...
6	1,2,4,6	3	...
7	1,2,7	2	...
itd.

Co daje taki zapis? Przede wszystkim, pozwala z łatwością, pojedynczym zapytaniem, pobieramy fragmenty drzewa:

  1. SELECT id, mpath, level, DATA FROM tree_mpath
  2. WHERE FIND_IN_SET(id, (SELECT mpath FROM tree_mpath WHERE id = 4))
  3. ORDER BY level;

zwróci:

id	mpath	level	data
1	1	0	...
2	1,2	1	...
4	1,2,4	2	...

czyli wszystkie elementy nadrzędne węzła 4 (wraz z tym węzłem, co akurat łatwo wyfiltrować).

Do pobierania elementów podrzędnych węzła możemy użyć zapytania:

  1. SELECT id, mpath, level, DATA FROM tree_mpath
  2. WHERE mpath LIKE (SELECT CONCAT(mpath, '%') FROM tree_mpath WHERE id = 4)
  3. ORDER BY level

które w wyniku da nam:

id	mpath	level	data
4	1,2,4	2	...
5	1,2,4,5	3	...
6	1,2,4,6	3	...

Pobieranie fragmentu drzewa też nie jest trudne: powiedzmy, że chcemy pobrać tylko bezpośrednich potomków węzła o id = 2:

  1. SELECT id, mpath, level, DATA FROM tree_mpath
  2. WHERE mpath LIKE (SELECT CONCAT(mpath, '%') FROM tree_mpath WHERE id = 2)
  3. AND level = (SELECT level+1 FROM tree_mpath WHERE id = 2)

i w efekcie dostaniemy:

id	mpath	level	data
4	1,2,4	2	...
7	1,2,7	2	...

Jak widać - zalety tego modelu są znaczne. Praktycznie dowolny fragment drzewa można czytać pojedynczym zapytaniem, zarówno “w górę” jak i “w dół” od wskazanego węzła. Oczywiście, dla sprawnego działania na taką tabelę należy nałożyć odpowiednie indeksy: na pole id (to chyba oczywiste), mpath oraz level.

Jakie są wady tego modelu?

1. Wysoki koszt aktualizacji. O ile dodanie nowego rekordu jest całkiem znośne, usunięcie również jest całkiem szybkie (choć wymaga dość złożonych warunków, podobnych do tych używanych w zapytaniach SELECT), to przesuwanie węzła w inne miejsce w drzewie jest drogą przez mękę: nie dość, że trzeba zaktualizować przesuwany rekord, to należy też zmodyfikować wszystkie jego węzły potomne. Biorąc pod uwagę, że aktualizacji podlegają indeksy, narzut czasowy jest poważny.

2. Spójność danych. Konstrukcja tabeli nie pozwala na używanie kaskad przy usuwaniu rekordu. W efekcie błąd może doprowadzić do powstania węzłów-zombie, nie powiązanych z pozostałą strukturą drzewa.

3. Ograniczenia wielkości. Jeśli pole mpath będzie polem typu VARCHAR, trzeba pamiętać, że maksymalna długość tego pola to 255 bajtów. Jeżeli identyfikatory kategorii będą 3-znakowe (100-999), to każdy poziom zagłębienia będzie zabierał 4 bajty (identyfikator + przecinek), co daje maksymalny poziom zagłębienia ok. 60. Przy identyfikatorach 4 znakowych (1000-9999), maksymalny poziom zagłębienia to ok. 50. Przy dłuższych identyfikatorach (np. 36-bajtowy uu_id z MS SQL Server) maksymalna wielkość drzewa drastycznie spada (6 poziomów dla uu_id).

Zmiana typu mpath na TEXT rozwiązuje ten problem, ale może się pojawić problem z indeksowaniem takiego pola - np. MySQL nie pozwala na zakładanie indeksów na pole TEXT w InnoDB.

4. Normalizacja. Konstrukcja pola mpath łamie postać normalną tabeli. Zawartość pola level jest wprost powiązany z zawartością pola mpath (level ma wartość “długość ścieżki - 1″), i teoretycznie mógłaby zostać pominięta.

Istnieje rozwiązanie problemów 2-4 - nazywa się znormalizowanym modelem ścieżki zmaterializowanej. Ale o tym innym razem…

Obsługa drzew w SQL - część 1

Napisano czerwiec 4, 2009 * Komentarze (3)

Praktycznie w każdym projekcie informatycznym (a w e-commerce w szczególności)  pojawiają sie jakieś struktury drzewiaste. Ich zapisywanie do bazy danych stanowi problem, ponieważ tabele baz danych są przystosowane do zapisu ‘liniowego’ a nie drzewiastego.

Załóżmy, że mam taką strukturę drzewa (cyferki oznaczają identyfikatory węzłów):

Drzewiasta struktura danych

Najczęściej używaną strukturą jest wstawianie do rekordu potomnego klucza obcego wskazującego na rekord-rodzic bieżącego rekordu. Tabela tree będzie zawierała następujące dane:

id	parent_id		data
1 	NULL 		…
2 	1 		…
3 	1 		…
4 	2		…
5 	4 		…
6 	4 		…
7 	2 		…
itd

Sens tych wartości jest oczywisty: każdy rekord zawiera referencję na rekord ‘nadrzędny’ (rodzica). Rekord od id = 1 nie ma rodzica - w związku z tym parent_id = NULL.

Co daje taki model? Na pewno bardzo proste wstawianie nowych rekordów. Równie proste jest przesuwanie - jednym zapytaniem można przesunąć całą gałąź do innego węzła. Z usuwaniem sprawa nie jest już taka prosta, ale można skorzystać z kaskady (ON DELETE CASCADE), która bardzo ładnie usunie całą gałąź poniżej usuwanego elementu.

Problem w tym, że wstawianie, usuwanie i przesuwanie to nie są operacje najczęściej wykonywane na drzewie. Typowe operacje to: “pobierz wszystkie węzły potomne oddalone o mniej niż 2 od wskazanego węzła“, albo “pobierz wszystkie węzły macierzyste wskazanego węzła“. W praktycznych zastosowaniach pierwsza operacja odpowiada np. budowaniu nawigacji na podstawie drzewa kategorii, druga zaś - tworzenia ścieżki dostępu (tzw. breadcrumbs) od bieżącej kategorii do strony głównej serwisu.

SQL nie zawiera wydajnych narzędzi czytania drzew zdefiniowanych tak, jak w powyższym przykładzie. W efekcie każda próba odczytania dowolnego fragmentu drzewa wymaga wielokrotnych zapytań do bazy danych - po jednym dla każdego poziomu przy czytaniu “w górę”, i co najmniej po jednym na każdy poziom przy czytaniu w dół. Przy serwisach z bardziej złożonym układem kategorii narzut związany z budowaniem nawigacji może być bardzo znaczący. Oczywiście, można użyć jednej z wielu technik cachowania, ale cache tylko maskuje prawdziwy problem.

Na szczęscie jest metoda pozwalająca na odczytanie dowolnego fragmentu drzewa pojedynczym zapytaniem - kosztem bardziej złożonej procedury dodawania i modyfikacji drzewa. Ale o tym w następnym wpisie.

SQL Subselect - parę słów o wydajności

Napisano maj 8, 2008 * Komentarze (2)

Trafiłem ostatnio na ciekawy wpis na blogu Krisa, traktujący o problemach związanych z wydajnością SQL subselect w dużych bazach (a przynajmniej dużych jak na aplikacje internetową). Temat dla mnie również ciekawy, ponieważ nasza aplikacja ma poważne problemy z wydajnością pojawiające się przy rozroście bazy danych, i część tych problemów jest związana z bazą danych.

Podejście Krisa - polegające na złamaniu postaci normalnej poprzez utworzenie kolumn pomocniczych z pewnością - poprawiło wydajność, ale budzi we mnie niepokój. Spreparowałem więc sobie zestaw danych wejściowych w celu przeprowadzenia własnego eksperymentu…
Czytaj dalej »