Handling of Skew


Handling of Skew
􀂄 The distribution of tuples to disks may be skewed — that is,
some disks have many tuples, while others may have fewer
tuples.
􀂄 Types of skew:
􀃌 Attribute-value skew.
􀂾 Some values appear in the partitioning attributes of many tuples;
all the tuples with the same value for the partitioning attribute
end up in the same partition.
􀂾 Can occur with range-partitioning and hash-partitioning.
􀃌 Partition skew.
􀂾 With range-partitioning, badly chosen partition vector may assign
too many tuples to some partitions and too few to others.
􀂾 Less likely with hash-partitioning if a good hash-function is
chosen.

Handling Skew in Range-Partitioning
􀂄 To create a balanced partitioning vector (assuming partitioning
attribute forms a key of the relation):
􀃌 Sort the relation on the partitioning attribute.
􀃌 Construct the partition vector by scanning the relation in sorted order
as follows.
􀂾 After every 1/nth of the relation has been read, the value of the
partitioning attribute of the next tuple is added to the partition
vector.
􀃌 n denotes the number of partitions to be constructed.
􀃌 Duplicate entries or imbalances can result if duplicates are present in
partitioning attributes.
􀂄 Alternative technique based on histograms used in practice

Handling Skew using Histograms
􀂄 Balanced partitioning vector can be constructed from histogram in a
relatively straightforward fashion
􀂄 Assume uniform distribution within each range of the histogram
􀂄 Histogram can be constructed by scanning relation, or sampling
(blocks containing) tuples of the relation

Handling Skew Using Virtual Processor
Partitioning
􀂄 Skew in range partitioning can be handled elegantly using virtual
processor partitioning:
􀃌 create a large number of partitions (say 10 to 20 times the number
of processors)
􀃌 Assign virtual processors to partitions either in round-robin fashion
or based on estimated cost of processing each virtual partition
􀂄 Basic idea:
􀃌 If any normal partition would have been skewed, it is very likely the
skew is spread over a number of virtual partitions
􀃌 Skewed virtual partitions get spread across a number of processors,
so work gets distributed evenly!



Comments

Post a Comment

Popular posts from this blog

Fragment-and-Replicate Join

Fragment-and-Replicate Join 􀂄 Partitioning not possible for some join conditions 􀃌 e.g., non-equijoin conditions, such as r.A > s.B. 􀂄 For joins were partitioning is not applicable, parallelization can be accomplished by fragment and replicate technique 􀃌 Depicted on next slide 􀂄 Special case – asymmetric fragment-and-replicate: 􀃌 One of the relations, say r, is partitioned; any partitioning technique can be used. 􀃌 The other relation, s, is replicated across all the processors. 􀃌 Processor Pi then locally computes the join of ri with all of s using any join technique. 􀂄 General case: reduces the sizes of the relations at each processor. 􀃌 r is partitioned into n partitions,r0, r1, ..., r n-1;s is partitioned into m partitions, s0, s1, ..., sm-1. 􀃌 Any partitioning technique may be used. 􀃌 There must be at least m * n processors. 􀃌 Label the processors as 􀃌 P0,0, P0,1, ..., P0,m-1, P1,0, ..., Pn-1m-1. 􀃌 Pi,j computes the join of ri with sj. In ...
Read more

USER INTERFACE DESIGN FOR ANNA UNIVERSITY SYLLABUS

Unit – I Introduction Objective To Understand the definition and importance of User Interface Design To know about the concept, advantages and applications of GUI and Web interface User Interface Design Definition • User interface design is a subset of a field of study called human-computer interaction (HCI). Human-computer interaction is the study, planning, and design of how people and computers work together so that a person’s needs are satisfied in the most effective way. • The user interface is the part of a computer and its software that people can see, hear, touch, talk to, or otherwise understand or direct. The user interface has essentially two components: input and output. • Input is how people communicate his needs to the system using keyboard or any pointing device and output is how the system returns processing result to user through screen or sound. • The best interface is one which has proper design with combination of effective input and output mechanisms. Importance of...
Read more