@KofClubs is also working on this (or maybe the work has stalled?). Just FYI.

The Add method contains logic for processing the CounterResetHint, but the Sub method does not. Is this intentional, or could it be an oversight?

Yes, I know. (See the TODO here). I'm not sure
yet how to deal with negative counters in general (which wreaks havoc with the whole "only goes down if there is a counter reset" heuristics).

@KofClubs is also working on this (or maybe the work has stalled?). Just FYI.

I know, I guess the work has stalled as there hasn’t been activity for a long time. If that's not the case, then I'm ok to step aside and not interfere. Otherwise I'm ready to keep on

Thank you very much, I'll have a detailed look ASAP (which is probably not very soon, as I'm about to disappear into my holiday break). If anyone wants to review this in the meantime, be my guest.

I haven't heard anything from @KofClubs , so let's hope we don't have redundant work happening here.

Back from my holiday break, but swamped by the backlog. I hope I'll get to this next week.

@crush-on-anechka @beorn7

I just received an email about @crush-on-anechka 's good work. I'm sorry that I put this work on hold due to the long office hours every day:(

I shall unassign the corresponding issue.

Sorry, I caught a cold and got less done than planned. I need to ask for more patience. (And of course, if somebody else beats me to the review, be my guest.)

The Add method contains logic for processing the CounterResetHint, but the Sub method does not. Is this intentional, or could it be an oversight?

That's because I still haven't made up my mind how to treat counter resets for subtraction. I'll add that once I have an idea.

The reduceResolution function currently performs floating-point additions when merging buckets. Incorporating the Kahan summation algorithm here would add complexity but Is it worth it?

Let's not do it for now. I don't expect the counts in the merged buckets to be hugely different, and usually we'll only add a few buckets anyway.

A few more thoughts:

We currently don't do Kahan summation for the float binary + or - operator. That would require more plumbing in the PromQL engine, and I would also doubt it's terribly useful because it's unlikely to chain a lot of those operations in practical use.

Kahan summation is currently only used in certain aggregations, the corresponding "over time" functions and some specific functions. Many of those only act on float samples. The only aggregations and functions we will need Kahan summation for histograms for will be:

• sum aggregation
• avg aggregation
• sum_over_time function
• avg_over_time function

As far as I can see, we do not need KahanSub for any of those. So we actually do not need those parts.

@beorn7 thank you for the comments! I will be able to proceed in a week, if that's fine

@beorn7 I fixed the issues. I also replaced Add with KahanAdd in engine.go/aggregation and corresponding functions as you mentioned, but I'm a little bit confused with how to handle errors in adding up the accumulated receiving histogram and compensation histograms (lines 3129 and 3161) since handleAggregationError demands metricName. The solution could be to store metric name in groupedAggregation so we would have access to them, but I'm not sure.

Thanks for all the updates. I'll have a look ASAP.

Still being caught is other things. Hopefully I'll get to this before this weeks ends.

More apologies. I'm still drawn away from more substantial code reviews by other things. This is still on my list to do ASAP.

@beorn7 Thanks for the feedback! I'll analyze the information and update the PR asap

To go even further down the rabbit hole:

When reconciling zero buckets, we might be merging buckets into the zero bucket.

Even when ignoring zero buckets, we will still merge buckets if we sum up histograms of different resolution.

If we merge buckets, we add numbers. And we might need to add a very small to a very large number. So we should also use Kahan summation in this case, given that we have the compensation value available anyway.

However, now we don't add one number to another one with its compensation value, we add two numbers with each having their own compensation term. Let's say bucket b1 with c1, and bucket b2 with c2. We need to check the math, but I guess it will be something like first doing b1, c1 = kahansum.Inc(b2, b1, c1) and then c1 += c2.

For the merge between regular buckets, I guess this can easily be added to kahanReduceResolution. For the merge in case of reconciling zero buckets, it could go into the special kahanReconcileZeroBuckets hypothesized above.

@beorn7 regarding the rabbit hole - I see where you're coming from, I'll take care of it

• Removed KahanSub, cleaned up the leftover line, and added explanations for previously commented-out tests.
• Added CounterResetHint field to the compensation histogram because some tests started failing after rebasing onto the current main.
• Added an explanation for why the error returned from Add in aggregation is ignored.

histogram_avg_incremental_2:
The question why this test doesn't work stumped me. During another round of investigation, I found that it’s outcome appeared random due to the unpredictable order in which histograms are processed from the input series. The core issue was that Mul and Div operations (used in incremental average calculations) on high-magnitude floats caused rounding errors in insignificant digits which led to huge errors later on, as in our tests values are chosen to cancel each other out.
Example: intermediate values -2e+99 and 2.0000000000000002e+99, which should sum to 0, could instead produce a result of magnitude 1e86.
To fix this behavior I added RoundToSignificant() method which rounds the least significant digits of float values. It's applied only during incremental avg calculation. This fixes the high-magnitude float issues and allows histogram_avg_incremental_2 to pass.
But there are trade-offs: In certain scenarios, this rounding may slightly reduce accuracy without practical benefit.
Another edge case: averaging multiple values like 1.7976931348623157e+308 can result in +Inf when using RoundToSignificant() (without it, the calculation works correctly).
What do you think of this approach?

My spontaneous thought about the rounding: This might work out in our (artificial) test cases, where we do expect round numbers, but in general, the rounding can only reduce accuracy rather than increasing it.

It's inevitable that the accuracy of the float operations depends in their order, and we have decided so far to not go down the rabbit hole and start to reorder operations for improved accuracy (see comments), so we have to accept that the accuracy is "randomly" depending on whatever order happens to be used.

About the counter reset hint: Yes, we only recently improved the testing framework to actually check for the counter reset hint. This explains the test failures after the rebase.

You’re right, I overlooked that the main goal here is to improve accuracy. Rounding intermediate results only to make an artificial test pass is not an effective approach.
I’ve removed the rounding path, commented out the failing test, and added an explanation describing why it doesn't work. The changes were squashed into the existing commits and force-pushed.

Great. I'll give this a final look tomorrow, and then we are hopefully and finally done.

My apologies that this took so long, but I think we have learned a lot on the journey.

One final question: I appreciate your effort to keep the commits meaningful for reviewing. However, I would not like to merge the now 40 commits into main as-is. My idea is to just squash them all into one big "add Kahan summation for native histograms" commit. For example, we don't need to have the journey of adding a KahanSub and then removing it again in main. However, if you feel strongly about it, let me know and then we can check if there is a meaningful grouping of commits to do.

I’m totally fine with squashing commits into one on merge. The only reason I tried to keep them clean was to make the review easier.

I received an email saying that the CI had failed, but I decided to leave it until the morning. Happy to have it all done, thank you for all your guidance!