# HLL (HyperLogLog) Tutorial

```elixir
Mix.install([
  {:ex_data_sketch, "~> 0.10"}
],
config: [
    ex_data_sketch: [
      backend: ExDataSketch.Backend.Rust,
      integrations: [opentelemetry: false]
    ]
  ])
```

## Introduction

Every event that arrives gets hashed. `ExDataSketch.HLL` looks at the
*pattern* of that hash -- specifically, how long a run of leading zero
bits it has -- and keeps only the longest run it has ever seen, per
bucket. Long runs are exponentially rare, so if you've observed a very
long one, you've probably hashed a lot of distinct items. That's the
whole trick: no set, no list, no per-item bookkeeping, just `2^p`
single-byte counters updated in place, forever:

```mermaid
flowchart LR
    A[event] --> B["hash(event)"]
    B --> C["first p bits\n= register index"]
    B --> D["remaining bits\n= leading-zero run length"]
    C --> E["registers[index] =\nmax(current, run length)"]
    D --> E
    E --> F["harmonic mean\nacross 2^p registers"]
    F --> G["cardinality\nestimate"]
```

**Use it for:** "how many unique visitors," "how many distinct IPs hit
this endpoint," "how many distinct users touched this feature this
month" -- any question where the *count* of distinct items matters but
you don't need to know *which* items they were, at a scale where
holding every item in memory would be wasteful or impossible.

**Don't use it for:** exact counts (HLL is inherently probabilistic --
reach for a `MapSet` or a database `COUNT(DISTINCT ...)` when the
number must be precise), membership testing ("was X one of the items
I've seen?" -- HLL can't answer that at all; see `ExDataSketch.Bloom`
or `ExDataSketch.Cuckoo`), or per-item frequency ("how many times did X
occur?" -- see `ExDataSketch.CMS`).

**What it buys you:** a precision-14 HLL is a fixed __16 KB__ (`4 + 2^p`
bytes, see the moduledoc's "Binary State Layout"), whether it has
counted a thousand events or a billion -- with roughly __0.8%__ expected
error at that precision (the formula is `~1.04/sqrt(2^p)`; see
"Precision Range" below for the full table). An exact set holding a
billion identifiers keeps growing without bound; the sketch does not:

| Approach                  | Memory (billion-event stream) | Answer      |
| ------------------------- | ----------------------------- | ----------- |
| Exact set (`MapSet`, DB)  | Grows unbounded (GBs, and up) | Exact       |
| `ExDataSketch.HLL` (p=14) | 16 KB, fixed                  | ~0.8% error |

If a fraction of a percent of error is an acceptable trade for constant,
tiny memory, HLL is usually the right first reach for a distinct-count
problem.

## Sample data (cached locally)

2,000,000 page-view events from a pool of 500,000 distinct visitors --
so the *true* distinct count is 500,000, even though there are 4x as
many events. This mismatch (events != distinct visitors) is exactly
what HLL is for. `ExDataSketch.SampleData` generates and caches this
(and every other tutorial's sample data) to a local file, so re-running
this livebook later is instant after the first time.

```elixir
events = ExDataSketch.SampleData.hll_events()
IO.puts("#{length(events)} events ready (true distinct count: 500,000)")
```

## Basic usage

```elixir
alias ExDataSketch.HLL

sketch = HLL.new(p: 14)
sketch = HLL.update(sketch, "visitor_1")
HLL.estimate(sketch)
```

`update/2` is for one item at a time; `update_many/2` (or `from_enumerable/2`
to build straight from a collection) is far more efficient for a batch like
our sample data:

```elixir
sketch = HLL.from_enumerable(events, p: 14)

estimate = HLL.estimate(sketch)
true_count = 500_000
error_pct = abs(estimate - true_count) / true_count * 100

IO.puts("Estimate: #{Float.round(estimate, 0)}")
IO.puts("True count: #{true_count}")
IO.puts("Error: #{Float.round(error_pct, 2)}%")
IO.puts("Sketch size: #{HLL.size_bytes(sketch)} bytes")
```

## Precision trade-off

`:p` controls both memory (`2^p` registers) and accuracy. Higher `p` means
more memory, less error:

```elixir
for p <- [4, 10, 12, 14, 16, 20] do
  sketch = HLL.from_enumerable(events, p: p)
  estimate = HLL.estimate(sketch)
  error_pct = abs(estimate - 500_000) / 500_000 * 100

  IO.puts(
    "p=#{p}: #{HLL.size_bytes(sketch)} bytes, " <>
      "estimate=#{Float.round(estimate, 0)}, error=#{Float.round(error_pct, 2)}%"
  )
end
```

### Why 4..26?

`p >= 4` is a real algorithmic floor: the bias-correction constant
`alpha(m)` (`m = 2^p`, the register count) is only defined via exact
published values for `m in {16, 32, 64}` plus a general asymptotic
formula valid for `m >= 128` -- together these cover exactly `p >= 4`,
with no case for `p < 4`.

`p <= 26` is a *practical* ceiling, not an algorithmic one -- nothing in
HLL's register encoding or estimator caps `p` below 26 (registers are
plain bytes with tons of headroom, and `alpha(m)`'s formula works for
any `m >= 128`). It's set to 26 specifically to match `ExDataSketch.ULL`'s
ceiling, which *is* a hard limit (see `ull.livemd`), so choosing between
the two estimators is an apples-to-apples memory/precision tradeoff. At
`p = 26` a single sketch is 64 MiB -- most workloads should stay at
`p <= 18` or so, well below either ceiling.

## Merging (distributed counting)

HLL merge is associative and commutative -- you can split your event stream across
N workers, each builds its own sketch, and merging them gives the same
answer as if one process had seen everything:

```elixir
half = div(length(events), 2)
{first_half, second_half} = Enum.split(events, half)

worker_a = HLL.from_enumerable(first_half, p: 14)
worker_b = HLL.from_enumerable(second_half, p: 14)

merged = HLL.merge(worker_a, worker_b)
IO.puts("Merged estimate: #{Float.round(HLL.estimate(merged), 0)} (true: 500,000)")
```

## Serialization

```elixir
sketch = HLL.from_enumerable(Enum.take(events, 100_000), p: 14)
IO.puts("before serialize estimate: #{Float.round(HLL.estimate(sketch), 0)}")
binary = HLL.serialize(sketch)
{:ok, restored} = HLL.deserialize(binary)

IO.puts("Round-tripped estimate: #{Float.round(HLL.estimate(restored), 0)}")
```

## Operational guidance

| `p` | Memory | Typical error               |
| --- | ------ | --------------------------- |
| 10  | ~1KB   | ~3.25%                      |
| 12  | ~4KB   | ~1.6%                       |
| 14  | ~16KB  | ~0.8% (recommended default) |
| 16  | ~64KB  | ~0.4%                       |

## See also

* `ExDataSketch.HLL` module documentation -- full API reference.
* `ExDataSketch.ULL` -- an alternative cardinality estimator; see
  `livebooks/sketches/ull.livemd` for the comparison.
* `guides/streaming_sketches.md`, `livebooks/streaming_cardinality.livemd`
  -- `Stream`/`Collectable` integration instead of building from a plain list.
* `guides/apache_interop.md` -- reading/writing sketches built by the
  Apache DataSketches Java/C++/Python implementations.