How to speed up a SQL Server query involving count(distinct())

Question

I have a deceptively simple SQL Server query that's taking a lot longer than I would expect.

SET TRANSACTION ISOLATION LEVEL READ UNCOMMITTED
SELECT COUNT(DISTINCT(guid)) FROM listens WHERE url='http://www.sample.com/'

'guid' is varchar(64) NULL

'url' is varchar(900) NULL

There is an index on guid and url.

There are over 7 million rows in the 'listens' table, of which 17,000 match the url in question, and the result of the query is 5,500.

It is taking over 1 minute to run this query on SQL Server 2008 on a fairly idle Dual-Core AMD Opteron 2GHz with 1GB RAM.

Any ideas how to get the execution time down? Ideally it should be under 1 second!

Answer 1

Your GUID column will, by nature, be a lot more labour-intensive than, say, a bigint as it takes up more space (16 bytes). Can you replace the GUID column with an auto-incremented numerical column, or failing that, introduce a new column of type bigint/int that is incremented for each new value of the GUID column (you could then use your GUID to ensure global uniqueness, and the bigint/int for indexing purposes)?

From the link above:

At 16 bytes, the uniqueidentifier data type is relatively large compared to other data types such as 4-byte integers. This means indexes built using uniqueidentifier keys may be relatively slower than implementing the indexes using an int key.

Is there any particular reason why you're using a varchar for your guid column rather than uniqueidentifier?

Answer 2

Have you tried eliminating the DISTINCT keyword and getting a grouping instead?

SELECT 
guid, COUNT(*)
FROM listens
WHERE url='http://www.sample.com'
GROUP BY guid

Answer 3

Create an index on url which would cover the GUID:

CREATE INDEX ix_listens_url__guid ON listens (url) INCLUDE (guid)

When dealing with urls as identifiers, it is much better to store and index the URL hash rather than the whole URL.

Answer 4

scaning indexes that large will take long no matter what.
what you need to do is to shorten the indexes.
what you can do is have an integer column where the checksum of the url is calculated and stored. this way your index will be narrow and count will be fast.

note that checksum is not unique but it's unique enough. here's a complete code example of how to do it. I've included checksums for both columns but it probably needs only one. you could also calculate the checksum on the insert or update by yourself and remove the trigger.

CREATE TABLE MyTable
(
    ID INT IDENTITY(1,1) PRIMARY KEY,
    [Guid] varchar(64),
    Url varchar(900),
    GuidChecksum int,
    UrlChecksum int
)
GO

CREATE TRIGGER trgMyTableCheckSumCalculation ON MyTable
FOR UPDATE, INSERT
as
UPDATE t1
SET    GuidChecksum = checksum(I.[Guid]),
       UrlChecksum = checksum(I.Url)
FROM   MyTable t1 
       join inserted I on t1.ID = I.ID

GO
CREATE NONCLUSTERED INDEX NCI_MyTable_GuidChecksum ON MyTable(GuidChecksum)
CREATE NONCLUSTERED INDEX NCI_MyTable_UrlChecksum ON MyTable(UrlChecksum)

INSERT INTO MyTable([Guid], Url)
select NEWID(), 'my url 1' union all
select NEWID(), 'my url 2' union all
select null, 'my url 3' union all
select null, 'my url 4'

SELECT  *
FROM    MyTable

SELECT  COUNT(GuidChecksum)
FROM    MyTable
WHERE   Url = 'my url 3'
GO

DROP TABLE MyTable

Answer 5

Some hints ...

1) Refactor your query, e.g. use with clause ...

    with url_entries as (  
      select guid   
      from listens   
      where url='http://www.sample.com/'  
    )   
    select count(distinct(enries.guid)) as distinct_guid_count   
    from url_entries entries

2) Tell exact SQL Serever which index must be scanned while performing query (of course, index by url field). Another way - simple drop index by guid and leave index by url alone. Look here for more information about hints. Especially for constructions like select ... from listens with (index(index_name_for_url_field) )

3) Verify state of indexes on listens table and update index statistics.

Answer 6

I bet if you have more than 1GB of memory in the machine it would perform better (all DBA's I've met expect at least 4GB in a production SQL server.)

I've no idea if this matters but if you do a

  SELECT DISTINCT(guid) FROM listens WHERE url='http://www.sample.com/'

won't @rowcount contain the result you want?

Answer 7

Your best possible plan is a range seek to obtain the 17k candidate URLs and the count distinct to rely on a guaranteed order of input so it does not have to sort. The proper data structure that can satisfy both of these requirements is an index on (url, guid):

CREATE INDEX idxListensURLGuid on listens(url, guid);

You already got plenty of feedback on the wideness of the key used and you can definetely seek to improve them, and also increase that puny 1Gb of RAM if you can.

If is possible to deploy on SQL 2008 EE, then make sure you turn on page compression for such a highly repetitive and wide index. It will do miracles on performance due to reduced IO.