CSI2004 - Advanced Database

Management Systems
M ODULE - 2
Parallel Databases - Architecture
 Parallel Systems
 Parallel systems improve processing and I/O speeds by
using multiple processors and disks in parallel.
 Parallel database systems consist of multiple processors
and multiple disks connected by a fast interconnection
network.
 A coarse-grain parallel machine consists of a small
number of powerful processors
 A massively parallel or fine grain parallel machine
utilizes thousands of smaller processors.
 Two main performance measures:
 Throughput --- the number of tasks that can be
completed in a given time interval
 Response time --- the amount of time it takes to
complete a single task from the time it is submitted
 Speed-Up and Scale-Up

•Running a given task in less time by increasing the

degree of parallelism is called speedup.

•Handling larger tasks by increasing the degree of

parallelism is called scaleup
 Speed-Up and Scale-Up
 Speedup: a fixed-sized problem executing on a small system
is given to a system which is N-times larger.
 Measured by:
speedup = small system elapsed time
large system elapsed time

 Scaleup: increase the size of both the problem and the

system
 N-times larger system used to perform N-times larger job
 Measured by:
scaleup = small system small problem elapsed time
big system big problem elapsed time
 Factors Limiting Speedup and Scaleup

 Startup costs: Cost of starting up multiple processes may

dominate computation time, if the degree of parallelism is
high.
 Interference: Processes accessing shared resources (e.g.,
system bus, disks, or locks) compete with each other, thus
spending time waiting on other processes, rather than
performing useful work.
 Skew: Increasing the degree of parallelism increases the
variance in service times of parallely executing tasks.
Overall execution time determined by slowest of parallely
executing tasks. (By breaking down a single task into a
number of parallel steps, we reduce the size of the average
step.)
 SKEW

• It is often difficult to divide a task into exactly

equal-sized parts, and the way that the sizes are
distributed is therefore skewed.

• For example, if a task of size 100 is divided into 10

parts, and the division is skewed, there may be some
tasks of size less than 10 and some tasks of size
more than 10;
 Interconnection Network Architectures

 Bus. System components send data on and receive data

from a single communication bus;
 Does not scale well with increasing parallelism.
 Mesh. Components are arranged as nodes in a grid, and
each component is connected to all adjacent components
 Communication links grow with growing number of
components, and so scales better.
 But may require 2n hops to send message to a node (or
n with wraparound connections at edge of grid).
 Hypercube. Components are numbered in binary;
components are connected to one another if their binary
representations differ in exactly one bit.
 n components are connected to log(n) other components
and can reach each other via at most log(n) links;
reduces communication delays.
Interconnection Architectures
 Parallel Database Architectures

 Shared memory -- processors share a common

memory
 Shared disk -- processors share a common disk
 Shared nothing -- processors share neither a common
memory nor common disk
 Hierarchical -- hybrid of the above architectures
Parallel Database Architectures
 Shared Memory

 Processors and disks have access to a common

memory, typically via a bus or through an
interconnection network.
 Extremely efficient communication between
processors — data in shared memory can be accessed
by any processor without having to move it using
software.
 Downside – architecture is not scalable beyond 32 or
64 processors since the bus or the interconnection
network becomes a bottleneck
 Widely used for lower degrees of parallelism (4 to 8).
Shared Disk

 All processors can directly access all disks via an interconnection

network, but the processors have private memories.
 The memory bus is not a bottleneck
 Architecture provides a degree of fault-tolerance — if a
processor fails, the other processors can take over its tasks since
the database is resident on disks that are accessible from all
processors.
 Examples: IBM Sysplex and DEC clusters (now part of Compaq)
running Rdb (now Oracle Rdb) were early commercial users
 Downside: bottleneck now occurs at interconnection to the disk
subsystem.
 Shared-disk systems can scale to a somewhat larger number of
processors, but communication between processors is slower.
Shared Nothing

 Node consists of a processor, memory, and one or more

