Follow-up to #130, which added an exact AggCountDistinct.
Why
The exact count keeps one entry per distinct value per group for the duration of the scan. That is the right trade for the attributes people usually count by (Owner, Host, JobStatus), and the wrong one for a high-cardinality attribute over a large history — COUNT(DISTINCT GlobalJobId) over a few hundred million archived rows would hold every value in memory to produce one number.
An approximate count answers the same question in O(1) memory per group, which is what makes it usable at that scale.
What
A second function — AggApproxCountDistinct — accumulating a HyperLogLog per group during the scan instead of a set. It must be a separate function, asked for by name: silently approximating a query written COUNT(DISTINCT ...) would be wrong rather than fast, which is why #130 did not do it.
Because the sketch is built during the scan (rather than read from the per-segment segStats.hll), it composes with everything the exact version does:
- a
WHERE constraint,
GROUP BY, including a bucketed time series,- a per-aggregate
FILTER (WHERE ...).
What NOT to do
The persisted per-segment sketches (segStats.hll) look tempting — merging them answers a distinct count without touching a single row. But they are per segment per indexed attribute and cover the whole segment, so they can only answer an unconstrained, ungrouped count. That is a small enough slice of real queries that a fast path for it would mostly add a second code path with different accuracy characteristics. Worth reconsidering only if unconstrained whole-table distinct counts turn out to be a hot pattern.
Wire
It needs no new opcode: like AggCountDistinct, an unrecognized AggFunc on the extended opcodes is refused by an older server (ErrExtendedAggregateUnsupported), so adding an enum value is enough. See anyFiltered in dbrpc/aggregate.go.
Accuracy
Whatever HLL precision is chosen should be stated in the doc comment and in the column header or function name, so a reader knows the number is an estimate. Standard HLL at p=14 is ~0.8% relative error for ~1.6 KiB per group; the per-group memory bound is the whole point, so the precision should be fixed rather than tunable per query.
Repl side
Once this exists, htcondordb needs the spelling (APPROX_COUNT_DISTINCT(attr), and possibly COUNT(DISTINCT attr) APPROXIMATE) plus a client-side reduction for the AS OF and computed-group-key paths — the same two places COUNT(DISTINCT) needed one.
Follow-up to #130, which added an exact
AggCountDistinct.Why
The exact count keeps one entry per distinct value per group for the duration of the scan. That is the right trade for the attributes people usually count by (
Owner,Host,JobStatus), and the wrong one for a high-cardinality attribute over a large history —COUNT(DISTINCT GlobalJobId)over a few hundred million archived rows would hold every value in memory to produce one number.An approximate count answers the same question in O(1) memory per group, which is what makes it usable at that scale.
What
A second function —
AggApproxCountDistinct— accumulating a HyperLogLog per group during the scan instead of a set. It must be a separate function, asked for by name: silently approximating a query writtenCOUNT(DISTINCT ...)would be wrong rather than fast, which is why #130 did not do it.Because the sketch is built during the scan (rather than read from the per-segment
segStats.hll), it composes with everything the exact version does:WHEREconstraint,GROUP BY, including a bucketed time series,FILTER (WHERE ...).What NOT to do
The persisted per-segment sketches (
segStats.hll) look tempting — merging them answers a distinct count without touching a single row. But they are per segment per indexed attribute and cover the whole segment, so they can only answer an unconstrained, ungrouped count. That is a small enough slice of real queries that a fast path for it would mostly add a second code path with different accuracy characteristics. Worth reconsidering only if unconstrained whole-table distinct counts turn out to be a hot pattern.Wire
It needs no new opcode: like
AggCountDistinct, an unrecognizedAggFuncon the extended opcodes is refused by an older server (ErrExtendedAggregateUnsupported), so adding an enum value is enough. SeeanyFilteredindbrpc/aggregate.go.Accuracy
Whatever HLL precision is chosen should be stated in the doc comment and in the column header or function name, so a reader knows the number is an estimate. Standard HLL at p=14 is ~0.8% relative error for ~1.6 KiB per group; the per-group memory bound is the whole point, so the precision should be fixed rather than tunable per query.
Repl side
Once this exists,
htcondordbneeds the spelling (APPROX_COUNT_DISTINCT(attr), and possiblyCOUNT(DISTINCT attr) APPROXIMATE) plus a client-side reduction for the AS OF and computed-group-key paths — the same two placesCOUNT(DISTINCT)needed one.