Indeksy grupujące a sterty – co zajmie więcej miejsca na dysku?

Jednym z zadań projektowych podczas definiowania struktury bazodanowej jest  określenie, czy dana tabela ma posiadać indeks grupujący, czy powinna być stertą. O ile nie chciałbym rozpoczynać dyskusji na temat, czy zakładanie indeksu grupującego na każdej tabeli w bazie danych jest dobrym podejściem (jestem zwolennikiem tej opcji), to w dzisiejszym poście chciałbym pokazać, że przechowywanie w postaci zgrupowanej może zająć mniej miejsca na dysku niż gdy dane tworzą tzw. stertę.

Wstęp teoretyczny

Zanim zaczniemy badać przedstawioną przez mnie tezę zacznijmy od krótkiego przypomnienia, czym jest sterta, a czym indeks grupujący.

Dane wewnątrz bazy SQL Server-a są przechowywane na 8Kb stronach. W przypadku, gdy nie są  one logicznie uporządkowane, to mówimy, że tabelą jest stertą.

Jak widać na powyższym obrazku, id rekordu nie determinuje ułożenia danych na stronach (id równe 3 jest po 8, a 8 po 5). Wadą tego typu struktury jest fakt, że  jeżeli zechcemy odszukać konkretne id, to musimy przeczytać całą tabelę (zakładając, że nie ma ona odpowiedniego indeksu niegrupującego).

Jeżeli uporządkujemy dane tabeli za pomocą odpowiedniego klucza, to mówimy, że tabela jest indeksem grupującym

Na obrazku powyżej widać, że dane w tabeli są uporządkowane wg kolumny o nazwie id. Indeks grupujący w SQL Server jest przetrzymywany w postaci B-drzewa. Dzięki temu podejściu dostęp do danych za pomocą klucza indeksu jest bardzo efektywny. Jeżeli zachcemy wybrać rekord o id = 5, to silnik bazy nawigując po utworzonym drzewie jest w stanie odszukać go odczytując niewielką ilość stron: korzeń drzewa, odpowiednie strony pośrednie i stronę z danymi (a nie jak w poprzednim przypadku skanując całą tabelę). Wadą przetrzymywania danych w ten sposób jest fakt, że utworzenie B-drzewa powoduje wygenerowanie struktur nadmiarowych, które też muszą być zapisane na dysku.

Tabela bez indeksu grupującego większa od zindeksowanej ??

Po wstępie teoretycznym prawdopodobnie część z was zaczęła zastanawiać jak to jest możliwe, że sterta (czyli same strony danych) może zająć więcej miejsca na dysku niż indeks grupujący (a więc strony danych + struktury nadmiarowe). W tym momencie chciałbym podkreślić, że sytuacja taka występuje, choć nie koniecznie jest ona regułą 🙂

Rozpoczynamy test

Aby zademonstrować taką sytuację stworzyłem nową bazę danych o nazwie TestDB.

CREATE DATABASE TestDB

Następnie utworzyłem 2 tabele (z i bez indeksu grupującego):

-- nasza sterta
CREATE TABLE Sterta (
 id int,
 kolA char(1800)
 )
-- jeżeli mamy PRIMARY KEY,
-- domyślnie indeks grupujący jest tworzony na kluczu
CREATE TABLE IndeksGrupujacy (
 id int PRIMARY KEY,
 kolA char(1800)
 )

Oraz wpisałem do każdej z nich 10000 wierszy:

-- wpisujemy dane do obu tabel
 DECLARE @i int = 1
WHILE @i <= 10000
 BEGIN
 INSERT Sterta(id, kolA)
 VALUES (@i, REPLICATE('s', 1800))
 INSERT IndeksGrupujacy(id, kolA)
 VALUES (@i, REPLICATE('s', 1800))
 SET @i = @i+1
END

Sprawdźmy ilość zajmowanego miejsca:

EXEC sp_spaceused 'Sterta'
EXEC sp_spaceused 'IndeksGrupujacy'

Ewidentnie sterta zajmuje więcej miejsca, pytanie tylko jak to się stało??

Wyjaśnienie zagadki

