Quizmaster

Learning objectives

What you will be able to explain

You are evaluating a data processing application to run on a parallel database. Through profiling, you determine that 80% of the workload can be parallelized, while the remaining 20% is strictly serial. According to Amdahl's Law, how many processor cores ( $N$ ) would you need to provision to achieve a speedup of exactly 4?
An analytics team is scaling up their workload. As they add more processing power, they proportionately increase the size of the dataset they analyze. They observe that on a 100-node cluster, the scaled speedup is 90.1. Using Gustafson's Law, calculate the serial fraction ( $1-P$ ) of this workload.
What is the theoretical maximum speedup limit as $N \to \infty$ for a program governed by Amdahl's Law if $P = 0.75$ ?
Which of the following phenomena can theoretically cause a super-linear speedup in a parallel database system?
Which scaling metric describes the rate at which solution time varies with the number of processors for a fixed total problem size?
In the context of distributed vs. parallel databases, which of the following is a defining characteristic of a strictly distributed database?

Section 01

You are evaluating a data processing application to run on a parallel database. Through profiling, you determine that 80% of the workload can be parallelized, while the remaining 20% is strictly serial. According to Amdahl's Law, how many processor cores ( $N$ ) would you need to provision to achieve a speedup of exactly 4? to What is the theoretical maximum speedup limit as $N \to \infty$ for a program governed by Amdahl's Law if $P = 0.75$ ?

You are evaluating a data processing application to run on a parallel database. Through profiling, you determine that 80% of the workload can be parallelized, while the remaining 20% is strictly serial. According to Amdahl's Law, how many processor cores ( $N$ ) would you need to provision to achieve a speedup of exactly 4?

Path of Calculation: 1. Use Amdahl's Law for fixed-size speedup:

S = \frac{1}{(1 - P) + \frac{P}{N}}

. 2. Substitute the given values:

S = 4

P = 0.8

. 3.

4 = \frac{1}{0.2 + \frac{0.8}{N}}

. 4. Invert both sides:

0.2 + \frac{0.8}{N} = 0.25

. 5. Isolate the parallel term:

\frac{0.8}{N} = 0.05

. 6. Solve for

N

N = \frac{0.8}{0.05} = 16

. Interpretation: - With a 20% serial part, you need 16 processors to reach speedup 4. - This also illustrates diminishing returns: adding more cores cannot overcome the serial bottleneck indefinitely. Final Answer: 16 processors.

An analytics team is scaling up their workload. As they add more processing power, they proportionately increase the size of the dataset they analyze. They observe that on a 100-node cluster, the scaled speedup is 90.1. Using Gustafson's Law, calculate the serial fraction ( $1-P$ ) of this workload.

Path of Calculation: 1. Apply Gustafson's Law (scaled speedup):

S(N) = (1 - P) + N \cdot P

. 2. Plug in

S(N)=90.1

and

N=100

90.1 = (1-P) + 100P = 1 + 99P

. 3. Rearrange:

89.1 = 99P

. 4. Solve:

P = \frac{89.1}{99} = 0.9

. 5. Serial fraction is

(1-P) = 1 - 0.9 = 0.1

. Interpretation: - About 90% of the scaled workload behaves as parallel work. - About 10% remains effectively serial even under scaling. Final Answer: 0.1 (10%).

What is the theoretical maximum speedup limit as $N \to \infty$ for a program governed by Amdahl's Law if $P = 0.75$ ?

For Amdahl's Law, as

N \to \infty

, the parallel term

\frac{P}{N}

tends to 0, so the limit becomes:

S_{max} = \frac{1}{1-P}

. With

P=0.75

S_{max}=\frac{1}{0.25}=4.0

. So even infinitely many processors cannot exceed speedup 4 because the serial fraction (25%) dominates the limit.

Section 02

Which of the following phenomena can theoretically cause a super-linear speedup in a parallel database system? to In the context of distributed vs. parallel databases, which of the following is a defining characteristic of a strictly distributed database?

Which of the following phenomena can theoretically cause a super-linear speedup in a parallel database system?

Statement-by-statement: - A is False: making

(1-P)=0

