$Q2YHUYLHZRI4XHU\

2SWLPL]DWLRQLQ5HODWLRQDO
6\VWHPV

2XWOLQH
3UHOLPLQDULHV

6XUDMLW&KDXGKXUL
0LFURVRIW5HVHDUFK
VXUDMLWF#PLFURVRIWFRP
KWWSUHVHDUFKPLFURVRIWFRPaVXUDMLWF

5HODWLRQDOTXHU\HQJLQH
2SHUDWRU7UHHV

4XHU\2SWLPL]DWLRQ)UDPHZRUN
%XLOGLQJ%ORFNV
7XQLQJ2SWLPL]HUV
$FWLYH$UHDVRI5HVHDUFK
&RQFOXVLRQ

4/23/99

5HODWLRQDO'%06&RPSRQHQWV

Surajit Chaudhuri

6FDQDQG6HOHFWLRQ
2SHUDWRUV

SQL

6FDQ>LQGH[@WDEOHSUHGLFDWH

Parsing

Query Optimizer
Relational
Engine

6HTXHQWLDO6FDQ
,QGH[VFDQ:KLFKLQGH[HVWRXVH"
$OZD\VSXVKGRZQLQGH[HYDOXDEOH
SUHGLFDWHV

Execution Engine

)LOWHUWDEOHSUHGLFDWH

Storage Engine
(Manages Tables and Indexes)

4/23/99

Surajit Chaudhuri

-RLQ2SHUDWRUV

4/23/99

-RLQ>PHWKRG@RXWHULQQHUMRLQ
SUHGLFDWH

5HTXLUHVVRUWHGRUGHURQ5D5D
2XWSXWLVDVRUWHGRUGHU

3LSHOLQHG

-RLQ1HVWHG/RRS555D
5E

Surajit Chaudhuri

*HQHULF-RLQ2SHUDWRUV

-RLQ0HUJH555D 5D

4/23/99

$V\PPHWULF
(IIHFWRISK\VLFDOSURSHUWLHVRILQSXWVWUHDPV
HJVRUWHGLQSXW

3K\VLFDOSURSHUWLHVRIRXWSXWVWUHDPHJ
VRUWHG

6RUWHGLQSXWVRIQRFRQVHTXHQFH

2XWSXWKDVWKHVDPHVRUWRUGHUDV5D

3LSHOLQHGYV%ORFNLQJ
1HVWHG/RRSYV6RUW0HUJH

3LSHOLQHG
Surajit Chaudhuri

4/23/99

Surajit Chaudhuri

*HQHULF9LHZRI5(
2SHUDWRUV

6RUW +DVK

,QSXW2QHRUPRUHGDWDVWUHDPV
2XWSXW2QHGDWDVWUHDP
,PSOHPHQWDWLRQ

6RUW5^$%&`SDUDPHWHUV

%ORFNLQJRQO\LQSDUW

%XLOG+DVK5^&'`SDUDPHWHUV

%ORFNLQJ

3UREH+DVK5^&'`KDVKWDEOH

3LSHOLQLQJ

RSHQ
JHWQH[W
FORVH

3LSHOLQHG%ORFNLQJ
4/23/99

Surajit Chaudhuri

Sort

Scan R2

4/23/99

Scan R1

(R1 sorted on A)

Scan R3

Surajit Chaudhuri

2XWOLQH

4/23/99

:K\GRLW"

:KDWLQIRUPDWLRQQHHGVWREH

%XLOGLQJ%ORFNV
7XQLQJ2SWLPL]HUV
$FWLYH$UHDVRI5HVHDUFK
&RQFOXVLRQ Surajit Chaudhuri

10

&RPSLOHD64/TXHU\LQDQRSHUDWRU
WUHH
$SSURDFK

FRQVLGHUHG"

4/23/99

Surajit Chaudhuri

4XHU\2SWLPL]DWLRQ

3UHOLPLQDULHV
4XHU\2SWLPL]DWLRQ)UDPHZRUN

'HPDQGGULYHQDUFKLWHFWXUHLVWKH
VLPSOHVW
RSHQLVSURSDJDWHGIURPWKHURRW
JHWQH[WDWWKHURRWLVSURSDJDWHG
,IJHWQH[WDWWKHURRWIDLOVWR
UHWXUQDQHZWXSOHWKHQQRPRUH
DQVZHUVIRUWKHTXHU\

2.A = 3.A
Merge Join

NL Join

Surajit Chaudhuri

([HFXWLRQRIDQ2SHUDWRU
7UHH

5(2SHUDWRU7UHH

4.B = 5.B

4/23/99

7DNHD64/H[SUHVVLRQ
5HSUHVHQWDVDWUHH
7XUQDOJHEUDLFRSHUDWRUVLQWR5(
RSHUDWRUV

:K\LVWKLVQRWDGHTXDWH"
11

4/23/99

Surajit Chaudhuri

12

2EVHUYDWLRQV

5LFKQHVVRI&KRLFH

6HOHFWLRQVDOZD\VUHGXFHUHODWLRQVL]H
,QGH[VFDQPD\PD\QRWEHPRUHHIILFLHQW
2UGHURIHYDOXDWLRQRIMRLQVLUUHOHYDQWIRU
FRUUHFWQHVV

%XWRUGHUGHWHUPLQHVHIILFLHQF\

7RWDOVDOHVIRU3URGXFWVIRU4IURP1:

6XPVDOHVRIDOOSURGXFWVMRLQZLWK3URGXFWV

$OJHEUDLFSURSHUWLHVDOORZVHPDQWLFDOO\
HTXLYDOHQWDOJHEUDLFWUHHVIRUDTXHU\
0XOWLSOHLPSOHPHQWDWLRQWHFKQLTXHVIRU
HDFKDOJHEUDLFRSHUDWRU
&RVWVRIWKHDOWHUQDWLYHVPD\EHZLGHO\
GLIIHUHQWGHSHQGLQJRQVWDWLVWLFDO
SURSHUWLHVRIGDWD

-RLQSURGXFWVZLWK6DOHWKHQVXP

4/23/99

Surajit Chaudhuri

13

4/23/99

Surajit Chaudhuri

*RDORI4XHU\2SWLPL]HU

,PSOHPHQWLQJDQ2SWLPL]HU

&RPSLOHD64/TXHU\LQDQRSHUDWRUWUHH
)LQGWKHWUHHZLWKOHDVWFRVWVXEMHFWWR

(TXLYDOHQFHWUDQVIRUPDWLRQV
$YDLODEOH5(RSHUDWRUV
'DWDEDVHVWDWLVWLFV

([SORUHWKHVSDFHRIWUHHVHIILFLHQWO\
2SWLPL]HUKHOSVDFKLHYH

3URJUDP2SWLPL]DWLRQ
6HDUFK$OJRULWKPV3ODQQLQJ
&RPELQDWRULDO2SWLPL]DWLRQ
:HZLOOUHYLVLWWKLVLVVXHLQWKHQH[W
OHFWXUH

'DWD,QGHSHQGHQFH

4/23/99

Surajit Chaudhuri

15

$)UDPHZRUNIRU4XHU\
2SWLPL]DWLRQ

,PSOHPHQWDWLRQRSWLRQV

1HHGVWRHVWLPDWHFRVWRIDQRSHUDWRU
WUHHLQFUHPHQWDOO\

7UHH)LQGHUVHDUFK

)DVW0HPRU\HIILFLHQW

Surajit Chaudhuri

Surajit Chaudhuri

16

3UHOLPLQDULHV
4XHU\2SWLPL]DWLRQ)UDPHZRUN
%XLOGLQJ%ORFNV

$OJHEUDLFSURSHUWLHV

(VWLPDWLRQ0RGHO

4/23/99

2XWOLQH

(TXLYDOHQFH7UDQVIRUPDWLRQV

4/23/99

14

17

(TXLYDOHQFH7UDQVIRUPDWLRQV
6WDWLVWLFDO0RGHO
7UHH)LQGHU

7XQLQJ2SWLPL]HUV
$FWLYH$UHDVRI5HVHDUFK
4/23/99
&RQFOXVLRQ Surajit Chaudhuri

18

([DPSOHVRI
7UDQVIRUPDWLRQV

$63-4XHULHV

-RLQ2UGHULQJ
&RPPXWLQJMRLQDQGRXWHUMRLQ
&RPPXWLQJJURXSE\DQGMRLQ
2SWLPL]HPXOWLEORFNTXHULHV

6HOHFW$D6XP%]
)URP$%&
:KHUH$[

%[DQG%\

&\

*URXS%\$D
2UGHU%\$D

&ROODSVHPXOWLEORFNTXHU\WRDVLQJOH
EORFNTXHU\

2SWLPL]HDFURVVPXOWLSOHTXHU\EORFNV

4/23/99

Surajit Chaudhuri

19

,PSOHPHQWDWLRQ
7UDQVIRUPDWLRQV

)LOWHU-RLQ$%D

-RLQ)LOWHU$D%

-RLQVDUHDVVRFLDWLYHDQGFRPPXWDWLYH

IRUPV

6HTXHQWLDOVFDQ

)LOWHU

