Indeksy (InterBase i Firebird)

Alexey Kovyazin, ostatnia aktualizacja 07-Sep-2005

Koncepcja leżąca u podstaw indeksów jest prosta i wizualna oraz stanowi jedną z najważniejszych podstaw projektowania baz danych. Na bazie indeksów opiera się wiele podstawowych obiektów baz danych, a ponadto poprawne użycie indeksów jest kluczem do zwiększenia wydajności aplikacji bazodanowych. Czym jednak jest indeks? Indeks to uporządkowany wskaźnik rekordów w tabeli. Wskaźnik oznacza, że indeks zawiera wartości jednego lub kilku pól w tabeli oraz adresy stron danych, na których te wartości się znajdują (szczegóły dotyczące stron danych znajdziesz w rozdziale „Struktura bazy danych InterBase") (część 4). Innymi słowy, indeks składa się z par wartości „wartość pola" - „fizyczna lokalizacja tego pola".

Zatem po wartości pola (lub pól) zawartego w indeksie, używając indeksu, możemy szybko znaleźć miejsce w tabeli, w którym znajduje się rekord zawierający tę wartość. Uporządkowany oznacza, że wartości pól przechowywane w indeksie są uporządkowane. Bardzo często indeks porównywany jest z katalogiem bibliotecznym, w którym wszystkie książki są zapisane na kartach i uporządkowane w jakiś sposób: alfabetycznie lub tematycznie, a każda karta zawiera informację, gdzie dokładnie dana książka znajduje się w magazynie.

Po co nam indeksy?

Jedyną rzeczą, którą wspierają indeksy, jest przyspieszenie wyszukiwania rekordów po ich indeksowanym polu (indeksowane - oznacza zawarte w indeksie). Główną funkcją indeksów jest zapewnienie szybkiego wyszukiwania rekordów w tabeli. Każde użycie indeksu sprowadza się do tego.

Jak realizowana jest ta funkcja wyszukiwania? Na wejściu tej funkcji mamy wartość indeksowanego pola (lub kilku pól). W wyniku wyszukiwania powinniśmy otrzymać cały rekord, w którym indeksowane pole ma zadaną wartość. Najpierw w indeksie (a dokładniej w uporządkowanej tablicy wartości indeksowanego pola) wyszukiwana jest wymagana wartość, następnie pobierany jest adres strony danych, na której znajduje się wymagany rekord, serwer przechodzi do tej strony i odczytuje znaleziony rekord. Wygląda to dość nieporęcznie, jednak wyszukiwanie z użyciem indeksu jest wielokrotnie szybsze niż sekwencyjne przeszukiwanie wszystkich wartości z tabeli.

Jeśli kontynuujemy analogię między indeksem a katalogiem bibliotecznym, zobaczymy, że wyszukiwanie rekordów z użyciem indeksu jest bardzo podobne do wyszukiwania książki za pomocą karty. Gdy znajdziemy książkę w dość małym katalogu (w porównaniu z całym magazynem biblioteki), natychmiast otrzymujemy informację, gdzie dokładnie książka jest przechowywana, i możemy udać się prosto tam. Wyszukiwanie bez użycia indeksu można porównać z sekwencyjnym przeszukiwaniem wszystkich książek w bibliotece!

Przeszukiwanie wszystkich rekordów w tabeli nazywane jest bezpośrednim lub naturalnym. Należy powiedzieć, że pomimo mocy współczesnych komputerów naturalne przeszukiwanie może być bardzo długie, jeśli tabela zawiera dużą liczbę rekordów.

Jak są zorganizowane?

Indeks nie jest częścią tabeli; jest osobnym obiektem połączonym z tabelą i innymi obiektami bazy danych. Jest to bardzo ważny punkt implementacji systemu zarządzania bazą danych, pozwalający oddzielić przechowywanie informacji od jej prezentacji.

InterBase, jak każda inna relacyjna baza danych, przechowuje rekordy w tabelach w sposób nieuporządkowany, tj. w ogóle nie dba o to, jak rekordy są fizycznie rozmieszczone w tabeli. Nieuporządkowane przechowywanie oznacza, że dwa rekordy dodane do tabeli jeden po drugim mogą nie znajdować się obok siebie. Co więcej, dane pobrane z tabeli również nie mają żadnego porządku, poza tym, który powinien być jawnie określony przez użytkownika wykonującego zapytanie.

Nie możemy jednak obejść się bez porządkowania przechowywanych danych: użytkownicy końcowi aplikacji chcą widzieć dane w określonym porządku - na przykład nazwiska osób alfabetycznie. Indeksy rozwiązują problem prezentacji danych w sposób uporządkowany. Wartości pól zawarte w indeksie są uporządkowane i przedstawione w specjalnym widoku, zoptymalizowanym pod kątem wyszukiwania wymaganych wartości (a mianowicie jest to istotne dla tworzenia uporządkowanych sekwencji).

Oddzielenie przechowywania danych od ich prezentacji daje dodatkowe korzyści w porównaniu z bezpośrednim sortowaniem - być może będziesz musiał sortować początkową tabelę na różne sposoby. Wtedy pomogą ci indeksy - dla każdej tabeli może być nawet 64 indeksów!

Jeśli mówimy o implementacji indeksów na poziomie fizycznym, reprezentują one drzewo binarne, którego węzły reprezentują pary „wartość pola w indeksie" - „lokalizacja danych w tabeli". Wyszukiwanie wymaganego rekordu w indeksie odbywa się za pomocą mechanizmu wyszukiwania haszującego - jednego z najszybszych algorytmów wyszukiwania.

Zastosowanie indeksów

Teraz, gdy wiadomo, czego możemy wymagać od indeksów, czas poznać ich funkcję w bazie danych. Indeksy są używane w trzech głównych przypadkach:

Przyspieszanie wykonywania zapytań. Indeksy są tworzone dla pól używanych w warunkach wyszukiwania zapytań SQL.
Wsparcie unikalności wartości w polach; ograniczenie klucza podstawowego (o którym była mowa w rozdziale „Tabele. Klucze podstawowe") wymaga, aby w tabeli nie było dwóch identycznych wartości pól zawartych w kluczu podstawowym. Aby spełnić ten warunek, podczas wstawiania nowego rekordu należy wyszukać tę samą wartość, która zostanie wstawiona. Do wyszukiwania rekordów używana jest specjalna odmiana indeksu - indeks unikalny (patrz poniżej).
Wsparcie integralności referencyjnej. Ograniczenia kluczy obcych (omówione w rozdziale „Ograniczenia bazy danych") są używane do sprawdzania, czy wartości wstawiane do tabeli koniecznie istnieją w innej tabeli. Podczas tworzenia klucza obcego indeks jest tworzony automatycznie. Ten indeks jest używany do przyspieszania zapytań wykorzystujących łączenie tabel, a także do sprawdzania warunków klucza obcego. Krótko omówiliśmy wszystkie możliwe zastosowania indeksów. Teraz rozważymy szczegóły każdego przypadku bardziej szczegółowo i odpowiemy na najczęściej pojawiające się pytania dotyczące stosowania indeksów.

Przyspieszanie wykonywania zapytań za pomocą indeksów

Opisano powyżej, że zastosowanie indeksów może znacznie przyspieszyć wykonywanie zapytań. Rzeczywiście tak jest w większości przypadków, ale istnieją pewne zastrzeżenia. Najpierw odpowiemy na pytanie często pojawiające się wśród tych, którzy zapoznali się z indeksami. Jeśli indeksy przyspieszają wyszukiwanie w bazie danych, dlaczego nie indeksować wszystkich pól w tabeli? Istnieją dwa momenty blokujące ogólne indeksowanie - miejsce na dysku i koszty przy modyfikacji danych w tabeli. Każdy utworzony indeks ma rozmiar równy rozmiarowi danych w indeksowanym polu plus rozmiar danych lokalizacji rekordów. Jeśli utworzymy indeksy dla każdego pola w tabeli, ich całkowity rozmiar będzie większy niż rozmiar danych w tabeli! Dlatego tworzenie dużej liczby indeksów prowadzi do ogromnego wydatku miejsca na dysku.

Drugi moment jest ważniejszy. Są to nakłady przy modyfikacji danych w tabeli. W relacyjnym systemie zarządzania bazą danych, jak wiadomo, rekordy w tabelach są nieuporządkowane, a zatem dodawanie/usuwanie rekordów odbywa się bez znaczących nakładów zasobów serwera. Nawet jeśli rekord zostanie usunięty ze środka bazy danych, nie ma przesuwania danych w celu wypełnienia tej pustki - nie jest to wymagane: serwer po prostu oznaczy puste miejsce i zapisze tam coś, gdy będzie to konieczne. Jeśli chodzi o dodawanie, w większości przypadków jest ono wykonywane na końcu tabeli. Jednak chociaż serwer nie przesuwa głównych danych w tabeli podczas modyfikacji, dane przechowywane w indeksach są porządkowane za każdym razem podczas dodawania/usuwania rekordów! Innymi słowy, serwer musi przebudować indeks podczas dodawania rekordu do środka tabeli. Oczywiście implementacja indeksu jest w jakiś sposób przeznaczona do częstych reorganizacji, ale operacje te mimo wszystko zajmują czas i zasoby procesora, a gdy w tabeli jest duża liczba indeksów, modyfikacja danych w niej może być znacznie wolniejsza niż w tej samej tabeli bez indeksów!

To są dwa główne powody, które przeszkadzają w ogólnym indeksowaniu. Oprócz nich istnieje jeszcze kilka uwag ograniczających stosowanie indeksów. Pierwszą jest zasada 20%. Mówi ona, że jeśli zapytanie wyszukujące zwraca więcej niż 20% rekordów z tabeli, użycie indeksu może spowolnić pobieranie danych! Oczywiście sytuacja zależy od konkretnego zapytania i warunków ustawionych dla wyszukiwania, ale należy pamiętać, że 20% rekordów to próg, przy którym efektywność użycia indeksów staje się wątpliwa. Druga uwaga nie jest sformułowana tak jasno. Jest związana z pracą optymalizatora InterBase.

Optymalizator to zbiór mechanizmów, które opracowują harmonogram wykonywania zapytania. Gdy użytkownik podaje InterBase dowolne zapytanie SQL, określa, co serwer powinien zwrócić po wykonaniu zapytania, ale nie definiuje, JAK serwer powinien wykonać zapytanie. Optymalizator na podstawie danego zapytania tworzy harmonogram jego wykonania, tj. skąd i w jakiej kolejności dane do wykonania zapytania zostaną pobrane, jakie indeksy zostaną przy tym użyte. Gdy serwer analizuje warunki wyszukiwania (są to głównie części wyrażeń WHERE, ORDER BY itp.) dla każdego pola zawartego w warunku, serwer próbuje użyć indeksu. Niestety algorytm tworzenia harmonogramu jest niekompletny i optymalizator często używa indeksów, które nie są zbyt efektywne dla konkretnego zapytania, przez co czas wykonania może zostać znacznie spowolniony. Dlatego tworzenie niepotrzebnych indeksów może prowadzić do tworzenia nieoptymalnych harmonogramów.

Należy zaznaczyć, że w klonie Yaffil problem ten jest rozwiązany dzięki zastosowaniu nowoczesnych algorytmów tworzenia harmonogramów. Trzecim przypadkiem, gdy indeks nie jest konieczny, są pola z ograniczonym zestawem wartości - na przykład pole przechowujące informację o płci osoby i zawierające tylko dwie możliwe wartości - „K" i „M"; nie ma sensu indeksować tego pola. Omówiliśmy zatem główne ograniczenia tworzenia indeksów. Teraz powinniśmy omówić problem, kiedy konieczne jest użycie indeksów w celu osiągnięcia poprawy wydajności. Istnieją 3 główne przypadki, gdy pole musi być indeksowane:

Gdy to pole jest używane w warunkach wyszukiwania w zapytaniach
Gdy łączenia tabel używają tego pola
Gdy to pole jest używane w klauzuli sortowania ORDER BY

Jeśli pole jest używane w sposób wymieniony powyżej, utworzenie dla niego indeksu może prowadzić do poprawy wydajności zapytań.

Rozważmy składnię tworzenia indeksów. Oto pełny format polecenia DDL, które pozwala tworzyć indeksy:

CREATE [UNIQUE] [ASC[ENDING] | DESC[ENDING]] INDEX index ON table (col [, col …]);

Minimalne wyrażenie tworzące indeks jest następujące:

CREATE INDEX my_index ON Table_example(ID)

W tym przykładzie indeks o nazwie my_index jest tworzony dla tabeli Table_example, a pole ID jest polem indeksowanym. Indeks jest rosnący, tj. wartości w nim są uporządkowane rosnąco, a także nieunikalny, co oznacza, że pole ID może mieć kilka identycznych wartości. Jest to oczywiście najprostszy przykład indeksu - najczęstszy. Jak widać z opisu składni, indeks może zawierać nie jedno, ale kilka pól. Taki indeks jest używany, gdy zapytania są często wykonywane i zawierają kombinację indeksowanych pól w warunkach wyszukiwania lub sortowania. Na przykład, jeśli mamy tabelę zawierającą pola Nazwisko, Imię, Patronimik, taki indeks zostanie użyty podczas tworzenia zapytania, które używa sortowania według Nazwiska, Imienia i Patronimiku. Ogólnie rzecz biorąc, nie jest konieczne określanie warunków dla wszystkich 3 pól użytych w indeksie, aby wykorzystać jego zalety. Jeśli chcemy posortować wynik zapytania, indeks zostanie użyty, gdy pierwsze pole w warunku sortowania pokrywa się z pierwszym polem w indeksie. Na przykład nasz indeks zostanie użyty w przypadku sortowania według Nazwiska i Imienia.

Zgodnie z dokumentacją, aby zoptymalizować wykonywanie zapytania zawierającego w klauzuli WHERE połączenie pól z warunkiem OR, należy używać nie indeksu zbiorczego, ale kilku pojedynczych dla wszystkich pól zawartych w warunku OR.

Co do kwestii kolejności sortowania indeksu, może być ona rosnąca lub malejąca. Po co nam różne kolejności sortowania? Oczywiście, dla różnych sortowań! Jeśli chcemy sortować osoby według nazwiska w kolejności rosnącej, tworzymy indeks rosnący (ASC), a jeśli malejącej (od Z do A) - to malejący! Jeśli chcemy obu, musimy utworzyć oba indeksy.

Wsparcie integralności referencyjnej za pomocą indeksów

Istnieje jeszcze jedna opcja w definicji indeksu - UNIQUE. Jeśli ją określimy, indeks pozwoli na wstawianie do tabeli tylko unikalnych wartości. W rzeczywistości jest to podstawa implementacji kluczy unikalnych. Klucze unikalne są szeroko stosowane w bazach danych. To znaczy, że РК jest unikalnym indeksem kluczowym, ale nie każdy UK jest РК. Powyżej mówiliśmy tylko o РК. Klucz podstawowy jest najczęściej używanym typem klucza unikalnego. Podczas tworzenia klucza podstawowego dla tabeli automatycznie tworzony jest unikalny indeks. Otrzymuje on nazwę złożoną z RDB$PRIMARYNNN, gdzie NNN jest sekwencyjnym unikalnym numerem w bazie danych. Zatem dwa główne ograniczenia integralności referencyjnej - klucz unikalny i klucz podstawowy - są realizowane dzięki użyciu unikalnego indeksu. Jest oczywiste, że pojęcie unikalności jest nie do pogodzenia z pojęciem wartości nieokreślonej. Innymi słowy, w polach zawartych w unikalnych indeksach nie powinno być żadnych wartości typu NULL. Przed utworzeniem unikalnego indeksu dla pola konieczne jest ustawienie ograniczenia NOT NULL. Jeśli indeks jest tworzony dla danych, które już istnieją, to podczas tworzenia pole indeksowane będzie sprawdzane pod kątem zawierania jakichkolwiek powtarzających się wartości. Jeśli zawiera, utworzenie indeksu będzie zabronione.

Oprócz ograniczeń klucza unikalnego i podstawowego, mechanizm indeksów leży u podstaw implementacji jeszcze jednego ograniczenia integralności referencyjnej - klucza obcego. Ograniczenie klucza obcego jest ustawiane dla jednego lub kilku pól dowolnej tabeli i zapobiega wstawianiu do tych pól wartości, które nie są zawarte w kluczu podstawowym innej, nadrzędnej tabeli. Do implementacji klucza obcego, tj. do przeprowadzenia sprawdzenia, czy wartość istnieje w tabeli nadrzędnej, automatycznie tworzony jest specjalny indeks. Jego nazwa to RDB$FOREIGNNN, gdzie NNN jest sekwencyjnym unikalnym numerem w bazie danych.

Dlaczego mechanizm indeksów jest używany do implementacji ograniczeń integralności referencyjnej? Rzecz w tym, że indeksy w InterBase są w specjalnej, uprzywilejowanej pozycji - mówi się, że są wykonywane poza kontekstem transakcji. Jest to bardzo ważna właściwość. O transakcjach będziemy mówić później, w rozdziale im poświęconym. Teraz tylko wspomnimy, że gdy indeksy są poza transakcjami, oznacza to, że wszyscy użytkownicy pracujący jednocześnie z danymi w tej samej tabeli muszą przestrzegać ograniczeń integralności referencyjnej.

Optymalizacja wydajności indeksów

W tytule tej części możemy dostrzec pewien paradoks - indeksy, jak powiedziano powyżej, mają przyspieszać wykonywanie zapytań, a okazuje się, że one również wymagają optymalizacji! Ale co robić (takie jest życie) - ktoś musi dbać o indeksy. Co dzieje się z indeksami? Dlaczego „tracą formę”? Musimy po raz kolejny powiedzieć, że indeksy są realizowane jako drzewo binarne. A gdy do tabeli dodawany jest nowy rekord (aktualizowany, usuwany - jak wolisz), do drzewa dodawana jest nowa gałąź. Gałęzie te są dodawane nie do środka drzewa, ale do wierzchołków innych gałęzi. Stopniowo drzewo staje się coraz bardziej rozgałęzione (lub niezrównoważone), a wyszukiwanie - mniej efektywne. Przebudowa drzewa lub (w niektórych przypadkach) ponowne przeliczenie statystyk może poprawić sytuację.

Okresowo wymagane jest ponowne utworzenie indeksu w celu przywrócenia jego wydajności. Ponowne utworzenie indeksu ma miejsce w następujących przypadkach:

Podczas przebudowy indeksu za pomocą polecenia ALTER INDEX.
Podczas usuwania i ponownego tworzenia indeksu za pomocą poleceń DROP INDEX i CREATE INDEX.
Podczas tworzenia kopii zapasowej i przywracania z kopii zapasowej za pomocą narzędzia gbak.

Można również użyć ponownego przeliczenia statystyk. Należy jednak rozumieć, że ta operacja nie zmienia stanu indeksu, jedynie informuje optymalizator o dokładnych informacjach na temat jego stanu, umożliwiając prawidłowe użycie tego indeksu. Innymi słowy, ponowne przeliczenie statystyk nie jest „lekarstwem” na indeks, a jedynie dokładną diagnozą jego stanu. Rozważmy wszystkie te sposoby optymalizacji indeksów bardziej szczegółowo. Użycie polecenia ALTER INDEX ma następujący format:

ALTER INDEX nazwa {ACTIVE | INACTIVE};

Tutaj nazwa to nazwa indeksu, a ACTIVE i INACTIVE - dwa stany indeksu, na które można go przekształcić za pomocą polecenia ALTER INDEX. Parametr ACTIVE oznacza, że indeks jest aktywny i może być stosowany we wszystkich zapytaniach i procedurach. Jeśli ustawisz indeks na INACTIVE, spowoduje to wyłączenie jego użycia. Aby przestawić drzewo, należy sekwencyjnie wykonać dwa polecenia:

ALTER INDEX nazwa INACTIVE; ALTER INDEX nazwa ACTIVE;

W ten sposób indeks zostanie przebudowany. Użycie ALTER INDEX ma szereg ograniczeń: nie można przebudowywać indeksów używanych w kluczach podstawowych, unikalnych i obcych; nie można przebudowywać indeksu, jeśli jest on aktualnie używany przez jakiekolwiek zapytanie; a także do zmiany indeksu konieczne jest posiadanie uprawnień administratora (SYSDBA) lub bycie twórcą danego indeksu.

Ponowne utworzenie indeksu za pomocą poleceń DROP INDEX i CREATE INDEX prowadzi do całkowitego usunięcia indeksu z bazy danych, a następnie do jego utworzenia od podstaw. Składnia polecenia DROP INDEX jest oczywista:

DROP INDEX nazwa_indeksu;

Po usunięciu konieczne jest utworzenie indeksu o tej samej nazwie i parametrach za pomocą polecenia CREATE INDEX, którego składnię już rozważaliśmy. Sposób przebudowy indeksu przez jego całkowite ponowne utworzenie ma ograniczenia podobne do ograniczeń dla użycia ALTER INDEX.

Trzeci sposób przebudowy indeksu opiera się na właściwości kopii zapasowych baz danych InterBase tworzonych przez narzędzie gbak. Rzecz w tym, że podczas tworzenia kopii zapasowej dane zawarte w indeksie nie są zapisywane w kopii zapasowej, przechowywana jest tylko definicja indeksu. Podczas przywracania z kopii zapasowej indeks jest tworzony ponownie. Jeśli chcesz dowiedzieć się więcej o kopiach zapasowych, zobacz rozdział „Tworzenie kopii zapasowych i przywracanie z kopii zapasowej” (część 4).

Czwartym sposobem poprawy wydajności indeksów jest zbieranie statystyk na temat indeksów za pomocą polecenia SET STATISTICS. Statystyka tabeli to wartość z zakresu od 0 do 1, której wartość zależy od liczby różnych rekordów w tabeli. Optymalizator InterBase używa statystyk do określenia efektywności zastosowania tego czy innego indeksu w zapytaniu. Gdy liczba rekordów w tabeli może się znacznie zmienić (na przykład z powodu dużej liczby wstawień lub usunięć), ponowne przeliczenie statystyk może znacznie poprawić wydajność. Polecenie ponownego przeliczenia statystyk wygląda następująco:

SET STATISTICS INDEX nazwa;

Tutaj nazwa to nazwa indeksu, dla którego przeliczane są statystyki. Ponowne przeliczenie statystyk nie przebudowuje indeksu i dlatego jest wolne od większości ograniczeń ustawionych dla opisanych powyżej sposobów poprawy wydajności, z wyjątkiem tego, że tylko twórca indeksu lub administrator systemu (użytkownik o nazwie SYSDBA) może przeliczać statystyki. Prawidłowe statystyki umożliwiają optymalizatorowi podjęcie właściwej decyzji o użyciu lub nieużyciu danego indeksu.

Rozważyliśmy kilka sposobów poprawy wydajności indeksów. Za pomocą poleceń ALTER INDEX i DROP/CREATE INDEX możemy przebudować dowolne indeksy z wyjątkiem indeksów systemowych tworzonych automatycznie, przeznaczonych do zapewnienia integralności referencyjnej. Jeśli chcesz przebudować te indeksy, powinieneś użyć poleceń zmiany i tworzenia tabel - ALTER TABLE i CREATE TABLE, ponieważ indeksy te są integralną częścią kluczy tabelarycznych.