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 n_d 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 n_d reads and n_d 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 n_d)

IOWRITE(Aggregation phase) = O(2 n_d)

When I build enterprise scale solution it is crucial for me to know what sort of scalability can be expected from a server product. Is it linear? It is exponential? Should I scale-out or scale-up? Are there hard limits to what the architecture can do?

To understand these limitations and provide valid statements about scalability - you have to know the time complexity of the operations performed by your implementation.

A major challenge for large scale Analysis Services installations is to reduce the processing time for a cube. If we are understand to what constitutes a cube processing we must first look at how processing is done. Processing proceeds in three phases

1. Read phase - Rows are read from the data source and into Analysis Services.
2. Aggregation phase - Based on the rows read - aggregations are build.
3. Index build phase - The aggregations are indexed to provide fast query access

I need to get a deeper understanding of the index phase before embarrassing myself completely (as opposed to partially) in my blog.

For now - lets look at the first two phases in more detail:

Read Phase

The purpose of the read phase is - as the name implies - to read the rows from the relational data source. The rows read form what I call the "base aggregations" - I.e. the leaf level (or key level if you like) data of the cube. It is these base aggregations that are used to answer queries at leaf level. The base aggregations also form the "base" of higher level aggregates in the next phase.

Each row from the relational source is read once. Assuming there are n rows in the source. We find that our number of IO reads must be proportional with:

IOREAD(Read Phase) = O(n)

Each row takes about the same amount of CPU time to read. Hence, our CPU usage is:

CPU(Read Phase) = O(n)

How about the writes, once could assume O(n) - but this would not be completely true:

As you may be aware - a relational fact table can contain "duplicate" data at the leaf level. Let me provide you with a few examples:

Example 1: I go into a supermarket today and buy a bottle of coke. Being a caffeine junkie - I later visit the same store - buying yet another bottle of coke. This will generate two rows in the Point Of Sales system - one of each bottle. Depending on your warehouse design - you may see both of these rows in your relational source - hence observing a "duplicate" row. The interesting data from the cube perspective (assuming no drillthrough) is one row with 2 bottles of coke - not two rows with 1 each

Example 2: You have a relational fact table with 5 dimension columns. However, for you analysis services cube you only want to use 4 of these dimensions. When you read the fact table you will almost certainly read duplicate leaf level data. Why? Compare the two statements:

(1) SELECT DISTINCT D1, D2, D3, D4 , D5 FROM <FactTable>

(2) SELECT DISTINCT D1, D2, D3, D4 FROM <FactTable>

The row count of (2) is most likely smaller than (1) - why else would you even bother with D5 in the first place?

Because the two examples happens a lot in the OLAP world, Analysis Services implements a "merge buffer" . While reading rows from the relational source- this buffer is used to merge such duplicate rows into single rows - thus reducing the storage space needed for the leaf level aggregates.

The merge buffer will not eliminate all duplicates. It has a limited size and will thus only on a subset of the fact table. In the ideal world - where the fact rows enter Analysis Services in sorted order and the merge buffer is large enough, we will eliminate all duplicates.

This brings us back to the number of IO operations needed to write base aggregation. Let n_d be the distinct count of the dimension columns we use in the cube. Assuming an optimal reading of the fact table we have:

IOWRITE(Read Phase) = O(n_d)

The reduction of the writes compared with the read can be quite significant for later phases of processing. Essentially we are seeing a kind of "pre aggregation" here. I like to think of n_d as the size of the "non empty cube space".

Also, notice that there is an upper limit to n_d that is unaffected by you fact table size. Assuming your cube dimension, D₁, ... , D_n have the following leaf level sizes: |D₁|, ... , |D_n|. The upper limit for n_d is:

n_d <= |D₁| *, ... ,* |D_n|

For cubes with a small number of dimensions this upper limit can work to your advantage - as we shall see later.

Aggregation Phase

Once analysis services has stored the data read it must build higher level aggregates.

If you have ever tried managing you own aggregate tables in a relational database you will know that there are two ways to build an aggregate:

1. Directly from the leaf level (in a relational database this would be the fact table)
2. Derive the aggregate from another aggregate.

 This is where things get a little complicated - but I will give it a shot. Let's start with the first case - leaf level aggregation building:

Every attribute in you cube is a potential candidate for an aggregation. You control which ones you want to aggregate by a combination of:

• Setting the attribute properties (see my previous post)
• Running the storage design wizard. This will create some "statistically correct choices"
• Using a custom aggregation tool to manually specify which aggregates you want

