ClickHouse / ClickHouse/ClickHouse
arrayJaccardIndex union from arrayUniq disagrees with arrayIntersect: returns inf
- Dominant language
- C++
- Stars
- 49.9k
- Forks
- 9k
- Avg merge
- 21h 32m
- Merged PRs (30d)
- 515
Description
### Describe what's wrong
**`arrayJaccardIndex` returns `inf`, or a ratio greater than 1, for `Array(Nullable(T))` arguments that contain both a NULL and T's default value, when T is one of the types `arrayUniq` handles on its generic hashed path (Decimal*, DateTime64, UUID, IPv4, IPv6, Int128/Int256/UInt128/UInt256, Tuple). `SELECT arrayJaccardIndex([NULL, toDecimal32(0, 2)], [NULL, toDecimal32(0, 2)])` gives `inf`; the same query on master gives the correct `1`.**
- **Root cause:** [`src/Functions/array/arrayJaccardIndex.cpp:60-61`](https://github.com/ClickHouse/ClickHouse/blob/360a086963a/src/Functions/array/arrayJaccardIndex.cpp#L60-L61) computes `union_size = left_unique_sizes[i] + right_unique_sizes[i] - intersect_size` from two sources that do not share an equality relation, with no check that `union_size >= intersect_size` and no guard against `union_size == 0`. The pre-PR formula used the raw offsets of the very same columns `arrayIntersect` consumed, so `left_size + right_size - intersect_size >= intersect_size` held by construction and the result was always in [0, 1].
Analysis details (evidence, affected locations, impact)
**Why we believe this is a bug:** `FunctionArrayJaccardIndex::executeImpl` (arrayJaccardIndex.cpp:143-144) now obtains the union term by running `arrayUniq` on each ORIGINAL argument, while the intersection term still comes from `arrayIntersect` (line 123). `FunctionArrayUniq::executeImpl` computes a null map at arrayUniq.cpp:173 and strips the `ColumnNullable` at line 171, but for every nested type not covered by `executeNumber`/`executeString`/`executeFixedString` it falls through to `executeHashed`, which passes `nullptr` for that null map (arrayUniq.cpp:317). NULL is then hashed as the value sitting in the nested column at that position -- the type default -- and collapses into a real default element. `arrayIntersect` keeps NULL as a distinct member. `vector` (arrayJaccardIndex.cpp:59-62) subtracts the larger intersection from the smaller union.
**Affected locations:**
- [`src/Functions/array/arrayJaccardIndex.cpp:60`](https://github.com/ClickHouse/ClickHouse/blob/360a086963a/src/Functions/array/arrayJaccardIndex.cpp#L60) — union_size computed from arrayUniq counts minus the arrayIntersect size; no clamp, no zero check
- [`src/Functions/array/arrayJaccardIndex.cpp:143`](https://github.com/ClickHouse/ClickHouse/blob/360a086963a/src/Functions/array/arrayJaccardIndex.cpp#L143) — left/right unique counts delegated to arrayUniq on the original argument types
- [`src/Functions/array/arrayUniq.cpp:317`](https://github.com/ClickHouse/ClickHouse/blob/360a086963a/src/Functions/array/arrayUniq.cpp#L317) — executeHashed discards the null map that executeImpl computed, so NULL hashes as the nested default
**Impact:** Wrong results, including `inf`, from a function whose output is mathematically bounded by [0, 1]. Downstream `ORDER BY arrayJaccardIndex(...) DESC`, similarity thresholds and `round()` all silently take the poisoned value; `inf` also survives insertion into a Float64 column. The inputs that regress -- `Array(Nullable(Decimal))`, `Array(Nullable(DateTime64))`, `Array(Nullable(UUID))` holding a NULL next to 0 / the epoch / the zero UUID -- returned the mathematically correct value before this PR.
### Does it reproduce on most recent release?
Yes — confirmed on current `master` (commit `360a086963a`).
### How to reproduce
[▶ Run on ClickHouse Fiddle](https://fiddle.clickhouse.com/5e1f3953-53a6-4af5-8c9c-2b806785f5aa)
Reproducer
```sql
-- Test: arrayJaccardIndex over Array(Nullable(T)) where the array also holds T's default value
SELECT arrayJaccardIndex([NULL, toDecimal32(0, 2)], [NULL, toDecimal32(0, 2)]);
SELECT arrayJaccardIndex([NULL, toDecimal32(0, 2)], [toDecimal32(0, 2)]);
SELECT round(arrayJaccardIndex([NULL, toDecimal32(0, 2), toDecimal32(3, 2)], [NULL, toDecimal32(0, 2)]), 2);
SELECT arrayJaccardIndex([NULL, toUUID('00000000-0000-0000-0000-000000000000')], [NULL, toUUID('00000000-0000-0000-0000-000000000000')]);
SELECT arrayJaccardIndex(materialize([NULL, toDecimal32(0, 2)]), materialize([NULL, toDecimal32(0, 2)]));
```
### Expected behavior
Expected output of the reproducer above:
```
1
0.5
0.67
1
1
```
### Error message and/or stacktrace
Actual output of the reproducer above on `master` (`360a086963a`):
```
inf
1
2
inf
inf
```
Suggested fix
Two options. (a) Fix the disagreement at the source: forward `null_map` from `FunctionArrayUniq::executeImpl` into `executeHashed` (arrayUniq.cpp:312-318) the way `executeNumber`/`executeString`/`executeFixedString` already do, so `arrayUniq` counts NULL as one distinct element for every nested type. This also fixes `arrayUniq` standalone. (b) Keep the union consistent with the intersection by construction -- derive both unique counts from the same cast columns `arrayIntersect` works on (e.g. `|A union B| = |arrayIntersect(A, A)| + |arrayIntersect(B, B)| - |arrayIntersect(A, B)|`) instead of calling `arrayUniq` on the uncast arguments. Either way, add an assertion or clamp at arrayJaccardIndex.cpp:60 so a future divergence cannot produce `inf`.
Additional context
**Open risks:**
- `FunctionArrayUniq::executeImpl` also hands `executeHashed` the already-stripped nested column (arrayUniq.cpp:171), so option (a) must restore the null map without re-introducing double counting of NULLs.
- The same class of divergence will reappear for any nested type later added to ClickHouse that `arrayIntersect` can compare but that is absent from arrayUniq.cpp:184-195; the clamp in option (b) is the only structural defence.
Found during automated review of [PR #119560](https://github.com/ClickHouse/ClickHouse/pull/119560). Severity P1 · Finding `h_pr119560_001`
cc @fallintoplace @alexey-milovidov (from #119560)
Contributor guide
Assessment
This issue has not been assessed yet.