Prawda o indeksach

Indeksy to podstawowy oręż w walce o wydajność zapytań, powszechnie określanej mianem optymalizacji. Każda broń najzwyczajniej w świecie zużywa się - podobna sytuacja ma miejsce w przypadku indeksów. Trzeba pamiętać, że proces optymalizacji zachodzi w każdym przypadku przetwarzania zapytania przez SQL Server - niezależnie od naszych intencji. Oczywiście możemy wiele wnieść do tego procesu, pisząc zapytania w sposób, który podsunie serwerowi najkorzystniejsze rozwiązanie zapytania - w końcu tylko my wiemy, co chcemy osiągnąć.

SQL Server query optimizer wykorzystuje estymację opartą na kosztach (cost-based optimization) w celu wyboru najkorzystniejszego planu wykonania zapytania (chodzi przede wszystkim o jak najmniejszą ilość operacji IO, ale nie jest to oczywiście jedyne kryterium). Optimizer naturalnie nie ma czarodziejskiej kuli - wszystkie obliczenia wykonuje na podstawie informacji o stanie danych i m.in. oceny aktualnego obciążenia. Z jego punktu widzenia celem jest jak najszybsze dostarczenie określonego przez zapytanie podzbioru rekordów.

Zakładając, że dane muszą być w odpowiedni sposób wybrane - optimizer jest zainteresowany tylko takimi operacjami, które najszybciej doprowadzą do selekcji żądanych rekordów ze zbioru źródłowego. SQL Server ma do wyboru kilka strategii: może patrzeć po kolei na poszczególne elementy zbioru (rekordy), dokonywać etapowo zawężeń lub łączyć obydwie techniki. Zawężenia wprowadzane są w oparciu o cechy (atrybuty) elementów zbioru, które okazują się maksymalnie selektywne. Ponadto potrzebna jest struktura, który szybko dostarczy informacji o tym, które elementy posiadają określoną cechę - w przeciwnym razie trzeba będzie przeglądać wszystkie po kolei. Jest to właśnie zadanie dla indeksu, który stanowi strukturę funkcjonalnie odpowiadającą spisowi treści dowolnej książki. Na podstawie zapytania SQL Server określa atrybuty zbioru (kolumny tabeli), które narzucone są w kryterium wyboru elementów (warunek WHERE, JOIN itd.). Wie także, jakie indeksy zostały utworzone. Musi podjąć decyzję, z których skorzystać, a z których korzystać się nie opłaca. Niewielki przecież pożytek z indeksu opartego na kolumnie, której wszystkie wartości są sobie równe albo niewiele jest elementów różniących się. Powiemy w takim przypadku, że kolumna ma małą selektywność (selectivity). Przykładowo: zerową selektywność ma wybór wszystkich czerwonych bil ze zbioru składającego się wyłącznie z czerwonych bil. Wielkością odwrotnie proporcjonalną do selektywności indeksu (kolumny) jest jego gęstość (density).

Gęstość to stosunek ilości wszystkich wartości kolumny (= wierszy) do liczby wartości unikalnych lub inaczej - to średnia liczba duplikatów wartości kolumny. Wielkość ta wyrażana jest jako procent lub ułamek o podstawie 100. Gęstość indeksu opartego na kolumnie, która w danej tabeli ze 100 wierszami ma wszystkie wartości unikalne wynosi 1%. Selektywność indeksu opartego na takiej kolumnie wynosi więc 100%. Jest naturalne, że im większa selektywność indeksu (kolumny), tym mniej odczytów trzeba wykonać, aby pobrać potrzebne dane (spis treści, który pozwala dotrzeć do informacji otwierając jedną czy dwie strony książki jest dużo efektywniejszy niż ten, za pomocą którego zawęzimy obszar poszukiwań np. tylko do rozdziału).

Oczywiście optimizer musi być w stanie oszacować aktualną przydatność indeksu przed jego ewentualnym zastosowaniem. Służą do tego statystyki indeksu (index statistics). Od razu wyjaśnię pewną nieścisłość pojęciową: co prawda powszechnie używa się terminu "statystyki indeksu", jednak w rzeczywistości statystyki dotyczą wyłącznie kolumny - i to nawet niekoniecznie indeksowanej. W praktyce dopuszczalny jest skrót myślowy polegający na tym, że mówiąc o wartościach indeksu, w rzeczywistości mówimy o wartościach kolumny, na której indeks jest zbudowany (sam indeks zasadniczo nie zawiera w sobie wartości kolumny, tylko referencje do nich przez wartości klucza głównego lub identyfikator wiersza - RID). Z tego punktu widzenia statystyki indeksu pojęciowo automatycznie odnosimy do statystyk kolumny.