disks. Processors at one node communicate with another
processor at another node using an interconnection network.
A node functions as the server for the data on the disk or
disks the node owns.
 Examples: Teradata, Tandem, Oracle-n CUBE
 Data accessed from local disks (and local memory accesses)
do not pass through interconnection network, thereby
minimizing the interference of resource sharing.
 Shared-nothing multiprocessors can be scaled up to
thousands of processors without interference.
 Main drawback: cost of communication and non-local disk
access; sending data involves software interaction at both
ends.
 Shared Nothing

•Advantages:
•Number of processors used here is scalable. That is, the
design is flexible to add more number of computers.
•Unlike in other two architectures, only the data request which
cannot be answered by local processors need to be forwarded
through interconnection network.

•Disadvantages:
•Non-local disk accesses are costly. That is, if one server
receives the request. If the required data not available, it
must be routed to the server where the data is available. It is
slightly complex.
•Communication cost involved in transporting data among
computers.
1/11/2025 8:38:30 16
PM
 Hierarchical
 Combines characteristics of shared-memory, shared-disk,
and shared-nothing architectures.
 Top level is a shared-nothing architecture – nodes
connected by an interconnection network, and do not share
disks or memory with each other.
 Each node of the system could be a shared-memory system
with a few processors. (Base level)
 Alternatively, each node could be a shared-disk system
(Middle), and each of the systems sharing a set of disks
could be a shared-memory system.
 Reduce the complexity of programming such systems by
distributed virtual-memory architectures
 Since access speeds differ, also called non-uniform
memory architecture (NUMA)
 Data Partitioning Strategy – IO
Parallelism

1/11/2025 8:38:30 18
PM
 Data partitioning strategy

• Partitioning the tables/databases is very important step

in parallelizing the database activities.
• Reduce the time required to retrieve relations from disk by
partitioning the relations on multiple disks.
• By partitioning the data equally into many different
processors’ workload, we can achieve better performance
(better parallelism) of the whole system.
• We have the following types of fragmentation
(partitioning) techniques in Parallel database;
• Horizontal Fragmentation
• Vertical Fragmentation
 Horizontal partitioning – tuples of a relation are divided

among many disks such that each tuple resides on one disk.
 Data partitioning strategy
•Horizontal Fragmentation – Partitioning the tables using
the conditions specified through WHERE clause of SQL query
to distribute bunch of tuples (records). For example, consider
the following schema;
STUDENT (Regno, SName, Address, Branch, Phone)
•In this table, Branch column is used to store the academic
branch in which the student admitted in. suppose, there are
various branches like ‘BTech CIVIL’, ‘BTech MECH’,
‘BTech CSE’, and so on, then the following query would be
used to partition the table using horizontal partitioning.
SELECT * FROM student WHERE Branch = branch name;
•In the result, there won’t be any changes in the schema of the
table; i.e the structure of the table is unaltered. Only, ‘BTech
ECE’ students fragmented into one partition, ‘BTech CSE’
students fragmented into one partition and so on.
1/11/2025 8:38:30 20
PM
 Data partitioning strategy

•Vertical Fragmentation – Partitioning tables using the

decomposition rules to break and distribute the tables
into multiple partitions vertically (different schemas)
is called Vertical fragmentation.
•For example, if we would like to break STUDENT into
different tables like STUDENT(Regno, SName,
Address, Branch) and STU_PHONE(Regno,
Phone), i.e into two different schema on columns is
Vertical partitioning.
•Among the above discussed fragmentation techniques,
partitioning any relation with respect to Parallel
databases involves Horizontal Partitioning. Horizontal
data partition helps us to distribute the data into several
processors to execute queries on them simultaneously.
1/11/2025 8:38:30 21
PM
 Data partitioning strategy
•There are various partitioning strategies proposed to
manage the data distribution into multiple processors
evenly.
•Let us assume that in our parallel database system we
have n processors P0, P1, P2, …, Pn-1 and n disks D0, D1,
D2, …, Dn-1 where we partition our data.
•The value of n is chosen according to the degree of
parallelism required.
•The partitioning strategies are,
•Round-Robin Partitioning
•Hash Partitioning
•Range Partitioning
1/11/2025 8:38:30 22
PM
 Data Partitioning Strategy

