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.patch
diff --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