abelianbee opened a new pull request, #51299:
URL: https://github.com/apache/arrow/pull/51299
### Rationale for this change
`NormalizeTime` is documented as preserving order. For signed types it
doesn't, because the bias is applied after the value has already been widened:
```c++
uint64_t bias =
std::is_signed<T>::value ? static_cast<uint64_t>(1) << (8 * sizeof(T) -
1) : 0;
return t < 0 ? static_cast<uint64_t>(t + bias) : static_cast<uint64_t>(t);
```
A negative `t` converts to `uint64_t` first and sign-extends to `2^64 + t`,
so adding `2^(W-1)` wraps back into `[0, 2^(W-1))`, where the non-negative
branch already maps. That folds the domain 2-to-1: `NormalizeTime(t) ==
NormalizeTime(t + 2^(W-1))` for every negative `t`. Over the full int16 domain
only 32768 of 65536 outputs are distinct, and order inverts once, at `-1 -> 0`.
`NormalizeTime(INT64_MIN)` and `NormalizeTime(int64_t{0})` are both 0.
`GetTime` routes TIMESTAMP, DATE64 and TIME64 through int64 and
DATE32/TIME32 through int32, and asof_join_node and sorted_merge_node both key
rows on it, so any pre-epoch timestamp hits this.
Two symptoms. The one in the issue is the out-of-order error, from input
that is correctly sorted, such as `[-1000, 0, 1000]`:
```
Invalid: AsofJoin does not allow out-of-order on-key values
asof_join_node.cc:693 Advance()
```
The other is silent. `TolType::Accepts` compares differences of normalized
values, and those are exact only when both operands have the same sign, so an
asof join whose tolerance window straddles the epoch drops matches that are
inside the window without raising anything. A left row at t=30 and a right row
at t=-30 with a backward tolerance of 60 returns null.
### What changes are included in this PR?
Flip the sign bit inside `T`'s own width, then zero-extend. That is a
strictly increasing bijection onto the same-width unsigned type, and
zero-extension preserves order. Unsigned `T` stays the identity.
The definition moves into the header. It was declared there and defined in
the `.cc` with no explicit instantiation, so it only linked because `GetTime`
instantiates it in that same TU, and no test TU could instantiate it at all.
Explicit instantiations would work too if you would rather it stayed put.
### Are these changes tested?
New `time_series_util_test.cc` on the existing `util_test` target:
exhaustive monotonicity and injectivity over int8, uint8, int16 and uint16,
boundary sweeps for the wider types, `INT64_MIN -> 0` and `INT64_MAX ->
UINT64_MAX`, and exactness of differences spanning zero. Plus
`TimesStraddlingEpochAreOrdered` and `ToleranceWindowStraddlingEpoch` in
asof_join_node_test.
All six fail without the fix. With it, util_test 18 pass,
asof_join_node_test 154 pass with the pre-existing BackpressureWithBatchesGen
skip, sorted_merge_node_test 1 pass.
### Are there any user-facing changes?
Asof joins and sorted merges over pre-epoch timestamps stop erroring and
stop dropping rows. Normalized values are an internal key encoding, so no API
change.
**This PR contains a "Critical Fix".** Asof joins over pre-epoch timestamps
could silently return wrong results.
--
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.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
