pg.ddx.io  pgvector/pgvector GitHub issues and pull requests  
help / color / mirror / Atom feed
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.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();

view thread (8+ messages)  latest in thread

Message-ID: <gh-pgvector-pgvector-1058@github.com>
Permalink:  ../gh-pgvector-pgvector-1058@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