[prev] 79 [next]

Cost of Sort-based Projection

The costs involved are (assuming B=n+1 buffers for sort):
  • scanning original relation Rel:   bR   (with cR)
  • writing Temp relation:   bT     (smaller tuples, cT > cR, sorted)
  • sorting Temp relation:
      2.bT.ceil(lognb0) where b0 = ceil(bT/B)
  • scanning Temp, removing duplicates:   bT
  • writing the result relation:   bOut     (maybe less tuples)
Cost = sum of above = bR + bT + 2.bT.ceil(lognb0) + bT + bOut