Calculate sum in Kahan summation algorithm in aggregations (#27807) by liketic · Pull Request #27848 · elastic/elasticsearch

liketic · 2017-12-16T08:22:08Z

Currently, when computing sum of double values in aggregators, all values are summed up in naive summation. Kahan summation is a compensated summation algorithm which is more accurate for double values. However for NaN and infinities, Kahan summation will not get the same result as naive summation.

Closes #27807

…7807)

elasticmachine · 2017-12-16T08:22:10Z

Since this is a community submitted pull request, a Jenkins build has not been kicked off automatically. Can an Elastic organization member please verify the contents of this patch and then kick off a build manually?

jpountz

I left some comments to the avg aggregation that applies to other aggregations as well. It looks good to me. I think we should also modify the InternalSum, InternalAvg, ... aggregations to store the compensation as well, so that merging sums that come from multiple shards retains more accuracy. Finally I think we need to modify the extended stats aggregation as well?

jpountz · 2017-12-17T19:38:47Z

core/src/main/java/org/elasticsearch/search/aggregations/metrics/avg/AvgAggregator.java

    DoubleArray sums;
    DocValueFormat format;

+    private DoubleArray compensations;


please declare it next to sums and using the same modifiers

jpountz · 2017-12-17T19:39:43Z

core/src/main/java/org/elasticsearch/search/aggregations/metrics/avg/AvgAggregator.java

+                        double corrected = values.nextValue() - compensation;
+                        double newSum = sum + corrected;
+                        compensation = (newSum - sum) - corrected;
+                        sum = newSum;


can you add a comment saying this is Kahan summation?

Thanks @jpountz . I pushed 6c45e08

…tors

liketic · 2017-12-19T03:33:47Z

core/src/test/java/org/elasticsearch/search/aggregations/metrics/InternalSumTests.java

+        }
+        assertEquals(expectedSum, reduced.getValue(), 0.000d);
+    }
+


Why I have to modify this test case is because if there is a Double.NEGATIVE_INFINITY in the values to sum, Kahan summation with get Double.NaN, and naive summation will get Double.NEGATIVE_INFINITY, I'm not sure if this use case should be supported.

We started rejecting this on new indices recently, but old indices might still have infinities. I think we should have special handling for these values in the aggregators?

I pushed 15cdec2

elasticmachine · 2018-01-01T14:18:45Z

Since this is a community submitted pull request, a Jenkins build has not been kicked off automatically. Can an Elastic organization member please verify the contents of this patch and then kick off a build manually?

jpountz

Thank you, this looks almost good to me. I left some minor comments on the avg aggregation that apply to other aggs as well. Could you also add some tests for the Infinity/NaN corner-cases, including things like summing up a few finite doubles that are so large that the sum is infinite?

jpountz · 2018-01-02T14:10:06Z

