Processing btree walks as a batch to parallelize IO

On 4/9/21 7:33 PM, James Coleman wrote:

$SUBJECT is still a very loosely formed idea, so forgive lack of detail
or things I've likely missed, but I wanted to get it out there to see if
it sounded at all intriguing to people. 

Background: One of the big problems with non-local storage such as AWS
EBS volumes or a SAN is that in a large database (really, working set,
where working set includes reads) exceeds the size of buffer cache (and
page cache) the cost of random page reads hitting the underlying disk
system dominates. This is because networked disks have an order of
magnitude higher latency than a bunch of RAIDed SSDs (even more so with
NVMe storage). In some of our experiments on Aurora I've seen a 10x
change versus pretty good physical hardware, and I'd assume RDS (since
it's EBS-backed) is similar. 

A specific area where this is particularly painful is btree index reads.
Walking the tree to leaf pages isn't naturally prefetchable, and so for
each level you pay the random page cost. Of course higher levels in the
tree will almost certainly exhibit emergent behavior such that they
(just by fact of the LRU caching) will be in the buffer cache, but for a
large index lower levels likely won't be. 

What do you consider a large index level?

Consider a 1TB table, with just a single UUID column - that's ~25B rows,
give or take. Real tables will have more columns, so this seems like a
reasonable model of the largest number of rows per relation. With ~32B
per index tuple, that's about 100M leaf pages, and with ~256 branches
per internal page, that's still only ~5 levels. I think it's quite rare
to see indexes with more than 6 or 7 levels.

And the internal pages are maybe 0.5% of the whole index (so ~4GB out of
750GB). I think the usual expectation is that most of that will fit into
RAM, but of course there may be more indexes competing for that.

I think the index level is not really the crucial bit - it's more about
the total amount of indexes in the DB.

If we squint a bit, insertions look a whole lot like reads as well since
we have to walk the tree to find the leaf insertion page for a new
tuple. This is particularly true for indexes where inserts are roughly
randomly distributed data, like a uuid. 

Yep. We need to walk the index to the leaf pages in both cases, both for
read and insert workloads.

The read-for-lookups problem is harder to solve, but the cost as it
relates to table inserts is possibly more tractable. Tables typically
have more than one index to update, so the obvious approach is "let's
just parallelize the index insertions". Of course we know that's
difficult given the multi-process approach Postgres uses for parallelism. 

Hmm. Not sure if reads are harder to real with, but I think you're right
those two cases (reads and writes) may look similar at the level of a
single index, but may need rather different approaches exactly because
inserts have to deal with all indexes, while reads only really deal with
a single index.

FWIW I think there are a couple options for improving reads, at least in
some cases.

1) I wonder if e.g. _bt_readnextpage could prefetch at least one page
ahead. We can't look further ahead, but perhaps this would help.

2) In some cases (e.g. nested loop with inner indexes scan) we could
collect an array of values and then look them up at once, which should
allow us to do at least some fo the I/O in parallel, I think. That's
similar to what you propose for writes, except that it works against the
same index.

Another approach that at first glance seems like it fits better into
Postgres (I'm not claiming it's easy or a small patch) would be to
process a batch of indexes at once. For example, if the index access
methods were extended to allow being given a list of indexes that need
to be walked, then the btree code could process each layer in the walk
as a group -- issuing IO fetches for all of the first level blocks in
the tree, and then computing all of the next level blocks needed and
issuing those IO requests at a time, and so on. 

Yeah, I agree having a way to say "prefetch all pages needed to insert
these keys into these indexes" might be better than just parallelizing
it in a "naive" way.

Not sure how complex would it be - I think the API would need to allow
traversing the index with each step split into two phases:

1) determine the page needed for the next step, return it to caller

2) the caller collects pages from all indexes, initiates prefetch

3) instruct indexes to actually do the next step, stop if it's a leaf
page (otherwise go to (1))

And then we might just do index inserts in a serial way, just like we do
today, hoping to hit the prefetched pages.

FWIW while this probably helps saturating the I/O, it unfortunately does
nothing to reduce the write amplification - we still need to modify the
same amount of leaf pages in all indexes, produce the same amount of WAL
etc. I think there were some proposals to add small internal buffers,
and instead of pushing the inserts all the way down to the leaf page,
just add them to the internal buffer. And when the buffer gets full,
propagate the contents to the next level of buffers.