For the moment - lets keep attribute relationships out of the equation. Let's just assume you have a cube with aggregates designed, one way or the other, for a subset, A_Agg, of your attributes.

During the aggregation phase analysis services has to read your leaf level rows (remember, there were n_d of these). Reading these rows takes:

IOREAD(Read Leaf level data) = O(n_d)

From my conversations with Eric Jacobsen I gather that the aggregation algorithm in AS 2005 is an external disk sort (as compared to the other common alternative - a hash/bucket sort). What does this tell us? Well, for those you that don't already own it - get a copy of Donald E. Knuths masterpiece: "The Art of Computer Programming". From this work we can lookup the complexity of different sort algoritms and how to implement them. I fair assumption is that the external sort uses quicksort on its memory buffer the time complexiy: O(n lg(n)). Each attribute that is aggregated must be sorted - so we have:

CPU(Aggregation Phase) = O( A_Agg * n_d * lg(n_d))

Aggregation phase - summary so far

Time complexity: Not surprisingly - CPU usage in the aggregation phase is proportional to the number of attributes you are aggregating. Notice however, that it is not proportional to the amount of rows in your relational database. Its proportional to the DISTINCT count of dimension values (assuming your merging in the read phase is optimal).

Possible optimization (untested): This is pure speculation - but there may be some benefit of sorting your fact table using a clustered index to optimize the "pre aggregation" in the read phase.

Cubes with a small number of dimension: If you cube has a very small number of dimension with relatively few manbers you may be able to leverage the fact that n_d has an upper limit. This is pure theory - but it seems to be that some cubes could always be fully aggregated in reasonable time - irrespective of the number of source rows in the underlying relational table

It's time to post this first part. Next part: Attribute relationships and how they are used to build higher level aggregates. 

Most of you are probably using the aggregation wizard to create aggregations for your cubes. If you done your homework and set attribute relationships, counts and properties right (please refer to my previous post) - the aggregation wizard will generally do a good job creating the right aggregations.

The exact workings of the storage design wizard are probably best left to a separate blog entry. But there are a few things you should be aware of: To determine which aggregations to build, the storage design wizard will apply the "30% rule". Roughly speaking this means is that an aggregation is only considered for building if it represents the sum of at least 30% of level below it in a natural hierarchy.

As an example, take this hierarchy:

The top level is considered for aggregation: The 3 rows each aggregate an average of 20 / 3 - around: 6.6 rows - this is more than 30% of the 20 rows just below the top level.

The second level is not considered for aggregation: It is almost as fast to scan the 30 rows as it is to scan the almost equal sized 20 rows above them.

There are rare cases when the aggregations designed by the wizard using the 30% rule are not good enough. A real life customer example had a hierarchy with these characteristics:

The middle level, with 1 million members, is not considered for aggregation by the storage design wizard:  it does not meet the criteria of the 30% rule. However, in this particular case - a large fraction of the customers queries will access the middle level. Furthermore, the distribution between the middle and the bottom level is skewed: there might only be an average of 1.2 members the lowest level for every members at the middle level - but some members have thousands of children - whereas some only have one.

For this particular customer - adding a custom aggregation to the middle level with 1 million members boosted query performance significantly. An optimization not achievable with the storage design wizard.

A word of warning: Creating the right custom aggregations is a task for cube experts. Creating every possible aggregation in your cube is not a good way to boost query performance. In the worst case your cube processing will never finish. Lets just, theoretically, assume you could process your cube with all aggregations design. Locating the right aggregation to use in the universe sized space of aggregations will still take eternity for Analysis Services. The words "eternity" and "universe" are fitting in this context - cube space can be BIG - very very BIG - you really don't want to aggregate all of it.

Assuming you have heeded my words of warning - how do you go about manually adding aggregations to your cube? Though the API is there Microsoft does not supply a tool for inspecting and creating custom aggregations. One way is of course to edit the cube XML files or use XML/A. A daunting task.

But guess what? The developers at Microsoft probably needed a tool for their own internal use - so they build one. This tool is called AggDesign - and I have had the pleasure of using it. According to Eric Jacobsen from Microsoft, we may see this tool shipped with SQL Server 2005 SP2. AggDesign allows you to visually inspect your cube aggregations and add new ones a you see fit. The tools allows you to assign one or more "AggDesigns" to each partition in your cube. These AggDesign add extra aggregations to the ones already defined by the storage wizard. If you are working with a large cube and feel very confident that you need custom aggregations (and you really should be sure) you might be able to get a copy of this tool from your local Microsoft product support.