Round-robin:
 Send the i th tuple inserted in the relation to disk
i mod n
 The round-robin scheme ensures an even distribution of
tuples across disks
 Example:
• If the number of available disks n is 10,
• then first record goes to D1 (1 mod 10 = 1),
• second record goes to D2 (2 mod 10 =2), and so on
• 10th record goes to D0 (10 mod 10 = 0),
• 11th record goes to D1 (11 mod 10 = 1)
• This scheme
1/11/2025 8:38:30 distributes data evenly in all the disks. 23
PM
 Data Partitioning Strategy
Hash partitioning:
Choose one or more attributes as the partitioning attributes.
 Choose hash function h with range 0…n - 1
If the hash function returns i, then the tuple is placed on disk
Di
•For example, consider the following table;
EMPLOYEE(ENo, EName, DeptNo, Salary, Age)
•If we choose DeptNo attribute as the partitioning attribute and
if we have 10 disks to distribute the data, then the following
would be a hash function;
h(DeptNo) = DeptNo mod 10
If we have 10 departments, then according to the hash function,
all the employees of department 1 will go into disk 1,
department 2 to
1/11/2025 8:38:30
disk 2 and so on. 24
PM
 Data Partitioning Strategy

Example:2
• If we choose the EName of the employees as
partitioning attribute, then we could have the
following hash function;
h(EName) = (Sum of ASCII value of every
character in the name) mod n,
•where n is the number of disks/partitions needed.

1/11/2025 8:38:30 25
PM
 Data Partitioning Strategy

Range partitioning:
This strategy distributes tuples by assigning
contiguous attribute-value ranges to each disk.
Choose an attribute as the partitioning attribute.
A partitioning vector [vo, v1, ..., vn-2] is chosen.
Consider a tuple t such that t [A] = x.
If x < v0, then t goes on disk D0.
If x ≥ vn−2, then t goes on disk Dn−1.
If vi ≤ x < vi+1, then t goes on disk Di+1.

Example, range partitioning with three disks

numbered 0, 1, and 2 may assign tuples with values less
than 5 to disk 0, values between 5 and 40 to disk 1, and
1/11/2025 8:38:30 26
values
PM greater than 40 to disk 2
 Data Partitioning Strategy
4 disks
•Example, for the EMPLOYEE relation given above, if
the partitioning attribute is Salary, then the vector would
be one as follows;
[5000, 15000, 30000],
where every value means the individual range of salaries.
 5000 represents the first range (0 – 5000),
 15000 represents the range (5001 –15000),
 30000 represents the third range (15001 – 30000),
 final range which is (30001 – rest).
 Hence, the vector with 3 values represents 4
disks/partitions.
1/11/2025 8:38:30 27
PM
 Data Partitioning Strategy
4 disks
•Example
•We have chosen the following vector as range vector;
•v [5000, 10000, 25000]
•These vector represents 4 partitions  5000 and less,
10000 and less, 25000 and less, and the other salary
values more than 25000. For this range vector, our data
will be :distributed as follows;
R7 (only record 7 is <=5000)
•Disk 0 : R5 (only record 5 is >5000 and <=10000)
•Disk 1 : R2, R3, R8 (the range >10000 and <=25000)
•Disk 2 : R4, R6 (the range >25000)
•Disk 3
1/11/2025 8:38:30 28
PM
 Data Partitioning Strategy

•Disadvantages:
• Execution Skew might occur.

•For example, the records in the range 10001 and 26000

falls in Disk 2 and 3.

•Unfortunately, because of the bad range vectors, disk 2

and 3 have more number of records compared to any
other disks.
•Hence, though the query needs to be executed at
Processor 2 and 3, it consumes more time as there are
more number of records.
1/11/2025 8:38:30 29
PM
 Data Partitioning Strategy -
Examples

1/11/2025 8:38:30 30
PM
 Data Partitioning Strategy

