pg.ddx.io pgvector/pgvector GitHub issues and pull requests
help / color / mirror / Atom feed[pgvector/pgvector] PR #86: Ivf index prefetch
11+ messages / 3 participants
[nested] [flat]
* [pgvector/pgvector] PR #86: Ivf index prefetch
@ 2023-04-06 15:07 "knizhnik (@knizhnik)" <noreply+knizhnik@github.com>
0 siblings, 0 replies; 11+ messages in thread
From: knizhnik (@knizhnik) @ 2023-04-06 15:07 UTC (permalink / raw)
To: pgvector/pgvector <noreply+pgvector-pgvector@github.com>
Implement prefetch for index scan. It can significantly increase query execution speed if index doesn't fit in memory.
inline patch 1: .github/workflows/build.yml, src/ivfflat.h, src/ivfinsert.c and 1 more (+87/-30 lines) download inline-1.patch
diff --git a/.github/workflows/build.yml b/.github/workflows/build.yml
index 6d00634f3..4c1d5266b 100644
--- a/.github/workflows/build.yml
+++ b/.github/workflows/build.yml
@@ -16,8 +16,6 @@ jobs:
os: ubuntu-20.04
- postgres: 12
os: ubuntu-20.04
- - postgres: 11
- os: ubuntu-18.04
steps:
- uses: actions/checkout@v3
- uses: ankane/setup-postgres@v1
diff --git a/src/ivfflat.h b/src/ivfflat.h
index 5bd7622ca..24a3ccdba 100644
--- a/src/ivfflat.h
+++ b/src/ivfflat.h
@@ -11,6 +11,7 @@
#include "access/reloptions.h"
#include "nodes/execnodes.h"
#include "port.h" /* for strtof() and random() */
+#include "storage/bufmgr.h"
#include "utils/sampling.h"
#include "utils/tuplesort.h"
#include "vector.h"
@@ -25,6 +26,8 @@
#define IVFFLAT_MAX_DIM 2000
+#define IVFFLAT_LIST_EXTEND_QUANTUM 8
+
/* Support functions */
#define IVFFLAT_DISTANCE_PROC 1
#define IVFFLAT_NORM_PROC 2
@@ -187,6 +190,12 @@ typedef struct IvfflatScanList
double distance;
} IvfflatScanList;
+typedef struct IvfflatTupleData
+{
+ ItemPointerData tid;
+ BlockNumber indexblkno;
+} IvfflatTuple;
+
typedef struct IvfflatScanOpaqueData
{
int probes;
@@ -204,6 +213,13 @@ typedef struct IvfflatScanOpaqueData
FmgrInfo *normprocinfo;
Oid collation;
+ /* Prefetch state */
+ size_t prefetch_limit;
+ size_t n_prefetch_requests;
+ size_t curr_tuple;
+ IvfflatTuple prefetched_tuples[MAX_IO_CONCURRENCY];
+ BlockNumber last_prefetched_index_blockno;
+
/* Lists */
pairingheap *listQueue;
IvfflatScanList lists[FLEXIBLE_ARRAY_MEMBER]; /* must come last */
diff --git a/src/ivfinsert.c b/src/ivfinsert.c
index 8d87267a2..92ee1710a 100644
--- a/src/ivfinsert.c
+++ b/src/ivfinsert.c
@@ -129,34 +129,36 @@ InsertTuple(Relation rel, Datum *values, bool *isnull, ItemPointer heap_tid, Rel
metabuf = ReadBuffer(rel, IVFFLAT_METAPAGE_BLKNO);
LockBuffer(metabuf, BUFFER_LOCK_EXCLUSIVE);
- /* Add a new page */
- newbuf = IvfflatNewBuffer(rel, MAIN_FORKNUM);
- newpage = GenericXLogRegisterBuffer(state, newbuf, GENERIC_XLOG_FULL_IMAGE);
+ for (int i = 0; i < IVFFLAT_LIST_EXTEND_QUANTUM; i++)
+ {
+ /* Add a new page */
+ newbuf = IvfflatNewBuffer(rel, MAIN_FORKNUM);
+ newpage = GenericXLogRegisterBuffer(state, newbuf, GENERIC_XLOG_FULL_IMAGE);
- /* Init new page */
- IvfflatInitPage(newbuf, newpage);
+ /* Init new page */
+ IvfflatInitPage(newbuf, newpage);
- /* Update insert page */
- insertPage = BufferGetBlockNumber(newbuf);
+ /* Update insert page */
+ insertPage = BufferGetBlockNumber(newbuf);
- /* Update previous buffer */
- IvfflatPageGetOpaque(page)->nextblkno = insertPage;
+ /* Update previous buffer */
+ IvfflatPageGetOpaque(page)->nextblkno = insertPage;
- /* Commit */
- MarkBufferDirty(newbuf);
- MarkBufferDirty(buf);
- GenericXLogFinish(state);
+ /* Commit */
+ MarkBufferDirty(newbuf);
+ MarkBufferDirty(buf);
+ GenericXLogFinish(state);
- /* Unlock extend relation lock as early as possible */
- UnlockReleaseBuffer(metabuf);
+ /* Unlock previous buffer */
+ UnlockReleaseBuffer(buf);
- /* Unlock previous buffer */
- UnlockReleaseBuffer(buf);
+ state = GenericXLogStart(rel);
+ buf = newbuf;
+ page = GenericXLogRegisterBuffer(state, buf, 0);
+ }
- /* Prepare new buffer */
- state = GenericXLogStart(rel);
- buf = newbuf;
- page = GenericXLogRegisterBuffer(state, buf, 0);
+ /* Unlock extend relation lock as early as possible */
+ UnlockReleaseBuffer(metabuf);
break;
}
}
diff --git a/src/ivfscan.c b/src/ivfscan.c
index 2fcaf3b12..f6b5e9e1c 100644
--- a/src/ivfscan.c
+++ b/src/ivfscan.c
@@ -5,7 +5,9 @@
#include "access/relscan.h"
#include "ivfflat.h"
#include "miscadmin.h"
+#include "optimizer/cost.h"
#include "storage/bufmgr.h"
+#include "utils/spccache.h"
#include "catalog/pg_operator_d.h"
#include "catalog/pg_type_d.h"
@@ -118,11 +120,9 @@ GetScanItems(IndexScanDesc scan, Datum value)
#endif
/*
- * Reuse same set of shared buffers for scan
- *
- * See postgres/src/backend/storage/buffer/README for description
+ * BAS_BULKREAD use ring buffer and so prevent prewarming cache even if there is enough space in shared buffers
*/
- BufferAccessStrategy bas = GetAccessStrategy(BAS_BULKREAD);
+ BufferAccessStrategy bas = GetAccessStrategy(BAS_NORMAL);
/* Search closest probes lists */
while (!pairingheap_is_empty(so->listQueue))
@@ -130,8 +130,15 @@ GetScanItems(IndexScanDesc scan, Datum value)
searchPage = ((IvfflatScanList *) pairingheap_remove_first(so->listQueue))->startPage;
/* Search all entry pages for list */
- while (BlockNumberIsValid(searchPage))
+ for (int chunk_offs = 0; BlockNumberIsValid(searchPage); chunk_offs++)
{
+ if (so->prefetch_limit != 0 && chunk_offs % IVFFLAT_LIST_EXTEND_QUANTUM == 0)
+ {
+ for (int i = 0; i < IVFFLAT_LIST_EXTEND_QUANTUM; i++)
+ {
+ PrefetchBuffer(scan->indexRelation, MAIN_FORKNUM, searchPage+i);
+ }
+ }
buf = ReadBufferExtended(scan->indexRelation, MAIN_FORKNUM, searchPage, RBM_NORMAL, bas);
LockBuffer(buf, BUFFER_LOCK_SHARE);
page = BufferGetPage(buf);
@@ -200,6 +207,8 @@ ivfflatbeginscan(Relation index, int nkeys, int norderbys)
so->normprocinfo = IvfflatOptionalProcInfo(index, IVFFLAT_NORM_PROC);
so->collation = index->rd_indcollation[0];
+ so->prefetch_limit = get_tablespace_io_concurrency(scan->indexRelation->rd_rel->reltablespace);
+
/* Create tuple description for sorting */
#if PG_VERSION_NUM >= 120000
so->tupdesc = CreateTemplateTupleDesc(3);
@@ -256,6 +265,7 @@ bool
ivfflatgettuple(IndexScanDesc scan, ScanDirection dir)
{
IvfflatScanOpaque so = (IvfflatScanOpaque) scan->opaque;
+ int n_prefetched;
/*
* Index can be used to scan backward, but Postgres doesn't support
@@ -291,16 +301,47 @@ ivfflatgettuple(IndexScanDesc scan, ScanDirection dir)
IvfflatBench("GetScanLists", GetScanLists(scan, value));
IvfflatBench("GetScanItems", GetScanItems(scan, value));
so->first = false;
+ so->n_prefetch_requests = 0;
+ so->last_prefetched_index_blockno = InvalidBlockNumber;
+ so->curr_tuple = 0;
/* Clean up if we allocated a new value */
if (value != scan->orderByData->sk_argument)
pfree(DatumGetPointer(value));
}
-
- if (tuplesort_gettupleslot(so->sortstate, true, false, so->slot, NULL))
+ for (n_prefetched = 0; so->n_prefetch_requests + n_prefetched < so->prefetch_limit
+ && tuplesort_gettupleslot(so->sortstate, true, false, so->slot, NULL); n_prefetched++)
{
ItemPointer tid = (ItemPointer) DatumGetPointer(slot_getattr(so->slot, 2, &so->isnull));
BlockNumber indexblkno = DatumGetInt32(slot_getattr(so->slot, 3, &so->isnull));
+ size_t tuple_index = (so->curr_tuple + so->n_prefetch_requests + n_prefetched) % MAX_IO_CONCURRENCY;
+ if (indexblkno != so->last_prefetched_index_blockno)
+ {
+ so->last_prefetched_index_blockno = indexblkno;
+ PrefetchBuffer(scan->indexRelation, MAIN_FORKNUM, indexblkno);
+ }
+ PrefetchBuffer(scan->heapRelation, MAIN_FORKNUM, ItemPointerGetBlockNumber(tid));
+ so->prefetched_tuples[tuple_index].tid = *tid;
+ so->prefetched_tuples[tuple_index].indexblkno = indexblkno;
+ }
+ so->n_prefetch_requests += n_prefetched;
+ if (so->n_prefetch_requests != 0 || tuplesort_gettupleslot(so->sortstate, true, false, so->slot, NULL))
+ {
+ ItemPointer tid;
+ BlockNumber indexblkno;
+
+ if (so->n_prefetch_requests != 0)
+ {
+ size_t tuple_index = so->curr_tuple++ % MAX_IO_CONCURRENCY;
+ so->n_prefetch_requests -= 1; /* consume one prefetched item */
+ tid = &so->prefetched_tuples[tuple_index].tid;
+ indexblkno = so->prefetched_tuples[tuple_index].indexblkno;
+ }
+ else
+ {
+ tid = (ItemPointer) DatumGetPointer(slot_getattr(so->slot, 2, &so->isnull));
+ indexblkno = DatumGetInt32(slot_getattr(so->slot, 3, &so->isnull));
+ }
#if PG_VERSION_NUM >= 120000
scan->xs_heaptid = *tid;
^ permalink raw [nested|flat] 11+ messages in thread
* Re: [pgvector/pgvector] PR #86: Ivf index prefetch
@ 2023-04-11 05:13 "ankane (@ankane)" <noreply+ankane@github.com>
9 siblings, 0 replies; 11+ messages in thread
From: ankane (@ankane) @ 2023-04-11 05:13 UTC (permalink / raw)
To: pgvector/pgvector <noreply+pgvector-pgvector@github.com>
Hi @knizhnik, thanks for the PR, and sorry for the delay. Will dig into this and see how the different aspects affect performance. If you have any benchmarks, please share.
^ permalink raw [nested|flat] 11+ messages in thread
* Re: [pgvector/pgvector] PR #86: Ivf index prefetch
@ 2023-04-12 11:11 "knizhnik (@knizhnik)" <noreply+knizhnik@github.com>
9 siblings, 0 replies; 11+ messages in thread
From: knizhnik (@knizhnik) @ 2023-04-12 11:11 UTC (permalink / raw)
To: pgvector/pgvector <noreply+pgvector-pgvector@github.com>
> Hi @knizhnik, thanks for the PR, and sorry for the delay. Will dig into this and see how the different aspects affect performance. If you have any benchmarks, please share.
Hi @ankane !
Prefetching is most critical when working set doesn't fir in memory (neither in shared buffers, neither in file system cache).
I am adopting pgvector extension for Neon (https://neon.tech/) - it is serverless Postgres with separated compute and storage.
In this case time of roundrip between compute and pageserver is very critical. In AWS if both compute and paeserver are located in the same AZ it is about 0.2msec. In this case prefetcing of pages in ivf_index allows to increase speed about 7 times - 5198msec vs. 777 msec for [GIST](http://corpus-texmex.irisa.fr/) with 1M records each with 960 dimensions from https://github.com/erikbern/ann-benchmarks. Unfortunately it is still ~30 times slower comparing with case when all data fits in shared buffers (23msec).
^ permalink raw [nested|flat] 11+ messages in thread
* Re: [pgvector/pgvector] PR #86: Ivf index prefetch
@ 2023-05-21 00:19 "ankane (@ankane)" <noreply+ankane@github.com>
9 siblings, 0 replies; 11+ messages in thread
From: ankane (@ankane) @ 2023-05-21 00:19 UTC (permalink / raw)
To: pgvector/pgvector <noreply+pgvector-pgvector@github.com>
Hi @knizhnik, sorry for not following up sooner. I think the four parts of this are:
1. Changing the buffer access strategy
2. Adding multiple (sequential) pages on inserts
3. Prefetching pages for `GetScanItems`
4. Prefetching heap pages
For 1, the current strategy was added to prevent [cache wiping](https://momjian.us/main/blogs/pgblog/2020.html#May_13_2020), but from the article, Postgres only uses `BAS_BULKREAD` when it expects to access more than 25% of the shared buffers, so we should probably do the same.
For 2, makes sense to me (related: #133).
Let's break 1 and 2 into separate PRs to discuss.
For 3 and 4, I'm not sure I'd like to add the complexity right now, but to avoid prefetching extra pages with 3, you'll want to use `IVFFLAT_LIST_EXTEND_QUANTUM` for the index build as well. You may also want to use a custom index version and prefetch conditionally to avoid prefetching extra pages with existing indexes.
^ permalink raw [nested|flat] 11+ messages in thread
* Re: [pgvector/pgvector] PR #86: Ivf index prefetch
@ 2023-05-21 11:11 "knizhnik (@knizhnik)" <noreply+knizhnik@github.com>
9 siblings, 0 replies; 11+ messages in thread
From: knizhnik (@knizhnik) @ 2023-05-21 11:11 UTC (permalink / raw)
To: pgvector/pgvector <noreply+pgvector-pgvector@github.com>
> For 1, the current strategy was added to prevent [cache wiping](https://momjian.us/main/blogs/pgblog/2020.html#May_13_2020), but from the article, Postgres only uses `BAS_BULKREAD` when it expects to access more than 25% of the shared buffers, so we should probably do the same.
Postgres is using `BAS_BULKREAD` for seqscan but here we perform index scan.
May be my assumption is wrong, but all embedding datasets I saw (for example fro ann-banchmark) are not so large and should fit in memory. In this case filling shared buffers with this ivfflat data should not cause cache wiping and lead to faster prewarming.
Right now it is not possible to prewarm infflat index without using special extension (pg_prewarm).
>
> Let's break 1 and 2 into separate PRs to discuss.
>
> For 3 and 4, I'm not sure I'd like to add the complexity right now, but to avoid prefetching extra pages with 3, you'll want to use `IVFFLAT_LIST_EXTEND_QUANTUM` for the index build as well. You may also want to use a custom index version and prefetch conditionally to avoid prefetching extra pages with existing indexes.
I agree with you. Such aggressive prefetching is needed mostly for Neon architecture.
In case of vanilla Postgres we can rely on OS read-ahead mechanism.
^ permalink raw [nested|flat] 11+ messages in thread
* Re: [pgvector/pgvector] PR #86: Ivf index prefetch
@ 2023-05-24 01:07 "jkatz (@jkatz)" <noreply+jkatz@github.com>
9 siblings, 0 replies; 11+ messages in thread
From: jkatz (@jkatz) @ 2023-05-24 01:07 UTC (permalink / raw)
To: pgvector/pgvector <noreply+pgvector-pgvector@github.com>
From my testing, I'm -1 on changing from `BAS_BULKREAD` to `BAS_NORMAL`, though I'd like to test a bit more so I can bring numbers I'm more confident in. For queries under the defaults (i.e. `ivfflat.probes` is `1`), this likely makes little difference. However, increasing the number of probes requires loading more pages into memory, both indexes and heap, and the benefits of `BAS_BULKREAD` becoming noticeable in this case as the vector dimensionality increases.
Assuming that "datasets fit into memory" may work on systems that are exclusively processing vector data, but my current experience from seeing people integrating pgvector is that it exists alongside current workloads.
^ permalink raw [nested|flat] 11+ messages in thread
* Re: [pgvector/pgvector] PR #86: Ivf index prefetch
@ 2023-05-24 06:05 "knizhnik (@knizhnik)" <noreply+knizhnik@github.com>
9 siblings, 0 replies; 11+ messages in thread
From: knizhnik (@knizhnik) @ 2023-05-24 06:05 UTC (permalink / raw)
To: pgvector/pgvector <noreply+pgvector-pgvector@github.com>
> From my testing, I'm -1 on changing from `BAS_BULKREAD` to `BAS_NORMAL`, though I'd like to test a bit more so I can bring numbers I'm more confident in. For queries under the defaults (i.e. `ivfflat.probes` is `1`), this likely makes little difference. However, increasing the number of probes requires loading more pages into memory, both indexes and heap, and the benefits of `BAS_BULKREAD` becoming noticeable in this case as the vector dimensionality increases.
>
> Assuming that "datasets fit into memory" may work on systems that are exclusively processing vector data, but my current experience from seeing people integrating pgvector is that it exists alongside current workloads.
Please notice that Postgres is using ring buffer strategies only for seqscan, not for index scan.
I wonder why ivfflat index scan is considered to be more close to seqscan rather than to index scan?
IMHO Postgres use very strange approach for buffer eviction when it is throwing away pages from shared buffers even if there are free buffers. It leads to worse performance even if it is enough free memory at the system to keep the whole data set in memory. Without usin special extensions like pg_prewarm it is not possible to to reach maximal possible speed. Yes, file system cache may help i this case, but it is about 15% slow then access to the page in shared buffers.
So I think that BAS_BULKREAD should be used at least when expected relation size is more than 1// or better 1/2 os shared buffers, but IMHO it is better not to use BAS_BULKREAD at all, because we are actually performing index scan and let buffer manager eviction algorithm do it work.
^ permalink raw [nested|flat] 11+ messages in thread
* Re: [pgvector/pgvector] PR #86: Ivf index prefetch
@ 2023-08-27 21:00 "ankane (@ankane)" <noreply+ankane@github.com>
9 siblings, 0 replies; 11+ messages in thread
From: ankane (@ankane) @ 2023-08-27 21:00 UTC (permalink / raw)
To: pgvector/pgvector <noreply+pgvector-pgvector@github.com>
Cleaning up stale PRs, but may revisit 1 and 2 in the future.
^ permalink raw [nested|flat] 11+ messages in thread
* Re: [pgvector/pgvector] PR #86: Ivf index prefetch
@ 2023-08-27 21:00 "ankane (@ankane)" <noreply+ankane@github.com>
9 siblings, 0 replies; 11+ messages in thread
From: ankane (@ankane) @ 2023-08-27 21:00 UTC (permalink / raw)
To: pgvector/pgvector <noreply+pgvector-pgvector@github.com>
@ankane closed this.
^ permalink raw [nested|flat] 11+ messages in thread
* Re: [pgvector/pgvector] PR #86: Ivf index prefetch
@ 2026-11-09 02:08 "ankane (@ankane)" <noreply+ankane@github.com>
9 siblings, 0 replies; 11+ messages in thread
From: ankane (@ankane) @ 2026-11-09 02:08 UTC (permalink / raw)
To: pgvector/pgvector <noreply+pgvector-pgvector@github.com>
Hi @knizhnik, just revisited this and agree it makes sense to use the default buffer access strategy like other index types, so made this change for 0.9.0 in the commit above. Also planning to try read stream / buffer prefetching for index pages.
^ permalink raw [nested|flat] 11+ messages in thread
* Re: [pgvector/pgvector] PR #86: Ivf index prefetch
@ 2026-11-09 06:34 "ankane (@ankane)" <noreply+ankane@github.com>
9 siblings, 0 replies; 11+ messages in thread
From: ankane (@ankane) @ 2026-11-09 06:34 UTC (permalink / raw)
To: pgvector/pgvector <noreply+pgvector-pgvector@github.com>
Added support for read streams for Postgres 18+ in d34e9d13ee8045367f864d0f99792e897d90f70a. Also plan to enable for Postgres 17, and use `PrefetchBuffer` for Postgres 15 and 16 (like HNSW).
^ permalink raw [nested|flat] 11+ messages in thread
end of thread, other threads:[~2026-11-09 06:34 UTC | newest]
Thread overview: 11+ messages (download: mbox mbox.gz follow: Atom feed)
-- links below jump to the message on this page --
2023-04-06 15:07 [pgvector/pgvector] PR #86: Ivf index prefetch "knizhnik (@knizhnik)" <noreply+knizhnik@github.com>
2023-04-11 05:13 ` "ankane (@ankane)" <noreply+ankane@github.com>
2023-04-12 11:11 ` "knizhnik (@knizhnik)" <noreply+knizhnik@github.com>
2023-05-21 00:19 ` "ankane (@ankane)" <noreply+ankane@github.com>
2023-05-21 11:11 ` "knizhnik (@knizhnik)" <noreply+knizhnik@github.com>
2023-05-24 01:07 ` "jkatz (@jkatz)" <noreply+jkatz@github.com>
2023-05-24 06:05 ` "knizhnik (@knizhnik)" <noreply+knizhnik@github.com>
2023-08-27 21:00 ` "ankane (@ankane)" <noreply+ankane@github.com>
2023-08-27 21:00 ` "ankane (@ankane)" <noreply+ankane@github.com>
2026-11-09 02:08 ` "ankane (@ankane)" <noreply+ankane@github.com>
2026-11-09 06: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