ClickHouse / ClickHouse/ClickHouse

arrayJaccardIndex union from arrayUniq disagrees with arrayIntersect: returns inf

Open
#120,072 0 comments 0 reactions 0 assignees View on GitHub
comp-regular-function
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

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.