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.
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.
W pierwszej kolejności określamy pole działania (ang. workload) tworzonej aplikacji bazodanowej.
Pole działania aplikacji bazodanowej tworzą:
Najważniejsze zapytania razem z informacją jak często będą używane.
Najważniejsze aktualizacje razem z informacją jak często będą używane.
Pożądana szybkość działania tych zapytań i aktualizacji.
Dla każdego zidentyfikowanego zapytania:
Do których tabel jest wymagany dostęp?
Które kolumny występują w warunkach selekcji/złączenia? Jak bardzo te warunki są selektywne?
Dla każdej zidentyfikowanej aktualizacji:
Które kolumny występują w warunkach selekcji? Jak bardzo te warunki są selektywne?
Typ aktualizacji (INSERT/DELETE/UPDATE) i których kolumn dotyczy?
W oparciu o zebrane informacje podejmujemy decyzje:
Na których tabelach i kolumnach należy utworzyć indeksy? Jakiego typu:
główny/jednoznaczny/zwykły? pogrupowany/zwykły?
haszowany/drzewowy? dynamiczny/statyczny?
(Bierzemy oczywiście pod uwagę jakie rodzaje indeksów realizuje stosowany
przez nas SZBD - na ogół tylko część z nich. Indeksy realizowane w
Oracle będą omówione w dalszej części tego wykładu.)
Czy warto dokonać poziomego podziału tabeli np. tabeli Osoby na osobne tabele Pracownicy i Studenci - co byłoby wskazane w przypadku gdyby kierowane do bazy danych zapytania dotyczyły osobno albo pracowników albo studentów oraz odpowiednie warunki wyszukiwania sugerowałyby indeksy na innych kolumnach?
Czy połączyć zapis kilku tabel w klaster? Ich złączenie staje się szybsze; operacje na pojedynczych tabelach stają się nieco wolniejsze niż bez klastra. Na przykład, czy zapisywać pozycje zamówień razem z zamówieniami w jednym pliku, w taki sposób, aby na dysku obok rekordu zamówienia były zapisane wszystkie jego pozycje?
Czy w celu wykonania konkretnego, ważnego zapytania utworzyć indeks z kluczem wyszukiwania obejmującym kolumny występujące w zapytaniu pamiętając, że indeksy mogą przyśpieszyć wykonanie zapytania ale spowalniają aktualizacje i zwiększają zajętość miejsca na dysku?
Czy w celu wykonywania konkretnego, ważnego zapytania zawierającego złożone konstrukcje jak złączenia, agregacje lub podzapytania, nie utworzyć dla niego perspektywy zmaterializowanej (przypominamy, że perspektywa zmaterializowana to perspektywa, której zawartość jest obliczana i zapisywana w tabeli, w regularnych odstępach czasu) z założonym odpowiednim indeksem pogrupowanym pamiętając, że zapytanie będzie wykonywane szybko ale kosztem aktualizacji perspektywy zmaterializowanej i zwiększenia zajętości miejsca na dysku? Na przykład, czy zamiast liczyć przy każdym zapytaniu statystykę stanu kont bankowych nie warto, mieć ją obliczoną raz na dzień lub raz na godzinę?
Jeszcze krótkie podsumowanie projektowania indeksów:
Emp.Job='MANAGER'
przy czym istotne jest aby wyszukiwanie było selektywne tj. aby procent wyszukiwanych wierszy nie był zbyt duży,
powiedzmy co najwyżej 5 do 10%;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)
|
|
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)
|
|
Wystarczy dowolny indeks na E.Deptno
, ponieważ nie trzeba przechodzić do
pliku rekordów tabeli E.
(c)
|
|
Przydałby się indeks drzewowy na <E.Deptno
, E.sal
>.
Wtedy nie trzeba byłoby przechodzić do pliku rekordów tabeli E.
(d)
|
|
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
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.
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.
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:
Miasta(Id_miasta, Nazwa_miasta)
Klienci(Id_miasta, Id_klien_w_miescie, Nazwisko, Hobby, Wiek)
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;
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.
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 BYz.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:
- Konta(Id_konta, Saldo, Imie, Nazwisko, Adres)
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.
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';
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.
pole działania - składa się z informacji o aplikacji bazy danych:
jakie są najważniejsze zapytania i jak często będą używane,
jakie są najważniejsze aktualizacje i jak często będą używane,
jaka jest pożądana szybkość działania tych zapytań i aktualizacji.
SELECT E.Mgr, COUNT(*)
FROM Emp E
GROUP BY E.Mgr;
SELECT E.Ename
FROM Emp E, Dept D
WHERE E.Deptno=D.Deptno AND
D.Dname='SALES'
ORDER BY e.Empno;
SELECT e.Dname, COUNT(*)
FROM Emp E, Dept D
WHERE E.Deptno=D.Deptno AND
E.Job = 'SALESMAN'
GROUP BY e.Deptno, e.Dname;
SELECT E.Ename, D.Dname
FROM Emp E, Dept D
WHERE E.Deptno=D.Deptno AND
E.Job = 'SALESMAN'
ORDER BY e.Empno;
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).