Optimize query with year 2009 condition

Query: Π name, title (σ dept-name = music ∧ year = 2009 (instructor ⋈ (teaches ⋈ Π c_id, title (course))))

Assumed schema: instructor(ID, name, dept_name, salary), teaches(ID, c_id, sec_id, semester, year), course(c_id, title, dept_name, credits). The attribute dept_name is in instructor and year is in teaches.

Original tree

Π name,title
  |
σ dept=music ∧ year=2009
  |
  ⋈
 /  \
instructor   ⋈
            /  \
       teaches  Π c_id,title
                    |
                  course

Rules applied

1. Cascade of selection: σθ1∧θ2(E) = σθ1(σθ2(E)). The conjunction is split into dept_name = music and year = 2009.
2. Push selection through join: σθ(E1 ⋈ E2) = σθ(E1) ⋈ E2 when θ uses only attributes of E1. Here dept_name = music goes to instructor and year = 2009 goes to teaches.
3. Early projection and a good join order (join the two reduced relations first).

Step by step

1. Split the selection:

   σ dept=music ( σ year=2009 ( instructor ⋈ (teaches ⋈ Π c_id,title(course)) ) )

2. Push each part down to its own relation:

   Π name,title ( σ dept=music(instructor) ⋈ ( σ year=2009(teaches) ⋈ Π c_id,title(course) ) )

3. Reorder so that the two filtered relations are joined first, and drop unneeded columns:

   Π name,title ( ( Π ID,name(σ dept=music(instructor)) ⋈ Π ID,c_id(σ year=2009(teaches)) ) ⋈ Π c_id,title(course) )

Optimized tree

            Π name,title
                 |
              ⋈ (c_id)
           /            \
       ⋈ (ID)         Π c_id,title
      /      \             |
Π ID,name   Π ID,c_id    course
    |           |
σ dept=music  σ year=2009
    |           |
instructor   teaches

Both large tables, instructor and teaches, are filtered before any join, so the joins work on small inputs. The result is the same as that of the original query, but the cost (tuples and disk blocks processed) is much lower.