•Let us start with the following

table Emp_table.
•
•Emp_table instance has 14
records and every record
stores information about the
name of the employee;
his/her work grade, and the
department name.

•Assume that we have 3

processors namely P0, P1, P2,
and 3 Disks associated with
those 3 processors
1/11/2025 8:38:30
namely 31
D0, PM
D1, D2.
 Data Partitioning Strategy
•Round-Robin Partitioning:
•We partition records in a round-robin manner using the function
i mod n
•where i is the record position in the table and n is the number of
partitions/disks which is in our case 3.
•On the application of partitioning technique, first record goes into D1,
second record goes into D2, third record goes into D0, fourth record
goes into D1, and so on. After distribution of records, we will get the
following partitions; D1 D0

D2

1/11/2025 8:38:30 32
PM
 Data Partitioning Strategy
•Hash Partitioning:
•GRADE attribute of the Emp_table to explain Hash
partitioning.
•Let us choose a hash function as follows;
h(GRADE) = (GRADE mod n)
•where GRADE is the value of GRADE attribute of a record
and n is number of partitions which is 3 in our case.
•While applying the hash partitioning on GRADE, we will get
the following partitions of Emp_table.
•For example,
•GRADE of ‘Smith’ is 1 and hashing the function shows
partition 1 (1 mod 3 = 1).
•GRADE of ‘Blake’ is 4, then (4 mod 3=1) directs to
partition 1.
•GRADE of
1/11/2025 8:38:31
‘King’ is 5, then (5 mod 3=2) which directs
33
to
PMpartition 2.
 Data Partitioning Strategy
h(GRADE) =(GRADEmod n)

D0

D1

D2

1/11/2025 8:38:31 34
PM
 Data Partitioning Strategy

•Range Partitioning:
•GRADE of Emp_table to partition under range
partitioning.
•For applying range partition, we need to first identify
partitioning vector, [v0, v1, …, vn-2].
•Let us choose the following vector as range partitioning
vector for our case;
[2, 4]
•According to the vector, the records having the GRADE
value
•0 to 2  Partition 0,
•3 – 4 Partition 1
•Greater than 4  Partition 2
1/11/2025 8:38:31 35
PM
 Data Partitioning Strategy
GRADE
•0 to 2  Partition 0
D0
•3 – 4 Partition 1
•Greater than 4 
Partition 2

D1

D2
1/11/2025 8:38:31 36
PM
 Example-2

1/11/2025 8:38:31 37
PM
 Data Partitioning Strategy

•A table Employee with the schema Employee(ENo, EName,

DOB, Designation, Salary).
•We assume that Shared Nothing Parallel Architecture is used.
•For partitioning this table using Hash or Range partitioning
we need one or more attributes as partitioning attributes.
•Let us choose Salary as partitioning attribute.

1/11/2025 8:38:31 38
PM
 Data Partitioning Strategy

•Consider the salary values differently for different

partitioning.
•That is, treat the values as 100 to MAX for Round-
robin and
•Hash partitioning (not as group of values instead treat
as one group), and as different vectors for Range
partitioning

1/11/2025 8:38:31 39
PM
 Data Partitioning Strategy
•Round-Robin Technique
i mod n
•Here, variable i represents the position (physical order) of the
record in the actual table. Variable n represents the number of
target disks into which the table should be partitioned.
•For example, the records of Table 1, according to the function i
mod 4, will be sent to the 4 disks as follows;
• Disk 0 : R4, R8 (i.e, records with salary values 30011, and 21016 respectively)
• Disk 1 : R1, R5 (i.e, records with salary values 10002, and 9031 respectively)
• Disk 2 : R2, R6 (i.e, records with salary values 23000, and 29002 respectively)
• Disk 3 : R3, R7 (i.e, records with salary values 22051, and 4004 respectively)

1/11/2025 8:38:31 40
PM
 Data Partitioning Strategy