gives at best linear speedup, not super-linear by itself. - B is True: extra aggregate memory can reduce paging and cache misses, sometimes yielding more-than-linear improvement relative to a memory-constrained baseline. - C is True: cache effects can make later accesses cheaper across cooperating cores, improving observed performance beyond linear expectations. - D is True: avoiding duplicated work through shared intermediate results can reduce total work, making measured speedup appear super-linear. Therefore, B/C/D are the super-linear mechanisms, not A.

Which scaling metric describes the rate at which solution time varies with the number of processors for a fixed total problem size?

Strong scaling asks: if the total problem size stays fixed, how does runtime change as processors increase? That matches the question exactly. - Weak scaling keeps work per processor fixed while total problem size grows. - Elastic/pipeline scaling are not the standard metric names in this context. So the correct metric is Strong scaling.

In the context of distributed vs. parallel databases, which of the following is a defining characteristic of a strictly distributed database?

A strictly distributed database is characterized by loose coupling and potential site autonomy. This means nodes can be geographically separated, possibly heterogeneous, and may continue local operation independently. Options A and B describe tightly coupled parallel systems, and D is too narrow because distributed design also emphasizes autonomy, availability, and federation concerns.

Section 03

In a [Select: Shared Memory / Shared Disk / Shared Nothing] architecture, several nodes with multiple CPUs have their own private memory but access a single attached storage array (like a NAS or SAN). to According to the slides, what is a major problem for query processing in a heterogeneous distributed database?

In a [Select: Shared Memory / Shared Disk / Shared Nothing] architecture, several nodes with multiple CPUs have their own private memory but access a single attached storage array (like a NAS or SAN).

The key signature is: - each node has private CPU and memory, - but all nodes access the same storage subsystem. That is exactly Shared Disk architecture. Shared Memory would imply a common memory space, and Shared Nothing would require private memory and private storage per node.

Which of the following are recognized challenges or limitations of the Shared-Nothing architecture as clusters scale up? (Select all that apply)

Why each option: - A is not the typical core limitation for shared-nothing; cache-coherency bottlenecks are mainly a shared-memory concern. - B is a real risk: without replication, node loss implies partition/data loss. - C is real: communication and coordination overhead rise with cluster size, flattening speedup curves. - D is real: replicated data requires consistency mechanisms, which add protocol and synchronization cost. Therefore B, C, and D are correct.

According to the slides, what is a major problem for query processing in a heterogeneous distributed database?

In heterogeneous distributed databases, local systems often model similar entities differently (different attribute names, structures, keys, types). This schema heterogeneity is a major obstacle for distributed query planning and integration because query rewriting, mapping, and semantic reconciliation become necessary.

Section 04

To mitigate the bottlenecks of traditional Shared-Nothing architectures (like IP stack message passing), modern architectures propose separating state and compute. Which technology is specifically cited to handle ALL communication to enable this scalability? to Which of the following are characteristics of Pipeline Parallelism (Inter-Operator Parallelism) in databases? (Select all that apply)

To mitigate the bottlenecks of traditional Shared-Nothing architectures (like IP stack message passing), modern architectures propose separating state and compute. Which technology is specifically cited to handle ALL communication to enable this scalability?

RDMA is explicitly used to bypass much of the traditional networking software overhead (kernel/network stack involvement) and enable low-latency, high-throughput remote memory operations. That is why it is cited as the communication substrate for scalable disaggregated state/compute architectures.

Historically, how has the evolution of network bandwidth compared to CPU computing power?

Historically, CPU compute capability improved faster than network bandwidth/latency. This creates a communication bottleneck in distributed/parallel systems: compute gets cheaper faster than moving data. Hence communication-aware design (locality, reduced shuffle, RDMA, compression) becomes critical.

Which of the following are characteristics of Pipeline Parallelism (Inter-Operator Parallelism) in databases? (Select all that apply)

Pipeline (inter-operator) parallelism means different operators/stages run concurrently on streaming data. - A is wrong: that describes hardware instruction pipelining/superscalar execution, not DB operator pipelines. - B is correct: multiple operator pipelines can run in parallel while each pipeline stage is often a single execution thread context. - C is not generally true; pipeline boundaries can still require buffering/backpressure coordination. - D is correct: uneven operator costs (e.g., huge build side vs tiny one) can cause severe imbalance. Therefore B and D are correct.

