Support first-visited limitk compatibility in ALB TSM fanout

Parent: #1068

Summary

Add global PromQL limitk(k, v) handling to ALB Time Series Merge (TSM)
using the selection algorithm in the current Prometheus evaluator: for every
aggregation group and evaluation timestamp, retain the first k input samples
encountered while visiting the inner expression's result matrix.

Prometheus documentation describes the subset as deterministic
pseudo-random, but the current implementation does not assign a label-hash
score or rank all candidates. It scans the input matrix in its existing order,
appends samples until each group has k, and then may stop scanning early.

Prometheus requests selector series from storage without requiring them to be
sorted. Consequently, there is no public canonical visitation order that a
federated query layer can reconstruct to guarantee the identical label set a
separate global Prometheus deployment would have selected. Trickster will
reproduce the current first-visited algorithm over a stable, documented TSM
merged-series order. It will guarantee cardinality, grouping, repeatability for
the same merged input/order, and independence from goroutine completion order,
but will not claim identical selected-series identity across different storage
engines or physical shard layouts.

limitk is experimental in Prometheus. This compatibility contract should be
revisited if Prometheus defines a canonical selection order or changes its
implementation.

Compatibility contract

• For each (result, timestamp, aggregation group), scan the globally merged
  inner vector in stable TSM series order.
• Retain the first min(k, group cardinality) samples present at that
  timestamp.
• Use by and without only to form selection groups; selected samples retain
  their complete original PromQL labels and values.
• Include both float and native-histogram samples.
• Do not rank by value or by label hash.
• Do not promise the same selected label set as a separate global Prometheus
  instance whose storage layer supplies a different input order.
• Do guarantee that asynchronous fanout completion does not affect the merged
  order or selected result.

Scope

• Support non-negative literal k values accepted by the target Prometheus
  compatibility version.
• Support by (...) and without (...), before or after the aggregation
  arguments.
• Support instant and range queries.
• Preserve float samples, native-histogram samples, original labels, and sample
  values.
• Preserve common outer sort and sort_desc wrappers.
• Rewrite and globally merge the inner expression before selection whenever
  it contains an operation already supported by the TSM planner.
• Retain a warning for unsupported scalar parameter expressions or inner
  expressions whose cross-shard semantics TSM cannot evaluate correctly.

Implementation guidance

• Extend the aggregation parser beyond topk/bottomk to produce a
  limitk specification containing k, inner query, grouping, and any
  outer sort wrapper.
• Rewrite fanout requests to the inner expression rather than allowing
  every shard to independently discard all but its local first k.
• Classify and merge the rewritten inner expression before finalization,
  so a query such as limitk(5, sum by (service, instance) (...)) uses
  globally merged inner values.
• Define stable TSM merged-series order as pool-member index followed by
  the order of series in that member's response, subject to normal
  same-label-set deduplication. If the existing merge layer uses a different
  stable order, document and test that order instead.
• Ensure concurrent fanout completion and batch-merge scheduling cannot
  change finalizer input order.
• In the finalizer, precompute each series' by/without group and then,
  at each timestamp, scan series in merged order and retain the first k
  samples present in every group.
• Once every known group has selected k samples for a timestamp, stop
  examining later series for that timestamp, matching Prometheus's early-
  termination optimization.
• For range queries, make selection independently at every timestamp. A
  series can be selected at one step and omitted at another.
• Preserve native histograms rather than filtering them as the existing
  topk/bottomk finalizer does.
• Apply routing-only/injected-label handling before group calculation and
  final output so those labels neither create artificial groups nor leak to
  clients.
• Preserve incomplete-fanout warnings; first-k selection over incomplete
  input is not a complete federated result.

Acceptance criteria

• For a fixed ordered inner vector, Trickster selects the same first k
  samples per group/timestamp as the current Prometheus evaluator.
• The result contains min(k, group cardinality) samples for every group
  and timestamp.
• k = 0, k = 1, k greater than group cardinality, malformed k, and
  overflow cases match Prometheus behavior for the supported literal
  parameter forms.
• Repeated requests over the same merged inputs produce the same selected
  label sets.
• Fanout response completion order and TSM merge batching do not change the
  result.
• by and without work for instant and range queries.
• Float and native-histogram samples retain their original labels and
  values.
• Exact HA replicas are deduplicated before selection.
• Outer sort and sort_desc behavior remains compatible with the
  existing TSM finalizer, including its range-query warning.
• Supported queries no longer include the generic inaccurate-result
  warning.
• User-facing documentation explicitly states that selected-series
  identity may differ from another Prometheus deployment with a different
  inner-vector visitation order.

Tests

• Parser tests for grouping positions, wrappers, invalid/overflow k, and
  unsupported scalar parameter expressions.
• Ordered-vector table tests proving first-visited rather than value- or
  hash-ranked selection.
• Per-group cardinality tests for k = 0, k = 1, and k > N.
• Tests with interleaved groups proving the first k of each group are
  retained.
• Determinism tests across fanout completion orders and batch-merge
  schedules while pool order and inputs remain fixed.
• A pool-order test documenting that changing the defined merged input
  order is allowed to change the selected subset.
• Multi-shard, exact-HA-deduplication, and injected-label tests.
• Instant and range tests with sparse samples and changing membership.
• Float/native-histogram preservation tests.
• Nested inner-merge test such as
  limitk(2, sum by (service, instance) (requests)).
• Partial-failure and capture-limit tests.
• Benchmarks for high-cardinality inputs and large k.

Prometheus references

• limitk operator documentation
  describes the intended deterministic pseudo-random subset behavior,
  grouping, and support for float and histogram samples.
• PromQL aggregation evaluator (engine.go)
  is the implementation compatibility reference. Relevant sections include
  eval for AggregateExpr, rangeEvalAgg, and aggregationK's LIMITK
  branch, which scans inputMatrix in order and stops after collecting k
  samples for every group. The same file also shows that a top-level range
  result is label-sorted before being returned, while an in-process outer
  limitk operates before that final result sort; a rewritten inner range
  query therefore cannot expose the original internal visitation order.
• Prometheus storage interface (interface.go)
  defines the Select(..., sortSeries bool, ...) contract. The evaluator calls
  it with sortSeries=false, so selector visitation order is not a canonical
  label sort imposed by PromQL.
• Original Prometheus implementation PR #12503
  describes limitk as returning the first N gathered samples and explains
  its early-termination motivation.
• Prometheus feature-flag documentation
  describes the experimental PromQL feature gate that includes limitk.

Non-goals

• Label-hash or value-based ranking; neither represents the current Prometheus
  limitk evaluator.
• Guaranteeing identical selected-series identity with a separate Prometheus
  deployment that visits its inner vector in a different order.
• Making the result invariant to an intentional change in the documented TSM
  merged-series order, such as reordering pool members.
• Supporting an arbitrary inner expression whose cross-shard behavior cannot
  be planned by TSM.