Quizmaster

Learning objectives

What you will be able to explain

Which Relational Algebra operator is conceptually equivalent to a Cartesian Product followed by a Selection?
Which of the following are considered "Base Operators" of Relational Algebra according to the slides?
Identify whether the following statements about the Iterator (Volcano) Model are True or False:
In a Volcano-style Iterator model, a query plan consists of a Project operator sitting above a Selection operator, which sits above a Table Scan. The table contains 5,000 tuples. The Selection operator has a selectivity of 10% (i.e., 500 tuples pass). How many total `GetNext()` calls will the Selection operator receive from the Project operator?
In the Iterator model, which function is responsible for initializing data structures and calling the initialization of child operators, without producing any records?
Match the processing model to its respective intra-operator granularity:

Section 01

Which Relational Algebra operator is conceptually equivalent to a Cartesian Product followed by a Selection? to Identify whether the following statements about the Iterator (Volcano) Model are True or False:

Which Relational Algebra operator is conceptually equivalent to a Cartesian Product followed by a Selection?

A theta-join can be expressed as Selection(predicate) applied to a Cartesian Product, so Join is the relational algebra operator that captures that combined behavior.

Which of the following are considered "Base Operators" of Relational Algebra according to the slides?

In this course framing, Selection (sigma), Projection (pi), and Cartesian Product (x) are treated as base operators. Join and Intersection can be expressed from base operators, so they are not selected here.

Identify whether the following statements about the Iterator (Volcano) Model are True or False:

A) True: Volcano is tuple-at-a-time pull execution. B) False: control flow is decentralized via operator calls, not a central scheduler. C) True: operators can pipeline tuples immediately. D) False: per-tuple virtual calls increase instruction overhead and hurt cache locality.

Section 02

In a Volcano-style Iterator model, a query plan consists of a Project operator sitting above a Selection operator, which sits above a Table Scan. The table contains 5,000 tuples. The Selection operator has a selectivity of 10% (i.e., 500 tuples pass). How many total `GetNext()` calls will the Selection operator receive from the Project operator? to Match the processing model to its respective intra-operator granularity:

In a Volcano-style Iterator model, a query plan consists of a Project operator sitting above a Selection operator, which sits above a Table Scan. The table contains 5,000 tuples. The Selection operator has a selectivity of 10% (i.e., 500 tuples pass). How many total `GetNext()` calls will the Selection operator receive from the Project operator?

Project pulls one tuple at a time from Selection. With 500 qualifying tuples, it needs 500 successful `GetNext()` calls plus one extra call to receive end-of-stream (`NotFound`). Total calls are 501.

In the Iterator model, which function is responsible for initializing data structures and calling the initialization of child operators, without producing any records?

`Open()` initializes operator state and recursively opens children before tuple production begins. `GetNext()` produces tuples, and `Close()` releases resources.

Match the processing model to its respective intra-operator granularity:

Iterator processes one tuple per call, materialization processes full operator outputs at once, and vectorization processes fixed-size batches. So the correct mapping is tuple-at-a-time, operator-at-a-time, batch-at-a-time.

Section 03

Regarding Pipelining vs. Blocking operators: to A database uses Morsel-Driven Parallelism. A specific Table Scan operator needs to process a table containing 2,450,000 tuples. If the system uses the standard morsel size of 100,000 tuples mentioned in the lecture, how many morsels (tasks) will be created for this operator?

Regarding Pipelining vs. Blocking operators:

A) True: selection can stream tuples as they pass predicates. B) False: sort is blocking because it needs all input first. C) True: hash-join build must consume/build before probing. D) True: probe can then stream matches and be pipelined.

Which processing model is described as a "two-edged sword" because it is cache-efficient for code but can lead to intermediate results that do not fit in memory?

Materialization has good code locality because each operator runs over its full input, but it creates potentially large intermediate results. That trade-off is why it is called a two-edged sword.

A database uses Morsel-Driven Parallelism. A specific Table Scan operator needs to process a table containing 2,450,000 tuples. If the system uses the standard morsel size of 100,000 tuples mentioned in the lecture, how many morsels (tasks) will be created for this operator?

Morsels are chunked tasks: ceil(2,450,000 / 100,000) = ceil(24.5) = 25. That is 24 full morsels and one partial morsel.

Section 04

What is the primary motivation for using Query Compilation in modern DBMS? to In the Produce/Consume model of query compilation, what occurs during the "Produce Phase"?

What is the primary motivation for using Query Compilation in modern DBMS?

Query compilation removes repeated interpreter overhead (virtual dispatch, type checks, generic expression evaluation) by generating specialized machine code for the plan.

Which of the following systems are identified in the slides as using a "Compilation-based, data-centric, push-based execution" model?

HyPer, Umbra, and Impala are highlighted as compilation-oriented, data-centric, push-based systems in the lecture context. The other listed systems are associated with different primary execution styles.

In the Produce/Consume model of query compilation, what occurs during the "Produce Phase"?

During Produce, the system identifies/constructs pipelines (bounded by blocking operators). Consume is where generated code pushes tuples through those pipeline stages.

Section 05

About Parallel Execution in the Volcano model using Exchange Operators: to Which term describes the policy of picking one tuple and applying all possible operations to it before moving to the next tuple, as seen in compilation-based models?

About Parallel Execution in the Volcano model using Exchange Operators:

A) False: exchange operators encapsulate parallelism so most operators remain unchanged. B) True: static partitioning can create load imbalance. C) False: degree is usually fixed per instantiation. D) True: one operator pipeline instance is commonly created per worker thread.

