Quizmaster

Learning objectives

What you will be able to explain

Which task is performed by the Parser, but NOT by the Preprocessor?
Regarding the stages of Query Processing, are the following statements True or False?
Assign the following tasks to either "Parser" or "Preprocessor":
In "Pre-Optimization" heuristics, what is the primary goal of "Pushing Down Selections"?
Identify if the following Relational Algebra equivalences are correct (True) or incorrect (False) for Sets/Bags:
Which transformation rule allows combining a Selection and a Cartesian Product into a single operator?

Section 01

Which task is performed by the Parser, but NOT by the Preprocessor? to Assign the following tasks to either "Parser" or "Preprocessor":

Which task is performed by the Parser, but NOT by the Preprocessor?

The parser is responsible for syntax analysis and grammar-driven parse-tree construction. Semantic tasks such as schema checks, type checks, and view expansion are handled later in preprocessing.

Regarding the stages of Query Processing, are the following statements True or False?

A is False because parsing produces a parse tree, not a full logical plan. B is True since preprocessing performs semantic checks. C is True because optimization includes logical rewrites and physical plan selection. D is True because the execution engine runs the physical plan.

Assign the following tasks to either "Parser" or "Preprocessor":

Parser tasks are syntax/grammar validation (1 and 4). Preprocessor tasks are semantic and algebraic preparation, such as validating referenced relations and translating to an internal query expression tree (2 and 3).

Section 02

In "Pre-Optimization" heuristics, what is the primary goal of "Pushing Down Selections"? to Which transformation rule allows combining a Selection and a Cartesian Product into a single operator?

In "Pre-Optimization" heuristics, what is the primary goal of "Pushing Down Selections"?

Selection push-down applies filters as close to base relations as possible so fewer tuples flow into joins and later operators, reducing intermediate result size and total cost.

Identify if the following Relational Algebra equivalences are correct (True) or incorrect (False) for Sets/Bags:

A and D are valid algebraic commutativity/associativity rules. B is also valid because conjunctive selections can be cascaded. C is not always true for bags because duplicate multiplicities make OR-decomposition with union non-equivalent in general.

Which transformation rule allows combining a Selection and a Cartesian Product into a single operator?

Join introduction is the rule that recognizes selection-over-cartesian-product as an equi-join pattern and replaces it with an explicit join operator, which is more meaningful and usually cheaper to optimize.

Section 03

Given a relation $R$ with $T(R) = 20,000$ tuples and $V(R, A) = 400$ distinct values for attribute $A$ . Estimate the number of tuples for the selection $S = \sigma_{A=10}(R)$ assuming a uniform distribution. to A query has a conjunction of two independent predicates: $\sigma_{A=10 \text{ AND } B<20}(R)$ . Given: $T(R) = 12,000$ , $V(R, A) = 40$ , and the selectivity for $B<20$ is $1/3$ . Calculate the estimated result size.

Given a relation $R$ with $T(R) = 20,000$ tuples and $V(R, A) = 400$ distinct values for attribute $A$ . Estimate the number of tuples for the selection $S = \sigma_{A=10}(R)$ assuming a uniform distribution.

Path of Calculation: 1. Formula:

T(S) = T(R) / V(R, A)

2. Calculation:

20,000 / 400 = 50

Correct Answer: 50

Consider relation $R$ with $T(R) = 15,000$ and $V(R, A) = 50$ . Estimate the result size for $S = \sigma_{A \neq 10}(R)$ using the "Often better" formula from the slides.

Path of Calculation: 1. Formula:

T(S) = T(R) \cdot \frac{V(R, A) - 1}{V(R, A)}

2. Calculation:

15,000 \cdot \frac{50 - 1}{50} = 15,000 \cdot \frac{49}{50} = 15,000 \cdot 0.98 = 14,700

Correct Answer: 14,700

