Politechnika Krakowska im. T. Kościuszki
INSTYTUT INFORMATYKI STOSOWANEJ M-7
Esej o trudnej SELEKTYWNOÅšCI? Czyli o optymalizacji inaczej.
Nr 00
Bazy danych II nieLABORATORIUM Czas [min]: Nr 00
Nr 00
Nr 00
jak długo tylko
chcesz
1. Cel
Próba przybliżenia z czym  zjeść SELEKTYWNOŚĆ i aby zrozumieć wyrażenie do
obliczania selektywności, które wydaje się być trudne, podaje prawidłowe (prawdopodobne)
wyniki, ale większość użytkowników nie wie, dlaczego!
2. SELEKTYWNOŚĆ, której nie rozumiemy
Chyba nie wszyscy rozumiemy, jak istotna może być selektywność (filtra zapytania)?
Człowiek od optymalizacji to zazwyczaj nowy pracownik właśnie przyjęty na stanowisko
analityka, może administratora, o stosunkowo niewielkim doświadczeniu  to w Polsce lub
administrator, który  zjadł zęby na Oraclu, a Oracle University nie może mu zaoferować już
żadnego szkolenie, którego sam nie mógłby prowadzić  to w UE i USA.
Mój faworyt: Donald K. Burleson (spójrz tu: http://www.dba-oracle.com/redneck.htm )  ale
jego poniższe rozumowanie się nie tyczy  mój pełny szacunek.
Otóż, jeśli  gość ą i &! od optymalizacji (patrz Figura :) 1.  tak mógłby wyglądać) dostanie
Ä… &!
Ä… &!
Ä… &!
bazÄ™ developerskÄ… do strojenia (albo produkcyjnÄ…, ale to inny przypadek - gorszy), to:
1. Próbuje zoptymalizować przepływy informacji na poziomie powiązań tabel, ale:
Uuuu! Wydawało mi się, że baza będzie mniejsza - mniej tabel, który program to
wygenerował, a może programiści  wrrr! Trzeba przeanalizować przepływy
wszystkich kluczy, ale to skomplikowane  mnóstwo roboty! A co ze wszystkimi
zapytaniami, insertami, updatami, jak coÅ› wyrzucÄ™?
2. Próbuje zoptymalizować działanie instancji:
No wreszcie mogę iść na całość, mam serwer developerski, to nic, że programiści
coś tam piszą, a testerzy już próbują testować (ich wina, że mnie tak póz
no
zatrudnili), trochę resetów serwera nie powinno zaszkodzić.
3. Tuning sprzętu (głównie I/O):
Na tym serwerze nic nie zdziałam (zbyt archaiczny), a macierz dyskowa  pogadam z
adminami, może coś wymyślimy. Wiem!!! Każemy klientowi kupić szybki sprzęt,
macierz z dyskami FC 15k (interfejs FC 4Gb/s, 15 tys. obrotów) i niech ma możliwość
wirtualizacji i zwielokrotniania portów i... , tylko czy będzie to potrzebne do tej
aplikacji, a jego na to stać? Cóż, zobaczymy!
4. Optymalizacja SQL
Hmm! Ustaliłem, że w tej aplikacji czas wprowadzania danych nie jest najistotniejszy,
ale selct-y, pasuje, aby wykonywały się szybciej niż teraz, bo jak będzie więcej
danych to user pomyśli, że mu się program zawiesił! Dobrze, skupię się więc na
SQL-u!
BD © 2006-2007 Dariusz Karpisz Politechnika Krakowska im. T.KoÅ›ciuszki
1
Uwaga!
Nasz niebieski bohater jest dość specyficzną osobą  traktujmy jego wypowiedzi
z dystansem. Opisany przypadek może być modelowy (i częsty). Optymalizacja nie musi
odbywać się w tej kolejności i w takich krokach (<- a to żeby nieco skomplikować sprawę jak
na Oracle przystało  polecam kluby dla  nienawidzących Oracle , np.:
http://forums.worsethanfailure.com/forums/post/25910.aspx ).
Figura :) 1. Stallman jako święty Ignucy.
"Jestem święty Ignucy z Kościoła Emacs - powiedział, wznosząc prawą rękę w geście szyderczego
błogosławieństwa. - Błogosławię twój komputer, moje dziecko".
[Zdjęcia: Woutera van Oortmerssena, Tekst: Sam Williams, W obronie wolności, Helion].
WNIOSEK 1
Hmm! Z powyższych dywagacji wynika, że najbardziej opłacalna jest
optymalizacja ... SQL-a, TAK! Gratuluję wszystkim, którzy właśnie się ze mną
zgodzili :), choć nie twierdzę, że mam całkowitą rację!
Dobrze, więc zobaczmy, o co chodzi?
Dla naszego systemu developerskiego dostaliśmy trochę danych rzeczywistych, aby zasilić
bazę danych. Napiszemy też generatory danych, żeby wstawić w insert-ach tyle danych, aby
baza przypominała coś, co funkcjonuje w podobnej objętości w świecie rzeczywistym.
Oczywiście zakładam, że jesteśmy w stanie napisać takie generatory (w pakiecie  a jakże),
może wykorzystujące kolekcje (tak, tak, ... składowane w tabelach zagnieżdżonych jako
obiekty tabel relacyjnych). Zasilamy bazę danymi zbliżonymi do rzeczywistych!
Åšwietnie!
A jak szybko baza będzie rosła?
Przeanalizowałem sytuację z klientem. Mniej więcej wiem, jak wiele danych będzie
przybywać w stosunku miesięcznym/rocznym. Niestety w niektórych tabelach nie będzie zbyt
optymistycznie  rosną .... (: , a zapytania do nich są dość często wykonywane. Może je
zmienić, inaczej zapisać, zmienić warunki wyszukiwania, tabele sterujące, ...
Ale, zaraz, zaraz, a ile właściwie wierszy będzie zwracało to zapytanie (ile czasu i zasobów
pożre)? Sprawdzę na naszej bazie developerskiej.  ok. 200 tys., A gdy przybędzie danych,
to ile???
Obliczę selektywność filtra zapytania!
BD © 2006-2007 Dariusz Karpisz Politechnika Krakowska im. T.KoÅ›ciuszki
2
Przykład jest prosty: Nasza tabela testowa nie jest skomplikowana, ale,.. ma 2 mln wierszy,
więc można już coś pokazać (Figura 2).
Figura 2. Tabela testowa  oczywiście można jeszcze prościej.
Przypadek 1  prognozowana duża selektywność
Otóż mamy do czynienia z zapytaniem (Figura 3), które zwraca stosunkowo niedużą ilość
wierszy ( stosunkowo , to chyba najlepsze określenie, jakie udało mi się dopasować,
a zaraz zobaczymy, że chyba słusznie).
Figura 3. Zapytanie, którego nie mogłem już uprościć.
Obliczmy selektywność, jak pokazuje Figura 4  będziemy wiedzieli (z pewnym
prawdopodobieństwem), o ile wierszy więcej (%) zwróci zapytanie, jeśli zwiększy się ilość
danych.
Oczywiście, aby powyższe stwierdzenie było prawdziwe, musimy przyjąć, że rozkład danych
(statystyczny) nie zmieni się, tzn. proporcje różnych wartości w ramach wybieranej kolumny
będą podobne (cóż  tu posiłkujemy się badaniem histogramów, ale to inne zagadnienie).
BD © 2006-2007 Dariusz Karpisz Politechnika Krakowska im. T.KoÅ›ciuszki
3
Figura 4. Zapytanie, którego nie mogłem już uprościć i jego selektywność.
Jak widać (Figura 4), selektywność jest obliczana jako stosunek ilości wystąpień danej
wartości do ilości wszystkich wierszy w tabeli.
Ale skąd mamy wiedzieć, że prognozowana jest duża selektywność?
Tu jest pewien problem. Tak naprawdę trzeba mieć wiedzę o znaczeniu tej tabeli i częstości
zmiany kardynalności danych w kolumnach tej tabeli. Czyli, robimy to niejako  na wyczucie .
Przypadek 2  prognozowana bardzo duża selektywność
Tym razem przykład będzie wręcz trywialny (Figura 5). Warunek sprawdza zgodność
podanej wartości z wartościami dla klucza unikatowego tabeli. Już na pierwszy rzut oka
widać, że selektywność tego filtra to (1 / ilo wierszy).
Co więcej, selektywność będzie równa dla wszystkich wartości porównywanych w tym
warunku, bo ile jest ASBk_1_ID o numerze 333? Oczywiści 1 na 200000 wierszy lub ... 0.
Figura 6. Kolejny  prosty przykład.
BD © 2006-2007 Dariusz Karpisz Politechnika Krakowska im. T.KoÅ›ciuszki
4
Jeśli chcemy potraktować problem szerzej, to właściwe powinno być stwierdzenie, że
prawdopodobieństwo wystąpienia danej wartości dla kardynalności dążącej do
nieskończoności to:
(1 / ilo _unikatowych_warto ci_w_tabeli)
Teraz powinno być oczywiste, czemu zamiast count(*) stosujemy w wyrażeniu SQL zapis
count(distinct(kolumna)).
Przypadek 3  prognozowana niska selektywność
Jeśli czytasz ten tekst, to muszę ci uświadomić, że dotarliśmy do przypadku, który jest
kwintesencją rozważań w tym opracowaniu.
Figura 7. Zapytanie, którego nie mogłem już uprościć o nietrywialnej selektywności.
Przeanalizujmy przykład pokazany na Figurze 7. Wydaje się być prosty i od strony użytkowej
taki właśnie jest, ale jak obliczyć selektywność wiedząc, że kardynalność kolumny
ASB_MaxRabat jest bardzo mała, tzn. kolumna przyjmuje wartości z niewielkiego (pytanie,
jak małego?) zbioru danych? Zakładamy również, że w przyszłości kardynalność tej kolumny
nie zmieni siÄ™ znaczÄ…co.
Zapytanie zwróciło dokładnie:
222582/2000000 wierszy a" 11.13% wierszy tabeli
Ale jak to przewidzieć?
W takim przypadku stosuje się podejście pokazane na Figurze 8.
Figura 8. Bardziej uniwersalny sposób obliczania  trudnej selektywności.
BD © 2006-2007 Dariusz Karpisz Politechnika Krakowska im. T.KoÅ›ciuszki
5
Najpierw przeanalizujemy podejście probabilistyczne do tego problemu, a następnie samo
wyrażenie do obliczania selektywności zapisane w SQL. (Proszę czytać uważnie!)
1. Wybieramy wiersze z kolumny o małej kardynalności, czyli mówiąc żargonem
probabilistycznym, istnieje duże prawdopodobieństwo wybierania wierszy o
często występujących wartościach. W naszym przypadku to 9 unikalnych wartości
dla próbki 2 mln wierszy (Figura 9)!
Figura 9. Kardynalność dla kolumny ASB_MaxRabat.
Podobne przypadki występują bardzo często w rzeczywistych bazach danych. Np.
dla systemów obsługujących duże grupy ludności istnieje duże
prawdopodobieństwo obsługi petentów o nazwisku  Kowalski , a relatywnie
mniejsze dla nazwiska  Karpisz . Podobne zasady można znalez
ć w obrębie wielu
dziedzin niekoniecznie związanych z obsługą danych teleadresowych.
W systemie kart szpitalnych pacjentów, z pewnością wielu z nich dostaje ten sam
środek przeciwbólowy, a lista środków farmakologicznych jest skończona.
2. Jak wynika z punku 1., prawdopodobieństwo wylosowania danej wartości jest
większe dla kryterium wyszukiwania  Kowalski niż dla  Karpisz . Zakładając
losowy rozkład danych i różną liczebność w obrębie danej, unikalnej wartości,
możemy stwierdzić, że byłoby błędne stwierdzenie, że dla każdej, unikatowej
wartości prawdopodobieństwo jest równe.
W rozpatrywanym przypadku nie powinniśmy zatem przyjmować dla każdej
wartości prawdopodobieństwa 1/9 z pośród wszystkich wierszy.
3. Selektywność całkowita powinna być sumą selektywności cząstkowych dla każdej
unikatowej wartości kolumny:
Selektywno = ( n(i) / cont(*) )
gdzie:
n(i)  ilość wystąpień i-tej niepustej wartości kolumny,
cont(*)  ilość wszystkich wierszy tabeli.
Czyli, suma z ilości wystąpień danej, niepustej wartości przez ilość wierszy tabeli.
4. No dobrze, ale co z wartościami NULL? Nasza metoda jest obarczona błędem.
Zróbmy więc tak:
( n(i) / cont(i) )
gdzie:
cont(i)  ilość wszystkich wierszy tabeli o niepustych wartościach
kolumny filtra.
Teraz obliczamy selektywność w odniesieniu do wszystkich niepustych wartości
kolumny. Należy jednak zauważyć, że wyrażenie cont(i)jest równe sumie
liczby wystąpień wszystkich niepustych, unikalnych wartości tej kolumny:
n(i), a wiec zapis selektywności powinien wyglądać tak:
( n(i) / ( n(i)) )
BD © 2006-2007 Dariusz Karpisz Politechnika Krakowska im. T.KoÅ›ciuszki
6
5. Jesteśmy już blisko. Aby nasze obliczenia końcowe były zgodne
z rzeczywistością, należy pomnożyć sumę selektywności cząstkowych
i prawdopodobieństw ich wystąpienia, czyli:
( n(i) / cont(i) ) * ( n(i) / ( n(i)) )
przekształcamy do postaci (szkolna matematyka):
( n(i) * n(i) ) <- wyra enie 1
/
( cont(i) * ( n(i)) ) <- wyra enie 2
6. No dobrze, może już niektórzy z nas po kilkukrotnym przeczytaniu tych punktów
wiedzą jak to działa (oczywiście z pewną dozą prawdopodobieństwa).
Spróbujmy zapisać powyższe w SQL-u.
Chcemy analizować wszystkie unikatowe wartości  do dyspozycji mamy dwie
metody:
a) Napisanie wyrażeń z DISTINCT, ale to chyba zły pomysł, bo nie grupuje
wartości,
b) Napisanie zapytania z wykorzystaniem funkcji grupujÄ…cych  genialnie!
Efekt nie wymaga komentarzy:
select &
from TABELA
group by Grupowana_kolumna;
Zapiszmy teraz pełne wyrażenie na liście wybieranych kolumn, zgodnie z tym, co
napisano w punkcie 5:
select
sum(count(kolumna) * count(kolumna)) <- wyra enie 1
/
( sum(count(kolumna)) * sum(count(*)) ) <- wyra enie 2
from TABELA
group by kolumna;
I to wszystko!
Ups! Nie mówiliśmy o indeksach  tu też mamy możliwość sprawdzania selektywności, ale o
tym być może następnym razem.
WNIOSEK 2
Wybór metody obliczania selektywności nie jest oczywisty! Duże znaczenie
ma dobre zrozumienie tematu w jakim operuje zapytanie tj. zrozumienie
wybieranych danych. Ponadto musimy wiedzieć jak dane będą się zmieniać
w przyszłości.
Musimy więc spoglądać w przyszłość
 w końcu ang. oracle to WYROCZNIA!
(PS. Niestety  oracle po francusku to WYROK!)
BD © 2006-2007 Dariusz Karpisz Politechnika Krakowska im. T.KoÅ›ciuszki
7