pg.ddx.io pgvector/pgvector GitHub issues and pull requests
help / color / mirror / Atom feed[pgvector/pgvector] PR #1058: Improved performance of IVFFlat index scans
8+ messages / 2 participants
[nested] [flat]
* [pgvector/pgvector] PR #1058: Improved performance of IVFFlat index scans
@ 2026-11-05 22:40 "Waterpine (@Waterpine)" <noreply+Waterpine@github.com>
0 siblings, 0 replies; 8+ messages in thread
From: Waterpine (@Waterpine) @ 2026-11-05 22:40 UTC (permalink / raw)
To: pgvector/pgvector <noreply+pgvector-pgvector@github.com>
## What
IVFFlat scans currently put every item of the probed lists into a tuplesort (one virtual tuple per item) and sort them all before returning the first row. Typical queries (`ORDER BY ... LIMIT k`) only consume a few of them.
This keeps `(distance, tid)` in a plain array and builds a binary heap when the scan has collected its items, so rows are returned with `O(n + k log n)` work instead of `O(n log n)`. The array is limited to half of `work_mem`; if a scan collects more items than that, the items are moved to the existing tuplesort, which spills to disk exactly as before. Iterative scans reset the state for every batch.
Only `ivfscan.c` and `ivfflat.h` change. Distance functions, fmgr calls and the opclass interface are untouched.
## Results
Measured against `master` with only this change applied (PostgreSQL 16.15, gcc 13.3, 2 x Xeon E5-2630 v3, synthetic Gaussian-mixture data, 101k x 768-d, `lists = 316`, `ivfflat.probes = 10`, `SELECT id ... ORDER BY embedding <-> $1 LIMIT 10`, `shared_buffers = 8GB` prewarmed, `work_mem = 64MB` (a scan collects roughly 3,200 items, which also fit in memory at the default 4MB), 7 rounds, balanced order, fresh server per round; ratios are this change / master with a bootstrap 95% CI):
| metric | master | this change | ratio |
|---|---|---|---|
| latency p50 | 17.1 ms | 10.9 ms | 0.637 [0.622, 0.652] |
| latency p95 | 26.5 ms | 14.0 ms | 0.529 [0.515, 0.543] |
| throughput (6 clients) | 284 tps | 414 tps | 1.469 [1.441, 1.503] |
| backend private memory (Pss_Anon) | 3.93 MiB | 2.22 MiB | -43.6% |
A second, independent 10-round run gave p50 0.644, p95 0.549, throughput 1.462. HNSW and exact-scan workloads on the same builds are unchanged within the noise between identical builds (about 3%). Recall@10 on the same index is identical to master for all workloads.
## Behavior
- Items with exactly equal distances can be returned in a different order than before (the order was unspecified).
- Memory stays within about 1.5 x `work_mem`: the array is limited to half of it, and while its items are moved to the tuplesort (which is limited by `work_mem` before it spills) both exist; the array is freed afterwards.
## Tests
`test/t/049_ivfflat_scan_order.pl`: results of a full scan equal an exact scan, with `work_mem = 64kB` (spills) and `4MB` (in memory), top-k with many duplicate distances, iterative scans with a filter, and nested loop rescans. It passes on `master` too. Injecting a wrong heap order, dropping items when moving to the tuplesort, or not resetting the items on rescan makes it fail.
## Not measured
Only one platform and synthetic data. Index sizes that do not fit in memory (I/O bound scans) were not measured.
inline patch 1: src/ivfflat.h, src/ivfscan.c, test/t/049_ivfflat_scan_order.pl (+238/-16 lines) download inline-1.patch
diff --git a/src/ivfflat.h b/src/ivfflat.h
index d5d929645..f7af09dbf 100644
--- a/src/ivfflat.h
+++ b/src/ivfflat.h
@@ -271,6 +271,12 @@ typedef struct IvfflatScanList
double distance;
} IvfflatScanList;
+typedef struct IvfflatScanItem
+{
+ double distance;
+ ItemPointerData heaptid;
+} IvfflatScanItem;
+
typedef struct IvfflatScanOpaqueData
{
const IvfflatTypeInfo *typeInfo;
@@ -281,6 +287,13 @@ typedef struct IvfflatScanOpaqueData
Datum value;
MemoryContext tmpCtx;
+ /* Heap of items (used instead of sorting when it fits in work_mem) */
+ IvfflatScanItem *items;
+ int itemsLength;
+ int itemsCapacity;
+ int itemsLimit;
+ bool useSort;
+
/* Sorting */
Tuplesortstate *sortstate;
TupleDesc tupdesc;
diff --git a/src/ivfscan.c b/src/ivfscan.c
index 623e5fa7b..d12e264e5 100644
--- a/src/ivfscan.c
+++ b/src/ivfscan.c
@@ -14,6 +14,7 @@
#include "miscadmin.h"
#include "pgstat.h"
#include "storage/bufmgr.h"
+#include "utils/float.h"
#include "utils/memutils.h"
#include "utils/rel.h"
#include "utils/snapmgr.h"
@@ -117,6 +118,98 @@ GetScanLists(IndexScanDesc scan, Datum value)
Assert(pairingheap_is_empty(so->listQueue));
}
+/* Initial number of items to allocate */
+#define IVFFLAT_INITIAL_ITEMS 1024
+
+/*
+ * Move an item down the heap to restore heap order
+ */
+static void
+SiftDownItem(IvfflatScanItem * items, int length, int i)
+{
+ IvfflatScanItem item = items[i];
+
+ for (;;)
+ {
+ int child = 2 * i + 1;
+
+ if (child >= length)
+ break;
+
+ if (child + 1 < length && float8_lt(items[child + 1].distance, items[child].distance))
+ child++;
+
+ if (!float8_lt(items[child].distance, item.distance))
+ break;
+
+ items[i] = items[child];
+ i = child;
+ }
+
+ items[i] = item;
+}
+
+/*
+ * Add an item to the sort state
+ */
+static void
+SortItem(IvfflatScanOpaque so, double distance, ItemPointer heaptid)
+{
+ TupleTableSlot *slot = so->vslot;
+
+ ExecClearTuple(slot);
+ slot->tts_values[0] = Float8GetDatum(distance);
+ slot->tts_isnull[0] = false;
+ slot->tts_values[1] = PointerGetDatum(heaptid);
+ slot->tts_isnull[1] = false;
+ ExecStoreVirtualTuple(slot);
+
+ tuplesort_puttupleslot(so->sortstate, slot);
+}
+
+/*
+ * Add an item
+ *
+ * Items are kept in an array that is turned into a heap (only the closest
+ * items are typically needed), unless they do not fit in work_mem
+ */
+static inline void
+AddScanItem(IvfflatScanOpaque so, double distance, ItemPointer heaptid)
+{
+ if (!so->useSort && so->itemsLength == so->itemsCapacity)
+ {
+ if (so->itemsCapacity < so->itemsLimit)
+ {
+ so->itemsCapacity = Min(so->itemsCapacity * 2, so->itemsLimit);
+ so->items = repalloc(so->items, sizeof(IvfflatScanItem) * so->itemsCapacity);
+ }
+ else
+ {
+ /* Sort instead, which can spill to disk */
+ for (int i = 0; i < so->itemsLength; i++)
+ SortItem(so, so->items[i].distance, &so->items[i].heaptid);
+
+ so->itemsLength = 0;
+ so->useSort = true;
+
+ /* Free memory used by items */
+ pfree(so->items);
+ so->itemsCapacity = Min(so->itemsLimit, IVFFLAT_INITIAL_ITEMS);
+ so->items = palloc_array_checked(IvfflatScanItem, so->itemsCapacity);
+ }
+ }
+
+ if (so->useSort)
+ SortItem(so, distance, heaptid);
+ else
+ {
+ IvfflatScanItem *item = &so->items[so->itemsLength++];
+
+ item->distance = distance;
+ item->heaptid = *heaptid;
+ }
+}
+
/*
* Get items
*/
@@ -125,10 +218,11 @@ GetScanItems(IndexScanDesc scan, Datum value)
{
IvfflatScanOpaque so = (IvfflatScanOpaque) scan->opaque;
TupleDesc tupdesc = RelationGetDescr(scan->indexRelation);
- TupleTableSlot *slot = so->vslot;
int batchProbes = 0;
tuplesort_reset(so->sortstate);
+ so->itemsLength = 0;
+ so->useSort = false;
/* Search closest probes lists */
while (so->listIndex < so->maxProbes && (++batchProbes) <= so->probes)
@@ -158,19 +252,10 @@ GetScanItems(IndexScanDesc scan, Datum value)
datum = index_getattr(itup, 1, tupdesc, &isnull);
/*
- * Add virtual tuple
- *
* Use procinfo from the index instead of scan key for
* performance
*/
- ExecClearTuple(slot);
- slot->tts_values[0] = so->distfunc(so->procinfo, so->collation, datum, value);
- slot->tts_isnull[0] = false;
- slot->tts_values[1] = PointerGetDatum(&itup->t_tid);
- slot->tts_isnull[1] = false;
- ExecStoreVirtualTuple(slot);
-
- tuplesort_puttupleslot(so->sortstate, slot);
+ AddScanItem(so, DatumGetFloat8(so->distfunc(so->procinfo, so->collation, datum, value)), &itup->t_tid);
}
searchPage = IvfflatPageGetOpaque(page)->nextblkno;
@@ -179,7 +264,14 @@ GetScanItems(IndexScanDesc scan, Datum value)
}
}
- tuplesort_performsort(so->sortstate);
+ if (so->useSort)
+ tuplesort_performsort(so->sortstate);
+ else
+ {
+ /* Build heap */
+ for (int i = so->itemsLength / 2 - 1; i >= 0; i--)
+ SiftDownItem(so->items, so->itemsLength, i);
+ }
#if defined(IVFFLAT_MEMORY)
elog(INFO, "memory: %zu MB", MemoryContextMemAllocated(CurrentMemoryContext, true) / (1024 * 1024));
@@ -320,6 +412,17 @@ ivfflatbeginscan(Relation index, int nkeys, int norderbys)
*/
so->bas = GetAccessStrategy(BAS_BULKREAD);
+ /*
+ * Items that fit in half of work_mem, so memory stays within 1.5 times
+ * work_mem when moving items to the sort
+ */
+ so->itemsLimit = (int) Min((double) work_mem * 1024 / 2 / sizeof(IvfflatScanItem), MaxAllocSize / sizeof(IvfflatScanItem));
+ so->itemsLimit = Max(so->itemsLimit, 1);
+ so->itemsCapacity = Min(so->itemsLimit, IVFFLAT_INITIAL_ITEMS);
+ so->items = palloc_array_checked(IvfflatScanItem, so->itemsCapacity);
+ so->itemsLength = 0;
+ so->useSort = false;
+
so->listQueue = pairingheap_allocate(CompareLists, scan);
so->listPages = palloc_array_checked(BlockNumber, maxProbes);
so->listIndex = 0;
@@ -400,17 +503,32 @@ ivfflatgettuple(IndexScanDesc scan, ScanDirection dir)
so->value = value;
}
- while (!tuplesort_gettupleslot(so->sortstate, true, false, so->mslot, NULL))
+ for (;;)
{
+ if (so->useSort)
+ {
+ if (tuplesort_gettupleslot(so->sortstate, true, false, so->mslot, NULL))
+ {
+ heaptid = (ItemPointer) DatumGetPointer(slot_getattr(so->mslot, 2, &isnull));
+ scan->xs_heaptid = *heaptid;
+ break;
+ }
+ }
+ else if (so->itemsLength > 0)
+ {
+ /* Remove closest item from heap */
+ scan->xs_heaptid = so->items[0].heaptid;
+ so->items[0] = so->items[--so->itemsLength];
+ SiftDownItem(so->items, so->itemsLength, 0);
+ break;
+ }
+
if (so->listIndex == so->maxProbes)
return false;
IvfflatBench("GetScanItems", GetScanItems(scan, so->value));
}
- heaptid = (ItemPointer) DatumGetPointer(slot_getattr(so->mslot, 2, &isnull));
-
- scan->xs_heaptid = *heaptid;
scan->xs_recheck = false;
scan->xs_recheckorderby = false;
return true;
diff --git a/test/t/049_ivfflat_scan_order.pl b/test/t/049_ivfflat_scan_order.pl
new file mode 100644
index 000000000..1e6588af6
--- /dev/null
+++ b/test/t/049_ivfflat_scan_order.pl
@@ -0,0 +1,91 @@
+use strict;
+use warnings FATAL => 'all';
+use PostgreSQL::Test::Cluster;
+use PostgreSQL::Test::Utils;
+use Test::More;
+
+# IVFFlat scans must return rows in non-decreasing distance order and, when
+# all lists are probed, exactly the rows of a sequential scan.
+#
+# Items are kept in memory while they fit in half of work_mem (4MB below) and
+# are sorted with a tuplesort otherwise (64kB below), so cover both, as well as
+# iterative scans with a filter, rescans (nested loop joins), and duplicate
+# distances (ties).
+
+my $node = PostgreSQL::Test::Cluster->new('node');
+$node->init;
+$node->start;
+$node->safe_psql("postgres", "CREATE EXTENSION vector;");
+
+# Integer coordinates so there are many duplicate distances
+$node->safe_psql("postgres", qq(
+ SELECT setseed(0.5);
+ CREATE TABLE tst (i int4, c int4, v vector(8));
+ INSERT INTO tst SELECT i, i % 10, ARRAY(SELECT floor(random() * 8) FROM generate_series(1, 8) WHERE i > 0) FROM generate_series(1, 6000) i;
+ INSERT INTO tst SELECT 6000 + i, i % 10, v FROM tst WHERE i <= 500;
+ CREATE INDEX ON tst USING ivfflat (v vector_l2_ops) WITH (lists = 10);
+ ANALYZE tst;
+));
+
+my @queries = ("[0,0,0,0,0,0,0,0]", "[3,3,3,3,3,3,3,3]", "[7,1,6,2,5,3,4,0]");
+
+for my $wm ("64kB", "4MB")
+{
+ for my $q (@queries)
+ {
+ # All lists probed: same ordered distances as an exact scan
+ my $exact = $node->safe_psql("postgres", qq(
+ SET enable_indexscan = off; SET work_mem = '$wm';
+ SELECT string_agg((v <-> '$q')::text, ',' ORDER BY v <-> '$q') FROM tst;
+ ));
+ my $ivf = $node->safe_psql("postgres", qq(
+ SET enable_seqscan = off; SET work_mem = '$wm'; SET ivfflat.probes = 10;
+ SELECT string_agg(d::text, ',' ORDER BY n) FROM (SELECT row_number() OVER () AS n, d FROM (SELECT v <-> '$q' AS d FROM tst ORDER BY v <-> '$q') s) t;
+ ));
+ is($ivf, $exact, "work_mem $wm query $q: all distances in order");
+
+ # Every row is returned exactly once
+ my $count = $node->safe_psql("postgres", qq(
+ SET enable_seqscan = off; SET work_mem = '$wm'; SET ivfflat.probes = 10;
+ SELECT count(*), count(DISTINCT i) FROM (SELECT i FROM tst ORDER BY v <-> '$q') s;
+ ));
+ is($count, "6500|6500", "work_mem $wm query $q: all rows returned once");
+
+ # Top 10 with ties
+ my $top_exact = $node->safe_psql("postgres", qq(
+ SET enable_indexscan = off;
+ SELECT string_agg(d::text, ',' ORDER BY d) FROM (SELECT v <-> '$q' AS d FROM tst ORDER BY d LIMIT 10) s;
+ ));
+ my $top_ivf = $node->safe_psql("postgres", qq(
+ SET enable_seqscan = off; SET work_mem = '$wm'; SET ivfflat.probes = 10;
+ SELECT string_agg(d::text, ',' ORDER BY d) FROM (SELECT v <-> '$q' AS d FROM tst ORDER BY v <-> '$q' LIMIT 10) s;
+ ));
+ is($top_ivf, $top_exact, "work_mem $wm query $q: top 10 distances");
+
+ # Iterative scan with a filter
+ my $iter = $node->safe_psql("postgres", qq(
+ SET enable_seqscan = off; SET work_mem = '$wm'; SET ivfflat.probes = 1;
+ SET ivfflat.iterative_scan = relaxed_order; SET ivfflat.max_probes = 10;
+ SELECT count(*) FROM (SELECT i FROM tst WHERE c = 3 ORDER BY v <-> '$q' LIMIT 50) s;
+ ));
+ is($iter, "50", "work_mem $wm query $q: iterative scan with filter");
+ }
+
+ # Rescans: every outer row restarts the index scan, which must start from
+ # a clean state (including after a previous scan used the tuplesort)
+ my $nested_exact = $node->safe_psql("postgres", qq(
+ SET enable_indexscan = off; SET work_mem = '$wm';
+ SELECT string_agg(d::text, ',' ORDER BY i, d) FROM (
+ SELECT q.i, x.d FROM tst q CROSS JOIN LATERAL (SELECT t.v <-> q.v AS d FROM tst t ORDER BY t.v <-> q.v LIMIT 3 OFFSET 1) x WHERE q.i <= 100
+ ) s;
+ ));
+ my $nested_ivf = $node->safe_psql("postgres", qq(
+ SET enable_seqscan = off; SET work_mem = '$wm'; SET ivfflat.probes = 10;
+ SELECT string_agg(d::text, ',' ORDER BY i, d) FROM (
+ SELECT q.i, x.d FROM tst q CROSS JOIN LATERAL (SELECT t.v <-> q.v AS d FROM tst t ORDER BY t.v <-> q.v LIMIT 3 OFFSET 1) x WHERE q.i <= 100
+ ) s;
+ ));
+ is($nested_ivf, $nested_exact, "work_mem $wm: nested loop rescans");
+}
+
+done_testing();
^ permalink raw [nested|flat] 8+ messages in thread
* Re: [pgvector/pgvector] PR #1058: Improved performance of IVFFlat index scans
@ 2026-11-11 07:11 "Waterpine (@Waterpine)" <noreply+Waterpine@github.com>
6 siblings, 0 replies; 8+ messages in thread
From: Waterpine (@Waterpine) @ 2026-11-11 07:11 UTC (permalink / raw)
To: pgvector/pgvector <noreply+pgvector-pgvector@github.com>
Hi @ankane, any thoughts on this PR when you get a chance? Thanks!
^ permalink raw [nested|flat] 8+ messages in thread
* Re: [pgvector/pgvector] PR #1058: Improved performance of IVFFlat index scans
@ 2026-11-17 10:51 "ankane (@ankane)" <noreply+ankane@github.com>
6 siblings, 0 replies; 8+ messages in thread
From: ankane (@ankane) @ 2026-11-17 10:51 UTC (permalink / raw)
To: pgvector/pgvector <noreply+pgvector-pgvector@github.com>
Hi @Waterpine, thanks for the PR. The approach looks promising. Will spend some time digging into it.
It'd be good to see how performance compares for larger datasets (using the [recommended values](https://github.com/pgvector/pgvector#ivfflat) for lists and probes), as well as for searches that spill to disk if sort memory is limited to half of `work_mem` (so it never exceeds it).
^ permalink raw [nested|flat] 8+ messages in thread
* Re: [pgvector/pgvector] PR #1058: Improved performance of IVFFlat index scans
@ 2026-11-17 23:23 "Waterpine (@Waterpine)" <noreply+Waterpine@github.com>
6 siblings, 0 replies; 8+ messages in thread
From: Waterpine (@Waterpine) @ 2026-11-17 23:23 UTC (permalink / raw)
To: pgvector/pgvector <noreply+pgvector-pgvector@github.com>
Thanks, @ankane. I tested the local patch on PostgreSQL 16.15 with 1.05M synthetic 16-dimensional vectors, `lists = 1025`, `ivfflat.probes = 32`, and `LIMIT 10`. The patch gives tuplesort half of `work_mem`, with a 64 kB minimum.
| `work_mem` | Paired rounds | Baseline | Patched | Mean latency change |
| --- | ---: | ---: | ---: | ---: |
| 4 MB (default, both in memory) | 4 | 28.918 ms | 8.816 ms | −69.51% |
| 128 kB (both spill) | 16 | 39.897 ms | 40.153 ms | +0.64% |
Each round ran 100 queries per build with matched random seeds and alternating build order. At 128 kB, `EXPLAIN (ANALYZE, BUFFERS)` confirmed temporary reads and writes for both builds.
Dropping the two largest and two smallest paired latency differences leaves an average slowdown of 0.198 ms (about 0.5%).
These results are from one machine with prewarmed data. The memory-budget change is still local.
^ permalink raw [nested|flat] 8+ messages in thread
* Re: [pgvector/pgvector] PR #1058: Improved performance of IVFFlat index scans
@ 2026-11-18 00:06 "ankane (@ankane)" <noreply+ankane@github.com>
6 siblings, 0 replies; 8+ messages in thread
From: ankane (@ankane) @ 2026-11-18 00:06 UTC (permalink / raw)
To: pgvector/pgvector <noreply+pgvector-pgvector@github.com>
Thanks @Waterpine, I'm currently working on getting a version of this merged. It looks like the on-disk tuple sort is efficient with little memory, so I think we can use most of `work_mem` for the binary heap.
^ permalink raw [nested|flat] 8+ messages in thread
* Re: [pgvector/pgvector] PR #1058: Improved performance of IVFFlat index scans
@ 2026-11-18 05:45 "ankane (@ankane)" <noreply+ankane@github.com>
6 siblings, 0 replies; 8+ messages in thread
From: ankane (@ankane) @ 2026-11-18 05:45 UTC (permalink / raw)
To: pgvector/pgvector <noreply+pgvector-pgvector@github.com>
@ankane closed this.
^ permalink raw [nested|flat] 8+ messages in thread
* Re: [pgvector/pgvector] PR #1058: Improved performance of IVFFlat index scans
@ 2026-11-18 05:47 "ankane (@ankane)" <noreply+ankane@github.com>
6 siblings, 0 replies; 8+ messages in thread
From: ankane (@ankane) @ 2026-11-18 05:47 UTC (permalink / raw)
To: pgvector/pgvector <noreply+pgvector-pgvector@github.com>
Merged in the commit above. This is a pretty big win for performance. Thanks @Waterpine!
^ permalink raw [nested|flat] 8+ messages in thread
* Re: [pgvector/pgvector] PR #1058: Improved performance of IVFFlat index scans
@ 2026-11-18 10:34 "ankane (@ankane)" <noreply+ankane@github.com>
6 siblings, 0 replies; 8+ messages in thread
From: ankane (@ankane) @ 2026-11-18 10:34 UTC (permalink / raw)
To: pgvector/pgvector <noreply+pgvector-pgvector@github.com>
A few related follow-up improvements (just fyi):
1. `sortstate` is only initialized when needed
2. a message is reported at the `DEBUG1` level when the scan spills to disk (to help users tune)
3. there's a [branch](https://github.com/pgvector/pgvector/compare/ivfflat-scan-mem-multiplier) for an `ivfflat.scan_mem_multipler` option
I also suspect there could be additional gains with another heap type (like 4-ary).
Edit: Not seeing much difference with a 4-ary heap ([branch](https://github.com/pgvector/pgvector/compare/ivfflat-4-ary)).
^ permalink raw [nested|flat] 8+ messages in thread
end of thread, other threads:[~2026-11-18 10:34 UTC | newest]
Thread overview: 8+ messages (download: mbox mbox.gz follow: Atom feed)
-- links below jump to the message on this page --
2026-11-05 22:40 [pgvector/pgvector] PR #1058: Improved performance of IVFFlat index scans "Waterpine (@Waterpine)" <noreply+Waterpine@github.com>
2026-11-11 07:11 ` "Waterpine (@Waterpine)" <noreply+Waterpine@github.com>
2026-11-17 10:51 ` "ankane (@ankane)" <noreply+ankane@github.com>
2026-11-17 23:23 ` "Waterpine (@Waterpine)" <noreply+Waterpine@github.com>
2026-11-18 00:06 ` "ankane (@ankane)" <noreply+ankane@github.com>
2026-11-18 05:45 ` "ankane (@ankane)" <noreply+ankane@github.com>
2026-11-18 05:47 ` "ankane (@ankane)" <noreply+ankane@github.com>
2026-11-18 10:34 ` "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