Manfred Koizar <mkoi-pg@aon.at> writes:
> COUNT is cheap. But COUNT(DISTINCT something) is not trivial, it has
> to keep a list of all values it has already counted. I didn't look at
> the implementation. Do we have O(n^2) cost here?
No, more like O(n ln n) --- it's a sort/uniq implementation.
regards, tom lane