Monthly Archives: Czerwiec 2012

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