Re: PoC: prefetching index leaf pages (for inserts)

Hi,

I had a chance to discuss this patch with Andres off-list a couple days
ago, and he suggested he tried sorting the (index) tuples before
inserting them, and that yielded significant benefits, possibly
comparable to the prefetching.

I've been somewhat skeptical the sorting might be very beneficial, but I
decided to do some more tests comparing the benefits.

The sorting only really works for bulk inserts (e.g. from COPY), when we
have multiple index tuples for each index. But I didn't have time to
rework the code like that, so I took a simpler approach - do the sort in
the INSERT, so that the insert tuples are sorted too. So, something like

  WITH data AS (SELECT md5(random()::text)::uuid
                  FROM generate_series(1,100) ORDER BY 1)
  INSERT INTO t SELECT * FROM data;

Obviously, this can only sort the rows in one way - if there are
multiple indexes, then only one of them will be sorted, limiting the
possible benefit of the optimization. In the COPY code we could do a
separate sort for each index, so the tuples would be sorted for all
indexes (which also has a cost, of course).

But as I said, I decided to do the simple SQL-level sort. There are
multiple indexes on the same column, so it's a bit as if we sorted the
tuples for each index independently.

Anyway, the test inserts batches of 100, ..., 100k rows into tables of
different sizes (10M - 1B rows), with/without prefetching, and possibly
sorts the batches before the insert. See the attached index.sql script.

The PDF shows the results, and also compares the different combinations.
For example the first 5 lines are results without and with prefetching,
followed by speedup, where green=faster and red=slower. For example 50%
means prefetching makes it 2x as fast.

Similarly, first column has timings without / with sorting, with speedup
right under it. Diagonally, we have speedup for enabling both sorting
and prefetch.

I did that with different table sizes, where 10M easily fits into RAM
while 1B certainly exceeds it. And I did that on the usual two machines
with different amounts of RAM and storage (SATA SSD vs. NVME).

The results are mostly similar on both, I think:

* On 10M tables (fits into RAM including indexes), prefetching doesn't
really help (assuming the data is not evicted from memory for other
reasons), and actually hurts a bit (~20%). Sorting does help, depending
on the number of indexes - can be 10-40% faster.

* On 1B tables (exceeds RAM), prefetching is a clear winner. Sorting
does not make any difference except for a couple rare "blips".

* On 100M tables it's a mix/transition of those two cases.


So maybe we should try doing both, perhaps with some heuristics to only
do the prefetching on sufficiently large/random indexes, and sorting
only on smaller ones?

Another option would be to make the prefetching smarter so that we don't
prefetch data that is already in memory (either in shared buffers or in
page cache). That would reduce the overhead/slowdown visible in results
on the 10M table.


regards

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