Johnny Lin/ notes
← All writing2026.06.25 · CS 411 · Database Systems

From Relational Algebra to Physical Operators: Where Query Cost Comes From

Separate logical meaning from scan, sort, hash, and join algorithms, then estimate their page-I/O cost.

SQL states a result. Relational algebra gives that result a logical operator tree. Physical operators decide how to produce it with pages, memory, indexes, sorting, and hashing.

One logical expression, many executions

π name (
  σ topic = 'databases' (
    Researcher ⋈ PaperAuthor ⋈ Paper
  )
)

Projection π, selection σ, and join ⋈ describe meaning. They do not require a particular join algorithm or order.

In plain terms: relational algebra says what intermediate results mean; a physical plan says which loops, hash tables, and page reads create them.

Scans establish the input

A sequential scan reads every page of a relation: approximately B(R) I/Os when it is not cached. An index scan first traverses the index, then may visit table pages. It wins only when avoided work exceeds random access and lookup overhead.

Projection can be pipelined if it only drops columns. Duplicate-removing projection requires hashing or sorting and therefore additional memory and I/O.

Join algorithms have different conditions

For relations R and S:

  • Tuple nested loop: simple, but disastrous when it rescans S for every row of R.
  • Block nested loop: uses memory pages to process chunks of the outer relation.
  • Index nested loop: effective when the inner side has a selective index and the outer side is small.
  • Hash join: strong for equality joins; build a hash table on the smaller input.
  • Sort-merge join: useful when inputs are already sorted or ordered output is valuable.

A simplified block nested-loop cost with M memory pages is:

B(R) + ceil(B(R) / (M - 2)) × B(S)

Making the smaller relation the outer input reduces the number of rescans.

One-pass and two-pass thinking

An operator is one-pass when its working state fits in available memory—for example, hashing a small relation before probing it. When it does not fit, a two-pass algorithm partitions or sorts data to disk, then processes partitions.

The memory threshold creates a cliff: a small cardinality-estimation error can turn an in-memory hash into a spill.

Pipeline or materialize

Pipelining sends rows directly to the next operator and reduces temporary storage. Materialization writes an intermediate result, which costs I/O but may be required for sorting, reuse, blocking aggregation, or plan boundaries.

Read a plan bottom-up

The bottom nodes produce rows. Their parents consume them. For every node ask:

  1. How many rows enter and leave?
  2. Is the operator blocking or streaming?
  3. Does it build memory state or spill?
  4. How many times does loops repeat it?

Review card

  • Logical operators define meaning; physical operators define work.
  • Count pages, not only rows.
  • Index access is useful only when it avoids enough table work.
  • Join algorithm choice depends on size, memory, predicates, and indexes.
  • Spilling changes an in-memory operator into extra I/O passes.
  • Read execution plans from leaves upward.