Pivot slashes GROUP BY top-K queries by skipping partitions that can't matter
Can GROUP BY still be optimized after all these years?
Pivot found a novel optimization for GROUP BY queries that rank the top K groups by aggregate value. Standard engines merge every partition, even though the top 10 results can touch only a handful of them. By giving each partition fixed hash slots that track combined counts, Pivot can safely skip a partition when no slot exceeds the current Kth value. On ClickBench's Q16, it pruned over 70% of partitions and ran 1.6× faster, from 35.6 ms to 22.2 ms.
Both partitions contain 1,500 orders, but only the second contains an item that would change the result.
- malisper
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
- ozgrakkurt
Their clickbench results look really good.
https://benchmark.clickhouse.com/#system=+liH|Hoaus|DcD|ucqs...
- toddbandrowsky
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.