20

6HOHFWDQG-RLQFRPPXWH

%WUHHLQGH[VFDQZLWKVDUJDEOH
3UHGLFDWH%HWZHHQDQGLWVGHJHQHUDWH

Surajit Chaudhuri

-RLQ2UGHULQJ

6FDQ

4/23/99

-RLQ-RLQ$%&

-RLQ-RLQ%$&

-RLQ-RLQ$&%

-RLQ-RLQ$%&

0DQ\HTXLYDOHQWH[SUHVVLRQV+RZPDQ\"

+RZDERXWQDU\MRLQV"

$Q\%RROHDQH[SUHVVLRQ

-RLQ

4/23/99

6RUW0HUJH1HVWHGORRS,QGH[HG
1HVWHGORRS

Surajit Chaudhuri

21

4/23/99

Surajit Chaudhuri

7UDQVIRUPDWLRQ !6SDFH

-RLQDQG2XWHU-RLQ

6KDSHRIMRLQWUHHV

'RRXWHUMRLQRSHUDWRUVFRPPXWH"
([DPSOH

5HVWULFWHGXVHRI$&SURSHUWLHV

/LQHDU-RLQ7UHHV

Surajit Chaudhuri

5/2-63UHVHUYHV5
-RLQ56/2-7

"

*RDORI7UDQVIRUPDWLRQV,VRODWHEORFNVRI
QDWXUDOMRLQ

%XVK\-RLQ7UHHV

4/23/99

22

23

4/23/99

Surajit Chaudhuri

24

2SHUDWRU7UHHV
*URXS%\DQG-RLQ

*URXS%\DQG-RLQ

6HOHFW)URP:KHUH*URXS%\

7UDGLWLRQDOO\H[HFXWLRQRIJURXSE\IROORZV
H[HFXWLRQRIMRLQV

7RWDOVDOHVIRU3URGXFWVIRU4IURP1:

6FKHPD
3URGXFWSLGXQLWSULFH
6DOHVWLGGDWHVWRUHSLGXQLWV

Join

7UHHV
Group By (pid)
sum(units)

6XPVDOHVRIDOOSURGXFWVMRLQZLWK3URGXFWV
-RLQSURGXFWVZLWK6DOHWKHQVXP

Group By (pid)
sum(units)

Join

Scan (Sales)

Products

Scan (Sales)

Filter (In NW)

Filter(Saledate = Q298)

Products
Filter (In NW)

Filter(date = Q298)
4/23/99

Surajit Chaudhuri

25

6DOHVWLGGDWHVWRUHSLGDPRXQW

([DPSOH

Group By (pid)
sum(amount)
Category

Scan (Sales)
Filter([Link] in
{CA, WA})
4/23/99

Filter (..)

Filter(..)

Filter([Link] in
{CA, WA})
27

4/23/99

7KHUHIRUHPD\UHGXFHFRVWRIVXEVHTXHQWMRLQV
&DQEHSLSHOLQHGZLWKLQGH[VFDQV

$SSOLFDWLRQQHHGVWREHFRVWEDVHGVLQFH
7KHFRVWRIJURXSE\PD\EHLQFUHDVHG

Surajit Chaudhuri

YLHZVZLWKDJJUHJDWHV
WDEOHH[SUHVVLRQV
QHVWHGVXETXHULHV

7HFKQLTXHVIRU2SWLPL]DWLRQ

$FFHVVPHWKRGVRQEDVHWDEOHVPD\QRORQJHUEHXVHIXO

(QFDSVXODWLQJDWUDQVIRUPDWLRQLVQRWHDV\

4/23/99

28

0XOWLEORFNVWUXFWXUHDULVHVGXHWR

*URXS%\FROODSVHVDQHTXLYDOHQFHFODVV

IRUWKHMRLQ

Surajit Chaudhuri

0XOWL%ORFN4XHULHV

3XVKLQJGRZQJURXSE\SDVWDMRLQ

I$JJ6$JJ6

0D\VRPHWLPHUHTXLUHXVHRIGHULYHGFROXPQV

Scan (Sales)

*URXS%\DQG-RLQ
3URVDQG&RQV

$JJ686

Category

Surajit Chaudhuri

1RVFKHPDFRQVWUDLQWVEXWSURSHUWLHVRI
DJJUHJDWHIXQFWLRQV

Join

Join

6FKHPDFRQVWUDLQWVDUELWUDU\DJJUHJDWLRQ
IXQFWLRQV

Group By (cid)
sum(amount)

&DWHJRU\SLGFLGGHWDLOV

Group By (cid)
sum(amount)

26

6FKHPD

Surajit Chaudhuri

3UHUHTXLVLWHV
*URXS%\DQG-RLQ

,QWURGXFLQJ2SHUDWRU
*URXS%\DQG-RLQ

4/23/99

29

4/23/99

0HUJHLQWRDVLQJOHEORFN
6KDUHLQIRUPDWLRQDFURVVEORFNV

Surajit Chaudhuri

30