pg.ddx.io  pgvector/pgvector GitHub issues and pull requests  
help / color / mirror / Atom feed
[pgvector/pgvector] PR #1056: Fixed Jaccard distance for two empty bit vectors
4+ messages / 2 participants
[nested] [flat]

* [pgvector/pgvector] PR #1056: Fixed Jaccard distance for two empty bit vectors
@ 2026-11-03 13:44  "Ksschkw (@Ksschkw)" <noreply+Ksschkw@github.com>
  0 siblings, 0 replies; 4+ messages in thread

From: Ksschkw (@Ksschkw) @ 2026-11-03 13:44 UTC (permalink / raw)
  To: pgvector/pgvector <noreply+pgvector-pgvector@github.com>

Fixes #1043.

## The bug

`BitJaccardDistanceDefault` collapses two distinct cases into one:

```c
if (ab == 0)
    return 1;
```

`ab` is the size of the intersection. When it is zero, the code cannot tell
"these vectors share no bits" from "both vectors are empty", so two identical
all-zero vectors report maximal distance while Hamming distance for the same
pair reports `0`.

Reproduced against an unmodified build:

```
 identical_zero | disjoint | hamming_zero
----------------+----------+--------------
              1 |        1 |            0
```

## The fix

`src/bitutils.c`: return `0` when both vectors are empty, `1` when only one is.

```c
if (ab == 0)
{
    if (aa == 0 && bb == 0)
        return 0;
    else
        return 1;
}
```

The AVX512 path accumulates `aa`/`bb` and delegates to this function, so the
one change covers both dispatch targets.

After the fix:

```
 identical_zero | disjoint
----------------+----------
              0 |        1
```

## Test changes

Two expected values in `test/expected/bit.out` follow the corrected behaviour:

- `jaccard_distance('0000', '0000')` changes from `1` to `0`
- `jaccard_distance('', '')` changes from `1` to `0`

Both are the same empty-set case. The disjoint cases (`'1111'` vs `'0000'`,
`'1000'` vs `'0000'`) are unchanged at `1`.

## Verification

`make installcheck` on Postgres 16, before and after:

| Build | Result |
| --- | --- |
| Without the patch, new expectation | `bit` fails, 13/14 pass |
| With the patch | **14/14 pass** |

The first row is the important one: reverting only the C change makes the
regression test fail, so the test genuinely pins the bug rather than agreeing
with the code.

## Changelog

Added a `Fixed` line under the unreleased `0.9.0` section.


inline patch 1: CHANGELOG.md, src/bitutils.c, test/expected/bit.out (+13/-3 lines) download inline-1.patchdiff --git a/CHANGELOG.md b/CHANGELOG.md index a724b193a..eda41606d 100644 --- a/CHANGELOG.md +++ b/CHANGELOG.md @@ -6,6 +6,7 @@ - Improved `amvalidate` for indexes - Improved property testing for indexes - Fixed possible error with iterative index scans during HNSW vacuuming +- Fixed Jaccard distance for two empty bit vectors - Dropped support for Postgres 13 and 14 ## 0.8.7 (2026-10-01) diff --git a/src/bitutils.c b/src/bitutils.c index a83776dd6..0a7315a46 100644 --- a/src/bitutils.c +++ b/src/bitutils.c @@ -124,8 +124,17 @@ BitJaccardDistanceDefault(uint32 bytes, unsigned char *ax, unsigned char *bx, ui bb += pg_number_of_ones[bx[i]]; } + /* + * An empty intersection means distance 1, unless both vectors are empty: + * two empty sets are identical, so their distance is 0. + */ if (ab == 0) - return 1; + { + if (aa == 0 && bb == 0) + return 0; + else + return 1; + } else return 1 - (ab / ((double) (aa + bb - ab))); } diff --git a/test/expected/bit.out b/test/expected/bit.out index 7c10bc4b8..58d4bb3b2 100644 --- a/test/expected/bit.out +++ b/test/expected/bit.out @@ -107,7 +107,7 @@ SELECT jaccard_distance('1000', '0000'); SELECT jaccard_distance('0000', '0000'); jaccard_distance ------------------ - 1 + 0 (1 row) SELECT jaccard_distance('10101010101010101010', '01010101010101010101'); @@ -137,7 +137,7 @@ SELECT jaccard_distance('1100000000000000000000000000000000000000000000000000000 SELECT jaccard_distance('', ''); jaccard_distance ------------------ - 1 + 0 (1 row) SELECT jaccard_distance('1111', '000');
^ permalink raw [nested|flat] 4+ messages in thread

