CSE 344: Section 7

Parallel Databases

​

November 18th, 2021

Administrivia

• HW5 Milestone 2 is due Today (Nov. 18)
• Prepare for HW6!
• Spec will be released soon!

​

• Agenda:
• Parallel databases
• MapReduce & Spark

Parallel DBs

Data Partitioning

We focus on shared-nothing architecture and intra-operator parallelism.

• Block Partition
• Tuples partitioned by raw size (no ordering considered)
• Hash partitioned on attribute A
• Node contains tuples with chosen attribute hashes
• Range partitioned on attribute A
• Node contains tuples in chosen attribute ranges

Distributed Query Processing

We only deal with shared-nothing architecture and intra-operator parallelism.

Horizontal Data Partitioning:

• Block Partition
• Hash partitioned on attribute A
• Range partitioned on attribute A

?????

Distributed Query Processing

We only deal with shared-nothing architecture and intra-operator parallelism.

Horizontal Data Partitioning:

• Block Partition
• Hash partitioned on attribute A
• Range partitioned on attribute A

?????

“Our processor/storage nodes are separate from each other and deal with only one operation at a time. We toss around whole tuples.”

Moving Data

We have a “network layer” to move tuples temporarily between nodes.

Transferring data is expensive, so we need to be efficient (especially on joins and grouping).

​

Moving Data:

Partitioned Hash-Join Mechanism

• Join on some attribute (e.g. R.x and S.y)
• Call hash function h(z)

Key Points:

• Hash shuffle tuples on join attributes

​

R1, S1

R2, S2

Rn, Sn

R1’, S1’

R2’, S2’

Rn’, Sn’

...

...

Contains tuples s.t.

h(R.x) = h(S.y) = red

Contains tuples s.t.

h(R.x) = h(S.y) = green

Contains

tuples s.t.

h(R.x) = h(S.y) = blue

​

Moving Data:

Broadcast Join Mechanism

Takes advantage of small datasets (can all fit into main memory)

​

Key Points:

• Partition type of R doesn’t matter
• S is unpartitioned and small
• Distribute S across all R

R1

R2

Rn

R1’, S

R2’, S

Rn’, S

...

...

S

Contains all of S

Contains all of S

Contains all of S

Now What?

“Cool. I know how to split data up and move it around efficiently. What does that have to do with my queries?”

Now What?

“Cool. I know how to split data up and move it around efficiently. What does that have to do with my queries?”

Query

Single Node Plan

Multi-Node Plan

Parallel Query Plans

Now, we need to know how to derive parallel plans from single node plans.

• Which RA operations can you do without talking to other nodes?
• Which RA operations require moving tuples?

⋈

σ

​

π

​

Parallel DB Practice!

We have a distributed database that holds the relations:

Drug(spec VARCHAR(255), compatibility INT)

Person(name VARCHAR(100) primary key, compatibility INT)

​

We want to compute:

SELECT P.name, count(D.spec)

FROM Person AS P, Drug AS D

WHERE P.compatibility = D.compatibility

GROUP BY P.name;

​

Drug is block-partitioned

Person is hash-partitioned on compatibility [h(n)]

​

You have three nodes. Draw a parallel query plan.

​

​

Ɣ_{P.name, count(D.spec)}(P ⋈ D)

Node 1

Node 2

Node 3

P ⋈ D

⋈

⋈

Ɣ_{P.name,count(D.spec)}

Ɣ

Ɣ

Hash [h(n)] Drug on compatibility

Takes advantage of:

1. Hash partitioning of [h(n)]
2. PK uniqueness of name

Block partitioning of Drug

MapReduce and Spark

Apache

Cluster-computing framework

Apache Hadoop MapReduce vs. Apache Spark

https://www.datamation.com/data-center/hadoop-vs.-spark-the-new-age-of-big-data.html

Hadoop MapReduce

Hadoop Distributed File System (HDFS): Store and manage access to

large files (tables) that are terabytes or petabytes large with MapReduce Job

​

High Level Steps:

• Map Task (EmitIntermediate)
• Reduce Task (Emit)

Fault Tolerance (Frequently write intermediate files to disk)

Counting Words w/ MapReduce

map(String key, String value):

​

// key: document name

// value: document contents

​

for each word w in value:

emitIntermediate(w, “1”);

reduce(String key, Iterator values):

// key: a word

// values: a list of counts

​

int result = 0;

for each v in values:

result += ParseInt(v);

emit(AsString(result));

Spark (HW6)

Resilient Distributed Datasets (RDD)

High level commands:

• Transformations (map, join, sort…) - Lazy
• Actions (count, reduce, save...) - Eager

Fault Tolerance (Uses main memory)

Spark Objects

HW6 Tip!

Row

RowFactory.create(Objects...)

Dataset<Row>

JavaRDD<Row>

JavaPairRDD<K, V>

Tuple2<> (You can leave the generics empty)

​

Spark Methods

HW6 Tip!

spark.sql(“SELECT ... FROM ...”) (spark must be a SparkSession)

d.filter(t -> f(t) == true/false)

d.distinct()

d.map() (d must be a JavaRDD)

d.mapToPair(t -> new Tuple2<>(K, V))

d.reduceByKey((v1, v2) -> f(v1, v2)) (d must be a JavaPairRDD)

Worksheet!