Parallel Database

these slides are prepared for MCA Atudents

1. 2/12/20131
1.Parallel and Distributed Databases
11. Parallel DB /D.S.Jagli
1. Parallel DB /D.S.Jagli

2. Parallel database
1. -Introduction
2. -Architecture for Parallel databases.
3. -Parallel query Evaluation
4. -Parallelizing Individual operations.
2/12/20132
21. Parallel DB /D.S.Jagli
1. Parallel DB /D.S.Jagli

3. Introduction
2/12/20133
What is a Centralized Database ?
-all the data is maintained at a single site and assumed that the processing of
individual transaction is essentially sequential.
31. Parallel DB /D.S.Jagli
1. Parallel DB /D.S.Jagli

4. 2/12/20134
PARALLEL DBMSs
WHY DO WE NEED THEM?
•More and More Data!
We have databases that hold a high amount of
data, in the order of 10
12
bytes:
10,000,000,000,000 bytes!
•Faster and Faster Access!
We have data applications that need to process
data at very high speeds:
10,000s transactions per second!
SINGLE-PROCESSOR DBMS AREN’T UP TO THE JOB!
41. Parallel DB /D.S.Jagli
1. Parallel DB /D.S.Jagli

5. 2/12/20131. Parallel DB /D.S.Jagli5
Why Parallel Access To Data?
1 Terabyte
10 MB/s
At 10 MB/s
1.2 days to scan
1 Terabyte
1,000 x parallel
1.5 minute to scan.
Parallelism:
divide a big problem
into many smaller ones
to be solved in parallel.

6. Parallel DB
2/12/20136
Paralleldatabasesystemseekstoimproveperformancethrough
parallelizationofvariousoperationssuchasloadingdata,building
indexes,andevaluatingqueriesbyusingmultipleCPUsandDisksin
Parallel.
MotivationforParallelDB
Parallelmachinesarebecomingquitecommonandaffordable
Pricesofmicroprocessors,memoryanddiskshavedroppedsharply
Databasesaregrowingincreasinglylarge
largevolumesoftransactiondataarecollectedandstoredforlater
analysis.
multimediaobjectslikeimagesareincreasinglystoredindatabases
61. Parallel DB /D.S.Jagli
1. Parallel DB /D.S.Jagli

7. 2/12/20137
Improves Response Time.
INTERQUERY PARALLELISM
It is possible to process a number of transactions in
parallel with each other.
Improves Throughput.
INTRAQUERY PARALLELISM
It is possible to process ‘sub-tasks’ of a transaction in
parallel with each other.
PARALLEL DBMSs
BENEFITS OF A PARALLEL DBMS
71. Parallel DB /D.S.Jagli
1. Parallel DB /D.S.Jagli

8. 2/12/20138
Speed-Up
–Addingmoreresourcesresultsinproportionallylessrunningtimefora
fixedamountofdata.
10 seconds to scan a DB of 10,000 records using 1 CPU
1 second to scan a DB of 10,000 records using 10 CPUs
PARALLEL DBMSs
HOW TO MEASURE THE BENEFITS
Scale-Up
Ifresourcesareincreasedinproportiontoanincreaseindata/problem
size,theoveralltimeshouldremainconstant
–1secondtoscanaDBof1,000recordsusing1CPU
1secondtoscanaDBof10,000recordsusing10CPUs
81. Parallel DB /D.S.Jagli
1. Parallel DB /D.S.Jagli

9. Architectures for Parallel Databases
2/12/20139
The basic idea behind Parallel DB is to carry out evaluation steps in
parallel whenever is possible.
There are many opportunities for parallelism in RDBMS.
3 main architectures have been proposed for building parallel DBMSs.
1.Shared Memory
2.Shared Disk
3.Shared Nothing
91. Parallel DB /D.S.Jagli
1. Parallel DB /D.S.Jagli

10. Shared Memory
2/12/201310
Advantages:
1.It is closer to conventional
machine , Easy to program
2.overhead is low.
3.OS services are leveraged to
utilize the additional CPUs.
Disadvantage:
1.It leads to bottleneck problem
2.Expensive to build
3.It is less sensitive to
partitioning
1. Parallel DB /D.S.Jagli 10
1. Parallel DB /D.S.Jagli

11. Shared Disk
2/12/201311
Advantages:
1.Almost same
Disadvantages:
1.More interference
2.Increases N/W band width
3.Shared disk less sensitive to
partitioning
1. Parallel DB /D.S.Jagli 11
1. Parallel DB /D.S.Jagli

