You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@impala.apache.org by ta...@apache.org on 2017/11/23 04:19:28 UTC
[4/5] incubator-impala git commit: IMPALA-4964: Fix Decimal modulo
overflow
IMPALA-4964: Fix Decimal modulo overflow
The modulo operation between two decimals should never overflow. Before
this patch, there would be an overflow if the scale difference between
the two decimals was large. We would try to scale up the one with the
smaller scale, so that the scales matched, which could result in an
overflow.
We fix the problem by first checking if the scaled up value would fit
into 128 bits by estimating the number of leading zeros in it. If we
detect that 128 bits is not enough, we convert both numbers to int256,
do the operation, then convert back to 128 bits.
Testing:
- Added some expr tests that excercise the new code path.
Change-Id: I5420201d4440d421e33e443df005cdcc16b8a6cd
Reviewed-on: http://gerrit.cloudera.org:8080/8329
Reviewed-by: Tim Armstrong <ta...@cloudera.com>
Tested-by: Impala Public Jenkins
Project: http://git-wip-us.apache.org/repos/asf/incubator-impala/repo
Commit: http://git-wip-us.apache.org/repos/asf/incubator-impala/commit/70f1c023
Tree: http://git-wip-us.apache.org/repos/asf/incubator-impala/tree/70f1c023
Diff: http://git-wip-us.apache.org/repos/asf/incubator-impala/diff/70f1c023
Branch: refs/heads/master
Commit: 70f1c023aada346343eba548cc9cc5129de2410f
Parents: 3845c0f
Author: Taras Bobrovytsky <tb...@cloudera.com>
Authored: Tue Oct 17 20:15:43 2017 -0700
Committer: Impala Public Jenkins <im...@gerrit.cloudera.org>
Committed: Thu Nov 23 00:55:35 2017 +0000
----------------------------------------------------------------------
be/src/exprs/expr-test.cc | 79 ++++++++++++++++++++++++++++--
be/src/runtime/decimal-test.cc | 3 +-
be/src/runtime/decimal-value.inline.h | 76 +++++++++++++++++++---------
3 files changed, 129 insertions(+), 29 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/incubator-impala/blob/70f1c023/be/src/exprs/expr-test.cc
----------------------------------------------------------------------
diff --git a/be/src/exprs/expr-test.cc b/be/src/exprs/expr-test.cc
index 294dcc9..3277042 100644
--- a/be/src/exprs/expr-test.cc
+++ b/be/src/exprs/expr-test.cc
@@ -2353,6 +2353,17 @@ DecimalTestCase decimal_cases[] = {
// Test modulo operator
{ "cast(1.23 as decimal(8,2)) % cast(1 as decimal(10,3))",
{{ false, false, 230, 9, 3 }}},
+ // The modulo operator is defined such that the following holds:
+ // (x / y) * y + x % y == x
+ // In order to satisfy the above, the following must also hold:
+ // x % -y == x % y
+ // (-x) % y == -(x % y)
+ { "cast(-1.23 as decimal(8,2)) % cast(1 as decimal(10,3))",
+ {{ false, false, -230, 9, 3 }}},
+ { "cast(1.23 as decimal(8,2)) % cast(-1 as decimal(10,3))",
+ {{ false, false, 230, 9, 3 }}},
+ { "cast(-1.23 as decimal(8,2)) % cast(-1 as decimal(10,3))",
+ {{ false, false, -230, 9, 3 }}},
{ "cast(1 as decimal(38,0)) % cast(.2 as decimal(38,1))",
{{ false, false, 0, 38, 1 }}},
{ "cast(1 as decimal(38,0)) % cast(3 as decimal(38,0))",
@@ -2365,14 +2376,74 @@ DecimalTestCase decimal_cases[] = {
"cast(99999999999999999999999999999999999999 as decimal(38,0))",
{{ false, false, 0, 38, 0 }}},
{ "cast(998 as decimal(38,0)) % cast(0.999 as decimal(38,38))",
- {{ false, true, 0, 38, 38 }, // IMPALA-4964 - this should not overflow
- { false, true, 0, 38, 38 }}},
+ {{ false, false, StringToInt128("99800000000000000000000000000000000000"), 38, 38 }}},
+ { "cast(-998 as decimal(38,0)) % cast(0.999 as decimal(38,38))",
+ {{ false, false, StringToInt128("-99800000000000000000000000000000000000"), 38, 38 }}},
+ { "cast(-998 as decimal(38,0)) % cast(-0.999 as decimal(38,38))",
+ {{ false, false, StringToInt128("-99800000000000000000000000000000000000"), 38, 38 }}},
+ { "cast(998 as decimal(38,0)) % cast(-0.999 as decimal(38,38))",
+ {{ false, false, StringToInt128("99800000000000000000000000000000000000"), 38, 38 }}},
{ "cast(0.998 as decimal(38,38)) % cast(999 as decimal(38,0))",
- {{ false, true, 0, 38, 38 }, // IMPALA-4964 - this should not overflow
- { false, true, 0, 38, 38 }}},
+ {{ false, false, StringToInt128("99800000000000000000000000000000000000"), 38, 38 }}},
+ { "cast(88888888888888888888888888888888888888 as decimal(38,0)) % "
+ "cast(0.33333333333333333333333333333333333333 as decimal(38,38))",
+ {{ false, false, StringToInt128("22222222222222222222222222222222222222"), 38, 38 }}},
+ { "cast(88888888888888888888888888888888888888 as decimal(38,0)) % "
+ "cast(3333333333333333333333333333.3333333333 as decimal(38,10))",
+ {{ false, false, StringToInt128("22222222222222222222222222222222222222"), 38, 10 }}},
+ { "cast(-88888888888888888888888888888888888888 as decimal(38,0)) % "
+ "cast(3333333333333333333333333333.3333333333 as decimal(38,10))",
+ {{ false, false, StringToInt128("-22222222222222222222222222222222222222"), 38, 10 }}},
+ { "cast(-88888888888888888888888888888888888888 as decimal(38,0)) % "
+ "cast(-3333333333333333333333333333.3333333333 as decimal(38,10))",
+ {{ false, false, StringToInt128("-22222222222222222222222222222222222222"), 38, 10 }}},
+ { "cast(88888888888888888888888888888888888888 as decimal(38,0)) % "
+ "cast(-3333333333333333333333333333.3333333333 as decimal(38,10))",
+ {{ false, false, StringToInt128("22222222222222222222222222222222222222"), 38, 10 }}},
+ { "cast(3333333333333333333333333333.3333333333 as decimal(38,10)) % "
+ "cast(88888888888888888888888888888888888888 as decimal(38,0))",
+ {{ false, false, StringToInt128("33333333333333333333333333333333333333"), 38, 10 }}},
{ "cast(0.00000000000000000000000000000000000001 as decimal(38,38)) % "
"cast(0.0000000000000000000000000000000000001 as decimal(38,38))",
{{ false, false, 1, 38, 38 }}},
+ // Largest values that do not get converted to int256.
+ // The values are 2^126 - 1 and 2^122 - 1.
+ { "cast(8507059173023461586584365185794205286.3 as decimal(38,1)) % "
+ "cast(5316911983139663491615228241121378303 as decimal(38,0))",
+ {{ false, false, StringToInt128("31901471898837980949691369446728269833"), 38, 1 }}},
+ { "cast(-8507059173023461586584365185794205286.3 as decimal(38,1)) % "
+ "cast(5316911983139663491615228241121378303 as decimal(38,0))",
+ {{ false, false, StringToInt128("-31901471898837980949691369446728269833"), 38, 1 }}},
+ { "cast(-8507059173023461586584365185794205286.3 as decimal(38,1)) % "
+ "cast(-5316911983139663491615228241121378303 as decimal(38,0))",
+ {{ false, false, StringToInt128("-31901471898837980949691369446728269833"), 38, 1 }}},
+ { "cast(8507059173023461586584365185794205286.3 as decimal(38,1)) % "
+ "cast(-5316911983139663491615228241121378303 as decimal(38,0))",
+ {{ false, false, StringToInt128("31901471898837980949691369446728269833"), 38, 1 }}},
+ { "cast(8507059173023461586584365185794205286.4 as decimal(38,1)) % "
+ "cast(5316911983139663491615228241121378303 as decimal(38,0))",
+ {{ false, false, StringToInt128("31901471898837980949691369446728269834"), 38, 1 }}},
+ { "cast(-8507059173023461586584365185794205286.4 as decimal(38,1)) % "
+ "cast(5316911983139663491615228241121378303 as decimal(38,0))",
+ {{ false, false, StringToInt128("-31901471898837980949691369446728269834"), 38, 1 }}},
+ { "cast(-8507059173023461586584365185794205286.4 as decimal(38,1)) % "
+ "cast(-5316911983139663491615228241121378303 as decimal(38,0))",
+ {{ false, false, StringToInt128("-31901471898837980949691369446728269834"), 38, 1 }}},
+ { "cast(8507059173023461586584365185794205286.4 as decimal(38,1)) % "
+ "cast(-5316911983139663491615228241121378303 as decimal(38,0))",
+ {{ false, false, StringToInt128("31901471898837980949691369446728269834"), 38, 1 }}},
+ { "cast(8507059173023461586584365185794205286.3 as decimal(38,1)) % "
+ "cast(5316911983139663491615228241121378304 as decimal(38,0))",
+ {{ false, false, StringToInt128("31901471898837980949691369446728269823"), 38, 1 }}},
+ { "cast(5316911983139663491615228241121378303 as decimal(38,0)) % "
+ "cast(8507059173023461586584365185794205286.3 as decimal(38,1))",
+ {{ false, false, StringToInt128("53169119831396634916152282411213783030"), 38, 1 }}},
+ { "cast(5316911983139663491615228241121378303 as decimal(38,0)) % "
+ "cast(8507059173023461586584365185794205286.4 as decimal(38,1))",
+ {{ false, false, StringToInt128("53169119831396634916152282411213783030"), 38, 1 }}},
+ { "cast(5316911983139663491615228241121378304 as decimal(38,0)) % "
+ "cast(8507059173023461586584365185794205286.3 as decimal(38,1))",
+ {{ false, false, StringToInt128("53169119831396634916152282411213783040"), 38, 1 }}},
// Test MOD builtin
{ "mod(cast('1' as decimal(2,0)), cast('10' as decimal(2,0)))",
{{ false, false, 1, 2, 0 }}},
http://git-wip-us.apache.org/repos/asf/incubator-impala/blob/70f1c023/be/src/runtime/decimal-test.cc
----------------------------------------------------------------------
diff --git a/be/src/runtime/decimal-test.cc b/be/src/runtime/decimal-test.cc
index d81a16e..f84fdaf 100644
--- a/be/src/runtime/decimal-test.cc
+++ b/be/src/runtime/decimal-test.cc
@@ -573,8 +573,9 @@ TEST(DecimalTest, Overflow) {
overflow = false;
bool is_nan;
result = d3.Mod<int128_t>(0, d3, 20, 38, 20, false, &is_nan, &overflow);
- EXPECT_TRUE(overflow);
+ EXPECT_FALSE(overflow);
EXPECT_FALSE(is_nan);
+ EXPECT_EQ(result.value(), 0);
overflow = false;
result = d3.Mod<int128_t>(0, two, 0, 38, 0, false, &is_nan, &overflow);
http://git-wip-us.apache.org/repos/asf/incubator-impala/blob/70f1c023/be/src/runtime/decimal-value.inline.h
----------------------------------------------------------------------
diff --git a/be/src/runtime/decimal-value.inline.h b/be/src/runtime/decimal-value.inline.h
index 3f14229..2e17d96 100644
--- a/be/src/runtime/decimal-value.inline.h
+++ b/be/src/runtime/decimal-value.inline.h
@@ -174,6 +174,20 @@ inline int MinLeadingZerosAfterScaling(int num_lz, int scale_diff) {
return num_lz - floor_log2[scale_diff] - 1;
}
+// Returns the minimum number of leading zero x or y would have after one of them gets
+// scaled up to match the scale of the other one.
+template<typename RESULT_T>
+inline int MinLeadingZeros(RESULT_T x, int x_scale, RESULT_T y, int y_scale) {
+ int x_lz = BitUtil::CountLeadingZeros(abs(x));
+ int y_lz = BitUtil::CountLeadingZeros(abs(y));
+ if (x_scale < y_scale) {
+ x_lz = detail::MinLeadingZerosAfterScaling(x_lz, y_scale - x_scale);
+ } else if (x_scale > y_scale) {
+ y_lz = detail::MinLeadingZerosAfterScaling(y_lz, x_scale - y_scale);
+ }
+ return std::min(x_lz, y_lz);
+}
+
// Separates x and y into into fractional and whole parts.
inline void SeparateFractional(int128_t x, int x_scale, int128_t y, int y_scale,
int128_t* x_left, int128_t* x_right, int128_t* y_left, int128_t* y_right) {
@@ -311,24 +325,16 @@ inline DecimalValue<RESULT_T> DecimalValue<T>::Add(int this_scale,
return DecimalValue<RESULT_T>(x + y);
}
- // We compute how many leading zeros x and y would have after one of them gets scaled
+ // Compute how many leading zeros x and y would have after one of them gets scaled
// up to match the scale of the other one.
- int x_lz = BitUtil::CountLeadingZeros(abs(value()));
- int y_lz = BitUtil::CountLeadingZeros(abs(other.value()));
-
- int result_scale_decrease = this_scale - result_scale;
- int scale_diff = this_scale - other_scale;
- if (scale_diff > 0) {
- y_lz = detail::MinLeadingZerosAfterScaling(y_lz, scale_diff);
- } else if (scale_diff < 0) {
- result_scale_decrease = other_scale - result_scale;
- x_lz = detail::MinLeadingZerosAfterScaling(x_lz, -scale_diff);
- }
+ int min_lz = detail::MinLeadingZeros(
+ abs(value()), this_scale, abs(other.value()), other_scale);
+ int result_scale_decrease = std::max(
+ this_scale - result_scale, other_scale - result_scale);
DCHECK_GE(result_scale_decrease, 0);
- DCHECK_EQ(result_scale_decrease, std::max(this_scale, other_scale) - result_scale);
const int MIN_LZ = 3;
- if ((x_lz >= MIN_LZ) && (y_lz >= MIN_LZ)) {
+ if (min_lz >= MIN_LZ) {
// If both numbers have at least MIN_LZ leading zeros, we can add them directly
// without the risk of overflow.
// We want the result to have at least 2 leading zeros, which ensures that it fits
@@ -526,17 +532,39 @@ inline DecimalValue<RESULT_T> DecimalValue<T>::Mod(int this_scale,
const DecimalValue& other, int other_scale, int result_precision, int result_scale,
bool round, bool* is_nan, bool* overflow) const {
DCHECK_EQ(result_scale, std::max(this_scale, other_scale));
- if (other.value() == 0) {
- // Mod by 0.
- *is_nan = true;
- return DecimalValue<RESULT_T>();
+ *is_nan = other.value() == 0;
+ if (UNLIKELY(*is_nan)) return DecimalValue<RESULT_T>();
+
+ RESULT_T result;
+ bool ovf = false;
+ // We check if it is possible to compute the result without having to convert the two
+ // inputs to int256_t, which is very slow.
+ if (sizeof(RESULT_T) < 16 ||
+ result_precision < 38 ||
+ // If the scales are the same, there is no danger in overflowing due to scaling up.
+ this_scale == other_scale ||
+ detail::MinLeadingZeros(value(), this_scale, other.value(), other_scale) >= 2) {
+ RESULT_T x, y;
+ ovf = AdjustToSameScale(*this, this_scale, other, other_scale,
+ result_precision, &x, &y);
+ result = x % y;
+ DCHECK(abs(result) < abs(y));
+ } else {
+ int256_t x_256 = ConvertToInt256(value());
+ int256_t y_256 = ConvertToInt256(other.value());
+ if (this_scale < other_scale) {
+ x_256 *= DecimalUtil::GetScaleMultiplier<int256_t>(other_scale - this_scale);
+ } else {
+ y_256 *= DecimalUtil::GetScaleMultiplier<int256_t>(this_scale - other_scale);
+ }
+ int256_t intermediate_result = x_256 % y_256;
+ result = ConvertToInt128(intermediate_result,
+ DecimalUtil::MAX_UNSCALED_DECIMAL16, &ovf);
+ DCHECK(abs(result) <= abs(value()) || abs(result) < abs(other.value()));
}
- *is_nan = false;
- RESULT_T x = 0;
- RESULT_T y = 1; // Initialize y to avoid mod by 0.
- *overflow |= AdjustToSameScale(*this, this_scale, other, other_scale,
- result_precision, &x, &y);
- return DecimalValue<RESULT_T>(x % y);
+ // An overflow should be impossible.
+ DCHECK(!ovf);
+ return DecimalValue<RESULT_T>(result);
}
template<typename T>