Resurrecting per-page cleaner for btree

This is a revised patch originated by Junji TERAMOTO for HEAD.
[BTree vacuum before page splitting]
http://archives.postgresql.org/pgsql-patches/2006-01/msg00301.php

I think we can resurrect his idea because we will scan btree pages
at-atime now; the missing-restarting-point problem went away.

Have I missed something? Comments welcome.

Regards,
---
ITAGAKI Takahiro
NTT Open Source Software Center

On Thu, 2006-07-13 at 10:49 +0900, ITAGAKI Takahiro wrote:

This is a revised patch originated by Junji TERAMOTO for HEAD.
[BTree vacuum before page splitting]
http://archives.postgresql.org/pgsql-patches/2006-01/msg00301.php

I think we can resurrect his idea because we will scan btree pages
at-atime now; the missing-restarting-point problem went away.

Have I missed something? Comments welcome.

The new locking system does allow this now.

So this is an option for us, AFAICS.

--
Simon Riggs
EnterpriseDB http://www.enterprisedb.com

On Wed, Jul 12, 2006 at 03:59:01PM +0900, ITAGAKI Takahiro wrote:

Hi Hackers,

Can we resurrect the patch proposed by Junji TERAMOTO?
It removes unnecessary items before btree pages split.
http://archives.postgresql.org/pgsql-patches/2006-01/msg00301.php

There was a problem in the patch when we restarted scans from deleted tuples.
But now we scan pages at-a-time, so the problem is resolved, isn't it?
http://archives.postgresql.org/pgsql-patches/2006-05/msg00008.php

I think this feature is independent from the SITC project and useful for
heavily-updated indexes. If it is worthwhile, I'll revise the patch to
catch up on HEAD.

Tom's comment about the patch needing better comments still holds. If
nothing else, do the best you can with the comments in English and
someone else can clean the grammar up.

It's also not clear to me if Tom's comment about not deleting LP_DELETE
tuples at-will is still valid or not.
--
Jim C. Nasby, Sr. Engineering Consultant jnasby@pervasive.com
Pervasive Software http://pervasive.com work: 512-231-6117
vcard: http://jim.nasby.net/pervasive.vcf cell: 512-569-9461

ITAGAKI Takahiro <itagaki.takahiro@oss.ntt.co.jp> writes:

This is a revised patch originated by Junji TERAMOTO for HEAD.
[BTree vacuum before page splitting]
http://archives.postgresql.org/pgsql-patches/2006-01/msg00301.php
I think we can resurrect his idea because we will scan btree pages
at-atime now; the missing-restarting-point problem went away.
Have I missed something? Comments welcome.

I think the only serious objection to this would be that it'd mean that
tuples that should have an index entry might not have one. The current
form of VACUUM does not care, but people keep raising the idea of doing
"retail" vacuuming that operates by looking up index entries explicitly.
You could certainly make a retail vacuumer do nothing if it fails to
find the expected index entry, but ISTM that'd be a rather serious loss
of consistency checking --- you could not tell the someone-already-
deleted-it case apart from a bug in the vacuumer's index value
computation or lookup.

Personally I don't think retail vacuuming in that form will ever fly
anyway, so I have no problem with installing the proposed patch,
but I thought I'd better throw this comment out to see if anyone
thinks it's a big deal.

regards, tom lane

On Mon, 24 Jul 2006, Tom Lane wrote:

Personally I don't think retail vacuuming in that form will ever fly
anyway, so I have no problem with installing the proposed patch,
but I thought I'd better throw this comment out to see if anyone
thinks it's a big deal.

My feeling is that retail vacuuming would be useful some day. But it's
certainly not going to be there in 8.2 so I have no objection with the
patch. It's a fairly localized change; it can easily be reverted later if
necessary.

- Heikki

Tom Lane wrote:

ITAGAKI Takahiro <itagaki.takahiro@oss.ntt.co.jp> writes:

This is a revised patch originated by Junji TERAMOTO for HEAD.
[BTree vacuum before page splitting]
http://archives.postgresql.org/pgsql-patches/2006-01/msg00301.php
I think we can resurrect his idea because we will scan btree pages
at-atime now; the missing-restarting-point problem went away.
Have I missed something? Comments welcome.

I think the only serious objection to this would be that it'd mean that
tuples that should have an index entry might not have one. The current
form of VACUUM does not care, but people keep raising the idea of doing
"retail" vacuuming that operates by looking up index entries explicitly.
You could certainly make a retail vacuumer do nothing if it fails to
find the expected index entry, but ISTM that'd be a rather serious loss
of consistency checking --- you could not tell the someone-already-
deleted-it case apart from a bug in the vacuumer's index value
computation or lookup.

Personally I don't think retail vacuuming in that form will ever fly
anyway, so I have no problem with installing the proposed patch,
but I thought I'd better throw this comment out to see if anyone
thinks it's a big deal.

Agreed. Reverse lookup of index entries will always be too slow.

--
Bruce Momjian bruce@momjian.us
EnterpriseDB http://www.enterprisedb.com

+ If your life is a hard drive, Christ can be your backup. +

Your patch has been added to the PostgreSQL unapplied patches list at:

http://momjian.postgresql.org/cgi-bin/pgpatches

It will be applied as soon as one of the PostgreSQL committers reviews
and approves it.

---------------------------------------------------------------------------

ITAGAKI Takahiro wrote:

This is a revised patch originated by Junji TERAMOTO for HEAD.
[BTree vacuum before page splitting]
http://archives.postgresql.org/pgsql-patches/2006-01/msg00301.php

I think we can resurrect his idea because we will scan btree pages
at-atime now; the missing-restarting-point problem went away.

Have I missed something? Comments welcome.

Regards,
---
ITAGAKI Takahiro
NTT Open Source Software Center

[ Attachment, skipping... ]

---------------------------(end of broadcast)---------------------------
TIP 2: Don't 'kill -9' the postmaster

--
Bruce Momjian bruce@momjian.us
EnterpriseDB http://www.enterprisedb.com

+ If your life is a hard drive, Christ can be your backup. +

Tom Lane <tgl@sss.pgh.pa.us> wrote:

I think the only serious objection to this would be that it'd mean that
tuples that should have an index entry might not have one.

This can occurs when we do REINDEX after DELETE, because dead tuples are
excluded on REINDEX. So we cannot guarantee that all heap tuples have
corresponding index entries. Vacuumers should not suppose their existence.

But I see the change is confusable, too.
I'll add more comments.

# CREATE TABLE test (i int);
# INSERT INTO test SELECT generate_series(1, 1000);
# CREATE INDEX test_idx ON test (i);
# DELETE FROM test WHERE i % 10 = 0;
# REINDEX INDEX test_idx;

# SELECT tuple_count, dead_tuple_count FROM pgstattuple('test');
tuple_count | dead_tuple_count
-------------+------------------
900 | 100

# SELECT tuple_count, dead_tuple_count FROM pgstattuple('test_idx');
tuple_count | dead_tuple_count
-------------+------------------
900 | 0

Regards,
---
ITAGAKI Takahiro
NTT Open Source Software Center

ITAGAKI Takahiro <itagaki.takahiro@oss.ntt.co.jp> writes:

Tom Lane <tgl@sss.pgh.pa.us> wrote:

I think the only serious objection to this would be that it'd mean that
tuples that should have an index entry might not have one.

This can occurs when we do REINDEX after DELETE, because dead tuples are
excluded on REINDEX.

Good point. So we already have that problem anyway ...

regards, tom lane

ITAGAKI Takahiro <itagaki.takahiro@oss.ntt.co.jp> writes:

I think we can resurrect his idea because we will scan btree pages
at-atime now; the missing-restarting-point problem went away.

