Horton

Re: BitmapHeapScan streaming read user and prelim refactoring

Andres Freund <andres@anarazel.de>

View thread View on postgr.es
From: Andres Freund <andres@anarazel.de>
To: James Hunter <james.hunter.pg@gmail.com>
Cc: Thomas Munro <thomas.munro@gmail.com>, Melanie Plageman <melanieplageman@gmail.com>, Tomas Vondra <tomas@vondra.me>, Nazir Bilal Yavuz <byavuz81@gmail.com>, Dilip Kumar <dilipbalaut@gmail.com>, Heikki Linnakangas <hlinnaka@iki.fi>, Pg Hackers <pgsql-hackers@postgresql.org>
Date: 2025-04-14T17:20:26Z
Lists: pgsql-hackers 
Hi,

On 2025-04-14 09:58:19 -0700, James Hunter wrote:
> Of course, late feedback is a burden, but I think our discussion here
> (and, in the future, if you try to "ReadStream" BTree index pages,
> themselves) illustrates my point.

FWIW, it's quite conceivable that we'll want to use non-readstream prefetching
for some cases where "heuristic" prefetching is easier. I think prefetching of
btree pages is one of those cases.

The read stream based API provides a single point of adjusting the readahead
logic, implementing read-combining etc, without needing to know about that in
the user of the read stream.


> I see two orthogonal problems, in processing Bitmap Heap pages in
> parallel: (1) we need to prefetch enough pages, far enough in advance,
> to hide read latency; (2) later, every parallel worker needs to be
> given a set of pages to process, in a way that minimizes contention.
> 
> The easiest way to hand out work to parallel workers (and often the
> best) is to maintain a single, shared, global work queue. Just put
> whatever pages you prefetch into a FIFO queue, and let each worker
> pull one piece of "work" off that queue. In this was, there's no
> "ramp-down" problem.

If you just issue prefetch requests separately you'll get no read combining -
and it turns out that that is a really rather significant loss, both on the
storage layer and just due to the syscall overhead.  So you do need to perform
batching when issuing IO. Which in turn requires a bit of rampup logic etc.


> If you find that contention on this shared queue becomes a bottleneck,
> then you just pull *n* pieces of work, in a batch. Then the
> "ramp-down" problem is limited to "n", instead of just 1. Often, one
> can find a suitable value of n that simultaneously makes contention
> effectively zero, while avoiding "ramp-down" problems; say n = 10.
> 
> So much for popping from the shared queue. Pushing to the shared queue
> is also easy, because you have async reads. Anytime a worker pops a
> (batch of) work item(s) off the shared queue, it checks to see if the
> queue is still large enough. If not, it issues the appropriate
> prefetch / "ReadStream" calls.
> 
> A single shared queue is easiest, but sometimes there's no way to
> prevent it from becoming a bottleneck. In that case, one typically
> partitions the input at startup, gives each worker its own partition,
> and waits for all workers to complete. In this, second, model, workers
> are entirely independent, so there is no contention: we scale out
> perfectly. The problem, as you've pointed out, is that one worker
> might finish its own work long before another; and then the worker
> that finished its work is idle and therefore wasted.
> 
> This is why a single shared queue is so nice, because it avoids
> workers being idle. But I am confused by your proposal, which seems to
> be trying to get the behavior of a single shared queue, but
> implemented with the added complexity of multiple queues.
> 
> Why not just use a single queue?

Accessing buffers in a maximally interleaved way, which is what a single queue
would give you, adds a good bit of overhead when you have a lot of memory,
because e.g. TLB hit rate is minimized.


> > These are now
> > real IOs running in the background and for the *exact* blocks you will
> > consume; posix_fadvise() was just a stepping towards AIO that
> > tolerated sloppy synchronisation including being entirely wrong.
> 
> It has never been clear to me why prefetching the exact blocks you'll
> later consume is seen as a *benefit*, rather than a *cost*. I'm not
> aware of any prefetch interface, other than PG's "ReadStream," that
> insists on this. But that's a separate discussion...

It (randomly ordered):

a) reduces wasted IO

b) makes things like IO combining a lot easier

c) makes it a lot easier to adaptively control readahead distance, because you
   have information about
   1) the # in-flight IOs
   2) the # completed IOs
   3) current position
   4) reada

d) provides *per-stream* control over readahead. You want to be only as
   aggressive about prefetching as you need to be, which very well can differ
   between different parts of a query tree.

e) provides one central point to implement readahead logic


As I said above, that's not to say that we'll only ever want to do readahead
via a the read stream interface.

Greetings,

Andres Freund

Commits

  1. Fix bitmapheapscan incorrect recheck of NULL tuples

  2. Increase default maintenance_io_concurrency to 16

  3. Separate TBM[Shared|Private]Iterator and TBMIterateResult

  4. Improve read_stream.c advice for dense streams.

  5. Increase default effective_io_concurrency to 16

  6. Delay extraction of TIDBitmap per page offsets

  7. Add lossy indicator to TBMIterateResult

  8. Move BitmapTableScan per-scan setup into a helper

  9. Add and use BitmapHeapScanDescData struct

  10. Fix bitmap table scan crash on iterator release

  11. Bitmap Table Scans use unified TBMIterator

  12. Add common interface for TBMIterators

  13. Make table_scan_bitmap_next_block() async-friendly

  14. Move EXPLAIN counter increment to heapam_scan_bitmap_next_block

  15. Refactor tidstore.c iterator buffering.

  16. BitmapHeapScan: Remove incorrect assert and reset field

  17. Change BitmapAdjustPrefetchIterator to accept BlockNumber

  18. BitmapHeapScan: Use correct recheck flag for skip_fetch

  19. BitmapHeapScan: Push skip_fetch optimization into table AM

  20. BitmapHeapScan: postpone setting can_skip_fetch

  21. BitmapHeapScan: begin scan after bitmap creation

  22. Fix EXPLAIN Bitmap heap scan to count pages with no visible tuples

  23. Remove redundant snapshot copying from parallel leader to workers

  24. Remove some obsolete smgrcloseall() calls.

  25. Remove the "snapshot too old" feature.

  26. Compute XID horizon for page level index vacuum on primary.