# DDSketch Tutorial

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

## Introduction

`ExDataSketch.DDSketch` maps every value into a logarithmically-spaced
bucket (`index = log(value) / log(gamma)`, where `gamma` is derived from
`alpha`) and just counts how many values landed in each bucket. Because
bucket boundaries are geometric rather than linear, every bucket
represents the *same relative width* regardless of where it sits in the
range -- which gives a guaranteed **relative error on the value, not the
rank**. A query for quantile `q` returns a value `v` such that the true
value `v'` satisfies `v' * (1 - alpha) <= v <= v' * (1 + alpha)` -- the
same relative accuracy whether you're looking at a 2ms value or a
20,000ms one:

```mermaid
flowchart LR
    A[value] --> B["index =\nlog(value) / log(gamma)"]
    B --> C["buckets[index] += 1"]
    C --> D["quantile query:\nwalk buckets by rank"]
    D --> E["value = geometric\nmidpoint of bucket"]
```

**Use it for:** latency/telemetry percentiles spanning several orders
of magnitude, where "off by 1ms" matters a lot at the low end and not
at all at the high end -- SLO/SLA tracking that needs the *same*
accuracy promise at p50 and at p99.9, not just wherever most of the
mass sits.

**Don't use it for:** negative values (rejected outright -- zero is
handled separately via a dedicated `zero_count`, but negative inputs
aren't representable); data with a narrow, known range where
`ExDataSketch.KLL`'s uniform *rank* error would use less memory for
comparable effective precision; exact percentiles where correctness
must be exact.

**What it buys you:** at the library default `alpha: 0.01` (1%
relative error), a real 1,000,000-value latency distribution spanning
roughly 1ms-5000ms measured __~3.4 KB__ -- bucket count scales with the
*range* of magnitudes observed, not the item count, so a wider dynamic
range costs more buckets but more data at the same range costs nothing
extra:

| Approach                              | Memory (1M values, ~1-5000ms range) | Guarantee                  |
| ---------------------------------------- | -------------------------------------- | ----------------------------- |
| Exact (sorted array of `f64`)          | ~7.6 MB                                | Exact                          |
| `ExDataSketch.DDSketch` (alpha=0.01)   | ~3.4 KB                                | +-1% relative value error, everywhere |

## Sample data (cached locally)

1,000,000 operation durations (ms) spanning several orders of
magnitude: fast API calls (~1-50ms), medium DB queries (~50-500ms),
and rare slow batch jobs (~10,000-100,000ms). DDSketch only accepts
non-negative values.

```elixir
durations = ExDataSketch.SampleData.ddsketch_durations()
sorted = Enum.sort(durations)
IO.puts("#{length(durations)} duration samples ready, spanning #{Float.round(List.first(sorted), 2)}ms to #{Float.round(List.last(sorted), 0)}ms")
```

## Basic usage

```elixir
alias ExDataSketch.DDSketch

sketch = DDSketch.new(alpha: 0.01) |> DDSketch.update_many(durations)

DDSketch.quantiles(sketch, [0.5, 0.9, 0.99, 0.999])
```

## Relative accuracy at both ends of the scale

Compare DDSketch's error at a *small* quantile value against a *large*
one -- both should be within `alpha`, unlike a fixed absolute-error
sketch, where the large value's error would dwarf the small one's:

```elixir
exact_percentile = fn p ->
  # Matches ExDataSketch.DDSketch.quantile/2's own rank convention exactly
  # (target = p * n, returns the value once cumulative count reaches that
  # target -- effectively the target-th smallest item, 1-indexed) rather
  # than an independently-chosen indexing scheme. A plain
  # `Enum.at(sorted, round(p * n))` is 0-indexed and off by one rank from
  # what DDSketch itself targets; that one-rank gap is usually
  # inconsequential, but exactly at a bucket boundary it can land the
  # "exact" reference value in the *next* bucket over from the one
  # DDSketch correctly answered for, making a correct estimate look like
  # it exceeded `alpha` when it didn't.
  rank = max(1, round(p * length(sorted)))
  Enum.at(sorted, min(rank - 1, length(sorted) - 1))
end

# p50 is in the "fast API calls" range (small values); p99.5 is in the
# "slow batch jobs" range (large values) -- three orders of magnitude apart.
for p <- [0.5, 0.995] do
  exact = exact_percentile.(p)
  estimate = DDSketch.quantile(sketch, p)
  relative_error = abs(estimate - exact) / exact * 100
  IO.puts("p#{p}: exact=#{Float.round(exact, 2)}ms, estimate=#{Float.round(estimate, 2)}ms, relative error=#{Float.round(relative_error, 2)}%")
end
```

Both relative errors should be at most `alpha * 100 = 1%`, regardless of
the three-orders-of-magnitude gap between the two values -- that's the
DDSketch guarantee, and it's a *tight* bound (achieved at a bucket's
edges), not a "usually comfortably inside" one, so don't be surprised to
see values sitting close to `1%` rather than well under it.

## Sizing: alpha trade-off

```elixir
for alpha <- [0.05, 0.01, 0.005, 0.001] do
  s = DDSketch.new(alpha: alpha) |> DDSketch.update_many(durations)
  estimate = DDSketch.quantile(s, 0.99)
  exact = exact_percentile.(0.99)
  error_pct = abs(estimate - exact) / exact * 100
  IO.puts("alpha=#{alpha} (#{DDSketch.size_bytes(s)} bytes): p99 error=#{Float.round(error_pct, 2)}%")
end
```

## count, min, max

`min_value/1`/`max_value/1` track the raw minimum/maximum ever inserted
at full precision -- independent of `alpha` and of the log-scale bucket
machinery entirely. With 900,000 samples drawn uniformly from `[0, 50)`
for the "fast API calls" bucket, the smallest of that many draws lands
well under 0.001ms (expected order of magnitude ~`50 / 900_000`), so
don't be surprised to see `Min: 0.0ms` if you round to only 3 decimal
places -- it's rounding display precision, not the sketch losing the
value:

```elixir
IO.puts("Count: #{DDSketch.count(sketch)}")
IO.puts("Min: #{DDSketch.min_value(sketch)}ms (exact, not rounded)")
IO.puts("Max: #{Float.round(DDSketch.max_value(sketch), 0)}ms")
```

## Merging

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

worker_a = DDSketch.new(alpha: 0.01) |> DDSketch.update_many(first_half)
worker_b = DDSketch.new(alpha: 0.01) |> DDSketch.update_many(second_half)

merged = DDSketch.merge(worker_a, worker_b)
IO.puts("Merged p99: #{Float.round(DDSketch.quantile(merged, 0.99), 1)}ms")
```

## Serialization

```elixir
binary = DDSketch.serialize(sketch)
{:ok, restored} = DDSketch.deserialize(binary)
IO.puts("Round-tripped p50: #{Float.round(DDSketch.quantile(restored, 0.5), 2)}ms")
```

## See also

* `ExDataSketch.DDSketch` module documentation -- full API reference and
  the DDS1 binary layout.
* `ExDataSketch.KLL` -- rank-relative accuracy instead of value-relative;
  see `livebooks/sketches/kll.livemd` for when that distinction matters.
* `ExDataSketch.REQ` -- extra accuracy specifically at extreme tail
  quantiles; see `livebooks/sketches/req.livemd`.