ParallelDBMS

1、1Parallel DBMSSlides adapted from textbook; from Joe Hellerstein; and from Jim Gray, Microsoft Research. DBMS Textbook Chapter 222Why Parallel Access To Data?1 Terabyte10 MB/s At 10 MB/s1.2 days to scan 1 Terabyte1,000 x parallel1.5 minute to scan.Parallelism: divide a big problem into many smaller

2、ones to be solved in parallel. Bandwidth3Parallel DBMS: IntroductionnParallelism natural to DBMS processingPipeline parallelism: many machines each doing one step in a multi-step process. Partition parallelism: many machines doing the same thing to different pieces of data.Both are natural in DBMS!P

3、ipelinePartitionAny Sequential ProgramAny Sequential ProgramSequentialSequentialSequentialSequentialAny Sequential ProgramAny Sequential Programoutputs split N ways, inputs merge M ways4DBMS: The | Success StorynDBMSs are among most (only?) successful application of parallelism.Teradata, Tandem vs.

4、Thinking Machines, Every major DBMS vendor has some | serverWorkstation manufacturers depend on | DB server sales.nReasons for success:Bulk-processing (= partitioned |-ism).Natural pipelining.Inexpensive hardware can do the trick!Users/app-prog. dont need to think in |5Some | TerminologynSpeed-UpMor

5、e resources means proportionally less time for given amount of data.nScale-UpIf resources increased in proportion to increase in data size, time is constant.degree of |-ismXact/sec.(throughput)Idealdegree of |-ismsec./Xact(response time)Ideal6Architecture Issue: Shared What?Shared Memory (SMP)Shared

6、 DiskShared Nothing (network)CLIENTSCLIENTSCLIENTSMemoryProcessorsEasy to programExpensive to buildDifficult to scaleupHard to programCheap to buildEasy to scaleupSequent, SGI, SunVMSclusterTandem, Teradata7What Systems Work This WayShared NothingTeradata: 400 nodesTandem: 110 nodesIBM / SP2 / DB2:

7、128 nodesInformix/SP2 48 nodesATT & Sybase ? nodesShared DiskOracle170 nodesDEC Rdb 24 nodesShared MemoryInformix 9 nodes RedBrick ? nodesCLIENTSMemoryProcessorsCLIENTSCLIENTS(as of 9/1995)8Different Types of DBMS |-ismnIntra-operator parallelismget all machines working to compute a given operat

8、ion (scan, sort, join)nInter-operator parallelismeach operator may run concurrently on a different site (exploits pipelining)nInter-query parallelismdifferent queries run on different site Well focus on intra-operator |-ism 9Automatic Data PartitioningPartitioning a table:RangeHashRound RobinShared-

9、disk and -memory less sensitive to partitioning, Shared nothing benefits from good partitioning !A.E F.J K.N O.S T.ZA.E F.J K.N O.S T.ZA.E F.J K.N O.S T.ZGood for group-by,range queries, andalso equip-joinGood for equijoins Good to spread load;Most flexible - but10Parallel ScansnScan in parallel, an

10、d merge.nSelection may not require access of all sites for range or hash partitioning.nIndexes can be built at each partition.nQuestion: How do indexes differ in the different schemes?Think about both lookups and inserts!11Parallel SortingnNew records again and again:8.5 Gb/minute, shared-nothing; D

11、atamation benchmark in 2.41 secs (UCB students)nIdea: Scan in parallel, and range-partition as you go.As tuples come in, begin “local” sorting on eachResulting data is sorted, and range-partitioned.Problem: skew!Solution: “sample” data at start to determine partition points. 12Jim Gray & Gordon

12、Bell: VLDB 95 Parallel Database Systems SurveyParallel AggregatesA.EF.JK.NO.ST.ZA TableCountCountCountCountCountCountnFor each aggregate function, need a decomposition:count(S) = S S count(s(i), ditto for sum()avg(S) = (S S sum(s(i) / S S count(s(i)nFor groups:Sub-aggregate groups close to source.Pa

13、ss each sub-aggregate to its groups site.13Parallel JoinsnNested loop:Each outer tuple must be compared with each inner tuple that might join.Easy for range partitioning on join cols, hard otherwise!nSort-Merge (or plain Merge-Join):Sorting gives range-partitioning.Merging partitioned tables is loca

14、l.14Parallel Hash JoinnIn first phase, partitions get distributed to different sites:A good hash function distributes work evenlynDo second phase at each site.nAlmost always the winner for equi-join.Original Relations(R then S)OUTPUT2B main memory buffersDiskDiskINPUT1hashfunctionhB-1Partitions12B-1

15、. . .Phase 115Dataflow Network for | JoinnGood use of split/merge makes it easier to build parallel versions of sequential join code.16Complex Parallel Query Plans nComplex Queries: Inter-Operator parallelismPipelining between operators: nsort and phase 1 of hash-join block the pipeline!Bushy TreesA

16、BRSSites 1-4Sites 5-8Sites 1-817NM-way ParallelismA.EF.JK.NO.ST.ZMergeJoinSortJoinSortJoinSortJoinSortJoinSortMergeMergeN inputs, M outputs, no bottlenecks.Partitioned DataPartitioned and Pipelined Data Flows18ObservationsnIt is relatively easy to build a fast parallel query executornIt is hard to w

17、rite a robust high-quality parallel query optimizer:There are many tricks.One quickly hits the complexity barrier.19Parallel Query OptimizationnCommon approach: 2 phasesPick best sequential plan (System R algo)Pick degree of parallelism based on current system parameters.n“Bind” operators to process

18、orsTake query tree, “decorate” with assigned processor20nBest serial plan != Best | plan ! nWhy?nTrivial counter-example:Table partitioned with local secondary index at two nodesRange query: all data of node 1 and 1% of node 2.Node 1 should do a scan of its partition.Node 2 should use secondary index. SELECT * FROM telephone_book WHERE name “NoGood”;Whats Wrong With That?N.ZTableScanA.MIndex Scan21Parallel DBMS Summaryn|-ism natural to query processing:Both pipeline and partition |-ism!nS