For example, each internal page might have one "buffer" page, so the
index size would not really change (the internal pages would double, but
it's still jut ~1% of the total index size). Of course, this makes
lookups more complex/expensive, because we need to check the internal
buffers. But it does reduce the write amplification, because it combines
changes to leaf pages.

In some workloads we've been testing I believe such an approach could
plausibly improve table insert (and update) performance by multiple
hundreds of percent. 

I don't have any code at the moment to show here, but I wanted to get
the idea out there to see if there were any immediate reactions or other
thoughts on the topic.

Thoughts?

I think you're right indexes may be a serious bottleneck in some cases,
so exploring ways to improve that seems useful. Ultimately I think we
should be looking for ways to reduce the amount of work we need to do,
but parallelizing it (i.e. doing the same amount of work but in multiple
processes) is a valid approach too.

regards

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

On Fri, Apr 9, 2021 at 4:57 PM Tomas Vondra
<tomas.vondra@enterprisedb.com> wrote:

On 4/9/21 7:33 PM, James Coleman wrote:

$SUBJECT is still a very loosely formed idea, so forgive lack of detail
or things I've likely missed, but I wanted to get it out there to see if
it sounded at all intriguing to people.

Background: One of the big problems with non-local storage such as AWS
EBS volumes or a SAN is that in a large database (really, working set,
where working set includes reads) exceeds the size of buffer cache (and
page cache) the cost of random page reads hitting the underlying disk
system dominates. This is because networked disks have an order of
magnitude higher latency than a bunch of RAIDed SSDs (even more so with
NVMe storage). In some of our experiments on Aurora I've seen a 10x
change versus pretty good physical hardware, and I'd assume RDS (since
it's EBS-backed) is similar.

A specific area where this is particularly painful is btree index reads.
Walking the tree to leaf pages isn't naturally prefetchable, and so for
each level you pay the random page cost. Of course higher levels in the
tree will almost certainly exhibit emergent behavior such that they
(just by fact of the LRU caching) will be in the buffer cache, but for a
large index lower levels likely won't be.

What do you consider a large index level?

In general it's probably all levels but the leaves (though depends on
cache and index size etc.)

Consider a 1TB table, with just a single UUID column - that's ~25B rows,
give or take. Real tables will have more columns, so this seems like a
reasonable model of the largest number of rows per relation. With ~32B
per index tuple, that's about 100M leaf pages, and with ~256 branches
per internal page, that's still only ~5 levels. I think it's quite rare
to see indexes with more than 6 or 7 levels.

And the internal pages are maybe 0.5% of the whole index (so ~4GB out of
750GB). I think the usual expectation is that most of that will fit into
RAM, but of course there may be more indexes competing for that.

I think the index level is not really the crucial bit - it's more about
the total amount of indexes in the DB.

I suppose? If the tables/indexes/etc. size is sufficiently large
relative to cache size it won't matter the quantity.

If we squint a bit, insertions look a whole lot like reads as well since
we have to walk the tree to find the leaf insertion page for a new
tuple. This is particularly true for indexes where inserts are roughly
randomly distributed data, like a uuid.

Yep. We need to walk the index to the leaf pages in both cases, both for
read and insert workloads.

The read-for-lookups problem is harder to solve, but the cost as it
relates to table inserts is possibly more tractable. Tables typically
have more than one index to update, so the obvious approach is "let's
just parallelize the index insertions". Of course we know that's
difficult given the multi-process approach Postgres uses for parallelism.

Hmm. Not sure if reads are harder to real with, but I think you're right
those two cases (reads and writes) may look similar at the level of a
single index, but may need rather different approaches exactly because
inserts have to deal with all indexes, while reads only really deal with
a single index.

Right. In practice it's harder to deal with a single index scan
because you don't have multiple such scans to parallelize.

FWIW I think there are a couple options for improving reads, at least in
some cases.

1) I wonder if e.g. _bt_readnextpage could prefetch at least one page
ahead. We can't look further ahead, but perhaps this would help.

2) In some cases (e.g. nested loop with inner indexes scan) we could
collect an array of values and then look them up at once, which should
allow us to do at least some fo the I/O in parallel, I think. That's
similar to what you propose for writes, except that it works against the
same index.

The "collect an array of values" approach isn't one I'd considered,
but seems likely interesting.

Another approach that at first glance seems like it fits better into
Postgres (I'm not claiming it's easy or a small patch) would be to
process a batch of indexes at once. For example, if the index access
methods were extended to allow being given a list of indexes that need
to be walked, then the btree code could process each layer in the walk
as a group -- issuing IO fetches for all of the first level blocks in
the tree, and then computing all of the next level blocks needed and
issuing those IO requests at a time, and so on.

Yeah, I agree having a way to say "prefetch all pages needed to insert
these keys into these indexes" might be better than just parallelizing
it in a "naive" way.

Not sure how complex would it be - I think the API would need to allow
traversing the index with each step split into two phases:

1) determine the page needed for the next step, return it to caller

2) the caller collects pages from all indexes, initiates prefetch

3) instruct indexes to actually do the next step, stop if it's a leaf
page (otherwise go to (1))

And then we might just do index inserts in a serial way, just like we do
today, hoping to hit the prefetched pages.

Correct; this is roughly what I was envisioning.

