You are viewing a plain text version of this content. The canonical link for it is here.
Posted to reviews@impala.apache.org by "Taras Bobrovytsky (Code Review)" <ge...@cloudera.org> on 2018/01/24 00:36:57 UTC

[Impala-ASF-CR] IMPALA-6429: Fix decimal division

Taras Bobrovytsky has uploaded this change for review. ( http://gerrit.cloudera.org:8080/9114


Change subject: IMPALA-6429: Fix decimal division
......................................................................

IMPALA-6429: Fix decimal division

Before this patch, it was possible for an overflow to not be detected
when doing a decimal division. When scaling up the dividend before
doing the division, we do not check for overflow. This is ok if the
we are scaling up by 10^38 or less because the result is guaranteed to
fit into 256 bits. However, when we are scaling up by more than 38, the
result may not fit into 256 bits and overflow. This overflow may not be
detected.

The problem is fixed by checking for overflow when scaling up the
dividend.

Testing:
- Added some BE tests

Change-Id: Ibd1075d9c78986cd975dd29c1125d71ba6560c23
---
M be/src/exprs/expr-test.cc
M be/src/runtime/decimal-value.inline.h
M be/src/util/decimal-util.h
3 files changed, 46 insertions(+), 24 deletions(-)



  git pull ssh://gerrit.cloudera.org:29418/Impala-ASF refs/changes/14/9114/1
-- 
To view, visit http://gerrit.cloudera.org:8080/9114
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: newchange
Gerrit-Change-Id: Ibd1075d9c78986cd975dd29c1125d71ba6560c23
Gerrit-Change-Number: 9114
Gerrit-PatchSet: 1
Gerrit-Owner: Taras Bobrovytsky <tb...@cloudera.com>

[Impala-ASF-CR] IMPALA-6429: Fix decimal division

Posted by "Taras Bobrovytsky (Code Review)" <ge...@cloudera.org>.
Taras Bobrovytsky has posted comments on this change. ( http://gerrit.cloudera.org:8080/9114 )

Change subject: IMPALA-6429: Fix decimal division
......................................................................


Patch Set 5: Code-Review+2

Forwarding the +2. Thanks for the reviews, Zach and Tim!


-- 
To view, visit http://gerrit.cloudera.org:8080/9114
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ibd1075d9c78986cd975dd29c1125d71ba6560c23
Gerrit-Change-Number: 9114
Gerrit-PatchSet: 5
Gerrit-Owner: Taras Bobrovytsky <tb...@cloudera.com>
Gerrit-Reviewer: Dan Hecht <dh...@cloudera.com>
Gerrit-Reviewer: Taras Bobrovytsky <tb...@cloudera.com>
Gerrit-Reviewer: Tim Armstrong <ta...@cloudera.com>
Gerrit-Reviewer: Zach Amsden <za...@cloudera.com>
Gerrit-Comment-Date: Thu, 01 Feb 2018 21:16:57 +0000
Gerrit-HasComments: No

[Impala-ASF-CR] IMPALA-6429: Fix decimal division

Posted by "Taras Bobrovytsky (Code Review)" <ge...@cloudera.org>.
Taras Bobrovytsky has posted comments on this change. ( http://gerrit.cloudera.org:8080/9114 )

Change subject: IMPALA-6429: Fix decimal division
......................................................................


Patch Set 3:

(1 comment)

http://gerrit.cloudera.org:8080/#/c/9114/3/be/src/util/decimal-util.h
File be/src/util/decimal-util.h:

http://gerrit.cloudera.org:8080/#/c/9114/3/be/src/util/decimal-util.h@58
PS3, Line 58:     return MultiplyByScale(v, t.scale, false, nullptr);
> Slight correction - I think it's even simpler than that - the template neve
Yes, I verified that all the tests still compile.



-- 
To view, visit http://gerrit.cloudera.org:8080/9114
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ibd1075d9c78986cd975dd29c1125d71ba6560c23
Gerrit-Change-Number: 9114
Gerrit-PatchSet: 3
Gerrit-Owner: Taras Bobrovytsky <tb...@cloudera.com>
Gerrit-Reviewer: Dan Hecht <dh...@cloudera.com>
Gerrit-Reviewer: Taras Bobrovytsky <tb...@cloudera.com>
Gerrit-Reviewer: Tim Armstrong <ta...@cloudera.com>
Gerrit-Reviewer: Zach Amsden <za...@cloudera.com>
Gerrit-Comment-Date: Thu, 01 Feb 2018 20:40:13 +0000
Gerrit-HasComments: Yes

[Impala-ASF-CR] IMPALA-6429: Fix decimal division

Posted by "Tim Armstrong (Code Review)" <ge...@cloudera.org>.
Tim Armstrong has posted comments on this change. ( http://gerrit.cloudera.org:8080/9114 )

Change subject: IMPALA-6429: Fix decimal division
......................................................................


Patch Set 4: Code-Review+2

(1 comment)

http://gerrit.cloudera.org:8080/#/c/9114/4/be/src/runtime/decimal-value.inline.h
File be/src/runtime/decimal-value.inline.h:

http://gerrit.cloudera.org:8080/#/c/9114/4/be/src/runtime/decimal-value.inline.h@483
PS4, Line 483:     bool ovf = scale_by > 38 && detail::MaxBitsRequiredAfterScaling(x_sp, scale_by) > 255;
Maybe reference the test in a comment that shows that this is correct?



-- 
To view, visit http://gerrit.cloudera.org:8080/9114
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ibd1075d9c78986cd975dd29c1125d71ba6560c23
Gerrit-Change-Number: 9114
Gerrit-PatchSet: 4
Gerrit-Owner: Taras Bobrovytsky <tb...@cloudera.com>
Gerrit-Reviewer: Dan Hecht <dh...@cloudera.com>
Gerrit-Reviewer: Taras Bobrovytsky <tb...@cloudera.com>
Gerrit-Reviewer: Tim Armstrong <ta...@cloudera.com>
Gerrit-Reviewer: Zach Amsden <za...@cloudera.com>
Gerrit-Comment-Date: Thu, 01 Feb 2018 21:05:46 +0000
Gerrit-HasComments: Yes

[Impala-ASF-CR] IMPALA-6429: Fix decimal division

Posted by "Zach Amsden (Code Review)" <ge...@cloudera.org>.
Zach Amsden has posted comments on this change. ( http://gerrit.cloudera.org:8080/9114 )

Change subject: IMPALA-6429: Fix decimal division
......................................................................


Patch Set 3:

(1 comment)

http://gerrit.cloudera.org:8080/#/c/9114/3/be/src/util/decimal-util.h
File be/src/util/decimal-util.h:

http://gerrit.cloudera.org:8080/#/c/9114/3/be/src/util/decimal-util.h@58
PS3, Line 58:     return MultiplyByScale(v, t.scale, false, nullptr);
> Good catch. I have no idea. I'm not sure how it even got compiled. It looks
SFINAE is why it compiled.



-- 
To view, visit http://gerrit.cloudera.org:8080/9114
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ibd1075d9c78986cd975dd29c1125d71ba6560c23
Gerrit-Change-Number: 9114
Gerrit-PatchSet: 3
Gerrit-Owner: Taras Bobrovytsky <tb...@cloudera.com>
Gerrit-Reviewer: Dan Hecht <dh...@cloudera.com>
Gerrit-Reviewer: Taras Bobrovytsky <tb...@cloudera.com>
Gerrit-Reviewer: Tim Armstrong <ta...@cloudera.com>
Gerrit-Reviewer: Zach Amsden <za...@cloudera.com>
Gerrit-Comment-Date: Thu, 01 Feb 2018 18:54:50 +0000
Gerrit-HasComments: Yes

[Impala-ASF-CR] IMPALA-6429: Fix decimal division

Posted by "Taras Bobrovytsky (Code Review)" <ge...@cloudera.org>.
Taras Bobrovytsky has posted comments on this change. ( http://gerrit.cloudera.org:8080/9114 )

Change subject: IMPALA-6429: Fix decimal division
......................................................................


Patch Set 3:

(5 comments)

http://gerrit.cloudera.org:8080/#/c/9114/3/be/src/exprs/expr-test.cc
File be/src/exprs/expr-test.cc:

http://gerrit.cloudera.org:8080/#/c/9114/3/be/src/exprs/expr-test.cc@2877
PS3, Line 2877:           EXPECT_TRUE((-scaled_up_dividend) / scale_multiplier !=
> I'm not sure how valuable this EXPECT_TRUE is - haven't we already verified
I'm checking it with negative numbers here. In the if condition it was with the positive numbers.


http://gerrit.cloudera.org:8080/#/c/9114/3/be/src/runtime/decimal-value.inline.h
File be/src/runtime/decimal-value.inline.h:

http://gerrit.cloudera.org:8080/#/c/9114/3/be/src/runtime/decimal-value.inline.h@161
PS3, Line 161:   return floor_log2[scale_by] + 1;
> Why not add the +1 into the floor function?  Then you can actually omit it 
Done


http://gerrit.cloudera.org:8080/#/c/9114/3/be/src/runtime/decimal-value.inline.h@175
PS3, Line 175:   int num_occupied = 128 - BitUtil::CountLeadingZeros<int128_t>(abs(num));
> An optimization idea for later.  Curious how efficient the abs() implementa
Might be worth experimenting with. Added a TODO comment.


http://gerrit.cloudera.org:8080/#/c/9114/3/be/src/util/decimal-util.h
File be/src/util/decimal-util.h:

http://gerrit.cloudera.org:8080/#/c/9114/3/be/src/util/decimal-util.h@54
PS3, Line 54:   /// TODO: do we need to handle overflow here or at a higher abstraction.
> TODO looks to be now done :)
Done


http://gerrit.cloudera.org:8080/#/c/9114/3/be/src/util/decimal-util.h@58
PS3, Line 58:     return MultiplyByScale(v, t.scale, false, nullptr);
> Which function is this actually calling?
Good catch. I have no idea. I'm not sure how it even got compiled. It looks like it doesn't get called by anything, so it's dead code. I removed it.



-- 
To view, visit http://gerrit.cloudera.org:8080/9114
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ibd1075d9c78986cd975dd29c1125d71ba6560c23
Gerrit-Change-Number: 9114
Gerrit-PatchSet: 3
Gerrit-Owner: Taras Bobrovytsky <tb...@cloudera.com>
Gerrit-Reviewer: Dan Hecht <dh...@cloudera.com>
Gerrit-Reviewer: Taras Bobrovytsky <tb...@cloudera.com>
Gerrit-Reviewer: Tim Armstrong <ta...@cloudera.com>
Gerrit-Reviewer: Zach Amsden <za...@cloudera.com>
Gerrit-Comment-Date: Wed, 31 Jan 2018 23:04:01 +0000
Gerrit-HasComments: Yes

[Impala-ASF-CR] IMPALA-6429: Fix decimal division

Posted by "Taras Bobrovytsky (Code Review)" <ge...@cloudera.org>.
Taras Bobrovytsky has uploaded a new patch set (#5). ( http://gerrit.cloudera.org:8080/9114 )

Change subject: IMPALA-6429: Fix decimal division
......................................................................

IMPALA-6429: Fix decimal division

Before this patch, it was possible for an overflow to not be detected
when doing a decimal division. When scaling up the dividend before
doing the division, we do not check for overflow. This is ok if the
we are scaling up by 10^38 or less because the result is guaranteed to
fit into 256 bits. However, when we are scaling up by more than 38, the
result may not fit into 256 bits and overflow. This overflow may not be
detected.

The problem is fixed by checking for overflow when scaling up the
dividend. The overflow check is done efficiently, by counting the
leading zeros. I added a test to prove that this check is correct.

Testing:
- Added some BE tests
- I ran a few benchmarks and did not see any performance regressions

Change-Id: Ibd1075d9c78986cd975dd29c1125d71ba6560c23
---
M be/src/exprs/expr-test.cc
M be/src/runtime/decimal-value.inline.h
M be/src/util/decimal-util.h
3 files changed, 127 insertions(+), 40 deletions(-)


  git pull ssh://gerrit.cloudera.org:29418/Impala-ASF refs/changes/14/9114/5
-- 
To view, visit http://gerrit.cloudera.org:8080/9114
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: newpatchset
Gerrit-Change-Id: Ibd1075d9c78986cd975dd29c1125d71ba6560c23
Gerrit-Change-Number: 9114
Gerrit-PatchSet: 5
Gerrit-Owner: Taras Bobrovytsky <tb...@cloudera.com>
Gerrit-Reviewer: Dan Hecht <dh...@cloudera.com>
Gerrit-Reviewer: Taras Bobrovytsky <tb...@cloudera.com>
Gerrit-Reviewer: Tim Armstrong <ta...@cloudera.com>
Gerrit-Reviewer: Zach Amsden <za...@cloudera.com>

[Impala-ASF-CR] IMPALA-6429: Fix decimal division

Posted by "Zach Amsden (Code Review)" <ge...@cloudera.org>.
Zach Amsden has posted comments on this change. ( http://gerrit.cloudera.org:8080/9114 )

Change subject: IMPALA-6429: Fix decimal division
......................................................................


Patch Set 3:

(1 comment)

http://gerrit.cloudera.org:8080/#/c/9114/3/be/src/util/decimal-util.h
File be/src/util/decimal-util.h:

http://gerrit.cloudera.org:8080/#/c/9114/3/be/src/util/decimal-util.h@58
PS3, Line 58:     return MultiplyByScale(v, t.scale, false, nullptr);
> SFINAE is why it compiled.
Slight correction - I think it's even simpler than that - the template never even got instantiated.  Please make sure that all the be tests still compile - some of them were doing weird things and creating their own ColumnTypes iirc.



-- 
To view, visit http://gerrit.cloudera.org:8080/9114
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ibd1075d9c78986cd975dd29c1125d71ba6560c23
Gerrit-Change-Number: 9114
Gerrit-PatchSet: 3
Gerrit-Owner: Taras Bobrovytsky <tb...@cloudera.com>
Gerrit-Reviewer: Dan Hecht <dh...@cloudera.com>
Gerrit-Reviewer: Taras Bobrovytsky <tb...@cloudera.com>
Gerrit-Reviewer: Tim Armstrong <ta...@cloudera.com>
Gerrit-Reviewer: Zach Amsden <za...@cloudera.com>
Gerrit-Comment-Date: Thu, 01 Feb 2018 19:02:46 +0000
Gerrit-HasComments: Yes

[Impala-ASF-CR] IMPALA-6429: Fix decimal division

Posted by "Impala Public Jenkins (Code Review)" <ge...@cloudera.org>.
Impala Public Jenkins has posted comments on this change. ( http://gerrit.cloudera.org:8080/9114 )

Change subject: IMPALA-6429: Fix decimal division
......................................................................


Patch Set 5:

Build started: https://jenkins.impala.io/job/gerrit-verify-dryrun/1858/


-- 
To view, visit http://gerrit.cloudera.org:8080/9114
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ibd1075d9c78986cd975dd29c1125d71ba6560c23
Gerrit-Change-Number: 9114
Gerrit-PatchSet: 5
Gerrit-Owner: Taras Bobrovytsky <tb...@cloudera.com>
Gerrit-Reviewer: Dan Hecht <dh...@cloudera.com>
Gerrit-Reviewer: Impala Public Jenkins
Gerrit-Reviewer: Taras Bobrovytsky <tb...@cloudera.com>
Gerrit-Reviewer: Tim Armstrong <ta...@cloudera.com>
Gerrit-Reviewer: Zach Amsden <za...@cloudera.com>
Gerrit-Comment-Date: Thu, 01 Feb 2018 21:17:38 +0000
Gerrit-HasComments: No

[Impala-ASF-CR] IMPALA-6429: Fix decimal division

Posted by "Taras Bobrovytsky (Code Review)" <ge...@cloudera.org>.
Taras Bobrovytsky has posted comments on this change. ( http://gerrit.cloudera.org:8080/9114 )

Change subject: IMPALA-6429: Fix decimal division
......................................................................


Patch Set 1:

(6 comments)

http://gerrit.cloudera.org:8080/#/c/9114/1//COMMIT_MSG
Commit Message:

http://gerrit.cloudera.org:8080/#/c/9114/1//COMMIT_MSG@18
PS1, Line 18: dividend.
> Will that ever lead to reporting overflow when the final answer does fit in
No, I don't think so. I added a test to prove this.


http://gerrit.cloudera.org:8080/#/c/9114/1/be/src/exprs/expr-test.cc
File be/src/exprs/expr-test.cc:

http://gerrit.cloudera.org:8080/#/c/9114/1/be/src/exprs/expr-test.cc@2400
PS1, Line 2400:      { true, false, 0, 38, 6 }}},
> Suggest also adding another test with full precision decimal(38,3) / decima
Done


http://gerrit.cloudera.org:8080/#/c/9114/1/be/src/runtime/decimal-value.inline.h
File be/src/runtime/decimal-value.inline.h:

http://gerrit.cloudera.org:8080/#/c/9114/1/be/src/runtime/decimal-value.inline.h@235
PS1, Line 235:   return DecimalUtil::SafeMultiply(left, mult, *overflow) + right;
> This is going to check *overflow with a branch anyway.  Why not hoist the c
Actually it's not true that SafeMultiply will check for overflow with a branch (at least in the release build). SafeMultiply() is just a multiplication followed by a DCHECK.

I think it's best to leave it as is. What do you think?


http://gerrit.cloudera.org:8080/#/c/9114/1/be/src/runtime/decimal-value.inline.h@288
PS1, Line 288:   return DecimalUtil::SafeMultiply(left, mult, *overflow) + right;
> Same comment applies.
Same response as above.


http://gerrit.cloudera.org:8080/#/c/9114/1/be/src/runtime/decimal-value.inline.h@457
PS1, Line 457:     bool may_overflow = scale_by > 38;
> You could add a leading zero check as well, but that requires knowing the m
I made pretty large modifications to how this is done in the latest patch. We check for overflow ONLY by looking at the leading zeros. Turns out this is sufficient.


http://gerrit.cloudera.org:8080/#/c/9114/1/be/src/util/decimal-util.h
File be/src/util/decimal-util.h:

http://gerrit.cloudera.org:8080/#/c/9114/1/be/src/util/decimal-util.h@67
PS1, Line 67:     if (UNLIKELY(result / multiplier != v)) *overflow = true;
> You can infer !may_overflow from overflow == nullptr, and this should inlin
Rewrote the patch quite significantly, so this does not quite apply. In the latest patch, this check is not necessary any more, so it should be faster.



-- 
To view, visit http://gerrit.cloudera.org:8080/9114
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ibd1075d9c78986cd975dd29c1125d71ba6560c23
Gerrit-Change-Number: 9114
Gerrit-PatchSet: 1
Gerrit-Owner: Taras Bobrovytsky <tb...@cloudera.com>
Gerrit-Reviewer: Dan Hecht <dh...@cloudera.com>
Gerrit-Reviewer: Taras Bobrovytsky <tb...@cloudera.com>
Gerrit-Reviewer: Tim Armstrong <ta...@cloudera.com>
Gerrit-Reviewer: Zach Amsden <za...@cloudera.com>
Gerrit-Comment-Date: Tue, 30 Jan 2018 23:02:31 +0000
Gerrit-HasComments: Yes

[Impala-ASF-CR] IMPALA-6429: Fix decimal division

Posted by "Taras Bobrovytsky (Code Review)" <ge...@cloudera.org>.
Taras Bobrovytsky has posted comments on this change. ( http://gerrit.cloudera.org:8080/9114 )

Change subject: IMPALA-6429: Fix decimal division
......................................................................


Patch Set 4:

(1 comment)

http://gerrit.cloudera.org:8080/#/c/9114/4/be/src/runtime/decimal-value.inline.h
File be/src/runtime/decimal-value.inline.h:

http://gerrit.cloudera.org:8080/#/c/9114/4/be/src/runtime/decimal-value.inline.h@483
PS4, Line 483:     bool ovf = scale_by > 38 && detail::MaxBitsRequiredAfterScaling(x_sp, scale_by) > 255;
> Maybe reference the test in a comment that shows that this is correct?
Done



-- 
To view, visit http://gerrit.cloudera.org:8080/9114
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ibd1075d9c78986cd975dd29c1125d71ba6560c23
Gerrit-Change-Number: 9114
Gerrit-PatchSet: 4
Gerrit-Owner: Taras Bobrovytsky <tb...@cloudera.com>
Gerrit-Reviewer: Dan Hecht <dh...@cloudera.com>
Gerrit-Reviewer: Taras Bobrovytsky <tb...@cloudera.com>
Gerrit-Reviewer: Tim Armstrong <ta...@cloudera.com>
Gerrit-Reviewer: Zach Amsden <za...@cloudera.com>
Gerrit-Comment-Date: Thu, 01 Feb 2018 21:15:09 +0000
Gerrit-HasComments: Yes

[Impala-ASF-CR] IMPALA-6429: Fix decimal division

Posted by "Zach Amsden (Code Review)" <ge...@cloudera.org>.
Zach Amsden has posted comments on this change. ( http://gerrit.cloudera.org:8080/9114 )

Change subject: IMPALA-6429: Fix decimal division
......................................................................


Patch Set 1:

(5 comments)

http://gerrit.cloudera.org:8080/#/c/9114/1/be/src/exprs/expr-test.cc
File be/src/exprs/expr-test.cc:

http://gerrit.cloudera.org:8080/#/c/9114/1/be/src/exprs/expr-test.cc@2400
PS1, Line 2400:      { true, false, 0, 38, 6 }}},
Suggest also adding another test with full precision decimal(38,3) / decimal(1,0), which will overflow in V2 since the result can't fit in decimal(38,6).  Even the value 1.0 will work as a divisor for this.


http://gerrit.cloudera.org:8080/#/c/9114/1/be/src/runtime/decimal-value.inline.h
File be/src/runtime/decimal-value.inline.h:

http://gerrit.cloudera.org:8080/#/c/9114/1/be/src/runtime/decimal-value.inline.h@235
PS1, Line 235:   return DecimalUtil::SafeMultiply(left, mult, *overflow) + right;
This is going to check *overflow with a branch anyway.  Why not hoist the check of *overflow to this function?  Then if (UNLIKELY(*overflow == true,)) return garbage, and always call DecimalUtil::SafeMultiply with false.


http://gerrit.cloudera.org:8080/#/c/9114/1/be/src/runtime/decimal-value.inline.h@288
PS1, Line 288:   return DecimalUtil::SafeMultiply(left, mult, *overflow) + right;
Same comment applies.


http://gerrit.cloudera.org:8080/#/c/9114/1/be/src/runtime/decimal-value.inline.h@457
PS1, Line 457:     bool may_overflow = scale_by > 38;
You could add a leading zero check as well, but that requires knowing the maximum value of scale_by.  This adds one more corner case that relies on the exact formula for result_scale, and that makes me uncomfortable.  In the future, we may want to improve decimal results by allowing the query to specify the output scale (as a cast, which gets pushed down into result_scale), and doing that is already a bit dangerous as I think there are other places that rely on the result scale formulas being predefined.


http://gerrit.cloudera.org:8080/#/c/9114/1/be/src/util/decimal-util.h
File be/src/util/decimal-util.h:

http://gerrit.cloudera.org:8080/#/c/9114/1/be/src/util/decimal-util.h@67
PS1, Line 67:     if (UNLIKELY(result / multiplier != v)) *overflow = true;
You can infer !may_overflow from overflow == nullptr, and this should inline just as well in cases where constant nullptr is passed.  (Edit - I see the way you are using it, this isn't quite true - I think if you adopt my suggestions for Add / SubtractLarge, then this may follow).

Also, this is likely expensive for int256_t.  I don't think there is a practical way to make that faster without direct access to the underlying type (to get the number of leading zeroes).



-- 
To view, visit http://gerrit.cloudera.org:8080/9114
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ibd1075d9c78986cd975dd29c1125d71ba6560c23
Gerrit-Change-Number: 9114
Gerrit-PatchSet: 1
Gerrit-Owner: Taras Bobrovytsky <tb...@cloudera.com>
Gerrit-Reviewer: Tim Armstrong <ta...@cloudera.com>
Gerrit-Reviewer: Zach Amsden <za...@cloudera.com>
Gerrit-Comment-Date: Wed, 24 Jan 2018 18:16:28 +0000
Gerrit-HasComments: Yes

[Impala-ASF-CR] IMPALA-6429: Fix decimal division

Posted by "Zach Amsden (Code Review)" <ge...@cloudera.org>.
Zach Amsden has posted comments on this change. ( http://gerrit.cloudera.org:8080/9114 )

Change subject: IMPALA-6429: Fix decimal division
......................................................................


Patch Set 4: Code-Review+1

Dan, Tim, any last comments?


-- 
To view, visit http://gerrit.cloudera.org:8080/9114
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ibd1075d9c78986cd975dd29c1125d71ba6560c23
Gerrit-Change-Number: 9114
Gerrit-PatchSet: 4
Gerrit-Owner: Taras Bobrovytsky <tb...@cloudera.com>
Gerrit-Reviewer: Dan Hecht <dh...@cloudera.com>
Gerrit-Reviewer: Taras Bobrovytsky <tb...@cloudera.com>
Gerrit-Reviewer: Tim Armstrong <ta...@cloudera.com>
Gerrit-Reviewer: Zach Amsden <za...@cloudera.com>
Gerrit-Comment-Date: Thu, 01 Feb 2018 18:55:40 +0000
Gerrit-HasComments: No

[Impala-ASF-CR] IMPALA-6429: Fix decimal division

Posted by "Taras Bobrovytsky (Code Review)" <ge...@cloudera.org>.
Taras Bobrovytsky has uploaded a new patch set (#2). ( http://gerrit.cloudera.org:8080/9114 )

Change subject: IMPALA-6429: Fix decimal division
......................................................................

IMPALA-6429: Fix decimal division

Before this patch, it was possible for an overflow to not be detected
when doing a decimal division. When scaling up the dividend before
doing the division, we do not check for overflow. This is ok if the
we are scaling up by 10^38 or less because the result is guaranteed to
fit into 256 bits. However, when we are scaling up by more than 38, the
result may not fit into 256 bits and overflow. This overflow may not be
detected.

The problem is fixed by checking for overflow when scaling up the
dividend. The overflow check is done efficiently, by counting the
leading zeros. I added a test to prove that this check is correct.

Testing:
- Added some BE tests

Change-Id: Ibd1075d9c78986cd975dd29c1125d71ba6560c23
---
M be/src/exprs/expr-test.cc
M be/src/runtime/decimal-value.inline.h
M be/src/util/decimal-util.h
3 files changed, 121 insertions(+), 36 deletions(-)


  git pull ssh://gerrit.cloudera.org:29418/Impala-ASF refs/changes/14/9114/2
-- 
To view, visit http://gerrit.cloudera.org:8080/9114
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: newpatchset
Gerrit-Change-Id: Ibd1075d9c78986cd975dd29c1125d71ba6560c23
Gerrit-Change-Number: 9114
Gerrit-PatchSet: 2
Gerrit-Owner: Taras Bobrovytsky <tb...@cloudera.com>
Gerrit-Reviewer: Dan Hecht <dh...@cloudera.com>
Gerrit-Reviewer: Taras Bobrovytsky <tb...@cloudera.com>
Gerrit-Reviewer: Tim Armstrong <ta...@cloudera.com>
Gerrit-Reviewer: Zach Amsden <za...@cloudera.com>

[Impala-ASF-CR] IMPALA-6429: Fix decimal division

Posted by "Impala Public Jenkins (Code Review)" <ge...@cloudera.org>.
Impala Public Jenkins has submitted this change and it was merged. ( http://gerrit.cloudera.org:8080/9114 )

Change subject: IMPALA-6429: Fix decimal division
......................................................................

IMPALA-6429: Fix decimal division

Before this patch, it was possible for an overflow to not be detected
when doing a decimal division. When scaling up the dividend before
doing the division, we do not check for overflow. This is ok if the
we are scaling up by 10^38 or less because the result is guaranteed to
fit into 256 bits. However, when we are scaling up by more than 38, the
result may not fit into 256 bits and overflow. This overflow may not be
detected.

The problem is fixed by checking for overflow when scaling up the
dividend. The overflow check is done efficiently, by counting the
leading zeros. I added a test to prove that this check is correct.

Testing:
- Added some BE tests
- I ran a few benchmarks and did not see any performance regressions

Change-Id: Ibd1075d9c78986cd975dd29c1125d71ba6560c23
Reviewed-on: http://gerrit.cloudera.org:8080/9114
Reviewed-by: Taras Bobrovytsky <tb...@cloudera.com>
Tested-by: Impala Public Jenkins
---
M be/src/exprs/expr-test.cc
M be/src/runtime/decimal-value.inline.h
M be/src/util/decimal-util.h
3 files changed, 127 insertions(+), 40 deletions(-)

Approvals:
  Taras Bobrovytsky: Looks good to me, approved
  Impala Public Jenkins: Verified

-- 
To view, visit http://gerrit.cloudera.org:8080/9114
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: merged
Gerrit-Change-Id: Ibd1075d9c78986cd975dd29c1125d71ba6560c23
Gerrit-Change-Number: 9114
Gerrit-PatchSet: 6
Gerrit-Owner: Taras Bobrovytsky <tb...@cloudera.com>
Gerrit-Reviewer: Dan Hecht <dh...@cloudera.com>
Gerrit-Reviewer: Impala Public Jenkins
Gerrit-Reviewer: Taras Bobrovytsky <tb...@cloudera.com>
Gerrit-Reviewer: Tim Armstrong <ta...@cloudera.com>
Gerrit-Reviewer: Zach Amsden <za...@cloudera.com>

[Impala-ASF-CR] IMPALA-6429: Fix decimal division

Posted by "Zach Amsden (Code Review)" <ge...@cloudera.org>.
Zach Amsden has posted comments on this change. ( http://gerrit.cloudera.org:8080/9114 )

Change subject: IMPALA-6429: Fix decimal division
......................................................................


Patch Set 3:

(5 comments)

http://gerrit.cloudera.org:8080/#/c/9114/3/be/src/exprs/expr-test.cc
File be/src/exprs/expr-test.cc:

http://gerrit.cloudera.org:8080/#/c/9114/3/be/src/exprs/expr-test.cc@2877
PS3, Line 2877:           EXPECT_TRUE((-scaled_up_dividend) / scale_multiplier !=
I'm not sure how valuable this EXPECT_TRUE is - haven't we already verified that with the if condition?


http://gerrit.cloudera.org:8080/#/c/9114/3/be/src/runtime/decimal-value.inline.h
File be/src/runtime/decimal-value.inline.h:

http://gerrit.cloudera.org:8080/#/c/9114/3/be/src/runtime/decimal-value.inline.h@161
PS3, Line 161:   return floor_log2[scale_by] + 1;
Why not add the +1 into the floor function?  Then you can actually omit it for the case of zero, where the formula is conservative (no increase in bits multiplying by 1).


http://gerrit.cloudera.org:8080/#/c/9114/3/be/src/runtime/decimal-value.inline.h@175
PS3, Line 175:   int num_occupied = 128 - BitUtil::CountLeadingZeros<int128_t>(abs(num));
An optimization idea for later.  Curious how efficient the abs() implementation is for int128_t.  Given that we have to do a lot of these abs() transformations, might it make sense for us to do that up front for large multiply and divide, do everything in unsigned math, and correct the result after?  This also simplifies getting the rounding correct.


http://gerrit.cloudera.org:8080/#/c/9114/3/be/src/util/decimal-util.h
File be/src/util/decimal-util.h:

http://gerrit.cloudera.org:8080/#/c/9114/3/be/src/util/decimal-util.h@54
PS3, Line 54:   /// TODO: do we need to handle overflow here or at a higher abstraction.
TODO looks to be now done :)


http://gerrit.cloudera.org:8080/#/c/9114/3/be/src/util/decimal-util.h@58
PS3, Line 58:     return MultiplyByScale(v, t.scale, false, nullptr);
Which function is this actually calling?



-- 
To view, visit http://gerrit.cloudera.org:8080/9114
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ibd1075d9c78986cd975dd29c1125d71ba6560c23
Gerrit-Change-Number: 9114
Gerrit-PatchSet: 3
Gerrit-Owner: Taras Bobrovytsky <tb...@cloudera.com>
Gerrit-Reviewer: Dan Hecht <dh...@cloudera.com>
Gerrit-Reviewer: Taras Bobrovytsky <tb...@cloudera.com>
Gerrit-Reviewer: Tim Armstrong <ta...@cloudera.com>
Gerrit-Reviewer: Zach Amsden <za...@cloudera.com>
Gerrit-Comment-Date: Wed, 31 Jan 2018 20:00:33 +0000
Gerrit-HasComments: Yes

[Impala-ASF-CR] IMPALA-6429: Fix decimal division

Posted by "Dan Hecht (Code Review)" <ge...@cloudera.org>.
Dan Hecht has posted comments on this change. ( http://gerrit.cloudera.org:8080/9114 )

Change subject: IMPALA-6429: Fix decimal division
......................................................................


Patch Set 1:

(1 comment)

http://gerrit.cloudera.org:8080/#/c/9114/1//COMMIT_MSG
Commit Message:

http://gerrit.cloudera.org:8080/#/c/9114/1//COMMIT_MSG@18
PS1, Line 18: dividend.
Will that ever lead to reporting overflow when the final answer does fit in the result (P, S) type?



-- 
To view, visit http://gerrit.cloudera.org:8080/9114
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ibd1075d9c78986cd975dd29c1125d71ba6560c23
Gerrit-Change-Number: 9114
Gerrit-PatchSet: 1
Gerrit-Owner: Taras Bobrovytsky <tb...@cloudera.com>
Gerrit-Reviewer: Dan Hecht <dh...@cloudera.com>
Gerrit-Reviewer: Tim Armstrong <ta...@cloudera.com>
Gerrit-Reviewer: Zach Amsden <za...@cloudera.com>
Gerrit-Comment-Date: Tue, 30 Jan 2018 18:00:04 +0000
Gerrit-HasComments: Yes

[Impala-ASF-CR] IMPALA-6429: Fix decimal division

Posted by "Taras Bobrovytsky (Code Review)" <ge...@cloudera.org>.
Taras Bobrovytsky has uploaded a new patch set (#4). ( http://gerrit.cloudera.org:8080/9114 )

Change subject: IMPALA-6429: Fix decimal division
......................................................................

IMPALA-6429: Fix decimal division

Before this patch, it was possible for an overflow to not be detected
when doing a decimal division. When scaling up the dividend before
doing the division, we do not check for overflow. This is ok if the
we are scaling up by 10^38 or less because the result is guaranteed to
fit into 256 bits. However, when we are scaling up by more than 38, the
result may not fit into 256 bits and overflow. This overflow may not be
detected.

The problem is fixed by checking for overflow when scaling up the
dividend. The overflow check is done efficiently, by counting the
leading zeros. I added a test to prove that this check is correct.

Testing:
- Added some BE tests

Change-Id: Ibd1075d9c78986cd975dd29c1125d71ba6560c23
---
M be/src/exprs/expr-test.cc
M be/src/runtime/decimal-value.inline.h
M be/src/util/decimal-util.h
3 files changed, 125 insertions(+), 40 deletions(-)


  git pull ssh://gerrit.cloudera.org:29418/Impala-ASF refs/changes/14/9114/4
-- 
To view, visit http://gerrit.cloudera.org:8080/9114
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: newpatchset
Gerrit-Change-Id: Ibd1075d9c78986cd975dd29c1125d71ba6560c23
Gerrit-Change-Number: 9114
Gerrit-PatchSet: 4
Gerrit-Owner: Taras Bobrovytsky <tb...@cloudera.com>
Gerrit-Reviewer: Dan Hecht <dh...@cloudera.com>
Gerrit-Reviewer: Taras Bobrovytsky <tb...@cloudera.com>
Gerrit-Reviewer: Tim Armstrong <ta...@cloudera.com>
Gerrit-Reviewer: Zach Amsden <za...@cloudera.com>

[Impala-ASF-CR] IMPALA-6429: Fix decimal division

Posted by "Taras Bobrovytsky (Code Review)" <ge...@cloudera.org>.
Taras Bobrovytsky has uploaded a new patch set (#3). ( http://gerrit.cloudera.org:8080/9114 )

Change subject: IMPALA-6429: Fix decimal division
......................................................................

IMPALA-6429: Fix decimal division

Before this patch, it was possible for an overflow to not be detected
when doing a decimal division. When scaling up the dividend before
doing the division, we do not check for overflow. This is ok if the
we are scaling up by 10^38 or less because the result is guaranteed to
fit into 256 bits. However, when we are scaling up by more than 38, the
result may not fit into 256 bits and overflow. This overflow may not be
detected.

The problem is fixed by checking for overflow when scaling up the
dividend. The overflow check is done efficiently, by counting the
leading zeros. I added a test to prove that this check is correct.

Testing:
- Added some BE tests

Change-Id: Ibd1075d9c78986cd975dd29c1125d71ba6560c23
---
M be/src/exprs/expr-test.cc
M be/src/runtime/decimal-value.inline.h
M be/src/util/decimal-util.h
3 files changed, 125 insertions(+), 36 deletions(-)


  git pull ssh://gerrit.cloudera.org:29418/Impala-ASF refs/changes/14/9114/3
-- 
To view, visit http://gerrit.cloudera.org:8080/9114
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: newpatchset
Gerrit-Change-Id: Ibd1075d9c78986cd975dd29c1125d71ba6560c23
Gerrit-Change-Number: 9114
Gerrit-PatchSet: 3
Gerrit-Owner: Taras Bobrovytsky <tb...@cloudera.com>
Gerrit-Reviewer: Dan Hecht <dh...@cloudera.com>
Gerrit-Reviewer: Taras Bobrovytsky <tb...@cloudera.com>
Gerrit-Reviewer: Tim Armstrong <ta...@cloudera.com>
Gerrit-Reviewer: Zach Amsden <za...@cloudera.com>

[Impala-ASF-CR] IMPALA-6429: Fix decimal division

Posted by "Impala Public Jenkins (Code Review)" <ge...@cloudera.org>.
Impala Public Jenkins has posted comments on this change. ( http://gerrit.cloudera.org:8080/9114 )

Change subject: IMPALA-6429: Fix decimal division
......................................................................


Patch Set 5: Verified+1


-- 
To view, visit http://gerrit.cloudera.org:8080/9114
To unsubscribe, visit http://gerrit.cloudera.org:8080/settings

Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-MessageType: comment
Gerrit-Change-Id: Ibd1075d9c78986cd975dd29c1125d71ba6560c23
Gerrit-Change-Number: 9114
Gerrit-PatchSet: 5
Gerrit-Owner: Taras Bobrovytsky <tb...@cloudera.com>
Gerrit-Reviewer: Dan Hecht <dh...@cloudera.com>
Gerrit-Reviewer: Impala Public Jenkins
Gerrit-Reviewer: Taras Bobrovytsky <tb...@cloudera.com>
Gerrit-Reviewer: Tim Armstrong <ta...@cloudera.com>
Gerrit-Reviewer: Zach Amsden <za...@cloudera.com>
Gerrit-Comment-Date: Fri, 02 Feb 2018 01:01:35 +0000
Gerrit-HasComments: No