Statystyki dostarczają informacji dotyczących rozkładu wartości w kolumnie. SQL Server tworzy w tym celu tzw. histogram. Odbywa się to w następujący sposób: najpierw ma miejsce sortowanie wartości kolumny i wybór do 200 elementów, które wyznaczają granice przedziałów. SQL Server określa następnie ile wartości przypada na każdy przedział, jaka jest jego gęstość i częstość występowania duplikatów. W zależności od typu danych kolumny, zbierane mogą być także inne informacje.

Bardzo ważną kwestią dotyczącą indeksów jest ich wewnętrzna i zewnętrzna fragmentacja (internal, external fragmentation). Nie będę tutaj dokładnie wyjaśniał na czym polegają te zjawiska, zainteresowanych odsyłam do zewnętrznych zasobów (linki poniżej). Istotne jest, że fragmentacja powstaje na skutek operacji DML na tabeli, kiedy logiczny porządek stron indeksu przestaje odpowiadać ich fizycznej kolejności. Wysoki poziom fragmentacji może uniemożliwić skuteczne użycie indeksu (samo odczytanie indeksu zacznie być dość kosztowne).

Z punktu widzenia powyższych rozważań dla skuteczności indeksu najistotniejsze są następujące kwestie:
- wysoka selektywność indeksu
- aktualność statystyk
- niski poziom fragmentacji

Pierwszy punkt dotyczy polityki zakładania indeksów. Temat jest bardzo szeroki i tutaj tylko go sygnalizuję (może w przyszłości coś o tym napiszę). Dwie pozostałe kwestie to już sfera bardziej techniczna. O stan indeksów musimy zadbać sami - inaczej urosną do dużych rozmiarów lub/i staną się nieefektywne. Mamy zasadniczo do wyboru trzy możliwości:

1. aktualizacja (update) statystyk
SQL Server 2000+2005: UPDATE STATISTICS, sp_updatestats

2. defragmentacja indeksu
SQL Server 2000: DBCC INDEXDEFRAG, SQL Server 2005: DBCC INDEXDEFRAG [deprecated], ALTER INDEX .. REORGANIZE

3. reindeksacja (odbudowa indeksu)
SQL Server 2000: DBCC REINDEX, SQL Server 2005: DBCC DBREINDEX [deprecated], ALTER INDEX .. REBUILD

Co do zasady im proces mniej inwazyjny, tym niestety mniej pożyteczny. Aktualizacja statystyk trwa dosłownie chwilę, ale nie poprawia struktury indeksu tylko sprawia, że optimizer dysponuje informacjami bardziej odpowiadającymi rzeczywistości. Defragmentacja indeksu z kolei nie gwarantuje pełnego usunięcia fragmentacji, ale ze względu na to, że w danym momencie zablokowane są tylko dwie strony danych - nie jest zbyt uciążliwa dla konkurujących procesów. Autor defragmentacji (Paul Randal) tak uzasadnił jej stworzenie:

"The main reason I wrote DBCC INDEXDEFRAG was to provide an online alternative to doing an index rebuild."

Doświadczyłem jednak już sytuacji przewlekłego zblokowania się defragmentacji i jednego z zapytań, więc mam bardziej krytyczne podejście do onlineowości tego procesu. Po defragmentacji należy we własnym zakresie zaktualizować statystyki. Reindeksjacja natomiast to w rzeczywistości pełna odbudowa indeksu (DROP + CREATE). Ma miejsce w jednej transakcji i blokuje daną tabelę na wyłączność na czas operacji (choć w wersji SQL Server 2005 Enterprise możne odbywać się także onlineowo). Zapewnia usunięcie wszystkich problemów związanym z pogarszaniem się stanu indeksów w drodze normalnej codziennej eksploatacji bazy. Po reindeksjacji nie ma potrzeby aktualizowania statystyk. Jestem zdania, że dla każdej bazy danych należy wyznaczyć czas na operacje maintenanceowe, które ze swej natury wymagają niekiedy trybu offline.

Oddzielnym zagadnieniem jest defragmentacja wolumenu, na którym znajdują się pliki baz danych. Jej sensowność bywa często kwestionowana (zwłaszcza przez osoby średnio orientujące się w temacie). Prawda jest jednak taka, że defragmentacja wolumenu przynosi poprawę wydajności bazy, zwykle jednak nie jest ona monumentalna. Z moich doświadczeń mogę powiedzieć, że po defragmentacji wolumenu zapytania wykonywały się zwykle około 5-7% szybciej (macierz RAID 1). Ze względu na problematyczność i uciążliwość tego typu operacji (choć zaznaczam, że nie musi to być operacja w trybie offline), administratorzy często nie decydują się na włączanie defragmentacji do polityki utrzymaniowej bazy.

Więcej informacji:
SQL Server Performance: SQL Server Index Fragmentation and Its Resolution
MSDN: Index Statistics
SQL Server 2005 Books Online: Understanding Indexes