MQE: initial implementation of common subexpression elimination #11189
Conversation
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
|
💻 Deploy preview deleted. |
18942bc to
3fda6ae
Compare
3fda6ae to
1a81f9e
Compare
jhesketh
reviewed
Apr 16, 2025
pkg/streamingpromql/optimize/plan/commonsubexpressionelimination/node.go
Show resolved
Hide resolved
pkg/streamingpromql/optimize/plan/commonsubexpressionelimination/operator.go
Outdated
Show resolved
Hide resolved
pkg/streamingpromql/optimize/plan/commonsubexpressionelimination/operator.go
Show resolved
Hide resolved
pkg/streamingpromql/optimize/plan/commonsubexpressionelimination/operator.go
Outdated
Show resolved
Hide resolved
pkg/streamingpromql/optimize/plan/commonsubexpressionelimination/optimization_pass.go
Show resolved
Hide resolved
pkg/streamingpromql/optimize/plan/commonsubexpressionelimination/series_data_ring_buffer.go
Outdated
Show resolved
Hide resolved
pkg/streamingpromql/optimize/plan/commonsubexpressionelimination/series_data_ring_buffer.go
Show resolved
Hide resolved
… query planning is enabled
…thout query planner enabled
…pression can be reached from different leaf nodes
…rrectly deduplicated
052def7 to
8e35d43
Compare
jhesketh
approved these changes
Apr 30, 2025
There was a problem hiding this comment.
lgtm, but a nit on the naming of the new metric.
Perhaps in the future we can also consider replacing the active query tracking with something that can hold the state of the query (eg planning, executing, etc), instead of needing to add a comment at the end of it. That would also remove the race for when the query is removed and readded to the tracker.
This is a good point - I'll tackle this separately. |
This comment has been minimized.
This comment has been minimized.
|
😢 zizmor failed with exit code 13. Expand for full output |
1 task
1 task
charleskorn
added a commit
that referenced
this pull request
Jun 24, 2025
…imestamp()` produce incorrect results (#11830) #### What this PR does This PR fixes an issue in common subexpression elimination where an expression like `timestamp(foo_time) - foo_time` would produce incorrect results. This happens because the instant vector selector is incorrectly deduplicated in this case: at present, the instant vector selector operator behaves differently if it is wrapped in `timestamp()`, but the query planner did not take this into consideration when identifying duplicate expressions. A future improvement would be to allow the instant vector selector operator to return both the sample value and sample timestamp to different consumers, but given queries like this are rare, I've opted for the simpler approach. #### Which issue(s) this PR fixes or relates to #11189 #### Checklist - [x] Tests updated. - [n/a] Documentation added. - [covered by #10067] `CHANGELOG.md` updated - the order of entries should be `[CHANGE]`, `[FEATURE]`, `[ENHANCEMENT]`, `[BUGFIX]`. If changelog entry is not needed, please add the `changelog-not-needed` label to the PR. - [n/a] [`about-versioning.md`](https://github.com/grafana/mimir/blob/main/docs/sources/mimir/configure/about-versioning.md) updated with experimental features.
mimir-github-bot bot
pushed a commit
that referenced
this pull request
Jun 24, 2025
…imestamp()` produce incorrect results (#11830) #### What this PR does This PR fixes an issue in common subexpression elimination where an expression like `timestamp(foo_time) - foo_time` would produce incorrect results. This happens because the instant vector selector is incorrectly deduplicated in this case: at present, the instant vector selector operator behaves differently if it is wrapped in `timestamp()`, but the query planner did not take this into consideration when identifying duplicate expressions. A future improvement would be to allow the instant vector selector operator to return both the sample value and sample timestamp to different consumers, but given queries like this are rare, I've opted for the simpler approach. #### Which issue(s) this PR fixes or relates to #11189 #### Checklist - [x] Tests updated. - [n/a] Documentation added. - [covered by #10067] `CHANGELOG.md` updated - the order of entries should be `[CHANGE]`, `[FEATURE]`, `[ENHANCEMENT]`, `[BUGFIX]`. If changelog entry is not needed, please add the `changelog-not-needed` label to the PR. - [n/a] [`about-versioning.md`](https://github.com/grafana/mimir/blob/main/docs/sources/mimir/configure/about-versioning.md) updated with experimental features. (cherry picked from commit dd17406)
1 task
charleskorn
added a commit
that referenced
this pull request
Jun 29, 2025
…ith multiple children, and add metric on number of selectors eliminated (#11879) #### What this PR does This PR makes two changes to common subexpression elimination: * Tests: I was worried we weren't handling the case where a expression has multiple children correctly, so added some tests to check. Turns out this case is OK, but I think it'd be valuable to retain so it's not broken in the future. * Metric: the existing `cortex_mimir_query_engine_common_subexpression_elimination_duplication_nodes_introduced` metric is useful for gauging the impact of CSE, but doesn't tell us how much load on ingesters and store-gateways we've avoided. The new metric tells us the number of selectors eliminated and therefore gives us a better idea of the number of avoided ingester and store-gateway requests. #### Which issue(s) this PR fixes or relates to #11189 #### Checklist - [x] Tests updated. - [n/a] Documentation added. - [covered by #10067] `CHANGELOG.md` updated - the order of entries should be `[CHANGE]`, `[FEATURE]`, `[ENHANCEMENT]`, `[BUGFIX]`. If changelog entry is not needed, please add the `changelog-not-needed` label to the PR. - [n/a] [`about-versioning.md`](https://github.com/grafana/mimir/blob/main/docs/sources/mimir/configure/about-versioning.md) updated with experimental features.
Merged
1 task
charleskorn
added a commit
that referenced
this pull request
Jul 7, 2025
… incorrect results (#11989) #### What this PR does This PR fixes an issue where common subexpression elimination (CSE) can cause a query to return incorrect query results. The issue would occur if the ring buffer used to buffer data was in a state where the head of the buffer is at the end of the slice, and the tail was at the beginning of the slice. In this case, calling `Remove` for the item at the end of the slice would return the correct value, as would the subsequent call for the item at the beginning of the slice, but all following calls would return incorrect values. #### Which issue(s) this PR fixes or relates to #11189 #### Checklist - [x] Tests updated. - [n/a] Documentation added. - [covered by #10067] `CHANGELOG.md` updated - the order of entries should be `[CHANGE]`, `[FEATURE]`, `[ENHANCEMENT]`, `[BUGFIX]`. If changelog entry is not needed, please add the `changelog-not-needed` label to the PR. - [n/a] [`about-versioning.md`](https://github.com/grafana/mimir/blob/main/docs/sources/mimir/configure/about-versioning.md) updated with experimental features.
mimir-github-bot bot
pushed a commit
that referenced
this pull request
Jul 7, 2025
… incorrect results (#11989) #### What this PR does This PR fixes an issue where common subexpression elimination (CSE) can cause a query to return incorrect query results. The issue would occur if the ring buffer used to buffer data was in a state where the head of the buffer is at the end of the slice, and the tail was at the beginning of the slice. In this case, calling `Remove` for the item at the end of the slice would return the correct value, as would the subsequent call for the item at the beginning of the slice, but all following calls would return incorrect values. #### Which issue(s) this PR fixes or relates to #11189 #### Checklist - [x] Tests updated. - [n/a] Documentation added. - [covered by #10067] `CHANGELOG.md` updated - the order of entries should be `[CHANGE]`, `[FEATURE]`, `[ENHANCEMENT]`, `[BUGFIX]`. If changelog entry is not needed, please add the `changelog-not-needed` label to the PR. - [n/a] [`about-versioning.md`](https://github.com/grafana/mimir/blob/main/docs/sources/mimir/configure/about-versioning.md) updated with experimental features. (cherry picked from commit 8c9ffff)
mimir-github-bot bot
pushed a commit
that referenced
this pull request
Jul 7, 2025
… incorrect results (#11989) #### What this PR does This PR fixes an issue where common subexpression elimination (CSE) can cause a query to return incorrect query results. The issue would occur if the ring buffer used to buffer data was in a state where the head of the buffer is at the end of the slice, and the tail was at the beginning of the slice. In this case, calling `Remove` for the item at the end of the slice would return the correct value, as would the subsequent call for the item at the beginning of the slice, but all following calls would return incorrect values. #### Which issue(s) this PR fixes or relates to #11189 #### Checklist - [x] Tests updated. - [n/a] Documentation added. - [covered by #10067] `CHANGELOG.md` updated - the order of entries should be `[CHANGE]`, `[FEATURE]`, `[ENHANCEMENT]`, `[BUGFIX]`. If changelog entry is not needed, please add the `changelog-not-needed` label to the PR. - [n/a] [`about-versioning.md`](https://github.com/grafana/mimir/blob/main/docs/sources/mimir/configure/about-versioning.md) updated with experimental features. (cherry picked from commit 8c9ffff)
mimir-github-bot bot
pushed a commit
that referenced
this pull request
Jul 7, 2025
… incorrect results (#11989) #### What this PR does This PR fixes an issue where common subexpression elimination (CSE) can cause a query to return incorrect query results. The issue would occur if the ring buffer used to buffer data was in a state where the head of the buffer is at the end of the slice, and the tail was at the beginning of the slice. In this case, calling `Remove` for the item at the end of the slice would return the correct value, as would the subsequent call for the item at the beginning of the slice, but all following calls would return incorrect values. #### Which issue(s) this PR fixes or relates to #11189 #### Checklist - [x] Tests updated. - [n/a] Documentation added. - [covered by #10067] `CHANGELOG.md` updated - the order of entries should be `[CHANGE]`, `[FEATURE]`, `[ENHANCEMENT]`, `[BUGFIX]`. If changelog entry is not needed, please add the `changelog-not-needed` label to the PR. - [n/a] [`about-versioning.md`](https://github.com/grafana/mimir/blob/main/docs/sources/mimir/configure/about-versioning.md) updated with experimental features. (cherry picked from commit 8c9ffff)
mimir-github-bot bot
pushed a commit
that referenced
this pull request
Jul 7, 2025
… incorrect results (#11989) #### What this PR does This PR fixes an issue where common subexpression elimination (CSE) can cause a query to return incorrect query results. The issue would occur if the ring buffer used to buffer data was in a state where the head of the buffer is at the end of the slice, and the tail was at the beginning of the slice. In this case, calling `Remove` for the item at the end of the slice would return the correct value, as would the subsequent call for the item at the beginning of the slice, but all following calls would return incorrect values. #### Which issue(s) this PR fixes or relates to #11189 #### Checklist - [x] Tests updated. - [n/a] Documentation added. - [covered by #10067] `CHANGELOG.md` updated - the order of entries should be `[CHANGE]`, `[FEATURE]`, `[ENHANCEMENT]`, `[BUGFIX]`. If changelog entry is not needed, please add the `changelog-not-needed` label to the PR. - [n/a] [`about-versioning.md`](https://github.com/grafana/mimir/blob/main/docs/sources/mimir/configure/about-versioning.md) updated with experimental features. (cherry picked from commit 8c9ffff)
mimir-github-bot bot
pushed a commit
that referenced
this pull request
Jul 7, 2025
… incorrect results (#11989) #### What this PR does This PR fixes an issue where common subexpression elimination (CSE) can cause a query to return incorrect query results. The issue would occur if the ring buffer used to buffer data was in a state where the head of the buffer is at the end of the slice, and the tail was at the beginning of the slice. In this case, calling `Remove` for the item at the end of the slice would return the correct value, as would the subsequent call for the item at the beginning of the slice, but all following calls would return incorrect values. #### Which issue(s) this PR fixes or relates to #11189 #### Checklist - [x] Tests updated. - [n/a] Documentation added. - [covered by #10067] `CHANGELOG.md` updated - the order of entries should be `[CHANGE]`, `[FEATURE]`, `[ENHANCEMENT]`, `[BUGFIX]`. If changelog entry is not needed, please add the `changelog-not-needed` label to the PR. - [n/a] [`about-versioning.md`](https://github.com/grafana/mimir/blob/main/docs/sources/mimir/configure/about-versioning.md) updated with experimental features. (cherry picked from commit 8c9ffff)
mimir-github-bot bot
pushed a commit
that referenced
this pull request
Jul 7, 2025
… incorrect results (#11989) #### What this PR does This PR fixes an issue where common subexpression elimination (CSE) can cause a query to return incorrect query results. The issue would occur if the ring buffer used to buffer data was in a state where the head of the buffer is at the end of the slice, and the tail was at the beginning of the slice. In this case, calling `Remove` for the item at the end of the slice would return the correct value, as would the subsequent call for the item at the beginning of the slice, but all following calls would return incorrect values. #### Which issue(s) this PR fixes or relates to #11189 #### Checklist - [x] Tests updated. - [n/a] Documentation added. - [covered by #10067] `CHANGELOG.md` updated - the order of entries should be `[CHANGE]`, `[FEATURE]`, `[ENHANCEMENT]`, `[BUGFIX]`. If changelog entry is not needed, please add the `changelog-not-needed` label to the PR. - [n/a] [`about-versioning.md`](https://github.com/grafana/mimir/blob/main/docs/sources/mimir/configure/about-versioning.md) updated with experimental features. (cherry picked from commit 8c9ffff)
2 tasks
charleskorn
added a commit
that referenced
this pull request
Aug 1, 2025
…12236) #### What this PR does In #11189, we added common subexpression elimination (CSE) to MQE's query planner. However, this only supported expressions that produced instant vectors - so this would apply to expressions like `sum(foo)` in `sum(foo) + sum(foo)` or `rate(foo[5m])` in `rate(foo[5m]) + rate(foo[5m])`. In this PR, I'm adding support for expressions that produce range vectors, provided the parent query is an instant query. For example, CSE will now apply to `foo[5m]` in `sum_over_time(foo[5m]) / count_over_time(foo[5m])`. I've limited this to instant queries for the time being as supporting range queries adds a lot of complexity. The vast majority of queries we see in production Mimir clusters are instant queries from rules, so we get most of the benefit without the extra complexity. Benchmarks show a 40-50% latency improvement for affected queries, albeit at the cost of higher peak memory consumption due to the buffering required, similar to what we see for instant vector expressions: ``` goos: darwin goarch: arm64 pkg: github.com/grafana/mimir/pkg/streamingpromql/benchmarks cpu: Apple M1 Pro │ before.txt │ after.txt │ │ sec/op │ sec/op vs base │ Query/sum(sum_over_time(a_1[1m]))_/_sum(count_over_time(a_1[1m])),_instant_query/engine=Mimir-10 274.1µ ± 1% 152.4µ ± 1% -44.41% (p=0.002 n=6) Query/sum(sum_over_time(a_100[1m]))_/_sum(count_over_time(a_100[1m])),_instant_query/engine=Mimir-10 838.4µ ± 2% 495.7µ ± 0% -40.87% (p=0.002 n=6) Query/sum(sum_over_time(a_2000[1m]))_/_sum(count_over_time(a_2000[1m])),_instant_query/engine=Mimir-10 8.555m ± 1% 5.356m ± 0% -37.40% (p=0.002 n=6) Query/sum(sum_over_time(a_1[1d]))_/_sum(count_over_time(a_1[1d])),_instant_query/engine=Mimir-10 1136.0µ ± 1% 606.9µ ± 2% -46.58% (p=0.002 n=6) Query/sum(sum_over_time(a_100[1d]))_/_sum(count_over_time(a_100[1d])),_instant_query/engine=Mimir-10 68.34m ± 1% 36.16m ± 2% -47.09% (p=0.002 n=6) Query/sum(sum_over_time(a_2000[1d]))_/_sum(count_over_time(a_2000[1d])),_instant_query/engine=Mimir-10 1306.9m ± 0% 666.7m ± 1% -48.98% (p=0.002 n=6) │ before.txt │ after.txt │ │ B │ B vs base │ Query/sum(sum_over_time(a_1[1m]))_/_sum(count_over_time(a_1[1m])),_instant_query/engine=Mimir-10 56.76Mi ± 1% 56.53Mi ± 0% ~ (p=0.223 n=6) Query/sum(sum_over_time(a_100[1m]))_/_sum(count_over_time(a_100[1m])),_instant_query/engine=Mimir-10 56.73Mi ± 1% 56.52Mi ± 1% ~ (p=0.509 n=6) Query/sum(sum_over_time(a_2000[1m]))_/_sum(count_over_time(a_2000[1m])),_instant_query/engine=Mimir-10 58.97Mi ± 1% 59.06Mi ± 1% ~ (p=0.420 n=6) Query/sum(sum_over_time(a_1[1d]))_/_sum(count_over_time(a_1[1d])),_instant_query/engine=Mimir-10 62.27Mi ± 1% 62.34Mi ± 1% ~ (p=0.554 n=6) Query/sum(sum_over_time(a_100[1d]))_/_sum(count_over_time(a_100[1d])),_instant_query/engine=Mimir-10 69.50Mi ± 3% 116.27Mi ± 3% +67.30% (p=0.002 n=6) Query/sum(sum_over_time(a_2000[1d]))_/_sum(count_over_time(a_2000[1d])),_instant_query/engine=Mimir-10 75.62Mi ± 4% 430.17Mi ± 0% +468.88% (p=0.002 n=6) ``` Benchmarks show no noticable impact for the existing instant vector implementation due to making `SeriesDataRingBuffer` generic. #### Which issue(s) this PR fixes or relates to #11189 #### Checklist - [x] Tests updated. - [n/a] Documentation added. - [x] `CHANGELOG.md` updated - the order of entries should be `[CHANGE]`, `[FEATURE]`, `[ENHANCEMENT]`, `[BUGFIX]`. If changelog entry is not needed, please add the `changelog-not-needed` label to the PR. - [n/a] [`about-versioning.md`](https://github.com/grafana/mimir/blob/main/docs/sources/mimir/configure/about-versioning.md) updated with experimental features.
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.
This suggestion is invalid because no changes were made to the code.
Suggestions cannot be applied while the pull request is closed.
Suggestions cannot be applied while viewing a subset of changes.
Only one suggestion per line can be applied in a batch.
Add this suggestion to a batch that can be applied as a single commit.
Applying suggestions on deleted lines is not supported.
You must change the existing code in this line in order to create a valid suggestion.
Outdated suggestions cannot be applied.
This suggestion has been applied or marked resolved.
Suggestions cannot be applied from pending reviews.
Suggestions cannot be applied on multi-line comments.
Suggestions cannot be applied while the pull request is queued to merge.
Suggestion cannot be applied right now. Please check back later.
What this PR does
This PR implements common subexpression elimination in MQE.
Prior to this PR, when given an expression like
sum(foo) / (sum(foo) + sum(bar)), MQE would evaluatesum(foo)twice. This is not necessary: we can instead computesum(foo)once and use the result in both places, and that's what this PR implements.This improves overall query performance, and also saves CPU time in queriers, ingesters and store-gateways. However, the drawback is that queriers must buffer unused parts of common results until they are consumed by all places that need them. For queries where the size of the common result is small, this is not an issue, but in other cases this can increase the peak memory consumption of queries significantly.
This could be addressed somewhat by consuming from both sides of binary operations concurrently, but this is out of scope for this PR - for now, given the substantial performance improvements and relative cost of CPU and memory, we can provision more memory for queriers if needed. In any case, query memory consumption will be no worse than Prometheus' engine.
Benchmark results
Overall, latency improves roughly in line with the ratio of eliminated selectors to original selectors. (For example, if there were two selectors originally, and they're both the same, then latency improves around 50%, or if there were three selectors and two are the same, then latency improves around 33%.)
Which issue(s) this PR fixes or relates to
(none)
Checklist
CHANGELOG.mdupdated - the order of entries should be[CHANGE],[FEATURE],[ENHANCEMENT],[BUGFIX].about-versioning.mdupdated with experimental features.