pg.ddx.io pgvector/pgvector GitHub issues and pull requests
help / color / mirror / Atom feedFrom: knizhnik (@knizhnik) <noreply+knizhnik@github.com>
To: pgvector/pgvector <noreply+pgvector-pgvector@github.com>
Subject: [pgvector/pgvector] PR #86: Ivf index prefetch
Date: Thu, 06 Apr 2023 15:07:07 +0000
Message-ID: <gh-pgvector-pgvector-86@github.com> (raw)
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;
view thread (11+ messages) latest in thread
Message-ID: <gh-pgvector-pgvector-86@github.com>
Permalink: ../gh-pgvector-pgvector-86@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