read stream: Backward I/O combining - Mailing list pgsql-hackers

Hi,

This patch implements backward I/O combining mainly to help index
prefetching work [1]. Since there is no real user of this patch
without [1], this patch should be applied on top of it. It doesn't
cleanly apply on top of the master without it.

----------

High level design:

Instead of implementing backward I/O combining in all subsystems (read
stream, aio, bufmgr etc.), I decided to implement it in read stream
level only. So, only read stream code knows backward I/O combining is
happening and then it sends the reverse of these I/O requests to lower
levels; so lower levels will behave the same as forward I/O combining.
Then the read stream returns these buffers in the reverse order as
they reversed once while sending to lower levels.This decision is made
because of 2 main reasons:
1- Almost all of I/O related code is designed for forward I/O
combining, there would be too much duplicated code.
2- There is no actual way to do backward read with pread(), it does
forward read only so the I/O request needs to be reversed at some
point.

----------

Implementation details:

We have a new struct called ReverseRange, this struct saves the
information of 'the start index of backward I/O combining and how many
blocks it includes'. All of the blocks in this range are in descending
order. Then when the read stream encounters the start index of
ReverseRange, we reverse them and read all buffers in this range
before returning any buffer to the read stream user. That is important
because let's say our ReverseRange consists of 5 blocks and their
numbers are [8, 7, 6, 5, 4], keep in mind that the first block that
will be returned is 8. When we reverse this range (while sending the
lower levels), blocks are in ascending order: [4, 5, 6, 7, 8] so the
first block we return (8) will be the last block we read. Because of
that, we need to read all blocks in range before returning any of
them.

Also, because of the same problem above we can't have forwarded
buffers in backward I/O combining (i.e having short read and then
continuing to expand I/O combined blocks from remaining I/O). Let's
have the same example, our range is [8, 7, 6, 5, 4] and its reverse is
[4, 5, 6, 7, 8]. We had a short read because of some reason and we
read [4, 5, 6] first. [7, 8] are still remaining and we must finish
reading [7, 8] before returning 8. We can't expand (combine) [7, 8]
with any blocks.

----------

Benchmark:

I used a simple benchmark script generated by LLM. I checked the
script and it works correctly. This script uses
read_stream_for_blocks() to benchmark, by using that we directly see
the effect of backward I/O combining patch without any external
effect. This benchmark shows up to 4x speedups for the backward scans
when the I/O combining is available and there are no regressions. I
see similar speedups with the backward index scan when the I/O
combining is available.

You can run the benchmark script by: 'DATADIR=/tmp/pg_datadir
./bench_read_stream.sh' command. Some results from the benchmark
script:

Without backward I/O combining patch:

=== cold ===
io_combine_limit |  forward(ms) | backward(ms) |  bwd/fwd
-----------------+--------------+--------------+---------
1                |      115.448 |      136.790 |    1.18x
8                |       49.344 |      141.556 |    2.87x
16               |       40.519 |      141.847 |    3.50x
32               |       35.429 |      139.396 |    3.93x


With backward I/O combining patch:

=== cold ===
io_combine_limit |  forward(ms) | backward(ms) |  bwd/fwd
-----------------+--------------+--------------+---------
1                |      112.774 |      134.188 |    1.19x
8                |       42.958 |       47.918 |    1.12x
16               |       40.161 |       40.352 |    1.00x
32               |       36.299 |       36.284 |    1.00x

----------

v1 is attached. 0001 is the squashed patch of v31 index prefetching
patches [2]. 0002 is the actual patch which implements backward I/O
combining. 0003 has the benchmark script and the required code to run
the benchmark. Only 0002 is attached for a review / commit.

Any feedback would be appreciated.

[1] https://postgr.es/m/cf85f46f-b02f-05b2-5248-5000b894ebab%40enterprisedb.com
[2] https://postgr.es/m/CAH2-WzmpQV7wqbwE_bW%2B1Ja32chnh87i%3Dwx2Y6NkhFiuEVsBzw%40mail.gmail.com

--
Regards,
Nazir Bilal Yavuz
Microsoft