Re: read stream: Backward I/O combining

Hi,

Thanks for the patch. I got this patch a couple days/week ago, as part
of the work on index prefetching. So I got to do a bit of benchmarking.

Note: It's hard to generate the backward heap access without an index
scan, as all other ReadStream users generate forward pattern (with
increasing block number). So this is very index-scan specific patch.

I've been also interested if / how much this helps to mitigate the
annoying differences I described almost exactly a year ago:

https://vondra.me/posts/fun-and-weirdness-with-ssds/

The gist of that post is that both the kernel read-ahead and the
heuristics in SSD firmware are very helpful, but do not kick in for
backward access at all (just like "our" combining before the patch).

The blog post focuses on "raw" fio tests, showing massive differences
depending on the access direction. In most cases the backward access
performs about the same as random.

There's a couple queries with index scans, and the cases with backward
access are often ~30x slower, despite accessing exactly the same amount
of data. It's all just because the kernel/firmware does not recognize
the backward access pattern.

The blog post did not test the index prefetching patch, but that helps
quite a bit - it gets the regression to ~5x (so much better than 30x).
But it's still far worse than an equivalent forward case. Most likely
due to the I/O combining not kicking in, so still doing 8K reads (while
for forward access it gets combined into 128K chunks).

So I was wondering if this patch gets us closer to the forward access.

This may seem like an artificial case, but I think it's pretty common in
practice. Consider a table with a "creation time", and queries like:

SELECT * FROM my_table ORDER BY creation_time DESC

The table is likely correlated with creation_time (modulo some small
perturbations due to deletes / updates), and so the query will generate
a nice backward access pattern. I could construct more more examples.

Of course, the costing completely ignores this effect. That seems bad,
but it's not clear what to do about it.

So, I ran a benchmark compring timings for runs with a number of
parameters. You can find the scripts and results here:

https://github.com/tvondra/index-backward-tests

There's a "fio" folder with measurements for some low-level I/O tests
(some results are interesting/funny), but I'll focus on the "pg"
results, measuring timing of queries.

It runs tests for different combinations of a couple parameters:

- buffered vs. direct I/O
- io_method and io_workers
- 0 and 4 parallel workers
- branch: master vs. index-prefetch vs. index-prefetch-backward-combine
- effective_io_concurrency 16 and 128
- ASC / DESC query order (translates to forward vs. backward access)
- device (6 different SSD devices on 2 machines)

I'm attaching a PDF summarizing the results. The columns show timings
for the ASC/DESC direction, prefetch on/off and various branches. And
then the last group of columns show timings relative to master/ASC
(which is a baseline). green=good red=bad, as usual.

The pattern is pretty clear. The DESC (backward access) is much slower,
hence the huge area of red results for runs without index prefetch.

The index prefetch helps quite a bit, with ~5x speedup, which is nice.
But it's still ~5x slower than the ASC case. The combining gets us to
~1.5x compared to master/ASC for all the tested SSD devices etc.

So I think this works pretty well, and it largely addresses the issue
with backward access.

I haven't done that yet, but it might be interesting to run these tests
on non-local storage.

regards

--
Tomas Vondra