core/src/main/java/org/elasticsearch/search/aggregations/metrics/avg/AvgAggregator.java

                    for (int i = 0; i < valueCount; i++) {
-                        sum += values.nextValue();
+                        double value = values.nextValue();
+                        if (Double.isNaN(value) || Double.isInfinite(value)) {


We could test both at once by doing Double.isFinite(value) == false?

Yes, it's much better.

jpountz · 2018-01-02T14:10:35Z

core/src/main/java/org/elasticsearch/search/aggregations/metrics/avg/AvgAggregator.java

+                            sum += value;
+                            if (Double.isNaN(sum))
+                                break;
+                        } else if (Double.isFinite(sum)) {


this is always true I think? So we could make it an else block?

The check statement is needed. For example when summing up [Double.POSITIVE_INFINITY, 1, 2, 3], if no this check, we'll got NaN, and we expect Double.POSITIVE_INFINITY here.

jpountz · 2018-01-02T14:11:04Z

core/src/main/java/org/elasticsearch/search/aggregations/metrics/avg/AvgAggregator.java

+                        double value = values.nextValue();
+                        if (Double.isNaN(value) || Double.isInfinite(value)) {
+                            sum += value;
+                            if (Double.isNaN(sum))


I would not try to break once the sum is NaN, this doesn't bring much imo

jpountz · 2018-01-02T14:15:29Z

core/src/main/java/org/elasticsearch/search/aggregations/metrics/avg/InternalAvg.java

-            sum += ((InternalAvg) aggregation).sum;
+            InternalAvg avg = (InternalAvg) aggregation;
+            count += avg.count;
+            if (Double.isNaN(sum) == false) {


I would remove this if statement to keep things simple?

Make sense.

liketic · 2018-01-03T11:26:24Z

Hi @jpountz Thanks for your comments. They're really useful to me. 👍 When I trying to add test case for some corner cases for SumAggregator, I found for negative values, the result is wired. For example in SumAggregatorTests, I made some documents contains a negative value:

        testCase(new MatchAllDocsQuery(),
            iw -> {
                for (int i = 0; i < 10; i++) {
                    iw.addDocument(singleton(new DoubleDocValuesField(FIELD_NAME, -1)));
                }
            },
            result -> assertEquals(-10, result.getValue(), TOLERANCE),
            NumberFieldMapper.NumberType.DOUBLE
        );

The result of result.getValue() is -39.99999999999999. I'm not really understand how the result computed, but obviously, it's not the sum of value in all documents. Where can I find some useful information about the internal logic? Thanks in advance.

jpountz · 2018-01-12T15:03:28Z

Sorry for the long time with no response. I just fetched your code, and this is due to the fact that you use DoubleDocValuesField, which Lucene provides for single-valued fields. Yet in Elasticsearch all fields can be multi-valued, so you should replace it with new NumericDocValuesField(FIELD_NAME, NumericUtils.doubleToSortableLong(-1)). Without going into too much details, this helps guarantee that values are stored in ascending order in case a field is multi-valued, which some aggregations and sort options rely on.

…o feature/issues/27807

liketic · 2018-01-16T07:06:53Z

@jpountz Thanks for your help. It's really helped me a lot. I pushed 176be1f to add more test cases. Thanks very much!

jpountz

I think I found one corner case, but other than that, it looks good to me!

jpountz · 2018-01-16T08:56:52Z

server/src/main/java/org/elasticsearch/search/aggregations/metrics/avg/AvgAggregator.java

+                            double newSum = sum + corrected;
+                            compensation = (newSum - sum) - corrected;
+                            sum = newSum;
+                        }


I think one corner-case is not covered with this logic. Imagine that all values are finite but 2: -Inf and +Inf, for instance:
[+Inf, 4, -Inf]. The expected result is NaN but your logic will make it return +Inf if I'm not mistaken. Maybe this should be something like that instead:

if (Double.isFinite(value) == false || Double.isFinite(sum) == false) { sum += value; } else { // kahan summation }

Hi @jpountz Thanks a lot! I made a test for both of them:

double sum = 0; double compensation = 0; double[] values = new double[]{Double.POSITIVE_INFINITY, 4, Double.NEGATIVE_INFINITY}; for (int i = 0; i < values.length; i++) { double value = values[i]; if (Double.isFinite(value) == false) { sum += value; } else if (Double.isFinite(sum)) { double corrected = value - compensation; double newSum = sum + corrected; compensation = (newSum - sum) - corrected; sum = newSum; } } System.out.println(sum); sum = 0; compensation = 0; for (int i = 0; i < values.length; i++) { double value = values[i]; if (Double.isFinite(value) == false || Double.isFinite(sum) == false) { sum += value; } else { double corrected = value - compensation; double newSum = sum + corrected; compensation = (newSum - sum) - corrected; sum = newSum; } } System.out.println(sum);

Both of their result are NaN. Because in my code, for each value, if it's not finite, it will be summed up to sum, no matter what sum is. I can also made this change because I also think your way is more intuitive. I also have a random test case for this kind corner-case:

int n = randomIntBetween(5, 10); values = new double[n]; double sum = 0; for (int i = 0; i < n; i++) { values[i] = frequently() ? randomFrom(Double.NaN, Double.NEGATIVE_INFINITY, Double.POSITIVE_INFINITY) : randomDoubleBetween(Double.MIN_VALUE, Double.MAX_VALUE, true); sum += values[i]; } verifyAvgOfDoubles(values, sum / n, 1e-10);

I can make it be regular for example:

double[] values = new double[]{Double.POSITIVE_INFINITY, 4, Double.NEGATIVE_INFINITY}; verifyAvgOfDoubles(values, NaN, 0d);

WDYT?

I had misread your code, sorry! I am fine either way.

Let's keep things the way they are.

jpountz · 2018-01-16T10:27:49Z

@elasticmachine please test it

…27848)

* master: Trim down usages of `ShardOperationFailedException` interface (#28312) Do not return all indices if a specific alias is requested via get aliases api. [Test] Lower bwc version for rank-eval rest tests CountedBitSet doesn't need to extend BitSet. (#28239) Calculate sum in Kahan summation algorithm in aggregations (#27807) (#27848) Remove the `update_all_types` option. (#28288) Add information when master node left to DiscoveryNodes' shortSummary() (#28197) Provide explanation of dangling indices, fixes #26008 (#26999)

* 6.x: Trim down usages of `ShardOperationFailedException` interface (#28312) Clean up commits when global checkpoint advanced (#28140) Do not return all indices if a specific alias is requested via get aliases api. CountedBitSet doesn't need to extend BitSet. (#28239) Calculate sum in Kahan summation algorithm in aggregations (#27807) (#27848)

* master: (94 commits) Completely remove Painless Type from AnalyzerCaster in favor of Java Class. (elastic#28329) Fix spelling error Reindex: Wait for deletion in test Reindex: log more on rare test failure Ensure we protect Collections obtained from scripts from self-referencing (elastic#28335) [Docs] Fix asciidoc style in composite agg docs Adds the ability to specify a format on composite date_histogram source (elastic#28310) Provide a better error message for the case when all shards failed (elastic#28333) [Test] Re-Add integer_range and date_range field types for query builder tests (elastic#28171) Added Put Mapping API to high-level Rest client (elastic#27869) Revert change that does not return all indices if a specific alias is requested via get alias api. (elastic#28294) Painless: Replace Painless Type with Java Class during Casts (elastic#27847) Notify affixMap settings when any under the registered prefix matches (elastic#28317) Trim down usages of `ShardOperationFailedException` interface (elastic#28312) Do not return all indices if a specific alias is requested via get aliases api. [Test] Lower bwc version for rank-eval rest tests CountedBitSet doesn't need to extend BitSet. (elastic#28239) Calculate sum in Kahan summation algorithm in aggregations (elastic#27807) (elastic#27848) Remove the `update_all_types` option. (elastic#28288) Add information when master node left to DiscoveryNodes' shortSummary() (elastic#28197) ...

Calculate sum in Kahan summation algorithm in aggregations (elastic#2…

30f7228

…7807)

jpountz suggested changes Dec 17, 2017

View reviewed changes

Compute summation with Kahan summation algorithm for internal aggrega…

6c45e08

…tors

liketic commented Dec 19, 2017

View reviewed changes

liketic added 2 commits December 31, 2017 16:36

Merge remote-tracking branch 'upstream/master' into feature/issues/27807

95aff79

Properly calculate sum of NaN and infinities

15cdec2

jpountz reviewed Jan 2, 2018

View reviewed changes

Simplify summing up algorithm for aggregations

1f07cca

liketic force-pushed the feature/issues/27807 branch from af772c4 to 1f07cca Compare January 3, 2018 11:09

mayya-sharipova added :Analytics/Aggregations Aggregations >feature labels Jan 4, 2018

liketic added 3 commits January 15, 2018 18:58

Merge remote-tracking branch 'upstream/master' into feature/issues/27807

594f750

Merge branch 'master' of https://github.com/elastic/elasticsearch int…

b2ce7cb

…o feature/issues/27807

Add test case for summing up NaN and infinities

176be1f

liketic force-pushed the feature/issues/27807 branch from b6f5984 to 176be1f Compare January 16, 2018 07:03

jpountz reviewed Jan 16, 2018

View reviewed changes

jpountz approved these changes Jan 16, 2018

View reviewed changes

jpountz added v7.0.0 v6.3.0 labels Jan 22, 2018

jpountz merged commit 452c36c into elastic:master Jan 22, 2018

jpountz pushed a commit that referenced this pull request Jan 22, 2018

Calculate sum in Kahan summation algorithm in aggregations (#27807) (#…

82d782b

…27848)

liketic deleted the feature/issues/27807 branch January 22, 2018 12:53

colings86 mentioned this pull request Apr 3, 2018

Inaccurate values when calculating SUM or AVG aggregations #29345

Closed

colings86 added v7.0.0-beta1 and removed v7.0.0 labels Feb 7, 2019

Conversation

liketic commented Dec 16, 2017 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

elasticmachine commented Dec 16, 2017

Uh oh!

jpountz left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

elasticmachine commented Jan 1, 2018

Uh oh!

jpountz left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

liketic commented Jan 3, 2018

Uh oh!

jpountz commented Jan 12, 2018

Uh oh!

liketic commented Jan 16, 2018

Uh oh!

jpountz left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

jpountz commented Jan 16, 2018

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

5 participants

liketic commented Dec 16, 2017 •

edited

Loading