Wykład 11

Planowanie indeksów

 

Streszczenie

Wykład składa się z dwóch części. W pierwszej części są omówione zasady projektowania fizycznego schematu bazy danych i jego dostrajanie: jakie założyć indeksy, czy pogrupować tabele w klastry, jak poprawić schemat logiczny bazy danych z punktu widzenia szybkości działania zapytań.

W drugiej części, jako uzupełnienie do tematu budowy i wyboru indeksów w bazie danych, są przedstawione rodzaje indeksów realizowane w SZBD Oracle.


11.1 Projektowanie fizycznej bazy danych

Ulepszanie schematu tabel i postacie normalne

Redundancja na poziomie logicznym (schematu tabel) pociąga za sobą redundancję zapisu na nośniku danych, bo wymagane jest więcej miejsca na dysku, oraz anomalie przy wstawianiu, usuwaniu i aktualizacji danych. Redundacje w schemacie tabel są eliminowane przy użyciu analizy zależności funkcyjnych i dekompozycji tabel na mniejsze. Jednak wówczas może się okazać, że do wykonania zapytania będzie potrzebne złączenie dwóch lub więcej tabel, co może istotnie zwiększyć czas realizacji zapytania.

  1. Jeśli wszystkie tabele są w postaci normalnej BCNF (Boyce'a-Codda), to są one wolne od redundancji związanych z zależnościami funkcyjnymi.
  2. Jeśli tabela nie jest w postaci BCNF, staramy się dokonać jej dekompozycji na zbiór tabel w postaci BCNF:
  3. Gdy aplikacja przetwarza osobno dwa zbiory wierszy może opłacać się rozdzielić tabelę na dwie np. tabelę Osoby na tabele: Studenci i Pracownicy. Tutaj dekompozycja jest pozioma, przy normalizacji natomiast, dekompozycja jest pionowa.
  4. Sprawdzamy czy tabela jest wolna od zależności wielowartościowych. Jeśli nie, dokonujemy odpowiedniej dekompozycji.

Projektowanie indeksów

W pierwszej kolejności określamy pole działania (ang. workload) tworzonej aplikacji bazodanowej.

Pole działania aplikacji bazodanowej tworzą:

Dla każdego zidentyfikowanego zapytania:

Dla każdej zidentyfikowanej aktualizacji:

W oparciu o zebrane informacje podejmujemy decyzje:

Jeszcze krótkie podsumowanie projektowania indeksów:

Rozważymy teraz na przykładach problem projektowania indeksów. Przypominamy, że potrzeba założenia indeksu ma swoje źródło w wymaganiu szybkiego wykonania jednego lub więcej zapytań na budowanej bazie danych.

Przykład 1

SELECT E.Ename, D.Loc
FROM Emp E, Dept D
WHERE E.Deptno=D.Deptno AND
           D.Dname='SALES';

Indeks na D.Dname wspomaga selekcję D.Dname='SALES' gdy D jest  tabelą zewnętrzną. Potrzebny jest indeks albo jednoznaczny albo selektywny albo pogrupowany.

Indeks na E.Deptno wspomaga złączenie (E – tabela wewnętrzna). Powinien być pogrupowany, ponieważ spodziewamy się wybrania wielu wierszy z E.

Jeszcze lepszym rozwiązaniem byłby klaster obu tabel. Wtedy złączenie sprowadzilibyśmy do selekcji na klastrze zbudowanym w oparciu o indeks na kolumnie D.Dname. Przy odpowiednim zapisie klastra (jak w implementacji Oracle opisanej w dalszej części wykładu) dla danego departamentu rekordy wszystkich pracowników pracujących w tym departamencie byłyby zapisane na tej samej stronie co rekord departamentu lub tylko na kilku. Zastosowanie klastra jest więc szczególnie istotne gdy selekcja dotyczy tabeli po stronie jeden związku między tabelami (to jest po stronie klucza głównego) a dołączane przy złączaniu rekordy pochodzą z tabeli po stronie klucza obcego.

W krytycznych zastosowaniach można byłoby pomyśleć o zaprojektowaniu perspektywy zmaterializowanej liczącej tę konkretną instrukcję SELECT. Wynik byłby dostępny natychmiast.

Można byłoby też pomyśleć o perspektywie zmaterializowanej liczącej całe złączenie tabel Dept i Emp:

SELECT D.Dname, E.Ename, D.Loc
FROM Emp E, Dept D
WHERE E.Deptno=D.Deptno;
i założenie odpowiedniego indeksu na kolumnie D.Dname w celu przyśpieszenia wyszukiwania po kolumnie D.Dname.

Przykład 2

SELECT E.Ename, D.Loc
FROM Emp E, Dept D
WHERE E.Deptno=D.Deptno AND
    E.Sal BETWEEN 10000 AND 20000 AND E.Job='SALESMAN';

Ze względu na warunki ograniczające dla tabeli E, wybieramy Emp E jako tabelę zewnętrzną złączenia. Wtedy Dept D będzie tabelą wewnętrzną złączenia.

Kolumna D.Deptno jest kluczem głównym, posiada zawsze indeks, który można użyć przy złączaniu.

Jaki indeks jest potrzebny na tabeli Emp E? Albo indeks na E.Sal albo na E.Job – wybór zależy od selektywności warunków wyszukiwania - przy złej selektywności potrzebny byłby indeks pogrupowany na E.Job.

Alternatywnie system może zastosować przejście przez cały plik rekordów (scan) tabeli E - wtedy ewentualne indeksy w E nie byłyby zastosowane.

Klaster też mógłby być zastosowany do przyśpieszenia wykonania zapytania. Tym razem selekcja dotyczy tabeli po stronie wiele (to jest po stronie klucza obcego): dla rekordu pracownika obok na tej samej stronie moglibyśmy odczytać rekord departamentu.

Przykład 3

SELECT E.Deptno, COUNT(*)
FROM Emp E
WHERE E.Sal>2000
GROUP BY E.Deptno;

Potrzebny jest indeks pogrupowany na kolumnie E.Deptno. Jeśli nie jest możliwe założenie takiego indeksu, system posortuje względem E.Deptno plik rekordów tabeli Emp E - biorąc pod uwagę tylko rekordy dla których E.Sal>2000. Następnie wykona zliczanie COUNT(*).

Byłoby jeszcze lepiej, gdybyśmy dysponowali indeksem drzewowym na kolumnach <E.Deptno, E.Sal>. Wtedy moglibyśmy wykonać zapytanie przechodząc tylko indeks bez potrzeby przechodzenia do pliku rekordów – tzn. stosując strategię tylko-indeks.

Przykład 4

Pewne zapytania, jak ostatnie, można wykonać bezpośrednio przez indeks - bez przechodzenia do pliku rekordów. Oto kilka dodatkowych przykładów:

 
(a)

 

SELECT D.Dname
FROM Dept D, Emp E
WHERE D.Deptno=E.Deptno;

W tym przypadku wystarczy dowolny indeks na E.Deptno, ponieważ w ogóle nie trzeba przechodzić do pliku rekordów tabeli E! Zapytanie jest realizowane przez przejście (scan) całego pliku rekordów tabeli D i za każdym razem sięgnięcie do indeksu na E.Deptno w celu sprawdzenia czy istnieje pozycja danych z wartością klucza wyszukiwania równą D.Deptno.

 
(b)

 

SELECT E.Deptno, COUNT(*)
FROM Emp E
GROUP BY E.Deptno;

Wystarczy dowolny indeks na E.Deptno, ponieważ nie trzeba przechodzić do pliku rekordów tabeli E.

 
(c)

 

SELECT E.Deptno, MIN(E.sal)
FROM Emp E
GROUP BY E.Deptno;

Przydałby się indeks drzewowy na <E.Deptno, E.sal>. Wtedy nie trzeba byłoby przechodzić do pliku rekordów tabeli E.

 
(d)

 

SELECT AVG(E.Sal)
FROM Emp E
WHERE E.Deptno=25 AND E.Sal BETWEEN 3000 AND 5000;
Przydałby się indeks drzewowy na <E.Deptno,E.Sal> lub na <E.Sal, E.Deptno>. Wtedy nie trzeba by było przechodzić do pliku rekordów tabeli E.
 

Heurystyki optymalizacyjne dotyczące zapytań i indeksów

 


11.2 Indeksy w Oracle

Pokażemy teraz jak przedstawione idee budowy i użycia indeksów stosują się w przypadku konkretnego SZBD, mianowicie firmy Oracle.

W Oracle rezultatem wyszukiwania w indeksie są identyfikatory wierszy będące wartościami specjalnego typu danych ROWID. Są następujące rodzaje indeksów.

1. Indeks oparty na B+ drzewie

Pozycja danych składa się z wartości indeksowanych kolumn oraz z identyfikatora ROWID wiersza w tabeli - określającego fizyczne położenie danego wiersza na dysku. Umożliwia szybkie znalezienie wiersza w oparciu o daną wartość klucza wyszukiwania oraz realizację zapytań zakresowych. Odpowiada koncepcji indeksu nie pogrupowanego.

Przy wykonywaniu zapytania system używa indeksu opartego na B+ drzewie tylko wtedy gdy jest zapewniona wystarczająca selektywność wyszukiwania, powiedzmy 5 do 10% wszystkich rekordów w pliku.

Zwykły indeks oparty na B+ drzewie jest automatycznie tworzony dla każdego klucza głównego i jednoznacznego.

2. Tabela połączona z indeksem opartym na B+ drzewie

(tworzona za pomocą klauzuli ORGANIZATION INDEX w instrukcji CREATE TABLE)

Pozycjami danych indeksu głównego są rekordy pliku tzn. wiersze tabeli są trzymane w indeksie. Jest zapewniony bardzo szybki dostęp do wierszy przez wartości klucza głównego. Wiersze nie posiadają swoich identyfikatorów (ROWID) – identyfikacja wierszy przebiega wyłącznie przez wartości klucza głównego;  w pozostałych indeksach wynikiem wyszukania jest wartość klucza głównego – a nie ROWID. Odpowiada to koncepcji indeksu pogrupowanego - ale budowanego tylko dla klucza głównego.

Przydatność tabeli połączonej z indeksem prześledzimy na następującym przykładzie. Załóżmy, że chcemy dokonywać analizy klientów wyszukując klientów mieszkających w określonym mieście. Załóżmy więc, że mamy dwie tabele:

z podkreślonymi kluczami głównymi. Jeśli tabela Klienci jest połączona z indeksem na swoim kluczu głównym, istotnie można przyśpieszyć wykonywanie zapytań w rodzaju:

SELECT Klienci.Nazwisko, Klienci.Hobby
FROM Klienci, Miasta
WHERE Klienci.Id_miasta = Miasta.Id_miasta
     AND Miasta.Nazwa_miasta = 'WARSZAWA'
     AND Klienci.Wiek BETWEEN 18 and 25;

ponieważ po znalezieniu Id_miasta Warszawy wszyscy klienci z Warszawy będą zapisani razem tylko na kilku stronach a nie rozrzuceni po całym dysku, jak mogłoby się zdarzyć bez połączenia tabeli z indeksem.

Przykład ten jest interesujący i z tego powodu, że pokazuje zastosowanie złożonego klucza głównego.

Dla pełności prezentacji podajemy składnię instrukcji tworzącej tabelę Klienci:

CREATE TABLE Klienci(
   Id_miasta INTEGER,
   Id_klien_w_miescie INTEGER,
   Nazwisko VARCHAR2(80),
   Hobby VARCHAR(20),
   Wiek INTEGER,
   CONSTRAINT Klienci_pk PRIMARY KEY(Id_miasta,Id_klien_w_miescie),
   CONSTRAINT Klienci_fk FOREIGN KEY(Id_miasta) REFERENCES Miasta
   )
   ORGANIZATION INDEX;

3. Indeks oparty na B+ drzewie z odwróconymi wartościami kluczy

(klauzula REVERSE w instrukcji CREATE TABLE)

Jest stosowany tylko z predykatem równości – nie można w szczególności wypisywać wierszy wynikowych w kolejności uporządkowanej względem wartości klucza wyszukiwania. Bywa stosowany przy podziale tabeli i indeksu na partycje, gdzie równomierne rozłożenie wartości kluczy w poddrzewach B+ drzewa ma istotne znaczenie.

4. Indeks oparty na klastrze jednej lub więcej tabel, indeks haszowany

W klastrze wiersze kilku tabel są przechowywane razem uporządkowane względem wartości wybranych kolumn - nazywanych kluczem klastra, np. zamówienie razem ze swoimi pozycjami (kluczem klastra jest numer zamówienia). Jest to dobra struktura w przypadku gdy aplikacje często używają złączenia dwóch lub więcej tabel wchodzących w skład klastra.

Na każdym klastrze jest zakładany indeks zewnętrzny jednego z dwóch rodzajów:

Rozważmy przykładowe zapytanie liczące wartości zamówień złożonych przez klienta Kowalskiego.

SELECT z.Id_zam, SUM(p.Wartość*p.Ilość)
FROM Zamówienia z, Pozycje_zam p, Klienci k
WHERE p.Id_zam = z.Id_zam
    AND z.Id_klienta = k.Id_klienta
    AND k.Nazwisko = 'Kowalski'
GROUP BY
z.Id_zam;

Wykonanie tego zapytania można istotnie przyśpieszyć korzystając z klastra zawierającego tabele Zamówienia i Pozycje_zam, ponieważ wszystkie pozycje zamówień znajdują się albo na tej samej stronie co samo zamówienie, albo tylko na kilku stronach na dysku.

CREATE CLUSTER Klast_zam(Id_zam INTEGER)
  SIZE 2000;
Parametr SIZE określa ilość miejsca w bajtach przeznaczoną do zapisania jednego zamówienia i jego pozycji. Domyślną wartością jest rozmiar strony dyskowej. Jeśli wszystkie wiersze dla danej wartości klucza klastra nie mieszczą się w jednym bloku, są zapisywane na liście bloków.

Zatem chociaż indeks klastra nie jest pogrupowany, to jednak poprzez dobór odpowiedniej wartości SIZE można spowodować, że wszystkie rekordy z daną wartością klucza znajdą się na tej samej lub sąsiednich stronach dyskowych. Oznacza to, że wyszukiwanie przez klaster może być szybkie nawet przy nie najlepszej selektywności wyszukiwania przez indeks klastra. Sztywne ustawienie wartości SIZE może jednak  spowodować nie efektywne wykorzystanie miejsca na dysku – gdy zarezerwujemy więcej miejsca na rekordy z daną wartością klucza niż będzie to na ogół potrzebne.

Po utworzeniu tabel a przed wstawieniem do nich danych należy utworzyć indeks klastra.

CREATE INDEX Idx_zam ON CLUSTER Klast_zam;
Pełny przykład tworzenia klastra został podany na wykładzie 3.

W przykładzie z zamówieniami należałoby mieć założone także zwykłe indeksy na kolumnach Klienci.Nazwisko i Zamówienia.Id_klienta.

Podamy przykład zastosowania indeksu haszowanego dla klucza głównego Id_konta tabeli:

Zakładamy, że tabela Konta zawiera bardzo dużo wierszy oraz że często wielu kasjerów w banku równocześnie wykonuje zapytanie:

SELECT *
FROM Konta k
WHERE k.Id_konta = :numer;

Najpierw definiujemy klaster korzystając z opcji SINGLE TABLE:

CREATE CLUSTER Klast_konta(Id_konta INTEGER)
  SIZE 512
  SINGLE TABLE
  HASHKEYS 100000 HASH IS mod(Id_konta, 100003);

gdzie:

Liczbę wartości funkcji haszującej można odczytać z perspektywy słownika danych:

SELECT u.Hashkeys
FROM User_clusters u
WHERE u.Cluster_name = 'KLAST_KONTA';

Następnie definiujemy tabelę Konta:

CREATE TABLE Konta(Id_konta INTEGER PRIMARY KEY,
     Saldo NUMBER,
     Imie VARCHAR2(20),
     Nazwisko VARCHAR2(50),
     Adres VARCHAR2(70))
CLUSTER Klast_konta(Id_konta);

W przypadku klastra haszowanego nie trzeba explicite tworzyć indeksu na kolumnie klucza klastra.

Dostęp do informacji o koncie klienta jest teraz bardzo szybki – na ogół wystarczy sprowadzić dwie strony z dysku (jedną indeksu i jedną z pliku rekordów), aby odczytać wartości w wierszu. W przypadku pesymistycznym może się jednak zdarzyć, że wiele kluczy da tę samą wartość funkcji haszującej i wtedy po przekroczeniu rozmiaru SIZE kolejne rekordy będą umieszczane na stronach nadmiarowych.

5. Indeks z pozycjami określonymi za pomocą wyrażeń

Kolumny indeksu mogą być wyrażeniami zawierającymi funkcje (z wyłączeniem funkcji agregujących). Na przykład, założenie indeksu

CREATE INDEX Uppercase_idx ON Emp(UPPER(Ename));

pomaga w realizacji wyszukiwania pracowników w oparciu o ich nazwiska - nie biorąc pod uwagę wielkości liter w nazwisku:

SELECT * FROM Emp e
WHERE UPPER(e.Ename)='KOWALSKI';

6. Indeks bitmapowy

zostanie omówiony w wykładzie na temat hurtowni danych.

 


11.3 Podsumowanie

W wykładzie 11 zostały omówione zasady projektowania fizycznego schematu bazy danych i jego dostrajanie: jakie założyć indeksy, czy pogrupować tabele w klastry, jak poprawić schemat logiczny bazy danych z punktu widzenia szybkości działania zapytań.

Dodatkowo zostały przedstawione rodzaje indeksów, które występują w systemie Oracle. Pokazuje to, jak ogólna teoria dotycząca indeksów jest realizowana w praktyce.
 


11.4 Słownik pojęć

pole działania - składa się z informacji o aplikacji bazy danych:


11.5 Zadania

  1. Omów wybór indeksów na tabelach Emp i Dept z punktu widzenia wykonania zapytania. Opisz przypuszczalny plan wykonania zapytania wybrany przez optymalizator zapytań.
    1. SELECT E.Mgr, COUNT(*)
      FROM Emp E
      GROUP BY E.Mgr;
    2. SELECT E.Ename
      FROM Emp E, Dept D
      WHERE E.Deptno=D.Deptno AND
                 D.Dname='SALES'
      ORDER BY e.Empno;
    3. SELECT e.Dname, COUNT(*)
      FROM Emp E, Dept D
      WHERE E.Deptno=D.Deptno AND
            E.Job = 'SALESMAN'
      GROUP BY e.Deptno, e.Dname;
    4. SELECT E.Ename, D.Dname
      FROM Emp E, Dept D
      WHERE E.Deptno=D.Deptno AND
            E.Job = 'SALESMAN'
      ORDER BY e.Empno;
    5. SELECT E.Ename, E.job, D.Dname
      FROM Emp E, Dept D
      WHERE E.Deptno=D.Deptno
      ORDER BY e.Ename;

2. Podaj przykład aplikacji gdzie warto zastosować tabelę połączoną z indeksem opartym na B+ drzewie (w wersji Oracle).



Strona przygotowana przez Lecha Banachowskiego - 12/04/05.