KZ BD w14 2 id 256670 Nieznany

background image

Bazy danych – wykład dwunasty

Wykonywanie i optymalizacja zapyta ´n SQL

Konrad Zdanowski

Uniwersytet Kardynała Stefana Wyszy ´nskiego, Warszawa

Konrad Zdanowski ( Uniwersytet Kardynała Stefana Wyszy ´nskiego, Warszawa)

Bazy danych – wykład dwunasty Wykonywanie i optymalizacja zapyta ´n SQL

1 / 36

background image

Model kosztów

Paremtry okre´slaj ˛

ace rozmiar relacji R:

B(R) – liczba bloków jakie zajmuje R (b ˛edziemy zakłada´c, ˙ze
relacja jest sklastrowana),

T (R) – liczba krotek w relacji R,

V (R, A) – liczba

róznych warto´sci atrybutu A w R,

V (R[a

1

, . . . ,

a

k

])

– liczba

róznych krotek o warto´sci atrybutów

a

1

, . . . ,

a

k

w R

Szacuj ˛

ac koszty wykonania zapytania minimalizujemy liczb ˛e operacji

I/O.

Konrad Zdanowski ( Uniwersytet Kardynała Stefana Wyszy ´nskiego, Warszawa)

Bazy danych – wykład dwunasty Wykonywanie i optymalizacja zapyta ´n SQL

2 / 36

background image

Model kosztów

Dla sklastrowanej relacji R koszt wczytania relacji to B(R).

Koszt sortowania relacji R, je´sli ta mie´sci si ˛e w cało´sci w pami ˛eci
operacyjnej, to równie˙z B(R).

Konrad Zdanowski ( Uniwersytet Kardynała Stefana Wyszy ´nskiego, Warszawa)

Bazy danych – wykład dwunasty Wykonywanie i optymalizacja zapyta ´n SQL

3 / 36

background image

Podstawowe operacje na relacjach – przypomnienie

Niech R(A

1

, . . . ,

A

k

),

S(B

1

, . . . ,

B

n

)

dane relacje.

Rzutowanie

π

A

1

,...,

A

m

(

R) = {(a

1

, . . . ,

a

m

)

:

istniej ˛

a a

m+1

, . . . ,

a

k

, takie, ˙ze (a

1

, . . . ,

a

m

,

a

m+1

, . . . ,

a

k

)

R}.

Oczywi´scie, mo˙zemy wybra´c w rzutowaniu dowolne atrybuty.

Dla warunku C na krotki relacji R,

σ

C

(

R) = {(a

1

, . . . ,

a

k

) :

C(a

1

, . . . ,

a

k

)}.

Konrad Zdanowski ( Uniwersytet Kardynała Stefana Wyszy ´nskiego, Warszawa)

Bazy danych – wykład dwunasty Wykonywanie i optymalizacja zapyta ´n SQL

4 / 36

background image

Podstawowe operacje na relacjach – przypomnienie

Niech R(A, B, C, D), S(C, D, E ) dane relacje.

Zł ˛

aczenie

R o

n S = {(a, b, c, d , e) : (a, b, c, d ) R (c, d , e) S}.

Zł ˛

aczenie warunkowe dla warunku Θ,

R o

n

Θ

S = {(a, b, c, d , e) : (a, b, c, d ) R (c, d , e) S

Θ(

a, b, c, d , e)}.

Konrad Zdanowski ( Uniwersytet Kardynała Stefana Wyszy ´nskiego, Warszawa)

Bazy danych – wykład dwunasty Wykonywanie i optymalizacja zapyta ´n SQL

5 / 36

background image

Koszt pewnych operacji jednoargumentowych

Uwaga. Zajmiemy si ˛e kosztem operacji jednoprzebiegowych. Tzn.
tylko raz wczytujemy dan ˛

a krotk˛e i cały wynik albo zmie´sci si ˛e w

pami ˛eci operacyjnej albo mo˙zemy go generowa´c “online”.

Algorytm naiwny – dla ka˙zdej nowej krotki sprawdzamy, czy ju˙z
nie wyst ˛

apiła – ma koszt n