* Re: [pgvector/pgvector] PR #1056: Fixed Jaccard distance for two empty bit vectors
@ 2026-11-03 17:34  "Ksschkw (@Ksschkw)" <noreply+Ksschkw@github.com>
  2 siblings, 0 replies; 4+ messages in thread

From: Ksschkw (@Ksschkw) @ 2026-11-03 17:34 UTC (permalink / raw)
  To: pgvector/pgvector <noreply+pgvector-pgvector@github.com>

Answering the question you asked on the issue — the practical case, briefly.

An all-zero bit vector is what you get when the source yields no bits: empty
or stopword-only text, or an empty tag/feature set. Under distance `1`, such a
row is tied at *maximal* distance with every other row, including itself. Two
consequences:

1. It cannot be distinguished as its own nearest neighbour, so an index/search
   round trip fails for exactly the rows that carry no signal. `<~>` on the same
   pair returns 0, so the two operators disagree about the same input.
2. Identical empty documents cannot be deduplicated by Jaccard similarity, so a
   "find duplicates" query silently misses them.

Nearest-neighbour search over bit vectors is usually about tag or feature
overlap, where empty rows are ordinary rather than exceptional.

That said, your point stands that scikit-learn and RDKit return 1, and the
distance is genuinely undefined for two empty sets. If you would rather keep 1
as the documented behaviour, I am happy to close this and open a documentation
change instead — either way the choice should be stated, not discovered.

Your call; no urgency from my side.


^ permalink  raw  [nested|flat] 4+ messages in thread

* Re: [pgvector/pgvector] PR #1056: Fixed Jaccard distance for two empty bit vectors
@ 2026-11-03 18:39  "ankane (@ankane)" <noreply+ankane@github.com>
  2 siblings, 0 replies; 4+ messages in thread

From: ankane (@ankane) @ 2026-11-03 18:39 UTC (permalink / raw)
  To: pgvector/pgvector <noreply+pgvector-pgvector@github.com>

Hi @Ksschkw, there's already [a branch](https://github.com/pgvector/pgvector/compare/jaccard-metric) for this.

^ permalink  raw  [nested|flat] 4+ messages in thread

* Re: [pgvector/pgvector] PR #1056: Fixed Jaccard distance for two empty bit vectors
@ 2026-11-03 18:39  "ankane (@ankane)" <noreply+ankane@github.com>
  2 siblings, 0 replies; 4+ messages in thread

From: ankane (@ankane) @ 2026-11-03 18:39 UTC (permalink / raw)
  To: pgvector/pgvector <noreply+pgvector-pgvector@github.com>

@ankane closed this.

^ permalink  raw  [nested|flat] 4+ messages in thread


end of thread, other threads:[~2026-11-03 18:39 UTC | newest]

Thread overview: 4+ messages (download: mbox mbox.gz follow: Atom feed)
-- links below jump to the message on this page --
2026-11-03 13:44 [pgvector/pgvector] PR #1056: Fixed Jaccard distance for two empty bit vectors "Ksschkw (@Ksschkw)" <noreply+Ksschkw@github.com>
2026-11-03 17:34 ` "Ksschkw (@Ksschkw)" <noreply+Ksschkw@github.com>
2026-11-03 18:39 ` "ankane (@ankane)" <noreply+ankane@github.com>
2026-11-03 18:39 ` "ankane (@ankane)" <noreply+ankane@github.com>

This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox