Class Note for CMPSCI 645 at UMass(5)
Class Note for CMPSCI 645 at UMass(5)
Popular in Course
Popular in Department
This 47 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at University of Massachusetts taught by a professor in Fall. Since its upload, it has received 18 views.
Reviews for Class Note for CMPSCI 645 at UMass(5)
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 02/06/15
g I Evaluation of Relational Operations CMPSCI 645 Mar 11 2008 Slides Courtesy of R Ramakrishnan and Gehrke Relational Operations 9 We will consider how to implement Selection 0 Selects a subset of rows from relation Projection 75 Deletes unwanted columns from relation 39 m gtltl Allows us to combine two relations Setdifterence Tuples in reln 1 but not in reln 2 Union U Tuples in reln 1 and in reln 2 Aggregation SUM MIN etc and GROUP BY Order By Returns tuples in specified order rt After we cover the operations we will discuss how to optimize queries formed by composing them Outline 6 Sorting oz Evaluation of joins oz Evaluation of other operations Why Sort 3 A classic problem in computer science oz Important utility in DBMS I Data requested in sorted order e g ORDER BY eg find students in increasing gpa order I Sorting useful for eliminating duplicates e g SELECT DISTINCT I Sortmerge join algorithm involves sorting I Sorting is first step in bulk loading B tree index 3 Problem sort 1Gb of data with 1Mb of RAM 2Way Sort Requires 3 Bu ers oz Pass 1 Read a page sort it write it only one buffer page is used 3 Pass 2 3 etc three buffer pages used I My 11 1 I I Disk Main memory buffers Disk TwoWay External Merge Each pass we read write each page in file 2N N pages in the file gt the number of passes l39log2 N I 1 So total cost is 2Nlog2 N39 1 Idea Divide and conquer sort subfiles and merge Sort 34 26 49 78 56 13 23 47 13 46 89 56 2 23 44 12 67 35 89 6 I 12 23 34 45 66 78 9 I Input file PASS 0 2 1pageruns PASS 1 2page runs PASS 2 4page runs PASS 3 8page runs General External Merge Sort n More than 3 buffer pages How can we utilize them 3 To sort a file with N pages using B buffer pages Pass 0 use B buffer pages Produce N B sorted runs of B pages each Pass 2 etC merge B1 runs Disk B Main memory buffers Disk Cost of External Merge Sort 3 Number of passes 1 1083 1fN B 3 Cost 2N of passes oz Eg with 5 buffer pages to sort 108 page file Pass 0 108 5 22 sorted runs of 5 pages each last run is only 3 pages Pass 1 22 4 6 sorted runs of 20 pages each last run is only 8 pages Pass 2 2 sorted runs 80 pages and 28 pages Pass 3 Sorted file of 108 pages Number of Passes of External Sort N B3 B5 B9 B17 B129 B257 100 7 4 3 2 1 1 1000 10 5 4 3 2 2 10000 13 7 5 4 2 2 100000 17 9 6 5 3 3 1000000 20 10 7 5 3 3 10000000 23 12 8 6 4 3 100000000 26 14 9 7 4 4 1000000000 30 15 10 8 5 4 Replacement Sort li 8 12 Produces sorted runs as long 10 3 as possible 4 Pick tuple r in the current set with the smallest value that Input Current Set Output is 2 largest value in output 1 buffer B2 buffers 1 buffer e g 8 in the example Fill the space in current set by adding tuples from input Write output buffer out if full extending the current run Current run terminates if every tuple in the current set is smaller than the largest tuple in output When used in Pass 0 for sorting can write out sorted runs of size 2B on average 10 Blocked 10 for External Merge Sort 3 longer runs often means fewer passes 3 Actually we don t do 10 a page at a time oz In fact read a block of pages sequentially 3 Suggests we should make each buffer input output be a block of pages But this will reduce fanout during merge passes In practice most files still sorted in 23 passes 11 Number of Passes 0f Optimized Sort N B1000 B5000 B10000 100 1 1 1 1000 1 1 1 10000 2 2 1 100000 3 2 2 1000000 3 2 2 10000000 4 3 3 100000000 5 3 3 1000000000 5 4 3 It Block size 32 12 Double Bu ering 3 To reduce wait time for IO request to complete can prefetch into shadow block Potentially more passes in practice most files L111 sorted in 23 passes INPUT 139 INPUT 239 OUTPUT39 lt gt b block size INPUT k39 B main memory buffers kway merge 13 Sorting Records oz Sorting has become highly competitive Parallel sorting is the name of the game oz Datamation sort benchmark Sort 1M records of size 100 bytes in 1985 15 minutes World records 118 seconds 1998 record 39 16 offtheshelf PC each with 2 Pentium processor tow hard disks running NT40 3 New benchmarks proposed Minute Sort How many can you sort in 1 minute Dollar Sort How many can you sort for 100 14 Using B Trees for Sorting 3 Scenario Table to be sorted has B tree index on sorting columns oz Idea Can retrieve records in order by traversing leaf pages oz Is this a good idea oz Cases to consider Good idea Could be a very bad idea B tree is Clustered B tree is not Clustered 15 Clustered B Tree Used for Sorting 4 Cost root to the left 9 If Alternative 2 is used Index most leaf then retrieve Directs search all leaf pages Alternative 1 Data Entries Data Records Additional cost of retrieving data records each page fetched just once n Always better than external sorting 16 Unclustered B Tree Used for Sorting oz Alternative 2 for data entries each data entry contains rid of a data record In general one 10 per data record Worse case 1 O pN p records per page N pages in file Index Directs search 393939 3939 39 Data Entries quotSequence setquot quotquot39quot3939Jquot3939 quot3939quot39 quot W Data Records 17 g I External Sorting vs Unclustered Index N Sorting p1 p10 p100 100 200 100 1000 10000 1000 2000 1000 10000 100000 10000 40000 10000 100000 1000000 100000 600000 100000 1000000 10000000 1000000 8000000 1000000 10000000 100000000 10000000 80000000 10000000 100000000 1000000000 n p of records per page M B1000 and block size32 for sorting n p100 is the more realistic value 18 Summary oz External sorting is important DBMS may dedicate part of buffer pool for sorting 3 External merge sort minimizes disk lO cost Pass 0 Produces sorted runs of size B buffer pages Later passes merge runs of runs merged at a time depends on B and block size Larger block size means less I 0 cost per page Larger block size means smaller runs merged In practice of runs rarely more than 2 or 3 3 Clustered B tree is good for sorting unclustered tree is usually very bad 19 Outline 6 Sorting oz Evaluation of joins oz Evaluation of other operations 20 Some Common Techniques 0 Algorithms for evaluating relational operators use some simple ideas extensively I Indexing Can use WHERE conditions to retrieve small set of tuples selections joins I Iteration Sometimes faster to scan all tuples even if there is an index And sometimes we can scan the data entries in an index instead of the table itself I Partitioning By using sorting or hashing we can partition the input tuples and replace an expensive operation by similar operations on smaller inputs Watch for these techniques as we discuss query evaluation 21 Schema for Examples Sailors sid integer sname string rating integer age real Reserves sid integer bid integer day date rname string 3 Reserves Each tuple is 40 bytes long 100 tuples per page 1000 pages 3 Sailors Each tuple is 50 bytes long 80 tuples per page 500 pages 22 Equality oins With One loin Column SELECT FROM Reserves R1 Sailors S1 WHERE R1sidS1sid 3 In algebra R gtlt1 S Common relational operation I R X S is large R X S followed by a selection is inefficient I Must be carefully optimized ozo Assume M pages in R pR tuples per page N pages in S pS tuples per page In our examples R is Reserves and S is Sailors oz We will consider more complex join conditions later oz Cost metric of 103 We will ignore output costs 23 Simple Nested Loops loin foreach tuple r in R do foreach tuple s in S do if r1 sj then add ltr sgt to result oz For each tuple in the outer relation R we scan the entire inner relation S Cost M pR M N 1000 1001000500 1000 5 107 105 Assuming each I 0 takes 10 ms the join will take about 140 hours 24 PageOriented Nested Loops loin 3 For each age of R get each page of S and write out matching pairs of tuples ltr sgt where r is in Rpage and Sis in Spage Cost M M N 1000 1000500 501000 IOs Assuming each I 0 takes 10 ms the join will take about 14 hours 3 Choice of the smaller relation as the outer If smaller relation S is outer cost 500 5001000 500500 I Os 25 Block Nested Loops loin 4 Take the smaller relation say R as outer the other as inner 4 Use one buffer for scanning the inner S one buffer for output and use all remaining buffers to hold block of outer R For each matching tuple r in R block s in Spage add ltr sgt to result Then read next page in 8 until S is finished Then read next R block scan S R in R l amp S Hash table for block ofR JO 9811 t k lt Bl pages I 6 Input buffer for S Output buffer 26 g I Examples of Block Nested Loops 3 Cost Scan of outer outer blocks scan of inner outer blocks pages of outer block size Given available buffer size B block size is at most B2 MNMB2 oz With Sailors S as outer a block has 100 pages of S Cost of scanning S is 500 I Os a total of 5 blocks Per block of S we scan Reserves 51000 I Os Total 500 5 1000 5500 IOs a little over 1 minute 27 Index Nested Loops loin foreach tuple r in R do foreach tuple s in S Where r1 sj do add ltr sgt to result oz If there is an index on the join column of one relation say S can make it the inner and exploit the index Cost M MpR cost of finding matching S tuples oz For each R tuple cost of probing S index is about 12 for hash index 24 for B tree Cost of then finding S tuples assuming Alt 2 or 3 for data entries depends on clustering Clustered index 1 l O typical Unclustered up to 1 l 0 per matching S tuple 28 g I Examples of Index Nested Loops oz Hashindex Alt 2 on sid of Sailors as inner Scan Reserves 1000 page I Os 1001000 tuples For each Reserves tuple 12 l Os to get data entry in index plus 1 l O to get the exactly one matching Sailors tuple Total 1000 100100022 221000 I Os 3 Hashindex Alt 2 on sid of Reserves as inner Scan Sailors 500 page I Os 80500 tuples For each Sailors tuple 12 l Os to find index page with data entries plus cost of retrieving matching Reserves tuples If uniform distribution 25 reservations per sailor 100000 40000 Cost of retrieving them is 1 or 25 l Os cluster Total 500805002237 88500148500 l Os 29 SortMerge loin R S 3 1 m R and S on the join column 2 Merge them on join col and output result tuples oz Merge repeat until either R or S is finished Scanning Advance scan of R until current Rtuplegtcurrent S tuple advance scan of S until current Stuplegtcurrent R tuple do this until current R tuple current S tuple Matching Now all R tuples with same value in Ri current R group and all S tuples with same value in Sj current S group match output ltr sgt for all pairs of such tuples oz R is scanned once each S group is scanned once per matching R tuple Multiple scans of an S group are likely to find needed pages in buffer 30 Example of SortMerge loin E m day mame g I 28 103 12496 guppy 22 dustin 7 4 50 28 1 03 1 1396 yuppy 28 yuppy 9 3 50 3 1 1 o 1 1 01 096 dustln 3 1 lubber 8 555 3 1 1 02 1 01 296 lubber 44 guppy 5 350 3 1 1 o 1 1 01 196 lubber 58 rusty 1 0 350 58 1 03 1 11296 dustin sid sname rating age 1 Cost M log M N log N MN 39 The cost of merging MN could be MN very unlikely MN is guaranteed in foreign key join why As with sorting log M and log N are small numbers eg 3 4 4 With 35 100 or 300 buffer pages both Reserves and Sailors can be sorted in 2 passes total join cost 7500 BNL cost 2500 B300 5500 B100 15000 B35 31 st Partitioning Partition Hashloin both relations using hash fn h R tuples in partition i will only match S tuples in partition i Probing Read in partition i of R build hash table on Ri using h2 ltgt hl Scan partition i of S search for matches Original Relation OUTPUT Partitions EE 1 INPUT 2 t h h funiiion h 0 0 0 El Bl B main memory buffers Disk Join Result Disk Partitions of R amp S Hash table for partltlon hash Ri k lt B1 pages fn h2 0 O 0 h2 0 0 0 Output El Inplgrb liffer buffer V B main memory buffers Disk 32 Observations on Hashloin oz partitions S B 1 and size of largest partition S B 2 to be held in memory Assuming uniformly sized partitions we get M 13 1 lt 13 2 ie B must be gt W Hashjoin works if the smaller relation satisfies above 3 If we build an inmemory hash table to speed up the matching of tuples a little more memory is needed oz If hash function h does not partition uniformly one or more R partitions may not fit in memory Can apply hashjoin technique recursively to do the join of this Rpartition with corresponding Spartition 33 Cost ofHashIoin 3 Partitioning readswrites both relns 2MN Probing reads both relns MN l Os The total is 3MN I In our running example a total of 4500 l Os using hash join less than 1 min compared to 140 hours W NLJ 3 SortMerge Join vs Hash Join Given a minimum amount of memory both have a cost of 3MN l Os Hash Join superior on this count if relation sizes differ greatly Assuming MltN What if sqrtM lt B lt sqrtN Also Hash Join is shown to be highly parallelizable SortMerge less sensitive to data skew result is sorted 34 General loin Conditions oz Equalities over several attributes e g RsidSsid AND RrnameSsname For Index NL build index on ltsid snamegt S is inner or use existing indexes on sid or smime and check the other join condition on the fly For SortMerge and Hash Join sort partition on combination of the two join columns 3 Inequality conditions eg Rrname lt Ssname For Index NL need B tree index 39 Range probes on inner matches likely to be much higher than for equality joins clustered index is much preferred Hash Join Sort Merge Join not applicable Block NL quite likely to be a Winner here 35 Outline 6 Sorting oz Evaluation of joins oz Evaluation of other operations 36 Using an Index for Selections 3 Cost depends on qualifying tuples and clustering Cost of finding qualifying data entries typically small plus cost of retrieving records could be large W o Clustering Consider a selection of the form gpa gt 30 and assume 10 of tuples qualify 100 pages 10000 tuples With a Clustered index cost is little more than 100 1 OS if unclustered upto 10000 1 OS 339 Important re nement for nnclnstered indexes 1 Find qualifying data entries 2 Sort the rid s of the data records to be retrieved 3 Fetch rids in order 37 Two Approaches to General Selections oz First approach 1 Find the most selective access path retrieve tuples using it and 2 apply any remaining terms that don t match the index on the y Most selective access path An index or file scan that we estimate will require the fewest page 1 OS Terms that match this index reduce the number of tuples retrieved other terms are used to discard some retrieved tuples but do not affect number of tuples pages fetched Consider daylt8994 AND bid5 AND sid3 A B tree index on day can be used then bid5 and sid3 must be checked for each retrieved tuple A hash index on ltbid sidgt could be used daylt8994 must then be checked on the fly 38 Intersection of Kids 1 Second approach if we have 2 or more matching indexes that use Alternatives 2 or 3 for data entries Get sets of rids of data records using each matching index Then intersect these sets of rids Retrieve the records and apply any remaining terms Consider daylt8994 AND bid5 AND sid3 If we have a B tree index on day and an index on sid both using Alternative 2 we can retrieve rids of records satisfying daylt8994 using the first rids of records satisfying sid3 using the second intersect these rids retrieve records and check bid5 39 The Projection Operation SELECT DISTINCT Rsid Rbid FROM Reserves R 3 Projection consists of two steps Remove unwanted attributes ie those not specified in the projection Eliminate any duplicate tuples that are produced 39339 Algorithms single relation sorting and hashing based on all remaining attributes 40 Projection Based on Sorting 3 Modify Pass 0 of external sort to eliminate unwanted fields Thus runs of about 2B pages are produced but tuples in runs are smaller than input tuples Size ratio depends on and size of fields that are dropped 3 Modify merging passes to eliminate duplicates Thus number of result tuples smaller than input Difference depends on of duplicates 3 Cost In Pass 0 read original relation size M write out same number of smaller tuples ln merging passes fewer tuples written out in each pass Using Reserves example 1000 input pages reduced to 250 in Pass 0 if size ratio is 025 41 Projection Based on Hashing 3 Partitioning phase Read R using one input buffer For each tuple discard unwanted fields apply hash function hi to choose one of Bl output buffers Result is Bl partitions of tuples with no unwanted fields 2 tuples from different partitions guaranteed to be distinct 339 Duplicate elimination phase For each partition read it and build an inmemory hash table using hash fn h2 ltgt hi on all fields while discarding duplicates If partition does not fit in memory can apply hashbased projection algorithm recursively to this partition 42 Discussion of Projection 3 Sortbased approach is the standard better handling of skew and result is sorted oz If an index on the relation contains all wanted attributes in its search key can do index only scan Apply projection techniques to data entries much smaller oz If an ordered ie tree index contains all wanted attributes as prefix of search key can do even better Retrieve data entries in order indexonly scan discard unwanted fields compare adjacent tuples to check for duplicates 43 Set Operations 3 Intersection and crossproduct special cases of join I Intersection equality on all fields 3 Union Distinct and Except similar we ll do union oz Sorting based approach to union Sort both relations on combination of all attributes Scan sorted relations and merge them removing duplicates oz Hash based approach to union Partition R and S using hash function h For each S partition build inmemory hash table using h2 Scan R partition For each tuple probe the hash table If the tuple is in the hash table discard it OW add it to the hash table 44 Aggregate Operations AVG MIN etc ozo Without grouping In general requires scanning the relation Given index whose search key includes all attributes in the SELECT or WHERE clauses can do indexonly scan oz With grouping GROUP BY Sort on groupby attributes then scan relation and compute aggregate for each group Can improve upon this by combining sorting and aggregate computation Similar approach based on hashing on groupby attributes Given tree index whose search key includes all attributes in SELECT WHERE and GROUP BY clauses can do indexonly scan if groupby attributes form pre x of search key can retrieve data entries tuples in groupby order 45 Summary 3 A virtue of relational DBMSS queries are composed of a few basic operators the implementation of these operators can be carefully tuned 3 Algorithms for evaluating relational operators use some simple ideas extensively I Indexing Can use WHERE conditions to retrieve small set of tuples selections joins I Iteration Sometimes faster to scan all tuples even if there is an index And sometimes we can scan the data entries in an index instead of the table itself I Partitioning By using sorting or hashing we can partition the input tuples and replace an expensive operation by similar operations on smaller inputs 46 Summary contd 3 Many implementation techniques for each operator no universally superior technique for most operators 3 Must consider available alternatives for each operation in a query and choose best one based on I system state e g memory and I statistics table size tuples matching value k 3 This is part of the broader task of optimizing a query composed of several ops 47
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'