Investigate performance drop for DISTINCT queries

[comphead]

Is your feature request related to a problem or challenge? Please describe what you are trying to do.
ClickBench reported a performance drop for COUNT(DISTINCT) computation #5276 (comment)

Describe the solution you'd like
Its needed to investigate a performance drop root cause in DISTINCT queries and find out how is it possible to increase the speed.

Describe alternatives you've considered
Not doing this

Additional context
Metrics can be found #5276 (comment)
Reproduce the case #5276 (comment)

[comphead]

Adding Flamegraph profiler for query
SELECT COUNT(*) AS c, COUNT(DISTINCT "UserID") FROM hits GROUP BY "RegionID" LIMIT 10;

[Dandandan]

So here we have the answer - it's very inefficient because of inefficiently tracking memory (which was added some versions ago). FYI @alamb

[alamb]

So here we have the answer - it's very inefficient because of inefficiently tracking memory (which was added some versions ago). FYI @alamb

Nice sluthing -- thank you @comphead and @Dandandan - - I can file a ticket for the regression related to tracking memory if that would help

[comphead]

@Dandandan do you mean these?
https://github.com/apache/arrow-datafusion/pull/4342/files#diff-08e5824197365dbe355c53949deee767063f6ac52f65974e19da0c0a63ae4f7cR222

https://github.com/apache/arrow-datafusion/pull/4540/files#diff-08e5824197365dbe355c53949deee767063f6ac52f65974e19da0c0a63ae4f7cR233

[comphead]

so yeah, size function needed to calc additional number of bytes that were allocated during aggregate_batch process.
I have commented this out and the same query runs 4 sec instead of 100sec.

@Dandandan @alamb I'll file a ticket to optimize this part

[Dandandan]

so yeah, size function needed to calc additional number of bytes that were allocated during aggregate_batch process. I have commented this out and the same query runs 4 sec instead of 100sec.

@Dandandan @alamb I'll file a ticket to optimize this part

Yes, some quadratic complexity because of the growing state.

[Dandandan]

(you could identify it from your flamegraph, it's just the longest bar(s) at the top consuming all the time)

[comphead]

Right, the function was evident to identify, but it was introduced recently, took some time to figure out its purpose.

[comphead]

Filed #5325

@Dandandan @alamb should we close this ticket?

[alamb]

I agree the analysis is done -- thank you @comphead