Consider a Materialization Model where a query performs a Scan on Table A (10,000 rows, 50 bytes per row) followed by a Filter with 20% selectivity. The Filtered output is then Joined with Table B (which is already materialized in memory). How much memory (in bytes) is required to store the intermediate result produced specifically by the Filter operator?

Filter output cardinality is 10,000 x 0.20 = 2,000 rows. At 50 bytes each, intermediate materialized size is 2,000 x 50 = 100,000 bytes.

Which term describes the policy of picking one tuple and applying all possible operations to it before moving to the next tuple, as seen in compilation-based models?

Data-centric execution keeps work focused on one tuple (or small chunk) through multiple operations before moving on. That improves register reuse and reduces intermediate materialization.

Section 06

Which of the following are "Derived Operators" in Relational Algebra? to In a Vectorization Model, a Scan operator processes a table with 8,200 tuples. The vector size is configured to be 500 tuples. How many total calls to the `next()` function are made to the Scan operator by the operator above it (including the call that returns `NotFound`)?

Which of the following are "Derived Operators" in Relational Algebra?

In the lecture's decomposition, Intersection and Join are derived because they can be expressed via combinations of base operators. Difference and Union are treated differently in this specific classification.

What is the major drawback of the Compilation-based approach for short-running queries?

Compilation has startup cost: generating and compiling code can dominate runtime for very short queries. This overhead is the main downside for short-lived workloads.

In a Vectorization Model, a Scan operator processes a table with 8,200 tuples. The vector size is configured to be 500 tuples. How many total calls to the `next()` function are made to the Scan operator by the operator above it (including the call that returns `NotFound`)?

The scan returns ceil(8,200/500)=17 data batches (16 full + 1 partial). One additional call is needed to detect end-of-stream, so total `next()` calls are 18.

Section 07

Regarding Inter-operator execution: to What is a "Pipeline Breaker"?

Regarding Inter-operator execution:

A) True: pull means downstream requests tuples. B) True: push means upstream emits tuples downstream. C) False: Volcano iterator is pull-based. D) True: compiled data-centric pipelines are typically push-oriented.

Which Relational Algebra operator is used to translate "Bags" to "Sets" (de-duplication)?

Distinct/Unique converts bag semantics to set semantics by removing duplicates. Grouping may also deduplicate in some cases, but the direct operator for bag-to-set conversion is Distinct.

What is a "Pipeline Breaker"?

A pipeline breaker is a blocking operator that must consume all (or a major partition of) input before emitting first output, such as sort or hash-build phases.

Section 08

Which of the following are advantages of the Vectorization Model? to In the context of DBMS architecture shown in the slides:

Which of the following are advantages of the Vectorization Model?

Vectorization reduces per-tuple call overhead by processing batches and enables hardware-friendly optimizations (SIMD/cache behavior). It does not remove all materialization, and optimal vector size is workload-dependent.

In a Produce/Consume query compilation model, a query involves joining three tables: $R \bowtie S \bowtie T$ . The joins are implemented as Hash Joins where $R$ is used to build the first hash table, $S$ is used to build the second hash table, and $T$ is the probe relation. How many separate pipelines will the Produce Phase identify?

Each hash-table build phase is blocking and forms its own pipeline boundary: one pipeline for building on R, one for building on S, and one final pipeline for scanning T and probing. Total pipelines are 3.

In the context of DBMS architecture shown in the slides:

A) True: parser -> optimizer -> execution manager is the standard query path. B) True: access methods belong to storage-engine components. C) False: transaction management is separate from the query processor. D) True: buffer manager is also part of storage-engine infrastructure.

Section 09

Which research prototype is associated with the Vectorization Model (specifically the X100 project)? to Which of the following are motivations for the "Data-centric" approach in query compilation?

Which research prototype is associated with the Vectorization Model (specifically the X100 project)?

The X100 vectorized execution project is associated with MonetDB and influenced later analytical execution engines.

In Morsel-driven parallelism, how are morsels assigned to threads?

Morsel-driven execution uses a shared task queue and runtime scheduling so idle threads can take new morsels, which improves load balancing.

Which of the following are motivations for the "Data-centric" approach in query compilation?

Data-centric compilation keeps data in registers longer, reduces memory traffic by avoiding unnecessary intermediates, and allows cross-operator compiler optimization. It is the opposite of adding virtual-call overhead.

Section 10

A query plan in the Iterator model has a Join operator on top of two Scan operators. The left table (outer) has 100 tuples and the right table (inner) has 1,000 tuples. If the join is a Nested Loop Join (without indexes), how many total `GetNext()` calls will the Join operator make to the inner Scan operator? to Regarding the Logical-Physical Mapping:

A query plan in the Iterator model has a Join operator on top of two Scan operators. The left table (outer) has 100 tuples and the right table (inner) has 1,000 tuples. If the join is a Nested Loop Join (without indexes), how many total `GetNext()` calls will the Join operator make to the inner Scan operator?

Without indexes, each of 100 outer tuples scans the full inner stream. One inner scan costs 1,000 successful calls plus one end call, so total inner `GetNext()` calls are 100 x 1,001 = 100,100.

In the Produce/Consume model, which phase is responsible for "filling" the pipeline with operators and pushing tuples towards the consuming operator?

Produce defines/opens pipeline structure, while Consume emits tuple-processing code that actually pushes tuples through downstream operators. So pipeline filling and tuple pushing happen in Consume.

Regarding the Logical-Physical Mapping:

A) True: logical joins can map to physical nested loops (among others). B) True: a selection predicate may map to index access if an index satisfies it. C) True: duplicate-eliminating projection corresponds to a grouping-style physical implementation. D) False: a logical relation maps to physical scans/access paths, not always filters.

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