Subject: Re: BitmapHeapScan streaming read user and prelim refactoring

From: Melanie Plageman <[email-masked]>
Date: Wed, 28 Feb 2024 15:06:08 -0500

On Wed, Feb 28, 2024 at 2:23 PM Tomas Vondra
<[email-masked]> wrote:
>
> On 2/28/24 15:56, Tomas Vondra wrote:
> >> ...
> >
> > Sure, I can do that. It'll take a couple hours to get the results, I'll
> > share them when I have them.
> >
>
> Here are the results with only patches 0001 - 0012 applied (i.e. without
> the patch introducing the streaming read API, and the patch switching
> the bitmap heap scan to use it).
>
> The changes in performance don't disappear entirely, but the scale is
> certainly much smaller - both in the complete results for all runs, and
> for the "optimal" runs that would actually pick bitmapscan.

Hmm. I'm trying to think how my refactor could have had this impact.
It seems like all the most notable regressions are with 4 parallel
workers. What do the numeric column labels mean across the top
(2,4,8,16...) -- are they related to "matches"? And if so, what does
that mean?

- Melanie

---

From: Tomas Vondra <[email-masked]>
Date: Thu, 29 Feb 2024 00:17:51 +0100

> (2,4,8,16...) -- are they related to "matches"? And if so, what does

That's the number of distinct values matched by the query, which should
be an approximation of the number of matching rows. The number of
distinct values in the data set differs by data set, but for 1M rows
it's roughly like this:

uniform: 10k
linear: 10k
cyclic: 100

So for example matches=128 means ~1% of rows for uniform/linear, and
100% for cyclic data sets.

As for the possible cause, I think it's clear most of the difference
comes from the last patch that actually switches bitmap heap scan to the
streaming read API. That's mostly expected/understandable, although we
probably need to look into the regressions or cases with e_i_c=0.

To analyze the 0001-0012 patches, maybe it'd be helpful to run tests for
individual patches. I can try doing that tomorrow. It'll have to be a
limited set of tests, to reduce the time, but might tell us whether it's
due to a single patch or multiple patches.

regards

-- 
Tomas Vondra
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

---

From: Melanie Plageman <[email-masked]>
Date: Wed, 28 Feb 2024 18:40:47 -0500

> 100% for cyclic data sets.

Ah, thank you for the explanation. I also looked at your script after
having sent this email and saw that it is clear in your script what
"matches" is.

> probably need to look into the regressions or cases with e_i_c=0.

Right, I'm mostly surprised about the regressions for patches 0001-0012.

Re eic 0: Thomas Munro and I chatted off-list, and you bring up a
great point about eic 0. In old bitmapheapscan code eic 0 basically
disabled prefetching but with the streaming read API, it will still
issue fadvises when eic is 0. That is an easy one line fix. Thomas
prefers to fix it by always avoiding an fadvise for the last buffer in
a range before issuing a read (since we are about to read it anyway,
best not fadvise it too). This will fix eic 0 and also cut one system
call from each invocation of the streaming read machinery.

> due to a single patch or multiple patches.

Yes, tomorrow I planned to start trying to repro some of the "red"
cases myself. Any one of the commits could cause a slight regression
but a 3.5x regression is quite surprising, so I might focus on trying
to repro that locally and then narrow down which patch causes it.

For the non-cached regressions, perhaps the commit to use the correct
recheck flag (0004) when prefetching could be the culprit. And for the
cached regressions, my money is on the commit which changes the whole
control flow of BitmapHeapNext() and the next_block() and next_tuple()
functions (0010).

- Melanie

---

From: Tomas Vondra <[email-masked]>
Date: Thu, 29 Feb 2024 13:54:05 +0100

> control flow of BitmapHeapNext() and the next_block() and next_tuple()

I do have some partial results, comparing the patches. I only ran one of
the more affected workloads (cyclic) on the xeon, attached is a PDF
comparing master and the 0001-0014 patches. The percentages are timing
vs. the preceding patch (green - faster, red - slower).

This suggests only patches 0010 and 0014 affect performance, the rest is
just noise. I'll see if I can do more runs and get data from the other
machine (seems it's more significant on old SATA SSDs).

regards

---

From: Melanie Plageman <[email-masked]>
Date: Thu, 29 Feb 2024 16:19:43 -0500

> vs. the preceding patch (green - faster, red - slower).

Just confirming: the results are for uncached?

- Melanie

---

From: Tomas Vondra <[email-masked]>
Date: Thu, 29 Feb 2024 23:44:27 +0100

> Just confirming: the results are for uncached?

Yes, cyclic data set, uncached case. I picked this because it seemed
like one of the most affected cases. Do you want me to test some other
cases too?

regards

---

From: Tomas Vondra <[email-masked]>
Date: Fri, 1 Mar 2024 00:44:32 +0100

> like one of the most affected cases. Do you want me to test some other

BTW I decided to look at the data from a slightly different angle and
compare the behavior with increasing effective_io_concurrency. Attached
are charts for three "uncached" cases:

 * uniform, work_mem=4MB, workers_per_gather=0
 * linear-fuzz, work_mem=4MB, workers_per_gather=0
 * uniform, work_mem=4MB, workers_per_gather=4

Each page has charts for master and patched build (with all patches). I
think there's a pretty obvious difference in how increasing e_i_c
affects the two builds:

1) On master there's clear difference between eic=0 and eic=1 cases, but
on the patched build there's literally no difference - for example the
"uniform" distribution is clearly not great for prefetching, but eic=0
regresses to eic=1 poor behavior).