Have I missed something? Comments welcome.

I was thinking for awhile just now that this would break the interlock
that guarantees VACUUM can't delete a heap tuple that an indexscanning
process is about to visit. After further thought, it doesn't, but it's
non-obvious. I've added the attached commentary to nbtree/README:

On-the-fly deletion of index tuples
-----------------------------------

If a process visits a heap tuple and finds that it's dead and removable
(ie, dead to all open transactions, not only that process), then we can
return to the index and mark the corresponding index entry "known dead",
allowing subsequent index scans to skip visiting the heap tuple. The
"known dead" marking uses the LP_DELETE bit in ItemIds. This is currently
only done in plain indexscans, not bitmap scans, because only plain scans
visit the heap and index "in sync" and so there's not a convenient way
to do it for bitmap scans.

Once an index tuple has been marked LP_DELETE it can actually be removed
from the index immediately; since index scans only stop "between" pages,
no scan can lose its place from such a deletion. We separate the steps
because we allow LP_DELETE to be set with only a share lock (it's exactly
like a hint bit for a heap tuple), but physically removing tuples requires
exclusive lock. In the current code we try to remove LP_DELETE tuples when
we are otherwise faced with having to split a page to do an insertion (and
hence have exclusive lock on it already).

This leaves the index in a state where it has no entry for a dead tuple
that still exists in the heap. This is not a problem for the current
implementation of VACUUM, but it could be a problem for anything that
explicitly tries to find index entries for dead tuples. (However, the
same situation is created by REINDEX, since it doesn't enter dead
tuples into the index.)

It's sufficient to have an exclusive lock on the index page, not a
super-exclusive lock, to do deletion of LP_DELETE items. It might seem
that this breaks the interlock between VACUUM and indexscans, but that is
not so: as long as an indexscanning process has a pin on the page where
the index item used to be, VACUUM cannot complete its btbulkdelete scan
and so cannot remove the heap tuple. This is another reason why
btbulkdelete has to get super-exclusive lock on every leaf page, not only
the ones where it actually sees items to delete.

regards, tom lane

ITAGAKI Takahiro <itagaki.takahiro@oss.ntt.co.jp> writes:

This is a revised patch originated by Junji TERAMOTO for HEAD.
[BTree vacuum before page splitting]
http://archives.postgresql.org/pgsql-patches/2006-01/msg00301.php
I think we can resurrect his idea because we will scan btree pages
at-atime now; the missing-restarting-point problem went away.