Section 05

Utilizing the vector units of a CPU (e.g., SSE, MMX) to execute the exact same operation on different independent subsets of data is an example of: to Evaluate the following statements regarding Data Parallelism:

Utilizing the vector units of a CPU (e.g., SSE, MMX) to execute the exact same operation on different independent subsets of data is an example of:

Vector instructions apply the same operation to many data elements at once (SIMD style), which is a canonical form of data parallelism. It is not task parallelism (different tasks), nor inter-operator pipeline parallelism.

Which type of parallelism is specifically highlighted as important for highly analytical scenarios (OLAP)?

OLAP queries are typically large scans/joins/aggregations within a single query. To accelerate them, the system parallelizes work inside one query plan across many threads/cores/nodes, i.e., Intra-Query Parallelism. Inter-query parallelism is more relevant for high-throughput OLTP mixes.

Evaluate the following statements regarding Data Parallelism:

Statement-by-statement: - A is False: many filters are tuple-local predicates and do not require a global view. - B is True: in theory, filtering can be partitioned very finely (up to tuple granularity). - C is True: group-by/aggregation usually requires co-locating identical grouping keys (or a final combine step after partitioned partial aggregation). Hence A is False, B/C are True.

Section 06

What are the disadvantages of fully replicating a relation across all sites? (Select all that apply) to Which partitioning strategy guarantees an equal number of tuples per set but results in no apparent relationship between the tuples within that set?

What are the disadvantages of fully replicating a relation across all sites? (Select all that apply)

Fully replicating data improves read locality/availability, but introduces costs: - B is correct: every logical update must be propagated to all replicas, increasing write overhead. - D is correct: concurrency control/consistency management becomes more complex across replicas. - A is false because replication usually increases (not decreases) availability. - C is false because replication can still support parallel reads. So B and D are the disadvantages.

Complete the statement:

Range partitioning explicitly defines value boundaries over one or more columns and assigns tuples by where their key values fall. That is exactly what the prompt describes. Round robin ignores key values; hash uses hash functions rather than explicit domain bounds.

Which partitioning strategy guarantees an equal number of tuples per set but results in no apparent relationship between the tuples within that set?

Round Robin distributes tuples cyclically, so partition cardinalities are typically balanced. However, tuples in the same partition have no key-based locality relationship, which can hurt pruning and locality-sensitive queries. That combination matches the question description.

Section 07

What is an extreme form of vertical partitioning mentioned in the lecture? to In a distributed transaction, what are the responsibilities of the local transaction manager? (Select all that apply)

What is an extreme form of vertical partitioning mentioned in the lecture?

Vertical partitioning splits attributes (columns) across storage segments. A column store is the extreme case where each column is effectively stored independently, maximizing columnar access efficiency for analytics. So the lecture's extreme vertical form is Column stores.

Evaluate these statements about partitioning:

Statement-by-statement: - A is True: horizontal partitions keep the same schema and split by rows. - B is True: vertical partitioning needs a shared key to reconstruct full tuples by joining fragments. - C is True: partitioned lifecycle management often allows dropping entire old partitions efficiently. Therefore all three are True.

In a distributed transaction, what are the responsibilities of the local transaction manager? (Select all that apply)

In the referenced architecture split, local transaction managers primarily: - maintain local recovery state/logging (B), and - coordinate concurrency for transactions executing at that site (D). Starting global transactions or distributing subtransactions is typically associated with higher-level/global transaction management responsibilities in this lecture framing.

Section 08

During the Two-Phase Commit (2PC) algorithm, what causes the coordinator to make an "abort" decision during the second phase? to Which failure type is unique to distributed systems compared to single-node monolithic systems?

During the Two-Phase Commit (2PC) algorithm, what causes the coordinator to make an "abort" decision during the second phase?

In 2PC, the coordinator first collects votes from participants. If any participant votes NO (or cannot safely commit), the global decision must be ABORT to preserve atomicity. Only unanimous YES votes allow COMMIT.

Why is the Two-Phase Commit (2PC) protocol fundamentally flawed in certain failure scenarios (often requiring 3PC as a solution)?

