Approach summary:- Don’t build large in-memory sets per group. Use either exact distributed COUNT(DISTINCT) with key bucketing/partitioning or an approximate sketch (HLL) for memory efficiency at scale.- Trade-offs: concatenating keys (country||'|'||device||'|'||user_id) allows a single global distinct but can be expensive and requires shuffling; exact COUNT(DISTINCT) is accurate but memory- and network-heavy. HLL trades off small, bounded memory and speed for an error (~1-2% typical) and easy mergeability.1) Exact per (country, device) using concatenated key (scales by shuffling; heavy for high cardinality users)sql
-- BigQuery: exact distinct (may be expensive for huge user_id cardinality)
SELECT country, device, COUNT(DISTINCT user_id) AS distinct_users
FROM `project.dataset.events`
GROUP BY country, device;
If you need a single global distinct across many grouping columns you can concatenate:sql
SELECT
SPLIT(k, '|')[OFFSET(0)] AS country,
SPLIT(k, '|')[OFFSET(1)] AS device,
COUNT(DISTINCT SPLIT(k, '|')[OFFSET(2)]) AS distinct_users
FROM (
SELECT CONCAT(country, '|', device, '|', user_id) AS k
FROM `project.dataset.events`
)
GROUP BY country, device;
Note: concatenation increases row size and still requires heavy aggregation; watch delimiter collisions and NULLs (use safe encoding).2) Approximate using BigQuery built-in APPROX_COUNT_DISTINCT (fast, low memory, acceptable error)sql
SELECT
country,
device,
APPROX_COUNT_DISTINCT(user_id) AS approx_distinct_users
FROM `project.dataset.events`
GROUP BY country, device;
- Pros: simple, scalable, low memory, distributed-friendly.- Cons: non-zero error, not mergeable with arbitrary custom sketches.3) HLL sketch flow (more control; create per-shard sketches, merge; useful in streaming/ETL pipelines)- Pseudocode / BigQuery HLL functions (init → merge → estimate):sql
-- create per-row HLL sketch
WITH sketches AS (
SELECT
country,
device,
HLL_COUNT.INIT(user_id) AS hll -- create HLL sketch per row/partition
FROM `project.dataset.events`
)
-- aggregate/merge sketches per group then extract estimate
SELECT
country,
device,
HLL_COUNT.EXTRACT(HLL_COUNT.MERGE_AGG(hll)) AS approx_distinct_users
FROM sketches
GROUP BY country, device;
If HLL_COUNT.* isn’t available, use a public HLL UDF (e.g., Google-provided HLL UDF) to build and merge byte-array sketches similarly. In streaming pipelines (Beam/Spark) use an HLL library (e.g., stream-lib, datasketches) to create per-partition sketches and merge reducers.Trade-offs and guidance:- Use exact COUNT(DISTINCT) when correctness is mandatory and cardinality is moderate.- Use APPROX_COUNT_DISTINCT for quick queries and dashboards where ~1-2% error is acceptable.- Use HLL sketches when you need: - Controlled, mergeable sketches across pipeline stages, - To store compact sketches in tables for later merges, - Very high-cardinality and strict resource limits.- Watch out for: - Bias/standard error of chosen HLL parameters, - Storing sketches as BYTES/VARBINARY and versioning UDFs, - Null/user_id format normalization before sketching.Complexity:- Exact COUNT(DISTINCT): heavy network I/O and memory; worst-case O(N) state per group.- HLL/APPROX: O(1) memory per group (sketch size), O(N) time streaming but tiny per-row cost.