Just How Expensive is a Sort Operator in a Query Plan

I was looking at a query plan with a co-worker and we noticed a Sort operator.  I was contemplating various methods we could use to get rid of it when my co-worker asked, "Why do you want to get rid of the Sort Operator, it's only 4% of the query, it's not like it's 88%?".  

Good question.  Sorting can be quite expensive over larger input sets (which this query was).  Sorting has N * LOG(N) algorithm complexity, theoretically, which is definitely not linear.  So, the more rows your input has, the more expensive the sort becomes on a per-row basis.  This quick breakdown I did in Excel shows how the cost of the sort in terms of amount of work needed to be done grows as the number of rows in the input to the sort grows:  

It gets even worse if your SORT spills to tempdb.  Your odds of this happening increase as the number of rows in your input grows.  

So, yes, the Sort operator is expensive and should be eliminated if it can be.  

More Information

• [[Scans and Sorts]]
• [[Sorts and Filters Performance]]