12. Shared Nothing
2/12/201312
Advantages:
1.It provides linear scale up
&linear speed up
2.Shared nothing benefits from
"good" partitioning
3.Cheap to build
Disadvantage
1.Hard to program
2.Addition of new nodes
requires reorganizing
1. Parallel DB /D.S.Jagli 12
1. Parallel DB /D.S.Jagli

13. 2/12/201313
Sub-linear speed-up
Linear speed-up (ideal)
Number of CPUs
Number of transactions/second
1000/Sec
5 CPUs
2000/Sec
10 CPUs 16 CPUs
1600/Sec
PARALLEL DBMSs
SPEED-UP
131. Parallel DB /D.S.Jagli
1. Parallel DB /D.S.Jagli

14. 2/12/201314
10 CPUs
2 GB Database
Number of CPUs, Database size
Number of transactions/second
Linear scale-up (ideal)
Sub-linear scale-up
1000/Sec
5 CPUs
1 GB Database
900/Sec
PARALLEL DBMSs
SCALE-UP
141. Parallel DB /D.S.Jagli
1. Parallel DB /D.S.Jagli

15. PARALLEL QUERY EVALUATION
2/12/201315
1.1. Parallel DB /D.S.Jagli 15
Arelationalqueryexecutionplanisgraph/treeof
relationalalgebraoperators(basedonthisoperatorscan
executeinparallel)
1. Parallel DB /D.S.Jagli

16. Different Types of DBMS ||-ism
2/12/201316
ParallelevaluationofarelationalqueryinDBMSWithshared–nothing
architecture
1.Inter-queryparallelism
Multiplequeriesrunondifferentsites
2.Intra-queryparallelism
Parallelexecutionofsinglequeryrunondifferentsites.
a)Intra-operatorparallelism
a)getallmachinesworkingtogethertocomputeagivenoperation(scan,sort,
join).
b)Inter-operatorparallelism
eachoperatormayrunconcurrentlyonadifferentsite(exploits
pipelining).
Inordertoevaluatedifferentoperatorsinparallel,weneedto
evaluateeachoperatorinqueryplaninParallel.
1.1. Parallel DB /D.S.Jagli 16
1. Parallel DB /D.S.Jagli

17. Data Partitioning
2/12/2013
1. Parallel DB /D.S.Jagli17
Types of Partitioning
1.Horizontal Partitioning: tuple of a relation are divided among
many disks such that each tuple resides on one disk.
ItenablestoexploittheI/Obandwidthofdisksbyreading&writing
theminparallel.
Reducethetimerequiredtoretrieverelationsfromdiskby
partitioningtherelationsonmultipledisks.
1.Range Partitioning
2.Hash Partitioning
3.Round Robin Partitioning
2.Vertical Partitioning
17

18. 1.Range Partitioning
2/12/20131. Parallel DB /D.S.Jagli18
Tuples are sorted (conceptually), and nranges are chosen for
the sort key values so that each range contains roughly the
same number of tuples;
tuples in rangei are assigned to processor i.
Eg:
sailor _id 1-10 assigned to disk 1
sailor _id 10-20 assigned to disk 2
sailor _id 20-30 assigned to disk 3
range partitioning can lead to data skew; that is, partitions with widely
varying number of tuples across
18

19. 2.Hash Partitioning
2/12/20131. Parallel DB /D.S.Jagli19
A hash function is applied to selected fields of a tuple to determine its
processor.
Hash partitioning has the additional virtue that it keeps data evenly
distributed even if the data grows and shrinks over time.
19

20. 3.Round Robin Partitioning
2/12/20131. Parallel DB /D.S.Jagli20
If there aren processors, the ithtuple is assigned to processor imod nin
round-robin partitioning.
Round-robin partitioning is suitable for efficiently evaluating queries that
access the entire relation.
If only a subset of the tuples (e.g., those that satisfy the selection
condition age = 20) is required, hash partitioning and range partitioning
are better than round-robin partitioning
20

21. 2/12/201321
1. Parallel DB /D.S.Jagli 21
Range Hash Round Robin
A...EF...JK...NO...ST...ZA...EF...JK...NO...ST...Z A...EF...JK...NO...ST...Z
Good for equijoins,
exact-match queries,
and range queries
Good for equijoins,
exact match queries
Good to spread load
1. Parallel DB /D.S.Jagli

22. Parallelizing Sequential Operator
Evaluation Code
2/12/201322
1.AnelegantsoftwarearchitectureforparallelDBMSsenablesusto
readilyparallelizeexistingcodeforsequentiallyevaluatinga
relationaloperator.
2.Thebasicideaistouseparalleldatastreams.
3.Streamsaremergedasneededtoprovidetheinputsforarelational
operator.
4.Theoutputofanoperatorissplitasneededtoparallelizesubsequent
processing.
5.Aparallelevaluationplanconsistsofadataflownetworkof
relational,merge,andsplitoperators.
1. Parallel DB /D.S.Jagli 22
1. Parallel DB /D.S.Jagli

23. PARALLELIZING INDIVIDUAL
OPERATIONS
2/12/201323
How various operations can be implemented in parallel in a shared-
nothing architecture?
Techniques
1.Bulk loading& scanning
2.Sorting
3.Joins
1. Parallel DB /D.S.Jagli 23
1. Parallel DB /D.S.Jagli

24. 1.Bulk Loading and scanning
2/12/201324
scanningarelation:Pagescanbereadinparallelwhilescanninga
relation,andtheretrievedtuplescanthenbemerged,iftherelationis
partitionedacrossseveraldisks.
bulkloading:ifarelationhasassociatedindexes,anysortingofdata
entriesrequiredforbuildingtheindexesduringbulkloadingcanalso
bedoneinparallel.
1. Parallel DB /D.S.Jagli 24
1. Parallel DB /D.S.Jagli

25. 2.Parallel Sorting :
2/12/201325
Parallel sorting steps:
1.First redistribute all tuples in the relation using range partitioning.
2.Each processor then sorts the tuples assigned to it
3.The entire sorted relation can be retrieved by visiting the processors in
an order corresponding to the ranges assigned to them.
Problem: Data skew
Solution: “sample” the data at the outset to determine good
range partition points.
A particularly important application of parallel sorting is sorting the data
entries in tree-structured indexes.
251. Parallel DB /D.S.Jagli
1. Parallel DB /D.S.Jagli

26. 3.Parallel Join
2/12/201326
1.The basic idea for joining A and B in parallel is to decompose the join
into a collection of k smaller joins by using partition.
2.By using the same partitioning function for both A and B, we ensure that
the union of the k smaller joins computes the join of A and B.
Hash-Join
Sort-merge-join
261. Parallel DB /D.S.Jagli
1. Parallel DB /D.S.Jagli

27. Sort-merge-join
partitionAandBbydividingtherangeofthejoinattributeintokdisjoint
subrangesandplacingAandBtuplesintopartitionsaccordingtothe
subrangetowhichtheirvaluesbelong.
Eachprocessorcarryoutalocaljoin.
Inthiscasethenumberofpartitionskischosentobeequaltothenumber
ofprocessorsn.
TheresultofthejoinofAandB,theoutputofthejoinprocessmaybe
splitintoseveraldatastreams.
The advantage that the output is available in sorted order
2/12/201327
271. Parallel DB /D.S.Jagli
1. Parallel DB /D.S.Jagli

28. 2/12/201328
Dataflow Network of Operators for
Parallel Join
281. Parallel DB /D.S.Jagli
Good use of split/merge makes it easier to build parallel versions of sequential
join code
1. Parallel DB /D.S.Jagli

29. I.Introduction to DDBMS
II.Architecture of DDBs
III.Storing data in DDBs
IV.Distributed catalog management
V.Distributed query processing
VI.Transaction Processing
VII.Distributed concurrency control and recovery
DDBMS
2/12/201329
1. Parallel DB /D.S.Jagli 29
1. Parallel DB /D.S.Jagli

30. I.Introductionto DDBMS
2/12/201330
Datainadistributeddatabasesystemisstoredacrossseveralsites.
EachsiteistypicallymanagedbyaDBMSthatcanrunindependentlyof
theothersitesthatco-operateinatransparentmanner.
Transparentimpliesthateachuserwithinthesystemmayaccessallof
thedatawithinallofthedatabasesasiftheywereasingledatabase
Thereshouldbe„locationindependence‟i.e.-astheuserisunawareof
wherethedataislocateditispossibletomovethedatafromonephysical
locationtoanotherwithoutaffectingtheuser.
301. Parallel DB /D.S.Jagli
1. Parallel DB /D.S.Jagli

