Hacker News
points by malisper 19 hours ago | 0 comments
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.
[–] SkiFire13 55 minutes ago
> 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.