Set and dedup operations: aggregation with an empty accumulator

How do UNION, INTERSECT, EXCEPT and DISTINCT follow from what we already know, and which shortcut is dangerous?

Deduplication is aggregation with an empty accumulator

• Hash dedup is the hash aggregation from Aggregation algorithms with nothing in the value slot.
• Sort dedup is the sort-based aggregation from Aggregation algorithms with nothing in the value slot.
• INTERSECT and EXCEPT are the semi-join and anti-join from the earlier articles, with every column as the key. (A semi-join keeps rows of one side that have a match on the other; an anti-join keeps rows that have none.)

Almost the entire article has already been derived. Noticing that is worth more than the article itself: the operator catalogue has real structure instead of being a list, and four mechanisms cover eleven surface features. What is left is one thing, and it is the most dangerous item here.

The state parameter, and the one inversion from aggregation

Dedup's state is O(NDV). Its output is NDV rows. Its two-phase arithmetic is the same as in Aggregation algorithms: local dedup, shuffle by key, final dedup, with the reduction factor N/(P·G), where G is the distinct count. Everything transfers.

One thing inverts, and exactly halfway. In Aggregation algorithms, the state of partial aggregation is a cache, not a requirement: flush it whenever you like, the final merge fixes it. For dedup this holds for the local stage and fails for the final stage.

• A local dedup that flushes early emits some duplicates, which the final stage removes.
• A final dedup that forgets a key emits it twice, and nothing downstream corrects it.

So partial dedup is safely flushable, and final dedup is not. The final stage must fit in memory, spill, or be replaced by a sort.

This is why sort-based dedup is more attractive here than in aggregation. Sort dedup uses O(1) memory (compare each key to the previous one, emit when it changes) and cannot fail on memory at any input size. If the input is already sorted, which it often is after a merge join, an LSM read or a clustered scan, dedup is free and fully streaming.

There is also a latency asymmetry that does not match the earlier articles. Hash dedup emits a row the moment it is first seen. It is state-blocking (it must keep all keys) but not latency-blocking (it does not make you wait). Sort dedup is both. In aggregation, both variants were latency-blocking, so hash had no latency advantage. In dedup it does. The hash/sort duality is real, but its balance point moves with the operator. This is the third time that has come up.

Wide keys: hash the digest, and use 128 bits

DISTINCT on a full row, INTERSECT and EXCEPT all use every column as the key, so the key is wide. Two consequences follow from the sorting article.

1. Normalized keys pay off here more than anywhere, because a multi-column typed comparison is exactly what they remove.
2. The reduction ratio N/(P·G) tends toward 1 when the key is the whole row. Nearly unique keys mean nearly no reduction. So partial dedup usually does not pay for set operations on wide rows, unlike grouped aggregation, where it almost always pays.

The standard implementation hashes each row to a fixed-width digest (a short fingerprint) and dedups on the digest. The width matters more than people think. With a b-bit digest and n rows, the probability that at least two rows collide is roughly 1 − exp(−n² / 2^(b+1)) (the "birthday" formula).

At ten billion rows a collision is not a risk. It is the expected result. And in dedup, a digest collision means a row is thrown away as a "duplicate" when it was not one.

Approximate dedup: the same filter, the opposite consequence

The phrase "sketch-based approximate dedup" mixes up two different problems. Naming the mix-up is the correction.

Approximate distinct counting (HyperLogLog and its relatives) answers "how many distinct values are there?" It belongs to the aggregation article, because it is an aggregation. It has no membership query at all: HLL cannot tell you whether a particular row has been seen. It only knows how many distinct items it absorbed.

Approximate duplicate removal needs a membership structure, such as a Bloom filter or a cuckoo filter. These answer "have I seen this key?" with one-sided error: no false negatives, some false positives (they may say "yes, seen" when the answer is no, but never say "no" when the answer is yes). Here is the whole point.

• In the join article, a Bloom filter's false positive meant a probe row passed the filter, reached the exact join, and was correctly rejected there. The error cost work.
• In dedup, a false positive means the filter says "seen before" about a row that was not seen. The row is dropped. No exact test downstream catches it. The error costs data, silently and permanently.

Same structure, same mathematics, same library call, opposite consequence. This refines the earlier principle "a conservative pre-filter keeps the answer exact":

The repair is to invert the test. Use the filter as a negative oracle:

• "Definitely not present" means certainly new: emit at once, no lookup.
• "Possibly present" means check the exact structure.

Now a false positive costs a lookup instead of a row, and the exact structure sees only a small share of the traffic. This is how an LSM-tree point lookup uses a Bloom filter to skip files: the same pattern, arriving here again. A sketch of the pattern:

def dedup_stream(rows, bloom, exact_store):
    for key, row in rows:
        if not bloom.might_contain(key):   # definitely new
            bloom.add(key); exact_store.add(key)
            yield row
        elif key not in exact_store:       # false positive: filter said "maybe"
            bloom.add(key); exact_store.add(key)
            yield row
        # else: truly seen before, drop

(The exact store still needs memory or disk proportional to the number of distinct keys; the filter only saves lookups.)

Where approximate dedup is acceptable:

• best-effort telemetry, where volume control matters more than completeness;
• pipelines whose consumer is itself idempotent (repeating or missing a suppression can be repaired);
• bounded-window dedup, where the filter is reset periodically, so the error is bounded in time instead of accumulating forever.

Where it is not acceptable: anything that produces a reported figure. It is deployed there anyway, routinely, because a 0.1% silent row loss is invisible to every monitor anyone builds. Who pays when the assumption breaks? The downstream consumer, in numbers that are quietly and permanently a little low.

This is also the one place here where a point on the exact-versus-approximate scale is chosen wrongly by default, because the technique is imported from a setting where its error was harmless. It is also a fail-degraded choice (the system keeps running with worse results) with no matching fail-fast signal (nothing tells anyone). It degrades without telling anybody, which is the worst position on that scale.