A Myth About Count(distinct …)

[hic]

Do you belong to the group of people who think that Count(distinct…) in a chart is a slow, single-threaded operation that should be avoided?

If so, I can tell you that you are wrong.

Well - it used to be single-threaded and slow, but that was long ago. It was fixed already for – I think – version 9, but the rumor of its slowness lives on like an urban myth that refuses to die. Today the calculation is multi-threaded and optimized.

To prove that Count(distinct…) is faster than what many people think, I constructed a test which categorically shows that it is not slower – it is in fact a lot faster than the alternative solutions.

I created a data model with a very large fact table: 1M, 3M, 10M, 30M and 100M records. In it, I created a secondary key, with a large number of distinct values: 1%, 0.1% and 0.01% of the number of records in the fact table.

The goal was to count the number of distinct values of the secondary key when making a selection. There are several ways that this can be done:

• Use count distinct in the fact table: Count(distinct [Secondary ID])
• Use count on a second table that just contains the unique IDs: Count([Secondary ID Copy])
• Use sum on a field that just contains ‘1’ in the second table: Sum([Secondary ID Count])

I also created a dimension ("Dim" in the “Dim Table”) with 26 values, also randomly assigned to the data in the fact table. Then I recorded the response times for three charts, each using “Dim” as dimension and one of the three expressions above. I made this for four different selections.

Then I remade all measurements using “Dim ID” as dimension, i.e. I moved also the dimension to the fact table. Finally, I loaded all the recorded data into QlikView and analyzed it.

The first obvious result is that the response time increases with the number of records in the fact table. This is hardly surprising…

…so I need to compensate for this: I divide the response times with the number of fact table records and get a normalized response time in picoseconds:

This graph is extremely interesting. It clearly shows that if I use a Count(distinct…) on the fact table, I have a response time that is considerably smaller than if I make a count or a sum in a dimensional table. The table below shows the numbers.

Finally, I calculated the ratios between the response times for having the dimension in the fact table vs. in a dimensional table, and the same ratio for making the aggregation in the fact table vs. in a dimensional table.

This graph shows the relative response time I get by moving the dimension or the aggregation into the fact table. For instance, at 100M records, the response time from a fact table aggregation (i.e. a Count(distinct…)) is only 20% of an aggregation that is made in a dimensional table.

This is the behavior on my mock-up data on my four-core laptop with 16GB. If you make a similar test, you may get a slightly different result since the calculations depend very much on both hardware and the data model. But I still think it is safe to say that you should not spend time avoiding the use of Count(distinct…) on a field in the fact table.

In fact, you should consider moving your ID to the fact table if you need to improve the performance. Especially if you have a large fact table.

HIC

[hic]

@ Roland Vecera

Many things in the script are single threaded, probably also the creation of synthetic keys. In the front end, most things are multi threaded, but not all.

For example, when a chart is calculated there is first one step where it creates a link table if the dimension and the fields for the aggregation reside in different tables. This is single threaded. Further, if the aggregation contains fields from different data tables, it creates a lookup table to create all combinations between the fields before it can aggregate. This is also single threaded. Normally, these two steps are done quickly, so you don't notice that it is single threaded. But if the second largest table also is a large table, these steps will take some time.

See picture below from my tests. Note the CPU-usage: Single threading!

HIC

[hic]

@ srikanthsri1

The charts contain the units - either milliseconds or picoseconds.

HIC

[hic]

@ Jeffrey Vermeire ; @ Jay Jakosky

You are both correct that what takes time is the hop to the next table.

However, I still claim that it is a fair test: In real life, the developer has the choice of using Count(distinct ...) in the fact table, or a Count(ID) or Sum(Count) in a side table. Other options do not exist. It is not possible to put [Secondary ID Count] in the fact table and expect QlikView to make a correct calculation. Hence, a relevant comparison.

HIC

[#5]

Other needs exist. You need a real-world example. Here's one:

[Dim Table] contains customers, with a Customer ID and Name. [Fact Table] is traditional sales. [ID Table] is products, containing Product ID, Product Number, Product Version, and Description.

But for this company the Product ID is a compound key of the highly unique product number and a low-cardinality Version. Most products have only one version. And a hypothetical QV chart does not care about the Version, just the Product Number.

You want the count of unique Product Numbers by customer. So now you have to do a count(distinct) that crosses into the third table.

[philip_doyne]

A brave man - challenging HIC!       Great to see the discussion though ...   Philip

[#7]

HIC, I understand your statement that there are no other options. The three expressions you gave are isomorphisms. The isomorphisms for my scenario would require a 4th table in the data model.

My problem is that your analysis charts are so dramatically in favor of count(distinct) that most readers would conclude that they should use it. But what I see is a cautionary tale about traversing table links.

[hic]

@ Jay Jakosky

I totally agree that there are cases where you for different reasons don't want to or maybe even cannot move the ID into the fact table. And that's fine. Then you need to make an aggregation on the side table.

But I still say that you should consider the possibility of using Count(distinct...) on the fact table, if you have a large fact table and performance issues. Often the penalty of a larger fact table (from adding a column there) is smaller than the gain of a faster aggregation.

My main goal when writing this post was to kill the myth that you should avoid Count(distinct...) because of performance problems. Because that is a misconception.

HIC

PS You write "But what I see is a cautionary tale about traversing table links."  I can only say: Then you read it correctly!

[#9]

Thanks Henric!

[philip_doyne]

Which would be more efficient?

1) Stringing Together your unique Product Number (excl Version - you must be able to derive this from the full Product ID) & Customer ID as a field in fact table created during script load and Count(distinct) on that or

2) Doing a count distinct on Product No in product table

3) Creating a 4th table with just product Number and count or Sum on that (without distinct)

My guess would be (1) - less hops and slight overhead of extra field in Fact table.

Philip

[#11]

More time efficient? Number 1. But with a slight loss in clarity. "Why is this duplicated?"

For small apps, I'd choose #2. Clarity over speed. Network latency and JavaScript performance eclipse QV engine calc times until the app reaches millions of rows. Then there's a middle ground where #1 is more efficient and it is noticeable in user response times. But then, as you get into hundreds of millions of rows, #1 becomes space inefficient, so you should move back to #2.

Thanks to Henric, we can say #3 is a poor choice in every respect: speed, space, clarity and maintainability.

J