Chris Webb explains the paradox:
As a follow-on from last week’s post about the new ApproximateDistinctCount function in DAX, I want to share something I found out from my recent testing for this function: ApproximateDistinctCount is sometimes slower than DistinctCount. This sounds counter-intuitive, right? After all ApproximateDistinctCount is a performance optimisation for the sometimes slow, expensive DistinctCount function. But it turns out that there are certain engine optimisations for DistinctCount that can’t be replicated for ApproximateDistinctCount which mean that for low-cardinality columns using DistinctCount can be faster.
Click through for an example.