abelianbee opened a new pull request, #51386:
URL: https://github.com/apache/arrow/pull/51386
### Rationale for this change
`NormalizeTime` documents itself as mapping an integral time value onto
uint64_t "while preserving ordering of values". It does not. For a signed
type it folds the domain exactly 2-to-1 onto half the output range, so
NormalizeTime(t) == NormalizeTime(t + 2^(W-1)) for every negative t.
The bias is applied at the wrong width:
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);
`bias` is a uint64_t, so in `t + bias` the signed `t` is converted to
uint64_t first and sign-extends to 2^64 + t. Adding 2^(W-1) and wrapping
leaves t + 2^(W-1), which lands in [0, 2^(W-1)) — the same range the
non-negative branch maps onto. The bias never takes effect for negative
values at all.
Sweeping the full domain of the narrow types, using the current
implementation:
domain distinct collisions monotonicity breaks
int8 256 128 128 1
int16 65536 32768 32768 1
uint8 256 256 0 0
Half the signed domain is unreachable and ordering inverts at exactly one
point, -1 -> 0:
NormalizeTime(int64_t{-1}) = 9223372036854775807
NormalizeTime(int64_t{0}) = 0
NormalizeTime(INT64_MIN) = 0 // collides with 0
`GetTime` routes TIMESTAMP, DATE64 and TIME64 through the int64 path and
DATE32/TIME32 through int32, and both asof_join_node and sorted_merge_node
use it as the per-row time-key path. So any pre-epoch timestamp is
affected.
The reported symptom is the out-of-order error from that single inversion,
and it reproduces from properly sorted input: an on-key column of
[-1000, 0, 1000] fails with
Invalid: AsofJoin does not allow out-of-order on-key values
asof_join_node.cc:693 Advance()
But there is a second, quieter consequence. TolType::Accepts compares
*differences* of normalized values, and differences are exact only when
both operands have the same sign. An as-of join whose tolerance window
straddles the epoch therefore drops legitimate matches with no error at
all: with a left row at t=30, a right row at t=-30 and a backward
tolerance of 60, the right row is exactly within tolerance, and the join
returns null for it.
Both of those are added as tests in this PR and both fail on the current
implementation.
### What changes are included in this PR?
Apply the bias inside the source width instead of after widening: cast to
the unsigned type of the same width, flip the top bit, then zero-extend.
XOR of the sign bit is a strictly increasing bijection from T onto that
unsigned type, and zero-extension preserves order. Unsigned T stays the
identity.
The definition moves from time_series_util.cc into the header. It had to:
the template was declared in the header and defined in the .cc with no
explicit instantiation, so it linked only because GetTime instantiates it
implicitly in that same translation unit, and no test translation unit
could instantiate it at all.
Adds time_series_util_test.cc, on the existing util_test target:
- strict monotonicity and injectivity over the *entire* domain of int8,
uint8, int16 and uint16
- boundary sweeps around the extremes and zero for all eight integral types
- endpoint mapping: INT64_MIN -> 0 and INT64_MAX -> UINT64_MAX, so that
TolType's saturation at kMinValue/kMaxValue still covers the full range
- exactness of differences spanning zero, which is what Accepts relies on
Adds two end-to-end tests to asof_join_node_test.cc, one per symptom:
TimesStraddlingEpochAreOrdered and ToleranceWindowStraddlingEpoch.
The new test is registered in both cpp/src/arrow/acero/CMakeLists.txt and
cpp/src/arrow/acero/meson.build.
### Are these changes tested?
Yes, and each new test was confirmed to fail without the fix.
suite patched unpatched
arrow-acero-util-test 18 pass 4 new fail
arrow-acero-asof-join-node-test 154 pass, 1 skip 2 new fail
arrow-acero-sorted-merge-node-test 1 pass -
The skip is the pre-existing AsofJoinTest.BackpressureWithBatchesGen.
Release build, Apple M1 Max. time_series_util.h is included only by
asof_join_node.cc and sorted_merge_node.cc, so those suites plus the new
helper test cover the full surface of the change.
### Are there any user-facing changes?
Yes, and they are the point: as-of joins and sorted merges over time
columns containing pre-epoch values previously either errored or silently
dropped matches, and now behave correctly. Normalized values are not part
of the public API — they are an internal key encoding — so no API changes.
**This PR contains a critical bug fix.** Wrong results from an as-of join
over pre-epoch timestamps, with no error raised.
One judgment call: moving the definition into the header. The alternative is
explicit instantiations in the `.cc`, which keeps the definition where it is
but is more boilerplate for a three-line inline function. Happy to go the other
way if maintainers prefer.
--
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]
