Subject: Re: [WIP] [B-Tree] Keep indexes sorted by heap physical location

From: Peter Geoghegan <[email-masked]>
Date: Fri, 18 Nov 2016 17:05:20 -0800

On Thu, Aug 18, 2016 at 2:15 PM, Peter Geoghegan <[email-masked]> wrote:
> I think that this is a bad idea. We need to implement suffix
> truncation of internal page index tuples at some point, to make them
> contain less information from the original leaf page index tuple.
> That's an important optimization, because it increases fan-in. This
> seems like a move in the opposite direction.

Maybe I was too hasty, here. Can you rebase this patch, Claudio?

It's possible that this idea could have further non-obvious benefits.
I see some potential for this to help with nbtree page deletion, item
recycling, etc. For example, maybe VACUUM can manage to do something
much closer to a regular index scan when that seems to make sense --
Andres (CC'd) has talked about this before. And, maybe we get a
benefit from localizing where the LP_DEAD bit can be set for the
kill_prior_tuple stuff to work in UPDATE-heavy workloads. Naturally,
there'd often be some kind of locality in terms of older row versions
belonging earlier in the heap, versions which can be concentrated onto
one leaf page with this patch. As newer updates make it look like the
leaf page needs to be split, there is a concentration of LP_DEAD-set
line items to reclaim space from, letting some UPDATEs (index tuple
inserters) defer the split. There is a lot less value in the LP_DEAD
stuff if reclaimable line items are sprayed all over the place, which
seems quite possible to me on current versions.

I also think that this might help with bitmap index scans.

-- 
Peter Geoghegan

-- 
Sent via pgsql-hackers mailing list ([email-masked])
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

---

From: Claudio Freire <[email-masked]>
Date: Fri, 18 Nov 2016 22:27:10 -0300

> Maybe I was too hasty, here. Can you rebase this patch, Claudio?

I've been changing the on-disk format considerably, to one that makes
more sense.

I haven't posted it because it still doesn't have suffix (and prefix)
truncation, but it should be compatible with it (ie: it could be
implemented as an optimization that doesn't change the on-disk
format).

However, I haven't tested the current state of the patch thoroughly.

If a WIP is fine, I can post the what I have, rebased.

> much closer to a regular index scan when that seems to make sense --

That was on my mind too

> I also think that this might help with bitmap index scans.

How so?

AFAIK it helps regular scans on low-cardinality indexes more than
bitmap index scans. With low cardinality indexes, the resulting heap
access pattern will be an unordered series of sequential range scans,
which is better than the fully random scan the current layout causes.
Bitmap index scans, however, deny that benefit.

---

From: Peter Geoghegan <[email-masked]>
Date: Fri, 18 Nov 2016 18:09:53 -0800

> I've been changing the on-disk format considerably, to one that makes

I can see how that would be necessary. I'm going to suggest some more
things that need a new btree version number now, too.

I realized today, quite suddenly, why I disliked your original patch:
it didn't go far enough with embracing the idea of
heap-item-pointer-as-key. In other words, I didn't like that you
didn't change anything in the internal pages. Maybe you should put
heap TIDs someplace in new internal pages, so that even there we treat
them as part of the key. This may significantly benefit UPDATE-heavy
workloads where HOT doesn't work out so well. Particularly for
non-unique indexes, we currently have to wade through a lot of bloat
from the leaf level, rather than jumping straight to the correct leaf
page when updating or inserting.

You might not want to do the same with unique indexes, where we must
initially buffer lock "the first leaf page that a duplicate could be
on" while we potentially look in one or more additional sibling pages
(but bloat won't be so bad there, perhaps). Or, you might want to make
sure that B-Tree tuple insertions still find that "first page" to
check, despite still generally treating heap item pointer as part of
the key proper (in unique indexes, it can still behave like NULL, and
not participate in uniqueness checking, while still essentially being
part of the key/sort order).

Of course, it isn't great to add stuff to the internal pages, but if
you're also implementing suffix truncation, there is probably no harm
at all. You're only going to affect cases that will also greatly
benefit from having that extra information, to guide insertions of new
values to the right place more efficiently (by inserters, I mostly
mean insertions from UPDATEs).

It also occurs to me that our performance for updates in the event of
many NULL values in indexes is probably really bad, and could be
helped by this. You'll want to test all of this with a workload that
isn't very sympathetic to HOT, of course -- most of these benefits are
seen when HOT doesn't help.

> If a WIP is fine, I can post the what I have, rebased.

I'm mostly curious about the effects on bloat. I now feel like you
haven't sufficiently examined the potential benefits there, since you
never made heap item pointer a first class part of the key space.
Maybe you'd like to look into that yourself first?

>> I also think that this might help with bitmap index scans.

I was thinking about teaching nbtree to start the scan at the level
above the leaf level. If the heap TID was part of the key proper, one
can imagine it being much cheaper to build a bitmap for a moderate
cardinality value (e.g., NULL values needed for "WHERE foo IS NULL"
index scans). The exact details would need to be worked out, but one
can imagine building a bitmap that is much larger than necessary one
level up from the leaf, then lazily unsetting bits as we descend the
B-Tree to the leaf level and find pages whose bitmap bits can be
unset. We might balance the avoidance of I/O during the scan against
how much we might expect to save in a subsequent bitmap heap scan, and
so on. This might be based on a selectivity estimate.

That's all fairly hand-wavy, certainly, but I see significant
potential along these lines.

-- 
Peter Geoghegan

---

From: Claudio Freire <[email-masked]>
Date: Mon, 21 Nov 2016 14:42:13 -0300

On Fri, Nov 18, 2016 at 11:09 PM, Peter Geoghegan <[email-masked]> wrote:
> didn't change anything in the internal pages.

But it did. In fact it only changed internal pages.

> Maybe you should put
> them as part of the key.

That is indeed what's happening (both in the old and new version).

The new version also opens up to the possibility of omitting the heap
TID in inner pages, if they're redundant (ie: if two consecutive keys
are different already, the heap TID part of the key is redundant,
since it's not necessary to make tree descent decisions).

> This may significantly benefit UPDATE-heavy

That is improved in the patch as well. The lookup for an insertion
point for a heavily bloated (unique or not) index is done efficiently,
instead of the O(N^2) way it used before.

> (but bloat won't be so bad there, perhaps).

It's done even for unique indexes. Locking in that case becomes
complex, true, but I believe it's not an insurmountable problem.

> Or, you might want to make

It behaves like that (even though it's not coded like that)

> seen when HOT doesn't help.

I haven't really tested with an overabundance of NULLs, I'll add that
to the tests. I have tested low-cardinality indexes though, but only
for correctness.

> Maybe you'd like to look into that yourself first?

What do you mean with "first class part"?

It's not included in the scankey for a variety of reasons, not the
least of which is not breaking the interface for current uses, and
because the tid type is quite limited in its capabilities ATM. Also,
the heap TID is usually there on most AM calls that care about it (ie:
insertions have it, of course), so adding it to the scankey also
seemed redundant.

If not adding to the scankey, what do you mean by "first class" then?

---

From: Peter Geoghegan <[email-masked]>
Date: Mon, 21 Nov 2016 12:42:40 -0800

> But it did. In fact it only changed internal pages.

Oh, okay.

> That is indeed what's happening (both in the old and new version).

Good.

> since it's not necessary to make tree descent decisions).

Makes sense; this is just another aspect of suffix truncation.

> instead of the O(N^2) way it used before.

Cool.

> complex, true, but I believe it's not an insurmountable problem.

I actually don't think that that would be all that complicated. It's
just one case where you have to mostly match the existing behavior.

> It behaves like that (even though it's not coded like that)

Why not? What do you mean?

What I'm interested in evaluating is an implementation where an index
on (foo) has a sort order/key space that is precisely the same as an
index on (foo, ctid), with zero exceptions.

> to the tests. I have tested low-cardinality indexes though, but only

I think we'll have to model data distribution to evaluate the idea
well. After all, if there is a uniform distribution of values anyway,
you're going to end up with many dirty leaf pages. Whereas, in the
more realistic case where updates are localized, we can hope to better
amortize the cost of inserting index tuples, and recycling index
tuples.

> insertions have it, of course), so adding it to the scankey also

I mean that insertions into indexes that are low cardinality should be
largely guided by TID comparisons.

> If not adding to the scankey, what do you mean by "first class" then?

Just what I said about the sort order of an index on "(foo)" now
precisely matching what we'd get for "(foo, ctid)". There are a couple
of tricky issues with that that you'd have to look out for, like
making sure that the high key continues to hold a real TID, which at a
glance looks like something that just happens already. I'm not sure
that we preserve the item pointer TID in all cases, since the current
assumption is that a high key's TID is just filler -- maybe we can
lose that at some point.

You should use amcheck to specifically verify that that happens
reliably in all cases. Presumably, its use of an insertion scankey
would automatically see the use of TID as a tie-breaker with patched
Postgres amcheck verification, and so amcheck will work for this
purpose unmodified.

-- 
Peter Geoghegan

---

From: Claudio Freire <[email-masked]>
Date: Mon, 21 Nov 2016 22:15:39 -0300

> index on (foo, ctid), with zero exceptions.

Well, the patch does the same sorting, but without explicitly adding
the ctid to the scankey.

When inserting into a unique index, the lookup for the insertion point
proceeds as it would if the key was (foo, ctid), finding a page in the
middle of the range that contain item pointers for foo.

When that happens on a regular index, the insertion is done at that
point and nothing else needs to be done. But when it happens on a
unique index, the code first checks to see if the first item pointer
for foo is on the same page (allegedly a frequent case). If so, the
uniqueness check is done in a very straightforward and efficient
manner. If not, however, the code retraces its steps up the tree to
the first time it followed a key other than foo (that's the only way
it could land at a middle page), and then follows the downlinks
looking at a truncated key (just foo, ignoring ctid).

Kind of what you say, but without the explicit null.

> amortize the cost of inserting index tuples, and recycling index

Quite possibly

> largely guided by TID comparisons.

...

> precisely matching what we'd get for "(foo, ctid)".

It is the case in both versions of the patch

> There are a couple

I thought long about that, and inner pages don't need a real TID in
their keys, as those keys only specify key space cutoff points and not
real tids, and high tids in leaf pages are always real.

I haven't had any issue with that, aside from the headaches resulting
from thinking about that for protracted periods of time.

> Postgres amcheck verification, and so amcheck will work for this

It's totally on my roadmap. I'll have to adapt it for the new index
format though, it doesn't work without modification.

---

From: Peter Geoghegan <[email-masked]>
Date: Tue, 22 Nov 2016 19:27:31 -0800

> real tids, and high tids in leaf pages are always real.

Not if there are duplicates in the inner pages. Then, you have to add
in the TID, and separate the key space, to guide insertions to the
right leaf page directly (particularly for non-HOT UPDATEs). That's
what I'm mostly interested in investigating, here.

-- 
Peter Geoghegan