FWIW while this probably helps saturating the I/O, it unfortunately does
nothing to reduce the write amplification - we still need to modify the
same amount of leaf pages in all indexes, produce the same amount of WAL
etc. I think there were some proposals to add small internal buffers,
and instead of pushing the inserts all the way down to the leaf page,
just add them to the internal buffer. And when the buffer gets full,
propagate the contents to the next level of buffers.

For example, each internal page might have one "buffer" page, so the
index size would not really change (the internal pages would double, but
it's still jut ~1% of the total index size). Of course, this makes
lookups more complex/expensive, because we need to check the internal
buffers. But it does reduce the write amplification, because it combines
changes to leaf pages.

I think I've seen that discussion, and it's very interesting, but also
I think still orthogonal to this.

In some workloads we've been testing I believe such an approach could
plausibly improve table insert (and update) performance by multiple
hundreds of percent.

I don't have any code at the moment to show here, but I wanted to get
the idea out there to see if there were any immediate reactions or other
thoughts on the topic.

Thoughts?

I think you're right indexes may be a serious bottleneck in some cases,
so exploring ways to improve that seems useful. Ultimately I think we
should be looking for ways to reduce the amount of work we need to do,
but parallelizing it (i.e. doing the same amount of work but in multiple
processes) is a valid approach too.

Thanks for the feedback.

James

On Fri, 9 Apr 2021 at 16:58, Tomas Vondra <tomas.vondra@enterprisedb.com> wrote:

On 4/9/21 7:33 PM, James Coleman wrote:

A specific area where this is particularly painful is btree index reads.
Walking the tree to leaf pages isn't naturally prefetchable, and so for
each level you pay the random page cost. Of course higher levels in the
tree will almost certainly exhibit emergent behavior such that they
(just by fact of the LRU caching) will be in the buffer cache, but for a
large index lower levels likely won't be.

We've talked before about buffering inserts even just for disk-based
indexes. Much like how GIN buffers inserts and periodically flushes
them out. We talked about doing a local buffer in each session since
no other session even needs to see these buffered inserts until commit
anyways. And we can more efficiently merge in multiple keys at once
than doing them one by one.

But that was just for disk i/o. For something longer-latency it would
be an even bigger win. Buffer the inserted keys in local memory in
case you do lookups in this same session and start the i/o to insert
the rows into the index but handle that in the background or in a
separate process without blocking the transaction until commit.

What do you consider a large index level?

Consider a 1TB table, with just a single UUID column - that's ~25B rows,
give or take. Real tables will have more columns, so this seems like a
reasonable model of the largest number of rows per relation. With ~32B
per index tuple, that's about 100M leaf pages, and with ~256 branches
per internal page, that's still only ~5 levels. I think it's quite rare
to see indexes with more than 6 or 7 levels.

That's a good model for a well-designed schema with an efficient
index. There are plenty of less-than-optimal schemas with indexes on
longer column lists or fairly large text fields....

--
greg

On Fri, May 7, 2021 at 3:34 PM Greg Stark <stark@mit.edu> wrote:

We've talked before about buffering inserts even just for disk-based
indexes. Much like how GIN buffers inserts and periodically flushes
them out. We talked about doing a local buffer in each session since
no other session even needs to see these buffered inserts until commit
anyways. And we can more efficiently merge in multiple keys at once
than doing them one by one.

Mark Callaghan's high level analysis of the trade-offs here is worth a
read, too.

That's a good model for a well-designed schema with an efficient
index. There are plenty of less-than-optimal schemas with indexes on
longer column lists or fairly large text fields....

Suffix truncation can take care of this -- all you really need is a
minimally distinguishing separator key to delineate which values
belong on which page one level down. It is almost always possible for
leaf page splits to find a way to make the new high key (also the key
to be inserted in the parent level) much smaller than your typical
key. Granted, we don't have what I've called "classic" suffix
truncation (within text column truncation) yet, so this analysis isn't
going to work with long text keys (we only truncate at the attribute
granularity currently).

Even if we're pessimistic about suffix truncation, the logarithmic
rate of growth still wins -- Tomas' analysis is sound. You cannot
realistically make a Postgres B-Tree have more than about 1% of all
pages as internal pages, unless you make the indexed keys ludicrously
large -- as in several hundred bytes each (~0.5% is typical in
practice). I think that 6 levels is very pessimistic, even with a
massive B-Tree with weirdly large keys. My mental model for internal
pages is that they are practically guaranteed to be in shared_buffers
at all times, which is about as accurate as any generalization like
that ever can be.

I once wrote a test harness that deliberately created a B-Tree that
was as tall as possible -- something with the largest possible index
tuples on the leaf level (had to disable TOAST for this). I think that
it was about 7 or 8 levels deep. The CPU overhead of the test case
made it excruciatingly slow, but it wasn't I/O bound at all (pretty
sure it all fitted in shared_buffers).

--
Peter Geoghegan