There is a New COUNT in Town

Comments 0

Share to social media

We have all been using the COUNT(DISTINCT) function to return row counts for a distinct list of column values in a table for ages. With the introduction of SQL Server 2019, there is a new way to get an estimate of distinct row values and counts for a table. It is by using the new APPROX_COUNT_DISTINCT() function. This new function doesn’t return the actual number of rows for each distinct value in a table, but instead returns an approximate count for each distinct value. This new function uses fewer resources than the tried and true COUNT(DISTINCT) function. Let’s take a little closer look at this new function.

What Problem is APPROX_COUNT_DISTINCT() Trying to Solve?

The new APPROX_COUNT DISTINCT() function is trying to solve the “Count Distinct Problem.” More information about this problem can be found here. Basically, the problem is that counting distinct values requires more and more memory as the number of distinct values increases. At some point, SQL Server can no longer manage to maintain the count of distinct values in memory and must spill to tempdb. Spilling to tempdb causes overhead and leads to increased execution time.

The implementation of APPROX_COUNT_DISTINCT() has a much smaller memory requirement than the COUNT(DISTINCT) function. The algorithm used for this new function is HyperLogLog. This algorithm can estimate the number of distinct values of greater than 1,000,000,000, where the accuracy of the calculated approximate distinct count value is within 2% of the actual distinct count value. It can do this while using less than 1.5 KB of memory.

More Information About the APPROX_COUNT_DISTINCT Function

The APPROX_COUNT_DISTINCT function has been available in other vendor software packages for a while now, but it is new in SQL Server. It first became available in Azure SQL Database, and now has been released for on premises use with SQL Server 2019 Community Technical Preview (CTP) 2.0. This new function is design to quickly return the approximate number of unique non-null values in a group, when your data set has millions, or billions of rows, and many distinct values.

This APPROX_COUNT_DISTINCT() function is designed to give you the approximate aggregated counts more quickly than using the COUNT (DISTINCT) method. It does this by using the HyperLogLog algorithm, which reduces the memory footprint required to maintain a list of distinct values. Because less memory is needed, APPROX_COUNT(DISTINCT) is, therefore, less likely to spill to tempdb when aggregating millions or billions of rows of data. This equates to shorter execution times compared to using the COUNT(DISTINCT) method.

The documentation states that this new function “guarantees up to a 2% error rate within a 97% accuracy.” Therefore, if speed is more important than absolute accuracy of the distinct count, then you might want to consider using this new function.

Invoking this function is similar to using the COUNT(DISTINCT) function. Here is the syntax:

The expression can be any type, except for image, sql_variant, ntext, or text value.

Testing APPROX_COUNT_DISTINCT() for Performance

