Made in USA: Enterprise Application Services

Call Today!817-210-4042

Cost Estimation of JOIN Operations

Estimating the cost of join operations is a little more complicated than doing so for SELECT operations because we have to consider the type of indexing available for each table that participates in the join. We must also factor in the cost of writing the result file, but since the size of the result file remains constant despite altering the execution strategy, we can ignore it for the basis of comparison.

Assume that in addition to the EMPLOYEE table, we also have a DEPT table with a DeptNum field indicating the department’s number.

Other assumptions:

Field Value
Number of EMPLOYEE records (re) 100,000
Number of EMPLOYEE disk blocks (be) 10,000
Blocking factor (bfr) (records per block) 5
Number of DEPARTMENT records (rd) 25
Number of DEPARTMENT disk blocks (bd) 5

The query we wish to evaluate is:
SELECT * FROM EMPLOYEE AS E, DEPARTMENT AS D WHERE E.DeptNum = D.DeptNum;

We will compare the following execution strategies for this query:

  1. Nested-loop join (brute force)
  2. Single loop join (using an index)
  3. Sort-merge join