2

(dla n – krotek wyniku – to problem

cho´c oczywi´scie nie zmieniamy ilo´sci operacji I/O).

Tablice z haszowaniem optymalizuj ˛

a ten koszt wymagaj ˛

ac

dodatkowej pami ˛eci.

Operacje agreguj ˛

ace – mo˙zemy oblicza´c podczas tworzenia

kolejnych krotek wynikowej relacji.

Konrad Zdanowski ( Uniwersytet Kardynała Stefana Wyszy ´nskiego, Warszawa)

Bazy danych – wykład dwunasty Wykonywanie i optymalizacja zapyta ´n SQL

6 / 36

background image

Koszt operacji dwuargumentowych

Rozwa˙zmy operacje sumy, iloczyny, ró˙znicy dla wielozbiorów i zbiorów
(bez powtórze ´n).

Niech M liczba wolnych buforów w pami ˛eci operacyjnej.

Suma wielozbiorów dla relacji R i S to B(R) + B(S).

Dla róznicy i iloczynu musimy wczyta´c mniejsz ˛

a relacj ˛e do

pami ˛eci operacyjnej, czyli musi by´c spełniony warunek
min(B(R), B(S)) ¬ M(1).

Dla operacji na zbiorach (bez powtórze ´n) musimy wczyta´c
mniejsz ˛

a relacj ˛e i zarezerwowa´c dodatkow ˛

a pami ˛e´c na struktury

pomocnicze (jak tablice haszuj ˛

ace). W przybli˙zeniu mamy wi ˛ec

wymóg min(B(R), B(S)) ¬ M.

Konrad Zdanowski ( Uniwersytet Kardynała Stefana Wyszy ´nskiego, Warszawa)

Bazy danych – wykład dwunasty Wykonywanie i optymalizacja zapyta ´n SQL

7 / 36

background image

Koszt zł ˛

aczenia

Rozpatrzmy zł ˛

aczenie R(A, B) o

n S(B, C).

Naiwny algorytm wymaga B(R)B(S) operacji wczytania.

Je´sli mamy M buforów, mo˙zemy wczytywa´c po M 1 bloków
relacji R i nast ˛epnie wczytywa´c po jednym bloku z S aby stworzy´c
zł ˛

aczenie.

Koszt wyniesie około B(R)B(S)/M.

Konrad Zdanowski ( Uniwersytet Kardynała Stefana Wyszy ´nskiego, Warszawa)

Bazy danych – wykład dwunasty Wykonywanie i optymalizacja zapyta ´n SQL

8 / 36

background image

Koszt operacji dwuargumentowych

Zauwa˙zmy, ˙ze koszt tych operacji mo˙zemy istotnie zmniejszy´c
przy zastosowaniu dodatkowyc struktur danych (np. tablic
haszuj ˛

acych, indeksów).

Np. je´sli na B jest nało˙zony indeks w R lub S, mo˙zemy efektywnie
znajdowa´c krotki, które wejd ˛

a do zł ˛

aczenia. Koszt zł ˛

aczenia

b ˛edzie wtedy optymalny.

Konrad Zdanowski ( Uniwersytet Kardynała Stefana Wyszy ´nskiego, Warszawa)

Bazy danych – wykład dwunasty Wykonywanie i optymalizacja zapyta ´n SQL

9 / 36

background image

Przetwa˙zanie zapytania SQL

Elementy procesu wykonywania zapytania:

kompilacja zapytania (przedstawienie zapytania w “optymalnej”
postaci logicznej,

wykonywanie zapytania.

Aby wykonanie przebiegło efektywnie potrzebujemy zdefiniowa´c
cz ˛esto dodatkowe struktury danych (np. indeksy).

Konrad Zdanowski ( Uniwersytet Kardynała Stefana Wyszy ´nskiego, Warszawa)

Bazy danych – wykład dwunasty Wykonywanie i optymalizacja zapyta ´n SQL

10 / 36

background image

Kompilowanie zapytania SQL

Elementy procesu kompilowania zapytania:

zapisanie zapytania w postaci wyra˙zenia algebry relacji (drzewo
zapytania),

wybranie optymalnej, z równowa˙znych, postaci zapytania,

wybranie algorytmów przetwa˙zania bazy danych.

Aby wykonanie przebiegło efektywnie potrzebujemy zdefiniowa´c
cz ˛esto dodatkowe struktury danych (np. indeksy).

Konrad Zdanowski ( Uniwersytet Kardynała Stefana Wyszy ´nskiego, Warszawa)

Bazy danych – wykład dwunasty Wykonywanie i optymalizacja zapyta ´n SQL

11 / 36

background image

Drzewo zapytania – przykład

select tytul from Ksiazki where rok == 2011;

π

tytul

σ

rok=2011

Ksiazki

Konrad Zdanowski ( Uniwersytet Kardynała Stefana Wyszy ´nskiego, Warszawa)

Bazy danych – wykład dwunasty Wykonywanie i optymalizacja zapyta ´n SQL

12 / 36

background image

Drzewo zapytania – przykład

select tytul from Ksiazki where rok = 2011 and wydawca = ’Znak’;
Które z drzew da efektywniejsze wykonanie?

π

tytul

σ

rok=2011

σ

rok=’Znak’

Ksiazki

π

tytul

σ

rok=2011rok=’Znak’

Ksiazki

Oba plany s ˛

a równowa˙zne, bo σ

CD

(

R) = σ

C

(σ

D

(

R)).

Konrad Zdanowski ( Uniwersytet Kardynała Stefana Wyszy ´nskiego, Warszawa)

Bazy danych – wykład dwunasty Wykonywanie i optymalizacja zapyta ´n SQL

13 / 36

background image

Drzewo zapytania – przykład

select nazwisko, tytul from Ksiazki, Autorzy where Ksiazki.autor_id =
Autorzy.id;

π

nazwisko, tytul

σ

Ksiazki.autor_id=Autorzy.id

×

Ksiazki

Autorzy

Konrad Zdanowski ( Uniwersytet Kardynała Stefana Wyszy ´nskiego, Warszawa)

Bazy danych – wykład dwunasty Wykonywanie i optymalizacja zapyta ´n SQL

14 / 36

background image

Drzewo zapytania – przykład

select nazwisko, tytul from Ksiazki, Autorzy where Ksiazki.autor_id =
Autorzy.id and rok=2011;

Które plan jest lepszy? Ci zmienia (prawdopodobna) obecno´s´c
indeksu na atrybucie, po którym zł ˛

aczamy?

π

nazwisko, tytul

σ

Ksiazki.autor_id=Autorzy.idrok=2011

×

Ksiazki

Autorzy

π

nazwisko, tytul

σ

Ksiazki.autor_id=Autorzy.id

×

σ

rok=2011

Ksiazki

Autorzy

Konrad Zdanowski ( Uniwersytet Kardynała Stefana Wyszy ´nskiego, Warszawa)

Bazy danych – wykład dwunasty Wykonywanie i optymalizacja zapyta ´n SQL

15 / 36

background image

Optymalizacja zapytania

Stworzenie reprezentacji algebraicznej.

Eliminacja (je´sli mo˙zliwa) podzapyta ´n.

Transformacje algebraiczne w algebrze relacji.

Zdefiniowanie porz ˛

adku wykonywania zł ˛

acze ´n i innych operacji.

Po tych krokach nast ˛epuj ˛e wybór konkretnych algorytmów
operuj ˛

acych na bazie danych.

Konrad Zdanowski ( Uniwersytet Kardynała Stefana Wyszy ´nskiego, Warszawa)

Bazy danych – wykład dwunasty Wykonywanie i optymalizacja zapyta ´n SQL

16 / 36

background image

Analiza semantyczna zapytania

Po stworzeniu reprezentacji algebraicznej mo˙zemy upro´sci´c
zapytanie korzystaj ˛

ac z praw logicznych oraz arytmetycznych.

W szczególno´sci mo˙zemy wyeliminowac warunki (i zapytania)
sprzeczne.

Konrad Zdanowski ( Uniwersytet Kardynała Stefana Wyszy ´nskiego, Warszawa)

Bazy danych – wykład dwunasty Wykonywanie i optymalizacja zapyta ´n SQL

17 / 36

background image

Transformacja zapytania

Korzystaj ˛

ac z praw algebry relacji mo˙zemy upro´sci´c i

zoptymalizowa´c dane zapytanie

Oprócz metod “aksjomatycznych” stosowa´c mo˙zna te˙z analizy
statystyczne, szacowanie kosztów w oparciu o statystyki działania
bazy danych (pracochłonne i kosztowne).

Operacje unarne (filtruj ˛

ace) przesuwamy w dół drzewa zapytania.

Operacje binarne przesuwamy w góre.

Zł ˛

aczenia najlepiej definiowa´c na atrybutach, na których mamy

zdefiniowany indeks.

Konrad Zdanowski ( Uniwersytet Kardynała Stefana Wyszy ´nskiego, Warszawa)

Bazy danych – wykład dwunasty Wykonywanie i optymalizacja zapyta ´n SQL

18 / 36

background image

Przykładowe prawa algebry relacji

R o

n (S o

n T ) = (R o

n S) o

n T ,

R o

n (S T ) = (R o

n S) (R o

n T ),

σ

CD

(

R) = σ

C

(σ

D

(

R)) = σ

C

(

R) ∩ σ

D

(

R),

σ

CD

(

R) = σ

C

(

R) ∪ σ

D

(

R),

Konrad Zdanowski ( Uniwersytet Kardynała Stefana Wyszy ´nskiego, Warszawa)

Bazy danych – wykład dwunasty Wykonywanie i optymalizacja zapyta ´n SQL

19 / 36

background image

Przykładowe prawa algebry relacji

σ

C

(

R S) = σ

C

(

R) S,

je´sli C zawiera tylko predykaty z R to

σ

C

(

R o

n S) = σ

C

(

R) o

n S,

je´sli M = N Q, gdzie N to atrybuty z R a Q to atrybuty z S (i N i
Q zawieraj ˛

a atrybuty, po których obliczamy zł ˛

aczenie), to

π

M

(

R o

n S) = π

N

(

R) o

n π

Q

(

S),

je´sli M nie zawiera atrybutów Z , po których obliczamy zł ˛

aczenie,

to

π

M

(

R o

n S) = π

NZ

(

R) o

n π

QZ

(

S).

Konrad Zdanowski ( Uniwersytet Kardynała Stefana Wyszy ´nskiego, Warszawa)

Bazy danych – wykład dwunasty Wykonywanie i optymalizacja zapyta ´n SQL

20 / 36

background image

Przykłady

Niech dane R(A, B) i S(B, C).

Czy lepsze jest σ

A=a

(

R o

n S) czy σ

A=a

(

R) o

n S?

Czy lepsze jest σ

A=aC=c

(

R o

n S) czy σ

A=a

(

R) o

n σ

C=c

(

S)?

Czy σ

A=aC=c

(

R o

n S), czy σ

A=a

(

R o

n S) ∪ σ

C=c

(

R o

n S), czy

(σ

A=a

(

R) o

n S) (R o

n σ

C=c

(

S)?

Czy co´s mog ˛

a zmieni´c indeksy na atrybutacie C?

Konrad Zdanowski ( Uniwersytet Kardynała Stefana Wyszy ´nskiego, Warszawa)

Bazy danych – wykład dwunasty Wykonywanie i optymalizacja zapyta ´n SQL

21 / 36

background image

Optymalizacja podzapyta ´n

Podzapytanie wymaga obliczenia dla ka˙zdej krotki, która mo˙ze
nale˙ze´c do wyniku.

Trudno optymalizowa´c razem zapytanie i podzapytanie.
Optymalizuj ˛

ac je oddzielnie mo˙zemy pomin ˛

a´c pewne mo˙zliwo´sci

uproszczenia.

Zmniejszenie kosztów mo˙zna (czasem) osi ˛

agn ˛

a´c przez

eleminacje podzapytania.

Konrad Zdanowski ( Uniwersytet Kardynała Stefana Wyszy ´nskiego, Warszawa)

Bazy danych – wykład dwunasty Wykonywanie i optymalizacja zapyta ´n SQL

22 / 36

background image

Przykład - optymalizacja podzapyta ´n

Jak zooptymalizowa´c to zapytanie?

s e l e c t a . nazwisko , a . mi as t o

from A u t o r z y a
where a . r o k _ u r o d z e n i a >1980 and

a . i d

i n ( s e l e c t k . a u t o r _ i d

from K s i a z k i k
where k . rok_wydania < 2000 ) ;

Konrad Zdanowski ( Uniwersytet Kardynała Stefana Wyszy ´nskiego, Warszawa)

Bazy danych – wykład dwunasty Wykonywanie i optymalizacja zapyta ´n SQL

23 / 36

background image

Przykład - optymalizacja podzapyta ´n

s e l e c t a . nazwisko , a . mi as t o

from A u t o r z y a , K s i a z k i k
where a . r o k _ u r o d z e n i a >1980

and

k . rok_wydania < 2000

and a . i d = k . a u t o r _ i d ;

Konrad Zdanowski ( Uniwersytet Kardynała Stefana Wyszy ´nskiego, Warszawa)

Bazy danych – wykład dwunasty Wykonywanie i optymalizacja zapyta ´n SQL

24 / 36

background image

Przykład - optymalizacja podzapyta ´n

s e l e c t a . nazwisko , a . mi as t o

from A u t o r z y a
where a . p l e c = ’ F ’

and

k . r o k _ u r o d z e n i a <=

ALL ( s e l e c t b . r o k _ u r o d z e n i a

from A u t o r z y b
where b . p l e c = ’ F ’

and a . m i a s t o _ u r o d z e n i a =

b . m i a s t o _ u r o d z e n i a ) ;

Konrad Zdanowski ( Uniwersytet Kardynała Stefana Wyszy ´nskiego, Warszawa)

Bazy danych – wykład dwunasty Wykonywanie i optymalizacja zapyta ´n SQL

25 / 36

background image

Przykład - optymalizacja podzapyta ´n

Obliczmy zbiór “nie najmłodszych” autorek:

s e l e c t a . nazwisko , a . mi as t o

from A u t o r z y a
where a . p l e c = ’ F ’

and

k . r o k _ u r o d z e n i a >

SOME ( s e l e c t b . r o k _ u r o d z e n i a

from A u t o r z y b
where b . p l e c = ’ F ’

and a . m i a s t o _ u r o d z e n i a =

b . m i a s t o _ u r o d z e n i a ) ;

Konrad Zdanowski ( Uniwersytet Kardynała Stefana Wyszy ´nskiego, Warszawa)

Bazy danych – wykład dwunasty Wykonywanie i optymalizacja zapyta ´n SQL

26 / 36

background image

Przykład - optymalizacja podzapyta ´n

Zoptymalizujmy ostatnie zapytanie:

s e l e c t a . nazwisko , a . mi as t o

from A u t o r z y a , A u t o r z y b
where a . p l e c = ’ F ’

and b . p l e c = ’ F ’

and a . m i a s t o _ u r o d z e n i a = b . m i a s t o _ u r o d z e n i a
and a . r o k _ u r o d z e n i a > b . r o k _ u r o d z e n i a ;

Konrad Zdanowski ( Uniwersytet Kardynała Stefana Wyszy ´nskiego, Warszawa)

Bazy danych – wykład dwunasty Wykonywanie i optymalizacja zapyta ´n SQL

27 / 36

background image

Przykład - optymalizacja podzapyta ´n

Odejmijmy:

(

s e l e c t a . nazwisko , a . mi as t o

from A u t o r z y a
where a . p l e c = ’ F ’ )

except

(

s e l e c t a . nazwisko , a . mi as t o

from A u t o r z y a , A u t o r z y b
where a . p l e c = ’ F ’

and b . p l e c = ’ F ’

and a . m i a s t o _ u r o d z e n i a = b . m i a s t o _ u r o d z e n i a
and a . r o k _ u r o d z e n i a > b . r o k _ u r o d z e n i a ; )

Konrad Zdanowski ( Uniwersytet Kardynała Stefana Wyszy ´nskiego, Warszawa)

Bazy danych – wykład dwunasty Wykonywanie i optymalizacja zapyta ´n SQL

28 / 36

background image

Przesuwanie predykatów

π

nazwisko, tytul

σ

rok=2011

o

n

Ksiazki.autor_id=Autorzy.id

Ksiazki

Autorzy

π

nazwisko, tytul

o

n

Ksiazki.autor_id=Autorzy.id

σ

rok=2011

Ksiazki

Autorzy

Konrad Zdanowski ( Uniwersytet Kardynała Stefana Wyszy ´nskiego, Warszawa)

Bazy danych – wykład dwunasty Wykonywanie i optymalizacja zapyta ´n SQL

29 / 36

background image

Przesuwanie predykatów

s e l e c t w . nazwa , Min ( a . r o k _ u r o d z e n i a )

from Wydawnictwa w, A u t o r z y a
where w . a u t o r _ i d = a . i d
group by w . nazwa
having Min ( a . r o k _ u r o d z e n i a ) <=1939;

s e l e c t w . nazwa , Min ( a . r o k _ u r o d z e n i a )

from Wydawnictwa w, A u t o r z y a
where w . a u t o r _ i d = a . i d

and a . r o k _ u r o d z e n i a <=1939
group by w . nazwa ;

Konrad Zdanowski ( Uniwersytet Kardynała Stefana Wyszy ´nskiego, Warszawa)

Bazy danych – wykład dwunasty Wykonywanie i optymalizacja zapyta ´n SQL

30 / 36

background image

Przesuwanie predykatów

Czy tak te˙z mo˙zna?

s e l e c t w . nazwa , Min ( a . r o k _ u r o d z e n i a )

from Wydawnictwa w, A u t o r z y a
where w . a u t o r _ i d = a . i d
group by w . nazwa
having Min ( a . r o k _ u r o d z e n i a ) >1939;

s e l e c t w . nazwa , Min ( a . r o k _ u r o d z e n i a )

from Wydawnictwa w, A u t o r z y a
where w . a u t o r _ i d = a . i d

and a . r o k _ u r o d z e n i a >1939
group by w . nazwa ;

Konrad Zdanowski ( Uniwersytet Kardynała Stefana Wyszy ´nskiego, Warszawa)

Bazy danych – wykład dwunasty Wykonywanie i optymalizacja zapyta ´n SQL

31 / 36

background image

Optymalizacja zapytania – heurystyka

Selekcje opart ˛

a na warunku, σ

C

(

R) warto przenie´s´c w dół drzewa,

je´sli to mo˙zliwe.

Podobnie post ˛epujemy z projekcjami.

Usuwanie powtórze ´n cz ˛esto lepiej zrobi´c wy˙zej w drzewie (je´sli
trzeba) aby operowa´c na mniejszych relacjach.

Przed zł ˛

aczeniem lepiej wykona´c selekcj ˛e na obu relacjach

składowych (je´sli wogle chcemy wykona´c selekcj ˛e).

Konrad Zdanowski ( Uniwersytet Kardynała Stefana Wyszy ´nskiego, Warszawa)

Bazy danych – wykład dwunasty Wykonywanie i optymalizacja zapyta ´n SQL

32 / 36

background image

Fizyczny plan realizacji zapytania

Po dokonaniu optymalizacji logicznej trzeba wybra´c algorytmy
realizacji zapytania:

kolejno´s´c wykonania operacji przemiennych jak zł ˛

aczenia, sumy,

. . . ,

algorytmy dla operatorów logicznych (haszowanie, zagnie˙zd˙zone
p ˛etle, . . . ),

realizacja operatorów sortowania, grupowania, . . . ,

sposób przekazywania argumentów i wyników podzapyta ´n (przez
dysk, pami ˛e´c operacyjna, po jednej krotce, . . . ).

Konrad Zdanowski ( Uniwersytet Kardynała Stefana Wyszy ´nskiego, Warszawa)

Bazy danych – wykład dwunasty Wykonywanie i optymalizacja zapyta ´n SQL

33 / 36

background image

Szacowanie kosztów

Aby wybra´c odpowiednie algorytmu nale˙zy oszacowa´c ich koszty,
czyli przede wszystkim oszacowa´c wielko´s´c po´srednich wyników.
Stosuje si ˛e tutaj:

I

przewidywanie przypadków najgorszych,

I

rachunek prawdopodobie ´nstwa by wyliczy´c oczekiwane warto´sci
rozmiaru relacji

I

obliczanie okresowo statystyk bazy danych.

Konrad Zdanowski ( Uniwersytet Kardynała Stefana Wyszy ´nskiego, Warszawa)

Bazy danych – wykład dwunasty Wykonywanie i optymalizacja zapyta ´n SQL

34 / 36

background image

Szacowanie kosztów – rozmiar projekcji

Je´sli dane maj ˛

a rozkład jednostajny, to oczekiawna wielko´s´c projekcji

σ

A=a

(

R) wynosi T (R)/V (R, A).

W praktyce wiele danych ma np. rozkład Zipfa (np. rozmiar populacji
miast - podzielony na przedziały). W rozkładzie Zipfa i-ta najcz ˛estsza

warto´s´c wyst ˛epuje z cz ˛estotliwo´sci ˛

a 1/

i. Otrzymujemy wtedy ci ˛

ag

stosunków cz ˛esto´sci 1, 0.71, 0.58, . . .

Konrad Zdanowski ( Uniwersytet Kardynała Stefana Wyszy ´nskiego, Warszawa)

Bazy danych – wykład dwunasty Wykonywanie i optymalizacja zapyta ´n SQL

35 / 36

background image

Szacowanie kosztów

Szacowanie rozmiaru sumy, iloczynu, ró˙znicy do´s´c łatwe cho´c
niekoniecznie dokładne.

Np. rozmiar ró˙znicy R S zawiera si ˛e w T (R) a T (R) T (S).

´

Srednio mo˙zemy przyj ˛

ac

(

T (R) + (T (R) T (S)))/2 = T (R) T (S)/2.

Zł ˛

aczenie R(A, B) is S(B, C) mo˙ze mie´c w wyniku

I

0 krotek,

I

T (R) krotek, je´sli B jest kluczem obcym w R pobieranym z S,

I

rz ˛edu T (R)T (S) krotek, je´sli warto´s´c atrybutu B jest w obu
relacjach taka sama i mało zmienna.

Przy pewnych dodatkowych zało˙zeniach (V (R, B) ¬ V (S, B)) i
V (R o

n S, A) = V (R, A)) mo ˙

zemy szacowa´c rozmiar zł ˛

aczenia

jako T (R)T (S)/ max(V (R, B), V (S, B)).

Konrad Zdanowski ( Uniwersytet Kardynała Stefana Wyszy ´nskiego, Warszawa)

Bazy danych – wykład dwunasty Wykonywanie i optymalizacja zapyta ´n SQL

36 / 36


Wyszukiwarka

Podobne podstrony:
KZ BD w09 id 256667 Nieznany
KZ BD w07 id 256666 Nieznany
KZ BD w12 id 256669 Nieznany
KZ BD w03 2 id 256664 Nieznany
KZ BD w11 2 id 256668 Nieznany
KZ BD w09 id 256667 Nieznany
bd lab2 id 81995 Nieznany (2)
bd dbastudio id 81961 Nieznany (2)
BD 408e id 130025 Nieznany (2)
bd w1 id 81977 Nieznany (2)
bd lab2 id 81995 Nieznany (2)
bd dbastudio id 81961 Nieznany (2)
BD 1st 2 4 lab3 tresc 1 1 id 81 Nieznany
bd lab 04 id 81967 Nieznany (2)
Calosc BD id 108184 Nieznany
BD 2st 1 2 w13 tresc 1 1 id 819 Nieznany (2)
BD 1st 2 4 lab1 tresc 1 1 id 81 Nieznany (2)
BD 1st 2 4 lab4 tresc 1 1 id 81 Nieznany (2)

więcej podobnych podstron