From: Waterpine (@Waterpine) <noreply+Waterpine@github.com>
To: pgvector/pgvector <noreply+pgvector-pgvector@github.com>
Subject: [pgvector/pgvector] PR #1058: Improved performance of IVFFlat index scans
Date: Thu, 05 Nov 2026 22:40:09 +0000
Message-ID: <gh-pgvector-pgvector-1058@github.com> (raw)
## 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.patchdiff --git a/src/ivfflat.h b/src/ivfflat.hindex 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.cindex 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.plnew file mode 100644index 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();