Can GROUP BY still be optimized after all these years? | Hacker News Reader

Can GROUP BY still be optimized after all these years?

pivotlake.io

122 pointsntur133726 comments

I wonder why you didn't opt to perform a Top-K aggregation in each partition in parallel. That would give you both a reduction of elements in each partition and also the correct maximum of each partition, which can be used for further pruning.

The query is:

  SELECT item_id, COUNT(*) AS c
  FROM orders
  GROUP BY item_id
  ORDER BY c DESC
  LIMIT 10;

They are getting the top 10 most frequent values of item_id. It's possible for one item_id to be the 11th most popular item across every partition and not the 10th. Then when you sum the counts across all partitions, it becomes the 10th most common.

> Then when you sum the counts across all partitions, it becomes the 10th most common.

They are already summing these counts _before applying their optimization_.

From what I see this is the "base" algorithm:

    1. Get the data from disk, which will be partitioned by storage key.
    2. Parallelizing by storage key, aggregate each partition according to the grouping key. The result are many partitions by grouping key holding partially aggregated data.
    3. Parallelizing by grouping key, merge the partially aggregated results. The results are fully aggregated partitions (each item is present in one and only one partition)
    4. Merge these partitions into a global list of aggregated results
    5. Pick the top K of this list

Both the optimization in the article and my proposal act on step 4. At that point the aggregation for an item is already guaranteed to exist in exactly one partition, so there's no way it can be 11th in the partition but 10th in the overeall aggregation.

Neat! For others, the data structure they are describing is a count-min sketch. It looks like they're using it to set a bound on elements that can enter the group-by and using it to skip a bunch of extra work

Their clickbench results look really good.

https://benchmark.clickhouse.com/#system=+liH|Hoaus|DcD|ucqs...

What's the difference between pivot and duckdb? They seem rather similar and this implementation of group by may be copied by other to achieve similar bench results

Hi! One of Pivot’s authors here :)

While DuckDB is a query engine that can indeed also query Iceberg and other open table formats, Pivot aims to bring the experience of a “full database” like ClickHouse to the world of open data formats - with the ability to spin up a cluster, run a single query across multiple nodes, handle ingestion and compaction, run in server mode to serve multiple clients, etc.. in a fast and efficient way

We love DuckDB, but we see that many companies still choose ClickHouse over DuckDB, despite its proprietary storage format, because it offers a complete end-to-end solution that DuckDB doesn’t

Comparison feels more like to Motherduck for this kind of thing

