Parallelizing ClickHouse aggregation merge for fixed hash map

Summary

I recently worked on https://github.com/ClickHouse/ClickHouse/pull/87366. The idea is simple but learned a lot of ClickHouse aggregation, so want to jot it down.BackgroundThe original issue stated it clear, if you run almost identical queries, their performances varies a lot!milovidov-pc :) SELECT number % 10000 AS k, uniq(number) AS u FROM numbers_mt(1e9) GROUP BY k ORDER BY u DESC LIMIT 10 SELECT number % 10000 AS k, uniq(number) AS u FROM numbers_mt(1000000000.) GROUP BY k ORDER BY u DESC LIMIT 10 Query id: d3e22e17-1a32-4615-bf1a-a2da6e0510eb ┌────k─┬──────u─┐ 1. │ 4759 │ 101196 │ 2. │ 4587 │ 101079 │ 3. │ 6178 │ 101034 │ 4. │ 6567 │ 101032 │ 5. │ 9463 │ 101013 │ 6. │ 298 │ 101009 │ 7. │ 2049 │ 100993 │ 8. │ 8167 │ 100989 │ 9. │ 5530 │ 100973 │ 10. │ 1968 │ 100973 │ └──────┴────────┘ 10 rows in set. Elapsed: 62.793 sec. Processed 1.00 billion rows, 8.00 GB (15.93 million rows/s., 127.40 MB/s.) Peak memory usage: 11.30 GiB. milovidov-pc :) SELECT 0 + number % 10000 AS k, uniq(number) AS u FROM numbers_mt(1e9) GROUP BY k ORDER BY u DESC LIMIT 10 SELECT 0 + (number % 10000) AS k, uniq(number) AS u FROM numbers_mt(1000000000.) GROUP BY k ORDER BY u DESC LIMIT 10 Query id: e6a24292-54cf-47cb-8e39-81584736d41a ┌────k─┬──────u─┐ 1. │ 4759 │ 101196 │ 2. │ 4587 │ 101079 │ 3. │ 6178 │ 101034 │ 4. │ 6567 │ 101032 │ 5. │ 9463 │ 101013 │ 6. │ 298 │ 101009 │ 7. │ 2049 │ 100993 │ 8. │ 8167 │ 100989 │ 9. │ 5530 │ 100973 │ 10. │ 1968 │ 100973 │ └──────┴────────┘ 10 rows in set. Elapsed: 8.547 sec. Processed 1.00 billion rows, 8.00 GB (116.99 million rows/s., 935.95 MB/s.) Peak memory usage: 10.09 GiB.The only difference is that second query is using 0 + (number % 10000) for the group by value k.ClickHouse treats the k as UInt16 in first query and UInt64 (or other types that UInt16). But why this matters? Let's delve into the aggregation technical details a bit in ClickHouse.How Aggregation WorksWhen group by a number smaller than UInt16, could use array for hashmap.Otherwise use...