31. DDBMS properties
2/12/201331
Distributeddataindependence:Usersshouldbeabletoaskqueries
withoutspecifyingwherethereferencedrelations,orcopiesor
fragmentsoftherelations,arelocated.
Distributedtransactionatomicity:Usersshouldbeabletowrite
transactionsthataccessandupdatedataatseveralsitesjustasthey
wouldwritetransactionsoverpurelylocaldata.
311. Parallel DB /D.S.Jagli
1. Parallel DB /D.S.Jagli

32. 2/12/201332
LAN
CLIENT
CLIENT
LAN
CLIENT CLIENT
CLIENT CLIENT
LAN
CLIENT
CLIENT
LAN
CLIENT
Mumbai
CLIENT
CLIENT CLIENT
Delhi
DBMS
Hyderabad Pune
DISTRIBUTED PROCESSING ARCHITECTURE
CLIENT
CLIENT
CLIENT
CLIENT
321. Parallel DB /D.S.Jagli
1. Parallel DB /D.S.Jagli

33. 2/12/20131. Parallel DB /D.S.Jagli33
LAN
CLIENT CLIENT
CLIENT CLIENT
DBMS
DISTRIBUTED DATABASE ARCHITECTURE
LAN
CLIENT CLIENT
CLIENT CLIENT
DBMS
Pune
CLIENT CLIENT
CLIENT
DBMS
Delhi
CLIENT
CLIENT CLIENT
CLIENT
DBMS
Hyderabad
CLIENT
CLIENT
CLIENT
Mumbai
331. Parallel DB /D.S.Jagli

34. 2/12/20131. Parallel DB /D.S.Jagli34
Distributed database
Communication Network-DBMS and Data at each node
•Users are unaware
of the distribution of
the data
Location
transparency

35. Types of Distributed Databases
Homogeneousdistributeddatabasesystem:
IfdataisdistributedbutallserversrunthesameDBMSsoftware.
Heterogeneousdistributeddatabase:
IfdifferentsitesrununderthecontrolofdifferentDBMSs,
essentiallyautonomously,areconnectedtoenableaccesstodata
frommultiplesites.
Thekeytobuildingheterogeneoussystemsistohavewell-accepted
standardsforgatewayprotocols.
AgatewayprotocolisanAPIthatexposesDBMSfunctionalityto
externalapplications.
2/12/201335
351. Parallel DB /D.S.Jagli
1. Parallel DB /D.S.Jagli

36. I.Introduction to DDBMS
II.Architecture of DDBs
III.Storing data in DDBs
IV.Distributed catalog management
V.Distributed query processing
VI.Transaction Processing
VII.Distributed concurrency control and recovery
DDBMS
2/12/201336
1. Parallel DB /D.S.Jagli 36
1. Parallel DB /D.S.Jagli

37. 2.DISTRIBUTED DBMS
ARCHITECTURES
1.Client-Server Systems:
2.Collaborating Server Systems
3.Middleware Systems
2/12/201337
371. Parallel DB /D.S.Jagli
1. Parallel DB /D.S.Jagli

38. 1.Client-Server Systems:
1.AClient-Serversystemhasoneormoreclient
processesandoneormoreserverprocesses,
2.Aclientprocesscansendaquerytoanyoneserver
process.
3.Clientsareresponsibleforuser-interfaceissues,
4.Serversmanagedataandexecutetransactions.
5.Aclientprocesscouldrunonapersonalcomputer
andsendqueriestoaserverrunningonamainframe.
6.TheClient-Serverarchitecturedoesnotallowasingle
querytospanmultipleservers
2/12/201338
381. Parallel DB /D.S.Jagli
1. Parallel DB /D.S.Jagli

39. 2/12/201339
DUMB
DUMB
DUMB
SPECIALISED NETWORK CONNECTION
TERMINALS
MAINFRAME COMPUTER
PRESENTATION LOGIC
BUSINESS LOGIC
DATA LOGIC
391. Parallel DB /D.S.Jagli
1. Parallel DB /D.S.Jagli

40. 2.Collaborating Server Systems
1.Theclientprocesswouldhavetobecapableofbreaking
suchaqueryintoappropriatesubqueries.
2.ACollaboratingServersystemcanhaveacollectionof
databaseservers,eachcapableofrunningtransactions
againstlocaldata,whichcooperativelyexecute
transactionsspanningmultipleservers.
3.Whenaserverreceivesaquerythatrequiresaccessto
dataatotherservers,itgeneratesappropriatesubqueries
tobeexecutedbyotherservers.
4.putstheresultstogethertocomputeanswerstothe
originalquery.
2/12/201340
401. Parallel DB /D.S.Jagli
1. Parallel DB /D.S.Jagli

