# REQ (Relative Error Quantiles) Tutorial

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

## Introduction

`ExDataSketch.REQ` uses the same level-and-compaction shape as
`ExDataSketch.KLL`, but with one deliberate asymmetry: compaction
doesn't discard a random half uniformly -- it *prefers* to discard the
half that matters least. In **HRA** mode (High Rank Accuracy, the
default), that means preferentially discarding low-value detail and
keeping high-quantile detail; **LRA** does the opposite. The result is
a sketch that spends its entire error budget where you told it to
care, instead of spreading it evenly like KLL does:

```mermaid
flowchart LR
    A[value] --> B["level 0 buffer"]
    B --> C{"level full?"}
    C -->|no| D[stored]
    C -->|yes| E["HRA: discard low half,\nkeep high-rank detail"]
    E --> F["level 1 buffer\n(promoted at 2x weight)"]
    F --> G["... more levels"]
    G --> H["quantile/rank query:\nweighted merge across levels"]
```

**Use it for:** SLO/tail-latency monitoring where "how bad is our
worst 1%" (p99, p99.9) matters far more than the median -- HRA
concentrates accuracy exactly there. LRA does the mirror-image job for
low-tail questions (p1, p5).

**Don't use it for:** anywhere you need *uniform* accuracy across the
whole distribution, median included -- that's what
`ExDataSketch.KLL`'s unbiased compaction is for; REQ's tail accuracy is
bought by deliberately sacrificing accuracy at the other end. Also
worth knowing: unlike most families here, REQ has no Rust NIF
acceleration at all (see its moduledoc) -- fine at REQ's typically
small `k`, but a factor at very high ingest rates.

**What it buys you:** aggressive biased compaction makes REQ very
compact at its typically-small `k`. A `k: 12`, HRA sketch (the library
default) over 1,000,000 latency samples measured __524 bytes__ --
against ~7.6 MB to store every raw value, roughly __14,500x smaller__
-- while still resolving p99.9 accurately, which is the one number a
uniform-error sketch of similar size would blur:

| Approach                          | Memory (1M samples) | Where accuracy lives     |
| ------------------------------------ | ---------------------- | ---------------------------- |
| Exact (sorted array of `f64`)       | ~7.6 MB                 | Everywhere (exact)            |
| `ExDataSketch.REQ` (k=12, HRA)      | 524 bytes                | Concentrated at high ranks    |

## Sample data (cached locally)

1,000,000 latencies (ms): tight and boring in the bulk (10-30ms),
with a long, important tail (a few requests taking seconds) --
exactly the shape where p99.9 accuracy matters more than p50 accuracy.

```elixir
latencies = ExDataSketch.SampleData.req_latencies()
sorted = Enum.sort(latencies)
IO.puts("#{length(latencies)} latency samples ready")
```

## Basic usage (HRA mode, the default)

```elixir
alias ExDataSketch.REQ

sketch = REQ.new(k: 12, hra: true) |> REQ.update_many(latencies)

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

## HRA vs LRA: where the accuracy budget goes

Build the same data into both modes and compare error at a *low* quantile
(p10) against a *high* one (p99.9) -- HRA should be visibly more accurate
at p99.9 and less accurate at p10; LRA the reverse.

This sample is a hard case for a small `k`: 99.9% of it is squeezed into
just 20 distinct discrete values (11-30ms), with the "important" tail
(500-5000ms) only 0.1% of the data. At `k: 12` (REQ's default) there
isn't enough retained resolution left for the HRA/LRA bias to show up at
all -- both modes converge to nearly the same (poor) answer at p99.9.
Push `k` up to `800` and the intended asymmetry reappears clearly:

```elixir
exact_percentile = fn p ->
  idx = min(round(p * length(sorted)), length(sorted) - 1)
  Enum.at(sorted, idx)
end

hra_sketch = REQ.new(k: 800, hra: true) |> REQ.update_many(latencies)
lra_sketch = REQ.new(k: 800, hra: false) |> REQ.update_many(latencies)

for {label, s} <- [{"HRA", hra_sketch}, {"LRA", lra_sketch}] do
  IO.puts("== #{label} ==")

  for p <- [0.1, 0.999] do
    exact = exact_percentile.(p)
    estimate = REQ.quantile(s, p)
    error_pct = abs(estimate - exact) / exact * 100
    IO.puts("  p#{p}: exact=#{Float.round(exact, 2)}, estimate=#{Float.round(estimate, 2)}, error=#{Float.round(error_pct, 1)}%")
  end
end
```

HRA's p99.9 error should now be clearly *smaller* than LRA's (LRA barely
escapes the 11-30ms bulk at all, typically still reporting something
near 30), and LRA's p10 error should be clearly smaller than HRA's --
the intended trade-off, showing up as designed. Don't expect HRA's own
p99.9 error to be small in absolute terms, though: p99.9 sits right at
the boundary between the dense bulk and the sparse tail, the same kind
of density cliff covered in `ExDataSketch.KLL`'s moduledoc -- a
correctly-working sketch can still land far from the exact value there,
because a tiny rank shift crosses from "extremely common" to "extremely
rare" data.

## rank/2, cdf/2, pmf/2

```elixir
rank_at_1s = REQ.rank(sketch, 1000.0)
IO.puts("#{Float.round(rank_at_1s * 100, 2)}% of requests were under 1 second")

REQ.cdf(sketch, [50.0, 500.0, 2000.0])
```

## count, min, max

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

## Merging

Both sketches being merged must share the same `:hra` mode:

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

worker_a = REQ.new(k: 12, hra: true) |> REQ.update_many(first_half)
worker_b = REQ.new(k: 12, hra: true) |> REQ.update_many(second_half)

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

## Serialization

```elixir
binary = REQ.serialize(sketch)
{:ok, restored} = REQ.deserialize(binary)
IO.puts("Round-tripped p99: #{Float.round(REQ.quantile(restored, 0.99), 1)}ms")
```

## See also

* `ExDataSketch.REQ` module documentation -- full API reference.
* `ExDataSketch.KLL` -- uniform accuracy across all ranks instead of
  biased toward one tail; see `livebooks/sketches/kll.livemd`.
* `ExDataSketch.DDSketch` -- value-relative (not rank-biased) accuracy;
  see `livebooks/sketches/ddsketch.livemd`.