public inbox for [email protected]help / color / mirror / Atom feed
[PATCH 6/8] Ignore correlation for new BRIN opclasses 19+ messages / 5 participants [nested] [flat]
* [PATCH 6/8] Ignore correlation for new BRIN opclasses @ 2020-09-12 13:07 Tomas Vondra <[email protected]> 0 siblings, 0 replies; 19+ messages in thread From: Tomas Vondra @ 2020-09-12 13:07 UTC (permalink / raw) The new BRIN opclasses (bloom and minmax-multi) are less sensitive to poorly correlated data, so just assume the data is perfectly correlated during costing. Author: Tomas Vondra <[email protected]> Discussion: https://postgr.es/m/[email protected] --- src/backend/access/brin/brin_bloom.c | 1 + src/backend/access/brin/brin_minmax_multi.c | 1 + src/backend/utils/adt/selfuncs.c | 19 ++++++++++++++++++- src/include/access/brin_internal.h | 3 +++ 4 files changed, 23 insertions(+), 1 deletion(-) diff --git a/src/backend/access/brin/brin_bloom.c b/src/backend/access/brin/brin_bloom.c index 000c2387ee..0137095660 100644 --- a/src/backend/access/brin/brin_bloom.c +++ b/src/backend/access/brin/brin_bloom.c @@ -385,6 +385,7 @@ brin_bloom_opcinfo(PG_FUNCTION_ARGS) result = palloc0(MAXALIGN(SizeofBrinOpcInfo(1)) + sizeof(BloomOpaque)); + result->oi_ignore_correlation = true; result->oi_nstored = 1; result->oi_regular_nulls = true; result->oi_opaque = (BloomOpaque *) diff --git a/src/backend/access/brin/brin_minmax_multi.c b/src/backend/access/brin/brin_minmax_multi.c index bd17da8cd5..6ef5c5f2bf 100644 --- a/src/backend/access/brin/brin_minmax_multi.c +++ b/src/backend/access/brin/brin_minmax_multi.c @@ -1309,6 +1309,7 @@ brin_minmax_multi_opcinfo(PG_FUNCTION_ARGS) result = palloc0(MAXALIGN(SizeofBrinOpcInfo(1)) + sizeof(MinmaxMultiOpaque)); + result->oi_ignore_correlation = true; result->oi_nstored = 1; result->oi_regular_nulls = true; result->oi_opaque = (MinmaxMultiOpaque *) diff --git a/src/backend/utils/adt/selfuncs.c b/src/backend/utils/adt/selfuncs.c index d5e61664bc..d0cc145938 100644 --- a/src/backend/utils/adt/selfuncs.c +++ b/src/backend/utils/adt/selfuncs.c @@ -98,6 +98,7 @@ #include <math.h> #include "access/brin.h" +#include "access/brin_internal.h" #include "access/brin_page.h" #include "access/gin.h" #include "access/table.h" @@ -7352,7 +7353,8 @@ brincostestimate(PlannerInfo *root, IndexPath *path, double loop_count, double minimalRanges; double estimatedRanges; double selec; - Relation indexRel; + Relation indexRel = NULL; + TupleDesc tupdesc = NULL; ListCell *l; VariableStatData vardata; @@ -7374,6 +7376,7 @@ brincostestimate(PlannerInfo *root, IndexPath *path, double loop_count, */ indexRel = index_open(index->indexoid, NoLock); brinGetStats(indexRel, &statsData); + tupdesc = RelationGetDescr(indexRel); index_close(indexRel, NoLock); /* work out the actual number of ranges in the index */ @@ -7407,6 +7410,17 @@ brincostestimate(PlannerInfo *root, IndexPath *path, double loop_count, { IndexClause *iclause = lfirst_node(IndexClause, l); AttrNumber attnum = index->indexkeys[iclause->indexcol]; + FmgrInfo *opcInfoFn; + BrinOpcInfo *opcInfo; + Form_pg_attribute attr = TupleDescAttr(tupdesc, iclause->indexcol); + bool ignore_correlation; + + opcInfoFn = index_getprocinfo(indexRel, iclause->indexcol + 1, BRIN_PROCNUM_OPCINFO); + + opcInfo = (BrinOpcInfo *) + DatumGetPointer(FunctionCall1(opcInfoFn, attr->atttypid)); + + ignore_correlation = opcInfo->oi_ignore_correlation; /* attempt to lookup stats in relation for this index column */ if (attnum != 0) @@ -7477,6 +7491,9 @@ brincostestimate(PlannerInfo *root, IndexPath *path, double loop_count, if (sslot.nnumbers > 0) varCorrelation = Abs(sslot.numbers[0]); + if (ignore_correlation) + varCorrelation = 1.0; + if (varCorrelation > *indexCorrelation) *indexCorrelation = varCorrelation; diff --git a/src/include/access/brin_internal.h b/src/include/access/brin_internal.h index fdaff42722..5fbf8cf9c7 100644 --- a/src/include/access/brin_internal.h +++ b/src/include/access/brin_internal.h @@ -30,6 +30,9 @@ typedef struct BrinOpcInfo /* Regular processing of NULLs in BrinValues? */ bool oi_regular_nulls; + /* Ignore correlation during cost estimation */ + bool oi_ignore_correlation; + /* Opaque pointer for the opclass' private use */ void *oi_opaque; -- 2.26.2 --------------FA974B75A0C3E9CA18CE7207 Content-Type: text/x-patch; charset=UTF-8; name="0007-patched-2-20210122.patch" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="0007-patched-2-20210122.patch" ^ permalink raw reply [nested|flat] 19+ messages in thread
* Re: Incorrect result of bitmap heap scan. @ 2024-12-02 15:08 Matthias van de Meent <[email protected]> 0 siblings, 2 replies; 19+ messages in thread From: Matthias van de Meent @ 2024-12-02 15:08 UTC (permalink / raw) To: Konstantin Knizhnik <[email protected]>; +Cc: pgsql-hackers On Mon, 2 Dec 2024 at 15:25, Konstantin Knizhnik <[email protected]> wrote: > > Hi hackers, > > Attached script reproduces the problem with incorrect results of `select count(*)` (it returns larger number of records than really available in the table). > It is not always reproduced, so you may need to repeat it multiple times - at my system it failed 3 times from 10. > > The problem takes place with pg16/17/18 (other versions I have not checked). I suspect all back branches are affected. As I partially also mentioned offline: The running theory is that bitmap executor nodes incorrectly assume that the rows contained in the bitmap all are still present in the index, and thus assume they're allowed to only check the visibility map to see if the reference contained in the bitmap is visible. However, this seems incorrect: Note that index AMs must hold at least pins on the index pages that contain their results when those results are returned by amgettuple() [0], and that amgetbitmap() doesn't do that for all TIDs in the bitmap; thus allowing vacuum to remove TIDs from the index (and later, heap) that are still present in the bitmap used in the scan. Concurrency timeline: Session 1. amgetbitmap() gets snapshot of index contents, containing references to dead tuples on heap P1. Session 2. VACUUM runs on the heap, removes TIDs for P1 from the index, deletes those TIDs from the heap pages, and finally sets heap pages' VM bits to ALL_VISIBLE, including the now cleaned page P1 Session 1. Executes the bitmap heap scan that uses the bitmap without checking tuples on P1 due to ALL_VISIBLE and a lack of output columns. I think this might be an oversight when the feature was originally committed in 7c70996e (PG11): we don't know when the VM bit was set, and the bitmap we're scanning may thus be out-of-date (and should've had TIDs removed it it had been an index), so I propose disabling this optimization for now, as attached. Patch v1 is against a recent HEAD, PG17 applies to the 17 branch, and PG16- should work on all (or at least, most) active backbranches older than PG17's. Kind regards, Matthias van de Meent Neon (https://neon.tech) PS. I don't think the optimization itself is completely impossible, and we can probably re-enable an optimization like that if (or when) we find a way to reliably keep track of when to stop using the optimization. I don't think that's an easy fix, though, and definitely not for backbranches. The solution I could think to keep most of this optimization requires the heap bitmap scan to notice that a concurrent process started removing TIDs from the heap after amgetbitmap was called; i.e.. a "vacuum generation counter" incremented every time heap starts the cleanup run. This is quite non-trivial, however, as we don't have much in place regarding per-relation shared structures which we could put such a value into, nor a good place to signal changes of the value to bitmap heap-scanning backends. From 07739e5af83664b67ea02d3db7a461a106d74040 Mon Sep 17 00:00:00 2001 From: Matthias van de Meent <[email protected]> Date: Mon, 2 Dec 2024 15:59:35 +0100 Subject: [PATCH v1] Disable BitmapScan's skip_fetch optimization The optimization doesn't take concurrent vacuum's removal of TIDs into account, which can remove dead TIDs and make ALL_VISIBLE pages for which we have pointers to those dead TIDs in the bitmap. The optimization itself isn't impossible, but would require more work figuring out that vacuum started removing TIDs and then stop using the optimization. However, we currently don't have such a system in place, making the optimization unsound to keep around. Reported-By: Konstantin Knizhnik <[email protected]> Backpatch-through: 13 --- src/include/access/heapam.h | 9 +++-- src/include/access/tableam.h | 3 +- src/backend/access/heap/heapam.c | 13 ------- src/backend/access/heap/heapam_handler.c | 28 --------------- src/backend/executor/nodeBitmapHeapscan.c | 42 ++--------------------- 5 files changed, 8 insertions(+), 87 deletions(-) diff --git a/src/include/access/heapam.h b/src/include/access/heapam.h index 65999dd64e..42f28109e2 100644 --- a/src/include/access/heapam.h +++ b/src/include/access/heapam.h @@ -92,11 +92,10 @@ typedef struct HeapScanDescData ParallelBlockTableScanWorkerData *rs_parallelworkerdata; /* - * These fields are only used for bitmap scans for the "skip fetch" - * optimization. Bitmap scans needing no fields from the heap may skip - * fetching an all visible block, instead using the number of tuples per - * block reported by the bitmap to determine how many NULL-filled tuples - * to return. + * These fields were kept around to guarantee ABI stability, but are + * otherwise unused. They were only used for bitmap scans for the + * "skip fetch" optimization, which turned out to be unsound when the + * second phase of vacuum ran concurrently. */ Buffer rs_vmbuffer; int rs_empty_tuples_pending; diff --git a/src/include/access/tableam.h b/src/include/access/tableam.h index da661289c1..5d54b0a18b 100644 --- a/src/include/access/tableam.h +++ b/src/include/access/tableam.h @@ -955,8 +955,7 @@ table_beginscan_bm(Relation rel, Snapshot snapshot, { uint32 flags = SO_TYPE_BITMAPSCAN | SO_ALLOW_PAGEMODE; - if (need_tuple) - flags |= SO_NEED_TUPLES; + flags |= SO_NEED_TUPLES; return rel->rd_tableam->scan_begin(rel, snapshot, nkeys, key, NULL, flags); } diff --git a/src/backend/access/heap/heapam.c b/src/backend/access/heap/heapam.c index bbe64b1e53..ca2dbb0b75 100644 --- a/src/backend/access/heap/heapam.c +++ b/src/backend/access/heap/heapam.c @@ -1188,19 +1188,6 @@ heap_rescan(TableScanDesc sscan, ScanKey key, bool set_params, if (BufferIsValid(scan->rs_cbuf)) ReleaseBuffer(scan->rs_cbuf); - if (BufferIsValid(scan->rs_vmbuffer)) - { - ReleaseBuffer(scan->rs_vmbuffer); - scan->rs_vmbuffer = InvalidBuffer; - } - - /* - * Reset rs_empty_tuples_pending, a field only used by bitmap heap scan, - * to avoid incorrectly emitting NULL-filled tuples from a previous scan - * on rescan. - */ - scan->rs_empty_tuples_pending = 0; - /* * The read stream is reset on rescan. This must be done before * initscan(), as some state referred to by read_stream_reset() is reset diff --git a/src/backend/access/heap/heapam_handler.c b/src/backend/access/heap/heapam_handler.c index 6f8b1b7929..93980be98a 100644 --- a/src/backend/access/heap/heapam_handler.c +++ b/src/backend/access/heap/heapam_handler.c @@ -2131,24 +2131,6 @@ heapam_scan_bitmap_next_block(TableScanDesc scan, hscan->rs_cindex = 0; hscan->rs_ntuples = 0; - /* - * We can skip fetching the heap page if we don't need any fields from the - * heap, the bitmap entries don't need rechecking, and all tuples on the - * page are visible to our transaction. - */ - if (!(scan->rs_flags & SO_NEED_TUPLES) && - !tbmres->recheck && - VM_ALL_VISIBLE(scan->rs_rd, tbmres->blockno, &hscan->rs_vmbuffer)) - { - /* can't be lossy in the skip_fetch case */ - Assert(tbmres->ntuples >= 0); - Assert(hscan->rs_empty_tuples_pending >= 0); - - hscan->rs_empty_tuples_pending += tbmres->ntuples; - - return true; - } - /* * Ignore any claimed entries past what we think is the end of the * relation. It may have been extended after the start of our scan (we @@ -2261,16 +2243,6 @@ heapam_scan_bitmap_next_tuple(TableScanDesc scan, Page page; ItemId lp; - if (hscan->rs_empty_tuples_pending > 0) - { - /* - * If we don't have to fetch the tuple, just return nulls. - */ - ExecStoreAllNullTuple(slot); - hscan->rs_empty_tuples_pending--; - return true; - } - /* * Out of range? If so, nothing more to look at on this page */ diff --git a/src/backend/executor/nodeBitmapHeapscan.c b/src/backend/executor/nodeBitmapHeapscan.c index 6b48a6d835..82402c0ac0 100644 --- a/src/backend/executor/nodeBitmapHeapscan.c +++ b/src/backend/executor/nodeBitmapHeapscan.c @@ -185,24 +185,11 @@ BitmapHeapNext(BitmapHeapScanState *node) */ if (!scan) { - bool need_tuples = false; - - /* - * We can potentially skip fetching heap pages if we do not need - * any columns of the table, either for checking non-indexable - * quals or for returning data. This test is a bit simplistic, as - * it checks the stronger condition that there's no qual or return - * tlist at all. But in most cases it's probably not worth working - * harder than that. - */ - need_tuples = (node->ss.ps.plan->qual != NIL || - node->ss.ps.plan->targetlist != NIL); - scan = table_beginscan_bm(node->ss.ss_currentRelation, node->ss.ps.state->es_snapshot, 0, NULL, - need_tuples); + true); node->ss.ss_currentScanDesc = scan; } @@ -459,7 +446,6 @@ BitmapPrefetch(BitmapHeapScanState *node, TableScanDesc scan) while (node->prefetch_pages < node->prefetch_target) { TBMIterateResult *tbmpre = tbm_iterate(prefetch_iterator); - bool skip_fetch; if (tbmpre == NULL) { @@ -470,20 +456,7 @@ BitmapPrefetch(BitmapHeapScanState *node, TableScanDesc scan) } node->prefetch_pages++; - /* - * If we expect not to have to actually read this heap page, - * skip this prefetch call, but continue to run the prefetch - * logic normally. (Would it be better not to increment - * prefetch_pages?) - */ - skip_fetch = (!(scan->rs_flags & SO_NEED_TUPLES) && - !tbmpre->recheck && - VM_ALL_VISIBLE(node->ss.ss_currentRelation, - tbmpre->blockno, - &node->pvmbuffer)); - - if (!skip_fetch) - PrefetchBuffer(scan->rs_rd, MAIN_FORKNUM, tbmpre->blockno); + PrefetchBuffer(scan->rs_rd, MAIN_FORKNUM, tbmpre->blockno); } } @@ -500,7 +473,6 @@ BitmapPrefetch(BitmapHeapScanState *node, TableScanDesc scan) { TBMIterateResult *tbmpre; bool do_prefetch = false; - bool skip_fetch; /* * Recheck under the mutex. If some other process has already @@ -526,15 +498,7 @@ BitmapPrefetch(BitmapHeapScanState *node, TableScanDesc scan) break; } - /* As above, skip prefetch if we expect not to need page */ - skip_fetch = (!(scan->rs_flags & SO_NEED_TUPLES) && - !tbmpre->recheck && - VM_ALL_VISIBLE(node->ss.ss_currentRelation, - tbmpre->blockno, - &node->pvmbuffer)); - - if (!skip_fetch) - PrefetchBuffer(scan->rs_rd, MAIN_FORKNUM, tbmpre->blockno); + PrefetchBuffer(scan->rs_rd, MAIN_FORKNUM, tbmpre->blockno); } } } -- 2.45.2 From eed8c4b613b5c44113e55bc6917ef3564d4632f8 Mon Sep 17 00:00:00 2001 From: Matthias van de Meent <[email protected]> Date: Mon, 2 Dec 2024 16:05:09 +0100 Subject: [PATCH v1] Disable BitmapScan's skip_fetch optimization The optimization doesn't take concurrent vacuum's removal of TIDs into account, which can remove dead TIDs and make ALL_VISIBLE pages for which we still have pointers to those dead TIDs in the bitmap. The optimization itself isn't impossible, but would require more work figuring out that vacuum started removing TIDs and then stop using the optimization. However, we currently don't have such a system in place, making the optimization unsound to keep around. Reported-By: Konstantin Knizhnik <[email protected]> Backpatch-through: 13 --- src/backend/executor/nodeBitmapHeapscan.c | 64 ++--------------------- 1 file changed, 4 insertions(+), 60 deletions(-) diff --git a/src/backend/executor/nodeBitmapHeapscan.c b/src/backend/executor/nodeBitmapHeapscan.c index 1cf0bbddd4..214c129472 100644 --- a/src/backend/executor/nodeBitmapHeapscan.c +++ b/src/backend/executor/nodeBitmapHeapscan.c @@ -186,8 +186,6 @@ BitmapHeapNext(BitmapHeapScanState *node) for (;;) { - bool skip_fetch; - CHECK_FOR_INTERRUPTS(); /* @@ -212,32 +210,7 @@ BitmapHeapNext(BitmapHeapScanState *node) else node->lossy_pages++; - /* - * We can skip fetching the heap page if we don't need any fields - * from the heap, and the bitmap entries don't need rechecking, - * and all tuples on the page are visible to our transaction. - * - * XXX: It's a layering violation that we do these checks above - * tableam, they should probably moved below it at some point. - */ - skip_fetch = (node->can_skip_fetch && - !tbmres->recheck && - VM_ALL_VISIBLE(node->ss.ss_currentRelation, - tbmres->blockno, - &node->vmbuffer)); - - if (skip_fetch) - { - /* can't be lossy in the skip_fetch case */ - Assert(tbmres->ntuples >= 0); - - /* - * The number of tuples on this page is put into - * node->return_empty_tuples. - */ - node->return_empty_tuples = tbmres->ntuples; - } - else if (!table_scan_bitmap_next_block(scan, tbmres)) + if (!table_scan_bitmap_next_block(scan, tbmres)) { /* AM doesn't think this block is valid, skip */ continue; @@ -475,7 +448,6 @@ BitmapPrefetch(BitmapHeapScanState *node, TableScanDesc scan) while (node->prefetch_pages < node->prefetch_target) { TBMIterateResult *tbmpre = tbm_iterate(prefetch_iterator); - bool skip_fetch; if (tbmpre == NULL) { @@ -486,25 +458,7 @@ BitmapPrefetch(BitmapHeapScanState *node, TableScanDesc scan) } node->prefetch_pages++; - /* - * If we expect not to have to actually read this heap page, - * skip this prefetch call, but continue to run the prefetch - * logic normally. (Would it be better not to increment - * prefetch_pages?) - * - * This depends on the assumption that the index AM will - * report the same recheck flag for this future heap page as - * it did for the current heap page; which is not a certainty - * but is true in many cases. - */ - skip_fetch = (node->can_skip_fetch && - (node->tbmres ? !node->tbmres->recheck : false) && - VM_ALL_VISIBLE(node->ss.ss_currentRelation, - tbmpre->blockno, - &node->pvmbuffer)); - - if (!skip_fetch) - PrefetchBuffer(scan->rs_rd, MAIN_FORKNUM, tbmpre->blockno); + PrefetchBuffer(scan->rs_rd, MAIN_FORKNUM, tbmpre->blockno); } } @@ -521,7 +475,6 @@ BitmapPrefetch(BitmapHeapScanState *node, TableScanDesc scan) { TBMIterateResult *tbmpre; bool do_prefetch = false; - bool skip_fetch; /* * Recheck under the mutex. If some other process has already @@ -547,15 +500,7 @@ BitmapPrefetch(BitmapHeapScanState *node, TableScanDesc scan) break; } - /* As above, skip prefetch if we expect not to need page */ - skip_fetch = (node->can_skip_fetch && - (node->tbmres ? !node->tbmres->recheck : false) && - VM_ALL_VISIBLE(node->ss.ss_currentRelation, - tbmpre->blockno, - &node->pvmbuffer)); - - if (!skip_fetch) - PrefetchBuffer(scan->rs_rd, MAIN_FORKNUM, tbmpre->blockno); + PrefetchBuffer(scan->rs_rd, MAIN_FORKNUM, tbmpre->blockno); } } } @@ -749,8 +694,7 @@ ExecInitBitmapHeapScan(BitmapHeapScan *node, EState *estate, int eflags) * stronger condition that there's no qual or return tlist at all. But in * most cases it's probably not worth working harder than that. */ - scanstate->can_skip_fetch = (node->scan.plan.qual == NIL && - node->scan.plan.targetlist == NIL); + scanstate->can_skip_fetch = false; /* * Miscellaneous initialization -- 2.45.2 Attachments: [text/plain] PG17-Disable-BitmapScan-s-skip_fetch-optimization.patch.txt (7.5K, ../../CAEze2Wg1Q4gWzm9RZ0yXydm23Mj3iScu8LA__Zz3JJEgpnoGPQ@mail.gmail.com/2-PG17-Disable-BitmapScan-s-skip_fetch-optimization.patch.txt) download | inline diff: From 07739e5af83664b67ea02d3db7a461a106d74040 Mon Sep 17 00:00:00 2001 From: Matthias van de Meent <[email protected]> Date: Mon, 2 Dec 2024 15:59:35 +0100 Subject: [PATCH v1] Disable BitmapScan's skip_fetch optimization The optimization doesn't take concurrent vacuum's removal of TIDs into account, which can remove dead TIDs and make ALL_VISIBLE pages for which we have pointers to those dead TIDs in the bitmap. The optimization itself isn't impossible, but would require more work figuring out that vacuum started removing TIDs and then stop using the optimization. However, we currently don't have such a system in place, making the optimization unsound to keep around. Reported-By: Konstantin Knizhnik <[email protected]> Backpatch-through: 13 --- src/include/access/heapam.h | 9 +++-- src/include/access/tableam.h | 3 +- src/backend/access/heap/heapam.c | 13 ------- src/backend/access/heap/heapam_handler.c | 28 --------------- src/backend/executor/nodeBitmapHeapscan.c | 42 ++--------------------- 5 files changed, 8 insertions(+), 87 deletions(-) diff --git a/src/include/access/heapam.h b/src/include/access/heapam.h index 65999dd64e..42f28109e2 100644 --- a/src/include/access/heapam.h +++ b/src/include/access/heapam.h @@ -92,11 +92,10 @@ typedef struct HeapScanDescData ParallelBlockTableScanWorkerData *rs_parallelworkerdata; /* - * These fields are only used for bitmap scans for the "skip fetch" - * optimization. Bitmap scans needing no fields from the heap may skip - * fetching an all visible block, instead using the number of tuples per - * block reported by the bitmap to determine how many NULL-filled tuples - * to return. + * These fields were kept around to guarantee ABI stability, but are + * otherwise unused. They were only used for bitmap scans for the + * "skip fetch" optimization, which turned out to be unsound when the + * second phase of vacuum ran concurrently. */ Buffer rs_vmbuffer; int rs_empty_tuples_pending; diff --git a/src/include/access/tableam.h b/src/include/access/tableam.h index da661289c1..5d54b0a18b 100644 --- a/src/include/access/tableam.h +++ b/src/include/access/tableam.h @@ -955,8 +955,7 @@ table_beginscan_bm(Relation rel, Snapshot snapshot, { uint32 flags = SO_TYPE_BITMAPSCAN | SO_ALLOW_PAGEMODE; - if (need_tuple) - flags |= SO_NEED_TUPLES; + flags |= SO_NEED_TUPLES; return rel->rd_tableam->scan_begin(rel, snapshot, nkeys, key, NULL, flags); } diff --git a/src/backend/access/heap/heapam.c b/src/backend/access/heap/heapam.c index bbe64b1e53..ca2dbb0b75 100644 --- a/src/backend/access/heap/heapam.c +++ b/src/backend/access/heap/heapam.c @@ -1188,19 +1188,6 @@ heap_rescan(TableScanDesc sscan, ScanKey key, bool set_params, if (BufferIsValid(scan->rs_cbuf)) ReleaseBuffer(scan->rs_cbuf); - if (BufferIsValid(scan->rs_vmbuffer)) - { - ReleaseBuffer(scan->rs_vmbuffer); - scan->rs_vmbuffer = InvalidBuffer; - } - - /* - * Reset rs_empty_tuples_pending, a field only used by bitmap heap scan, - * to avoid incorrectly emitting NULL-filled tuples from a previous scan - * on rescan. - */ - scan->rs_empty_tuples_pending = 0; - /* * The read stream is reset on rescan. This must be done before * initscan(), as some state referred to by read_stream_reset() is reset diff --git a/src/backend/access/heap/heapam_handler.c b/src/backend/access/heap/heapam_handler.c index 6f8b1b7929..93980be98a 100644 --- a/src/backend/access/heap/heapam_handler.c +++ b/src/backend/access/heap/heapam_handler.c @@ -2131,24 +2131,6 @@ heapam_scan_bitmap_next_block(TableScanDesc scan, hscan->rs_cindex = 0; hscan->rs_ntuples = 0; - /* - * We can skip fetching the heap page if we don't need any fields from the - * heap, the bitmap entries don't need rechecking, and all tuples on the - * page are visible to our transaction. - */ - if (!(scan->rs_flags & SO_NEED_TUPLES) && - !tbmres->recheck && - VM_ALL_VISIBLE(scan->rs_rd, tbmres->blockno, &hscan->rs_vmbuffer)) - { - /* can't be lossy in the skip_fetch case */ - Assert(tbmres->ntuples >= 0); - Assert(hscan->rs_empty_tuples_pending >= 0); - - hscan->rs_empty_tuples_pending += tbmres->ntuples; - - return true; - } - /* * Ignore any claimed entries past what we think is the end of the * relation. It may have been extended after the start of our scan (we @@ -2261,16 +2243,6 @@ heapam_scan_bitmap_next_tuple(TableScanDesc scan, Page page; ItemId lp; - if (hscan->rs_empty_tuples_pending > 0) - { - /* - * If we don't have to fetch the tuple, just return nulls. - */ - ExecStoreAllNullTuple(slot); - hscan->rs_empty_tuples_pending--; - return true; - } - /* * Out of range? If so, nothing more to look at on this page */ diff --git a/src/backend/executor/nodeBitmapHeapscan.c b/src/backend/executor/nodeBitmapHeapscan.c index 6b48a6d835..82402c0ac0 100644 --- a/src/backend/executor/nodeBitmapHeapscan.c +++ b/src/backend/executor/nodeBitmapHeapscan.c @@ -185,24 +185,11 @@ BitmapHeapNext(BitmapHeapScanState *node) */ if (!scan) { - bool need_tuples = false; - - /* - * We can potentially skip fetching heap pages if we do not need - * any columns of the table, either for checking non-indexable - * quals or for returning data. This test is a bit simplistic, as - * it checks the stronger condition that there's no qual or return - * tlist at all. But in most cases it's probably not worth working - * harder than that. - */ - need_tuples = (node->ss.ps.plan->qual != NIL || - node->ss.ps.plan->targetlist != NIL); - scan = table_beginscan_bm(node->ss.ss_currentRelation, node->ss.ps.state->es_snapshot, 0, NULL, - need_tuples); + true); node->ss.ss_currentScanDesc = scan; } @@ -459,7 +446,6 @@ BitmapPrefetch(BitmapHeapScanState *node, TableScanDesc scan) while (node->prefetch_pages < node->prefetch_target) { TBMIterateResult *tbmpre = tbm_iterate(prefetch_iterator); - bool skip_fetch; if (tbmpre == NULL) { @@ -470,20 +456,7 @@ BitmapPrefetch(BitmapHeapScanState *node, TableScanDesc scan) } node->prefetch_pages++; - /* - * If we expect not to have to actually read this heap page, - * skip this prefetch call, but continue to run the prefetch - * logic normally. (Would it be better not to increment - * prefetch_pages?) - */ - skip_fetch = (!(scan->rs_flags & SO_NEED_TUPLES) && - !tbmpre->recheck && - VM_ALL_VISIBLE(node->ss.ss_currentRelation, - tbmpre->blockno, - &node->pvmbuffer)); - - if (!skip_fetch) - PrefetchBuffer(scan->rs_rd, MAIN_FORKNUM, tbmpre->blockno); + PrefetchBuffer(scan->rs_rd, MAIN_FORKNUM, tbmpre->blockno); } } @@ -500,7 +473,6 @@ BitmapPrefetch(BitmapHeapScanState *node, TableScanDesc scan) { TBMIterateResult *tbmpre; bool do_prefetch = false; - bool skip_fetch; /* * Recheck under the mutex. If some other process has already @@ -526,15 +498,7 @@ BitmapPrefetch(BitmapHeapScanState *node, TableScanDesc scan) break; } - /* As above, skip prefetch if we expect not to need page */ - skip_fetch = (!(scan->rs_flags & SO_NEED_TUPLES) && - !tbmpre->recheck && - VM_ALL_VISIBLE(node->ss.ss_currentRelation, - tbmpre->blockno, - &node->pvmbuffer)); - - if (!skip_fetch) - PrefetchBuffer(scan->rs_rd, MAIN_FORKNUM, tbmpre->blockno); + PrefetchBuffer(scan->rs_rd, MAIN_FORKNUM, tbmpre->blockno); } } } -- 2.45.2 [application/x-patch] v1-0001-Remove-BitmapScan-s-skip_fetch-optimization.patch (8.3K, ../../CAEze2Wg1Q4gWzm9RZ0yXydm23Mj3iScu8LA__Zz3JJEgpnoGPQ@mail.gmail.com/3-v1-0001-Remove-BitmapScan-s-skip_fetch-optimization.patch) download | inline diff: From 43144d7511c93ed153b4ab5b30bf59ea3af20fbd Mon Sep 17 00:00:00 2001 From: Matthias van de Meent <[email protected]> Date: Mon, 2 Dec 2024 15:38:14 +0100 Subject: [PATCH v1] Remove BitmapScan's skip_fetch optimization The optimization doesn't take concurrent vacuum's removal of TIDs into account, which can remove dead TIDs and make ALL_VISIBLE pages for which we have pointers to those dead TIDs in the bitmap. The optimization itself isn't impossible, but would require more work figuring out that vacuum started removing TIDs and then stop using the optimization. However, we currently don't have such a system in place, making the optimization unsound to keep around. Reported-By: Konstantin Knizhnik <[email protected]> Backpatch-through: 13 --- src/include/access/heapam.h | 1 - src/include/access/tableam.h | 12 +------ src/backend/access/heap/heapam.c | 18 ---------- src/backend/access/heap/heapam_handler.c | 28 --------------- src/backend/executor/nodeBitmapHeapscan.c | 43 ++--------------------- 5 files changed, 4 insertions(+), 98 deletions(-) diff --git a/src/include/access/heapam.h b/src/include/access/heapam.h index 96cf82f97b..6dd233dc17 100644 --- a/src/include/access/heapam.h +++ b/src/include/access/heapam.h @@ -99,7 +99,6 @@ typedef struct HeapScanDescData * block reported by the bitmap to determine how many NULL-filled tuples * to return. */ - Buffer rs_vmbuffer; int rs_empty_tuples_pending; /* these fields only used in page-at-a-time mode and for bitmap scans */ diff --git a/src/include/access/tableam.h b/src/include/access/tableam.h index adb478a93c..283a19babe 100644 --- a/src/include/access/tableam.h +++ b/src/include/access/tableam.h @@ -62,13 +62,6 @@ typedef enum ScanOptions /* unregister snapshot at scan end? */ SO_TEMP_SNAPSHOT = 1 << 9, - - /* - * At the discretion of the table AM, bitmap table scans may be able to - * skip fetching a block from the table if none of the table data is - * needed. If table data may be needed, set SO_NEED_TUPLES. - */ - SO_NEED_TUPLES = 1 << 10, } ScanOptions; /* @@ -955,14 +948,11 @@ table_beginscan_strat(Relation rel, Snapshot snapshot, */ static inline TableScanDesc table_beginscan_bm(Relation rel, Snapshot snapshot, - int nkeys, struct ScanKeyData *key, bool need_tuple) + int nkeys, struct ScanKeyData *key) { TableScanDesc result; uint32 flags = SO_TYPE_BITMAPSCAN | SO_ALLOW_PAGEMODE; - if (need_tuple) - flags |= SO_NEED_TUPLES; - result = rel->rd_tableam->scan_begin(rel, snapshot, nkeys, key, NULL, flags); result->st.bitmap.rs_shared_iterator = NULL; diff --git a/src/backend/access/heap/heapam.c b/src/backend/access/heap/heapam.c index d00300c5dc..9ea9dec863 100644 --- a/src/backend/access/heap/heapam.c +++ b/src/backend/access/heap/heapam.c @@ -1053,8 +1053,6 @@ heap_beginscan(Relation relation, Snapshot snapshot, scan->rs_base.rs_flags = flags; scan->rs_base.rs_parallel = parallel_scan; scan->rs_strategy = NULL; /* set in initscan */ - scan->rs_vmbuffer = InvalidBuffer; - scan->rs_empty_tuples_pending = 0; /* * Disable page-at-a-time mode if it's not a MVCC-safe snapshot. @@ -1170,19 +1168,6 @@ heap_rescan(TableScanDesc sscan, ScanKey key, bool set_params, if (BufferIsValid(scan->rs_cbuf)) ReleaseBuffer(scan->rs_cbuf); - if (BufferIsValid(scan->rs_vmbuffer)) - { - ReleaseBuffer(scan->rs_vmbuffer); - scan->rs_vmbuffer = InvalidBuffer; - } - - /* - * Reset rs_empty_tuples_pending, a field only used by bitmap heap scan, - * to avoid incorrectly emitting NULL-filled tuples from a previous scan - * on rescan. - */ - scan->rs_empty_tuples_pending = 0; - /* * The read stream is reset on rescan. This must be done before * initscan(), as some state referred to by read_stream_reset() is reset @@ -1210,9 +1195,6 @@ heap_endscan(TableScanDesc sscan) if (BufferIsValid(scan->rs_cbuf)) ReleaseBuffer(scan->rs_cbuf); - if (BufferIsValid(scan->rs_vmbuffer)) - ReleaseBuffer(scan->rs_vmbuffer); - /* * Must free the read stream before freeing the BufferAccessStrategy. */ diff --git a/src/backend/access/heap/heapam_handler.c b/src/backend/access/heap/heapam_handler.c index a8d95e0f1c..b432eb8140 100644 --- a/src/backend/access/heap/heapam_handler.c +++ b/src/backend/access/heap/heapam_handler.c @@ -2158,24 +2158,6 @@ heapam_scan_bitmap_next_block(TableScanDesc scan, *blockno = tbmres->blockno; *recheck = tbmres->recheck; - /* - * We can skip fetching the heap page if we don't need any fields from the - * heap, the bitmap entries don't need rechecking, and all tuples on the - * page are visible to our transaction. - */ - if (!(scan->rs_flags & SO_NEED_TUPLES) && - !tbmres->recheck && - VM_ALL_VISIBLE(scan->rs_rd, tbmres->blockno, &hscan->rs_vmbuffer)) - { - /* can't be lossy in the skip_fetch case */ - Assert(tbmres->ntuples >= 0); - Assert(hscan->rs_empty_tuples_pending >= 0); - - hscan->rs_empty_tuples_pending += tbmres->ntuples; - - return true; - } - block = tbmres->blockno; /* @@ -2290,16 +2272,6 @@ heapam_scan_bitmap_next_tuple(TableScanDesc scan, Page page; ItemId lp; - if (hscan->rs_empty_tuples_pending > 0) - { - /* - * If we don't have to fetch the tuple, just return nulls. - */ - ExecStoreAllNullTuple(slot); - hscan->rs_empty_tuples_pending--; - return true; - } - /* * Out of range? If so, nothing more to look at on this page */ diff --git a/src/backend/executor/nodeBitmapHeapscan.c b/src/backend/executor/nodeBitmapHeapscan.c index 689bde16dd..9bf01bb0c3 100644 --- a/src/backend/executor/nodeBitmapHeapscan.c +++ b/src/backend/executor/nodeBitmapHeapscan.c @@ -176,24 +176,10 @@ BitmapHeapNext(BitmapHeapScanState *node) */ if (!scan) { - bool need_tuples = false; - - /* - * We can potentially skip fetching heap pages if we do not need - * any columns of the table, either for checking non-indexable - * quals or for returning data. This test is a bit simplistic, as - * it checks the stronger condition that there's no qual or return - * tlist at all. But in most cases it's probably not worth working - * harder than that. - */ - need_tuples = (node->ss.ps.plan->qual != NIL || - node->ss.ps.plan->targetlist != NIL); - scan = table_beginscan_bm(node->ss.ss_currentRelation, node->ss.ps.state->es_snapshot, 0, - NULL, - need_tuples); + NULL); node->ss.ss_currentScanDesc = scan; } @@ -453,7 +439,6 @@ BitmapPrefetch(BitmapHeapScanState *node, TableScanDesc scan) while (node->prefetch_pages < node->prefetch_target) { TBMIterateResult *tbmpre = tbm_iterate(prefetch_iterator); - bool skip_fetch; if (tbmpre == NULL) { @@ -465,20 +450,7 @@ BitmapPrefetch(BitmapHeapScanState *node, TableScanDesc scan) node->prefetch_pages++; node->prefetch_blockno = tbmpre->blockno; - /* - * If we expect not to have to actually read this heap page, - * skip this prefetch call, but continue to run the prefetch - * logic normally. (Would it be better not to increment - * prefetch_pages?) - */ - skip_fetch = (!(scan->rs_flags & SO_NEED_TUPLES) && - !tbmpre->recheck && - VM_ALL_VISIBLE(node->ss.ss_currentRelation, - tbmpre->blockno, - &node->pvmbuffer)); - - if (!skip_fetch) - PrefetchBuffer(scan->rs_rd, MAIN_FORKNUM, tbmpre->blockno); + PrefetchBuffer(scan->rs_rd, MAIN_FORKNUM, tbmpre->blockno); } } @@ -495,7 +467,6 @@ BitmapPrefetch(BitmapHeapScanState *node, TableScanDesc scan) { TBMIterateResult *tbmpre; bool do_prefetch = false; - bool skip_fetch; /* * Recheck under the mutex. If some other process has already @@ -523,15 +494,7 @@ BitmapPrefetch(BitmapHeapScanState *node, TableScanDesc scan) node->prefetch_blockno = tbmpre->blockno; - /* As above, skip prefetch if we expect not to need page */ - skip_fetch = (!(scan->rs_flags & SO_NEED_TUPLES) && - !tbmpre->recheck && - VM_ALL_VISIBLE(node->ss.ss_currentRelation, - tbmpre->blockno, - &node->pvmbuffer)); - - if (!skip_fetch) - PrefetchBuffer(scan->rs_rd, MAIN_FORKNUM, tbmpre->blockno); + PrefetchBuffer(scan->rs_rd, MAIN_FORKNUM, tbmpre->blockno); } } } -- 2.45.2 [text/plain] PG16-_Disable-BitmapScan-s-skip_fetch-optimization.patch.txt (4.8K, ../../CAEze2Wg1Q4gWzm9RZ0yXydm23Mj3iScu8LA__Zz3JJEgpnoGPQ@mail.gmail.com/4-PG16-_Disable-BitmapScan-s-skip_fetch-optimization.patch.txt) download | inline diff: From eed8c4b613b5c44113e55bc6917ef3564d4632f8 Mon Sep 17 00:00:00 2001 From: Matthias van de Meent <[email protected]> Date: Mon, 2 Dec 2024 16:05:09 +0100 Subject: [PATCH v1] Disable BitmapScan's skip_fetch optimization The optimization doesn't take concurrent vacuum's removal of TIDs into account, which can remove dead TIDs and make ALL_VISIBLE pages for which we still have pointers to those dead TIDs in the bitmap. The optimization itself isn't impossible, but would require more work figuring out that vacuum started removing TIDs and then stop using the optimization. However, we currently don't have such a system in place, making the optimization unsound to keep around. Reported-By: Konstantin Knizhnik <[email protected]> Backpatch-through: 13 --- src/backend/executor/nodeBitmapHeapscan.c | 64 ++--------------------- 1 file changed, 4 insertions(+), 60 deletions(-) diff --git a/src/backend/executor/nodeBitmapHeapscan.c b/src/backend/executor/nodeBitmapHeapscan.c index 1cf0bbddd4..214c129472 100644 --- a/src/backend/executor/nodeBitmapHeapscan.c +++ b/src/backend/executor/nodeBitmapHeapscan.c @@ -186,8 +186,6 @@ BitmapHeapNext(BitmapHeapScanState *node) for (;;) { - bool skip_fetch; - CHECK_FOR_INTERRUPTS(); /* @@ -212,32 +210,7 @@ BitmapHeapNext(BitmapHeapScanState *node) else node->lossy_pages++; - /* - * We can skip fetching the heap page if we don't need any fields - * from the heap, and the bitmap entries don't need rechecking, - * and all tuples on the page are visible to our transaction. - * - * XXX: It's a layering violation that we do these checks above - * tableam, they should probably moved below it at some point. - */ - skip_fetch = (node->can_skip_fetch && - !tbmres->recheck && - VM_ALL_VISIBLE(node->ss.ss_currentRelation, - tbmres->blockno, - &node->vmbuffer)); - - if (skip_fetch) - { - /* can't be lossy in the skip_fetch case */ - Assert(tbmres->ntuples >= 0); - - /* - * The number of tuples on this page is put into - * node->return_empty_tuples. - */ - node->return_empty_tuples = tbmres->ntuples; - } - else if (!table_scan_bitmap_next_block(scan, tbmres)) + if (!table_scan_bitmap_next_block(scan, tbmres)) { /* AM doesn't think this block is valid, skip */ continue; @@ -475,7 +448,6 @@ BitmapPrefetch(BitmapHeapScanState *node, TableScanDesc scan) while (node->prefetch_pages < node->prefetch_target) { TBMIterateResult *tbmpre = tbm_iterate(prefetch_iterator); - bool skip_fetch; if (tbmpre == NULL) { @@ -486,25 +458,7 @@ BitmapPrefetch(BitmapHeapScanState *node, TableScanDesc scan) } node->prefetch_pages++; - /* - * If we expect not to have to actually read this heap page, - * skip this prefetch call, but continue to run the prefetch - * logic normally. (Would it be better not to increment - * prefetch_pages?) - * - * This depends on the assumption that the index AM will - * report the same recheck flag for this future heap page as - * it did for the current heap page; which is not a certainty - * but is true in many cases. - */ - skip_fetch = (node->can_skip_fetch && - (node->tbmres ? !node->tbmres->recheck : false) && - VM_ALL_VISIBLE(node->ss.ss_currentRelation, - tbmpre->blockno, - &node->pvmbuffer)); - - if (!skip_fetch) - PrefetchBuffer(scan->rs_rd, MAIN_FORKNUM, tbmpre->blockno); + PrefetchBuffer(scan->rs_rd, MAIN_FORKNUM, tbmpre->blockno); } } @@ -521,7 +475,6 @@ BitmapPrefetch(BitmapHeapScanState *node, TableScanDesc scan) { TBMIterateResult *tbmpre; bool do_prefetch = false; - bool skip_fetch; /* * Recheck under the mutex. If some other process has already @@ -547,15 +500,7 @@ BitmapPrefetch(BitmapHeapScanState *node, TableScanDesc scan) break; } - /* As above, skip prefetch if we expect not to need page */ - skip_fetch = (node->can_skip_fetch && - (node->tbmres ? !node->tbmres->recheck : false) && - VM_ALL_VISIBLE(node->ss.ss_currentRelation, - tbmpre->blockno, - &node->pvmbuffer)); - - if (!skip_fetch) - PrefetchBuffer(scan->rs_rd, MAIN_FORKNUM, tbmpre->blockno); + PrefetchBuffer(scan->rs_rd, MAIN_FORKNUM, tbmpre->blockno); } } } @@ -749,8 +694,7 @@ ExecInitBitmapHeapScan(BitmapHeapScan *node, EState *estate, int eflags) * stronger condition that there's no qual or return tlist at all. But in * most cases it's probably not worth working harder than that. */ - scanstate->can_skip_fetch = (node->scan.plan.qual == NIL && - node->scan.plan.targetlist == NIL); + scanstate->can_skip_fetch = false; /* * Miscellaneous initialization -- 2.45.2 ^ permalink raw reply [nested|flat] 19+ messages in thread
* Re: Incorrect result of bitmap heap scan. @ 2024-12-02 16:07 Peter Geoghegan <[email protected]> parent: Matthias van de Meent <[email protected]> 1 sibling, 2 replies; 19+ messages in thread From: Peter Geoghegan @ 2024-12-02 16:07 UTC (permalink / raw) To: Matthias van de Meent <[email protected]>; +Cc: Konstantin Knizhnik <[email protected]>; pgsql-hackers; Tom Lane <[email protected]> On Mon, Dec 2, 2024 at 10:15 AM Matthias van de Meent <[email protected]> wrote: > The running theory is that bitmap executor nodes incorrectly assume > that the rows contained in the bitmap all are still present in the > index, and thus assume they're allowed to only check the visibility > map to see if the reference contained in the bitmap is visible. > However, this seems incorrect: Note that index AMs must hold at least > pins on the index pages that contain their results when those results > are returned by amgettuple() [0], and that amgetbitmap() doesn't do > that for all TIDs in the bitmap; thus allowing vacuum to remove TIDs > from the index (and later, heap) that are still present in the bitmap > used in the scan. This theory seems very believable. We hold onto a leaf page buffer pin for index-only scans as an interlock against concurrent TID recycling. If we assume for the sake of argument that the optimization from commit 7c70996e is correct, then why do we even bother with holding onto the pin during index-only scans? In theory we should either do the "buffer pin interlock against TID recycling" thing everywhere, or nowhere -- how could bitmap scans possibly be different here? > I think this might be an oversight when the feature was originally > committed in 7c70996e (PG11): we don't know when the VM bit was set, > and the bitmap we're scanning may thus be out-of-date (and should've > had TIDs removed it it had been an index), so I propose disabling this > optimization for now, as attached. I have a hard time imagining any alternative fix that is suitable for backpatch. Can we save the optimization on the master branch? Clearly it would be wildly impractical to do the "buffer pin interlock against TID recycling" thing in the context of bitmap scans. The only thing that I can think of that might work is a scheme that establishes a "safe LSN" for a given MVCC snapshot. If the VM page's LSN is later than the "safe LSN", it's not okay to trust its all-visible bits. At least not in the context of bitmap index scans that use the optimization from 7c70996e. -- Peter Geoghegan ^ permalink raw reply [nested|flat] 19+ messages in thread
* Re: Incorrect result of bitmap heap scan. @ 2024-12-02 16:31 Andres Freund <[email protected]> parent: Matthias van de Meent <[email protected]> 1 sibling, 3 replies; 19+ messages in thread From: Andres Freund @ 2024-12-02 16:31 UTC (permalink / raw) To: Matthias van de Meent <[email protected]>; Andrew Dunstan <[email protected]>; Melanie Plageman <[email protected]>; Thomas Munro <[email protected]>; +Cc: Konstantin Knizhnik <[email protected]>; pgsql-hackers; Alexander Kuzmenkov <[email protected]>; Tom Lane <[email protected]> Hi, On 2024-12-02 16:08:02 +0100, Matthias van de Meent wrote: > Concurrency timeline: > > Session 1. amgetbitmap() gets snapshot of index contents, containing > references to dead tuples on heap P1. IIUC, an unstanted important aspect here is that these dead tuples are *not* visible to S1. Otherwise the VACUUM in the next step could not remove the dead tuples. > Session 2. VACUUM runs on the heap, removes TIDs for P1 from the > index, deletes those TIDs from the heap pages, and finally sets heap > pages' VM bits to ALL_VISIBLE, including the now cleaned page P1 > Session 1. Executes the bitmap heap scan that uses the bitmap without > checking tuples on P1 due to ALL_VISIBLE and a lack of output columns. Ugh :/ Pretty depressing that we've only found this now, ~6 years after it's been released. We're lacking some tooling to find this stuff in a more automated fashion. > PS. > I don't think the optimization itself is completely impossible, and we > can probably re-enable an optimization like that if (or when) we find > a way to reliably keep track of when to stop using the optimization. I > don't think that's an easy fix, though, and definitely not for > backbranches. One way to make the optimization safe could be to move it into the indexam. If an indexam would check the VM bit while blocking removal of the index entries, it should make it safe. Of course that has the disadvantage of needing more VM lookups than before, because it would not yet have been deduplicated... Another issue with bitmap index scans is that it currently can't use killtuples. I've seen several production outages where performance would degrade horribly over time whenever estimates lead to important queries to switch to bitmap scans, because lots of dead tuples would get accessed over and over. It seems pretty much impossible to fix that with the current interaction between nodeBitmap* and indexam. I wonder if we could, at least in some cases, and likely with some heuristics / limits, address this by performing some visibility checks during the bitmap build. I'm bringing it up here because I suspect that some of the necessary changes would overlap with what's needed to repair bitmap index-only scans. > The solution I could think to keep most of this optimization requires > the heap bitmap scan to notice that a concurrent process started > removing TIDs from the heap after amgetbitmap was called; i.e.. a > "vacuum generation counter" incremented every time heap starts the > cleanup run. I'm not sure this is a good path. We can already clean up pages during index accesses and we are working on being able to set all-visible during "hot pruning"/page-level-vacuuming. That'd probably actually be safe (because we couldn't remove dead items without a real vacuum), but it's starting to get pretty complicated... > This is quite non-trivial, however, as we don't have much in place regarding > per-relation shared structures which we could put such a value into, nor a > good place to signal changes of the value to bitmap heap-scanning backends. It doesn't have to be driven of table state, it could be state in indexes. Most (all?) already have a metapage. We could also add that state to pg_class? We already update pg_class after most vacuums, so I don't think that'd be an issue. Thomas had a WIP patch to add a shared-memory table of all open relations. Which we need for quite a few features by now (e.g. more efficient buffer mapping table, avoiding the relation size lookup during planning / execution, more efficient truncation of relations, ...). > From 07739e5af83664b67ea02d3db7a461a106d74040 Mon Sep 17 00:00:00 2001 > From: Matthias van de Meent <[email protected]> > Date: Mon, 2 Dec 2024 15:59:35 +0100 > Subject: [PATCH v1] Disable BitmapScan's skip_fetch optimization > > The optimization doesn't take concurrent vacuum's removal of TIDs into > account, which can remove dead TIDs and make ALL_VISIBLE pages for which > we have pointers to those dead TIDs in the bitmap. > > The optimization itself isn't impossible, but would require more work > figuring out that vacuum started removing TIDs and then stop using the > optimization. However, we currently don't have such a system in place, > making the optimization unsound to keep around. Unfortunately I don't see a better path either. I think it'd be good if we added a test that shows the failure mechanism so that we don't re-introduce this in the future. Evidently this failure isn't immediately obvious... Greetings, Andres Freund ^ permalink raw reply [nested|flat] 19+ messages in thread
* Re: Incorrect result of bitmap heap scan. @ 2024-12-02 16:43 Tom Lane <[email protected]> parent: Peter Geoghegan <[email protected]> 1 sibling, 2 replies; 19+ messages in thread From: Tom Lane @ 2024-12-02 16:43 UTC (permalink / raw) To: Peter Geoghegan <[email protected]>; +Cc: Matthias van de Meent <[email protected]>; Konstantin Knizhnik <[email protected]>; pgsql-hackers Peter Geoghegan <[email protected]> writes: > On Mon, Dec 2, 2024 at 10:15 AM Matthias van de Meent > <[email protected]> wrote: >> The running theory is that bitmap executor nodes incorrectly assume >> that the rows contained in the bitmap all are still present in the >> index, and thus assume they're allowed to only check the visibility >> map to see if the reference contained in the bitmap is visible. >> However, this seems incorrect: Note that index AMs must hold at least >> pins on the index pages that contain their results when those results >> are returned by amgettuple() [0], and that amgetbitmap() doesn't do >> that for all TIDs in the bitmap; thus allowing vacuum to remove TIDs >> from the index (and later, heap) that are still present in the bitmap >> used in the scan. > This theory seems very believable. I'm not convinced. I think there are two assumptions underlying bitmap scan: 1. Regardless of index contents, it's not okay for vacuum to remove tuples that an open transaction could potentially see. So the heap tuple will be there if we look, unless it was already dead (in which case it could have been replaced, so we have to check visibility of whatever we find). 2. If the page's all-visible bit is set, there has been no recent change in its contents, so we don't have to look at the page. "Recent" is a bit squishily defined, but again it should surely cover outdating or removal of a tuple that an open transaction could see. If this is not working, I am suspicious that somebody made page freezing too aggressive somewhere along the line. Whether that's true or not, it seems like it'd be worth bisecting to see if we can finger a commit where the behavior changed (and the same goes for the question of why-isnt-it-an-IOS-scan). However, the reproducer seems to have quite a low failure probability for me, which makes it hard to do bisection testing with much confidence. Can we do anything to make the test more reliable? If I'm right to suspect autovacuum, maybe triggering lots of manual vacuums would improve the odds? regards, tom lane ^ permalink raw reply [nested|flat] 19+ messages in thread
* Re: Incorrect result of bitmap heap scan. @ 2024-12-02 16:46 Andres Freund <[email protected]> parent: Peter Geoghegan <[email protected]> 1 sibling, 0 replies; 19+ messages in thread From: Andres Freund @ 2024-12-02 16:46 UTC (permalink / raw) To: Peter Geoghegan <[email protected]>; +Cc: Matthias van de Meent <[email protected]>; Konstantin Knizhnik <[email protected]>; pgsql-hackers; Tom Lane <[email protected]> Hi, On 2024-12-02 11:07:38 -0500, Peter Geoghegan wrote: > Clearly it would be wildly impractical to do the "buffer pin interlock > against TID recycling" thing in the context of bitmap scans. That's certainly true if we do the VM check at the time of the bitmap heap scan. What if we did it whenever we first enter a block into the TID bitmap? There's sufficient padding space in PagetableEntry to store such state without increasing memory usage. That'd probably need some API evolution, because we'd only know after entering into the tidbitmap that we need to check the VM, we'd need to index pins during the VM checking and then update PagetableEntry with the result of the VM probe. I think, but am not certain, that it'd be sufficient to do the VM check the first time an index scan encounters a block. If a concurrent vacuum would mark the heap page all-visible after we encountered it first, we'd do "real" visibility checks, because the first VM lookup won't have it as all visible. And in the opposite situation, where we find a page all-visible in the VM, which then subsequently gets marked not-all-visible, normal snapshot semantics would make it safe to still consider the contents all-visible, because update/delete can't be visible to "us". Greetings, Andres Freund ^ permalink raw reply [nested|flat] 19+ messages in thread
* Re: Incorrect result of bitmap heap scan. @ 2024-12-02 16:52 Andres Freund <[email protected]> parent: Tom Lane <[email protected]> 1 sibling, 2 replies; 19+ messages in thread From: Andres Freund @ 2024-12-02 16:52 UTC (permalink / raw) To: Tom Lane <[email protected]>; +Cc: Peter Geoghegan <[email protected]>; Matthias van de Meent <[email protected]>; Konstantin Knizhnik <[email protected]>; pgsql-hackers Hi, On 2024-12-02 11:43:42 -0500, Tom Lane wrote: > Peter Geoghegan <[email protected]> writes: > > This theory seems very believable. > > I'm not convinced. I think there are two assumptions underlying > bitmap scan: > > 1. Regardless of index contents, it's not okay for vacuum to remove > tuples that an open transaction could potentially see. So the heap > tuple will be there if we look, unless it was already dead (in which > case it could have been replaced, so we have to check visibility of > whatever we find). I think the problematic scenario involves tuples that *nobody* can see. During the bitmap index scan we don't know that though. Thus the tid gets inserted into the bitmap. Then, before we visit the heap, a concurrent vacuum removes the tuple from the indexes and then the heap and marks the page as all-visible, as the deleted row version has been removed. Then, during the bitmap heap scan, we do a VM lookup and see the page being all-visible and thus assume there's a visible tuple pointed to by the tid. No snapshot semantics protect against this, as the tuple is *not* visible to anyone. Greetings, Andres Freund ^ permalink raw reply [nested|flat] 19+ messages in thread
* Re: Incorrect result of bitmap heap scan. @ 2024-12-02 17:02 Peter Geoghegan <[email protected]> parent: Andres Freund <[email protected]> 2 siblings, 0 replies; 19+ messages in thread From: Peter Geoghegan @ 2024-12-02 17:02 UTC (permalink / raw) To: Andres Freund <[email protected]>; +Cc: Matthias van de Meent <[email protected]>; Andrew Dunstan <[email protected]>; Melanie Plageman <[email protected]>; Thomas Munro <[email protected]>; Konstantin Knizhnik <[email protected]>; pgsql-hackers; Alexander Kuzmenkov <[email protected]>; Tom Lane <[email protected]> On Mon, Dec 2, 2024 at 11:32 AM Andres Freund <[email protected]> wrote: > On 2024-12-02 16:08:02 +0100, Matthias van de Meent wrote: > > Concurrency timeline: > > > > Session 1. amgetbitmap() gets snapshot of index contents, containing > > references to dead tuples on heap P1. > > IIUC, an unstanted important aspect here is that these dead tuples are *not* > visible to S1. Otherwise the VACUUM in the next step could not remove the dead > tuples. I would state the same thing slightly differently, FWIW: I would say that the assumption that has been violated is that a TID is a stable identifier for a given index tuple/logical row/row version (stable for the duration of the scan). This emphasis/definition seems slightly more useful, because it makes it clear why this is hard to hit: you have to be fairly unlucky for a dead-to-everyone TID to be returned by your scan (no LP_DEAD bit can be set) and set in the scan's bitmap, only to later be concurrently set LP_UNUSED in the heap -- all without VACUUM randomly being prevented from setting the same page all-visible due to some unrelated not-all-visible heap item making it unsafe. > Ugh :/ > > Pretty depressing that we've only found this now, ~6 years after it's been > released. We're lacking some tooling to find this stuff in a more automated > fashion. FWIW I have suspicions about similar problems with index-only scans that run in hot standby, and about all GiST index-only scans: https://postgr.es/m/CAH2-Wz=PqOziyRSrnN5jAtfXWXY7-BJcHz9S355LH8Dt=5qxWQ@mail.gmail.com In general there seems to be a lack of rigor in this area. I'm hoping that Tomas Vondra's work can tighten things up here in passing. > It seems pretty much impossible to fix that with the current interaction > between nodeBitmap* and indexam. I wonder if we could, at least in some cases, > and likely with some heuristics / limits, address this by performing some > visibility checks during the bitmap build. I'm bringing it up here because I > suspect that some of the necessary changes would overlap with what's needed to > repair bitmap index-only scans. This seems like it plays into some of the stuff I've discussed with Tomas, about caching visibility information in local state, as a means to avoiding holding onto pins in the index AM. For things like mark/restore support. > > This is quite non-trivial, however, as we don't have much in place regarding > > per-relation shared structures which we could put such a value into, nor a > > good place to signal changes of the value to bitmap heap-scanning backends. > > It doesn't have to be driven of table state, it could be state in > indexes. Most (all?) already have a metapage. FWIW GiST doesn't have a metapage (a historical oversight). > Unfortunately I don't see a better path either. > > I think it'd be good if we added a test that shows the failure mechanism so > that we don't re-introduce this in the future. Evidently this failure isn't > immediately obvious... Maybe a good use for injection points? -- Peter Geoghegan ^ permalink raw reply [nested|flat] 19+ messages in thread
* Re: Incorrect result of bitmap heap scan. @ 2024-12-02 17:02 Tom Lane <[email protected]> parent: Andres Freund <[email protected]> 1 sibling, 2 replies; 19+ messages in thread From: Tom Lane @ 2024-12-02 17:02 UTC (permalink / raw) To: Andres Freund <[email protected]>; +Cc: Peter Geoghegan <[email protected]>; Matthias van de Meent <[email protected]>; Konstantin Knizhnik <[email protected]>; pgsql-hackers Andres Freund <[email protected]> writes: > I think the problematic scenario involves tuples that *nobody* can see. During > the bitmap index scan we don't know that though. Thus the tid gets inserted > into the bitmap. Then, before we visit the heap, a concurrent vacuum removes > the tuple from the indexes and then the heap and marks the page as > all-visible, as the deleted row version has been removed. Yup. I am saying that that qualifies as too-aggressive setting of the all-visible bit. I'm not sure what rule we should adopt instead of the current one, but I'd much rather slow down page freezing than institute new page locking rules. regards, tom lane ^ permalink raw reply [nested|flat] 19+ messages in thread
* Re: Incorrect result of bitmap heap scan. @ 2024-12-02 17:15 Peter Geoghegan <[email protected]> parent: Andres Freund <[email protected]> 1 sibling, 0 replies; 19+ messages in thread From: Peter Geoghegan @ 2024-12-02 17:15 UTC (permalink / raw) To: Andres Freund <[email protected]>; +Cc: Tom Lane <[email protected]>; Matthias van de Meent <[email protected]>; Konstantin Knizhnik <[email protected]>; pgsql-hackers On Mon, Dec 2, 2024 at 11:52 AM Andres Freund <[email protected]> wrote: > I think the problematic scenario involves tuples that *nobody* can see. During > the bitmap index scan we don't know that though. Right, exactly. FWIW, this same issue is why it is safe for nbtree to drop its pin early during plain index scans, but not during index-only scans -- see _bt_drop_lock_and_maybe_pin, and the nbtree/README section on making concurrent TID recycling safe. Weirdly, nbtree is specifically aware that it needs to *not* drop its pin in the context of index-only scans (to make sure that VACUUM cannot do unsafe concurrent TID recycling) -- even though an equivalent index scan would be able to drop its pin like this. The underlying reason why nbtree can discriminate like this is that it "knows" that plain index scans will always visit the heap proper. If a TID points to an LP_UNUSED item, then it is considered dead to the scan (even though in general the heap page itself might be marked all-visible). If some completely unrelated, newly inserted heap tuple is found instead, then it cannot be visible to the plain index scan's MVCC snapshot (has to be an MVCC snapshot for the leaf page pin to get dropped like this). -- Peter Geoghegan ^ permalink raw reply [nested|flat] 19+ messages in thread
* Re: Incorrect result of bitmap heap scan. @ 2024-12-02 17:19 Andres Freund <[email protected]> parent: Tom Lane <[email protected]> 1 sibling, 0 replies; 19+ messages in thread From: Andres Freund @ 2024-12-02 17:19 UTC (permalink / raw) To: Tom Lane <[email protected]>; +Cc: Peter Geoghegan <[email protected]>; Matthias van de Meent <[email protected]>; Konstantin Knizhnik <[email protected]>; pgsql-hackers Hi, On 2024-12-02 12:02:39 -0500, Tom Lane wrote: > Andres Freund <[email protected]> writes: > > I think the problematic scenario involves tuples that *nobody* can see. During > > the bitmap index scan we don't know that though. Thus the tid gets inserted > > into the bitmap. Then, before we visit the heap, a concurrent vacuum removes > > the tuple from the indexes and then the heap and marks the page as > > all-visible, as the deleted row version has been removed. > > Yup. I am saying that that qualifies as too-aggressive setting of the > all-visible bit. I'm not sure what rule we should adopt instead of > the current one, but I'd much rather slow down page freezing than > institute new page locking rules. How? This basically would mean we could never set all-visible if there is *any* concurrent scan on the current relation, because any concurrent scan could have an outdated view of all-visible. Afaict this isn't an issue of "too-aggressive setting of the all-visible bit", it's an issue of setting it at all. Greetings, Andres Freund ^ permalink raw reply [nested|flat] 19+ messages in thread
* Re: Incorrect result of bitmap heap scan. @ 2024-12-02 19:42 Andres Freund <[email protected]> parent: Andres Freund <[email protected]> 2 siblings, 1 reply; 19+ messages in thread From: Andres Freund @ 2024-12-02 19:42 UTC (permalink / raw) To: Matthias van de Meent <[email protected]>; Andrew Dunstan <[email protected]>; Melanie Plageman <[email protected]>; Thomas Munro <[email protected]>; Peter Geoghegan <[email protected]>; +Cc: Konstantin Knizhnik <[email protected]>; pgsql-hackers; Alexander Kuzmenkov <[email protected]>; Tom Lane <[email protected]> Hi, On 2024-12-02 11:31:48 -0500, Andres Freund wrote: > I think it'd be good if we added a test that shows the failure mechanism so > that we don't re-introduce this in the future. Evidently this failure isn't > immediately obvious... Attached is an isolationtest that reliably shows wrong query results. Greetings, Andres Freund Attachments: [text/x-diff] v1-0001-isolationtester-showing-broken-index-only-bitmap-.patch (4.4K, ../../4vhpxjxmwedmnly6tm7i3rwwvqhzax6uf5g7dxvkixj252mbth@3l2h2kpnw4p5/2-v1-0001-isolationtester-showing-broken-index-only-bitmap-.patch) download | inline diff: From a666e6da7af9a0af31ae506de8c2c229b713f8a6 Mon Sep 17 00:00:00 2001 From: Andres Freund <[email protected]> Date: Mon, 2 Dec 2024 14:38:11 -0500 Subject: [PATCH v1] isolationtester showing broken index-only bitmap heap scan --- .../expected/index-only-bitmapscan.out | 28 ++++++ src/test/isolation/isolation_schedule | 1 + .../specs/index-only-bitmapscan.spec | 85 +++++++++++++++++++ 3 files changed, 114 insertions(+) create mode 100644 src/test/isolation/expected/index-only-bitmapscan.out create mode 100644 src/test/isolation/specs/index-only-bitmapscan.spec diff --git a/src/test/isolation/expected/index-only-bitmapscan.out b/src/test/isolation/expected/index-only-bitmapscan.out new file mode 100644 index 00000000000..132ff1bda70 --- /dev/null +++ b/src/test/isolation/expected/index-only-bitmapscan.out @@ -0,0 +1,28 @@ +Parsed test spec with 2 sessions + +starting permutation: s2_vacuum s2_mod s1_begin s1_prepare s1_fetch_1 s2_vacuum s1_fetch_all s1_commit +step s2_vacuum: VACUUM (TRUNCATE false) ios_bitmap; +step s2_mod: + DELETE FROM ios_bitmap WHERE a > 1; + +step s1_begin: BEGIN; +step s1_prepare: + DECLARE foo NO SCROLL CURSOR FOR SELECT row_number() OVER () FROM ios_bitmap WHERE a > 0 or b > 0; + +step s1_fetch_1: + FETCH FROM foo; + +row_number +---------- + 1 +(1 row) + +step s2_vacuum: VACUUM (TRUNCATE false) ios_bitmap; +step s1_fetch_all: + FETCH ALL FROM foo; + +row_number +---------- +(0 rows) + +step s1_commit: COMMIT; diff --git a/src/test/isolation/isolation_schedule b/src/test/isolation/isolation_schedule index 143109aa4da..e3c669a29c7 100644 --- a/src/test/isolation/isolation_schedule +++ b/src/test/isolation/isolation_schedule @@ -17,6 +17,7 @@ test: partial-index test: two-ids test: multiple-row-versions test: index-only-scan +test: index-only-bitmapscan test: predicate-lock-hot-tuple test: update-conflict-out test: deadlock-simple diff --git a/src/test/isolation/specs/index-only-bitmapscan.spec b/src/test/isolation/specs/index-only-bitmapscan.spec new file mode 100644 index 00000000000..9962b8dc531 --- /dev/null +++ b/src/test/isolation/specs/index-only-bitmapscan.spec @@ -0,0 +1,85 @@ +# index-only-bitmapscan test showing wrong results +# +setup +{ + -- by using a low fillfactor and a wide tuple we can get multiple blocks + -- with just few rows + CREATE TABLE ios_bitmap (a int NOT NULL, b int not null, pad char(1024) default '') + WITH (AUTOVACUUM_ENABLED = false, FILLFACTOR = 10); + + INSERT INTO ios_bitmap SELECT g.i, g.i FROM generate_series(1, 10) g(i); + + CREATE INDEX ios_bitmap_a ON ios_bitmap(a); + CREATE INDEX ios_bitmap_b ON ios_bitmap(b); +} + +teardown +{ + DROP TABLE ios_bitmap; +} + + +session s1 + +setup { + SET enable_seqscan = false; +} + +step s1_begin { BEGIN; } +step s1_commit { COMMIT; } + + +# The test query uses an or between two indexes to ensure make it more likely +# to use a bitmap index scan +# +# The row_number() hack is a way to have something returned (isolationtester +# doesn't display empty rows) while still allowing for the index-only scan +# optimization in bitmap heap scans, which requires an empty targetlist. +step s1_prepare { + DECLARE foo NO SCROLL CURSOR FOR SELECT row_number() OVER () FROM ios_bitmap WHERE a > 0 or b > 0; +} + +step s1_fetch_1 { + FETCH FROM foo; +} + +step s1_fetch_all { + FETCH ALL FROM foo; +} + + +session s2 + +# Don't delete row 1 so we have a row for the cursor to "rest" on. +step s2_mod +{ + DELETE FROM ios_bitmap WHERE a > 1; +} + +# Disable truncation, as otherwise we'll just wait for a timeout while trying +# to acquire the lock +step s2_vacuum { VACUUM (TRUNCATE false) ios_bitmap; } + +permutation + # Vacuum first, to ensure VM exists, otherwise the bitmapscan will consider + # VM to be size 0, due to caching. Can't do that in setup because + s2_vacuum + + # delete nearly all rows, to make issue visible + s2_mod + # create a cursor + s1_begin + s1_prepare + + # fetch one row from the cursor, that ensures the index scan portion is done + # before the vacuum in the next step + s1_fetch_1 + + # with the bug this vacuum will mark pages as all-visible that the scan in + # the next step then considers all-visible, despite all rows from those + # pages having been removed. + s2_vacuum + # if this returns any rows, we're busted + s1_fetch_all + + s1_commit -- 2.45.2.746.g06e570c0df.dirty ^ permalink raw reply [nested|flat] 19+ messages in thread
* Re: Incorrect result of bitmap heap scan. @ 2024-12-02 19:44 Peter Geoghegan <[email protected]> parent: Tom Lane <[email protected]> 1 sibling, 0 replies; 19+ messages in thread From: Peter Geoghegan @ 2024-12-02 19:44 UTC (permalink / raw) To: Tom Lane <[email protected]>; +Cc: Matthias van de Meent <[email protected]>; Konstantin Knizhnik <[email protected]>; pgsql-hackers On Mon, Dec 2, 2024 at 11:43 AM Tom Lane <[email protected]> wrote: > Whether that's true or not, it seems like it'd be worth bisecting > to see if we can finger a commit where the behavior changed (and > the same goes for the question of why-isnt-it-an-IOS-scan). However, > the reproducer seems to have quite a low failure probability for me, > which makes it hard to do bisection testing with much confidence. > Can we do anything to make the test more reliable? If I'm right > to suspect autovacuum, maybe triggering lots of manual vacuums > would improve the odds? I agree that autovacuum (actually, VACUUM) is important here. I find that the test becomes much more reliable if I create the test table "with (autovacuum_analyze_scale_factor=0.99, vacuum_truncate=off)". More importantly, rather than relying on autovacuum, I just run VACUUM manually from psql. I find it convenient to use "\watch 0.01" to run VACUUM repeatedly. -- Peter Geoghegan ^ permalink raw reply [nested|flat] 19+ messages in thread
* Re: Incorrect result of bitmap heap scan. @ 2024-12-02 20:56 Peter Geoghegan <[email protected]> parent: Andres Freund <[email protected]> 0 siblings, 2 replies; 19+ messages in thread From: Peter Geoghegan @ 2024-12-02 20:56 UTC (permalink / raw) To: Andres Freund <[email protected]>; +Cc: Matthias van de Meent <[email protected]>; Andrew Dunstan <[email protected]>; Melanie Plageman <[email protected]>; Thomas Munro <[email protected]>; Konstantin Knizhnik <[email protected]>; pgsql-hackers; Alexander Kuzmenkov <[email protected]>; Tom Lane <[email protected]>; Heikki Linnakangas <[email protected]> On Mon, Dec 2, 2024 at 2:43 PM Andres Freund <[email protected]> wrote: > Attached is an isolationtest that reliably shows wrong query results. Nice approach with the cursor! I took what you wrote, and repurposed it to prove my old theory about GiST index-only scans being broken due to the lack of an appropriate interlock against concurrent TID recycling. See the attached patch. -- Peter Geoghegan Attachments: [application/octet-stream] v1-0001-isolationtester-showing-broken-index-only-scans-w.patch (3.9K, ../../CAH2-Wzm6gBqc99iEKO6540ynwpjOqWESt5yjg-bHbt0hc8DPsw@mail.gmail.com/2-v1-0001-isolationtester-showing-broken-index-only-scans-w.patch) download | inline diff: From 3b189a59b2e59220ed192d8dde4080659f76fec9 Mon Sep 17 00:00:00 2001 From: Peter Geoghegan <[email protected]> Date: Mon, 2 Dec 2024 15:50:04 -0500 Subject: [PATCH v1] isolationtester showing broken index-only scans with GiST --- .../expected/index-only-gistscan.out | 28 +++++++ src/test/isolation/isolation_schedule | 1 + .../isolation/specs/index-only-gistscan.spec | 79 +++++++++++++++++++ 3 files changed, 108 insertions(+) create mode 100644 src/test/isolation/expected/index-only-gistscan.out create mode 100644 src/test/isolation/specs/index-only-gistscan.spec diff --git a/src/test/isolation/expected/index-only-gistscan.out b/src/test/isolation/expected/index-only-gistscan.out new file mode 100644 index 000000000..5c97d0f27 --- /dev/null +++ b/src/test/isolation/expected/index-only-gistscan.out @@ -0,0 +1,28 @@ +Parsed test spec with 2 sessions + +starting permutation: s2_vacuum s2_mod s1_begin s1_prepare s1_fetch_1 s2_vacuum s1_fetch_all s1_commit +step s2_vacuum: VACUUM (TRUNCATE false) ios_bitmap; +step s2_mod: + DELETE FROM ios_bitmap WHERE a > 1; + +step s1_begin: BEGIN; +step s1_prepare: + DECLARE foo NO SCROLL CURSOR FOR SELECT a FROM ios_bitmap WHERE a > 0; + +step s1_fetch_1: + FETCH FROM foo; + +a +- +1 +(1 row) + +step s2_vacuum: VACUUM (TRUNCATE false) ios_bitmap; +step s1_fetch_all: + FETCH ALL FROM foo; + +a +- +(0 rows) + +step s1_commit: COMMIT; diff --git a/src/test/isolation/isolation_schedule b/src/test/isolation/isolation_schedule index 143109aa4..e3c669a29 100644 --- a/src/test/isolation/isolation_schedule +++ b/src/test/isolation/isolation_schedule @@ -17,6 +17,7 @@ test: partial-index test: two-ids test: multiple-row-versions test: index-only-scan +test: index-only-bitmapscan test: predicate-lock-hot-tuple test: update-conflict-out test: deadlock-simple diff --git a/src/test/isolation/specs/index-only-gistscan.spec b/src/test/isolation/specs/index-only-gistscan.spec new file mode 100644 index 000000000..f42bcd80f --- /dev/null +++ b/src/test/isolation/specs/index-only-gistscan.spec @@ -0,0 +1,79 @@ +# index-only-scan test showing wrong results with GiST +# +setup +{ + -- by using a low fillfactor and a wide tuple we can get multiple blocks + -- with just few rows + create extension btree_gist; + CREATE TABLE ios_bitmap (a int NOT NULL, b int not null, pad char(1024) default '') + WITH (AUTOVACUUM_ENABLED = false, FILLFACTOR = 10); + + INSERT INTO ios_bitmap SELECT g.i, g.i FROM generate_series(1, 10) g(i); + + CREATE INDEX ios_gist_a ON ios_bitmap USING GIST (a); +} + +teardown +{ + DROP TABLE ios_bitmap; +} + + +session s1 + +setup { + SET enable_seqscan = false; + SET enable_bitmapscan = false; +} + +step s1_begin { BEGIN; } +step s1_commit { COMMIT; } + +step s1_prepare { + DECLARE foo NO SCROLL CURSOR FOR SELECT a FROM ios_bitmap WHERE a > 0; +} + +step s1_fetch_1 { + FETCH FROM foo; +} + +step s1_fetch_all { + FETCH ALL FROM foo; +} + + +session s2 + +# Don't delete row 1 so we have a row for the cursor to "rest" on. +step s2_mod +{ + DELETE FROM ios_bitmap WHERE a > 1; +} + +# Disable truncation, as otherwise we'll just wait for a timeout while trying +# to acquire the lock +step s2_vacuum { VACUUM (TRUNCATE false) ios_bitmap; } + +permutation + # Vacuum first, to ensure VM exists, otherwise the bitmapscan will consider + # VM to be size 0, due to caching. Can't do that in setup because + s2_vacuum + + # delete nearly all rows, to make issue visible + s2_mod + # create a cursor + s1_begin + s1_prepare + + # fetch one row from the cursor, that ensures the index scan portion is done + # before the vacuum in the next step + s1_fetch_1 + + # with the bug this vacuum will mark pages as all-visible that the scan in + # the next step then considers all-visible, despite all rows from those + # pages having been removed. + s2_vacuum + # if this returns any rows, we're busted + s1_fetch_all + + s1_commit -- 2.45.2 ^ permalink raw reply [nested|flat] 19+ messages in thread
* Re: Incorrect result of bitmap heap scan. @ 2024-12-02 20:59 Peter Geoghegan <[email protected]> parent: Peter Geoghegan <[email protected]> 1 sibling, 0 replies; 19+ messages in thread From: Peter Geoghegan @ 2024-12-02 20:59 UTC (permalink / raw) To: Andres Freund <[email protected]>; +Cc: Matthias van de Meent <[email protected]>; Andrew Dunstan <[email protected]>; Melanie Plageman <[email protected]>; Thomas Munro <[email protected]>; Konstantin Knizhnik <[email protected]>; pgsql-hackers; Alexander Kuzmenkov <[email protected]>; Tom Lane <[email protected]>; Heikki Linnakangas <[email protected]> On Mon, Dec 2, 2024 at 3:56 PM Peter Geoghegan <[email protected]> wrote: > I took what you wrote, and repurposed it to prove my old theory about > GiST index-only scans being broken due to the lack of an appropriate > interlock against concurrent TID recycling. See the attached patch. BTW, if you change the test case to use the default B-Tree index AM (by removing "USING GIST"), you'll see that VACUUM blocks on acquiring a cleanup lock (and so the test just times out). The problem is that GiST VACUUM just doesn't care about cleanup locks/TID recycling safety -- though clearly it should. -- Peter Geoghegan ^ permalink raw reply [nested|flat] 19+ messages in thread
* Re: Incorrect result of bitmap heap scan. @ 2024-12-03 01:22 Peter Geoghegan <[email protected]> parent: Peter Geoghegan <[email protected]> 1 sibling, 0 replies; 19+ messages in thread From: Peter Geoghegan @ 2024-12-03 01:22 UTC (permalink / raw) To: Andres Freund <[email protected]>; +Cc: Matthias van de Meent <[email protected]>; Andrew Dunstan <[email protected]>; Melanie Plageman <[email protected]>; Thomas Munro <[email protected]>; Konstantin Knizhnik <[email protected]>; pgsql-hackers; Alexander Kuzmenkov <[email protected]>; Tom Lane <[email protected]>; Heikki Linnakangas <[email protected]> On Mon, Dec 2, 2024 at 3:56 PM Peter Geoghegan <[email protected]> wrote: > I took what you wrote, and repurposed it to prove my old theory about > GiST index-only scans being broken due to the lack of an appropriate > interlock against concurrent TID recycling. See the attached patch. I've moved discussion of this GiST bug over to the old 2021 thread where I first raised concerns about the issue: https://postgr.es/m/CAH2-Wz=jjiNL9FCh8C1L-GUH15f4WFTWub2x+_NucngcDDcHKw@mail.gmail.com The GiST bug is actually causally unrelated to the bitmap index scan bug under discussion, despite the high-level similarity. Seems best to keep discussion of GiST on its own thread, for that reason. -- Peter Geoghegan ^ permalink raw reply [nested|flat] 19+ messages in thread
* Re: Incorrect result of bitmap heap scan. @ 2024-12-04 10:39 Matthias van de Meent <[email protected]> parent: Tom Lane <[email protected]> 1 sibling, 0 replies; 19+ messages in thread From: Matthias van de Meent @ 2024-12-04 10:39 UTC (permalink / raw) To: Tom Lane <[email protected]>; +Cc: Andres Freund <[email protected]>; Peter Geoghegan <[email protected]>; Konstantin Knizhnik <[email protected]>; pgsql-hackers On Mon, 2 Dec 2024 at 18:02, Tom Lane <[email protected]> wrote: > > Andres Freund <[email protected]> writes: > > I think the problematic scenario involves tuples that *nobody* can see. During > > the bitmap index scan we don't know that though. Thus the tid gets inserted > > into the bitmap. Then, before we visit the heap, a concurrent vacuum removes > > the tuple from the indexes and then the heap and marks the page as > > all-visible, as the deleted row version has been removed. > > Yup. I am saying that that qualifies as too-aggressive setting of the > all-visible bit. I'm not sure what rule we should adopt instead of > the current one, but I'd much rather slow down page freezing than > institute new page locking rules. I don't think it's new page locking rules, but rather a feature that forgot to apply page locking rules after bypassing MVCC's snapshot rules. IOS is only allowed exactly when they comply with index AM's locking rules "only return a TID that's on a page that can't concurrently be processed by vacuum" - why would this be different for the bitmap equivalent? By saying we're too aggressive with setting the all-visible bit you seem to suggest we should add rules to vacuum that to remove LP_DEAD items we don't just have to wait for tuples to be dead to all transactions, but also for all transactions that might've gotten those all_dead TIDs from indexes to have committed or rolled back, so that no references to those TIDs exist that might consider them "possibly visible". We could achieve that by adding a waitpoint to vacuum (between the index scan and the second heap scan for LP cleanup) which waits for all concurrent transactions accessing the table to commit (thus all bitmaps would be dropped), similar to REINDEX CONCURRENTLY's wait phase, but that would slow down vacuum's ability to clean up old data significantly, and change overall vacuum behaviour in a fundamental way. I'm quite opposed to such a change. Kind regards, Matthias van de Meent Neon (https://neon.tech) ^ permalink raw reply [nested|flat] 19+ messages in thread
* Re: Incorrect result of bitmap heap scan. @ 2024-12-04 11:56 Matthias van de Meent <[email protected]> parent: Andres Freund <[email protected]> 2 siblings, 1 reply; 19+ messages in thread From: Matthias van de Meent @ 2024-12-04 11:56 UTC (permalink / raw) To: Andres Freund <[email protected]>; +Cc: Andrew Dunstan <[email protected]>; Melanie Plageman <[email protected]>; Thomas Munro <[email protected]>; Konstantin Knizhnik <[email protected]>; pgsql-hackers; Alexander Kuzmenkov <[email protected]>; Tom Lane <[email protected]> On Mon, 2 Dec 2024 at 17:31, Andres Freund <[email protected]> wrote: > > Hi, > > On 2024-12-02 16:08:02 +0100, Matthias van de Meent wrote: > > Concurrency timeline: > > > > Session 1. amgetbitmap() gets snapshot of index contents, containing > > references to dead tuples on heap P1. > > IIUC, an unstanted important aspect here is that these dead tuples are *not* > visible to S1. Otherwise the VACUUM in the next step could not remove the dead > tuples. Correct, this is about TIDs that are dead to all transactions, so which might already be LP_DEAD in the heap. > > PS. > > I don't think the optimization itself is completely impossible, and we > > can probably re-enable an optimization like that if (or when) we find > > a way to reliably keep track of when to stop using the optimization. I > > don't think that's an easy fix, though, and definitely not for > > backbranches. > > One way to make the optimization safe could be to move it into the indexam. If > an indexam would check the VM bit while blocking removal of the index entries, > it should make it safe. Of course that has the disadvantage of needing more VM > lookups than before, because it would not yet have been deduplicated... I'm -0.5 on adding visibility checking to index AM's contract. The most basic contract that an index AM must implement is currently: 1. Store the index tuples provided by aminsert() 2.a With amgettuple, return at least all stored TIDs that might match the scankey (optionally marked with recheck when the AM isn't sure about the TID matching the scankeys, or when returning TIDs not provided by aminsert()), or 2.b With amgetbitmap, return a bitmap containing at least the TIDs that match the description of 2.a (i.e. allows an index to have an optimized approach to adding outputs of 2.a into a bitmap) 3. Remove all the bulkdelete-provided tids from its internal structures Note that visibility checking is absent. Any visibility or dead tuple hints (through e.g. kill_prior_tuple, or calling table_index_delete_tuples) are optimizations which are not required for basic index AM operations, and indeed they are frequently not implemented in index AMs. Adding a requirement for index AMs to do visibility checks would IMO significantly change the current API/layering contracts. > Another issue with bitmap index scans is that it currently can't use > killtuples. I've seen several production outages where performance would > degrade horribly over time whenever estimates lead to important queries to > switch to bitmap scans, because lots of dead tuples would get accessed over > and over. > > It seems pretty much impossible to fix that with the current interaction > between nodeBitmap* and indexam. I wonder if we could, at least in some cases, > and likely with some heuristics / limits, address this by performing some > visibility checks during the bitmap build. It's an interesting approach worth exploring. I'm a bit concerned about the IO patterns this would create, though, especially when this relates to BitmapAnd nodes: This node would create VM check IOs on the order of O(sum_matching_tuple_pages), instead of O(intersect_matching_tuple_pages). Additionally, it's wasted IO if we're planning to go to the heap anyway, so this VM precheck would have to be conditional on the bitmap scan not wanting any table data (e.g. row_number, count()). > I'm bringing it up here because I > suspect that some of the necessary changes would overlap with what's needed to > repair bitmap index-only scans. I'd call this "bitmap-only scans" instead, as there might be multiple indexes involved, but indeed, this also does sound like a viable approach. > > The solution I could think to keep most of this optimization requires > > the heap bitmap scan to notice that a concurrent process started > > removing TIDs from the heap after amgetbitmap was called; i.e.. a > > "vacuum generation counter" incremented every time heap starts the > > cleanup run. > > I'm not sure this is a good path. We can already clean up pages during index > accesses and we are working on being able to set all-visible during "hot > pruning"/page-level-vacuuming. That'd probably actually be safe (because we > couldn't remove dead items without a real vacuum), but it's starting to get > pretty complicated... I imagine this solution to happen in the executor/heapAM bitmapscan code, not in the index AM's amgetbitmap. It'd note down the 'vacuum generation counter' before extracting the index's bitmap, and then, after every VM lookup during the bitmap heap scan, it validates that the generation counter hasn't changed (and thus that we can use that VM bit as authorative for the visibility of the TIDs we got). I don't think that this interaction specifically is very complicated, but it would indeed add to the overall complexity of the system. Kind regards, Matthias van de Meent Neon (https://neon.tech) ^ permalink raw reply [nested|flat] 19+ messages in thread
* Re: Incorrect result of bitmap heap scan. @ 2025-01-07 17:46 Matthias van de Meent <[email protected]> parent: Matthias van de Meent <[email protected]> 0 siblings, 0 replies; 19+ messages in thread From: Matthias van de Meent @ 2025-01-07 17:46 UTC (permalink / raw) To: ; +Cc: Andres Freund <[email protected]>; Andrew Dunstan <[email protected]>; Melanie Plageman <[email protected]>; Thomas Munro <[email protected]>; Konstantin Knizhnik <[email protected]>; pgsql-hackers; Alexander Kuzmenkov <[email protected]>; Tom Lane <[email protected]> Hi, I've rebased my earlier patch to fix some minor conflicts with the work done on bitmaps in December last year. I've also included Andres' cursor-based isolation test as 0002; which now passes. This should take care of cfbot's misidentification of which patch to test, and thus get CFBot to succeed again. The patches for the back-branches didn't need updating, as those branches have not diverged enough for those patches to have gotten stale. They're still available in my initial mail over at [0]. Kind regards, Matthias van de Meent Neon (https://neon.tech) [0] https://www.postgresql.org/message-id/CAEze2Wg1Q4gWzm9RZ0yXydm23Mj3iScu8LA__Zz3JJEgpnoGPQ%40mail.gma... Attachments: [application/octet-stream] v3-0001-Remove-BitmapScan-s-skip_fetch-optimization.patch (8.2K, ../../CAEze2WibNxb__4gM3UoFug=vunqvc_DLm=E9Qsgq=tCsHX1p2Q@mail.gmail.com/2-v3-0001-Remove-BitmapScan-s-skip_fetch-optimization.patch) download | inline diff: From f5e90fc3ac68b8606cc14bba42d72d062c25eab1 Mon Sep 17 00:00:00 2001 From: Matthias van de Meent <[email protected]> Date: Mon, 2 Dec 2024 15:38:14 +0100 Subject: [PATCH v3 1/2] Remove BitmapScan's skip_fetch optimization The optimization doesn't take concurrent vacuum's removal of TIDs into account, which can remove dead TIDs and make ALL_VISIBLE pages for which we have pointers to those dead TIDs in the bitmap. The optimization itself isn't impossible, but would require more work figuring out that vacuum started removing TIDs and then stop using the optimization. However, we currently don't have such a system in place, making the optimization unsound to keep around. Reported-By: Konstantin Knizhnik <[email protected]> Backpatch-through: 13 --- src/include/access/heapam.h | 1 - src/include/access/tableam.h | 12 +------ src/backend/access/heap/heapam.c | 18 ---------- src/backend/access/heap/heapam_handler.c | 28 --------------- src/backend/executor/nodeBitmapHeapscan.c | 43 ++--------------------- 5 files changed, 4 insertions(+), 98 deletions(-) diff --git a/src/include/access/heapam.h b/src/include/access/heapam.h index 7d06dad83fc..84a1f30aecb 100644 --- a/src/include/access/heapam.h +++ b/src/include/access/heapam.h @@ -99,7 +99,6 @@ typedef struct HeapScanDescData * block reported by the bitmap to determine how many NULL-filled tuples * to return. */ - Buffer rs_vmbuffer; int rs_empty_tuples_pending; /* these fields only used in page-at-a-time mode and for bitmap scans */ diff --git a/src/include/access/tableam.h b/src/include/access/tableam.h index 09b9b394e0e..74c8befef6b 100644 --- a/src/include/access/tableam.h +++ b/src/include/access/tableam.h @@ -62,13 +62,6 @@ typedef enum ScanOptions /* unregister snapshot at scan end? */ SO_TEMP_SNAPSHOT = 1 << 9, - - /* - * At the discretion of the table AM, bitmap table scans may be able to - * skip fetching a block from the table if none of the table data is - * needed. If table data may be needed, set SO_NEED_TUPLES. - */ - SO_NEED_TUPLES = 1 << 10, } ScanOptions; /* @@ -955,13 +948,10 @@ table_beginscan_strat(Relation rel, Snapshot snapshot, */ static inline TableScanDesc table_beginscan_bm(Relation rel, Snapshot snapshot, - int nkeys, struct ScanKeyData *key, bool need_tuple) + int nkeys, struct ScanKeyData *key) { uint32 flags = SO_TYPE_BITMAPSCAN | SO_ALLOW_PAGEMODE; - if (need_tuple) - flags |= SO_NEED_TUPLES; - return rel->rd_tableam->scan_begin(rel, snapshot, nkeys, key, NULL, flags); } diff --git a/src/backend/access/heap/heapam.c b/src/backend/access/heap/heapam.c index 485525f4d64..905dd9d04a5 100644 --- a/src/backend/access/heap/heapam.c +++ b/src/backend/access/heap/heapam.c @@ -1056,8 +1056,6 @@ heap_beginscan(Relation relation, Snapshot snapshot, scan->rs_base.rs_flags = flags; scan->rs_base.rs_parallel = parallel_scan; scan->rs_strategy = NULL; /* set in initscan */ - scan->rs_vmbuffer = InvalidBuffer; - scan->rs_empty_tuples_pending = 0; /* * Disable page-at-a-time mode if it's not a MVCC-safe snapshot. @@ -1173,19 +1171,6 @@ heap_rescan(TableScanDesc sscan, ScanKey key, bool set_params, if (BufferIsValid(scan->rs_cbuf)) ReleaseBuffer(scan->rs_cbuf); - if (BufferIsValid(scan->rs_vmbuffer)) - { - ReleaseBuffer(scan->rs_vmbuffer); - scan->rs_vmbuffer = InvalidBuffer; - } - - /* - * Reset rs_empty_tuples_pending, a field only used by bitmap heap scan, - * to avoid incorrectly emitting NULL-filled tuples from a previous scan - * on rescan. - */ - scan->rs_empty_tuples_pending = 0; - /* * The read stream is reset on rescan. This must be done before * initscan(), as some state referred to by read_stream_reset() is reset @@ -1213,9 +1198,6 @@ heap_endscan(TableScanDesc sscan) if (BufferIsValid(scan->rs_cbuf)) ReleaseBuffer(scan->rs_cbuf); - if (BufferIsValid(scan->rs_vmbuffer)) - ReleaseBuffer(scan->rs_vmbuffer); - /* * Must free the read stream before freeing the BufferAccessStrategy. */ diff --git a/src/backend/access/heap/heapam_handler.c b/src/backend/access/heap/heapam_handler.c index e817f8f8f84..0ea4f029793 100644 --- a/src/backend/access/heap/heapam_handler.c +++ b/src/backend/access/heap/heapam_handler.c @@ -2155,24 +2155,6 @@ heapam_scan_bitmap_next_block(TableScanDesc scan, *blockno = tbmres->blockno; *recheck = tbmres->recheck; - /* - * We can skip fetching the heap page if we don't need any fields from the - * heap, the bitmap entries don't need rechecking, and all tuples on the - * page are visible to our transaction. - */ - if (!(scan->rs_flags & SO_NEED_TUPLES) && - !tbmres->recheck && - VM_ALL_VISIBLE(scan->rs_rd, tbmres->blockno, &hscan->rs_vmbuffer)) - { - /* can't be lossy in the skip_fetch case */ - Assert(tbmres->ntuples >= 0); - Assert(hscan->rs_empty_tuples_pending >= 0); - - hscan->rs_empty_tuples_pending += tbmres->ntuples; - - return true; - } - block = tbmres->blockno; /* @@ -2287,16 +2269,6 @@ heapam_scan_bitmap_next_tuple(TableScanDesc scan, Page page; ItemId lp; - if (hscan->rs_empty_tuples_pending > 0) - { - /* - * If we don't have to fetch the tuple, just return nulls. - */ - ExecStoreAllNullTuple(slot); - hscan->rs_empty_tuples_pending--; - return true; - } - /* * Out of range? If so, nothing more to look at on this page */ diff --git a/src/backend/executor/nodeBitmapHeapscan.c b/src/backend/executor/nodeBitmapHeapscan.c index be616683f98..e5d7fab4dbe 100644 --- a/src/backend/executor/nodeBitmapHeapscan.c +++ b/src/backend/executor/nodeBitmapHeapscan.c @@ -158,24 +158,10 @@ BitmapHeapNext(BitmapHeapScanState *node) */ if (!scan) { - bool need_tuples = false; - - /* - * We can potentially skip fetching heap pages if we do not need - * any columns of the table, either for checking non-indexable - * quals or for returning data. This test is a bit simplistic, as - * it checks the stronger condition that there's no qual or return - * tlist at all. But in most cases it's probably not worth working - * harder than that. - */ - need_tuples = (node->ss.ps.plan->qual != NIL || - node->ss.ps.plan->targetlist != NIL); - scan = table_beginscan_bm(node->ss.ss_currentRelation, node->ss.ps.state->es_snapshot, 0, - NULL, - need_tuples); + NULL); node->ss.ss_currentScanDesc = scan; } @@ -434,7 +420,6 @@ BitmapPrefetch(BitmapHeapScanState *node, TableScanDesc scan) while (node->prefetch_pages < node->prefetch_target) { TBMIterateResult *tbmpre = tbm_iterate(prefetch_iterator); - bool skip_fetch; if (tbmpre == NULL) { @@ -445,20 +430,7 @@ BitmapPrefetch(BitmapHeapScanState *node, TableScanDesc scan) node->prefetch_pages++; node->prefetch_blockno = tbmpre->blockno; - /* - * If we expect not to have to actually read this heap page, - * skip this prefetch call, but continue to run the prefetch - * logic normally. (Would it be better not to increment - * prefetch_pages?) - */ - skip_fetch = (!(scan->rs_flags & SO_NEED_TUPLES) && - !tbmpre->recheck && - VM_ALL_VISIBLE(node->ss.ss_currentRelation, - tbmpre->blockno, - &node->pvmbuffer)); - - if (!skip_fetch) - PrefetchBuffer(scan->rs_rd, MAIN_FORKNUM, tbmpre->blockno); + PrefetchBuffer(scan->rs_rd, MAIN_FORKNUM, tbmpre->blockno); } } @@ -475,7 +447,6 @@ BitmapPrefetch(BitmapHeapScanState *node, TableScanDesc scan) { TBMIterateResult *tbmpre; bool do_prefetch = false; - bool skip_fetch; /* * Recheck under the mutex. If some other process has already @@ -502,15 +473,7 @@ BitmapPrefetch(BitmapHeapScanState *node, TableScanDesc scan) node->prefetch_blockno = tbmpre->blockno; - /* As above, skip prefetch if we expect not to need page */ - skip_fetch = (!(scan->rs_flags & SO_NEED_TUPLES) && - !tbmpre->recheck && - VM_ALL_VISIBLE(node->ss.ss_currentRelation, - tbmpre->blockno, - &node->pvmbuffer)); - - if (!skip_fetch) - PrefetchBuffer(scan->rs_rd, MAIN_FORKNUM, tbmpre->blockno); + PrefetchBuffer(scan->rs_rd, MAIN_FORKNUM, tbmpre->blockno); } } } -- 2.45.2 [application/octet-stream] v3-0002-isolationtester-showing-broken-index-only-bitmap-.patch (4.4K, ../../CAEze2WibNxb__4gM3UoFug=vunqvc_DLm=E9Qsgq=tCsHX1p2Q@mail.gmail.com/3-v3-0002-isolationtester-showing-broken-index-only-bitmap-.patch) download | inline diff: From 11c89a393ebf194d5d5f6617d6bd70f753f6da74 Mon Sep 17 00:00:00 2001 From: Andres Freund <[email protected]> Date: Mon, 2 Dec 2024 14:38:11 -0500 Subject: [PATCH v3 2/2] isolationtester showing broken index-only bitmap heap scan --- .../expected/index-only-bitmapscan.out | 28 ++++++ src/test/isolation/isolation_schedule | 1 + .../specs/index-only-bitmapscan.spec | 85 +++++++++++++++++++ 3 files changed, 114 insertions(+) create mode 100644 src/test/isolation/expected/index-only-bitmapscan.out create mode 100644 src/test/isolation/specs/index-only-bitmapscan.spec diff --git a/src/test/isolation/expected/index-only-bitmapscan.out b/src/test/isolation/expected/index-only-bitmapscan.out new file mode 100644 index 00000000000..132ff1bda70 --- /dev/null +++ b/src/test/isolation/expected/index-only-bitmapscan.out @@ -0,0 +1,28 @@ +Parsed test spec with 2 sessions + +starting permutation: s2_vacuum s2_mod s1_begin s1_prepare s1_fetch_1 s2_vacuum s1_fetch_all s1_commit +step s2_vacuum: VACUUM (TRUNCATE false) ios_bitmap; +step s2_mod: + DELETE FROM ios_bitmap WHERE a > 1; + +step s1_begin: BEGIN; +step s1_prepare: + DECLARE foo NO SCROLL CURSOR FOR SELECT row_number() OVER () FROM ios_bitmap WHERE a > 0 or b > 0; + +step s1_fetch_1: + FETCH FROM foo; + +row_number +---------- + 1 +(1 row) + +step s2_vacuum: VACUUM (TRUNCATE false) ios_bitmap; +step s1_fetch_all: + FETCH ALL FROM foo; + +row_number +---------- +(0 rows) + +step s1_commit: COMMIT; diff --git a/src/test/isolation/isolation_schedule b/src/test/isolation/isolation_schedule index 143109aa4da..e3c669a29c7 100644 --- a/src/test/isolation/isolation_schedule +++ b/src/test/isolation/isolation_schedule @@ -17,6 +17,7 @@ test: partial-index test: two-ids test: multiple-row-versions test: index-only-scan +test: index-only-bitmapscan test: predicate-lock-hot-tuple test: update-conflict-out test: deadlock-simple diff --git a/src/test/isolation/specs/index-only-bitmapscan.spec b/src/test/isolation/specs/index-only-bitmapscan.spec new file mode 100644 index 00000000000..9962b8dc531 --- /dev/null +++ b/src/test/isolation/specs/index-only-bitmapscan.spec @@ -0,0 +1,85 @@ +# index-only-bitmapscan test showing wrong results +# +setup +{ + -- by using a low fillfactor and a wide tuple we can get multiple blocks + -- with just few rows + CREATE TABLE ios_bitmap (a int NOT NULL, b int not null, pad char(1024) default '') + WITH (AUTOVACUUM_ENABLED = false, FILLFACTOR = 10); + + INSERT INTO ios_bitmap SELECT g.i, g.i FROM generate_series(1, 10) g(i); + + CREATE INDEX ios_bitmap_a ON ios_bitmap(a); + CREATE INDEX ios_bitmap_b ON ios_bitmap(b); +} + +teardown +{ + DROP TABLE ios_bitmap; +} + + +session s1 + +setup { + SET enable_seqscan = false; +} + +step s1_begin { BEGIN; } +step s1_commit { COMMIT; } + + +# The test query uses an or between two indexes to ensure make it more likely +# to use a bitmap index scan +# +# The row_number() hack is a way to have something returned (isolationtester +# doesn't display empty rows) while still allowing for the index-only scan +# optimization in bitmap heap scans, which requires an empty targetlist. +step s1_prepare { + DECLARE foo NO SCROLL CURSOR FOR SELECT row_number() OVER () FROM ios_bitmap WHERE a > 0 or b > 0; +} + +step s1_fetch_1 { + FETCH FROM foo; +} + +step s1_fetch_all { + FETCH ALL FROM foo; +} + + +session s2 + +# Don't delete row 1 so we have a row for the cursor to "rest" on. +step s2_mod +{ + DELETE FROM ios_bitmap WHERE a > 1; +} + +# Disable truncation, as otherwise we'll just wait for a timeout while trying +# to acquire the lock +step s2_vacuum { VACUUM (TRUNCATE false) ios_bitmap; } + +permutation + # Vacuum first, to ensure VM exists, otherwise the bitmapscan will consider + # VM to be size 0, due to caching. Can't do that in setup because + s2_vacuum + + # delete nearly all rows, to make issue visible + s2_mod + # create a cursor + s1_begin + s1_prepare + + # fetch one row from the cursor, that ensures the index scan portion is done + # before the vacuum in the next step + s1_fetch_1 + + # with the bug this vacuum will mark pages as all-visible that the scan in + # the next step then considers all-visible, despite all rows from those + # pages having been removed. + s2_vacuum + # if this returns any rows, we're busted + s1_fetch_all + + s1_commit -- 2.45.2 ^ permalink raw reply [nested|flat] 19+ messages in thread
end of thread, other threads:[~2025-01-07 17:46 UTC | newest] Thread overview: 19+ messages (download: mbox mbox.gz follow: Atom feed) -- links below jump to the message on this page -- 2020-09-12 13:07 [PATCH 6/8] Ignore correlation for new BRIN opclasses Tomas Vondra <[email protected]> 2024-12-02 15:08 Re: Incorrect result of bitmap heap scan. Matthias van de Meent <[email protected]> 2024-12-02 16:07 ` Re: Incorrect result of bitmap heap scan. Peter Geoghegan <[email protected]> 2024-12-02 16:43 ` Re: Incorrect result of bitmap heap scan. Tom Lane <[email protected]> 2024-12-02 16:52 ` Re: Incorrect result of bitmap heap scan. Andres Freund <[email protected]> 2024-12-02 17:02 ` Re: Incorrect result of bitmap heap scan. Tom Lane <[email protected]> 2024-12-02 17:19 ` Re: Incorrect result of bitmap heap scan. Andres Freund <[email protected]> 2024-12-04 10:39 ` Re: Incorrect result of bitmap heap scan. Matthias van de Meent <[email protected]> 2024-12-02 17:15 ` Re: Incorrect result of bitmap heap scan. Peter Geoghegan <[email protected]> 2024-12-02 19:44 ` Re: Incorrect result of bitmap heap scan. Peter Geoghegan <[email protected]> 2024-12-02 16:46 ` Re: Incorrect result of bitmap heap scan. Andres Freund <[email protected]> 2024-12-02 16:31 ` Re: Incorrect result of bitmap heap scan. Andres Freund <[email protected]> 2024-12-02 17:02 ` Re: Incorrect result of bitmap heap scan. Peter Geoghegan <[email protected]> 2024-12-02 19:42 ` Re: Incorrect result of bitmap heap scan. Andres Freund <[email protected]> 2024-12-02 20:56 ` Re: Incorrect result of bitmap heap scan. Peter Geoghegan <[email protected]> 2024-12-02 20:59 ` Re: Incorrect result of bitmap heap scan. Peter Geoghegan <[email protected]> 2024-12-03 01:22 ` Re: Incorrect result of bitmap heap scan. Peter Geoghegan <[email protected]> 2024-12-04 11:56 ` Re: Incorrect result of bitmap heap scan. Matthias van de Meent <[email protected]> 2025-01-07 17:46 ` Re: Incorrect result of bitmap heap scan. Matthias van de Meent <[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