A query has a conjunction of two independent predicates: $\sigma_{A=10 \text{ AND } B<20}(R)$ . Given: $T(R) = 12,000$ , $V(R, A) = 40$ , and the selectivity for $B<20$ is $1/3$ . Calculate the estimated result size.

Path of Calculation: 1. Selectivity(A=10) =

1 / V(R, A) = 1/40

2. Selectivity(B<20) =

1/3

3. Combined Selectivity =

(1/40) \cdot (1/3) = 1/120

4. Result Size =

12,000 \cdot (1/120) = 100

Correct Answer: 100

Section 04

Calculate the result size for a disjunction $S = \sigma_{C1 \text{ OR } C2}(R)$ using Idea 3 (Probability theory). Given: $T(R) = 1,000$ , $T(\sigma_{C1}(R)) = 200$ , and $T(\sigma_{C2}(R)) = 300$ . to Estimate the cardinality of the 3-way join $R(A, B) \bowtie S(B, C) \bowtie U(C, D)$ .

Calculate the result size for a disjunction $S = \sigma_{C1 \text{ OR } C2}(R)$ using Idea 3 (Probability theory). Given: $T(R) = 1,000$ , $T(\sigma_{C1}(R)) = 200$ , and $T(\sigma_{C2}(R)) = 300$ .

Path of Calculation: 1. Formula:

n \cdot [1 - (1 - m_1/n)(1 - m_2/n)]

m_1/n = 200/1000 = 0.2

m_2/n = 300/1000 = 0.3

1 - (1 - 0.2)(1 - 0.3) = 1 - (0.8 \cdot 0.7) = 1 - 0.56 = 0.44

5. Result =

1,000 \cdot 0.44 = 440

Correct Answer: 440

Estimate the join cardinality for the Natural Join $R(X, Y) \bowtie S(Y, Z)$ .

Path of Calculation: 1. Formula:

T(R \bowtie S) = \frac{T(R) \cdot T(S)}{\max(V(R, Y), V(S, Y))}

2. Calculation:

\frac{5,000 \cdot 10,000}{\max(500, 250)} = \frac{50,000,000}{500} = 100,000

Correct Answer: 100,000

Guided checkpoint

R(X, Y)	S(Y, Z)
$T(R) = 5,000$	$T(S) = 10,000$
$V(R, Y) = 500$	$V(S, Y) = 250$

Estimate the cardinality of the 3-way join $R(A, B) \bowtie S(B, C) \bowtie U(C, D)$ .

Path of Calculation: 1. Step 1:

T(R \bowtie S) = (100 \cdot 200) / \max(10, 20) = 20,000 / 20 = 1,000

. 2. Step 2:

T((R \bowtie S) \bowtie U) = (1,000 \cdot 500) / \max(V(R \bowtie S, C), V(U, C))

. 3. Use preservation of value sets:

V(R \bowtie S, C) = V(S, C) = 50

. 4. Calculation:

(1,000 \cdot 500) / \max(50, 100) = 500,000 / 100 = 5,000

. Correct Answer: 5,000

Guided checkpoint

R(A, B)	S(B, C)	U(C, D)
$T(R) = 100$	$T(S) = 200$	$T(U) = 500$
$V(R, B) = 10$	$V(S, B) = 20$
	$V(S, C) = 50$	$V(U, C) = 100$

Section 05

A relation $R$ has 10,000 tuples. Each tuple is 108 bytes. The tuple header is 12 bytes. Blocks are 1,024 bytes with a 24-byte header. Calculate the number of blocks $B(R)$ required. to Which of the following are sources for estimation errors in Equi-Width histograms?

A relation $R$ has 10,000 tuples. Each tuple is 108 bytes. The tuple header is 12 bytes. Blocks are 1,024 bytes with a 24-byte header. Calculate the number of blocks $B(R)$ required.

Path of Calculation: 1. Tuple size =

108 + 12 = 120

bytes. 2. Available space per block =

1,024 - 24 = 1,000

bytes. 3. Tuples per block =