In order to test out the performance of this new function, I’ll use a specific use case to determine out how fast APPROX_COUNT_DISTINCT() runs as compared to COUNT(DISTINCT. In addition to verifying the speed, I’ll also look to see if I can detect if this new function uses a smaller memory footprint than the old COUNT(DISTINCT) standby.

To gather and compare these metrics, I’m going to use this specific hypothetical use case and situation:

Use Case:

Develop a dashboard indicator that shows whether the number of unique IP addresses that have accessed our site for the current month is more, less or the same as the prior month.

Situation:

I work at an internet search engine, and I am responsible for building queries to run against some of the data we have collected. One of the things we track are the IP addresses for every visit to our site. We collect billions of rows of data every month. My boss has asked me to develop a query that can be used as a dashboard trend indicator that will show whether the number of unique IP Addresses coming to our site has gone up (+) or down (-) in the current month, as compared to the prior month. My boss requires this new query to run as fast as possible across our IP Address tracking table that contains billions, and billions of rows. My boss is willing to accept some level of lesser precision in the accuracy of the number, provide the indicator and percentage of change can be produced more quickly than a method that has absolute accuracy.

To create a testing environment, I created a database and populated a table named Visits2 that has a billion rows of randomly generated data. You can find the code I used to create my sample database in Listing 3, at the end of this article.

First, I want to test how fast the APPROX_COUNT_DISTINCT() function runs as compared to the COUNT(DISTINCT) function. For this test, I ran two SELECT queries that supported my use case. The first SELECT statement uses the COUNT(DISTINCT)function, and the second SELECT statement uses the APPROX_COUNT_DISTINCT() function. This code, found in Listing 1, generates a count of the number of unique IP Address that have accessed our site for July and August. You can also turn on “live query statistics” if you wish to monitor the progress of each SELECT statement while they are running.

Listing 1: Code to compare COUNT(DISTINCT) and APPROX_COUNT_DISTINCT() functions

This code turns on time statistics and runs each SELECT statement. I will use the time statistics produced by running this code to determine how much CPU and elapsed time it takes to get distinct IP address counts for July and August. In Results 1, you can see the CPU and elapsed times I got when I ran the code in Listing 1.

Results 1: The timing results when running the code in Listing 1

In Results 1, I show the timing results of the output produced by setting the STATISTICS TIME ON, for the two SELECT statements. The first set of times are from the COUNT(DISTINCT) query, whereas the second set of times are from the APPROX_COUNT_DISTINCT query. As you can see, APPROX_COUNT_DISTINCT used less CPU and elapsed time compared to the COUNT(DISTINCT)query. The APPROX_COUNT_DISTINCT() function ran a little over 6% faster than the COUNT(DISTINCT) function and uses almost 24% less CPU.

To determine the number of memory grants used by each SELECT statement, I used the output of the execution plan. In Results 2 you can see the execution plan from these two SELECT queries.

Results 2: Execution Plan code in Listing 1

The first thing you might notice when comparing these two executions is that the Cost of the Hash Match operation for the COUNT(DISTINCT) function takes more than twice as long to run as the Hash Match operation for the APPROX_COUNT_DISTINCT() function.

When I hover over the Hash Match operator for the COUNT(DISTINCT) function, I can see it spilled to disk (see Results 3), but when I hover over the Hash Match operator for the APPROX_COUNT_DISTINCT function, it did not spill to disk (see Results 4).

Results 3: Details of Hash Match operation for COUNT(DISTINCT) function

Results 4: Details of Hash Match operation for APPROX_COUNT_DISTINCT function

To display the number of memory grants between the two different functions, I hover over the SELECT icon in the execution plan. When I hover over the COUNT(DISTINCT) SELECT icon I get the results in Results 5, and when I hover over the APPROX_COUNT_DISTINCT SELECT icon I get the results in Result 6.

Results 5: Memory Grants for COUNT(DISTINCT)

Results 6: Memory Grants for APPROX_COUNT_DISTINCT()

As you can see, the COUNT(DISTINCT) function required 1,847,736 memory grants, whereas the APPROX_COUNT_DISTINCT() function only required 24,776 memory grants. This means the COUNT(DISTINCT) took 74 times as many memory grants over the new APPROX_COUNT_DISTINCT() function. Based on this, you can see the APPROX_COUNT_DISTINCT() function had a significantly smaller number of additional memory grants required versus the COUNT(DISTINCT) function.

Testing APPROX_COUNT_DISTINCT() for Accuracy

In addition to performance testing, I also wanted to test the accuracy/precision of distinct values produced between the COUNT(DISTINCT) and the APPROX_COUNT_DISTINCT() functions. To determine the precision difference between the two functions, I compared the number of distinct values produced by the two different SELECT statements in Listing 1. The COUNT(DISTINCT) function returned a count of 16,581,375 distinct IP address for July, whereas the APPROX_COUNT_DISTINCT() function returns a count of 17,075,480 for July. By comparing these two numbers, I can see that the APPROX_COUNT_DISTINCT() function is off by a little over 2.97%. Since this number was not within 2% error rate as documented, I contact Microsoft about this.

An engineer at Microsoft told me that the SQL Server engine uses a “sophisticated analytic sampling method” to produce an estimated count, and because of this, it is possible to build a contrived table that throws off the sampling method and produces dramatically inaccurate results.

From this first test, I can see that the APPROX_COUNT_DISTINCT() function does, in fact, run faster and requires fewer resources over the COUNT(DISTINCT) function. The only problem I ran across with this first test, was that I had more than a 2% precision error when generating the approximate count, over the real distinct count value. In my case, I found the precision error was 2.97%, which according to documentation can occur.

Since my initial testing found the APPROX_COUNT_DISTINCT() function returned a distinct count that was more than 2% different than the actual distinct count, I decided to run some additional precision testing. The additional SELECT statements I will be testing can be found in Listing 2.

Listing 2: Additional Testing Queries

The code in Listing 2 will identity the number of unique counts for columns that have a different number of unique values. I will use this code in Listing 2 to determine the number of different values it takes for the APPROX_COUNT_DISTINCT function to produce a count which is different than the actual number of unique values produced by the COUNT(DISTINCT) function. The code from Listing 2 produces the output found in Results 7.

Results 7: Results from running code in Listing 2

As you can see by looking at Results 7, the APPROX_COUNT_DISTINCT() function produces the same number as compared to the COUNT(DISTINCT) function when the number of unique values is low. In my case less than 1,000 unique values. But for each column that had more than 100 values, the APPROX_COUNT_DISTINCT() function produced an approximate number was more or less than the actual number generated by the COUNT(DISTINCT) function. This test shows that when the actual number of distinct values in a table increases, the APPROX_COUNT_DISTINCT() functions don’t produce the same number of distinct values as the COUNT() function, however, it is close. Therefore, if your table contains a large number of distinct values, then expect this new function to produce a count value that is somewhat different than the actual number of distinct values.

Conclusions Based on My Initial Testing

From the few simple tests I ran here against my generated sample data, I have made the following observations:

  • The APPROX_COUNT_DISTINCT() function does return a distinct count number faster than the COUNT(DISTINCT) function.
  • The COUNT(DISTINCT) function requires more memory grants than the APPROX_COUNT_DISTINCT() function.
  • In one situation, I able to returns a unique count value that had more than a 2% error rate.
  • If the number of distinct values for a given column is low, then the APPROX_COUNT_DISTINCT() function returns the same count value as the COUNT(DISTINCT) function.

Should you start using the APPROX_COUNT_DISTINCT()function? That’s a good question. I suppose it depends on your situation. I was pleasantly surprised at how much I was able to improve the runtime and reduce the memory footprint using the APPROX_COUNT_DISTINCT() function over the COUNT(DISTINCT) function. But I was little concerned how easy it was for me to retrieve an aggregated count value that had a precision error of more than 2%. My Visits2 table was very contrived but did expose the improvement and drawbacks of using the APPROX_COUNT_DISTINCT() function. Therefore, before using this new function in a production environment, I would suggest developing a more exhaustive set of tests against real data to verify that any precision errors are within an acceptable range for each situation. As with any new feature, I suggest you identify what the new feature does and then test the heck out of it to verify it provides the improvements you desire in your environment.

Code Used to Create Sample Test Data

In Listing 3, you will find the code I used to create my contrived sample database (SampleData) and the table (Visits2) I used to support my testing. Keep in mind that the code in this listing is not very efficient at creating my sample data. It took over an hour on my laptop to create the billion-row table I used for testing.

Listing 3: Script to create database and Visit2 table

Load comments

About the author

Greg Larsen

See Profile

Greg started working in the computer industry in 1982. In 1985, he got his first DBA job, and since then he has held six different DBA jobs and managed a number of different database management systems. Greg has moved on from being a full-time DBA and is now an adjunct professor at St. Martins University and does part-time consulting work. He has published numerous articles in SQL Server Magazine, and many online web sites dedicated to SQL Server. He is a former SQL Server MVP and holds a number of Microsoft Certification. Greg can be reached at gregalarsen@msn.com.

Greg Larsen's contributions