Choose a dedup strategy
A query must remove duplicate rows (DISTINCT, UNION, deduplicating events) or count distinct values. Deduplication is aggregation with an empty accumulator: its state grows with the number of distinct values, and the final stage cannot be flushed early. Which method fits?
You will end with a deduplication method, sized against memory, and a safe policy for approximation.
Decide
Do you need to remove duplicates, or only count distinct values?
RemoveGo to 2
Why
Different problems, different structures. For counting, a sketch is usually right; for removing rows, it is usually wrong, because its errors drop or keep rows.
Is the input already sorted or grouped by the key?
Why
If duplicates arrive next to each other, comparing each row with the previous one removes them in constant memory. Nothing else needs deciding.
Does the final stage's set of distinct keys fit in memory?
Why
The final stage must hold every distinct key until the input ends; it cannot emit and forget. If it overflows, it either spills partitions to disk or, with a sort, works in bounded memory and cannot fail.
Where you can land
A distinct-count sketch
Use it when you only need the number of distinct values.
HyperLogLog or a Theta sketch: tiny, mergeable state with a known error.
Streaming dedup
Use it when input arrives sorted or grouped by the key.
Constant memory, no spill. What it costs: nothing, if the order really is guaranteed.
Hash dedup
Use it when the distinct keys fit in memory.
Before you build it
Decide whether a local stage pays
Pre-deduplicating on each worker before the shuffle pays only if each worker sees many copies of each key: rows ÷ (workers × distinct keys) well above 1. For grouping keys it usually does; when the key is the whole row, it usually does not.
Sort-based dedup, or spill by partition
Use it when the distinct keys do not fit in memory.
What it costs: sorting, or writing partitions to disk and processing them one at a time.
Whichever you land on
Wide rows: hash to 128 bits
If the key is a wide row: compare a 128-bit digest instead of the full row, and normalize the key first (trim, case, type) so equal values hash equally. Shorter digests collide often enough at scale to merge distinct rows.
Approximation: check which way the error points
A Bloom filter that says "seen before" can be wrong, and a false positive means a genuine new row is dropped. If you approximate: invert the filter into a negative test ("definitely not seen" is always right) with an exact check for the rest, or do not approximate.