41. 2/12/201341
1. Parallel DB /D.S.Jagli 41
D/BASE
SERVER #1
CLIENT
#1
D/BASE
SERVER #2
CLIENT
#2
CLIENT
#3
M:N CLIENT/SERVER DBMS ARCHITECTURE
NOT TRANSPARENT!
1. Parallel DB /D.S.Jagli

42. 3.Middleware Systems:
TheMiddlewarearchitectureisdesignedtoallowasingle
querytospanmultipleservers,withoutrequiringall
databaseserverstobecapableofmanagingsuchmultisite
executionstrategies.
Itisespeciallyattractivewhentryingtointegrateseveral
legacysystems,whosebasiccapabilitiescannotbe
extended.
2/12/201342
421. Parallel DB /D.S.Jagli
1. Parallel DB /D.S.Jagli

43. I.Introduction to DDBMS
II.Architecture of DDBs
III.Storing data in DDBs
IV.Distributed catalog management
V.Distributed query processing
VI.Transaction Processing
VII.Distributed concurrency control and recovery
DDBMS
2/12/201343
1. Parallel DB /D.S.Jagli 43
1. Parallel DB /D.S.Jagli

44. 3.Storing Data in DDBs
InadistributedDBMS,relationsarestoredacross
severalsites.
Accessingarelationthatisstoredataremotesite
includesmessage-passingcosts.
Asinglerelationmaybepartitionedorfragmented
acrossseveralsites.
2/12/201344
1. Parallel DB /D.S.Jagli 44
1. Parallel DB /D.S.Jagli

45. Types of Fragmentation:
Horizontalfragmentation:Theunionofthehorizontal
fragmentsmustbeequaltotheoriginalrelation.Fragments
areusuallyalsorequiredtobedisjoint.
Verticalfragmentation:Thecollectionofverticalfragments
shouldbealossless-joindecomposition.
2/12/20131. Parallel DB /D.S.Jagli45
45

46. 2/12/20131. Parallel DB /D.S.Jagli46
46

47. Replication
2/12/20131. Parallel DB /D.S.Jagli47
Replicationmeansthatwestoreseveralcopiesofarelation
orrelationfragment.
Themotivationforreplicationistwofold:
1.Increasedavailabilityofdata:
2.Fasterqueryevaluation:
Twokindsofreplications
1.synchronousreplication
2.asynchronousreplication
47

48. I.Introduction to DDBMS
II.Architecture of DDBs
III.Storing data in DDBs
IV.Distributed Catalog Management
V.Distributed Query Processing
VI.Transaction Processing
VII.Distributed concurrency control and recovery
DDBMS
2/12/201348
1. Parallel DB /D.S.Jagli 48
1. Parallel DB /D.S.Jagli

49. 4.Distributed Catalog Management
2/12/20131. Parallel DB /D.S.Jagli49
1.NamingObjects
•Ifarelationisfragmentedandreplicated,wemustbeableto
uniquelyidentifyeachreplicaofeachfragment.
1.Alocalnamefield
2.Abirthsitefield
2.CatalogStructure
AcentralizedsystemcatalogcanbeusedItisvulnerabletofailureof
thesitecontainingthecatalog).
Analternativeistomaintainacopyofaglobalsystemcatalog.
compromisessiteautonomy,)
49

50. 4.Distributed Catalog Management
2/12/20131. Parallel DB /D.S.Jagli50
Abetterapproach:
Eachsitemaintainsalocalcatalogthatdescribesallcopies
ofdatastoredatthatsite.
Inaddition,thecatalogatthebirthsiteforarelationis
responsibleforkeepingtrackofwherereplicasofthe
relationarestored.
50

51. I.Introduction to DDBMS
II.Architecture of DDBs
III.Storing data in DDBs
IV.Distributed Catalog management
V.Distributed Query Processing
VI.Transaction Processing
VII.Distributed concurrency control and recovery
DDBMS
2/12/201351
1. Parallel DB /D.S.Jagli 51
1. Parallel DB /D.S.Jagli

52. 5.Distributed Query Processing
2/12/20131. Parallel DB /D.S.Jagli52
Distributedqueryprocessing:Transformahigh-level
query(ofrelationalcalculus/SQL)onadistributeddatabase
(i.e.,asetofglobalrelations)intoanequivalentand
efficientlower-levelquery(ofrelationalalgebra)on
relationfragments.
Distributed query processing is more complex
1.–Fragmentation/replication of relations
2.–Additional communication costs
3.–Parallel execution
52

