Count Distinct In Large Table With 30M Records?

I have a task to count distinct records in a big table with roughly 30M records, performance is an important factor. Query is to be written to calculate weekly stats, weekly record number could be as high as 1M.

The actual result is like:
ID Policy
350235744Credit Cards
350235744PCI
350235744PCI Audit

So the final number for this particular Policy is 3

I can write the query like:

select count(distinct Incident_id) policy_name
from Reporting_DailyDlpDetail
Where (year(INSERT_DETECT_TS)=2015) and (month(INSERT_DETECT_TS) =6) and (day(INSERT_DETECT_TS) between 2 and 9)
This returns 526254 and costs 11 seconds to complete

or a query like:
Select distinct Incident_id, policy_name
from Reporting_DailyDlpDetail
Where (year(INSERT_DETECT_TS)=2015) and (month(INSERT_DETECT_TS) =6) and (day(INSERT_DETECT_TS) between 2 and 9)
This returns 749687 and costs roughly 1 minute to complete.

Result is different from the two queries, I believe the later gives correct number. How can I count the distinct based on a combo?Considering the size of data, what is the best and most efficient way to run the stats calculation against over 30 different scenarios (different policies and alert types) and not timeout?