SQL Server wpisując dane do tabeli będącej indeksem grupującym „musi” wstawić je w odpowiednim miejscu (inaczej dane nie byłyby posortowane). W przypadku, gdy dane nie mieszczą się na jednej stronie, alokowana jest kolejna.

W przypadku stert sytuacja wygląda nieco inaczej. Z uwagi na brak logicznego uporządkowania rekordów silnik bazy najpierw sprawdza za pomocą specjalnych stron PFS (Page Free Space), które strony danych tabeli są w stanie przyjąć kolejny rekord. Informacje zawarte na stronach PFS są jednak zgrubne, gdyż są one zapisane następującymi przedziałami: 1-50%, 51-80%, 81-95% i 96-100%.

Z  obserwacji jakie przeprowadziłem wynika, że SQL Server sprawdzając wypełnienie strony używa wartości wyższej i oblicza, czy nowy rekord się zmieści. Przeanalizujmy jak ten mechanizm działał w przedstawionym wcześniej skrypcie ładującym dane:

-- najpierw czyścimy tabelę
TRUNCATE TABLE dbo.Sterta

Wstawiamy pierwsze 3 rekordy do sterty:

-- wstawiamy pierwsze 3 rekordy
INSERT dbo.Sterta
VALUES (1, REPLICATE('1', 1800)), (2, REPLICATE('2', 1800)), (3, REPLICATE('3', 1800))

I sprawdzamy zajęte miejsce na dysku:

DBCC IND('TestDB', 'dbo.Sterta', 1)

Jak widać nasza tabela zajmuje 2 strony, pierwszą z nich jest strona IAM (179), a drugą strona z danymi (178). Skoro nasze dane zajmują tylko 1 stronę, to sprawdźmy poziom jej wypełnienia za pomocą odpowiedniej funkcji:

SELECT object_id, index_id, avg_page_space_used_in_percent
FROM sys.dm_db_index_physical_stats(
 DB_ID('testDB'), OBJECT_ID('dbo.Sterta'), DEFAULT, DEFAULT, 'DETAILED')

Strona ta jest wypełniona w 67 procentach, ciekawe co na to powie odpowiednia strona PFS:

DBCC TRACEON (3604)
DBCC PAGE ('testDB', 1, 1, 3)

Na powyższym obrazku widać, że wg zawartych tam informacji strona danych naszej tabeli jest w 80% zajęta. Skoro kolejny wstawiany rekord ma ponad 1800 bajtów, to zajmie więcej niż 20% miejsca strony, a więc raczej się nie zmieści. Silnik bazy danych podejmie decyzję o alokacji nowej strony i wpisaniu tam kolejnej wartości:

INSERT dbo.Sterta
VALUES (4, REPLICATE('4', 1800))

Sprawdźmy to:

DBCC IND('TestDB', 'dbo.Sterta', 1)

Po wykonaniu instrukcji INSERT silnik bazodanowy zaalokował kolejną stronę i tym samym zwiększył wielkość naszej tabeli do 16KB:

EXEC sp_spaceused 'dbo.Sterta'

Dla niedowiarków

Aby postawić kropkę nad „i”, sprawdźmy jak będzie wyglądać przydzielenie miejsca na dysku dla tabeli z indeksem grupującym:

TRUNCATE TABLE dbo.IndeksGrupujacy
-- pierwsze 3 rekordy
INSERT dbo.IndeksGrupujacy
VALUES (1, REPLICATE('1', 1800))
 , (2, REPLICATE('2', 1800))
 , (3, REPLICATE('3', 1800))

-- i "problematyczny" czwarty
INSERT dbo.IndeksGrupujacy
VALUES (4, REPLICATE('4', 1800))
DBCC IND('TestDB', 'dbo.IndeksGrupujacy', 1)

Po wstawieniu 4 rekordów tabela z indeksem grupującym składa się jedynie z 2 stron, jednej IAM i jednej z danymi.

Potwierdźmy ilość zajętego miejsca przez dane procedurą sp_spaceused:

EXEC sp_spaceused 'dbo.IndeksGrupujacy'

Dopiero dopisanie piątego rekordu będzie wymagać nowej przestrzeni dyskowej.

Podsumowanie

