>>> On this note, there has been a proposed (but as far as I know untested)
>>> patch to speed up this sort in a much simpler way, in this thread
>>>
>>> https://www.postgresql.org/message-id/
>>> CA%2BhUKGKztHEWm676csTFjYzortziWmOcf8HDss2Zr0muZ2xfEg%40mail.gmail.com
>>> <https://www.postgresql.org/message-id/
>>> CA%2BhUKGKztHEWm676csTFjYzortziWmOcf8HDss2Zr0muZ2xfEg%40mail.gmail.com>
>>>
>>> where you may find this patch
>>>
>>> https://www.postgresql.org/message-id/attachment/120560/0007-Specialize-
>>> pagetable-sort-routines-in-tidbitmap.c.patch <https://
>>> www.postgresql.org/message-id/attachment/120560/0007-Specialize-
>>> pagetable-sort-routines-in-tidbitmap.c.patch>
>>
>> Thanks for the pointer. I've applied that change to my patch set. See
>> other mail. It helped a lot further reducing the sort time in each
>> parallel worker.
>
> If that's the case, let's get that piece in committable shape first.
> That will make sure PG20 gets some improvement regardless of what
> happens with your other proposal, and allows us to isolate the effect
> of the proposed architectural change.
Attached is the patch for using sort_template.h in TIDBitmap based on
master. No other parallel BIS changes.
Here is a small test to show the gains. The relative savings increase
the more workers are used because the sorting is done serially.
create table test(col0 bigint, col1 bigint, filler char(5000));
insert into test select a, (random()*10000000)::bigint, 'test' from
generate_series(1, 10000000) a;
create index on test(col1);
vacuum analyze test;
set cpu_operator_cost = 2;
set max_parallel_workers_per_gather = 8;
explain analyze select count(col0) from test where col1 < 1000000;
Results (best of 5, settings for stable results enabled):
master: ~886 ms
patched: ~811 ms
The query plans are attached. The startup time of the parallel BHS
reduces significantly, which is were the serial sort takes place.
--
David Geier
Plan master:
------------
Finalize Aggregate (actual time=875.382..886.935 rows=1.00 loops=1)
Buffers: shared hit=144 read=1001172
-> Gather (actual time=868.104..886.929 rows=8.00 loops=1)
Workers Planned: 7
Workers Launched: 7
Buffers: shared hit=144 read=1001172
-> Partial Aggregate (actual time=865.977..865.978 rows=1.00 loops=8)
Buffers: shared hit=144 read=1001172
-> Parallel Bitmap Heap Scan on test (actual
time=342.064..861.735 rows=124846.50 loops=8)
Recheck Cond: (col1 < 1000000)
Heap Blocks: exact=127142
Buffers: shared hit=144 read=1001172
Worker 0: Heap Blocks: exact=122278
Worker 1: Heap Blocks: exact=124066
Worker 2: Heap Blocks: exact=126007
Worker 3: Heap Blocks: exact=122601
Worker 4: Heap Blocks: exact=127794
Worker 5: Heap Blocks: exact=124895
Worker 6: Heap Blocks: exact=123989
-> Bitmap Index Scan on test_col1_idx (actual
time=144.824..144.824 rows=998772.00 loops=1)
Index Cond: (col1 < 1000000)
Index Searches: 1
Buffers: shared read=2397
Plan patched:
-------------
Finalize Aggregate (actual time=800.958..811.642 rows=1.00 loops=1)
Buffers: shared hit=144 read=1001172
-> Gather (actual time=798.645..811.636 rows=8.00 loops=1)
Workers Planned: 7
Workers Launched: 7
Buffers: shared hit=144 read=1001172
-> Partial Aggregate (actual time=796.264..796.264 rows=1.00 loops=8)
Buffers: shared hit=144 read=1001172
-> Parallel Bitmap Heap Scan on test (actual
time=289.284..792.197 rows=124846.50 loops=8)
Recheck Cond: (col1 < 1000000)
Heap Blocks: exact=123881
Buffers: shared hit=144 read=1001172
Worker 0: Heap Blocks: exact=122751
Worker 1: Heap Blocks: exact=125432
Worker 2: Heap Blocks: exact=122463
Worker 3: Heap Blocks: exact=126538
Worker 4: Heap Blocks: exact=127470
Worker 5: Heap Blocks: exact=124592
Worker 6: Heap Blocks: exact=125645
-> Bitmap Index Scan on test_col1_idx (actual
time=142.290..142.290 rows=998772.00 loops=1)
Index Cond: (col1 < 1000000)
Index Searches: 1
Buffers: shared read=2397
Planning Time: 0.090 ms
Execution Time: 811.669 msFrom 7f00867f953b0207b6264863d86ccecb6a7fef6d Mon Sep 17 00:00:00 2001
From: David Geier <[email protected]>
Date: Tue, 13 Oct 2026 13:36:22 +0200
Subject: [PATCH v1] TIDBitmap uses sort_template.h for pagetable sorting
Generate specialized sort functions for the pagetable instead of
going through generic qsort()/qsort_arg() comparator calls. The
inlined comparator avoids function call overhead per comparison.
The shared-iteration index arrays need the pagetable base address
to resolve indexes to entries, so that variant uses
ST_COMPARE_ARG_TYPE to pass it through.
---
src/backend/nodes/tidbitmap.c | 68 ++++++++++++++---------------------
1 file changed, 26 insertions(+), 42 deletions(-)
diff --git a/src/backend/nodes/tidbitmap.c b/src/backend/nodes/tidbitmap.c
index f1f925cb13b..a8ccc99346e 100644
--- a/src/backend/nodes/tidbitmap.c
+++ b/src/backend/nodes/tidbitmap.c
@@ -225,9 +225,6 @@ static PagetableEntry *tbm_get_pageentry(TIDBitmap *tbm, BlockNumber pageno);
static bool tbm_page_is_lossy(const TIDBitmap *tbm, BlockNumber pageno);
static void tbm_mark_page_lossy(TIDBitmap *tbm, BlockNumber pageno);
static void tbm_lossify(TIDBitmap *tbm);
-static int tbm_comparator(const void *left, const void *right);
-static int tbm_shared_comparator(const void *left, const void *right,
- void *arg);
/* define hashtable mapping block numbers to PagetableEntry's */
#define SH_USE_NONDEFAULT_ALLOCATOR
@@ -242,6 +239,28 @@ static int tbm_shared_comparator(const void *left, const void *right,
#define SH_DECLARE
#include "lib/simplehash.h"
+/* Needed for sort template to work with pointers to PagetableEntry */
+typedef PagetableEntry *PagetableEntryPtr;
+
+#define ST_SORT qsort_pagetable
+#define ST_ELEMENT_TYPE PagetableEntryPtr
+#define ST_COMPARE(a, b) pg_cmp_u32((*(a))->blockno, (*(b))->blockno)
+#define ST_SCOPE static
+#define ST_DEFINE
+#include "lib/sort_template.h"
+
+/*
+ * The shared-iteration arrays contain indexes into the pagetable entry
+ * array rather than pointers, so their comparator needs the base address
+ * of the entry array passed through as an argument.
+ */
+#define ST_SORT qsort_pagetable_index
+#define ST_ELEMENT_TYPE int
+#define ST_COMPARE(a, b, base) pg_cmp_u32(base[*(a)].blockno, base[*(b)].blockno)
+#define ST_COMPARE_ARG_TYPE PagetableEntry
+#define ST_SCOPE static
+#define ST_DEFINE
+#include "lib/sort_template.h"
/*
* tbm_create - create an initially-empty bitmap
@@ -727,11 +746,9 @@ tbm_begin_private_iterate(TIDBitmap *tbm)
Assert(npages == tbm->npages);
Assert(nchunks == tbm->nchunks);
if (npages > 1)
- qsort(tbm->spages, npages, sizeof(PagetableEntry *),
- tbm_comparator);
+ qsort_pagetable(tbm->spages, npages);
if (nchunks > 1)
- qsort(tbm->schunks, nchunks, sizeof(PagetableEntry *),
- tbm_comparator);
+ qsort_pagetable(tbm->schunks, nchunks);
}
tbm->iterating = TBM_ITERATING_PRIVATE;
@@ -840,11 +857,9 @@ tbm_prepare_shared_iterate(TIDBitmap *tbm)
if (ptbase != NULL)
pg_atomic_init_u32(&ptbase->refcount, 0);
if (npages > 1)
- qsort_arg(ptpages->index, npages, sizeof(int),
- tbm_shared_comparator, ptbase->ptentry);
+ qsort_pagetable_index(ptpages->index, npages, ptbase->ptentry);
if (nchunks > 1)
- qsort_arg(ptchunks->index, nchunks, sizeof(int),
- tbm_shared_comparator, ptbase->ptentry);
+ qsort_pagetable_index(ptchunks->index, nchunks, ptbase->ptentry);
}
/*
@@ -1418,37 +1433,6 @@ tbm_lossify(TIDBitmap *tbm)
tbm->maxentries = Min(tbm->nentries, (INT_MAX - 1) / 2) * 2;
}
-/*
- * qsort comparator to handle PagetableEntry pointers.
- */
-static int
-tbm_comparator(const void *left, const void *right)
-{
- BlockNumber l = (*((PagetableEntry *const *) left))->blockno;
- BlockNumber r = (*((PagetableEntry *const *) right))->blockno;
-
- return pg_cmp_u32(l, r);
-}
-
-/*
- * As above, but this will get index into PagetableEntry array. Therefore,
- * it needs to get actual PagetableEntry using the index before comparing the
- * blockno.
- */
-static int
-tbm_shared_comparator(const void *left, const void *right, void *arg)
-{
- PagetableEntry *base = (PagetableEntry *) arg;
- PagetableEntry *lpage = &base[*(const int *) left];
- PagetableEntry *rpage = &base[*(const int *) right];
-
- if (lpage->blockno < rpage->blockno)
- return -1;
- else if (lpage->blockno > rpage->blockno)
- return 1;
- return 0;
-}
-
/*
* tbm_attach_shared_iterate
*
--
2.53.0