\lfloor 1,000 / 120 \rfloor = 8

tuples. 4. Number of blocks =

10,000 / 8 = 1,250

. Correct Answer: 1,250

Match the Histogram type to its characteristic:

Equi-width histograms define buckets by fixed value-range width (often represented via start and width). Equi-depth histograms define buckets so each bucket contains roughly equal tuple counts, adapting ranges to data skew.

Which of the following are sources for estimation errors in Equi-Width histograms?

Equi-width accuracy depends heavily on bucket count and on the uniform-within-bucket assumption. Too few buckets or skew inside a bucket can cause large selectivity errors.

Section 06

Why is "Sampling" often used for collecting statistics in a DBMS? to Which choices are involved in selecting a Physical Query Plan?

Why is "Sampling" often used for collecting statistics in a DBMS?

Full-table statistics computation can be expensive on large relations, so DBMSs commonly use sampling to trade a small accuracy loss for much lower collection overhead.

What is the "Inclusion Assumption" used in multiple join cardinality estimation?

The inclusion assumption says shared-domain values are assumed to appear across participating relations, which helps approximate multi-join cardinalities without exact cross-relation value correlations.

Which choices are involved in selecting a Physical Query Plan?

Physical planning chooses concrete operator implementations, join order/grouping choices among associative operators, and execution/data-flow style (e.g., pipelining vs materialization). Rewriting query semantics (like SELECT to UPDATE) is not part of physical planning.

Section 07

Which search strategy finds a "good" plan quickly and uses its cost as an upper bound to prune further search? to Regarding Join Ordering Heuristics:

Which search strategy finds a "good" plan quickly and uses its cost as an upper bound to prune further search?

Branch-and-bound quickly finds a feasible plan, then uses that cost as an upper bound to prune subspaces that cannot beat it, reducing search compared with exhaustive enumeration.

What is a significant disadvantage of the Hill-Climbing strategy?

Hill climbing improves a current plan by local moves, but local improvements do not guarantee global optimality. It can therefore stop at a local optimum.

Regarding Join Ordering Heuristics:

A is True because greedy methods prioritize immediately cheap join choices. B is False since index scans are often most useful with predicates. C is True because existing sort order can make sort-merge join attractive. D is False because multiple selections are typically pushed together early, not delayed.

Section 08

In Dynamic Programming for Join Ordering, what is the purpose of the "Principle of Optimality"? to What are "Interesting Orders" in Selinger-style optimization?

In Dynamic Programming for Join Ordering, what is the purpose of the "Principle of Optimality"?

Dynamic programming relies on optimal substructure: if a full join plan is optimal, its subplans must also be optimal for their subsets. This enables memoization over subsets.

In a Dynamic Programming lattice for 4 relations $\{R, S, T, U\}$ , how many subsets of size 2 (pairs) must be evaluated?

Path of Calculation: 1. Combinations of 4 taken 2 at a time:

\binom{4}{2}

. 2. Calculation:

\frac{4 \cdot 3}{2 \cdot 1} = 6

. Correct Answer: 6

What are "Interesting Orders" in Selinger-style optimization?

Interesting orders are output sort orders worth preserving because downstream operations (merge join, group by, order by) may reuse them and avoid extra sorting.

Section 09

To simplify the search space, which limitations are often applied to Dynamic Programming in optimizers? to According to the quote by T. Neumann, changes to the query optimizer can often improve performance by a factor of:

To simplify the search space, which limitations are often applied to Dynamic Programming in optimizers?

To keep DP tractable, optimizers often avoid unnecessary cross products and restrict tree shapes (commonly left-deep). These reduce combinatorial explosion while keeping good plans likely.

Assign the following to either "Logical Plan Optimization" or "Physical Plan Optimization":

Logical optimization rewrites algebra equivalently (e.g., push-downs, commutativity). Physical optimization chooses access paths and operator algorithms (scan types, join methods). Hence 1/3 are logical, 2/4 are physical.