Note: This is where the the "red bands" in the charts come from.

2) For some reason, the prefetching with eic>1 perform much better with
the patches, except for with very low selectivity values (close to 0%).
Not sure why this is happening - either the overhead is much lower
(which would matter on these "adversarial" data distribution, but how
could that be when fadvise is not free), or it ends up not doing any
prefetching (but then what about (1)?).

3) I'm not sure about the linear-fuzz case, the only explanation I have
we're able to skip almost all of the prefetches (and read-ahead likely
works pretty well here).

regards

---

From: Melanie Plageman <[email-masked]>
Date: Thu, 29 Feb 2024 19:29:45 -0500

> like one of the most affected cases. Do you want me to test some other

So, I actually may have found the source of at least part of the
regression with 0010. I was able to reproduce the regression with
patch 0010 applied for the unached case with 4 workers and eic 8 and
100000000 rows for the cyclic dataset. I see it for all number of
matches. The regression went away (for this specific example) when I
moved the BitmapAdjustPrefetchIterator call back up to before the call
to table_scan_bitmap_next_block() like this:

diff --git a/src/backend/executor/nodeBitmapHeapscan.c
b/src/backend/executor/nodeBitmapHeapscan.c
index f7ecc060317..268996bdeea 100644
--- a/src/backend/executor/nodeBitmapHeapscan.c
+++ b/src/backend/executor/nodeBitmapHeapscan.c
@@ -279,6 +279,8 @@ BitmapHeapNext(BitmapHeapScanState *node)
        }

 new_page:
+       BitmapAdjustPrefetchIterator(node, node->blockno);
+
        if (!table_scan_bitmap_next_block(scan, &node->recheck,
&lossy, &node->blockno))
            break;

@@ -287,7 +289,6 @@ new_page:
        else
            node->exact_pages++;

-       BitmapAdjustPrefetchIterator(node, node->blockno);
        /* Adjust the prefetch target */
        BitmapAdjustPrefetchTarget(node);
    }

It makes sense this would fix it. I haven't tried all the combinations
you tried. Do you mind running your tests with the new code? I've
pushed it into this branch.
https://github.com/melanieplageman/postgres/commits/bhs_pgsr/

Note that this will fix none of the issues with 0014 because that has
removed all of the old prefetching code anyway.

Thank you sooo much for running these to begin with and then helping
me figure out what is going on!

- Melanie

---

From: Melanie Plageman <[email-masked]>
Date: Thu, 29 Feb 2024 20:18:20 -0500

> think there's a pretty obvious difference in how increasing e_i_c

Wow! These visualizations make it exceptionally clear. I want to go to
the Vondra school of data visualizations for performance results!

> regresses to eic=1 poor behavior).

Yes, so eic=0 and eic=1 are identical with the streaming read API.
That is, eic 0 does not disable prefetching. Thomas is going to update
the streaming read API to avoid issuing an fadvise for the last block
in a range before issuing a read -- which would mean no prefetching
with eic 0 and eic 1. Not doing prefetching with eic 1 actually seems
like the right behavior -- which would be different than what master
is doing, right?

Hopefully this fixes the clear difference between master and the
patched version at eic 0.

> prefetching (but then what about (1)?).

For the uniform with four parallel workers, eic == 0 being worse than
master makes sense for the above reason. But I'm not totally sure why
eic == 1 would be worse with the patch than with master. Both are
doing a (somewhat useless) prefetch.

With very low selectivity, you are less likely to get readahead
(right?) and similarly less likely to be able to build up > 8kB IOs --
which is one of the main value propositions of the streaming read
code. I imagine that this larger read benefit is part of why the
performance is better at higher selectivities with the patch. This
might be a silly experiment, but we could try decreasing
MAX_BUFFERS_PER_TRANSFER on the patched version and see if the
performance gains go away.

> we're able to skip almost all of the prefetches (and read-ahead likely

I started looking at the data generated by linear-fuzz to understand
exactly what effect the fuzz was having but haven't had time to really
understand the characteristics of this dataset. In the original
results, I thought uncached linear-fuzz and linear had similar results
(performance improvement from master). What do you expect with linear
vs linear-fuzz?

- Melanie