pg.ddx.io pgvector/pgvector GitHub issues and pull requests
help / color / mirror / Atom feed[pgvector/pgvector] PR #1059: Improved performance of inner product and cosine distance for sparsevec
2+ messages / 1 participants
[nested] [flat]
* [pgvector/pgvector] PR #1059: Improved performance of inner product and cosine distance for sparsevec
@ 2026-11-05 23:17 "Waterpine (@Waterpine)" <noreply+Waterpine@github.com>
0 siblings, 0 replies; 2+ messages in thread
From: Waterpine (@Waterpine) @ 2026-11-05 23:17 UTC (permalink / raw)
To: pgvector/pgvector <noreply+pgvector-pgvector@github.com>
## What
The inner product (and so the negative inner product and cosine distance) of two sparse vectors is a sequential merge of the two sorted index arrays with a data dependent branch per element. This adds an AVX2 path that compares blocks of up to eight indices from each vector at once and advances the block with the smaller last index. The scalar code is unchanged and is used when AVX2 is not available (runtime check, same pattern as `halfutils.c`).
Matches are found in increasing index order, so the products are summed in the same order as the scalar code and **results are bit-identical**.
## Results
Measured against `master` with only this change applied (PostgreSQL 16.15, gcc 13.3, 2 x Xeon E5-2630 v3 with AVX2 and no AVX-512, 7 rounds, balanced order, fresh server per round; ratios are this change / master with a bootstrap 95% CI):
- Kernel (`sparsevec` inner product / cosine through the fmgr call path): 0.420x time (2.38x faster) on 18 cases (10000 dimensions, 16 / 128 / 1024 non-zero elements, working sets from L1 to last-level cache); 0.348x (2.87x) on 4 held-out cases (16000 dimensions, 50 / 500 non-zero elements). L2 and L1 (unchanged) are 1.002x.
- All 308 paired (round, case) kernel results have the same checksum as `master`.
- HNSW with `sparsevec_ip_ops` (51k vectors, 30000 dimensions, 20-80 non-zero elements, `shared_buffers = 8GB` prewarmed, `ef_search = 40`, top 10): latency p50 1.219 -> 0.849 ms (0.693 [0.686, 0.700]), p95 0.675x, throughput 1.404x [1.375, 1.428].
- Recall@10 on the same index is identical to `master`.
## Tests
The existing tests only use vectors with a handful of non-zero elements, so they never go beyond one block of eight. This adds 8 pairs to `test/sql/sparsevec.sql`: disjoint vectors, 8 and 9 elements, a block that ends exactly where the next one begins, interleaved and long overlapping ranges, and an empty vector. Each inner product is compared with the same sum computed in SQL (values are small integers, so the sums are exact). The expected output was generated with `master` (scalar code) and passes unchanged with the AVX2 code.
To check that the tests can fail, I injected bugs into the AVX2 code: advancing the larger block instead of the smaller one is not detected by the existing tests and is detected by the new ones; the other bugs I tried (false matches from the padding lanes, loading eight lanes at the tail, counting only the first match in a block, re-comparing the last element of a block) are also detected by the existing tests.
## Platforms
Performance was measured on one x86-64 machine with synthetic data. The change builds without warnings with `-Wall -Wextra -Werror` and passes the SQL regression suite with gcc 13 (assertions enabled, without `-march` flags, and with dispatch disabled, which uses the scalar code) and with clang 17. It was not built with MSVC and not run under Valgrind. Without `USE_DISPATCH` (non-x86) nothing changes.
inline patch 1: src/sparsevec.c, src/sparsevec.h, src/vector.c and 2 more (+211/-0 lines) download inline-1.patch
diff --git a/src/sparsevec.c b/src/sparsevec.c
index b3b70b33a..1a15cb255 100644
--- a/src/sparsevec.c
+++ b/src/sparsevec.c
@@ -10,6 +10,7 @@
#include "halfvec.h"
#include "lib/stringinfo.h"
#include "libpq/pqformat.h"
+#include "port/pg_bitutils.h"
#include "sparsevec.h"
#include "utils/array.h"
#include "utils/builtins.h"
@@ -34,6 +35,74 @@
#define repalloc_array_checked(pointer, type, count) ((type *) repalloc(pointer, mul_size(sizeof(type), count)))
#endif
+#if defined(USE_DISPATCH)
+#define SPARSEVEC_DISPATCH
+#endif
+
+#ifdef SPARSEVEC_DISPATCH
+#include <immintrin.h>
+
+#if defined(USE__GET_CPUID)
+#include <cpuid.h>
+#else
+#include <intrin.h>
+#endif
+
+#ifdef _MSC_VER
+#define TARGET_AVX2
+#define TARGET_XSAVE
+#else
+#define TARGET_AVX2 __attribute__((target("avx2")))
+#define TARGET_XSAVE __attribute__((target("xsave")))
+#endif
+
+static bool SparsevecUseAvx2 = false;
+#endif
+
+#ifdef SPARSEVEC_DISPATCH
+#define CPU_FEATURE_OSXSAVE (1 << 27) /* F1 ECX */
+#define CPU_FEATURE_AVX2 (1 << 5) /* F7,0 EBX */
+
+TARGET_XSAVE static bool
+SupportsAvx2(void)
+{
+ unsigned int exx[4] = {0, 0, 0, 0};
+
+#if defined(USE__GET_CPUID)
+ __get_cpuid(1, &exx[0], &exx[1], &exx[2], &exx[3]);
+#else
+ __cpuid(exx, 1);
+#endif
+
+ /* Check OS supports XSAVE */
+ if ((exx[2] & CPU_FEATURE_OSXSAVE) != CPU_FEATURE_OSXSAVE)
+ return false;
+
+ /* Check XMM and YMM registers are enabled */
+ if ((_xgetbv(0) & 6) != 6)
+ return false;
+
+#if defined(USE__GET_CPUID)
+ __get_cpuid_count(7, 0, &exx[0], &exx[1], &exx[2], &exx[3]);
+#else
+ __cpuidex(exx, 7, 0);
+#endif
+
+ return (exx[1] & CPU_FEATURE_AVX2) == CPU_FEATURE_AVX2;
+}
+#endif
+
+/*
+ * Initialize distance functions
+ */
+void
+SparsevecInit(void)
+{
+#ifdef SPARSEVEC_DISPATCH
+ SparsevecUseAvx2 = SupportsAvx2();
+#endif
+}
+
typedef struct SparseInputElement
{
int32 index;
@@ -898,6 +967,84 @@ sparsevec_l2_squared_distance(PG_FUNCTION_ARGS)
PG_RETURN_FLOAT8((double) SparsevecL2SquaredDistance(a, b));
}
+#ifdef SPARSEVEC_DISPATCH
+/*
+ * Load up to eight indices, filling missing lanes with a value that is never
+ * a valid index
+ */
+TARGET_AVX2 static inline __m256i
+SparsevecLoadIndices(int32 *indices, int count, int32 fill)
+{
+ __m256i mask;
+
+ if (count >= 8)
+ return _mm256_loadu_si256((__m256i *) indices);
+
+ mask = _mm256_cmpgt_epi32(_mm256_set1_epi32(count), _mm256_setr_epi32(0, 1, 2, 3, 4, 5, 6, 7));
+ return _mm256_blendv_epi8(_mm256_set1_epi32(fill), _mm256_maskload_epi32(indices, mask), mask);
+}
+
+TARGET_AVX2 static float
+SparsevecInnerProductAvx2(SparseVector * a, SparseVector * b)
+{
+ float *ax = SPARSEVEC_VALUES(a);
+ float *bx = SPARSEVEC_VALUES(b);
+ float distance = 0.0;
+ int i = 0;
+ int j = 0;
+ __m256i rotate = _mm256_setr_epi32(1, 2, 3, 4, 5, 6, 7, 0);
+
+ /*
+ * Compare blocks of up to eight indices from each vector and advance the
+ * block with the smaller last index. Matches are found in increasing
+ * index order, so the sum is the same as with a sequential merge.
+ */
+ while (i < a->nnz && j < b->nnz)
+ {
+ int acount = Min(a->nnz - i, 8);
+ int bcount = Min(b->nnz - j, 8);
+ __m256i aidx = SparsevecLoadIndices(a->indices + i, acount, -1);
+ __m256i bidx = SparsevecLoadIndices(b->indices + j, bcount, -2);
+ __m256i eq = _mm256_cmpeq_epi32(aidx, bidx);
+ int32 alast = a->indices[i + acount - 1];
+ int32 blast = b->indices[j + bcount - 1];
+ uint32 mask;
+
+ for (int r = 1; r < 8; r++)
+ {
+ bidx = _mm256_permutevar8x32_epi32(bidx, rotate);
+ eq = _mm256_or_si256(eq, _mm256_cmpeq_epi32(aidx, bidx));
+ }
+
+ /* Matches are rare, so find the other position with a scan */
+ mask = _mm256_movemask_ps(_mm256_castsi256_ps(eq));
+ while (mask != 0)
+ {
+ int k = pg_rightmost_one_pos32(mask);
+
+ for (int l = 0; l < bcount; l++)
+ {
+ if (b->indices[j + l] == a->indices[i + k])
+ {
+ distance += ax[i + k] * bx[j + l];
+ break;
+ }
+ }
+
+ mask &= mask - 1;
+ }
+
+ if (alast <= blast)
+ i += acount;
+
+ if (blast <= alast)
+ j += bcount;
+ }
+
+ return distance;
+}
+#endif
+
/*
* Get the inner product of two sparse vectors
*/
@@ -909,6 +1056,11 @@ SparsevecInnerProduct(SparseVector * a, SparseVector * b)
float distance = 0.0;
int bpos = 0;
+#ifdef SPARSEVEC_DISPATCH
+ if (SparsevecUseAvx2)
+ return SparsevecInnerProductAvx2(a, b);
+#endif
+
for (int i = 0; i < a->nnz; i++)
{
int32 ai = a->indices[i];
diff --git a/src/sparsevec.h b/src/sparsevec.h
index e8ab355c4..5912e6b96 100644
--- a/src/sparsevec.h
+++ b/src/sparsevec.h
@@ -47,5 +47,6 @@ SPARSEVEC_VALUES(SparseVector * x)
}
SparseVector *InitSparseVector(int dim, int nnz);
+void SparsevecInit(void);
#endif
diff --git a/src/vector.c b/src/vector.c
index 9dcfd355b..a0df79988 100644
--- a/src/vector.c
+++ b/src/vector.c
@@ -62,6 +62,7 @@ _PG_init(void)
HalfvecInit();
HnswInit();
IvfflatInit();
+ SparsevecInit();
}
/*
diff --git a/test/expected/sparsevec.out b/test/expected/sparsevec.out
index 4bbb7e1f0..400c87301 100644
--- a/test/expected/sparsevec.out
+++ b/test/expected/sparsevec.out
@@ -685,3 +685,36 @@ SELECT l2_normalize('{2:3e37,4:3e-37,6:4e37,8:4e-37}/9'::sparsevec);
{2:0.6,6:0.8}/9
(1 row)
+-- inner product with many non-zero elements (values are small integers, so the sums are exact)
+CREATE TABLE sparse_cases (id int, a int[], b int[]);
+INSERT INTO sparse_cases VALUES
+ (1, ARRAY(SELECT generate_series(1, 39, 2)), ARRAY(SELECT generate_series(2, 40, 2))),
+ (2, ARRAY(SELECT generate_series(1, 8)), ARRAY(SELECT generate_series(1, 8))),
+ (3, ARRAY(SELECT generate_series(1, 9)), ARRAY(SELECT generate_series(1, 9))),
+ (4, ARRAY(SELECT generate_series(2, 200, 2)), ARRAY(SELECT generate_series(3, 300, 3))),
+ (5, ARRAY(SELECT generate_series(1, 8)), ARRAY(SELECT generate_series(8, 15))),
+ (6, ARRAY(SELECT generate_series(1, 120, 3)), ARRAY(SELECT generate_series(1, 120, 5))),
+ (7, ARRAY(SELECT generate_series(1, 500)), ARRAY(SELECT generate_series(250, 750))),
+ (8, ARRAY[]::int[], ARRAY(SELECT generate_series(1, 10)));
+WITH v AS (
+ SELECT id, a, b,
+ ('{' || coalesce((SELECT string_agg(i || ':' || (i % 5 + 1), ',' ORDER BY i) FROM unnest(a) i), '') || '}/1000')::sparsevec AS sa,
+ ('{' || coalesce((SELECT string_agg(i || ':' || (i % 5 + 1), ',' ORDER BY i) FROM unnest(b) i), '') || '}/1000')::sparsevec AS sb
+ FROM sparse_cases
+)
+SELECT id, -(sa <#> sb) AS inner_product,
+ sa <#> sb = -(SELECT coalesce(sum((i % 5 + 1) * (i % 5 + 1)), 0) FROM unnest(a) i WHERE i = ANY(b)) AS ok
+FROM v ORDER BY id;
+ id | inner_product | ok
+----+---------------+----
+ 1 | 0 | t
+ 2 | 84 | t
+ 3 | 109 | t
+ 4 | 359 | t
+ 5 | 16 | t
+ 6 | 32 | t
+ 7 | 2751 | t
+ 8 | 0 | t
+(8 rows)
+
+DROP TABLE sparse_cases;
diff --git a/test/sql/sparsevec.sql b/test/sql/sparsevec.sql
index 80ec6a997..34f342a5f 100644
--- a/test/sql/sparsevec.sql
+++ b/test/sql/sparsevec.sql
@@ -140,3 +140,27 @@ SELECT l2_normalize('{}/2'::sparsevec);
SELECT l2_normalize('{1:3e38}/1'::sparsevec);
SELECT l2_normalize('{1:3e38,2:1e-37}/2'::sparsevec);
SELECT l2_normalize('{2:3e37,4:3e-37,6:4e37,8:4e-37}/9'::sparsevec);
+
+-- inner product with many non-zero elements (values are small integers, so the sums are exact)
+CREATE TABLE sparse_cases (id int, a int[], b int[]);
+INSERT INTO sparse_cases VALUES
+ (1, ARRAY(SELECT generate_series(1, 39, 2)), ARRAY(SELECT generate_series(2, 40, 2))),
+ (2, ARRAY(SELECT generate_series(1, 8)), ARRAY(SELECT generate_series(1, 8))),
+ (3, ARRAY(SELECT generate_series(1, 9)), ARRAY(SELECT generate_series(1, 9))),
+ (4, ARRAY(SELECT generate_series(2, 200, 2)), ARRAY(SELECT generate_series(3, 300, 3))),
+ (5, ARRAY(SELECT generate_series(1, 8)), ARRAY(SELECT generate_series(8, 15))),
+ (6, ARRAY(SELECT generate_series(1, 120, 3)), ARRAY(SELECT generate_series(1, 120, 5))),
+ (7, ARRAY(SELECT generate_series(1, 500)), ARRAY(SELECT generate_series(250, 750))),
+ (8, ARRAY[]::int[], ARRAY(SELECT generate_series(1, 10)));
+
+WITH v AS (
+ SELECT id, a, b,
+ ('{' || coalesce((SELECT string_agg(i || ':' || (i % 5 + 1), ',' ORDER BY i) FROM unnest(a) i), '') || '}/1000')::sparsevec AS sa,
+ ('{' || coalesce((SELECT string_agg(i || ':' || (i % 5 + 1), ',' ORDER BY i) FROM unnest(b) i), '') || '}/1000')::sparsevec AS sb
+ FROM sparse_cases
+)
+SELECT id, -(sa <#> sb) AS inner_product,
+ sa <#> sb = -(SELECT coalesce(sum((i % 5 + 1) * (i % 5 + 1)), 0) FROM unnest(a) i WHERE i = ANY(b)) AS ok
+FROM v ORDER BY id;
+
+DROP TABLE sparse_cases;
^ permalink raw [nested|flat] 2+ messages in thread
* Re: [pgvector/pgvector] PR #1059: Improved performance of inner product and cosine distance for sparsevec
@ 2026-11-11 07:11 "Waterpine (@Waterpine)" <noreply+Waterpine@github.com>
0 siblings, 0 replies; 2+ messages in thread
From: Waterpine (@Waterpine) @ 2026-11-11 07:11 UTC (permalink / raw)
To: pgvector/pgvector <noreply+pgvector-pgvector@github.com>
Hi @ankane, have you had a chance to look at this PR? I’d appreciate any feedback when you have time. Thanks!
^ permalink raw [nested|flat] 2+ messages in thread
end of thread, other threads:[~2026-11-11 07:11 UTC | newest]
Thread overview: 2+ messages (download: mbox mbox.gz follow: Atom feed)
-- links below jump to the message on this page --
2026-11-05 23:17 [pgvector/pgvector] PR #1059: Improved performance of inner product and cosine distance for sparsevec "Waterpine (@Waterpine)" <noreply+Waterpine@github.com>
2026-11-11 07:11 Re: [pgvector/pgvector] PR #1059: Improved performance of inner product and cosine distance for sparsevec "Waterpine (@Waterpine)" <noreply+Waterpine@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