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