•Hash Partitioning
h (attribute mod n)
h (attribute mod n)
=h (salary mod 4)
=h(4004mod 4)
=0 Disk 0
•For this function, the records will be distributed as follows
•Disk 0 :R2, R7, R8
•Disk 1 :
•Disk 2 :R1, R6
•Disk 3 :R3, R4, R5

1/11/2025 8:38:31 41
PM
 Data Partitioning Strategy
•Range Partitioning
•For Range partitioning, we need a range vector.
•For this we have chosen the following vector as range vector;
•v [5000, 10000, 25000]
•These vector represents 4 partitions  5000 and less, 10000
and less, 25000 and less, and the other salary values more than
25000.
•For this range vector, our data will be distributed as follows;
•Disk 0 :R7 (only record 7 is <=5000)
•Disk 1 :R5 (only record 5 is >5000 and <=10000)
•Disk 2 :R2, R3, R8 (the range >10000 and <=25000)
•Disk 3 :R4, R6 (the range >25000)

1/11/2025 8:38:31 42
PM
 Data Partitioning Strategy

 Once a relation has been partitioned among several

disks, we can retrieve it in parallel, using all the disks.
 Similarly, when a relation is being partitioned, it can
be written to multiple disks in parallel.
 Thus, the transfer rates for reading or writing an entire
relation are much faster with I/O parallelism than
without it.
 However, reading an entire relation, or scanning a
relation, is only one kind of access to data.

1/11/2025 8:38:31 43
PM
 Data Partitioning Strategy

Access to data
1.Scanning the entire relation.

2.Locating a tuple associatively (for example, employee

name = “Campbell”); these queries, called point
queries, seek tuples that have a specified value for a
specific attribute.

3.Locating all tuples for which the value of a given

attribute lies within a specified range (for example,
10000 < salary < 20000); these queries are called range
queries.
1/11/2025 8:38:31 44
PM
 Data Partitioning Strategy
•Choosing the right partitioning technique
•Workload of the system
•What is the size of the database?
•How many users are accessing the system?
•What type of accesses they are? (reading/writing) and
so on.
•Type of data-accesses
(Scanning the entire relation, Point queries, Range
queries)
•Nature of data stored in the table.
•The data types
•Cardinality of data of every column (uniqueness of
values stored
1/11/2025 8:38:31
in a column) etc. 45
PM
Comparison of Partitioning Techniques

1/11/2025 8:38:31 46
PM
 Comparison of Partitioning Techniques

■ Round Robin
■ Advantages
• Best suited for scan of entire relation on each query.
• All disks have almost an equal number of tuples; retrieval
work is thus well balanced between disks.
• Both point and range queries are difficult to process
• No clustering -- tuples are scattered across all disks

1/11/2025 8:38:31 47
PM
Comparison of Partitioning Techniques

1/11/2025 8:38:31 48
PM
 Comparison of Partitioning Techniques

1/11/2025 8:38:31 49
PM
 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, resulting in skew
Can occur with range-partitioning and hash-partitioning.
Partition skew.
Refers to the fact that there may be load imbalance in the
partitioning, even when there is no attribute 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
1/11/2025 8:38:31 50
PM
 Handling of Skew
• Even a small skew can result in a significant decrease in
performance.

• Skew becomes an increasing problem with a higher degree of

parallelism.
• For example, if a relation of 1000 tuples is divided into 10 parts,
and the division is skewed, then there may be some partitions of
size less than 100 and some partitions of size more than 100; if
even one partition happens to be of size 200, the speedup that we
would obtain by accessing the partitions in parallel is only 5.

• If the same relation has to be partitioned into 100 parts, a partition

will have 10 tuples on an average. If even one partition has 40
tuples the speedup that we would obtain by accessing them in
parallel would be 25.

• Thus, we see that the loss of speedup due to skew increases with
parallelism
1/11/2025 8:38:31 51
PM
 Handling of Skew

1/11/2025 8:38:31 52
PM
 Handling of Skew
• 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

1/11/2025 8:38:31 53
PM
 Handling of Skew
• 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!
1/11/2025 8:38:31 54
PM