53. Distributed Query Processing Steps
2/12/20131. Parallel DB /D.S.Jagli53

54. 5.Distributed Query Processing
2/12/20131. Parallel DB /D.S.Jagli54
Sailors(sid: integer, sname: string, rating: integer, age: real)
Reserves(sid: integer, bid: integer, day: date, rname: string)
Assume Reserves and Sailors relations
each tuple of Reserves is 40 bytes long
a page can hold 100 Reserves tuples
1,000 pages of such tuples.
each tuple of Sailors is 50 bytes long
a page can hold 80 Sailors Tuples
500 pages of such tuples
How to estimate the cost?
54

55. 5.Distributed Query Processing
Criteria for measuring the cost of a query evaluation
strategy
For centralized DBMSs number of disk accesses (#
blocks read / written)
For distributed databases, additionally
The cost of data transmission over the network
Potential gain in performance from having several sites processing parts
of the query in parallel
2/12/20131. Parallel DB /D.S.Jagli55

56. 5.Distributed query processing
2/12/20131. Parallel DB /D.S.Jagli56
Toestimatethecostofanevaluationstrategy,inadditiontocounting
thenumberofpageI/Os.
wemustcountthenumberofpagesthatareshippedisa
communicationcosts.
Communicationcostsisasignificantcomponentofoverallcostina
distributeddatabase.
1.NonjoinQueriesinaDistributedDBMS
2.JoinsinaDistributedDBMS
3.Cost-BasedQueryOptimization
56

57. 5.Distributed Query Processing
1.Nonjoin Queries in a Distributed DBMS
Even simple operations such as scanning a relation, selection, and
projection are affected by fragmentation and replication.
SELECT S.age
FROM Sailors S
WHERE S.rating > 3 AND S.rating < 7
Suppose that the Sailors relation is horizontally fragmented, with all
tuples having a rating less than 5 at Mumbai and all tuples having a
rating greater than 5 at Delhi.
The DBMS must answer this query by evaluating it at both sites and
taking the union of the answers.
2/12/20131. Parallel DB /D.S.Jagli57
2/12/2013 57

58. 5.Distributed Query Processing
Eg 1: SELECT avg(age)
FROM Sailors S
WHERE S.rating > 3 AND S.rating < 7
taking the union of the answers is not enough
Eg 2: SELECT S.age
FROM Sailors S
WHERE S.rating > 6
taking the union of the answers is not enough
Eg 3: suppose that the Sailors relation is vertically fragmented, with the
sidand ratingfields at MUMBAI and the snameand agefields at
DELHI
Thisverticalfragmentationwouldbealossydecomposition
2/12/20131. Parallel DB /D.S.Jagli58

59. 5.Distributed Query Processing
Eg4:theentireSailorsrelationisstoredatbothMUMBAIandDELHI
sites.
Whereshouldthequerybeexecuted?
2JoinsinaDistributedDBMS
Eg:theSailorsrelationisstoredatMUMBAI,andthattheReserves
relationisstoredatDELHI.
Joinsofrelationsatdifferentsitescanbeveryexpensive.
JOIN STRATEGY
1.Fetch as needed
2.Ship whole
3.Semijoins
4.Bloomjoins
2/12/20131. Parallel DB /D.S.Jagli59
Which strategy is better for me?

60. 5.Distributed Query Processing
1.FetchAsNeeded
Page-orientedNestedLoopsjoin:ForeachpageofR,geteachpage
ofS,andwriteoutmatchingpairsoftuples<r,s>,whererisinR-page
andsisinS-page.
Wecoulddoapage-orientednestedloopsjoininMUMBAIwith
Sailorsastheouter,andforeachSailorspage,fetchallReservespages
fromDELHI.
IfwecachethefetchedReservespagesinMUMBAIuntilthejoinis
complete,pagesarefetchedonlyonce
2/12/20131. Parallel DB /D.S.Jagli60

61. Fetch As Needed: Transferring the relation
piecewise
2/12/20131. Parallel DB /D.S.Jagli61
QUERY: The query asks for R S

62. 5.Distributed Query Processing
2/12/20131. Parallel DB /D.S.Jagli62
Assume Reserves and Sailors relations
each tuple of Reserves is 40 bytes long
a page can hold 100 Reserves tuples
1,000 pages of such tuples.
each tuple of Sailors is 50 bytes long
a page can hold 80 Sailors Tuples
500 pages of such tuples
tdis cost to read/write page; tsis cost to ship page.
The cost is = 500tdto scan Sailors
for each Sailors page, the cost of scanning shipping all of Reserves, which is
=1000(td+ ts).
The total cost is = 500td + 500, 000(td+ ts).