SQL Server wstawiając dane do sterty i indeksu zgrupowanego posługuje się innymi algorytmami określającymi gdzie wstawić kolejny rekord. Z uwagi na fakt, że strony PFS zawierają jedynie zgrubne oszacowanie zajętego miejsca na stronie, to dopisywanie kolejnych wartości do tabeli może skutkować zbyt wczesną alokacją miejsca i niepełnym wykorzystaniem istniej przestrzeni dyskowej.

Reklamy

Posted on 7 czerwca 2012, in SQL Server and tagged . Bookmark the permalink. 9 Komentarzy.

  1. Bardzo prosto i dobrze wyjaśnione. Może pokusisz się o opis innych stroni niż PFS i IAM?

  2. Dzięki 🙂 Póki co ciężko z czasem, ale nie wykluczam 🙂

    Na razie mam dwa mity do obalenia (https://coltuszyk.wordpress.com/2012/05/06/mity-o-sql-server-zmiana-typu-kolumny-a-zwolnienie-miejsca-na-dysku/), tak więc szykuję środowisko na pierwszy z nich 🙂

  3. Jasne, jasne 🙂 Co do mitu z plikami tempdb. Mała podpowiedź: Microsoft zaleca faktycznie aby ilośc plików tempdb równała się ilości posiadanych rdzeni procesora. Proponuje przesledzić filemonitorem jak jest uzywana baza danych tempdb, która ma więcej niż 1 plik mdf. Jak się czasami okazuje więszka liczba plików nie zawsze daje pozytywny efekt i może spowolnic wykonanie zapytania 🙂 No, ale poczekajmy na testy

    • Zalecenie Microsoftu jest totalnie błędne i nigdy go nie stosuję na produkcyjnych bazach 🙂

      Niestety zanim to udowodnię i pokażę od czego zależy muszę parę zabawek zebrać (np. odpowiedni procesor).

      • Zalecenie nie jest totalnie błędne. Błędna jest interpretacja, która zakłada, że od razu na starcie mamy dzielić bazę tempdb na wiele plików danych. A zalecenie mówi, że podział robimy reaktywnie, gdy zauważymy problemy wynikające z intensywnego wykorzystania PFS w tempdb 🙂

      • Też racja 🙂

        Ja póki co skupię się na fakcie dlaczego nie robić tego z automatu. Niestety nie wiem czy uda mi się wymusić aż tak duże obciążenie tempdb, by pokazać kiedy podział tempdb na wiele plików zaczyna nabierać znaczenia (zwłaszcza na domowym sprzęcie).

  4. Czarku, wykorzystaj snapshot isolation level, trochę tabel tymczasowych i ostress 🙂 Na każdym sprzęcie powinno się dać.

    A co do sterty vs. indeks, to proponuję popróbować masowych operacji insert + delete. Okazuje się, że sterta ma problem z oddawaniem miejsca po usuniętych rekordach 🙂 Miałem kiedyś przypadek: SELECT * FROM Tabela, (0 row(s) affected) i… 3 sekundy duration (później okazało się, że robił 600 tys. readsów :-)).

    • Dzięki za radę, na pewno spróbuję 🙂

      600 tyś readsów to faktycznie jakaś masakra. Generalnie zachowanie stert podczas wstawiania, usuwania i aktualizacji rekordów jest czasem bardzo zaskakujące.

      Kilka nowych pomysłów na wpisy już mi w głowie siedzi, tak więc za jakiś czas będzie można o tym poczytać 🙂

  1. Pingback: blogi – co sie dzieje – czerwiec 2012 | ziembor.pl/blog

Skomentuj

Wprowadź swoje dane lub kliknij jedną z tych ikon, aby się zalogować:

Logo WordPress.com

Komentujesz korzystając z konta WordPress.com. Wyloguj / Zmień )

Zdjęcie z Twittera

Komentujesz korzystając z konta Twitter. Wyloguj / Zmień )

Zdjęcie na Facebooku

Komentujesz korzystając z konta Facebook. Wyloguj / Zmień )

Zdjęcie na Google+

Komentujesz korzystając z konta Google+. Wyloguj / Zmień )

Connecting to %s

%d blogerów lubi to: