You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@arrow.apache.org by GitBox <gi...@apache.org> on 2021/02/26 08:36:39 UTC
[GitHub] [arrow] emkornfield opened a new pull request #9582: PARQUET-1655: [C++] Fixed signed byte comparison
emkornfield opened a new pull request #9582:
URL: https://github.com/apache/arrow/pull/9582
The prior logic, I don't think is ever correct for signed
comparison. Signed comparison of bytes as far as I can
tell from the specification is only used by Decimal
encoded values. Decimals are always encoded as big-endian
two's complement integers.
The new logic reflects this by doing sign extension when
necessary for comparisons, and only using signed byte comparison
for the very first value when appropriate.
This PR also eliminates what appears to be a some dead code.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow] emkornfield commented on a change in pull request #9582: PARQUET-1655: [C++] Fix comparison of Decimal values in statistics
Posted by GitBox <gi...@apache.org>.
emkornfield commented on a change in pull request #9582:
URL: https://github.com/apache/arrow/pull/9582#discussion_r584862571
##########
File path: cpp/src/parquet/statistics.cc
##########
@@ -133,56 +136,95 @@ struct CompareHelper<Int96Type, is_signed> {
static T Max(int type_length, const T& a, const T& b) {
return Compare(0, a, b) ? b : a;
}
-}; // namespace parquet
-
-template <typename DType, bool is_signed>
-struct ByteLikeCompareHelperBase {
- using T = ByteArrayType::c_type;
- using PtrType = typename std::conditional<is_signed, int8_t, uint8_t>::type;
+};
- static T DefaultMin() { return {}; }
- static T DefaultMax() { return {}; }
- static T Coalesce(T val, T fallback) { return val; }
+template <typename T, bool is_signed>
+struct BinaryLikeComparer {};
- static inline bool Compare(int type_length, const T& a, const T& b) {
- const auto* aptr = reinterpret_cast<const PtrType*>(a.ptr);
- const auto* bptr = reinterpret_cast<const PtrType*>(b.ptr);
- return std::lexicographical_compare(aptr, aptr + a.len, bptr, bptr + b.len);
+template <typename T>
+struct BinaryLikeComparer<T, /*is_signed=*/false> {
+ static bool Compare(int type_length, const T& a, const T& b) {
+ int a_length = value_length(type_length, a);
+ int b_length = value_length(type_length, b);
+ // Unsigned comparison is used for non-numeric types so straight
+ // lexiographic comparison makes sense. (a.ptr is always unsigned)....
+ return std::lexicographical_compare(a.ptr, a.ptr + a_length, b.ptr, b.ptr + b_length);
}
+};
- static T Min(int type_length, const T& a, const T& b) {
- if (a.ptr == nullptr) return b;
- if (b.ptr == nullptr) return a;
- return Compare(type_length, a, b) ? a : b;
- }
+template <typename T>
+struct BinaryLikeComparer<T, /*is_signed=*/true> {
+ static bool Compare(int type_length, const T& a, const T& b) {
+ // Is signed is used for integers encoded as big-endian twos
+ // complement integers. (e.g. decimals).
+ int a_length = value_length(type_length, a);
+ int b_length = value_length(type_length, b);
+
+ // At least of the lengths is zero.
+ if (a_length == 0 || b_length == 0) {
+ return a_length == 0 && b_length > 0;
+ }
- static T Max(int type_length, const T& a, const T& b) {
- if (a.ptr == nullptr) return b;
- if (b.ptr == nullptr) return a;
- return Compare(type_length, a, b) ? b : a;
+ int8_t first_a = *a.ptr;
+ int8_t first_b = *b.ptr;
+ // We can short circuit for different signed numbers or
+ // for equal length bytes arrays that have different first bytes.
+ if ((0x80 & first_a) != (0x80 & first_b) ||
+ (a_length == b_length && first_a != first_b)) {
+ return first_a < first_b;
+ }
+ // When the lengths are unequal and the numbers are of the same
+ // sign we need to extend the digits.
Review comment:
See comment above. I think I addressed it their.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow] emkornfield commented on a change in pull request #9582: PARQUET-1655: [C++] Fix comparison of Decimal values in statistics
Posted by GitBox <gi...@apache.org>.
emkornfield commented on a change in pull request #9582:
URL: https://github.com/apache/arrow/pull/9582#discussion_r584864172
##########
File path: cpp/src/parquet/statistics_test.cc
##########
@@ -111,21 +117,28 @@ TEST(Comparison, UnsignedByteArray) {
}
TEST(Comparison, SignedFLBA) {
- int size = 10;
+ int size = 4;
auto comparator =
MakeComparator<FLBAType>(Type::FIXED_LEN_BYTE_ARRAY, SortOrder::SIGNED, size);
- std::string s1 = "Anti123456";
- std::string s2 = "Bunkd123456";
- FLBA s1flba = FLBAFromString(s1);
- FLBA s2flba = FLBAFromString(s2);
- ASSERT_TRUE(comparator->Compare(s1flba, s2flba));
+ std::vector<uint8_t> byte_values[] = {
+ {0x80, 0, 0, 0}, {0xFF, 0xFF, 0x01, 0}, {0xFF, 0xFF, 0x80, 0},
+ {0xFF, 0xFF, 0xFF, 0x80}, {0xFF, 0xFF, 0xFF, 0xFF}, {0, 0, 0x01, 0x01},
+ {0, 0x01, 0x01, 0}, {0x01, 0x01, 0, 0}};
+ std::vector<FLBA> values_to_compare;
+ for (auto& bytes : byte_values) {
+ values_to_compare.emplace_back(FLBA(bytes.data()));
+ }
- s1 = "Bünk123456";
- s2 = "Bunk123456";
- s1flba = FLBAFromString(s1);
- s2flba = FLBAFromString(s2);
- ASSERT_TRUE(comparator->Compare(s1flba, s2flba));
+ for (size_t x = 0; x < values_to_compare.size(); x++) {
+ EXPECT_FALSE(comparator->Compare(values_to_compare[x], values_to_compare[x])) << x;
+ for (size_t y = x + 1; y < values_to_compare.size(); y++) {
+ EXPECT_TRUE(comparator->Compare(values_to_compare[x], values_to_compare[y]))
+ << x << " " << y;
+ EXPECT_FALSE(comparator->Compare(values_to_compare[y], values_to_compare[x]))
+ << y << " " << x;
+ }
+ }
Review comment:
I think for FLBA these tests should be fairly complete. the bytes can be interepreted as big-endian two's complement number. I think I need to add an additional case that covers sign extension equality from the example I gave above. Is your concern upon representation here? Or would you like me to explicitly use util::Decimal* classes for the test cases?
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow] github-actions[bot] commented on pull request #9582: PARQUET-1655: [C++] Fixed signed byte comparison
Posted by GitBox <gi...@apache.org>.
github-actions[bot] commented on pull request #9582:
URL: https://github.com/apache/arrow/pull/9582#issuecomment-786496488
<!--
Licensed to the Apache Software Foundation (ASF) under one
or more contributor license agreements. See the NOTICE file
distributed with this work for additional information
regarding copyright ownership. The ASF licenses this file
to you under the Apache License, Version 2.0 (the
"License"); you may not use this file except in compliance
with the License. You may obtain a copy of the License at
http://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing,
software distributed under the License is distributed on an
"AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
KIND, either express or implied. See the License for the
specific language governing permissions and limitations
under the License.
-->
Thanks for opening a pull request!
Could you open an issue for this pull request on JIRA?
https://issues.apache.org/jira/browse/ARROW
Then could you also rename pull request title in the following format?
ARROW-${JIRA_ID}: [${COMPONENT}] ${SUMMARY}
See also:
* [Other pull requests](https://github.com/apache/arrow/pulls/)
* [Contribution Guidelines - How to contribute patches](https://arrow.apache.org/docs/developers/contributing.html#how-to-contribute-patches)
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow] pitrou commented on a change in pull request #9582: PARQUET-1655: [C++] Fix comparison of Decimal values in statistics
Posted by GitBox <gi...@apache.org>.
pitrou commented on a change in pull request #9582:
URL: https://github.com/apache/arrow/pull/9582#discussion_r584709632
##########
File path: cpp/src/parquet/statistics.cc
##########
@@ -133,56 +136,95 @@ struct CompareHelper<Int96Type, is_signed> {
static T Max(int type_length, const T& a, const T& b) {
return Compare(0, a, b) ? b : a;
}
-}; // namespace parquet
-
-template <typename DType, bool is_signed>
-struct ByteLikeCompareHelperBase {
- using T = ByteArrayType::c_type;
- using PtrType = typename std::conditional<is_signed, int8_t, uint8_t>::type;
+};
- static T DefaultMin() { return {}; }
- static T DefaultMax() { return {}; }
- static T Coalesce(T val, T fallback) { return val; }
+template <typename T, bool is_signed>
+struct BinaryLikeComparer {};
- static inline bool Compare(int type_length, const T& a, const T& b) {
- const auto* aptr = reinterpret_cast<const PtrType*>(a.ptr);
- const auto* bptr = reinterpret_cast<const PtrType*>(b.ptr);
- return std::lexicographical_compare(aptr, aptr + a.len, bptr, bptr + b.len);
+template <typename T>
+struct BinaryLikeComparer<T, /*is_signed=*/false> {
+ static bool Compare(int type_length, const T& a, const T& b) {
+ int a_length = value_length(type_length, a);
+ int b_length = value_length(type_length, b);
+ // Unsigned comparison is used for non-numeric types so straight
+ // lexiographic comparison makes sense. (a.ptr is always unsigned)....
+ return std::lexicographical_compare(a.ptr, a.ptr + a_length, b.ptr, b.ptr + b_length);
}
+};
- static T Min(int type_length, const T& a, const T& b) {
- if (a.ptr == nullptr) return b;
- if (b.ptr == nullptr) return a;
- return Compare(type_length, a, b) ? a : b;
- }
+template <typename T>
+struct BinaryLikeComparer<T, /*is_signed=*/true> {
+ static bool Compare(int type_length, const T& a, const T& b) {
+ // Is signed is used for integers encoded as big-endian twos
+ // complement integers. (e.g. decimals).
+ int a_length = value_length(type_length, a);
+ int b_length = value_length(type_length, b);
+
+ // At least of the lengths is zero.
+ if (a_length == 0 || b_length == 0) {
+ return a_length == 0 && b_length > 0;
+ }
- static T Max(int type_length, const T& a, const T& b) {
- if (a.ptr == nullptr) return b;
- if (b.ptr == nullptr) return a;
- return Compare(type_length, a, b) ? b : a;
+ int8_t first_a = *a.ptr;
+ int8_t first_b = *b.ptr;
+ // We can short circuit for different signed numbers or
+ // for equal length bytes arrays that have different first bytes.
+ if ((0x80 & first_a) != (0x80 & first_b) ||
+ (a_length == b_length && first_a != first_b)) {
+ return first_a < first_b;
+ }
+ // When the lengths are unequal and the numbers are of the same
+ // sign we need to extend the digits.
Review comment:
I'm not sure why all this is needed. The first bytes are equal. Regardless of the sign, wouldn't it be sufficient to write e.g.:
```c++
return std::lexicographical_compare(a.ptr + 1, a.ptr + a_length, b.ptr + 1, b.ptr + b_length);
```
i.e. only the MSB in a two's complement integer needs special handling, the other bytes are ordered naturally.
##########
File path: cpp/src/parquet/statistics.cc
##########
@@ -133,56 +136,95 @@ struct CompareHelper<Int96Type, is_signed> {
static T Max(int type_length, const T& a, const T& b) {
return Compare(0, a, b) ? b : a;
}
-}; // namespace parquet
-
-template <typename DType, bool is_signed>
-struct ByteLikeCompareHelperBase {
- using T = ByteArrayType::c_type;
- using PtrType = typename std::conditional<is_signed, int8_t, uint8_t>::type;
+};
- static T DefaultMin() { return {}; }
- static T DefaultMax() { return {}; }
- static T Coalesce(T val, T fallback) { return val; }
+template <typename T, bool is_signed>
+struct BinaryLikeComparer {};
- static inline bool Compare(int type_length, const T& a, const T& b) {
- const auto* aptr = reinterpret_cast<const PtrType*>(a.ptr);
- const auto* bptr = reinterpret_cast<const PtrType*>(b.ptr);
- return std::lexicographical_compare(aptr, aptr + a.len, bptr, bptr + b.len);
+template <typename T>
+struct BinaryLikeComparer<T, /*is_signed=*/false> {
+ static bool Compare(int type_length, const T& a, const T& b) {
+ int a_length = value_length(type_length, a);
+ int b_length = value_length(type_length, b);
+ // Unsigned comparison is used for non-numeric types so straight
+ // lexiographic comparison makes sense. (a.ptr is always unsigned)....
+ return std::lexicographical_compare(a.ptr, a.ptr + a_length, b.ptr, b.ptr + b_length);
}
+};
- static T Min(int type_length, const T& a, const T& b) {
- if (a.ptr == nullptr) return b;
- if (b.ptr == nullptr) return a;
- return Compare(type_length, a, b) ? a : b;
- }
+template <typename T>
+struct BinaryLikeComparer<T, /*is_signed=*/true> {
+ static bool Compare(int type_length, const T& a, const T& b) {
+ // Is signed is used for integers encoded as big-endian twos
+ // complement integers. (e.g. decimals).
+ int a_length = value_length(type_length, a);
+ int b_length = value_length(type_length, b);
+
+ // At least of the lengths is zero.
+ if (a_length == 0 || b_length == 0) {
+ return a_length == 0 && b_length > 0;
+ }
- static T Max(int type_length, const T& a, const T& b) {
- if (a.ptr == nullptr) return b;
- if (b.ptr == nullptr) return a;
- return Compare(type_length, a, b) ? b : a;
+ int8_t first_a = *a.ptr;
+ int8_t first_b = *b.ptr;
+ // We can short circuit for different signed numbers or
+ // for equal length bytes arrays that have different first bytes.
+ if ((0x80 & first_a) != (0x80 & first_b) ||
+ (a_length == b_length && first_a != first_b)) {
+ return first_a < first_b;
+ }
Review comment:
Why can't use always short-circuit if the first bytes are unequal? Intuitively:
```c++
if (first_a != first_b) {
return (first_a ^ 0x80) < (first_b ^ 0x80);
}
```
##########
File path: cpp/src/parquet/statistics_test.cc
##########
@@ -111,21 +117,28 @@ TEST(Comparison, UnsignedByteArray) {
}
TEST(Comparison, SignedFLBA) {
- int size = 10;
+ int size = 4;
auto comparator =
MakeComparator<FLBAType>(Type::FIXED_LEN_BYTE_ARRAY, SortOrder::SIGNED, size);
- std::string s1 = "Anti123456";
- std::string s2 = "Bunkd123456";
- FLBA s1flba = FLBAFromString(s1);
- FLBA s2flba = FLBAFromString(s2);
- ASSERT_TRUE(comparator->Compare(s1flba, s2flba));
+ std::vector<uint8_t> byte_values[] = {
+ {0x80, 0, 0, 0}, {0xFF, 0xFF, 0x01, 0}, {0xFF, 0xFF, 0x80, 0},
+ {0xFF, 0xFF, 0xFF, 0x80}, {0xFF, 0xFF, 0xFF, 0xFF}, {0, 0, 0x01, 0x01},
+ {0, 0x01, 0x01, 0}, {0x01, 0x01, 0, 0}};
+ std::vector<FLBA> values_to_compare;
+ for (auto& bytes : byte_values) {
+ values_to_compare.emplace_back(FLBA(bytes.data()));
+ }
- s1 = "Bünk123456";
- s2 = "Bunk123456";
- s1flba = FLBAFromString(s1);
- s2flba = FLBAFromString(s2);
- ASSERT_TRUE(comparator->Compare(s1flba, s2flba));
+ for (size_t x = 0; x < values_to_compare.size(); x++) {
+ EXPECT_FALSE(comparator->Compare(values_to_compare[x], values_to_compare[x])) << x;
+ for (size_t y = x + 1; y < values_to_compare.size(); y++) {
+ EXPECT_TRUE(comparator->Compare(values_to_compare[x], values_to_compare[y]))
+ << x << " " << y;
+ EXPECT_FALSE(comparator->Compare(values_to_compare[y], values_to_compare[x]))
+ << y << " " << x;
+ }
+ }
Review comment:
Do these tests cover the decimal case?
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow] emkornfield commented on a change in pull request #9582: PARQUET-1655: [C++] Fix comparison of Decimal values in statistics
Posted by GitBox <gi...@apache.org>.
emkornfield commented on a change in pull request #9582:
URL: https://github.com/apache/arrow/pull/9582#discussion_r587230891
##########
File path: cpp/src/parquet/statistics_test.cc
##########
@@ -71,19 +71,25 @@ static FLBA FLBAFromString(const std::string& s) {
TEST(Comparison, SignedByteArray) {
auto comparator = MakeComparator<ByteArrayType>(Type::BYTE_ARRAY, SortOrder::SIGNED);
- std::string s1 = "12345";
- std::string s2 = "12345678";
- ByteArray s1ba = ByteArrayFromString(s1);
- ByteArray s2ba = ByteArrayFromString(s2);
- ASSERT_TRUE(comparator->Compare(s1ba, s2ba));
+ std::vector<uint8_t> byte_values[] = {
+ {0x80, 0x80, 0, 0}, {/*0xFF,*/ 0x80, 0, 0}, {/*0xFF,*/ 0xFF, 0x01, 0},
+ {/*0xFF,0xFF,*/ 0x80, 0}, {/*0xFF,0xFF,0xFF,*/ 0x80}, {/*0xFF, 0xFF, 0xFF,*/ 0xFF},
+ {/*0, 0,*/ 0x01, 0x01}, {/*0,*/ 0x01, 0x01, 0}, {0x01, 0x01, 0, 0}};
Review comment:
did something similar to this. I don't think ByteArray supports string insertion?
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow] pitrou commented on a change in pull request #9582: PARQUET-1655: [C++] Fix comparison of Decimal values in statistics
Posted by GitBox <gi...@apache.org>.
pitrou commented on a change in pull request #9582:
URL: https://github.com/apache/arrow/pull/9582#discussion_r585572255
##########
File path: cpp/src/parquet/statistics.cc
##########
@@ -133,56 +136,95 @@ struct CompareHelper<Int96Type, is_signed> {
static T Max(int type_length, const T& a, const T& b) {
return Compare(0, a, b) ? b : a;
}
-}; // namespace parquet
-
-template <typename DType, bool is_signed>
-struct ByteLikeCompareHelperBase {
- using T = ByteArrayType::c_type;
- using PtrType = typename std::conditional<is_signed, int8_t, uint8_t>::type;
+};
- static T DefaultMin() { return {}; }
- static T DefaultMax() { return {}; }
- static T Coalesce(T val, T fallback) { return val; }
+template <typename T, bool is_signed>
+struct BinaryLikeComparer {};
- static inline bool Compare(int type_length, const T& a, const T& b) {
- const auto* aptr = reinterpret_cast<const PtrType*>(a.ptr);
- const auto* bptr = reinterpret_cast<const PtrType*>(b.ptr);
- return std::lexicographical_compare(aptr, aptr + a.len, bptr, bptr + b.len);
+template <typename T>
+struct BinaryLikeComparer<T, /*is_signed=*/false> {
+ static bool Compare(int type_length, const T& a, const T& b) {
+ int a_length = value_length(type_length, a);
+ int b_length = value_length(type_length, b);
+ // Unsigned comparison is used for non-numeric types so straight
+ // lexiographic comparison makes sense. (a.ptr is always unsigned)....
+ return std::lexicographical_compare(a.ptr, a.ptr + a_length, b.ptr, b.ptr + b_length);
}
+};
- static T Min(int type_length, const T& a, const T& b) {
- if (a.ptr == nullptr) return b;
- if (b.ptr == nullptr) return a;
- return Compare(type_length, a, b) ? a : b;
- }
+template <typename T>
+struct BinaryLikeComparer<T, /*is_signed=*/true> {
+ static bool Compare(int type_length, const T& a, const T& b) {
+ // Is signed is used for integers encoded as big-endian twos
+ // complement integers. (e.g. decimals).
+ int a_length = value_length(type_length, a);
+ int b_length = value_length(type_length, b);
+
+ // At least of the lengths is zero.
+ if (a_length == 0 || b_length == 0) {
+ return a_length == 0 && b_length > 0;
+ }
- static T Max(int type_length, const T& a, const T& b) {
- if (a.ptr == nullptr) return b;
- if (b.ptr == nullptr) return a;
- return Compare(type_length, a, b) ? b : a;
+ int8_t first_a = *a.ptr;
+ int8_t first_b = *b.ptr;
+ // We can short circuit for different signed numbers or
+ // for equal length bytes arrays that have different first bytes.
+ if ((0x80 & first_a) != (0x80 & first_b) ||
+ (a_length == b_length && first_a != first_b)) {
+ return first_a < first_b;
+ }
+ // When the lengths are unequal and the numbers are of the same
+ // sign we need to extend the digits.
+ const uint8_t* a_start = a.ptr;
+ const uint8_t* b_start = b.ptr;
+ if (a_length != b_length) {
+ const uint8_t* lead_start = nullptr;
+ const uint8_t* lead_end = nullptr;
+ if (a_length > b_length) {
+ int lead_length = a_length - b_length;
+ lead_start = a.ptr;
+ lead_end = a.ptr + lead_length;
+ a_start += lead_length;
+ } else {
+ DCHECK_LT(a_length, b_length);
+ int lead_length = b_length - a_length;
+ lead_start = b.ptr;
+ lead_end = b.ptr + lead_length;
+ b_start += lead_length;
+ }
+ // Compare extra bytes to the sign extension of the first
+ // byte of the other number.
+ uint8_t extension = first_a < 0 ? 0xFF : 0;
+ for (; lead_start != lead_end; lead_start++) {
+ if (*lead_start < extension) {
+ // The first bytes of the long value are less
+ // then the extended short one. So if a is the long value
+ // we can return true.
+ return a_length > b_length;
+ } else if (*lead_start > extension) {
Review comment:
Same here: if `extension` is 0xFF then this is never possible?
So perhaps it's possible to rewrite this:
```c++
if (first_a < 0) {
// Both numbers negative
for (; lead_start != lead_end; lead_start++) {
if (*lead_start != 0xff) {
return a_length > b_length;
}
}
} else {
// Both numbers positive
for (; lead_start != lead_end; lead_start++) {
if (*lead_start != 0) {
return a_length < b_length;
}
}
}
```
Note sure which one is more understandable.
##########
File path: cpp/src/parquet/statistics_test.cc
##########
@@ -71,19 +71,25 @@ static FLBA FLBAFromString(const std::string& s) {
TEST(Comparison, SignedByteArray) {
auto comparator = MakeComparator<ByteArrayType>(Type::BYTE_ARRAY, SortOrder::SIGNED);
- std::string s1 = "12345";
- std::string s2 = "12345678";
- ByteArray s1ba = ByteArrayFromString(s1);
- ByteArray s2ba = ByteArrayFromString(s2);
- ASSERT_TRUE(comparator->Compare(s1ba, s2ba));
+ std::vector<uint8_t> byte_values[] = {
+ {0x80, 0x80, 0, 0}, {/*0xFF,*/ 0x80, 0, 0}, {/*0xFF,*/ 0xFF, 0x01, 0},
+ {/*0xFF,0xFF,*/ 0x80, 0}, {/*0xFF,0xFF,0xFF,*/ 0x80}, {/*0xFF, 0xFF, 0xFF,*/ 0xFF},
+ {/*0, 0,*/ 0x01, 0x01}, {/*0,*/ 0x01, 0x01, 0}, {0x01, 0x01, 0, 0}};
Review comment:
Can you also test pairs of equal values with differing lengths?
Perhaps even do exhaustive pairwise comparisons, e.g.:
```c++
struct Case {
std::vector<uint8_t> bytes;
int order;
};
std::vector<Case> cases[] = {
{{0x80, 0x80, 0, 0}, 1},
{{0xFF, 0x80, 0x80, 0, 0}, 1},
{{0x80, 0, 0}, 2},
{{0xFF, 0x80, 0, 0}, 2},
{{0xFF, 0xFF, 0x80, 0, 0}, 2},
{{0xFF, 0x01, 0}, 3},
{{0xFF, 0xFF, 0x01, 0}, 3},
// ...
};
for (const auto& a : cases) {
for (const auto& b : cases) {
ByteArray ba(static_cast<int>(a.bytes.size()), a.bytes.data()));
ByteArray bb(static_cast<int>(b.bytes.size()), b.bytes.data()));
if (a.order < b.order) {
EXPECT_TRUE(comparator->Compare(ba, bb)) << ba << " " << bb;
} else {
EXPECT_FALSE(comparator->Compare(ba, bb)) << ba << " " << bb;
}
}
}
```
##########
File path: cpp/src/parquet/statistics.cc
##########
@@ -133,56 +136,95 @@ struct CompareHelper<Int96Type, is_signed> {
static T Max(int type_length, const T& a, const T& b) {
return Compare(0, a, b) ? b : a;
}
-}; // namespace parquet
-
-template <typename DType, bool is_signed>
-struct ByteLikeCompareHelperBase {
- using T = ByteArrayType::c_type;
- using PtrType = typename std::conditional<is_signed, int8_t, uint8_t>::type;
+};
- static T DefaultMin() { return {}; }
- static T DefaultMax() { return {}; }
- static T Coalesce(T val, T fallback) { return val; }
+template <typename T, bool is_signed>
+struct BinaryLikeComparer {};
- static inline bool Compare(int type_length, const T& a, const T& b) {
- const auto* aptr = reinterpret_cast<const PtrType*>(a.ptr);
- const auto* bptr = reinterpret_cast<const PtrType*>(b.ptr);
- return std::lexicographical_compare(aptr, aptr + a.len, bptr, bptr + b.len);
+template <typename T>
+struct BinaryLikeComparer<T, /*is_signed=*/false> {
+ static bool Compare(int type_length, const T& a, const T& b) {
+ int a_length = value_length(type_length, a);
+ int b_length = value_length(type_length, b);
+ // Unsigned comparison is used for non-numeric types so straight
+ // lexiographic comparison makes sense. (a.ptr is always unsigned)....
+ return std::lexicographical_compare(a.ptr, a.ptr + a_length, b.ptr, b.ptr + b_length);
}
+};
- static T Min(int type_length, const T& a, const T& b) {
- if (a.ptr == nullptr) return b;
- if (b.ptr == nullptr) return a;
- return Compare(type_length, a, b) ? a : b;
- }
+template <typename T>
+struct BinaryLikeComparer<T, /*is_signed=*/true> {
+ static bool Compare(int type_length, const T& a, const T& b) {
+ // Is signed is used for integers encoded as big-endian twos
+ // complement integers. (e.g. decimals).
+ int a_length = value_length(type_length, a);
+ int b_length = value_length(type_length, b);
+
+ // At least of the lengths is zero.
+ if (a_length == 0 || b_length == 0) {
+ return a_length == 0 && b_length > 0;
+ }
- static T Max(int type_length, const T& a, const T& b) {
- if (a.ptr == nullptr) return b;
- if (b.ptr == nullptr) return a;
- return Compare(type_length, a, b) ? b : a;
+ int8_t first_a = *a.ptr;
+ int8_t first_b = *b.ptr;
+ // We can short circuit for different signed numbers or
+ // for equal length bytes arrays that have different first bytes.
+ if ((0x80 & first_a) != (0x80 & first_b) ||
+ (a_length == b_length && first_a != first_b)) {
+ return first_a < first_b;
+ }
Review comment:
Ok, I understand and your assessment looks correct to me. Can you just add a bit more explanations as comments, so this doesn't produce too much head-scratching later on? :-)
##########
File path: cpp/src/parquet/statistics.cc
##########
@@ -133,56 +136,95 @@ struct CompareHelper<Int96Type, is_signed> {
static T Max(int type_length, const T& a, const T& b) {
return Compare(0, a, b) ? b : a;
}
-}; // namespace parquet
-
-template <typename DType, bool is_signed>
-struct ByteLikeCompareHelperBase {
- using T = ByteArrayType::c_type;
- using PtrType = typename std::conditional<is_signed, int8_t, uint8_t>::type;
+};
- static T DefaultMin() { return {}; }
- static T DefaultMax() { return {}; }
- static T Coalesce(T val, T fallback) { return val; }
+template <typename T, bool is_signed>
+struct BinaryLikeComparer {};
- static inline bool Compare(int type_length, const T& a, const T& b) {
- const auto* aptr = reinterpret_cast<const PtrType*>(a.ptr);
- const auto* bptr = reinterpret_cast<const PtrType*>(b.ptr);
- return std::lexicographical_compare(aptr, aptr + a.len, bptr, bptr + b.len);
+template <typename T>
+struct BinaryLikeComparer<T, /*is_signed=*/false> {
+ static bool Compare(int type_length, const T& a, const T& b) {
+ int a_length = value_length(type_length, a);
+ int b_length = value_length(type_length, b);
+ // Unsigned comparison is used for non-numeric types so straight
+ // lexiographic comparison makes sense. (a.ptr is always unsigned)....
+ return std::lexicographical_compare(a.ptr, a.ptr + a_length, b.ptr, b.ptr + b_length);
}
+};
- static T Min(int type_length, const T& a, const T& b) {
- if (a.ptr == nullptr) return b;
- if (b.ptr == nullptr) return a;
- return Compare(type_length, a, b) ? a : b;
- }
+template <typename T>
+struct BinaryLikeComparer<T, /*is_signed=*/true> {
+ static bool Compare(int type_length, const T& a, const T& b) {
+ // Is signed is used for integers encoded as big-endian twos
+ // complement integers. (e.g. decimals).
+ int a_length = value_length(type_length, a);
+ int b_length = value_length(type_length, b);
+
+ // At least of the lengths is zero.
+ if (a_length == 0 || b_length == 0) {
+ return a_length == 0 && b_length > 0;
+ }
- static T Max(int type_length, const T& a, const T& b) {
- if (a.ptr == nullptr) return b;
- if (b.ptr == nullptr) return a;
- return Compare(type_length, a, b) ? b : a;
+ int8_t first_a = *a.ptr;
+ int8_t first_b = *b.ptr;
+ // We can short circuit for different signed numbers or
+ // for equal length bytes arrays that have different first bytes.
+ if ((0x80 & first_a) != (0x80 & first_b) ||
+ (a_length == b_length && first_a != first_b)) {
+ return first_a < first_b;
+ }
+ // When the lengths are unequal and the numbers are of the same
+ // sign we need to extend the digits.
+ const uint8_t* a_start = a.ptr;
+ const uint8_t* b_start = b.ptr;
+ if (a_length != b_length) {
+ const uint8_t* lead_start = nullptr;
+ const uint8_t* lead_end = nullptr;
+ if (a_length > b_length) {
+ int lead_length = a_length - b_length;
+ lead_start = a.ptr;
+ lead_end = a.ptr + lead_length;
+ a_start += lead_length;
+ } else {
+ DCHECK_LT(a_length, b_length);
+ int lead_length = b_length - a_length;
+ lead_start = b.ptr;
+ lead_end = b.ptr + lead_length;
+ b_start += lead_length;
+ }
+ // Compare extra bytes to the sign extension of the first
+ // byte of the other number.
+ uint8_t extension = first_a < 0 ? 0xFF : 0;
+ for (; lead_start != lead_end; lead_start++) {
+ if (*lead_start < extension) {
Review comment:
If `extension` is 0 then this is never possible, right?
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow] pitrou commented on a change in pull request #9582: PARQUET-1655: [C++] Fix comparison of Decimal values in statistics
Posted by GitBox <gi...@apache.org>.
pitrou commented on a change in pull request #9582:
URL: https://github.com/apache/arrow/pull/9582#discussion_r585569492
##########
File path: cpp/src/parquet/statistics_test.cc
##########
@@ -111,21 +117,28 @@ TEST(Comparison, UnsignedByteArray) {
}
TEST(Comparison, SignedFLBA) {
- int size = 10;
+ int size = 4;
auto comparator =
MakeComparator<FLBAType>(Type::FIXED_LEN_BYTE_ARRAY, SortOrder::SIGNED, size);
- std::string s1 = "Anti123456";
- std::string s2 = "Bunkd123456";
- FLBA s1flba = FLBAFromString(s1);
- FLBA s2flba = FLBAFromString(s2);
- ASSERT_TRUE(comparator->Compare(s1flba, s2flba));
+ std::vector<uint8_t> byte_values[] = {
+ {0x80, 0, 0, 0}, {0xFF, 0xFF, 0x01, 0}, {0xFF, 0xFF, 0x80, 0},
+ {0xFF, 0xFF, 0xFF, 0x80}, {0xFF, 0xFF, 0xFF, 0xFF}, {0, 0, 0x01, 0x01},
+ {0, 0x01, 0x01, 0}, {0x01, 0x01, 0, 0}};
+ std::vector<FLBA> values_to_compare;
+ for (auto& bytes : byte_values) {
+ values_to_compare.emplace_back(FLBA(bytes.data()));
+ }
- s1 = "Bünk123456";
- s2 = "Bunk123456";
- s1flba = FLBAFromString(s1);
- s2flba = FLBAFromString(s2);
- ASSERT_TRUE(comparator->Compare(s1flba, s2flba));
+ for (size_t x = 0; x < values_to_compare.size(); x++) {
+ EXPECT_FALSE(comparator->Compare(values_to_compare[x], values_to_compare[x])) << x;
+ for (size_t y = x + 1; y < values_to_compare.size(); y++) {
+ EXPECT_TRUE(comparator->Compare(values_to_compare[x], values_to_compare[y]))
+ << x << " " << y;
+ EXPECT_FALSE(comparator->Compare(values_to_compare[y], values_to_compare[x]))
+ << y << " " << x;
+ }
+ }
Review comment:
I was merely wondering if we're sure that decimal columns trigger the code paths under test. But I'll trust you that it's the case :-)
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow] github-actions[bot] commented on pull request #9582: PARQUET-1655: [C++] Fixed signed byte comparison
Posted by GitBox <gi...@apache.org>.
github-actions[bot] commented on pull request #9582:
URL: https://github.com/apache/arrow/pull/9582#issuecomment-786905589
https://issues.apache.org/jira/browse/PARQUET-1655
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow] emkornfield commented on a change in pull request #9582: PARQUET-1655: [C++] Fix comparison of Decimal values in statistics
Posted by GitBox <gi...@apache.org>.
emkornfield commented on a change in pull request #9582:
URL: https://github.com/apache/arrow/pull/9582#discussion_r584862144
##########
File path: cpp/src/parquet/statistics.cc
##########
@@ -133,56 +136,95 @@ struct CompareHelper<Int96Type, is_signed> {
static T Max(int type_length, const T& a, const T& b) {
return Compare(0, a, b) ? b : a;
}
-}; // namespace parquet
-
-template <typename DType, bool is_signed>
-struct ByteLikeCompareHelperBase {
- using T = ByteArrayType::c_type;
- using PtrType = typename std::conditional<is_signed, int8_t, uint8_t>::type;
+};
- static T DefaultMin() { return {}; }
- static T DefaultMax() { return {}; }
- static T Coalesce(T val, T fallback) { return val; }
+template <typename T, bool is_signed>
+struct BinaryLikeComparer {};
- static inline bool Compare(int type_length, const T& a, const T& b) {
- const auto* aptr = reinterpret_cast<const PtrType*>(a.ptr);
- const auto* bptr = reinterpret_cast<const PtrType*>(b.ptr);
- return std::lexicographical_compare(aptr, aptr + a.len, bptr, bptr + b.len);
+template <typename T>
+struct BinaryLikeComparer<T, /*is_signed=*/false> {
+ static bool Compare(int type_length, const T& a, const T& b) {
+ int a_length = value_length(type_length, a);
+ int b_length = value_length(type_length, b);
+ // Unsigned comparison is used for non-numeric types so straight
+ // lexiographic comparison makes sense. (a.ptr is always unsigned)....
+ return std::lexicographical_compare(a.ptr, a.ptr + a_length, b.ptr, b.ptr + b_length);
}
+};
- static T Min(int type_length, const T& a, const T& b) {
- if (a.ptr == nullptr) return b;
- if (b.ptr == nullptr) return a;
- return Compare(type_length, a, b) ? a : b;
- }
+template <typename T>
+struct BinaryLikeComparer<T, /*is_signed=*/true> {
+ static bool Compare(int type_length, const T& a, const T& b) {
+ // Is signed is used for integers encoded as big-endian twos
+ // complement integers. (e.g. decimals).
+ int a_length = value_length(type_length, a);
+ int b_length = value_length(type_length, b);
+
+ // At least of the lengths is zero.
+ if (a_length == 0 || b_length == 0) {
+ return a_length == 0 && b_length > 0;
+ }
- static T Max(int type_length, const T& a, const T& b) {
- if (a.ptr == nullptr) return b;
- if (b.ptr == nullptr) return a;
- return Compare(type_length, a, b) ? b : a;
+ int8_t first_a = *a.ptr;
+ int8_t first_b = *b.ptr;
+ // We can short circuit for different signed numbers or
+ // for equal length bytes arrays that have different first bytes.
+ if ((0x80 & first_a) != (0x80 & first_b) ||
+ (a_length == b_length && first_a != first_b)) {
+ return first_a < first_b;
+ }
Review comment:
It is not entirely clear to me all potential use cases for this, so this is somewhat defensive. Decimals can be encoded either variable width or fixed width within a parquet file. Simply comparing the first bytes fails when sign extending values. For instance `0xFF80` and `0x80` are equal. This scenario seems like it could arise in two cases:
1. Trying to compare statistics in encoded form between a a fixed width encoded decimal column and a variable length encoded column (likely from two separate files).
2. The specification only says `The minimum number of bytes to store the unscaled value should be used.` since this isn't a "must" I could image some implementations doing something wacky here still be in compliance.
The first scenario seems more likely but still potentially rare for this code to hit in practice but like I said I'm being defensive. If this reasoning seems correct to you, I can add a comment to this affect. I can also remove the code but I think that might lead to bugs down the road (I quickly checked the java implementation and it looks like they have a notion of sign extension also.
A third option is we could still short-circuit if neither first byte corresponded to a sign extended value (I would need to think about it, but I think this would would work).
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow] emkornfield commented on pull request #9582: PARQUET-1655: [C++] Fix comparison of Decimal values in statistics
Posted by GitBox <gi...@apache.org>.
emkornfield commented on pull request #9582:
URL: https://github.com/apache/arrow/pull/9582#issuecomment-790754904
I thought there should be assert scalar equals but I was expecting it to be a macro which is why I think I missed it
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow] pitrou closed pull request #9582: PARQUET-1655: [C++] Fix comparison of Decimal values in statistics
Posted by GitBox <gi...@apache.org>.
pitrou closed pull request #9582:
URL: https://github.com/apache/arrow/pull/9582
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow] emkornfield commented on pull request #9582: PARQUET-1655: [C++] Fix comparison of Decimal values in statistics
Posted by GitBox <gi...@apache.org>.
emkornfield commented on pull request #9582:
URL: https://github.com/apache/arrow/pull/9582#issuecomment-790405647
@pitrou I think I addressed all of your comments, would you mind taking another look?
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow] emkornfield commented on a change in pull request #9582: PARQUET-1655: [C++] Fix comparison of Decimal values in statistics
Posted by GitBox <gi...@apache.org>.
emkornfield commented on a change in pull request #9582:
URL: https://github.com/apache/arrow/pull/9582#discussion_r587234738
##########
File path: cpp/src/parquet/statistics_test.cc
##########
@@ -111,21 +117,28 @@ TEST(Comparison, UnsignedByteArray) {
}
TEST(Comparison, SignedFLBA) {
- int size = 10;
+ int size = 4;
auto comparator =
MakeComparator<FLBAType>(Type::FIXED_LEN_BYTE_ARRAY, SortOrder::SIGNED, size);
- std::string s1 = "Anti123456";
- std::string s2 = "Bunkd123456";
- FLBA s1flba = FLBAFromString(s1);
- FLBA s2flba = FLBAFromString(s2);
- ASSERT_TRUE(comparator->Compare(s1flba, s2flba));
+ std::vector<uint8_t> byte_values[] = {
+ {0x80, 0, 0, 0}, {0xFF, 0xFF, 0x01, 0}, {0xFF, 0xFF, 0x80, 0},
+ {0xFF, 0xFF, 0xFF, 0x80}, {0xFF, 0xFF, 0xFF, 0xFF}, {0, 0, 0x01, 0x01},
+ {0, 0x01, 0x01, 0}, {0x01, 0x01, 0, 0}};
+ std::vector<FLBA> values_to_compare;
+ for (auto& bytes : byte_values) {
+ values_to_compare.emplace_back(FLBA(bytes.data()));
+ }
- s1 = "Bünk123456";
- s2 = "Bunk123456";
- s1flba = FLBAFromString(s1);
- s2flba = FLBAFromString(s2);
- ASSERT_TRUE(comparator->Compare(s1flba, s2flba));
+ for (size_t x = 0; x < values_to_compare.size(); x++) {
+ EXPECT_FALSE(comparator->Compare(values_to_compare[x], values_to_compare[x])) << x;
+ for (size_t y = x + 1; y < values_to_compare.size(); y++) {
+ EXPECT_TRUE(comparator->Compare(values_to_compare[x], values_to_compare[y]))
+ << x << " " << y;
+ EXPECT_FALSE(comparator->Compare(values_to_compare[y], values_to_compare[x]))
+ << y << " " << x;
+ }
+ }
Review comment:
you probably shouldn't trust me. I added a test when writing a column of Decimal128 values to arrow_reader_writer_test which failed without this change. This required fixing some cases with extracting scalar values and there are still some broken aspects to the extraction. I'll open up some JIRAs to fix these:
1. Decimals encoded as Ints aren't extracted correctly.
2. The decimal type chosen might not correspond to the decoded decimal type because we don't pass the arrow schema information through to the decoding. (i.e. we depend solely on precision for deciding Decimal128Scalar or Decimal256Scalar).
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow] pitrou commented on a change in pull request #9582: PARQUET-1655: [C++] Fix comparison of Decimal values in statistics
Posted by GitBox <gi...@apache.org>.
pitrou commented on a change in pull request #9582:
URL: https://github.com/apache/arrow/pull/9582#discussion_r587428039
##########
File path: cpp/src/parquet/statistics.cc
##########
@@ -133,56 +136,95 @@ struct CompareHelper<Int96Type, is_signed> {
static T Max(int type_length, const T& a, const T& b) {
return Compare(0, a, b) ? b : a;
}
-}; // namespace parquet
-
-template <typename DType, bool is_signed>
-struct ByteLikeCompareHelperBase {
- using T = ByteArrayType::c_type;
- using PtrType = typename std::conditional<is_signed, int8_t, uint8_t>::type;
+};
- static T DefaultMin() { return {}; }
- static T DefaultMax() { return {}; }
- static T Coalesce(T val, T fallback) { return val; }
+template <typename T, bool is_signed>
+struct BinaryLikeComparer {};
- static inline bool Compare(int type_length, const T& a, const T& b) {
- const auto* aptr = reinterpret_cast<const PtrType*>(a.ptr);
- const auto* bptr = reinterpret_cast<const PtrType*>(b.ptr);
- return std::lexicographical_compare(aptr, aptr + a.len, bptr, bptr + b.len);
+template <typename T>
+struct BinaryLikeComparer<T, /*is_signed=*/false> {
+ static bool Compare(int type_length, const T& a, const T& b) {
+ int a_length = value_length(type_length, a);
+ int b_length = value_length(type_length, b);
+ // Unsigned comparison is used for non-numeric types so straight
+ // lexiographic comparison makes sense. (a.ptr is always unsigned)....
+ return std::lexicographical_compare(a.ptr, a.ptr + a_length, b.ptr, b.ptr + b_length);
}
+};
- static T Min(int type_length, const T& a, const T& b) {
- if (a.ptr == nullptr) return b;
- if (b.ptr == nullptr) return a;
- return Compare(type_length, a, b) ? a : b;
- }
+template <typename T>
+struct BinaryLikeComparer<T, /*is_signed=*/true> {
+ static bool Compare(int type_length, const T& a, const T& b) {
+ // Is signed is used for integers encoded as big-endian twos
+ // complement integers. (e.g. decimals).
+ int a_length = value_length(type_length, a);
+ int b_length = value_length(type_length, b);
+
+ // At least of the lengths is zero.
+ if (a_length == 0 || b_length == 0) {
+ return a_length == 0 && b_length > 0;
+ }
- static T Max(int type_length, const T& a, const T& b) {
- if (a.ptr == nullptr) return b;
- if (b.ptr == nullptr) return a;
- return Compare(type_length, a, b) ? b : a;
+ int8_t first_a = *a.ptr;
+ int8_t first_b = *b.ptr;
+ // We can short circuit for different signed numbers or
+ // for equal length bytes arrays that have different first bytes.
+ if ((0x80 & first_a) != (0x80 & first_b) ||
+ (a_length == b_length && first_a != first_b)) {
+ return first_a < first_b;
+ }
+ // When the lengths are unequal and the numbers are of the same
+ // sign we need to extend the digits.
+ const uint8_t* a_start = a.ptr;
+ const uint8_t* b_start = b.ptr;
+ if (a_length != b_length) {
+ const uint8_t* lead_start = nullptr;
+ const uint8_t* lead_end = nullptr;
+ if (a_length > b_length) {
+ int lead_length = a_length - b_length;
+ lead_start = a.ptr;
+ lead_end = a.ptr + lead_length;
+ a_start += lead_length;
+ } else {
+ DCHECK_LT(a_length, b_length);
+ int lead_length = b_length - a_length;
+ lead_start = b.ptr;
+ lead_end = b.ptr + lead_length;
+ b_start += lead_length;
+ }
+ // Compare extra bytes to the sign extension of the first
+ // byte of the other number.
+ uint8_t extension = first_a < 0 ? 0xFF : 0;
+ for (; lead_start != lead_end; lead_start++) {
+ if (*lead_start < extension) {
+ // The first bytes of the long value are less
+ // then the extended short one. So if a is the long value
+ // we can return true.
+ return a_length > b_length;
+ } else if (*lead_start > extension) {
Review comment:
Yes, thank you.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow] emkornfield commented on a change in pull request #9582: PARQUET-1655: [C++] Fix comparison of Decimal values in statistics
Posted by GitBox <gi...@apache.org>.
emkornfield commented on a change in pull request #9582:
URL: https://github.com/apache/arrow/pull/9582#discussion_r587233240
##########
File path: cpp/src/parquet/statistics.cc
##########
@@ -133,56 +136,95 @@ struct CompareHelper<Int96Type, is_signed> {
static T Max(int type_length, const T& a, const T& b) {
return Compare(0, a, b) ? b : a;
}
-}; // namespace parquet
-
-template <typename DType, bool is_signed>
-struct ByteLikeCompareHelperBase {
- using T = ByteArrayType::c_type;
- using PtrType = typename std::conditional<is_signed, int8_t, uint8_t>::type;
+};
- static T DefaultMin() { return {}; }
- static T DefaultMax() { return {}; }
- static T Coalesce(T val, T fallback) { return val; }
+template <typename T, bool is_signed>
+struct BinaryLikeComparer {};
- static inline bool Compare(int type_length, const T& a, const T& b) {
- const auto* aptr = reinterpret_cast<const PtrType*>(a.ptr);
- const auto* bptr = reinterpret_cast<const PtrType*>(b.ptr);
- return std::lexicographical_compare(aptr, aptr + a.len, bptr, bptr + b.len);
+template <typename T>
+struct BinaryLikeComparer<T, /*is_signed=*/false> {
+ static bool Compare(int type_length, const T& a, const T& b) {
+ int a_length = value_length(type_length, a);
+ int b_length = value_length(type_length, b);
+ // Unsigned comparison is used for non-numeric types so straight
+ // lexiographic comparison makes sense. (a.ptr is always unsigned)....
+ return std::lexicographical_compare(a.ptr, a.ptr + a_length, b.ptr, b.ptr + b_length);
}
+};
- static T Min(int type_length, const T& a, const T& b) {
- if (a.ptr == nullptr) return b;
- if (b.ptr == nullptr) return a;
- return Compare(type_length, a, b) ? a : b;
- }
+template <typename T>
+struct BinaryLikeComparer<T, /*is_signed=*/true> {
+ static bool Compare(int type_length, const T& a, const T& b) {
+ // Is signed is used for integers encoded as big-endian twos
+ // complement integers. (e.g. decimals).
+ int a_length = value_length(type_length, a);
+ int b_length = value_length(type_length, b);
+
+ // At least of the lengths is zero.
+ if (a_length == 0 || b_length == 0) {
+ return a_length == 0 && b_length > 0;
+ }
- static T Max(int type_length, const T& a, const T& b) {
- if (a.ptr == nullptr) return b;
- if (b.ptr == nullptr) return a;
- return Compare(type_length, a, b) ? b : a;
+ int8_t first_a = *a.ptr;
+ int8_t first_b = *b.ptr;
+ // We can short circuit for different signed numbers or
+ // for equal length bytes arrays that have different first bytes.
+ if ((0x80 & first_a) != (0x80 & first_b) ||
+ (a_length == b_length && first_a != first_b)) {
+ return first_a < first_b;
+ }
Review comment:
Added the example above. I can add more of the explanation if you think it is worthwhile.
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow] pitrou commented on a change in pull request #9582: PARQUET-1655: [C++] Fix comparison of Decimal values in statistics
Posted by GitBox <gi...@apache.org>.
pitrou commented on a change in pull request #9582:
URL: https://github.com/apache/arrow/pull/9582#discussion_r587423364
##########
File path: cpp/src/parquet/arrow/arrow_reader_writer_test.cc
##########
@@ -2673,6 +2673,36 @@ TEST(ArrowReadWrite, Decimal256) {
CheckSimpleRoundtrip(table, 2, props_store_schema);
}
+TEST(ArrowReadWrite, DecimalStats) {
+ using ::arrow::Decimal128;
+ using ::arrow::field;
+
+ auto type = ::arrow::decimal128(/*precision=*/8, /*scale=*/0);
+
+ const char* json = R"(["255", "128", null, "0", "1", "-127", "-128", "-129", "-255"])";
+ auto array = ::arrow::ArrayFromJSON(type, json);
+ auto table = ::arrow::Table::Make(::arrow::schema({field("root", type)}), {array});
+
+ std::shared_ptr<Buffer> buffer;
+ ASSERT_NO_FATAL_FAILURE(WriteTableToBuffer(table, /*row_grop_size=*/100,
+ default_arrow_writer_properties(), &buffer));
+
+ std::unique_ptr<FileReader> reader;
+ ASSERT_OK_NO_THROW(OpenFile(std::make_shared<BufferReader>(buffer),
+ ::arrow::default_memory_pool(), &reader));
+
+ std::shared_ptr<Scalar> min, max;
+ ReadSingleColumnFileStatistics(std::move(reader), &min, &max);
+
+ std::shared_ptr<Scalar> expected_min, expected_max;
+ ASSERT_OK_AND_ASSIGN(expected_min, array->GetScalar(array->length() - 1));
+ ASSERT_OK_AND_ASSIGN(expected_max, array->GetScalar(0));
+ ASSERT_TRUE(expected_min->Equals(*min))
Review comment:
I think we have `AssertScalarsEqual`?
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow] pitrou commented on a change in pull request #9582: PARQUET-1655: [C++] Fix comparison of Decimal values in statistics
Posted by GitBox <gi...@apache.org>.
pitrou commented on a change in pull request #9582:
URL: https://github.com/apache/arrow/pull/9582#discussion_r584992780
##########
File path: cpp/src/parquet/statistics.cc
##########
@@ -133,56 +136,95 @@ struct CompareHelper<Int96Type, is_signed> {
static T Max(int type_length, const T& a, const T& b) {
return Compare(0, a, b) ? b : a;
}
-}; // namespace parquet
-
-template <typename DType, bool is_signed>
-struct ByteLikeCompareHelperBase {
- using T = ByteArrayType::c_type;
- using PtrType = typename std::conditional<is_signed, int8_t, uint8_t>::type;
+};
- static T DefaultMin() { return {}; }
- static T DefaultMax() { return {}; }
- static T Coalesce(T val, T fallback) { return val; }
+template <typename T, bool is_signed>
+struct BinaryLikeComparer {};
- static inline bool Compare(int type_length, const T& a, const T& b) {
- const auto* aptr = reinterpret_cast<const PtrType*>(a.ptr);
- const auto* bptr = reinterpret_cast<const PtrType*>(b.ptr);
- return std::lexicographical_compare(aptr, aptr + a.len, bptr, bptr + b.len);
+template <typename T>
+struct BinaryLikeComparer<T, /*is_signed=*/false> {
+ static bool Compare(int type_length, const T& a, const T& b) {
+ int a_length = value_length(type_length, a);
+ int b_length = value_length(type_length, b);
+ // Unsigned comparison is used for non-numeric types so straight
+ // lexiographic comparison makes sense. (a.ptr is always unsigned)....
+ return std::lexicographical_compare(a.ptr, a.ptr + a_length, b.ptr, b.ptr + b_length);
}
+};
- static T Min(int type_length, const T& a, const T& b) {
- if (a.ptr == nullptr) return b;
- if (b.ptr == nullptr) return a;
- return Compare(type_length, a, b) ? a : b;
- }
+template <typename T>
+struct BinaryLikeComparer<T, /*is_signed=*/true> {
+ static bool Compare(int type_length, const T& a, const T& b) {
+ // Is signed is used for integers encoded as big-endian twos
+ // complement integers. (e.g. decimals).
+ int a_length = value_length(type_length, a);
+ int b_length = value_length(type_length, b);
+
+ // At least of the lengths is zero.
+ if (a_length == 0 || b_length == 0) {
+ return a_length == 0 && b_length > 0;
+ }
- static T Max(int type_length, const T& a, const T& b) {
- if (a.ptr == nullptr) return b;
- if (b.ptr == nullptr) return a;
- return Compare(type_length, a, b) ? b : a;
+ int8_t first_a = *a.ptr;
+ int8_t first_b = *b.ptr;
+ // We can short circuit for different signed numbers or
+ // for equal length bytes arrays that have different first bytes.
+ if ((0x80 & first_a) != (0x80 & first_b) ||
+ (a_length == b_length && first_a != first_b)) {
+ return first_a < first_b;
+ }
Review comment:
Hmm, I see. I'll take a closer look :-)
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
[GitHub] [arrow] emkornfield commented on a change in pull request #9582: PARQUET-1655: [C++] Fix comparison of Decimal values in statistics
Posted by GitBox <gi...@apache.org>.
emkornfield commented on a change in pull request #9582:
URL: https://github.com/apache/arrow/pull/9582#discussion_r587235073
##########
File path: cpp/src/parquet/statistics.cc
##########
@@ -133,56 +136,95 @@ struct CompareHelper<Int96Type, is_signed> {
static T Max(int type_length, const T& a, const T& b) {
return Compare(0, a, b) ? b : a;
}
-}; // namespace parquet
-
-template <typename DType, bool is_signed>
-struct ByteLikeCompareHelperBase {
- using T = ByteArrayType::c_type;
- using PtrType = typename std::conditional<is_signed, int8_t, uint8_t>::type;
+};
- static T DefaultMin() { return {}; }
- static T DefaultMax() { return {}; }
- static T Coalesce(T val, T fallback) { return val; }
+template <typename T, bool is_signed>
+struct BinaryLikeComparer {};
- static inline bool Compare(int type_length, const T& a, const T& b) {
- const auto* aptr = reinterpret_cast<const PtrType*>(a.ptr);
- const auto* bptr = reinterpret_cast<const PtrType*>(b.ptr);
- return std::lexicographical_compare(aptr, aptr + a.len, bptr, bptr + b.len);
+template <typename T>
+struct BinaryLikeComparer<T, /*is_signed=*/false> {
+ static bool Compare(int type_length, const T& a, const T& b) {
+ int a_length = value_length(type_length, a);
+ int b_length = value_length(type_length, b);
+ // Unsigned comparison is used for non-numeric types so straight
+ // lexiographic comparison makes sense. (a.ptr is always unsigned)....
+ return std::lexicographical_compare(a.ptr, a.ptr + a_length, b.ptr, b.ptr + b_length);
}
+};
- static T Min(int type_length, const T& a, const T& b) {
- if (a.ptr == nullptr) return b;
- if (b.ptr == nullptr) return a;
- return Compare(type_length, a, b) ? a : b;
- }
+template <typename T>
+struct BinaryLikeComparer<T, /*is_signed=*/true> {
+ static bool Compare(int type_length, const T& a, const T& b) {
+ // Is signed is used for integers encoded as big-endian twos
+ // complement integers. (e.g. decimals).
+ int a_length = value_length(type_length, a);
+ int b_length = value_length(type_length, b);
+
+ // At least of the lengths is zero.
+ if (a_length == 0 || b_length == 0) {
+ return a_length == 0 && b_length > 0;
+ }
- static T Max(int type_length, const T& a, const T& b) {
- if (a.ptr == nullptr) return b;
- if (b.ptr == nullptr) return a;
- return Compare(type_length, a, b) ? b : a;
+ int8_t first_a = *a.ptr;
+ int8_t first_b = *b.ptr;
+ // We can short circuit for different signed numbers or
+ // for equal length bytes arrays that have different first bytes.
+ if ((0x80 & first_a) != (0x80 & first_b) ||
+ (a_length == b_length && first_a != first_b)) {
+ return first_a < first_b;
+ }
+ // When the lengths are unequal and the numbers are of the same
+ // sign we need to extend the digits.
+ const uint8_t* a_start = a.ptr;
+ const uint8_t* b_start = b.ptr;
+ if (a_length != b_length) {
+ const uint8_t* lead_start = nullptr;
+ const uint8_t* lead_end = nullptr;
+ if (a_length > b_length) {
+ int lead_length = a_length - b_length;
+ lead_start = a.ptr;
+ lead_end = a.ptr + lead_length;
+ a_start += lead_length;
+ } else {
+ DCHECK_LT(a_length, b_length);
+ int lead_length = b_length - a_length;
+ lead_start = b.ptr;
+ lead_end = b.ptr + lead_length;
+ b_start += lead_length;
+ }
+ // Compare extra bytes to the sign extension of the first
+ // byte of the other number.
+ uint8_t extension = first_a < 0 ? 0xFF : 0;
+ for (; lead_start != lead_end; lead_start++) {
+ if (*lead_start < extension) {
+ // The first bytes of the long value are less
+ // then the extended short one. So if a is the long value
+ // we can return true.
+ return a_length > b_length;
+ } else if (*lead_start > extension) {
Review comment:
I did a slightly different factoring let me know if you think that is clearer?
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org