63. 5.Distributed Query Processing
2/12/20131. Parallel DB /D.S.Jagli63
Thiscostdependsonthesizeoftheresult.
Thecostofshippingtheresultisgreaterthanthecostofshippingboth
SailorsandReservestothequerysite.
2.ShiptoOneSite(sort-merge-join)
ThecostofscanningandshippingSailors,savingitatDELHI,andthen
doingthejoinatDELHIis
=500(2td+ts)+(Result)td,
ThecostofshippingReservesanddoingthejoinatMUMBAIis
=1000(2td+ts)+(result)td.

64. Ship Whole: Transferring the complete
relation
2/12/20131. Parallel DB /D.S.Jagli64
QUERY: The query asks for R S

65. 5.Distributed Query Processing
2/12/20131. Parallel DB /D.S.Jagli65
Ship Whole vsFetch as needed:
Fetch as needed results in a high number of messages
Ship whole results in high amounts of transferred data
Note:SometuplesinReservesdonotjoinwithanytupleinSailors,we
couldavoidshippingthem.
3.SemijoinsandBloomjoins
Semijoins:3steps:
1.AtMUMBAI,computetheprojectionofSailorsontothejoincolumnsi.e
sidandshipthisprojectiontoDELHI.
2.2.AtDELHI,computethenaturaljoinoftheprojectionreceivedfrom
thefirstsitewiththeReservesrelation.
3.TheresultofthisjoiniscalledthereductionofReserveswithrespectto
Sailors.shipthereductionofReservestoMUMBAI.
4.3.AtMUMBAI,computethejoinofthereductionofReserveswith
Sailors.

66. Semijoin:
Semijoin: Requesting all join partners in just one step.
2/12/20131. Parallel DB /D.S.Jagli66

67. 5.Distributed query processing
2/12/20131. Parallel DB /D.S.Jagli67
Bloomjoins:3steps:
1.AtMUMBAI,Abit-vectorof(somechosen)sizekiscomputedby
hashingeachtupleofSailorsintotherange0tok−1andsettingbitito1.
ifsometuplehashestoi,and0otherwisethenshipthistoDELHI
2.AtDELHI,thereductionofReservesiscomputedbyhashingeachtuple
ofReserves(usingthesidfield)intotherange0tok−1,usingthesame
hashfunctionusedtoconstructthebit-vector,anddiscardingtuples
whosehashvalueicorrespondstoa0bit.shipthereductionofReserves
toMUMBAI.
3.AtMUMBAI,computethejoinofthereductionofReserveswithSailors.

68. Bloom join:
Bloom join:
Also known as bit-vector join
Avoiding to transfer all join attribute values to the other
node
Instead transferring a bitvector B[1 : : : n]
Transformation
Choose an appropriate hash function h
Apply h to transform attribute values to the range [1 : : : n]
Set the corresponding bits in the bitvector B[1 : : : n] to
2/12/20131. Parallel DB /D.S.Jagli68

69. Bloom join:
2/12/20131. Parallel DB /D.S.Jagli69

70. 2/12/20131. Parallel DB /D.S.Jagli70
Cost-Based Query Optimization
optimizing queries in a distributed database poses the following additional
challenges:
Communication costs must be considered. If we have several copies of a
relation, we must also decide which copy to use.
If individual sites are run under the control of different DBMSs, the
autonomy of each site must be respected while doing global query
planning.

71. Cost-Based Query Optimization
2/12/20131. Parallel DB /D.S.Jagli71
Cost-basedapproach;considerallplans,pickcheapest;similarto
centralizedoptimization.
Difference1:Communicationcostsmustbeconsidered.
Difference2:Localsiteautonomymustberespected.
Difference3:Newdistributedjoinmethods.
Querysiteconstructsglobalplan,withsuggestedlocalplansdescribing
processingateachsite.
Ifasitecanimprovesuggestedlocalplan,freetodoso.

72. 6.DISTRIBUTED TRANSACTIONS PROCESSING
2/12/20131. Parallel DB /D.S.Jagli72
Agiventransactionissubmittedatsomeonesite,butitcan
accessdataatothersites.
Whenatransactionissubmittedatsomesite,thetransaction
manageratthatsitebreaksitupintoacollectionofoneor
moresubtransactionsthatexecuteatdifferentsites.