According to the quote by T. Neumann, changes to the query optimizer can often improve performance by a factor of:

The quoted takeaway is that optimizer quality can have order-of-magnitude impact, commonly around 10x, because plan choices dominate execution cost.

Section 10

Match the execution tree shape to its description: to Which join pair is selected first by the Greedy join-ordering algorithm?

Match the execution tree shape to its description:

In left-deep trees, only one side (typically left in this convention) continues as a join subtree while the other is a base relation. Bushy trees allow both children to be join subtrees.

Regarding Statistics Collection:

A is False because statistics are usually refreshed periodically, not per update. B is True because even approximate stats guide better plans than none. C is True due to time/update-triggered refresh policies. D is False because stats gathering can be expensive.

Which join pair is selected first by the Greedy join-ordering algorithm?

Path of Calculation: 1. Size

(R \bowtie S) = 1000 \cdot 10 \cdot 0.01 = 100

. 2. Size

(S \bowtie T) = 10 \cdot 500 \cdot 0.1 = 500

. 3. Size

(R \bowtie T) = 1000 \cdot 500 \cdot 0.001 = 500

. 4. Greedy picks the smallest intermediate result. Correct Answer:

\{R, S\}

Guided checkpoint

Use Greedy Search on relations $R, S, T$ with the following statistics:

Relation	Cardinality
$\|R\|$	1000
$\|S\|$	10
$\|T\|$	500

Join Pair	Selectivity
$sel(R, S)$	0.01
$sel(S, T)$	0.1
$sel(R, T)$	0.001

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

Which task is performed by the Parser, but NOT by the Preprocessor? to Assign the following tasks to either "Parser" or "Preprocessor":

Which task is performed by the Parser, but NOT by the Preprocessor?

Regarding the stages of Query Processing, are the following statements True or False?

Assign the following tasks to either "Parser" or "Preprocessor":

In "Pre-Optimization" heuristics, what is the primary goal of "Pushing Down Selections"? to Which transformation rule allows combining a Selection and a Cartesian Product into a single operator?

In "Pre-Optimization" heuristics, what is the primary goal of "Pushing Down Selections"?

Identify if the following Relational Algebra equivalences are correct (True) or incorrect (False) for Sets/Bags:

Which transformation rule allows combining a Selection and a Cartesian Product into a single operator?

Given a relation RRR with T(R)=20,000T(R) = 20,000T(R)=20,000 tuples and V(R,A)=400V(R, A) = 400V(R,A)=400 distinct values for attribute AAA. Estimate the number of tuples for the selection S=σA=10(R)S = \sigma_{A=10}(R)S=σA=10​(R) assuming a uniform distribution.

Consider relation RRR with T(R)=15,000T(R) = 15,000T(R)=15,000 and V(R,A)=50V(R, A) = 50V(R,A)=50. Estimate the result size for S=σA≠10(R)S = \sigma_{A \neq 10}(R)S=σA=10​(R) using the "Often better" formula from the slides.

A query has a conjunction of two independent predicates: σA=10 AND B<20(R)\sigma_{A=10 \text{ AND } B<20}(R)σA=10 AND B<20​(R). Given: T(R)=12,000T(R) = 12,000T(R)=12,000, V(R,A)=40V(R, A) = 40V(R,A)=40, and the selectivity for B<20B<20B<20 is 1/31/31/3. Calculate the estimated result size.

Estimate the join cardinality for the Natural Join R(X,Y)⋈S(Y,Z)R(X, Y) \bowtie S(Y, Z)R(X,Y)⋈S(Y,Z).

Estimate the cardinality of the 3-way join R(A,B)⋈S(B,C)⋈U(C,D)R(A, B) \bowtie S(B, C) \bowtie U(C, D)R(A,B)⋈S(B,C)⋈U(C,D).

