[PERF] PromQL: replace maps with slices and reuse matching data structures in VectorBinop/And/Or/Unless by linasm · Pull Request #17159 · prometheus/prometheus

linasm · 2025-09-08T06:51:03Z

In this PR, we are reusing some vector matching data structures via EvalNodeHelper which reduces heap allocations. Also, the type of EvalNodeHelper.rightSigs and EvalNodeHelper.matchedSigs gets changed from map[int] to slices indexed by signature ordinal (for which we have a clear upper bound), further improving VectorBinop performance.

Benchmark results:

goos: darwin
goarch: arm64
pkg: github.com/prometheus/prometheus/promql
cpu: Apple M1 Pro
                                                                                                                │  main.txt   │   optimize-join-performance-5.txt   │
                                                                                                                │   sec/op    │   sec/op     vs base                │
JoinQuery/expr=rpc_request_success_total_+_rpc_request_error_total/steps=10000-10                                  3.264 ± 1%    2.774 ± 1%  -15.01% (p=0.000 n=10)
JoinQuery/expr=rpc_request_success_total_+_ON_(job,_instance)_GROUP_LEFT_rpc_request_error_total/steps=10000-10    4.222 ± 1%    3.369 ± 1%  -20.21% (p=0.000 n=10)
JoinQuery/expr=rpc_request_success_total_AND_rpc_request_error_total{instance=~"0.*"}/steps=10000-10              597.6m ± 1%   596.1m ± 2%        ~ (p=0.853 n=10)
JoinQuery/expr=rpc_request_success_total_OR_rpc_request_error_total{instance=~"0.*"}/steps=10000-10                1.381 ± 3%    1.402 ± 3%        ~ (p=0.353 n=10)
JoinQuery/expr=rpc_request_success_total_UNLESS_rpc_request_error_total{instance=~"0.*"}/steps=10000-10            1.327 ± 2%    1.338 ± 3%        ~ (p=0.796 n=10)
geomean                                                                                                            1.721         1.599        -7.09%

                                                                                                                │    main.txt    │   optimize-join-performance-5.txt    │
                                                                                                                │      B/op      │     B/op      vs base                │
JoinQuery/expr=rpc_request_success_total_+_rpc_request_error_total/steps=10000-10                                   54.41Mi ± 1%   54.17Mi ± 1%        ~ (p=0.218 n=10)
JoinQuery/expr=rpc_request_success_total_+_ON_(job,_instance)_GROUP_LEFT_rpc_request_error_total/steps=10000-10   1885.45Mi ± 0%   54.09Mi ± 1%  -97.13% (p=0.000 n=10)
JoinQuery/expr=rpc_request_success_total_AND_rpc_request_error_total{instance=~"0.*"}/steps=10000-10                38.10Mi ± 0%   28.21Mi ± 0%  -25.95% (p=0.000 n=10)
JoinQuery/expr=rpc_request_success_total_OR_rpc_request_error_total{instance=~"0.*"}/steps=10000-10                 38.48Mi ± 1%   28.72Mi ± 0%  -25.36% (p=0.001 n=10)
JoinQuery/expr=rpc_request_success_total_UNLESS_rpc_request_error_total{instance=~"0.*"}/steps=10000-10             38.42Mi ± 1%   28.66Mi ± 2%  -25.42% (p=0.000 n=10)
geomean                                                                                                             89.61Mi        36.86Mi       -58.87%

                                                                                                                │   main.txt    │   optimize-join-performance-5.txt   │
                                                                                                                │   allocs/op   │  allocs/op   vs base                │
JoinQuery/expr=rpc_request_success_total_+_rpc_request_error_total/steps=10000-10                                   562.7k ± 0%   562.7k ± 0%   -0.01% (p=0.005 n=10)
JoinQuery/expr=rpc_request_success_total_+_ON_(job,_instance)_GROUP_LEFT_rpc_request_error_total/steps=10000-10   20567.8k ± 0%   564.7k ± 0%  -97.25% (p=0.000 n=10)
JoinQuery/expr=rpc_request_success_total_AND_rpc_request_error_total{instance=~"0.*"}/steps=10000-10                306.9k ± 0%   296.9k ± 0%   -3.26% (p=0.000 n=10)
JoinQuery/expr=rpc_request_success_total_OR_rpc_request_error_total{instance=~"0.*"}/steps=10000-10                 306.9k ± 0%   296.9k ± 0%   -3.26% (p=0.000 n=10)
JoinQuery/expr=rpc_request_success_total_UNLESS_rpc_request_error_total{instance=~"0.*"}/steps=10000-10             306.9k ± 0%   296.9k ± 0%   -3.26% (p=0.000 n=10)
geomean                                                                                                             803.3k        383.7k       -52.24%

