Query Execution and Optimization

Question 1

Processing Model & Types

Answer 1

Defines how the system executes a query plan
-> Extreme 1: Tuple-at-a-time via the iterator model
-> Extreme 2: Blocks-oriented model (typically column-at-a-time)

Question 2

Iterator Model (Volcano Model)

Answer 2

• Each query operator implements a next function
  -> On each invocation, the operator returns either a single tuple or a marker that there are no more tuples
  -> next calls next on the operator’s children to retrieve and process their tuples
  -> many function calls
  -> top-down

Question 3

Block-oriented (aka materialization) model

Answer 3

• Each operator processes its input all at once and emits its output all at once
  -> The operator “materializes” its output as a single result
  -> bottom-up

Question 4

Advantages/Disadvantages Heuristic Optimizer (INGRES)

Answer 4

• Advantages:
  -> Easy to implement and debug
  -> Works reasonable well and is fast for simple queries & small tables
• Disadvantages:
  -> Doesn’t truly handle joins
  -> Join ordering based only on cardinalities
  -> Naive, nearly impossible to generate good plans when operators have complex interdependencies