Add label-filter optimization for multi-metric queries

[ekpdt]

Is your feature request related to a problem? Please describe.
Today, multi-metric queries like node_used_bytes{$LABELS1} / node_total_bytes{$LABELS2} appear to fetch all the series matching the numerator and all the series fetching the denominator, even if the intersection of $LABELS1 and $LABELS2 (and therefore, result of the expression) only produces one (or a few) series. This is especially costly if either labelset is the empty set.

I've found that users tend to be quite lazy and think they can get away with only putting their label selector in one part of the query. After all, their query gives the right answer! But the query evaluation takes 10-100x longer than needed as way more data than is necessary is fetched.

Describe the solution you'd like
When the optimizer can determine in advance that one (or an intersection of more than one) labelset in the query is "controlling" on the output, it should use that labelset for lookups on all queries.

It's possible to start simple here and add sophistication over time:

• metric1{labels} (arith|comp)_binary_op metric2 -> labels is controlling
• metric1{labels1} (arith|comp)_binary_op metric2{labels2} -> a synthetic labels that combines all non-repeated keys from labels1 and labels2 is controlling.
• One step further: a key in both labels1 and labels2 is in labels as the positive-lookahead of the values from labels1 and labels2.
• This can be extended for any number of arithmetic or comparison binary operators
• This can be extended for and as well.

Describe alternatives you've considered
User training is hard and is not working consistently
There may be broader optimization work possible that could subsume this suggestion

Additional context
@siebenmann describes this problem on his blog in thoughtful detail: https://utcc.utoronto.ca/~cks/space/blog/sysadmin/PrometheusLabelNonOptimization

[pstibrany]

This is a valid issue, but one that should be fixed at Prometheus level. In your example PromQL engine asks Cortex to load samples for node_used_bytes{$LABELS1} and node_total_bytes{$LABELS2} (from given time range), without providing more context about what it is doing. I don't think Cortex can optimize this on its own.

[pracucci]

Thanks @ekimekim! I was thinking about it just last weekend. I agree there's room for improvement here, but I would like to get @beorn7 and @gouthamve opinion whether there's any good reason to not do this kind of optimisations.

This is a valid issue, but one that should be fixed at Prometheus level

Or we could parse and manipulate the query in the query-frontend.

[beorn7]

I'm in no way an expert when it comes to the Prometheus evaluation engine, but I remember this discussion from long ago. I use to answer this as: "Yeah, that would require a query planner, but Prometheus doesn't have one yet. But it could have one, if someone implemented it."

I don't see an issue specifically for this in https://github.com/prometheus/prometheus , but that doesn't necessarily mean the idea was abandoned. I'd assume it will require some fundamental changes or extensions to the query engine that are way more involved than the simple description of the optimization in this issue suggests (but it would probably unlock a whole lot of similar optimizations). If someone intends to tackle this optimization, I'd recommend to introduce the idea on the developer mailing list https://groups.google.com/forum/#!forum/prometheus-developers , where any other known issues that I might not be aware of will be pointed out by others.

[ekimekim]

Thanks @ekimekim!

You're welcome, but I think you meant @ekpdt :P

[gouthamve]

I don't think Cortex can optimize this on its own.

I think we can rewrite the PromQL in the frontend to do this. See also prometheus/prometheus#8053

[bboreham]

Wild idea to get a query-optimizer:
Embed SQLite, create a row per series, translate the PromQL labels into a SQL SELECT, then the SQLite query optimizer will tell you which series you need.