IgnatiusPang opened a new pull request, #25746:
URL: https://github.com/apache/datafusion/pull/25746
## Rationale for this change
In `datafusion-functions::math::log`, `LogFunc::output_ordering` determines
whether the output of `log(base, num)` preserves the sort order of its
arguments:
```rust
match (num_sort_properties, base_sort_properties) {
(first @ SortProperties::Ordered(num), SortProperties::Ordered(base))
if num.descending != base.descending
&& num.nulls_first == base.nulls_first =>
{
Ok(first)
}
(
first @ (SortProperties::Ordered(_) | SortProperties::Singleton),
SortProperties::Singleton,
) => Ok(first),
(SortProperties::Singleton, second @ SortProperties::Ordered(_)) => {
Ok(-second)
}
_ => Ok(SortProperties::Unordered),
}
```
### The Mathematical Problem
The rule unconditionally asserts that `log_b(x)` is monotonically increasing
with respect to `x`:
$$\frac{\partial}{\partial x} \log_b(x) = \frac{1}{x \ln(b)}$$
1. **When $\text{base} > 1.0$**: $\ln(b) > 0$, so $\frac{\partial}{\partial
x} \log_b(x) > 0$. The function is strictly increasing (order-preserving).
2. **When $\text{base} \in (0, 1)$** (e.g., constant $0.5$): $\ln(b) < 0$,
so $\frac{\partial}{\partial x} \log_b(x) < 0$. The function is **strictly
decreasing** (order-inverting).
3. **When $\text{base} \le 0$ or $\text{base} == 1$**: The logarithm is
undefined or non-real.
Furthermore, with respect to the base:
$$\frac{\partial}{\partial b} \log_b(x) = -\frac{\ln(x)}{b (\ln(b))^2}$$
The sign depends on whether $x > 1.0$ ($\ln(x) > 0$) or $x \in (0, 1)$
($\ln(x) < 0$).
### Consequence in Query Execution
DataFusion's physical optimizer relies on `output_ordering` to decide
whether an intermediate plan already satisfies an order requirement. Because
`LogFunc::output_ordering` asserted that `log(0.5, x)` preserves ascending
order, the optimizer removed required `SortExec` operators, silently returning
out-of-order rows to users.
## What changes are included in this PR?
1. **Interval Bounds Verification for Base**:
- In `LogFunc::output_ordering`, evaluate `input[0].range` using interval
arithmetic to verify that `base > 1.0` (`base_range.gt(&one_point)? ==
Interval::TRUE`).
- If `base > 1.0` cannot be proven from input bounds (or if $\text{base}
\le 1.0$), return `Ok(SortProperties::Unordered)` soundly.
- For unary `log(x)`, the default base is 10 ($10 > 1.0$), which
preserves monotonic ordering without extra checks.
2. **Interval Bounds Verification for Number when Base Varies**:
- When the base varies, monotonicity also requires $x > 1.0$. Verify
`num_range > 1.0` before returning monotonic sort properties when base varies.
3. **Comprehensive Unit Tests**:
- Updated `test_log_output_ordering` with explicit interval bounds
($[2.0, 10.0]$) confirming monotonic sort preservation when `base > 1.0`.
- Added unit test cases for sub-unit base (e.g. constant $0.5 \in (0,
1)$), verifying that `output_ordering` returns `SortProperties::Unordered` and
prevents invalid sort omission.
- Added unit test cases for unbounded/unknown base ranges, verifying safe
fallback to `SortProperties::Unordered`.
## Are these changes tested?
Yes, all existing and newly added tests in `datafusion-functions` pass:
```bash
cargo test --package datafusion-functions --lib math::log
```
Result: `22 passed; 0 failed`.
## Are there any user-facing changes?
Yes: Queries ordering by `log(base, col)` where `base` is in $(0, 1)$ or has
unknown bounds will now correctly preserve necessary `SortExec` operations
rather than silently producing out-of-order results.
```
---
## 3. Git Push Command
Run the following command to push the branch to your fork on GitHub:
```bash
git push -u fork fix-log-monotonicity-ordering
```
--
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]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
