Approximate Top-K by Frequency

Concepts covered: Approximate Aggregates, Grouping

The last turn swaps salaries for frequencies. "Top 10 search queries per country per hour. 3 billion queries a day, 200 million distinct strings. Does it have to be exact?" Exact is 2 steps you own: COUNT(*) per query within each country and hour, then ROW_NUMBER over the counts. The cost is the first step, 1 counter per distinct (country, hour, query), tens of millions per executor in a busy hour, all of them shuffled. Ask whether the consumer needs the 10th count right.

Warehouses ship the approximate form: APPROX_TOP_K(query, 10, 1000) in Snowflake, approx_most_frequent(10, query, 1000) in Trino. The third argument is the number of counters the sketch keeps, and the error bound comes straight from it. BigQuery's APPROX_TOP_COUNT(query, 10) takes no capacity and does not document one, so no bound can be stated for it.

-- Exact: 1 counter per distinct (country, hour, query), then a window
WITH counts AS (
  SELECT country, hour, query, COUNT(*) AS n
  FROM searches
  GROUP BY country, hour, query
)
SELECT country, hour, query, n
FROM (
  SELECT *,
         ROW_NUMBER() OVER (PARTITION BY country, hour ORDER BY n DESC, query) AS rn
  FROM counts
) r
WHERE rn <= 10;

-- Approximate (Snowflake): 1 sketch of 1000 counters per (country, hour)
SELECT country, hour, APPROX_TOP_K(query, 10, 1000) AS top_queries
FROM searches
GROUP BY country, hour;

Space-Saving with 1000 counters

The algorithm underneath, wherever one is documented, is Space-Saving, and narrating it earns the credit. The sketch keeps m counters, and each holds an item and its count plus an error term. A tracked item's count goes up by 1. An untracked item takes a free counter at count 1. When none is free, the smallest counter is evicted, the newcomer inherits it at count min + 1, and min is recorded as its error. Nothing is undercounted, because an evicted item's count carries forward.

The merge row is the one to narrate, because a naive sum breaks the sketch: an item tracked on executor A and evicted on executor B loses B's occurrences and is undercounted. The mergeable rule charges it B's minimum counter as both count and error, since B could have seen it at most that many times. It then sums shared items and keeps the largest m, so overcount stays within (n1 + n2) / m. Each executor builds 1 sketch per (country, hour), and the shuffle carries 1000-entry sketches in place of a counter per string.

The items a sketch gets wrong

Be specific, because "it is approximate" is the answer the interviewer has heard 40 times. It gets the cutoff wrong: when the 10th and 11th queries are within the error of each other, the sketch can swap them. Below the boundary, a late arrival can carry an inherited count, so a query seen 300 times can sit at 10,300 with error 10,000, and the error field says to distrust it. Steady low-frequency items churn in and out and carry the largest errors. Heavy hitters far above n / m are always reported, and their order is right whenever their gap exceeds the error.

The consumer test fits 1 sentence: approximate when the reader acts on heavy hitters and tolerates swaps at the boundary, exact when anyone's pay or penalty rides on the 10th position, or an auditor will check it. If exact is too expensive, narrow the bucket; a group small enough to count exactly costs less than explaining a sketch to a regulator.

Approximate is good enough

• Trending and most-viewed panels refreshed every few minutes
• Autocomplete and recommendation seeds, where the 11th item is a near miss
• Spike alerts, where the heavy hitter is the signal

Run the exact query

• Any output that triggers a payment or a penalty, prizes included
• Compliance and audit reports, where a count must reproduce
• Buckets with a few thousand distinct items, where exact is cheap

Do

• Name the computation first: the count of rows in the group that strictly outrank this one
• End every ranking with a unique column, whichever of the 3 forms you write
• Rebuild a stored group from source on any delete or downgrade; apply inserts against the floor
• Lead the index with the group column, follow with the ORDER BY, and stop with a per-group LIMIT
• Aggregate before a local top N cut whenever you rank by a SUM or COUNT

Avoid

• Use INNER JOIN in the self-join form; the group's first row has nothing above it
• Assume the warehouse maintains a ranking view incrementally without reading its refresh rules
• Expect rn <= N to stop an index scan; the window reads every row of the partition
• Report an approximate top K where the 10th position pays out or gets audited
• Drop the error field from a sketch result; it tells the consumer which counts to trust

About this lesson

This section is part of the Top N Per Group: Advanced lesson on DataDriven, the home of data engineering. Lessons cover SQL, Python, Spark, data modeling and pipeline architecture, and each section pairs its explanation with worked examples and practice you run as you go.