(And I'm unclear what will happen given the Amazon situation)

Hi, thanks for the reply! Sorry, to bother you but I'm not familiar with Clickhouse. I'm trying to understand what you mean by "spin up a cluster, run a single query...". That's the "compute" part of a "suite" working on databases, like one could use Unity Catalog, but don't use the cluster compute on Databricks. So your main difference with duckdb or mother duck is the interconnection between the DB solution and "compute" to use the DB?

You know, I have a hard time seeing how it can be cheaper to run a dataset across a wire rather than just send its grouped results. That's really the problem. I mean, who cares if it takes 100ns to group by on a box when it will take 10 times much for the data to get to it and back.

The fastest possible group by is in sequential memory on that box, fetched from an nvme.

So, when we do group by partitioning, we're really saying, put the groups themselves on different boxes, and group the group by. If it were some utter megaset, the place to put it is on a mainframe, which is basically created for purposes of group by on ridiculous datasets.

group by is useful with other aggregates like sum, max, and so on.

At least they have useful technical information in it. Personally really like reading these blog posts.

Measurements and context is so situational that it would be useless anyway imo.

It is not like any DB company is writing blog posts with benchmarks compared to hardware limits. DuckDB had blog posts that has sentences like "You are doing it wrong if you are not using HTTP api on your database in 2026", last time I saw their blog.

I also think object storage is bad in this case. And rust is no a no-no for a database project like this, because it is not ergonomic to do static allocation and arena allocators in rust. And parquet is trash for performance because of many reasons like supported compression formats etc.

> And rust is no a no-no for a database project like this, because it is not ergonomic to do static allocation and arena allocators in rust.

I'm not sure ergonomics matter that much these days, when your agent can write the tedious bits?

Code being in a simple state also matters with the efficiency of agents ime.

It is not just ergonomics but the point of using rust is to have solid abstraction and a lot of high quality libraries to use.

If you are doing static allocation + arenas then you can't use nice abstraction, you can't use libraries, you have to write a ton of unsafe code because of these reasons. Then using rust is actually working against you so there is no point in using it.

You're not wrong: if you know how much memory you need for a single query and can keep the data in attached SSD (so ephemeral SSD on AWS), scaling vertically will give you the fastest execution time.

However horizontal scaling has advantages in that it's easier to scale up and down incrementally. It gives you more aggregate network bandwidth for accessing disaggregated data. Disaggregation allows for independent scaling of compute and storage. Losing a single machine has a marginal impact on the cluster, which can enable you to use cheaper spot resources.

Basically, it's often easier to operate a system designed around horizontal scaling if you need resiliency.

22.2ms vs 35.6ms is 1.6x faster! It's 0.4x faster and even doing worst math possible it's 0.62x faster.

Can't we really keep the IT without breaking news/we are all gonna die/sensationalist way of passing news?

The problem is that “faster” and “slower” compare speed, which is x units per y time. But here, we’re only comparing time. The semi-legit interpretation is “if one unit takes 22.2ms, how many units can I complete in 35.6ms”, and actually the answer to that is indeed the 1.6 number they mention.

It’s not sensationalist, it’s just a bit sloppy with the word “faster”.

It's 60% faster (0.6x faster, 1.6x as fast). Throughput (“how much stuff you can do per unit of time”) is the only reasonable way to describe performance[1], otherwise large speedups are basically impossible to describe in an intuitive way. (If something that took 10s now takes 1s, that's “ten times as fast”, not “zero point nine times faster”.)

[1] Even latency changes are best described in terms of throughput.

how can lantency changes be described in terms of throughput? you can have completely different latencies with the same throughput due to different choices of pipelining, no?

The same way: If you change latency from 10s to 1s, it's ten times as fast in terms of latency (or 900% faster, if you will); earlier, you could do 0.1 things/second, and now you can do 1.0 thing/second. The only real difference between latency and throughput is whether you can overlap work instances or not, you can use the same language to talk about their changes.

You obviously cannot _calculate_ latency from throughput or vice versa (except of course that one bounds the other); they are different values. But both can use the (very simple, very intuitive) framework of “number of stuffs per time unit”.

Now where things become ugly is when you talk about “N% _slower_”, which is also useful but gets very quickly ambiguous and problematic when N is not close to zero.

> (If something that took 10s now takes 1s, that's “ten times as fast”, not “zero point nine times faster”.)

It still works with speed as the measurement (not as "zero point nine" but just "nine"), you just have to inverse the relationship. Going from 10s to 1s can still be described as "9 times faster" but it's because, less intuitively as you say, "faster" is comparing the 1s to the 10s (as in, "9(1s) plus 1s is 10s") rather than the other way around ("9(10s) plus 10s is 1s" is obviously false). This works because we know that 1s is less time than 10s; "faster" inverses the numerical relationship for time because increasing it inherently means "slower". Indeed, the difference between them is 9x where x = 1. And 10 to 0.1 is 99 times faster because 99x where x = 0.1 is 9.9 (measured by throughput, assuming only the rate changed, it's also 99x more things and 100x as many things).

(Not that I think you don't know all this, just nitpicking, really.)

1.6x faster is completely acceptable in natural language.

acceptable if you don't care about misunderstandings

More importantly, WHY is mysql GROUP BY still broken as default? MySQL is the PHP of databases, but it seems they have no plan to fix bugs.

MySQL GROUP BY is not broken by default (ONLY_FULL_GROUP_BY, the standards-conforming choice, is default for a decade or more). But there is basically no team left on the MySQL optimizer, after a long series of layoffs; it's gone from something like 40 to 3, give or take. Try Postgres :-)

I wonder if with a LLM you could better analyse and make a strategy for querying. Maybe even live restructuring of data models based on its usage.

Reply on news.ycombinator.com