Home > Analysis Services, SQL Server > IO Complexity of processing aggregation phase

IO Complexity of processing aggregation phase

December 18, 2006 Leave a comment Go to comments

In my last post I missed the IO complexities of the aggregation phase. My memory of external sorting has become a bit rusty and I once again needed to bring Knuth from my bookshelf.

First of all – if you have not yet tried running perfmon while processing this would be a good time. It is worth noticing that the aggregations phase does not consume much IO. Even on a less than well tuned IO subsystem the aggregation phase is typically CPU bound. For those of you only interested optimizing the speed of the aggregation phase – take another look at your attribute relationships and properties (you can use some of previous posts as inspiration).

From my mail exchange with Eric Jacobsen I interpret that the external sort used by analysis services is a variant of balanced merge. The basic idea of the algorithm is

  1. Read rows from input (in this case the nd rows from the read phase) until memory full
  2. Sort records in memory (for example using quicksort)
  3. Write sorted records to a temp file on disk.
  4. Are there still rows left in the input? If so – goto 1
  5. Read all temp files and merge these to a new – sorted file

Steps 1-3 require nd reads and nd writes. Steps 4-5 require the same amount of reads and writes – furthermore, there is a small lg(q) CPU overhead for merging, with q being the number of temp files.

From the algorithm above we can also deduce that we can save a significant amount of IO if we have plenty of memory for the sort in phase 2. Not surpring – but it is worth noticing that the records size in analysis services tend to be very big. 64-bit memory spaces clearly have a big advantage in the aggregation phase.

Summarizing, we have:

IOREAD(Aggregation phase) = O(2 nd)

IOWRITE(Aggregation phase) = O(2 nd)

  1. May 15, 2011 at 15:30

    Hello, I found this site from stumbleupon. It’s not blog post I would regularly read, but I loved your perspective on it. Thanks for making an article worth reading!

  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s