PromQL: Improve space complexity by streaming more; avoid series pre-lookup.

[bwplotka]

Hi 👋

While changing SeriesSet interfaces, we found with @brian-brazil that our usage of SerieSet in PromQL might cause extra unnecessary allocations for certain implementations and cases. Let me describe the problem in two diagrams:

Current PromQL logic for Range Query with Metric Selection:

Google Draw Link

All function names should match the current master: https://github.com/prometheus/prometheus/tree/18d9ebf0ffc26b8bd0e136f552c8e9886d29ade4

Issues:

Google Draw Link

Problem: We are accumulating all series first, to gather all iterators.

With the current interfaces (StoreSet, Remote Read, Thanos StoreAPI) “Series by Series” means that we stream Series labels together with labels.

Current Flow Issues:

1. To finish this eval PromQL stage, we have to buffer & receive all data. Especially for remote data & Thanos, this means literally all. (: Realistic space complexity is now O(2 * series * chunks), for the biggest result, so ~ O(2 series * chunks) B
2. Current space complexity is also not great further with multi arg functions, as we build a hash map. For large cardinality queries, we end up hashing millions of Series potentially.

Solution: Stream more!

The idea would be to follow really exactly the same algorithm as everywhere else (vertical dedup, merge series etc): Implement Heap / MergeSort that will iterate over "sorted" series from two SeriesSets.

• Open Question: Good point that @brian-brazil mentioned, was that we don't know then how big matrix we should allocate. I wonder if we can workaround this somehow. To me it sounds we don't really want to operate on matrixes at all, rather on top two series from each SeriesSets... 🤔

This sounds like a big task but really needed, especially for Thanos community. Even with the work we are doing to make PromQL more concurrent for Prometheus Ecosystem (#6878), this issue might be impacting resource (memory) consumption significantly, especially for concurrent runs. I am happy to do this at some point, but I won't have time in near ~2weeks for this. so.. help wanted (:

Any feedback on this to make it easier to improve this? (: cc @slrtbtfs @brian-brazil @brancz @kakkoyun @cstyan @tomwilkie @gouthamve @cstyan

[brian-brazil]

This is actually quite a small change in removing the Expand from CheckAndExpand. It's really just cleanup from the big reworking of promql I did a few years back.

Current space complexity is also not great further with multi arg functions, as we build a hash map. For large cardinality queries, we end up hashing millions of Series potentially.

I don't see how this is related to what's being discussed here. Hashing is cheap, and we'll need to do it anyway.

I'm not sure why you've marked this as a P1 feature. It's a small performance thing that's not really something user visible, and it's not urgent. It's a P3 cleanup or enhancement.

[bwplotka]

Happy to hear it's easy =D let's try it out then.

[allenmqcymp]

Hi there, first time contributor looking to help with low hanging-fruit issues. Could someone point me to the relevant code files so I can better understand the issue?

[brian-brazil]

Basically in

prometheus/promql/engine.go

Line 728 in 933aa36

func checkAndExpandSeriesSet(ctx context.Context, expr parser.Expr) (storage.Warnings, error) {

we should not be expanding the whole series in advance - that should happen during evaluation one series at a time.

[allenmqcymp]

Hi, sorry for the inactivity. I would still like to pick this issue up. Currently looking through how engine.go works, is there any good documentation about the internals of the PromQL engine?

My current understanding of the issue is that it is inefficient to gather all the series data before rangeEval. I am still unsure of what the proposed fix might involve. Could someone please enlighten?

Thanks!

[brian-brazil]

I'm not sure there's much in general docs.

Could someone please enlighten?

In essence eliminate ExpandSeriesSet, and then fix up anything that breaks due to that. The only place things will happen to be fully expanded is subqueries, as that's what the output is.

[aryan9600]

Hey everyone, a first time contributor here. I would like to work on this issue if no one else is already working on it.

Having gone through this issue and some of the related code, I have a few doubts I was hoping to get cleared.

As far as I understand, we want to avoid using checkAndExpandSeriesSet and consequently expandSeriesSet in eval().
If we don't expand the SeriesSet, how do we get access to the iterator of each Series in order to use the buffer? Also how do we determine the length of our output matrix?

Unfortunately, @bwplotka's solution regarding Heap/MergeSort and streaming more made little sense to me, so it would be great if someone could elaborate on that.

Thanks!

[brian-brazil]

how do we get access to the iterator of each Series in order to use the buffer?

We do it as needed one by one, rather than in one big batch.

[aryan9600]

We do it as needed one by one.

I think I understand the issue, but can't really seem to get a grasp on the solution. Where exactly do we determine that we need to move to the next Series?

[brian-brazil]

Anywhere we iterate over the slice today, instead we call next.

[aryan9600]

Sorry for the inactivity, I have been trying to work on a patch, but can't get a few tests to pass (almost all of them pass), specifically some in functions.test and subquery.test. I replaced all for loops iterating over the slice, with a for loop which would expand the SeriesSet during eval time, but due to this a few Matrices (and consequently Vectors) are coming up empty, due to this change, and I can't really seem to figure out why exactly. Would you have any idea as to why this change would result in this error? Thanks :)

[brian-brazil]

That's a bit weird, can you make a PR so we can have a look?

[sthaha]

@bwplotka @brian-brazil , assuming the issue still exists, I would love to take a crack at this if @aryan9600 isn't keen on progressing with #8009

[bwplotka]

Totally, go for it. It's still available, but benchmarks might be necessary to assess results

[bwplotka]

Just to give status on it.

It's still needed for Thanos and (and potentially Cortex purposes). See: thanos-io/thanos#4780

Looks like @darshanime did a good job on this with #9071, so we can close #8009 (thanks for your hard initial work @aryan9600 !).

[keremgocen]

happy to take a look or collab if no one else is on it

[beorn7]

Hello from the bug scrub.

@bwplotka , our impression is that this is not required anymore (since #9071 was closed as "not required anymore"). Could you confirm? Please close if that's the case.

[bwplotka]

Correct, not needed anymore, we can reopen if there will be a need!