Probabilistic Data Structures (HyperLogLog).

In Big Data, the "Count Distinct" problem is notoriously expensive because it is not additive. You cannot simply sum the distinct counts of two partitions to get the global distinct count (User A might exist in both). To get an exact answer, you must shuffle all User IDs to a single reducer or maintain a global hash map, which scales linearly with Cardinality ($O(N)$). As $N$ approaches billions, memory requirements exceed physical RAM, causing disk spills and extreme slowness.

Application: HyperLogLog (HLL) is an algorithm that estimates cardinality by hashing elements and observing the probability of bit patterns (leading zeros). It consumes constant space ($O(1)$ effectively, usually a few KB) regardless of input size. In a Databricks/Spark context, swapping COUNT(DISTINCT) for approx_count_distinct transforms an I/O-bound, memory-hogging operation into a CPU-bound, lightweight operation. For dashboards and real-time reporting where "Directional Accuracy" (trends) is more valuable than "Accountant Accuracy" (exact integers), this optimization often yields 10x-100x performance improvements. The engineer effectively trades precision (which is expensive) for speed (which is cheap), a critical architectural decision in processing high-cardinality telemetry data.

Exam: exam2