2PC is blocking because participants may be left in an uncertain state after voting YES, waiting for the coordinator's final decision. If coordinator or network fails at that point, they may have to block until recovery resolves the outcome. That failure mode motivates protocols such as 3PC (under stronger assumptions).

Which failure type is unique to distributed systems compared to single-node monolithic systems?

Network partitioning means nodes are alive but mutually unreachable due to connectivity splits. This failure mode is specific to distributed systems and directly impacts consensus, commit protocols, and data consistency behavior.

Section 09

Distributed join transfer volume: broadcasting vs partitioned shuffle to Regarding data distribution, the "Mantra" of Distributed DBMS is:

Distributed join transfer volume: broadcasting vs partitioned shuffle

Path of Calculation: 1. Strategy 1 (broadcast small relation

S

): - Ship all of

S

to Node A. - Transfer volume =

10 \times 100 = 1{,}000

bytes. 2. Strategy 2 (2-way perfect hash shuffle): - Half of

R

must cross from A to B:

5{,}000 \times 100 = 500{,}000

bytes. - Half of

S

must cross from B to A:

5 \times 100 = 500

bytes. - Initial shuffle total =

500{,}000 + 500 = 500{,}500

bytes. 3. The problem explicitly says to ignore final-result transfer, so only base relation movement is counted. Interpretation: - Broadcasting the tiny relation is dramatically cheaper here. - This is a classic small-table broadcast join scenario. Final Answer: - Strategy 1: 1,000 bytes - Strategy 2 (initial shuffle): 500,500 bytes

Guided checkpoint

Compute network transfer volume for two execution strategies of $R \bowtie S$ .

Node	Relation	Cardinality	Tuple size
A	$R$	10,000 tuples	100 bytes/tuple
B	$S$	10 tuples	100 bytes/tuple

Strategy 1 (Broadcasting)

Ship all of $S$ to Node A and execute the join locally on Node A.

Strategy 2 (Partitioned Shuffling)

Hash-partition both $R$ and $S$ perfectly evenly across Node A and Node B; each node joins its local halves.

Ignore the final result payload. Report only base-relation bytes transferred over the network.

When evaluating distributed join strategies, which of the following is an expected factor when extending the physical algebra?

Centralized physical algebra mostly models local operators (scan, join, sort, etc.). Distributed optimization must additionally model data movement between sites because it can dominate cost. Therefore explicit communication operators such as send/receive are introduced into the physical plan.

Regarding data distribution, the "Mantra" of Distributed DBMS is:

The mantra 'Data Locality first' means computations should run where data already resides whenever possible. Reducing data movement usually improves both performance and scalability in distributed systems because network is expensive relative to local memory/CPU operations.

Section 10

How does "skew" affect a parallel query execution even if "high locality" is achieved? to Which factors must a distributed query optimizer consider that a centralized optimizer does not? (Select all that apply)

How does "skew" affect a parallel query execution even if "high locality" is achieved?

Even with high locality, skew causes some workers/partitions to receive much more work or data than others. That creates stragglers, lowers effective parallelism, and can dominate end-to-end runtime. So skew negates parallel gains through imbalance.

Complete the statement:

The scenario describes many threads collaborating on different parts/phases of one join execution pipeline for a single query. That is Intra-Query parallelism. Inter-Query would mean different independent queries in parallel, and instruction-level refers to micro-architectural execution details.

Which factors must a distributed query optimizer consider that a centralized optimizer does not? (Select all that apply)

A distributed optimizer must reason about dimensions absent in centralized settings: - A: network shipping costs for moving intermediate/base data. - B: heterogeneous per-node processing capabilities and placement effects. - C: network variability/congestion, which introduces uncertainty into cost estimates. D (disk cylinder count) is not the defining distributed-specific factor in this context.

Section 11

According to the slides, what is the consequence of low locality in a partitioned database?

Low locality means needed data for a task is not co-located with compute/partition ownership, so large cross-node shuffles are required. The consequence described in the slides is effectively broad spread of partition ownership and heavy redistribution overhead, which matches option B.

Knowledge check

Turn understanding into recall.

The quiz now follows the same concepts in scored form. You can return to this lesson from the quiz whenever a gap appears.

Start the quiz →Back to course

