<commit_before># Request deduplication throughout the render path

# Plan construction

During plan construction, identical requests can be deduplicated.
Requests are identical based on:
* metric name/patterns or SeriesByTag() call
* the context: depending on which functions have been passed through, the from/to or pngroup may have been adjusted (assuming pre-normalization is not disabled)

Examples:
* `target=(foo.*)&target=movingAverage(consolidateBy(sum(foo.*),"max"), "1min")` are different.
  We request `foo.*` twice, but with different from/to, consolidator and pngroup.
  (also MDP optimization may play a role here, but that is experimental / should always be disabled)
* `target=foo&target=sum(foo)`. PNGroup property will be 0 and >0 respectively.
* `target=sum(foo)&target=sum(foo)`. PNGroup property will different for both targets.

If they are identical, they lead to identical expr.Req objects, and will be saved in the plan only a single time.
Importantly, equivalent requests may appear (e.g. requests for the same series, once with and once without a pngroup)

# index lookups

For the purpose of index lookups we deduplicate more aggressively and only look at query/from/to.
Other properties such as pngroup, consolidator are not relevant for this purpose.
Note that a query like `target=foo.*&target=foo.bar` will return the series foo.bar twice, these are currently not deduplicated.

# ReqMap

For each combination of a plan.Req and all its resulting series, we generate a models.Req and save it into ReqMap.
Again, these requests may only differ by pngroup, consolidator or query pattern, despite covering the same data fetch

# Request planning: planRequests()

The ReqsPlan returned by planRequests() may have equivalent or identical requests.
E.g. a PNGroup may only change the effective fetch parameters if there's multiple different series, with different intervals, with the same PNGroup, because in that case, pre-normalization may kick in, and a different archive may be selected. (or the same archive/fetch but normalization at runtime)
Also, since max-points-per-req-soft gets applied group by group, and then the singles, breaching this condition may lead to different requests.

The point being, requests may be non-identical though equivalent in the ReqsPlan.

# getTargets

As described above, the list of models.Req to fetch, may contain requests that are non-identical though equivalent

* Pattern: as described in index lookups, we may fetch the exact same data twice, if it came in via different query patterns.
* PNgroup alone does not affect fetching, though honoring the PNGroup may have had an effect on e.g. the archive to fetch or AggNum
* ConsReq: requested consolidator does not matter for fetching or any processing
* Consolidator: the consolidator may have an effect on fetching (if we query a rollup) and/or on after-fetch normalization
* AggNum: affects after-fetch runtime-normalization, but not the fetching
* MaxPoints: only for mdp optimization (ignored here, experimental)

The fields that materially affect fetching are MKey, archive, from, to (and Consolidator if a rollup is fetched)

# datamap

The datamap is a list of series, grouped by expr.Req (which tracks the requested consolidator, but not the used consolidator)
There are a few cases where different expr.Req entries may have overlapping, or even identical lists of series:
* there may be two different requests with a Pattern such as `foo.*` and `foo`
* a request like `target=foo&target=sum(foo)` or `target=sum(foo)&target=sum(foo)` (and pre-normalization enabled) led to different requests to the pngroup

Note: even if the same series is present elsewhere in the datamap, each copy is a full/independent/deep copy.

# function processing

loading data and feeding into the function processing chain happens through FuncGet, which lookups data based on the expr.Req coming from the user, which maps 1:1 to the datamap above.
In particular: it takes into account pngroups (even if they lead to equivalent fetches and thus identical series). But each copy of a series is a distinct, deep copy.
It is important to note that any series may be processed or returned more than once. E.g. a query like `target=a&target=a`. For this reason, any function or operation such as runtime consolidation, needs to make sure not to effect the contents of the datamap.
How we solve this is described in the section "Considerations around Series changes and reuse and why we chose copy-on-write" below.

# Considerations when writing a Graphite processing function in metrictank

## constructors should return a pointer

* so that properties can be set
* we get a consistent PNGroup through the pipeline (if applicable)

