[prev] 25 [next]

Cost of Sort-based Projection

The costs involved are (assuming 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/n)
  • removing duplicates from Temp:   bT
  • writing the result relation:   bOut     (maybe less tuples)
Cost = sum of above = bR + bT + 2.bT.ceil(lognb0) + bT + bOut