You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@arrow.apache.org by "yinli-systems (via GitHub)" <gi...@apache.org> on 2026/09/11 22:53:35 UTC
[PR] Support RunEndEncoded arrays in numeric kernels [arrow-rs]
yinli-systems opened a new pull request, #11062:
URL: https://github.com/apache/arrow-rs/pull/11062
# Which issue does this PR close?
- Closes #10891.
# Rationale for this change
Numeric kernels currently reject run-end encoded inputs. This prevents consumers such as DataFusion from applying arithmetic to compressed ordering columns without decoding them first.
# What changes are included in this PR?
- Route the checked, wrapping, division, remainder, and negation numeric entry points through a shared REE implementation.
- Preserve run boundaries for scalar operations and use the union of boundaries for two REE operands. Aligned inputs avoid gathering their physical values.
- Normalize sliced run ends, preserve primitive null/overflow/decimal/temporal semantics, and select the wider run-end integer type for two differently encoded operands.
- Return an explicit error for a REE array combined with a non-scalar unencoded array. Like dictionary arithmetic, that case would require decoding to produce an unencoded result and is outside this compression-preserving path.
# Are these changes tested?
Yes. The new differential tests compare decoded REE results with the existing primitive kernels across all public numeric operations, all run-end integer widths, integer/float/decimal/timestamp values, nulls, checked and wrapping overflow, division errors, unequal run boundaries, every slice offset in a deterministic matrix, empty inputs, and both scalar directions. A billion-row logical array test verifies work and result storage remain proportional to physical runs.
Local validation:
- `cargo test -p arrow-arith --all-features`: 239 unit tests, 13 integration tests, and 16 doctests passed.
- `cargo test --lib --tests --release -p arrow-arith`: 239 unit tests and 13 integration tests passed.
- `cargo test -p arrow --features=force_validate,prettyprint,ipc_compression,ffi,chrono-tz`: passed.
- `cargo clippy -p arrow-arith --all-targets --all-features -- -D warnings`: passed.
- `cargo +stable fmt --all -- --check`: passed.
A local one-million-row release-mode timing harness showed the intended compression-dependent tradeoff. With runs of 128 rows, REE was 2.4x-13x faster than arithmetic over already-resident dense arrays; with runs of 4096 rows it was 64x-275x faster. Runs of 8 rows were 15%-6.5x slower, and run length 1 was substantially slower, so this PR does not claim REE is beneficial for low-compression data. The billion-row test covers the non-expansion property deterministically.
The same integration test file was also run against the unmodified base: 12 of 13 tests failed because REE numeric operations were unsupported; only the invalid-input test passed.
# Are there any user-facing changes?
Yes. Numeric arithmetic and negation can now operate directly on REE arrays when the other operand is a scalar or REE array. The result remains run-end encoded. There are no public API signature changes.
AI disclosure: Codex assisted with repository research, implementation, test generation, performance analysis, and self-review. I reviewed the resulting behavior through differential tests, negative controls against the base revision, release-mode tests, strict Clippy, and the compression benchmark. No independent human review is claimed.
--
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: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Support RunEndEncoded arrays in numeric kernels [arrow-rs]
Posted by "yinli-systems (via GitHub)" <gi...@apache.org>.
yinli-systems commented on PR #11062:
URL: https://github.com/apache/arrow-rs/pull/11062#issuecomment-5712195769
Thanks — I rechecked the consumer side and now have a concrete DataFusion A/B case for this PR.
DataFusion main currently has an explicit planning guard for finite-offset `RANGE` frames over an REE ordering column. That guard was retained in [DataFusion #24565](https://github.com/apache/datafusion/pull/24565) specifically because the frame implementation computes `current_value +/- offset`, while Arrow arithmetic could not handle the run-end-wrapped scalar. The review there also concluded that this should be implemented in the Arrow kernels rather than special-cased in DataFusion.
I tested DataFusion main at `b300cea226` (Arrow 59.3) with a minimal removal of that guard and an SLT query whose expected IDs are `2, 3`:
```sql
SELECT id
FROM (
SELECT
ROW_NUMBER() OVER (ORDER BY temperature) AS id,
SUM(temperature) OVER (
ORDER BY arrow_cast(
temperature,
'RunEndEncoded("run_ends": non-null Int32, "values": Int64)'
)
RANGE BETWEEN 1 PRECEDING AND 1 FOLLOWING
) AS windowed_sum
FROM sensor_readings
)
WHERE windowed_sum IN (45, 69)
ORDER BY id;
```
The A/B result was:
- Current DataFusion main: rejected at planning by the existing guard.
- Guard removed, unmodified Arrow 59.3: the four frame sums are incorrectly `89, 89, 89, 89`, and the query returns no rows.
- Guard removed, this PR backported to Arrow 59.3: the frame sums are `20, 45, 69, 47`, the query returns `2, 3`, and the focused DataFusion sqllogictest passes.
This is a pure DataFusion execution path, so there is no Spark fallback involved. It also shows that the guard is preventing a real correctness problem: removing it without the Arrow change produces silent wrong frame boundaries, not just a missing optimization.
I separately checked compression preservation with `year * 100 + month` over 50,000,000 logical rows. Both intermediate results remained one run with one physical value. In three release-mode processes (two warmups and seven samples each), the one-run REE path took 3.29–4.29 microseconds versus 68.21–68.60 milliseconds for already-resident dense arrays. Inputs plus both live results were 880 bytes by Arrow's array accounting versus 800,000,384 bytes dense; one `/usr/bin/time -l` run measured maximum RSS of 6,815,744 versus 1,206,681,600 bytes. This is intentionally an ideal one-run kernel microbenchmark, not a full-query speedup claim.
I also investigated an Iceberg/Comet partition-arithmetic candidate, but did not find it valid evidence: in the current Comet path the relevant operands are normalized to dense Spark-compatible integers before arithmetic. I am therefore not using that claim.
If this DataFusion case meets the use-case bar, the follow-up after Arrow updates would be small: remove the guard and add the end-to-end `2, 3` regression above. I reviewed the code path and test output myself; Codex assisted with the repository search, test harness, and drafting this summary.
--
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: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Support RunEndEncoded arrays in numeric kernels [arrow-rs]
Posted by "Jefffrey (via GitHub)" <gi...@apache.org>.
Jefffrey commented on PR #11062:
URL: https://github.com/apache/arrow-rs/pull/11062#issuecomment-5707101393
i think i'd still prefer to wait to see if we still have a strong use case for this before proceeding with the implementation
by the way, are these PR comments entirely LLM generated? not to mention this bit confuses me in the PR:
> No independent human review is claimed
this means no human looked at this?
--
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: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Support RunEndEncoded arrays in numeric kernels [arrow-rs]
Posted by "Jefffrey (via GitHub)" <gi...@apache.org>.
Jefffrey commented on PR #11062:
URL: https://github.com/apache/arrow-rs/pull/11062#issuecomment-5788727379
im still not clear on how datafusion treats such arithmetic for dictionaries vs run end encoded, per my original comment on the issue: https://github.com/apache/arrow-rs/issues/10891#issuecomment-5447531129
--
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: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Support RunEndEncoded arrays in numeric kernels [arrow-rs]
Posted by "thorfour (via GitHub)" <gi...@apache.org>.
thorfour commented on PR #11062:
URL: https://github.com/apache/arrow-rs/pull/11062#issuecomment-5718514852
Just chiming in that it would indeed be nice if this type of arithmetic kernel was supported. Thanks @yinli-systems for looking into adding the support.
--
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: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Support RunEndEncoded arrays in numeric kernels [arrow-rs]
Posted by "yinli-systems (via GitHub)" <gi...@apache.org>.
yinli-systems commented on PR #11062:
URL: https://github.com/apache/arrow-rs/pull/11062#issuecomment-5710516236
Yes, I did review the PR and the comments myself.
Some of the wording and analysis was assisted by an LLM, but I went through the output, checked the relevant code and evidence, and only kept points I believed were supported.
The line “No independent human review is claimed” was meant to say that there was not a separate second human reviewer independently auditing the work, not that no human looked at it. I can see how that wording was confusing, so I have changed the disclosure to say explicitly that the PR has not yet received a separate independent review from another human.
--
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: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Support RunEndEncoded arrays in numeric kernels [arrow-rs]
Posted by "yinli-systems (via GitHub)" <gi...@apache.org>.
yinli-systems commented on PR #11062:
URL: https://github.com/apache/arrow-rs/pull/11062#issuecomment-5676070962
Thanks @Jefffrey; I agree this needs an explicit encoded-type decision before merge. I checked the current layers: direct `arrow_arith::numeric::{add,sub,mul,div,neg,...}` dispatch accepts primitives but not `Dictionary`; DataFusion already has dictionary arithmetic tests such as `plus_op_dict`, with its coercion/evaluation layer producing dense primitive results. The DataFusion #24565 change is about REE coercion and window range extraction, not evidence that direct Arrow numeric kernels support dictionaries. Conversely, `arrow_arith::temporal::date_part` handles both Dictionary and REE by transforming physical values, so there does not appear to be a universal policy forbidding encoded inputs in Arrow kernels.
The narrow capability in this PR is compression-preserving `REE x scalar` and `REE x REE` arithmetic, where the output remains REE and work scales with runs. `REE x dense non-scalar` is rejected rather than silently expanding to logical length. Dictionary arithmetic has different cardinality/key-pair questions, so I would treat its direct-kernel contract as a separate design item instead of adding an unreviewed implementation here. I corrected the PR description, which had implied a stronger dictionary precedent than actually exists.
My suggested decision is: accept this narrow REE contract as an opt-in encoded kernel capability, then specify Dictionary and mixed dense/encoded semantics in follow-up work. If maintainers prefer consistent direct-kernel support for both encodings before this lands, I am happy to pause or rescope #11062 after that direction is clear.
--
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: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Support RunEndEncoded arrays in numeric kernels [arrow-rs]
Posted by "Jefffrey (via GitHub)" <gi...@apache.org>.
Jefffrey commented on PR #11062:
URL: https://github.com/apache/arrow-rs/pull/11062#issuecomment-5674158508
i think we need some discussion on this first, see my comment:
- https://github.com/apache/arrow-rs/issues/10891#issuecomment-5447531129
i originally suggested the issue be raised in arrow-rs because i thought we lacked REE support, but given it seems we also lack dictionary support then we need t decide if this is intentional or if we should actually add 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.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Support RunEndEncoded arrays in numeric kernels [arrow-rs]
Posted by "yinli-systems (via GitHub)" <gi...@apache.org>.
yinli-systems commented on PR #11062:
URL: https://github.com/apache/arrow-rs/pull/11062#issuecomment-5642248860
Pushed `5143d92fe` to address the MIRI (5) failure in `run_float_ieee_semantics`. The two arrays differed only in the sign bit of NaN (`+qNaN` versus `-qNaN`), which IEEE arithmetic does not guarantee to preserve across equivalent evaluation paths.
The regression now checks run ends, physical value length, and nulls explicitly; accepts any NaN only when the flat reference is NaN; and continues comparing every non-NaN value via `to_bits()`, preserving exact signed-zero and infinity behavior.
Validation on the updated head:
- matching 2026-09-11 nightly Miri: focused regression passes
- `cargo test -p arrow-arith`: 239 unit tests, 13 integration tests, and 16 doctests pass
- strict package Clippy with all targets/features passes
- stable rustfmt and `git diff --check` pass
This diagnosis, fix, and validation were prepared with Codex assistance.
--
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: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] Support RunEndEncoded arrays in numeric kernels [arrow-rs]
Posted by "yinli-systems (via GitHub)" <gi...@apache.org>.
yinli-systems commented on PR #11062:
URL: https://github.com/apache/arrow-rs/pull/11062#issuecomment-5800037346
I traced the Dictionary path end to end rather than assuming the copied planner branch meant it worked. It currently does not: Dictionary finite-offset RANGE is a separate silent-correctness bug in DataFusion.
On DataFusion b300cea226 (with Arrow 59.3), I ran the same four-row query twice:
- dense ORDER BY Int64: 20, 45, 69, 47
- ORDER BY arrow_cast(temperature, 'Dictionary(Int32, Int64)'): 89, 89, 89, 89
The probe passes when those exact outputs are asserted. It does not fall back or report an error.
The call path explains the result:
1. extract_window_frame_target_type unwraps Dictionary only to coerce the frame offset to Int64. This is the part #24565 copied for REE.
2. At execution, get_row_at_idx / ScalarValue::try_from_array retains the wrapper as ScalarValue::Dictionary(...), just as it retains ScalarValue::RunEndEncoded(...).
3. ScalarValue::add_checked / sub_checked delegates the wrapped one-row array to arrow_arith::numeric.
4. numeric arithmetic has neither Dictionary nor (without this PR) REE dispatch.
5. WindowFrameStateRange currently treats every arithmetic error as overflow and returns an unbounded partition edge. That turns the unsupported Dictionary operation into a full-partition frame, hence 89 for every row.
So Dictionary is not an existing working precedent that DataFusion uses differently. The planner accepts it, but the runtime result is wrong. REE has the same wrapper-preserving path; #11062 makes that path produce the correct 20, 45, 69, 47 result while retaining the run representation. Dictionary arithmetic remains a distinct missing-kernel/DataFusion-error-classification issue and should not be claimed as solved here.
This corrects the ambiguity in my earlier DataFusion comparison. I can file the Dictionary behavior separately, but I would keep this PR scoped to the accepted #10891 REE kernel work unless you prefer the two encodings handled together.
--
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: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org