(the exception here is the data loading function FuncGet() which doesn't need to set any properties)

## consider whether the function is GR, IA, a transparent or opaque aggregation, or combine different series together somehow

Such functions require special options. see [the optimizations documentation](../docs/render-path.md#optimizations)

## implement our copy-on-write approach when dealing with modifying series

See section 'Considerations around Series changes and reuse and why we chose copy-on-write' below.

* must not modify the fields of any pre-existing `models.Series`. Because these are stored in a slice, other functions may refer to the same slice and modifying them in place could potentially propagate changes to other execution branches.
  (exception: FuncGet)
* should use the pool to get new slices in which to store their new/modified datapoints.
* should add said new slices into the dataMap so that when the plan has run, and the caller calls plan.Clean(), we can return its datapoints slice to the pool.
* the other purpose of the dataMap is to add processed data to the set of available data such that other functions could reuse it, but this mechanism is not implemented yet.
  That's why we always add to the dataMap without bothering to set the right request key (`dataMap[Req{}]`).

example: an averageSeries() of 3 series:
* will create an output series value.
* it will use a new datapoints slice, retrieved from pool, because the points will be different. Also, it will allocate a new meta section and tags map because they are also different from the input series.
* won't put the 3 inputs back in the pool or dataMap, because whoever allocated the input series was responsible for doing that. We must not add the same arrays to the pool multiple times.
* It will however store the newly created series into the dataMap such that during plan cleanup time, the series' datapoints slice will be moved back to the pool.

# Considerations around Series changes and reuse and why we chose copy-on-write.

## Introduction

The `models.Series` type, even when passed by value, has a few fields that need special attention:
* `Datapoints []schema.Point`
* `Tags       map[string]string`
* `Meta       SeriesMeta`

Many processing functions, as well as other code running after function processing (e.g. runtime normalization)
will want to return an output series that differs from the input in terms of datapoints, tags or metadata.
They need a place to store their output but we cannot simply operate on the input series, or even a copy of it, as the underlying datastructures are shared.
(in particular, shared with the canonical copies inside of the datamap. The same series may be pulled out of the datamap multiple times if the same target is used more than once in a query).

## Goals

* processing should not modify data if that data needs to remain original (e.g. because of re-use of the same input data elsewhere)
* minimize allocations of new structures foremost
* minimize data copying as a smaller concern
* simple code

# Implementation

there's 2 main choices:

1) copy-on-write:
- each function does not modify data in their inputs, they allocate new structures (or possibly get from pool) if there's differences with input
- storing output data into new slice can typically be done in same pass as processing the input data
- if you have lots of processing steps (graphite function calls) in a row, we will be creating more slices and copy more data than strictly necessary (intermediate copies. also some points may not change).
- getting a slice from the pool may cause a stall if it's not large enough and runtime needs to re-allocate and copy
- allows us to pass the same data into multiple processing steps (reuse input data)

2) copy in advance:
- provide each processing function with input series in which they can do whatever they want (e.g. modify in place)<commit_msg>document series reuse stuff better<commit_after># Request deduplication throughout the render path

# Plan construction

During plan construction, identical requests can be deduplicated.
Requests are identical based on:
* metric name/patterns or SeriesByTag() call
* the context: depending on which functions have been passed through, the from/to or pngroup may have been adjusted (assuming pre-normalization is not disabled)

Examples:
* `target=(foo.*)&target=movingAverage(consolidateBy(sum(foo.*),"max"), "1min")` are different.
  We request `foo.*` twice, but with different from/to, consolidator and pngroup.
  (also MDP optimization may play a role here, but that is experimental / should always be disabled)
* `target=foo&target=sum(foo)`. PNGroup property will be 0 and >0 respectively.
* `target=sum(foo)&target=sum(foo)`. PNGroup property will different for both targets.

If they are identical, they lead to identical expr.Req objects, and will be saved in the plan only a single time.
Importantly, equivalent requests may appear (e.g. requests for the same series, once with and once without a pngroup)

# index lookups

For the purpose of index lookups we deduplicate more aggressively and only look at query/from/to.
Other properties such as pngroup, consolidator are not relevant for this purpose.
Note that a query like `target=foo.*&target=foo.bar` will return the series foo.bar twice, these are currently not deduplicated.

# ReqMap

For each combination of a plan.Req and all its resulting series, we generate a models.Req and save it into ReqMap.
Again, these requests may only differ by pngroup, consolidator or query pattern, despite covering the same data fetch

# Request planning: planRequests()

The ReqsPlan returned by planRequests() may have equivalent or identical requests.
E.g. a PNGroup may only change the effective fetch parameters if there's multiple different series, with different intervals, with the same PNGroup, because in that case, pre-normalization may kick in, and a different archive may be selected. (or the same archive/fetch but normalization at runtime)
Also, since max-points-per-req-soft gets applied group by group, and then the singles, breaching this condition may lead to different requests.

The point being, requests may be non-identical though equivalent in the ReqsPlan.

# getTargets

As described above, the list of models.Req to fetch, may contain requests that are non-identical though equivalent

* Pattern: as described in index lookups, we may fetch the exact same data twice, if it came in via different query patterns.
* PNgroup alone does not affect fetching, though honoring the PNGroup may have had an effect on e.g. the archive to fetch or AggNum
* ConsReq: requested consolidator does not matter for fetching or any processing
* Consolidator: the consolidator may have an effect on fetching (if we query a rollup) and/or on after-fetch normalization
* AggNum: affects after-fetch runtime-normalization, but not the fetching
* MaxPoints: only for mdp optimization (ignored here, experimental)

The fields that materially affect fetching are MKey, archive, from, to (and Consolidator if a rollup is fetched)

# datamap