Does this PR introduce a user-facing change?

[PERF] Improve performance and reduce heap allocations in PromQL joins (VectorBinop)/And/Or/Unless.

linasm · 2025-11-18T09:33:25Z

@bboreham this used to be the 5th PR in the stack, but now I have rebased on main branch so that it is no longer dependent on other PRs (and also reran the benchmarks, accordingly).

…nless Signed-off-by: Linas Medziunas <[email protected]>

vpranckaitis

LGTM. Not sure why TestEndpointsDiscoveryWithUpdatedNodeMetadata failed CI run, seems unrelated.

krajorama

LGTM

bboreham

LGTM. Personally I think the change from map to slice is more important than the memory reuse, so I would put that in the title. And in a PERF line in the changelog.

bboreham · 2026-02-17T09:17:30Z

+			if (len(matchedSigsPresent) > 0 && matchedSigsPresent[sigOrd]) ||
+				(len(matchedSigs) > 0 && matchedSigs[sigOrd] != nil) {


Are these len>0 checks expected to have the same result as matching.Card == parser.CardOneToOne ?
If not, I didn't understand what is going on.
If yes, would it not be simpler to write that?

Good point, the conditions are equivalent. Updated.

Signed-off-by: Linas Medziunas <[email protected]>

linasm · 2026-02-17T12:04:09Z

LGTM. Personally I think the change from map to slice is more important than the memory reuse, so I would put that in the title. And in a PERF line in the changelog.

Thanks @bboreham , updated PR title and change description, please let me know if this still needs any further updates.

bwplotka

Thanks!

##### [\`v3.11.0\`](https://github.com/prometheus/prometheus/releases/tag/v3.11.0) - \[CHANGE] Hetzner SD: The `__meta_hetzner_datacenter` label is deprecated for the role `robot` but kept for backward compatibility, use the `__meta_hetzner_robot_datacenter` label instead. For the role `hcloud`, the label is deprecated and will stop working after the 1 July 2026. [#17850](prometheus/prometheus#17850) - \[CHANGE] Hetzner SD: The `__meta_hetzner_hcloud_datacenter_location` and `__meta_hetzner_hcloud_datacenter_location_network_zone` labels are deprecated, use the `__meta_hetzner_hcloud_location` and `__meta_hetzner_hcloud_location_network_zone` labels instead. [#17850](prometheus/prometheus#17850) - \[CHANGE] Promtool: Redirect debug output to stderr to avoid interfering with stdout-based tool output. [#18346](prometheus/prometheus#18346) - \[FEATURE] AWS SD: Add Elasticache Role. [#18099](prometheus/prometheus#18099) - \[FEATURE] AWS SD: Add RDS Role. [#18206](prometheus/prometheus#18206) - \[FEATURE] Azure SD: Add support for Azure Workload Identity authentication method. [#17207](prometheus/prometheus#17207) - \[FEATURE] Discovery: Introduce `prometheus_sd_last_update_timestamp_seconds` metric to track the last time a service discovery update was sent to consumers. [#18194](prometheus/prometheus#18194) - \[FEATURE] Kubernetes SD: Add support for node role selectors for pod roles. [#18006](prometheus/prometheus#18006) - \[FEATURE] Kubernetes SD: Introduce pod-based labels for deployment, cronjob, and job controller names: `__meta_kubernetes_pod_deployment_name`, `__meta_kubernetes_pod_cronjob_name` and `__meta_kubernetes_pod_job_name`, respectively. [#17774](prometheus/prometheus#17774) - \[FEATURE] PromQL: Add `</` and `>/` operators for trimming observations from native histograms. [#17904](prometheus/prometheus#17904) - \[FEATURE] PromQL: Add experimental `histogram_quantiles` variadic function for computing multiple quantiles at once. [#17285](prometheus/prometheus#17285) - \[FEATURE] TSDB: Add `storage.tsdb.retention.percentage` configuration to configure the maximum percent of disk usable for TSDB storage. [#18080](prometheus/prometheus#18080) - \[FEATURE] TSDB: Add an experimental `fast-startup` feature flag that writes a `series_state.json` file to the WAL directory to track active series state across restarts. [#18303](prometheus/prometheus#18303) - \[FEATURE] TSDB: Add an experimental `st-storage` feature flag. When enabled, Prometheus stores ingested start timestamps (ST, previously called Created Timestamp) from scrape or OTLP in the TSDB and Agent WAL, and exposes them via Remote Write 2. [#18062](prometheus/prometheus#18062) - \[FEATURE] TSDB: Add an experimental `xor2-encoding` feature flag for the new TSDB block float sample chunk encoding that is optimized for scraped data and allows encoding start timestamps. [#18062](prometheus/prometheus#18062) - \[ENHANCEMENT] HTTP client: Add AWS `external_id` support for sigv4. [#17916](prometheus/prometheus#17916) - \[ENHANCEMENT] Kubernetes SD: Deduplicate deprecation warning logs from the Kubernetes API to reduce noise. [#17829](prometheus/prometheus#17829) - \[ENHANCEMENT] TSDB: Remove old temporary checkpoints when creating a Checkpoint. [#17598](prometheus/prometheus#17598) - \[ENHANCEMENT] UI: Add autocomplete support for experimental `first_over_time` and `ts_of_first_over_time` PromQL functions. [#18318](prometheus/prometheus#18318) - \[ENHANCEMENT] Vultr SD: Upgrade govultr library from v2 to v3 for continued security patches and maintenance. [#18347](prometheus/prometheus#18347) - \[PERF] PromQL: Improve performance and reduce heap allocations in joins (VectorBinop)/And/Or/Unless. [#17159](prometheus/prometheus#17159) - \[PERF] PromQL: Partially address performance regression in native histogram aggregations due to using `KahanAdd`. [#18252](prometheus/prometheus#18252) - \[PERF] Remote write: Optimize WAL watching used for RW sending to reuse internal buffers. [#18250](prometheus/prometheus#18250) - \[PERF] TSDB: Optimize LabelValues intersection performance for matchers. [#18069](prometheus/prometheus#18069) - \[PERF] UI: Skip restacking on hover in stacked series charts. [#18230](prometheus/prometheus#18230) - \[BUGFIX] AWS SD: Fix EC2 SD ignoring the configured `endpoint` option, a regression from the AWS SDK v2 migration. [#18133](prometheus/prometheus#18133) - \[BUGFIX] AWS SD: Fix panic in EC2 SD when DescribeAvailabilityZones returns nil ZoneName or ZoneId. [#18133](prometheus/prometheus#18133) - \[BUGFIX] Agent: Fix memory leak caused by duplicate SeriesRefs being loaded as active series. [#17538](prometheus/prometheus#17538) - \[BUGFIX] Alerting: Fix alert state incorrectly resetting to pending when the FOR period is increased in the config file. [#18244](prometheus/prometheus#18244) - \[BUGFIX] Azure SD: Fix system-assigned managed identity not working when `client_id` is empty. [#18323](prometheus/prometheus#18323) - \[BUGFIX] Consul SD: Fix filter parameter not being applied to health service endpoint, causing Node and Node.Meta filters to be ignored. [#17349](prometheus/prometheus#17349) - \[BUGFIX] Kubernetes SD: Fix duplicate targets generated by `*DualStack` EndpointSlices policies. [#18192](prometheus/prometheus#18192) - \[BUGFIX] OTLP: Fix ErrTooOldSample being returned as HTTP 500 instead of 400 in PRW v2 histogram write paths, preventing infinite client retry loops. [#18084](prometheus/prometheus#18084) - \[BUGFIX] OTLP: Fix exemplars getting mixed between incorrect parts of a histogram. [#18056](prometheus/prometheus#18056) - \[BUGFIX] PromQL: Do not skip histogram buckets in queries where histogram trimming is used. [#18263](prometheus/prometheus#18263) - \[BUGFIX] Remote write: Fix `prometheus_remote_storage_sent_batch_duration_seconds` measuring before the request was sent. [#18214](prometheus/prometheus#18214) - \[BUGFIX] Rules: Fix alert state restoration when rule labels contain Go template expressions. [#18375](prometheus/prometheus#18375) - \[BUGFIX] Scrape: Fix panic when parsing bare label names without an equal sign in brace-only metric notation. [#18229](prometheus/prometheus#18229) - \[BUGFIX] TSDB: Fail early when `use-uncached-io` feature flag is set on unsupported environments. [#18219](prometheus/prometheus#18219) - \[BUGFIX] TSDB: Fall back to CLI flag values when retention is removed from config file. [#18200](prometheus/prometheus#18200) - \[BUGFIX] TSDB: Fix memory leaks in buffer pools by clearing reference fields before returning buffers to pools. [#17895](prometheus/prometheus#17895) - \[BUGFIX] TSDB: Fix missing mmap of histogram chunks during WAL replay. [#18306](prometheus/prometheus#18306) - \[BUGFIX] TSDB: Fix storage.tsdb.retention.time unit mismatch in file causing retention to be 1e6 times longer than configured. [#18200](prometheus/prometheus#18200) - \[BUGFIX] Tracing: Fix missing traceID in query log when tracing is enabled, previously only spanID was emitted. [#18189](prometheus/prometheus#18189) - \[BUGFIX] UI: Fix tooltip Y-offset drift when using multiple graph panels. [#18228](prometheus/prometheus#18228) - \[BUGFIX] UI: Update retention display in runtime info when config is reloaded. [#18200](prometheus/prometheus#18200)

linasm requested a review from roidelapluie as a code owner September 8, 2025 06:51

linasm changed the title ~~Optimize join performance 5~~ [PERF] PromQL: reuse matching data structures in VectorBinop/And/Or/Unless Sep 8, 2025

linasm force-pushed the optimize-join-performance-5 branch from 710e1d6 to c0a7af5 Compare September 10, 2025 11:46

linasm mentioned this pull request Sep 18, 2025

PromQL join improvements (>50% performance improvement, up to 96% reduced allocations) #17143

Open

github-actions Bot added the stale label Nov 9, 2025

aknuds1 removed the stale label Nov 17, 2025

linasm force-pushed the optimize-join-performance-5 branch from c0a7af5 to 7e555d5 Compare November 18, 2025 07:54

linasm mentioned this pull request Nov 18, 2025

[PERF] PromQL: memoize resulting metric hashes in VectorBinop #17142

Closed

krajorama self-assigned this Nov 25, 2025

linasm force-pushed the optimize-join-performance-5 branch 2 times, most recently from 6e937ed to 1aa6598 Compare December 9, 2025 07:44

linasm force-pushed the optimize-join-performance-5 branch from 1aa6598 to 06e0bf9 Compare January 6, 2026 07:07

linasm mentioned this pull request Jan 27, 2026

perf(promql): update matchedSigs to a flat map reduce memory by 97% for GROUP_LEFT #17732

Closed

[PERF] PromQL: reuse matching data structures in VectorBinop/And/Or/U…

cde7bbf

…nless Signed-off-by: Linas Medziunas <[email protected]>

linasm force-pushed the optimize-join-performance-5 branch from 06e0bf9 to cde7bbf Compare January 28, 2026 07:39

linasm requested a review from a team as a code owner January 28, 2026 07:39

vpranckaitis approved these changes Jan 29, 2026

View reviewed changes

krajorama approved these changes Feb 17, 2026

View reviewed changes

bboreham approved these changes Feb 17, 2026

View reviewed changes

Use matching.Card == parser.CardOneToOne for slice selection

a448a5c

Signed-off-by: Linas Medziunas <[email protected]>

linasm changed the title ~~[PERF] PromQL: reuse matching data structures in VectorBinop/And/Or/Unless~~ [PERF] PromQL: replace maps with slices and reuse matching data structures in VectorBinop/And/Or/Unless Feb 17, 2026

bwplotka approved these changes Feb 25, 2026

View reviewed changes

bwplotka merged commit b53d738 into prometheus:main Feb 25, 2026
34 checks passed

github-actions Bot mentioned this pull request Apr 20, 2026

Update prom/prometheus Docker tag to v3.11.0 claytono/infra#2051

Merged

1 task

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

[PERF] PromQL: replace maps with slices and reuse matching data structures in VectorBinop/And/Or/Unless#17159

[PERF] PromQL: replace maps with slices and reuse matching data structures in VectorBinop/And/Or/Unless#17159
bwplotka merged 2 commits into
prometheus:mainfrom
linasm:optimize-join-performance-5

linasm commented Sep 8, 2025 •

edited

Loading

Uh oh!

linasm commented Nov 18, 2025

Uh oh!

vpranckaitis left a comment

Uh oh!

krajorama left a comment

Uh oh!

bboreham left a comment

Uh oh!

bboreham Feb 17, 2026

Uh oh!

linasm Feb 17, 2026

Uh oh!

linasm commented Feb 17, 2026

Uh oh!

bwplotka left a comment

Uh oh!

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

6 participants

		if (len(matchedSigsPresent) > 0 && matchedSigsPresent[sigOrd]) \|\|
		(len(matchedSigs) > 0 && matchedSigs[sigOrd] != nil) {

Uh oh!

Conversation

linasm commented Sep 8, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Does this PR introduce a user-facing change?

Uh oh!

linasm commented Nov 18, 2025

Uh oh!

vpranckaitis left a comment

Choose a reason for hiding this comment

Uh oh!

krajorama left a comment

Choose a reason for hiding this comment

Uh oh!

bboreham left a comment

Choose a reason for hiding this comment

Uh oh!

bboreham Feb 17, 2026

Choose a reason for hiding this comment

Uh oh!

linasm Feb 17, 2026

Choose a reason for hiding this comment

Uh oh!

linasm commented Feb 17, 2026

Uh oh!

bwplotka left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

6 participants

linasm commented Sep 8, 2025 •

edited

Loading