# UNDF: UNDF-2026-000000330
# victoria-metrics-0001 — `streamaggr`: O(L×K) `slices.Contains` inside `Push()` hot loop

## Status
PATCHED

## Severity
HIGH (>20× speedup at L=30, K=20, N=10k series/batch)

## Location
- `lib/streamaggr/streamaggr.go`, functions `dropSeriesLabels()` (line 164) and
  `getInputOutputLabels()` (lines 1127–1141)
- `lib/streamaggr/deduplicator.go`, function `dropSeriesLabels()` (line 164)

## Description
`aggregator.Push(tss []prompb.TimeSeries, ...)` is the hot ingestion path —
called on every scrape cycle for every matching time series. For each series
it invokes two label-filter helpers:

```go
// dropSeriesLabels — deduplicator.go:164 / streamaggr.go (shared)
func dropSeriesLabels(dst, src []prompb.Label, labelNames []string) []prompb.Label {
    for _, label := range src {
        if !slices.Contains(labelNames, label.Name) {  // O(K) linear scan
            dst = append(dst, label)
        }
    }
    return dst
}

// getInputOutputLabels — streamaggr.go:1127
func getInputOutputLabels(..., by, without []string) (...) {
    for _, label := range labels {
        if slices.Contains(without, label.Name) { ... }  // O(K) per label
    }
    // and the `by` branch is symmetric
}
```

`labelNames`, `by`, and `without` are **static aggregation-rule config** — they
do not change between calls. Yet for every series in every scrape batch, each
label (up to L per series) triggers a full O(K) walk of the config slice.

Total cost per `Push` call:
```
O(N × L × K)
```
where N = time series in batch, L = labels per series, K = `len(by|without|dropLabels)`.

At production scale (N=10k, L=30, K=20) that is **6 million comparisons** per
scrape cycle instead of 300k with a pre-built `map[string]bool`.

### Why `by`/`without` are never pre-built
`by` and `without` are stored as `[]string` fields on `aggregator` (set once
during `newAggregator`). Neither `getInputOutputLabels` nor `dropSeriesLabels`
receives a map — the helpers are passed raw slices every call.

## Patch

Pre-compute `map[string]struct{}` sets for `without`, `by`, and
`dropInputLabels` in `newAggregator()` and store them alongside the slices.
Pass the maps (or replace the slice parameters with maps) in the hot-path
helpers.

```go
// In aggregator struct — add:
bySet      map[string]struct{}
withoutSet map[string]struct{}
dropSet    map[string]struct{}

// In newAggregator():
a.bySet      = stringSliceToSet(cfg.By)
a.withoutSet = stringSliceToSet(cfg.Without)
a.dropSet    = stringSliceToSet(cfg.DropInputLabels)

// helpers:
func stringSliceToSet(ss []string) map[string]struct{} {
    m := make(map[string]struct{}, len(ss))
    for _, s := range ss {
        m[s] = struct{}{}
    }
    return m
}

// dropSeriesLabels — O(L) instead of O(L×K):
func dropSeriesLabels(dst, src []prompb.Label, dropSet map[string]struct{}) []prompb.Label {
    for _, label := range src {
        if _, drop := dropSet[label.Name]; !drop {
            dst = append(dst, label)
        }
    }
    return dst
}

// getInputOutputLabels — O(L) instead of O(L×K):
func getInputOutputLabels(dstInput, dstOutput, labels []prompb.Label,
    bySet, withoutSet map[string]struct{}) ([]prompb.Label, []prompb.Label) {
    if len(withoutSet) > 0 {
        for _, label := range labels {
            if _, ok := withoutSet[label.Name]; ok {
                dstInput = append(dstInput, label)
            } else {
                dstOutput = append(dstOutput, label)
            }
        }
    } else {
        for _, label := range labels {
            if _, ok := bySet[label.Name]; !ok {
                dstInput = append(dstInput, label)
            } else {
                dstOutput = append(dstOutput, label)
            }
        }
    }
    return dstInput, dstOutput
}
```

## Speedup estimate
| N series | L labels | K filters | Defective ops | Fixed ops | Ratio |
|---------|---------|-----------|--------------|-----------|-------|
| 1,000   | 10      | 10        | 100,000      | 10,000    | 10×   |
| 10,000  | 30      | 20        | 6,000,000    | 300,000   | 20×   |
| 100,000 | 30      | 20        | 60,000,000   | 3,000,000 | 20×   |

## Patch file
See `victoria-metrics-0001-streamaggr-label-filter-map.patch`
