public inbox for [email protected]help / color / mirror / Atom feed
[PATCH v10 11/17] table_scan_bitmap_next_block counts lossy and exact pages 3+ messages / 3 participants [nested] [flat]
* [PATCH v10 11/17] table_scan_bitmap_next_block counts lossy and exact pages @ 2024-03-22 21:09 Melanie Plageman <[email protected]> 0 siblings, 0 replies; 3+ messages in thread From: Melanie Plageman @ 2024-03-22 21:09 UTC (permalink / raw) Now that the table_scan_bitmap_next_block() callback only returns false when the bitmap is exhausted, it is simpler to move the management of the lossy and exact page counters into it. We will eventually remove this callback and table_scan_bitmap_next_tuple() will update those counters when a new block is read in. --- src/backend/access/heap/heapam_handler.c | 8 ++++++-- src/backend/executor/nodeBitmapHeapscan.c | 9 ++------- src/include/access/tableam.h | 21 +++++++++++++-------- 3 files changed, 21 insertions(+), 17 deletions(-) diff --git a/src/backend/access/heap/heapam_handler.c b/src/backend/access/heap/heapam_handler.c index c76849a98e..d85fee1e50 100644 --- a/src/backend/access/heap/heapam_handler.c +++ b/src/backend/access/heap/heapam_handler.c @@ -2114,7 +2114,8 @@ heapam_estimate_rel_size(Relation rel, int32 *attr_widths, static bool heapam_scan_bitmap_next_block(TableScanDesc scan, - bool *recheck, bool *lossy, BlockNumber *blockno) + bool *recheck, BlockNumber *blockno, + long *lossy_pages, long *exact_pages) { HeapScanDesc hscan = (HeapScanDesc) scan; BlockNumber block; @@ -2264,7 +2265,10 @@ heapam_scan_bitmap_next_block(TableScanDesc scan, Assert(ntup <= MaxHeapTuplesPerPage); hscan->rs_ntuples = ntup; - *lossy = tbmres->ntuples < 0; + if (tbmres->ntuples < 0) + (*lossy_pages)++; + else + (*exact_pages)++; /* * Return true to indicate that a valid block was found and the bitmap is diff --git a/src/backend/executor/nodeBitmapHeapscan.c b/src/backend/executor/nodeBitmapHeapscan.c index fe471a8a0c..076e1ff674 100644 --- a/src/backend/executor/nodeBitmapHeapscan.c +++ b/src/backend/executor/nodeBitmapHeapscan.c @@ -119,7 +119,6 @@ BitmapHeapNext(BitmapHeapScanState *node) { ExprContext *econtext; TableScanDesc scan; - bool lossy; TIDBitmap *tbm; TupleTableSlot *slot; ParallelBitmapHeapState *pstate = node->pstate; @@ -298,14 +297,10 @@ new_page: BitmapAdjustPrefetchIterator(node); - if (!table_scan_bitmap_next_block(scan, &node->recheck, &lossy, &node->blockno)) + if (!table_scan_bitmap_next_block(scan, &node->recheck, &node->blockno, + &node->lossy_pages, &node->exact_pages)) break; - if (lossy) - node->lossy_pages++; - else - node->exact_pages++; - /* * If serial, we can error out if the the prefetch block doesn't stay * ahead of the current block. diff --git a/src/include/access/tableam.h b/src/include/access/tableam.h index 29387166c1..edc54ecffe 100644 --- a/src/include/access/tableam.h +++ b/src/include/access/tableam.h @@ -797,8 +797,8 @@ typedef struct TableAmRoutine * work to allow scan_bitmap_next_tuple() to return tuples (e.g. it might * make sense to perform tuple visibility checks at this time). * - * lossy indicates whether or not the block's representation in the bitmap - * is lossy or exact. + * lossy_pages is incremented if the block's representation in the bitmap + * is lossy, otherwise, exact_pages is incremented. * * XXX: Currently this may only be implemented if the AM uses md.c as its * storage manager, and uses ItemPointer->ip_blkid in a manner that maps @@ -815,8 +815,10 @@ typedef struct TableAmRoutine * scan_bitmap_next_tuple need to exist, or neither. */ bool (*scan_bitmap_next_block) (TableScanDesc scan, - bool *recheck, bool *lossy, - BlockNumber *blockno); + bool *recheck, + BlockNumber *blockno, + long *lossy_pages, + long *exact_pages); /* * Fetch the next tuple of a bitmap table scan into `slot` and return true @@ -1994,15 +1996,17 @@ table_relation_estimate_size(Relation rel, int32 *attr_widths, /* * Prepare to fetch / check / return tuples as part of a bitmap table scan. * `scan` needs to have been started via table_beginscan_bm(). Returns false if - * there are no more blocks in the bitmap, true otherwise. lossy is set to true - * if bitmap is lossy for the selected block and false otherwise. + * there are no more blocks in the bitmap, true otherwise. lossy_pages is + * incremented if bitmap is lossy for the selected block and exact_pages is + * incremented otherwise. * * Note, this is an optionally implemented function, therefore should only be * used after verifying the presence (at plan time or such). */ static inline bool table_scan_bitmap_next_block(TableScanDesc scan, - bool *recheck, bool *lossy, BlockNumber *blockno) + bool *recheck, BlockNumber *blockno, + long *lossy_pages, long *exact_pages) { /* * We don't expect direct calls to table_scan_bitmap_next_block with valid @@ -2013,7 +2017,8 @@ table_scan_bitmap_next_block(TableScanDesc scan, elog(ERROR, "unexpected table_scan_bitmap_next_block call during logical decoding"); return scan->rs_rd->rd_tableam->scan_bitmap_next_block(scan, recheck, - lossy, blockno); + blockno, lossy_pages, + exact_pages); } /* -- 2.40.1 --3o7pc6dfau5a5hry Content-Type: text/x-diff; charset=us-ascii Content-Disposition: attachment; filename="v10-0012-Hard-code-TBMIterateResult-offsets-array-size.patch" ^ permalink raw reply [nested|flat] 3+ messages in thread
* Re: SIMD optimization for list_sort @ 2024-11-22 16:01 Heikki Linnakangas <[email protected]> 0 siblings, 1 reply; 3+ messages in thread From: Heikki Linnakangas @ 2024-11-22 16:01 UTC (permalink / raw) To: Giacchino, Luca <[email protected]>; [email protected] <[email protected]>; +Cc: R, Rakshit <[email protected]>; Shankaran, Akash <[email protected]>; Devulapalli, Raghuveer <[email protected]> On 22/11/2024 01:27, Giacchino, Luca wrote: > The existing list_sort takes a comparator function to compare pairs of > ListCell. On the other hand, x86-simd-sort requires an array of numeric > values to sort, and it returns an array of sorted indices. To enable > x86-simd-sort, we add new list_sort_simd functions that take an > extractor function. The function extracts a value (float or uint32) from > a ListCell. Those values are then collected into an array for x86-simd- > sort to work on. A comparator function can still be passed to be used as > tie-breaker. > > typedef float (*list_sort_extractor_float)(const ListCell *a); > > typedef uint32 (*list_sort_extractor_uint32)(const ListCell *a); > > void list_sort_simd_float(List *list, list_sort_extractor_float extract, > list_sort_comparator cmp); > > void list_sort_simd_uint32(List *list, list_sort_extractor_uint32 > extract, list_sort_comparator cmp); > > These functions will exist alongside the current list_sort. Existing > list_sort use cases in Postgres or extensions will not be affected by > default, and they can be converted to list_sort_simd functions where it > makes sense in terms of performance. I'd suggest targeting pg_qsort() directly, instead of list_sort(). list_sort() is not used in very performance critical parts. > We identified a first use case for list_sort_simd_float in pgvector. As > part of HNSW index construction, pgvector uses list_sort to sort > candidate vectors by distance. Using list_sort_simd_float, we observed > reduction in index build time in some scenarios. For example, we > observed 7% reduction in index build time with the gist-960 dataset and > 10% with the dbpedia-openai-1000k dataset (ANN-Benchmarks, HNSW index > with halfvec, m=80). We are also looking into microbenchmarks to measure > list_sort performance independently. That's interesting. I'd suggest proposing this to the pgvector project directly, since pgvector would immediately benefit. > We’d appreciate feedback on this approach. In the meantime, we will > complete the patch to share. We also plan to extend SIMD-based sort to > tuple sort in the future. If you could use this to speed up tuple sorting, that would be much more interesting for PostgreSQL itself. -- Heikki Linnakangas Neon (https://neon.tech) ^ permalink raw reply [nested|flat] 3+ messages in thread
* Re: SIMD optimization for list_sort @ 2024-11-22 21:10 Nathan Bossart <[email protected]> parent: Heikki Linnakangas <[email protected]> 0 siblings, 0 replies; 3+ messages in thread From: Nathan Bossart @ 2024-11-22 21:10 UTC (permalink / raw) To: Heikki Linnakangas <[email protected]>; +Cc: Giacchino, Luca <[email protected]>; [email protected] <[email protected]>; R, Rakshit <[email protected]>; Shankaran, Akash <[email protected]>; Devulapalli, Raghuveer <[email protected]> On Fri, Nov 22, 2024 at 06:01:22PM +0200, Heikki Linnakangas wrote: > On 22/11/2024 01:27, Giacchino, Luca wrote: >> We´d appreciate feedback on this approach. In the meantime, we will >> complete the patch to share. We also plan to extend SIMD-based sort to >> tuple sort in the future. > > If you could use this to speed up tuple sorting, that would be much more > interesting for PostgreSQL itself. +1 -- nathan ^ permalink raw reply [nested|flat] 3+ messages in thread
end of thread, other threads:[~2024-11-22 21:10 UTC | newest] Thread overview: 3+ messages (download: mbox mbox.gz follow: Atom feed) -- links below jump to the message on this page -- 2024-03-22 21:09 [PATCH v10 11/17] table_scan_bitmap_next_block counts lossy and exact pages Melanie Plageman <[email protected]> 2024-11-22 16:01 Re: SIMD optimization for list_sort Heikki Linnakangas <[email protected]> 2024-11-22 21:10 ` Re: SIMD optimization for list_sort Nathan Bossart <[email protected]>
This inbox is served by agora; see mirroring instructions for how to clone and mirror all data and code used for this inbox