The datamap is a list of series, grouped by expr.Req (which tracks the requested consolidator, but not the used consolidator)
There are a few cases where different expr.Req entries may have overlapping, or even identical lists of series:
* there may be two different requests with a Pattern such as `foo.*` and `foo`
* a request like `target=foo&target=sum(foo)` or `target=sum(foo)&target=sum(foo)` (and pre-normalization enabled) led to different requests to the pngroup

Note: even if the same series is present elsewhere in the datamap, each copy is a full/independent/deep copy.

# function processing

loading data and feeding into the function processing chain happens through FuncGet, which lookups data based on the expr.Req coming from the user, which maps 1:1 to the datamap above.
In particular: it takes into account pngroups (even if they lead to equivalent fetches and thus identical series). But each copy of a series is a distinct, deep copy.
It is important to note that any series may be processed or returned more than once. E.g. a query like `target=a&target=a`. For this reason, any function or operation such as runtime consolidation, needs to make sure not to effect the contents of the datamap.
How we solve this is described in the section "Considerations around Series changes and reuse and why we chose copy-on-write" below.

# Considerations when writing a Graphite processing function in metrictank

## constructors should return a pointer

* so that properties can be set
* we get a consistent PNGroup through the pipeline (if applicable)

(the exception here is the data loading function FuncGet() which doesn't need to set any properties)

## consider whether the function is GR, IA, a transparent or opaque aggregation, or combine different series together somehow

Such functions require special options. see [the optimizations documentation](../docs/render-path.md#optimizations)

## implement our copy-on-write approach when dealing with modifying series

See section 'Considerations around Series changes and reuse and why we chose copy-on-write' below.

* must not modify the fields of any pre-existing `models.Series`. Because these are stored in a slice, other functions may refer to the same slice and modifying them in place could potentially propagate changes to other execution branches.
  (exception: FuncGet)
* should use the pool to get new slices in which to store their new/modified datapoints.
* should add said new slices into the dataMap so that when the plan has run, and the caller calls plan.Clean(), we can return its datapoints slice to the pool.
* the other purpose of the dataMap is to add processed data to the set of available data such that other functions could reuse it, but this mechanism is not implemented yet.
  That's why we always add to the dataMap without bothering to set the right request key (`dataMap[Req{}]`).

example: an averageSeries() of 3 series:
* will create an output series value.
* it will use a new datapoints slice, retrieved from pool, because the points will be different. Also, it will allocate a new meta section and tags map because they are also different from the input series.
* won't put the 3 inputs back in the pool or dataMap, because whoever allocated the input series was responsible for doing that. We must not add the same arrays to the pool multiple times.
* It will however store the newly created series into the dataMap such that during plan cleanup time, the series' datapoints slice will be moved back to the pool.

# Considerations around Series changes and reuse and why we chose copy-on-write.

## Introduction

`plan.Run()` runs all function processing as well as any needed follup, such as runtime consolidation.
To do this, it has a dataMap as its source of data. For more information on how this structure is generated,
see above. But the TLDR is that it is the source of truth of series data, keyed by the expr.Req,
and that each entry in the datamap may be read more than once (if the same expression is used multiple times in a query)

Many processing functions (or runtime consolidation) will want to return an output series that differs from the input,
e.g. a different target or interval, tags, datapoints, etc.

This requires 2 special considerations:

1. Since in most of the processing chain, series are passed as series lists (`in []models.Series`),
any change such as `in[0].Interval = <newvalue>` will impact the entry in the datamap.
2. The `models.Series` type, even when copied or passed by value, still has a few fields that need special attention, because
  the underlying datastructures are shared. These are:
  - `Datapoints []schema.Point`
  - `Tags       map[string]string`
  - `Meta       SeriesMeta`

Thus, when making changes, we need a place to store the new output. For 1. it suffices to take a copy of the series struct itself,
for 2, we need to copy the underlying datastructures.

## Goals

* processing functions should not modify data if that data needs to remain original (e.g. because of re-use of the same input data elsewhere)
* minimize allocations of new structures foremost
* minimize data copying as a smaller concern
* simple code

# Implementation

there's 2 main choices:

1) copy-on-write:
- each function does not modify data in their inputs, they allocate new structures (or possibly get from pool) if there's differences with input
- storing output data into new slice can typically be done in same pass as processing the input data
- if you have lots of processing steps (graphite function calls) in a row, we will be creating more slices and copy more data than strictly necessary (intermediate copies. also some points may not change).
- getting a slice from the pool may cause a stall if it's not large enough and runtime needs to re-allocate and copy
- allows us to pass the same data into multiple processing steps (reuse input data)

2) copy in advance:
- provide each processing function with input series in which they can do whatever they want (e.g. modify in place)
{'fraction_non_alphanumeric': 0.050514081358962896, 'fraction_numerical': 0.0014528386231560126, 'mean_word_length': 4.59631019387117, 'pattern_counts': {'":': 0, '<': 4, '<?xml version=': 0, '>': 6, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '2680983', 'n_tokens_mistral': 4462, 'n_tokens_neox': 4322, 'n_words': 2697}