What you will be able to explain

What is the theoretical maximum speedup limit as N→∞N \to \inftyN→∞ for a program governed by Amdahl's Law if P=0.75P = 0.75P=0.75?

Which of the following phenomena can theoretically cause a super-linear speedup in a parallel database system? to In the context of distributed vs. parallel databases, which of the following is a defining characteristic of a strictly distributed database?

Which of the following phenomena can theoretically cause a super-linear speedup in a parallel database system?

Which scaling metric describes the rate at which solution time varies with the number of processors for a fixed total problem size?

In the context of distributed vs. parallel databases, which of the following is a defining characteristic of a strictly distributed database?

In a [Select: Shared Memory / Shared Disk / Shared Nothing] architecture, several nodes with multiple CPUs have their own private memory but access a single attached storage array (like a NAS or SAN).

Which of the following are recognized challenges or limitations of the Shared-Nothing architecture as clusters scale up? (Select all that apply)

According to the slides, what is a major problem for query processing in a heterogeneous distributed database?

To mitigate the bottlenecks of traditional Shared-Nothing architectures (like IP stack message passing), modern architectures propose separating state and compute. Which technology is specifically cited to handle ALL communication to enable this scalability?

Historically, how has the evolution of network bandwidth compared to CPU computing power?

Which of the following are characteristics of Pipeline Parallelism (Inter-Operator Parallelism) in databases? (Select all that apply)

Utilizing the vector units of a CPU (e.g., SSE, MMX) to execute the exact same operation on different independent subsets of data is an example of: to Evaluate the following statements regarding Data Parallelism:

Utilizing the vector units of a CPU (e.g., SSE, MMX) to execute the exact same operation on different independent subsets of data is an example of:

Which type of parallelism is specifically highlighted as important for highly analytical scenarios (OLAP)?

Evaluate the following statements regarding Data Parallelism:

What are the disadvantages of fully replicating a relation across all sites? (Select all that apply) to Which partitioning strategy guarantees an equal number of tuples per set but results in no apparent relationship between the tuples within that set?

What are the disadvantages of fully replicating a relation across all sites? (Select all that apply)

Complete the statement:

Which partitioning strategy guarantees an equal number of tuples per set but results in no apparent relationship between the tuples within that set?

What is an extreme form of vertical partitioning mentioned in the lecture? to In a distributed transaction, what are the responsibilities of the local transaction manager? (Select all that apply)

What is an extreme form of vertical partitioning mentioned in the lecture?

Evaluate these statements about partitioning:

In a distributed transaction, what are the responsibilities of the local transaction manager? (Select all that apply)

During the Two-Phase Commit (2PC) algorithm, what causes the coordinator to make an "abort" decision during the second phase? to Which failure type is unique to distributed systems compared to single-node monolithic systems?

During the Two-Phase Commit (2PC) algorithm, what causes the coordinator to make an "abort" decision during the second phase?

Why is the Two-Phase Commit (2PC) protocol fundamentally flawed in certain failure scenarios (often requiring 3PC as a solution)?

Which failure type is unique to distributed systems compared to single-node monolithic systems?

Distributed join transfer volume: broadcasting vs partitioned shuffle to Regarding data distribution, the "Mantra" of Distributed DBMS is:

Distributed join transfer volume: broadcasting vs partitioned shuffle

Strategy 1 (Broadcasting)

Strategy 2 (Partitioned Shuffling)

When evaluating distributed join strategies, which of the following is an expected factor when extending the physical algebra?

Regarding data distribution, the "Mantra" of Distributed DBMS is:

How does "skew" affect a parallel query execution even if "high locality" is achieved? to Which factors must a distributed query optimizer consider that a centralized optimizer does not? (Select all that apply)

How does "skew" affect a parallel query execution even if "high locality" is achieved?

Complete the statement:

Which factors must a distributed query optimizer consider that a centralized optimizer does not? (Select all that apply)

According to the slides, what is the consequence of low locality in a partitioned database?

According to the slides, what is the consequence of low locality in a partitioned database?

Turn understanding into recall.

What is the theoretical maximum speedup limit as $N \to \infty$ for a program governed by Amdahl's Law if $P = 0.75$ ?