A relation RRR has 10,000 tuples. Each tuple is 108 bytes. The tuple header is 12 bytes. Blocks are 1,024 bytes with a 24-byte header. Calculate the number of blocks B(R)B(R)B(R) required. to Which of the following are sources for estimation errors in Equi-Width histograms?

A relation RRR has 10,000 tuples. Each tuple is 108 bytes. The tuple header is 12 bytes. Blocks are 1,024 bytes with a 24-byte header. Calculate the number of blocks B(R)B(R)B(R) required.

Match the Histogram type to its characteristic:

Which of the following are sources for estimation errors in Equi-Width histograms?

Why is "Sampling" often used for collecting statistics in a DBMS? to Which choices are involved in selecting a Physical Query Plan?

Why is "Sampling" often used for collecting statistics in a DBMS?

What is the "Inclusion Assumption" used in multiple join cardinality estimation?

Which choices are involved in selecting a Physical Query Plan?

Which search strategy finds a "good" plan quickly and uses its cost as an upper bound to prune further search? to Regarding Join Ordering Heuristics:

Which search strategy finds a "good" plan quickly and uses its cost as an upper bound to prune further search?

What is a significant disadvantage of the Hill-Climbing strategy?

Regarding Join Ordering Heuristics:

In Dynamic Programming for Join Ordering, what is the purpose of the "Principle of Optimality"? to What are "Interesting Orders" in Selinger-style optimization?

In Dynamic Programming for Join Ordering, what is the purpose of the "Principle of Optimality"?

In a Dynamic Programming lattice for 4 relations {R,S,T,U}\{R, S, T, U\}{R,S,T,U}, how many subsets of size 2 (pairs) must be evaluated?

What are "Interesting Orders" in Selinger-style optimization?

To simplify the search space, which limitations are often applied to Dynamic Programming in optimizers? to According to the quote by T. Neumann, changes to the query optimizer can often improve performance by a factor of:

To simplify the search space, which limitations are often applied to Dynamic Programming in optimizers?

Assign the following to either "Logical Plan Optimization" or "Physical Plan Optimization":

According to the quote by T. Neumann, changes to the query optimizer can often improve performance by a factor of:

Match the execution tree shape to its description: to Which join pair is selected first by the Greedy join-ordering algorithm?

Match the execution tree shape to its description:

Regarding Statistics Collection:

Which join pair is selected first by the Greedy join-ordering algorithm?

Turn understanding into recall.

Given a relation $R$ with $T(R) = 20,000$ tuples and $V(R, A) = 400$ distinct values for attribute $A$ . Estimate the number of tuples for the selection $S = \sigma_{A=10}(R)$ assuming a uniform distribution.

Consider relation $R$ with $T(R) = 15,000$ and $V(R, A) = 50$ . Estimate the result size for $S = \sigma_{A \neq 10}(R)$ using the "Often better" formula from the slides.

A query has a conjunction of two independent predicates: $\sigma_{A=10 \text{ AND } B<20}(R)$ . Given: $T(R) = 12,000$ , $V(R, A) = 40$ , and the selectivity for $B<20$ is $1/3$ . Calculate the estimated result size.

Estimate the join cardinality for the Natural Join $R(X, Y) \bowtie S(Y, Z)$ .

Estimate the cardinality of the 3-way join $R(A, B) \bowtie S(B, C) \bowtie U(C, D)$ .

A relation $R$ has 10,000 tuples. Each tuple is 108 bytes. The tuple header is 12 bytes. Blocks are 1,024 bytes with a 24-byte header. Calculate the number of blocks $B(R)$ required. to Which of the following are sources for estimation errors in Equi-Width histograms?

A relation $R$ has 10,000 tuples. Each tuple is 108 bytes. The tuple header is 12 bytes. Blocks are 1,024 bytes with a 24-byte header. Calculate the number of blocks $B(R)$ required.

In a Dynamic Programming lattice for 4 relations $\{R, S, T, U\}$ , how many subsets of size 2 (pairs) must be evaluated?