Cost of Relational Operations

Selection: cost(${\sigma }_{\phi }(E)$) = (1 + ${ϵ}_{\phi }$)cost($E$)
Nested loop join: cost($R\times S$) = cost($R$) + ($|R|/b$)cost($S$)
Nested index join: cost($R\times {\sigma }_{\phi }(S)$) = cost($R$) + $d_s+|R|$

• Btree depth $d_s$
  Soft-merge join: cost($R{\bowtie }_{\phi }S$) = cost(sort($R$)) + cost(sort($S$))
• cost(sort($E$)) = cost($E$) + $(|E|/b)\log (|E|/b)$