Declarative Query Processing in Relational Database Systems - Automated Physical Database Design and Tuning - page 12

Filter
[TMP>10]

Stream Aggregate
[TMP count(*)]

Sort
[D.City]

Hash Join
[E.DId=D.DId]

Table Scan
[Dept (D)]

Hash Join
[M.EId=E.MId]

Table Scan
[Emp (M)]

Table Scan
[Emp (E)]

FIGURE 1.3 Execution plan for an SQL query.

To illustrate these concepts, consider again the query on page 10 that ob-
tains a list of all cities where more than 10 engineers working in low-budget
departments earn more than their managers. Figure 1.3 shows an execution
plan for this query. Each node in the figure corresponds to a physical oper-
ator. At the bottom of the tree there are Scan operators, which read tuples
from a given table and pass them up to the next operator in the plan. Ad-
ditionally, Scan operators can filter tuples on the fly based on single-table
predicates. The Scan operator on table Emp (alias E ) filters all employees that
are not engineers, while the Scan operator on table Emp (alias M ) routes all
employees to the next operator. These two Scan operators are inputs to a Hash
Join operator, which matches every (engineer) employee with his or her corre-
sponding manager (join operators simultaneously perform a Cartesian product
and an intertable predicate and exist because this combined operation is very
common). A Hash Join operator builds a hash table for each tuple in the right
input (hashed by Emp.EId ) and probes each tuple from the left input (hashing
it by Emp.MId ) against it (the procedure is similar to function countMatches2
in Figure 1.1 but additionally returns the matched tuples). As with Scan op-
erators, Hash Join operators can apply residual predicates on the matched