I've applied this but I'm now having some second thoughts about it,
because I'm seeing an actual *decrease* in pgbench numbers from the
immediately prior CVS HEAD code. Using
pgbench -i -s 10 bench
pgbench -c 10 -t 1000 bench (repeat this half a dozen times)
with fsync off but all other settings factory-stock, what I'm seeing
is that the first run looks really good but subsequent runs tail off in
spectacular fashion :-( Pre-patch there was only minor degradation in
successive runs.

What I think is happening is that because pgbench depends so heavily on
updating existing records, we get into a state where an index page is
about full and there's one dead tuple on it, and then for each insertion
we have

* check for uniqueness marks one more tuple dead (the
next-to-last version of the tuple)
* newly added code removes one tuple and does a write
* now there's enough room to insert one tuple
* lather, rinse, repeat, never splitting the page.

The problem is that we've traded splitting a page every few hundred
inserts for doing a PageIndexMultiDelete, and emitting an extra WAL
record, on *every* insert. This is not good.

Had you done any performance testing on this patch, and if so what
tests did you use? I'm a bit hesitant to try to fix it on the basis
of pgbench results alone.

One possible fix that comes to mind is to only perform the cleanup
if we are able to remove more than one dead tuple (perhaps about 10
would be good). Or do the deletion anyway, but then go ahead and
split the page unless X amount of space has been freed (where X is
more than just barely enough for the incoming tuple).

After all the thought we've put into this, it seems a shame to
just abandon it :-(. But it definitely needs more tweaking.

regards, tom lane

The attached patch requires the new row to fit, and 10% to be free on
the page. Would someone test that?

---------------------------------------------------------------------------

Tom Lane wrote:

ITAGAKI Takahiro <itagaki.takahiro@oss.ntt.co.jp> writes:

This is a revised patch originated by Junji TERAMOTO for HEAD.
[BTree vacuum before page splitting]
http://archives.postgresql.org/pgsql-patches/2006-01/msg00301.php
I think we can resurrect his idea because we will scan btree pages
at-atime now; the missing-restarting-point problem went away.

I've applied this but I'm now having some second thoughts about it,
because I'm seeing an actual *decrease* in pgbench numbers from the
immediately prior CVS HEAD code. Using
pgbench -i -s 10 bench
pgbench -c 10 -t 1000 bench (repeat this half a dozen times)
with fsync off but all other settings factory-stock, what I'm seeing
is that the first run looks really good but subsequent runs tail off in
spectacular fashion :-( Pre-patch there was only minor degradation in
successive runs.

What I think is happening is that because pgbench depends so heavily on
updating existing records, we get into a state where an index page is
about full and there's one dead tuple on it, and then for each insertion
we have

* check for uniqueness marks one more tuple dead (the
next-to-last version of the tuple)
* newly added code removes one tuple and does a write
* now there's enough room to insert one tuple
* lather, rinse, repeat, never splitting the page.

The problem is that we've traded splitting a page every few hundred
inserts for doing a PageIndexMultiDelete, and emitting an extra WAL
record, on *every* insert. This is not good.

Had you done any performance testing on this patch, and if so what
tests did you use? I'm a bit hesitant to try to fix it on the basis
of pgbench results alone.

One possible fix that comes to mind is to only perform the cleanup
if we are able to remove more than one dead tuple (perhaps about 10
would be good). Or do the deletion anyway, but then go ahead and
split the page unless X amount of space has been freed (where X is
more than just barely enough for the incoming tuple).

After all the thought we've put into this, it seems a shame to
just abandon it :-(. But it definitely needs more tweaking.

regards, tom lane

---------------------------(end of broadcast)---------------------------
TIP 4: Have you searched our list archives?

http://archives.postgresql.org

--
Bruce Momjian bruce@momjian.us
EnterpriseDB http://www.enterprisedb.com

+ If your life is a hard drive, Christ can be your backup. +

Tom, I ran your tests with fsync off (as you did), and saw numbers
bouncing between 400-700 tps without my patch, and sticking at 700 tps
with my patch.

---------------------------------------------------------------------------

Bruce Momjian wrote:

The attached patch requires the new row to fit, and 10% to be free on
the page. Would someone test that?

---------------------------------------------------------------------------

Tom Lane wrote:

ITAGAKI Takahiro <itagaki.takahiro@oss.ntt.co.jp> writes:

This is a revised patch originated by Junji TERAMOTO for HEAD.
[BTree vacuum before page splitting]
http://archives.postgresql.org/pgsql-patches/2006-01/msg00301.php
I think we can resurrect his idea because we will scan btree pages
at-atime now; the missing-restarting-point problem went away.

I've applied this but I'm now having some second thoughts about it,
because I'm seeing an actual *decrease* in pgbench numbers from the
immediately prior CVS HEAD code. Using
pgbench -i -s 10 bench
pgbench -c 10 -t 1000 bench (repeat this half a dozen times)
with fsync off but all other settings factory-stock, what I'm seeing
is that the first run looks really good but subsequent runs tail off in
spectacular fashion :-( Pre-patch there was only minor degradation in
successive runs.

What I think is happening is that because pgbench depends so heavily on
updating existing records, we get into a state where an index page is
about full and there's one dead tuple on it, and then for each insertion
we have

* check for uniqueness marks one more tuple dead (the
next-to-last version of the tuple)
* newly added code removes one tuple and does a write
* now there's enough room to insert one tuple
* lather, rinse, repeat, never splitting the page.

The problem is that we've traded splitting a page every few hundred
inserts for doing a PageIndexMultiDelete, and emitting an extra WAL
record, on *every* insert. This is not good.

Had you done any performance testing on this patch, and if so what
tests did you use? I'm a bit hesitant to try to fix it on the basis
of pgbench results alone.

One possible fix that comes to mind is to only perform the cleanup
if we are able to remove more than one dead tuple (perhaps about 10
would be good). Or do the deletion anyway, but then go ahead and
split the page unless X amount of space has been freed (where X is
more than just barely enough for the incoming tuple).

After all the thought we've put into this, it seems a shame to
just abandon it :-(. But it definitely needs more tweaking.

regards, tom lane

---------------------------(end of broadcast)---------------------------
TIP 4: Have you searched our list archives?

http://archives.postgresql.org

--
Bruce Momjian bruce@momjian.us
EnterpriseDB http://www.enterprisedb.com

+ If your life is a hard drive, Christ can be your backup. +

---------------------------(end of broadcast)---------------------------
TIP 2: Don't 'kill -9' the postmaster

--
Bruce Momjian bruce@momjian.us
EnterpriseDB http://www.enterprisedb.com

+ If your life is a hard drive, Christ can be your backup. +

Tom Lane <tgl@sss.pgh.pa.us> wrote:

ITAGAKI Takahiro <itagaki.takahiro@oss.ntt.co.jp> writes:
I've applied this but I'm now having some second thoughts about it,
because I'm seeing an actual *decrease* in pgbench numbers from the
immediately prior CVS HEAD code.

Had you done any performance testing on this patch, and if so what
tests did you use? I'm a bit hesitant to try to fix it on the basis
of pgbench results alone.

Thank you for applying and adding documentation.
But hmm... I tested on DBT-2 and pgbench, and the patch worked well on both.
I used disks with battery backup for WAL and enabled writeback cache, so the
extra WAL records might be of no significance.
On DBT-2, the bottleneck was completely the data disks. Cache usage was
important there, so avoiding splitting was useful for saving momory.
On pgbench, full dataset was cached in memory, so the bottleneck was CPUs.
Especially cleanup for branches_pkey was effective because it was frequently
updated and had many LP_DELETE'd tuples. Degradation was eased on my machine.

The problem is that we've traded splitting a page every few hundred
inserts for doing a PageIndexMultiDelete, and emitting an extra WAL
record, on *every* insert. This is not good.

I suspect PageIndexMultiDelete() consumes CPU. If there are one or two
dead tuples, PageIndexTupleDelete() is called and memmove(4KB average)
and adjustment of the linepointer-offsets are performed everytime.
I think this is a heavy operation. But if the size of most upper index
entry is same with the dead tuple, we can only move the upper to the hole
and avoid to modify all tuples. Is this change acceptable?

Regards,
---
ITAGAKI Takahiro
NTT Open Source Software Center

ITAGAKI Takahiro <itagaki.takahiro@oss.ntt.co.jp> writes:

Tom Lane <tgl@sss.pgh.pa.us> wrote:

The problem is that we've traded splitting a page every few hundred
inserts for doing a PageIndexMultiDelete, and emitting an extra WAL
record, on *every* insert. This is not good.

I suspect PageIndexMultiDelete() consumes CPU.

That's part of the problem, but only part: the extra WAL record is
expensive too.

If there are one or two
dead tuples, PageIndexTupleDelete() is called and memmove(4KB average)
and adjustment of the linepointer-offsets are performed everytime.
I think this is a heavy operation. But if the size of most upper index
entry is same with the dead tuple, we can only move the upper to the hole
and avoid to modify all tuples. Is this change acceptable?

I'm inclined to think that this is too special-purpose to be a good
solution. It will help pgbench because that test uses only integer
keys, but it won't help for any variable-width datatype. In any case
we'd still have the WAL overhead...

regards, tom lane

Tom Lane <tgl@sss.pgh.pa.us> writes:

ITAGAKI Takahiro <itagaki.takahiro@oss.ntt.co.jp> writes:

This is a revised patch originated by Junji TERAMOTO for HEAD.
[BTree vacuum before page splitting]
http://archives.postgresql.org/pgsql-patches/2006-01/msg00301.php
I think we can resurrect his idea because we will scan btree pages
at-atime now; the missing-restarting-point problem went away.
Have I missed something? Comments welcome.

I think the only serious objection to this would be that it'd mean that
tuples that should have an index entry might not have one. The current
form of VACUUM does not care, but people keep raising the idea of doing
"retail" vacuuming that operates by looking up index entries explicitly.
You could certainly make a retail vacuumer do nothing if it fails to
find the expected index entry, but ISTM that'd be a rather serious loss
of consistency checking --- you could not tell the someone-already-
deleted-it case apart from a bug in the vacuumer's index value
computation or lookup.

Well you already have that case anyways due to online index builds. (If a
vacuum gets in between the two transactions.) I suppose you could go and check
whether the pg_index entry for the index indicates that it's valid already but
that's not something anyone has to be looking for currently.

Personally I don't think retail vacuuming in that form will ever fly
anyway, so I have no problem with installing the proposed patch,
but I thought I'd better throw this comment out to see if anyone
thinks it's a big deal.

Well it's not like the existing vacuum checks for this. It's not even
convenient to check for it in the current vacuum architecture. It would have
to maintain the list of expired htids that haven't been found yet in the
bulkdelete and see if there are any left when it's done.

--
Gregory Stark
EnterpriseDB http://www.enterprisedb.com

Gregory Stark <gsstark@mit.edu> writes:

... Well it's not like the existing vacuum checks for this.

Right, that's exactly why the patch works at all. But the point here is
that the existing vacuum does not rely on re-computing index keys; all
it cares about is matching TIDs. The retail-vacuum idea depends on the
assumption that you can look at the tuple and re-compute the same index
keys that you computed the first time; which is an assumption much
shakier than the assumption that TID comparison works. (In fact, it's
trivial to see how user-defined functions that are mislabeled immutable
could make this fail.) So retail vacuum without any cross-check that
you got all the index tuples is a scary proposition IMHO.

regards, tom lane

[snip] (In fact, it's
trivial to see how user-defined functions that are mislabeled immutable
could make this fail.) So retail vacuum without any cross-check that
you got all the index tuples is a scary proposition IMHO.

Wouldn't work to restrict that kind of vacuum to only tables which have
no indexes using user defined functions ? That would mean a very small
restriction I guess, probably 99.9% of the indexes won't use user
defined functions...

I actually wonder if such a vacuum would be useful for my scenario,
where I have some pretty big tables, and update a relatively small
percentage of it. Would it be faster to run such a vacuum against the
current one ?
One example would be a ~100 million table where I have 1-4 million
updates per day. Could I run vacuum multiple times a day for this table
and expect that individual runs are relatively fast ?

Cheers,
Csaba.

Csaba Nagy <nagy@ecircle-ag.com> writes:

[snip] (In fact, it's
trivial to see how user-defined functions that are mislabeled immutable
could make this fail.) So retail vacuum without any cross-check that
you got all the index tuples is a scary proposition IMHO.

Wouldn't work to restrict that kind of vacuum to only tables which have
no indexes using user defined functions ?

Of course, we never have bugs in PG core. Nope, doesn't happen ...

I actually wonder if such a vacuum would be useful for my scenario,
where I have some pretty big tables, and update a relatively small
percentage of it. Would it be faster to run such a vacuum against the
current one ?

So far, the case hasn't been made for retail vacuum even ignoring the
not-so-immutable-function risk.

regards, tom lane