73. 7.Distributed Concurrency Control
2/12/20131. Parallel DB /D.S.Jagli73
Lockmanagementcanbedistributedacrosssitesinmany
ways:
1.Centralized:Asinglesiteisinchargeofhandlinglockand
unlockrequestsforallobjects.
2.Primarycopy:Onecopyofeachobjectisdesignatedasthe
primarycopy.
Allrequeststolockorunlockacopyofthisobjectarehandled
bythelockmanageratthesitewheretheprimarycopyisstored.
3.Fullydistributed:Requeststolockorunlockacopyofan
objectstoredatasitearehandledbythelockmanageratthe
sitewherethecopyisstored.
1. Parallel DB /D.S.Jagli 73

74. 7.Distributed Concurrency Control
2/12/20131. Parallel DB /D.S.Jagli74
Distributed Deadlock Detection:
Each site maintains a local waits-for graph.
A global deadlock might exist even if the local graphs contain no cycles:
Three solutions:
Centralized: send all local graphs to one site ;
Hierarchical: organize sites into a hierarchy and send local graphs to parent
in the hierarchy;
Timeout : abort Xact if it waits too long.

75. 2/12/20131. Parallel DB /D.S.Jagli75
PhantomDeadlocks:delaysinpropagatinglocalinformationmight
causethedeadlockdetectionalgorithmtoidentify`deadlocks'thatdonot
reallyexist.Suchsituationsarecalledphantomdeadlocks

76. 7.Distributed Recovery
2/12/20131. Parallel DB /D.S.Jagli76
RecoveryinadistributedDBMSismorecomplicatedthanina
centralizedDBMSforthefollowingreasons:
1.Newkindsoffailurecanarise:
failureofcommunicationlinks.
failureofaremotesiteatwhichasubtransactionis
executing.
2.Eitherallsubtransactionsofagiventransactionmust
commit,ornonemustcommit.
3.Thispropertymustbeguaranteedinspiteofany
combinationofsiteandlinkfailures.

77. 7.Distributed Recovery
2/12/20131. Parallel DB /D.S.Jagli77
Two-PhaseCommit(2PC):
SiteatwhichXactoriginatesiscoordinator;
othersitesatwhichitexecutessubXactaresubordinates.
Whentheuserdecidestocommitatransaction:
Thecommitcommandissenttothecoordinatorforthe
transaction.
Thisinitiatesthe2PCprotocol:

78. 7.Distributed Recovery(2pc)
2/12/20131. Parallel DB /D.S.Jagli78
1.Coordinatorsendspreparemsgtoeachsubordinate.
2.Subordinateforce-writesanabortorpreparelogrecordandthen
sendsanooryesmsgtocoordinator.
3.Ifcoordinatorgetsallyesvotes,force-writesacommitlogrecordand
sendscommitmsgtoallsubs.Else,force-writesabortlogrec,and
sendsabortmsg.
4.Subordinatesforce-writeabort/commitlogrecbasedonmsgthey
get,thensendackmsgtocoordinator.
5.Coordinatorwritesendlogrecaftergettingackmsgfromallsubs

79. 2/12/20131. Parallel DB /D.S.Jagli79
TWO-PHASE COMMIT (2PC) -commit

80. 2/12/20131. Parallel DB /D.S.Jagli80
TWO-PHASE COMMIT (2PC) -ABORT

81. 7.Distributed Recovery(3pc)
2/12/20131. Parallel DB /D.S.Jagli81
Three-PhaseCommit
1.AcommitprotocolcalledThree-PhaseCommit(3PC)canavoid
blockingevenifthecoordinatorsitefailsduringrecovery.
2.Thebasicideaisthatwhenthecoordinatorsendsoutprepare
messagesandreceivesyesvotesfromallsubordinates.
3.Itsendsallsitesaprecommitmessage,ratherthanacommitmessage.
4.Whenasufficientnumbermorethanthemaximumnumberoffailures
thatmustbehandledofackshavebeenreceived.
5.Thecoordinatorforce-writesacommitlogrecordandsendsacommit
messagetoallsubordinates.

82. Distributed Database
Advantages:
Reliability
Performance
Growth (incremental)
Local control
Transparency
Disadvantages:
Complexity of Query
opt.
Concurrency control
Recovery
Catalog management
2/12/20131. Parallel DB /D.S.Jagli82

83. Thank you
Queries?
2/12/20131. Parallel DB /D.S.Jagli83