namanjain24-sudo opened a new pull request, #25289: URL: https://github.com/apache/datafusion/pull/25289
## Which issue does this PR close? - Closes #25265. ## Rationale for this change `array_distance`, `cosine_distance` and `array_normalize` square their inputs directly. When a finite value's square falls outside the `Float64` range, they return a wrong answer even though the true result is representable: | query | `main` | this PR | | --- | --- | --- | | `array_distance([1e-200], [0])` | `0.0` | `1e-200` | | `array_distance([3e200], [-1e200])` | `inf` | `4e200` | | `cosine_distance([3e200, 4e200], [3e200, 4e200])` | `NaN` | `-2.220446049250313e-16` | | `cosine_distance([1e-200, 2e-200], [1e-200, 2e-200])` | `NULL` | `0.0` | | `array_normalize([3e200, 4e200])` | `[0.0, 0.0]` | `[0.6000000000000001, 0.8]` | | `array_normalize([3e-200, 4e-200])` | `NULL` | `[0.6, 0.8]` | The two results that are off in the last bit are ordinary rounding. The existing formula does the same for ordinary inputs: for identical vectors it already returns a small negative `cosine_distance` about 11% of the time. ## What changes are included in this PR? Each function still computes the sum of squares as before. Only when that sum may be wrong (infinite, NaN, or below `1e-180`) does it recompute with every value multiplied by a power of two that brings the largest magnitude close to 1 (`norm_scale` in `utils.rs`): - `array_distance` scales the element-wise differences, then divides the result by the same factor. - `cosine_distance` scales each vector on its own. The distance does not change when either vector is multiplied by a positive factor. - `array_normalize` scales the values. Dividing the scaled values by the scaled magnitude gives the same unit vector. Rows whose sums are in range run the same code as before, so their results do not change. Because the factor is a power of two, rescaling is exact, so a rescaled row gets the same result the unscaled code would have given had it not overflowed or underflowed. Empty, all-zero, NaN and infinite inputs are never rescaled, so their results are also unchanged, including `NULL` for zero vectors. ## What is the testing strategy for this PR? - sqllogictests for the overflow and underflow cases in `array/array_length.slt`, `cosine_distance.slt` and `array_normalize.slt`, plus non-finite inputs to pin the unchanged behaviour. `.slt` rounds floats to 12 decimal places, so the `1e-200` distance is checked as a ratio. - Unit tests for `norm_scale` and `needs_norm_scale` in `utils.rs`. - With the change to `datafusion/functions-nested/src` reverted and the new tests kept, the three new overflow and underflow queries fail (`0 Infinity` instead of `1 4`, `NaN NULL NULL` instead of `0 0 2`, and `[0.0, 0.0] NULL` instead of `[0.6, 0.8] [0.6, -0.8]`). The non-finite queries pass either way, as intended. - To check the "results do not change" claim, I ran copies of the old and new loops on 200,000 random vector pairs (1 to 32 elements, magnitudes between 1e-100 and 1e100) and compared the bits: no differences. On another 300,000 pairs with magnitudes near the `1e-180` threshold, about a third of them rescaled, the new code matched a version that always rescales, bit for bit. It also matched on 300,000 pairs whose elements span 1e-170 to 1e-80, including 90,137 rows that kept the unscaled path while some of their squares were subnormal. - I also ran 29 edge-case queries through `datafusion-cli` on `main` and on this branch. Only the six rows in the table above changed. I didn't find an existing benchmark for these functions, so I timed copies of the old and new loops on their own (20,000 rows of 1536-dimension vectors, best of 9 runs, `rustc -O`). The ratios are new time over `main` time: | input | `array_distance` | `cosine_distance` | `array_normalize` | | --- | --- | --- | --- | | values in [-1, 1], no row rescaled | 1.00x | 1.00x | 0.73x | | values around 1e-200, every row rescaled | 3.57x | 4.84x | 4.05x | Rescaled rows cost more, but those are the rows that returned wrong results before. The `array_normalize` speedup in the first row comes from writing the output with `extend`. I haven't measured it inside DataFusion. ## Are there any user-facing changes? Only for finite inputs whose squares overflowed or underflowed. Those now return the correct distance or normalized vector instead of `0`, `inf`, `NaN`, a zero vector or `NULL`. There are no API changes. -- 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]
