pgsql: Make heap TID a tiebreaker nbtree index column.
Make heap TID a tiebreaker nbtree index column.
Make nbtree treat all index tuples as having a heap TID attribute.
Index searches can distinguish duplicates by heap TID, since heap TID is
always guaranteed to be unique. This general approach has numerous
benefits for performance, and is prerequisite to teaching VACUUM to
perform "retail index tuple deletion".
Naively adding a new attribute to every pivot tuple has unacceptable
overhead (it bloats internal pages), so suffix truncation of pivot
tuples is added. This will usually truncate away the "extra" heap TID
attribute from pivot tuples during a leaf page split, and may also
truncate away additional user attributes. This can increase fan-out,
especially in a multi-column index. Truncation can only occur at the
attribute granularity, which isn't particularly effective, but works
well enough for now. A future patch may add support for truncating
"within" text attributes by generating truncated key values using new
opclass infrastructure.
Only new indexes (BTREE_VERSION 4 indexes) will have insertions that
treat heap TID as a tiebreaker attribute, or will have pivot tuples
undergo suffix truncation during a leaf page split (on-disk
compatibility with versions 2 and 3 is preserved). Upgrades to version
4 cannot be performed on-the-fly, unlike upgrades from version 2 to
version 3. contrib/amcheck continues to work with version 2 and 3
indexes, while also enforcing stricter invariants when verifying version
4 indexes. These stricter invariants are the same invariants described
by "3.1.12 Sequencing" from the Lehman and Yao paper.
A later patch will enhance the logic used by nbtree to pick a split
point. This patch is likely to negatively impact performance without
smarter choices around the precise point to split leaf pages at. Making
these two mostly-distinct sets of enhancements into distinct commits
seems like it might clarify their design, even though neither commit is
particularly useful on its own.
The maximum allowed size of new tuples is reduced by an amount equal to
the space required to store an extra MAXALIGN()'d TID in a new high key
during leaf page splits. The user-facing definition of the "1/3 of a
page" restriction is already imprecise, and so does not need to be
revised. However, there should be a compatibility note in the v12
release notes.
Author: Peter Geoghegan
Reviewed-By: Heikki Linnakangas, Alexander Korotkov
Discussion: /messages/by-id/CAH2-WzkVb0Kom=R+88fDFb=JSxZMFvbHVC6Mn9LJ2n=X=kS-Uw@mail.gmail.com
Branch
------
master
Details
-------
https://git.postgresql.org/pg/commitdiff/dd299df8189bd00fbe54b72c64f43b6af2ffeccd
Modified Files
--------------
contrib/amcheck/expected/check_btree.out | 5 +-
contrib/amcheck/sql/check_btree.sql | 5 +-
contrib/amcheck/verify_nbtree.c | 341 +++++++++++++++++++---
contrib/pageinspect/btreefuncs.c | 2 +-
contrib/pageinspect/expected/btree.out | 2 +-
contrib/pgstattuple/expected/pgstattuple.out | 10 +-
doc/src/sgml/indices.sgml | 24 +-
src/backend/access/common/indextuple.c | 6 +-
src/backend/access/nbtree/README | 124 ++++----
src/backend/access/nbtree/nbtinsert.c | 407 ++++++++++++++++----------
src/backend/access/nbtree/nbtpage.c | 206 +++++++++-----
src/backend/access/nbtree/nbtree.c | 2 +-
src/backend/access/nbtree/nbtsearch.c | 106 ++++++-
src/backend/access/nbtree/nbtsort.c | 91 +++---
src/backend/access/nbtree/nbtutils.c | 410 ++++++++++++++++++++++++---
src/backend/access/nbtree/nbtxlog.c | 47 +--
src/backend/access/rmgrdesc/nbtdesc.c | 8 -
src/backend/utils/sort/tuplesort.c | 13 +-
src/include/access/nbtree.h | 213 +++++++++++---
src/include/access/nbtxlog.h | 35 +--
src/test/regress/expected/btree_index.out | 34 +--
src/test/regress/expected/create_index.out | 13 +-
src/test/regress/expected/dependency.out | 4 +-
src/test/regress/expected/event_trigger.out | 4 +-
src/test/regress/expected/foreign_data.out | 9 +-
src/test/regress/expected/rowsecurity.out | 4 +-
src/test/regress/sql/btree_index.sql | 37 +--
src/test/regress/sql/create_index.sql | 14 +-
src/test/regress/sql/foreign_data.sql | 2 +-
29 files changed, 1619 insertions(+), 559 deletions(-)
On Wed, Mar 20, 2019 at 10:05 AM Peter Geoghegan <pg@bowt.ie> wrote:
Make heap TID a tiebreaker nbtree index column.
I see that this has caused SELinux test failures on rhinoceros (the
ddl test fails). It looks like the output order is affected by the
implementation details of nbtree, likely for some system catalog
index. This is something that I've had to deal with in other places
(with a lot of help from Tom).
It's not easy for me to set up SELinux to fix the issue. Is there
somebody comfortable with that area that could confirm I have it
right, and provide me with the actual test output? Or push a fix
themselves?
Thanks
--
Peter Geoghegan
Peter Geoghegan <pg@bowt.ie> writes:
On Wed, Mar 20, 2019 at 10:05 AM Peter Geoghegan <pg@bowt.ie> wrote:
Make heap TID a tiebreaker nbtree index column.
I see that this has caused SELinux test failures on rhinoceros (the
ddl test fails). It looks like the output order is affected by the
implementation details of nbtree, likely for some system catalog
index. This is something that I've had to deal with in other places
(with a lot of help from Tom).
The diffs all are related to the order of operations in a DROP OWNED BY
command, so I think blaming SELinux is just blaming the messenger.
This comes down to the point that we didn't do anything to ensure
drop order stability in shdepend-driven drops. Maybe we need to be
honest about that. Or do you have reason to think that your changes
will result in stability in that drop order anyway? If so, why?
regards, tom lane
Hi,
On 2019-03-20 11:00:06 -0700, Peter Geoghegan wrote:
On Wed, Mar 20, 2019 at 10:05 AM Peter Geoghegan <pg@bowt.ie> wrote:
Make heap TID a tiebreaker nbtree index column.
I see that this has caused SELinux test failures on rhinoceros (the
ddl test fails). It looks like the output order is affected by the
implementation details of nbtree, likely for some system catalog
index. This is something that I've had to deal with in other places
(with a lot of help from Tom).It's not easy for me to set up SELinux to fix the issue. Is there
somebody comfortable with that area that could confirm I have it
right, and provide me with the actual test output? Or push a fix
themselves?
FWIW, I just fix up the tests using the regression output from
rhinoceros when that happens. Sometimes takes more than a single round,
but it builds frequently enough...
Greetings,
Andres Freund
On Wed, Mar 20, 2019 at 11:08 AM Tom Lane <tgl@sss.pgh.pa.us> wrote:
The diffs all are related to the order of operations in a DROP OWNED BY
command, so I think blaming SELinux is just blaming the messenger.
This comes down to the point that we didn't do anything to ensure
drop order stability in shdepend-driven drops. Maybe we need to be
honest about that.
You can certainly make that argument. However, we still wouldn't make
broad guarantees about test stability that ensure that this general
category of flappiness goes away forever (IIRC the role stuff still
has the odd problem). I suppose that you could scope the guarantees as
being about pg_depend and pg_shdepend, but that seems arbitrary to me.
Your work on test stability probably eliminated 98% of the problems.
It's still early, but the buildfarm is mostly fine.
Or do you have reason to think that your changes
will result in stability in that drop order anyway? If so, why?
I strongly suspect that my changes will leave the output about as
stable as before, or will slightly improve matters. Duplicates are now
in ascending order, as opposed to very close to descending order. I
think that it would be fine to rely on the new output ordering, even
though it theoretically isn't any more stable.
--
Peter Geoghegan
On Wed, Mar 20, 2019 at 11:09 AM Andres Freund <andres@anarazel.de> wrote:
FWIW, I just fix up the tests using the regression output from
rhinoceros when that happens. Sometimes takes more than a single round,
but it builds frequently enough...
I'll give that a go, provided Tom is okay with it.
--
Peter Geoghegan
On Wed, Mar 20, 2019 at 11:30 AM Peter Geoghegan <pg@bowt.ie> wrote:
Your work on test stability probably eliminated 98% of the problems.
It's still early, but the buildfarm is mostly fine.
batfish just had a similar failure, this time in foreign_data -- two
lines of "DETAIL" output appear in opposite-of-expected order.
Obviously that's unstable in a way that it wasn't before now, since
every other animal doesn't have that problem.
--
Peter Geoghegan
Peter Geoghegan <pg@bowt.ie> writes:
On Wed, Mar 20, 2019 at 11:30 AM Peter Geoghegan <pg@bowt.ie> wrote:
Your work on test stability probably eliminated 98% of the problems.
It's still early, but the buildfarm is mostly fine.
batfish just had a similar failure, this time in foreign_data -- two
lines of "DETAIL" output appear in opposite-of-expected order.
Obviously that's unstable in a way that it wasn't before now, since
every other animal doesn't have that problem.
Yeah. My opinion is that we should just qsort the list of targets
during DROP OWNED and be done with this. I'll post a patch shortly.
In the meantime, would you mind cleaning this up:
nbtxlog.c: In function 'btree_xlog_split':
nbtxlog.c:269: warning: 'newitem' may be used uninitialized in this function
nbtxlog.c:269: note: 'newitem' was declared here
nbtxlog.c:271: warning: 'newitemsz' may be used uninitialized in this function
nbtxlog.c:271: note: 'newitemsz' was declared here
regards, tom lane
On Wed, Mar 20, 2019 at 1:46 PM Tom Lane <tgl@sss.pgh.pa.us> wrote:
In the meantime, would you mind cleaning this up:
nbtxlog.c: In function 'btree_xlog_split':
nbtxlog.c:269: warning: 'newitem' may be used uninitialized in this function
nbtxlog.c:269: note: 'newitem' was declared here
nbtxlog.c:271: warning: 'newitemsz' may be used uninitialized in this function
nbtxlog.c:271: note: 'newitemsz' was declared here
Sure. Will do that one next.
--
Peter Geoghegan
On Wed, Mar 20, 2019 at 1:46 PM Tom Lane <tgl@sss.pgh.pa.us> wrote:
Yeah. My opinion is that we should just qsort the list of targets
during DROP OWNED and be done with this. I'll post a patch shortly.
Sounds good.
Barring any objections, I will get the buildfarm completely green
again shortly by adjusting the output, rather than waiting for your
patch. Whether or not the verbosity hack can be ripped out can be
considered later, in a separate pass.
--
Peter Geoghegan
I wrote:
Yeah. My opinion is that we should just qsort the list of targets
during DROP OWNED and be done with this. I'll post a patch shortly.
Here's one way we could do this: add a flag to performMultipleDeletions
to invoke the sort. A small problem with it is that if we sort the
ObjectAddresses in-place as this does, we really oughta remove the
"const" from that argument. (I believe compilers would probably not
realize we were cheating if we didn't, but it'd still be cheating.)
That doesn't affect any existing callers, but in future it might
prevent const-ifying something or other. Another way we could handle
this is to make dependency.c expose a separate function
"void sortObjectAddresses(ObjectAddresses *objects)", and then have
callers call that as a separate action. Not sure which I like better
... any opinions?
A preliminary check-world run finds no places where the output changes,
but I've not tried this with SELinux yet.
regards, tom lane
Attachments:
sort-objects-during-drop-owned-1.patchtext/x-diff; charset=us-ascii; name=sort-objects-during-drop-owned-1.patchDownload+23-4
I wrote:
A preliminary check-world run finds no places where the output changes,
but I've not tried this with SELinux yet.
After trying it (against yesterday's sources) on my SELinux-capable
machine, I see no evidence that we need any output ordering changes
at all if we go this route. This is probably unsurprising considering
that the old btree code used to provide mostly-reverse-insertion-order
scan order.
regards, tom lane
On Wed, Mar 20, 2019 at 2:44 PM Tom Lane <tgl@sss.pgh.pa.us> wrote:
After trying it (against yesterday's sources) on my SELinux-capable
machine, I see no evidence that we need any output ordering changes
at all if we go this route. This is probably unsurprising considering
that the old btree code used to provide mostly-reverse-insertion-order
scan order.
That's good. I'm trying to fix it by hand right now, in the way that
Andres suggested. It is both tedious and error-prone.
--
Peter Geoghegan
Peter Geoghegan <pg@bowt.ie> writes:
On Wed, Mar 20, 2019 at 2:44 PM Tom Lane <tgl@sss.pgh.pa.us> wrote:
After trying it (against yesterday's sources) on my SELinux-capable
machine, I see no evidence that we need any output ordering changes
at all if we go this route. This is probably unsurprising considering
that the old btree code used to provide mostly-reverse-insertion-order
scan order.
That's good. I'm trying to fix it by hand right now, in the way that
Andres suggested. It is both tedious and error-prone.
Yeah. Don't do that.
After further thought I think I'll go with the alternate solution
(separate sortObjectAddresses function) as that could possibly have
other uses, and removing the "const" from performMultipleDeletions
seems a bit bletcherous. Will push a fix in a few minutes.
regards, tom lane
I wrote:
Will push a fix in a few minutes.
And done. Should be possible to revert 7d3bf73ac, if you wish.
regards, tom lane
On Wed, Mar 20, 2019 at 3:08 PM Tom Lane <tgl@sss.pgh.pa.us> wrote:
And done. Should be possible to revert 7d3bf73ac, if you wish.
Will do.
Thanks!
--
Peter Geoghegan
On Wed, Mar 20, 2019 at 3:11 PM Peter Geoghegan <pg@bowt.ie> wrote:
On Wed, Mar 20, 2019 at 3:08 PM Tom Lane <tgl@sss.pgh.pa.us> wrote:
And done. Should be possible to revert 7d3bf73ac, if you wish.
Will do.
Actually, I'm not sure why it would be fine to revert 7d3bf73ac now.
Might the problem actually be the order in which OIDs are originally
assigned, or something like that?
I neglected to test SEPostgres myself, but if I did I think that I
would have included the changes, avoiding the problem on rhinoceros.
IOW, I believe that it wasn't a test flappiness issue, whereas the
problem on batfish clearly is.
--
Peter Geoghegan
Peter Geoghegan <pg@bowt.ie> writes:
On Wed, Mar 20, 2019 at 3:11 PM Peter Geoghegan <pg@bowt.ie> wrote:
On Wed, Mar 20, 2019 at 3:08 PM Tom Lane <tgl@sss.pgh.pa.us> wrote:
And done. Should be possible to revert 7d3bf73ac, if you wish.
Actually, I'm not sure why it would be fine to revert 7d3bf73ac now.
Might the problem actually be the order in which OIDs are originally
assigned, or something like that?
No, because then things would have been unstable before, no?
I actually think that we should remove most or all of the
cascade-drop-hiding hacks that are in the regression tests now,
not only that one. They should not be necessary any more, and
they might be hiding things we need to know about, now or in
the future. But I haven't got round to it.
regards, tom lane
On Wed, Mar 20, 2019 at 8:17 PM Tom Lane <tgl@sss.pgh.pa.us> wrote:
Actually, I'm not sure why it would be fine to revert 7d3bf73ac now.
Might the problem actually be the order in which OIDs are originally
assigned, or something like that?No, because then things would have been unstable before, no?
Perhaps. The cost of being wrong here is trivial anyway. I have
reverted 7d3bf73ac based on the assumption that it's now unnecessary.
I actually think that we should remove most or all of the
cascade-drop-hiding hacks that are in the regression tests now,
not only that one. They should not be necessary any more, and
they might be hiding things we need to know about, now or in
the future. But I haven't got round to it.
Seems like a useful goal.
--
Peter Geoghegan
Peter Geoghegan <pg@bowt.ie> writes:
On Wed, Mar 20, 2019 at 8:17 PM Tom Lane <tgl@sss.pgh.pa.us> wrote:
Actually, I'm not sure why it would be fine to revert 7d3bf73ac now.
Might the problem actually be the order in which OIDs are originally
assigned, or something like that?
No, because then things would have been unstable before, no?
Perhaps. The cost of being wrong here is trivial anyway. I have
reverted 7d3bf73ac based on the assumption that it's now unnecessary.
Apparently, that case is indeed unstable, cf
https://buildfarm.postgresql.org/cgi-bin/show_log.pl?nm=fulmar&dt=2019-03-22%2016%3A15%3A14
I picked up on that because I've also seen it happen on my own
devel machine today, but just once --- I then tried to reproduce it,
but couldn't in several dozen tries.
I'm fairly baffled as to why the output order would be unstable
given the sort, and even more as to why the instability didn't
emerge before. Any thoughts?
regards, tom lane