> Vadim, can you remind me what UNDO is used for?

Ok, last reminder -:))

On transaction abort, read WAL records and undo (rollback)
changes made in storage. Would allow:

1. Reclaim space allocated by aborted transactions.
2. Implement SAVEPOINTs.
   Just to remind -:) - in the event of error discovered by server
   - duplicate key, deadlock, command mistyping, etc, - transaction
   will be rolled back to the nearest implicit savepoint setted
   just before query execution; - or transaction can be aborted by
   ROLLBACK TO <savepoint_name> command to some explicit savepoint
   setted by user. Transaction rolled back to savepoint may be continued.
3. Reuse transaction IDs on postmaster restart.
4. Split pg_log into small files with ability to remove old ones (which
   do not hold statuses for any running transactions).

Vadim

Fri, 18 May 2001 18:10:10 -0700
"Mikheev, Vadim" <vmikheev@SECTORBASE.COM>
RE: Plans for solving the VACUUM problem
"Mikheev, Vadim" <vmikheev@SECTORBASE.COM> writes:
>> Vadim, can you remind me what UNDO is used for?
> Ok, last reminder -:))

> On transaction abort, read WAL records and undo (rollback)
> changes made in storage. Would allow:

> 1. Reclaim space allocated by aborted transactions.
> 2. Implement SAVEPOINTs.
>    Just to remind -:) - in the event of error discovered by server
>    - duplicate key, deadlock, command mistyping, etc, - transaction
>    will be rolled back to the nearest implicit savepoint setted
>    just before query execution; - or transaction can be aborted by
>    ROLLBACK TO <savepoint_name> command to some explicit savepoint
>    setted by user. Transaction rolled back to savepoint may be continued.
> 3. Reuse transaction IDs on postmaster restart.
> 4. Split pg_log into small files with ability to remove old ones (which
>    do not hold statuses for any running transactions).

Hm.  On the other hand, relying on WAL for undo means you cannot drop
old WAL segments that contain records for any open transaction.  We've
already seen several complaints that the WAL logs grow unmanageably huge
when there is a long-running transaction, and I think we'll see a lot
more.

It would be nicer if we could drop WAL records after a checkpoint or two,
even in the presence of long-running transactions.  We could do that if
we were only relying on them for crash recovery and not for UNDO.

Looking at the advantages:

1. Space reclamation via UNDO doesn't excite me a whole lot, if we can
make lightweight VACUUM work well.  (I definitely don't like the idea
that after a very long transaction fails and aborts, I'd have to wait
another very long time for UNDO to do its thing before I could get on
with my work.  Would much rather have the space reclamation happen in
background.)

2. SAVEPOINTs would be awfully nice to have, I agree.

3. Reusing xact IDs would be nice, but there's an answer with a lot less
impact on the system: go to 8-byte xact IDs.  Having to shut down the
postmaster when you approach the 4Gb transaction mark isn't going to
impress people who want a 24x7 commitment, anyway.

4. Recycling pg_log would be nice too, but we've already discussed other
hacks that might allow pg_log to be kept finite without depending on
UNDO (or requiring postmaster restarts, IIRC).

I'm sort of thinking that undoing back to a savepoint is the only real
usefulness of WAL-based UNDO.  Is it practical to preserve the WAL log
just back to the last savepoint in each xact, not the whole xact?

Another thought: do we need WAL UNDO at all to implement savepoints?
Is there some way we could do them like nested transactions, wherein
each savepoint-to-savepoint segment is given its own transaction number?
Committing multiple xact IDs at once might be a little tricky, but it
seems like a narrow, soluble problem.  Implementing UNDO without
creating lots of performance issues looks a lot harder.

			regards, tom lane

Fri, 18 May 2001 21:37:37 -0400
Tom Lane <tgl@sss.pgh.pa.us>
Re: Plans for solving the VACUUM problem 
On Fri, May 18, 2001 at 06:10:10PM -0700, Mikheev, Vadim wrote:
> > Vadim, can you remind me what UNDO is used for?
> 
> Ok, last reminder -:))
> 
> On transaction abort, read WAL records and undo (rollback)
> changes made in storage. Would allow:
> 
> 1. Reclaim space allocated by aborted transactions.
> 2. Implement SAVEPOINTs.
>    Just to remind -:) - in the event of error discovered by server
>    - duplicate key, deadlock, command mistyping, etc, - transaction
>    will be rolled back to the nearest implicit savepoint setted
>    just before query execution; - or transaction can be aborted by
>    ROLLBACK TO <savepoint_name> command to some explicit savepoint
>    setted by user. Transaction rolled back to savepoint may be continued.
> 3. Reuse transaction IDs on postmaster restart.
> 4. Split pg_log into small files with ability to remove old ones (which
>    do not hold statuses for any running transactions).

I missed the original discussions; apologies if this has already been
beaten into the ground.  But... mightn't sub-transactions be a 
better-structured way to expose this service?

Nathan Myers
ncm@zembu.com

Fri, 18 May 2001 18:56:25 -0700
ncm@zembu.com (Nathan Myers)
Re: Plans for solving the VACUUM problem
> Another thought: do we need WAL UNDO at all to implement savepoints?
> Is there some way we could do them like nested transactions, wherein
> each savepoint-to-savepoint segment is given its own transaction number?
> Committing multiple xact IDs at once might be a little tricky, but it
> seems like a narrow, soluble problem.  Implementing UNDO without
> creating lots of performance issues looks a lot harder.

I am confused why we can't implement subtransactions as part of our
command counter?  The counter is already 4 bytes long.  Couldn't we
rollback to counter number X-10?

-- 
  Bruce Momjian                        |  http://candle.pha.pa.us
  pgman@candle.pha.pa.us               |  (610) 853-3000
  +  If your life is a hard drive,     |  830 Blythe Avenue
  +  Christ can be your backup.        |  Drexel Hill, Pennsylvania 19026

Fri, 18 May 2001 23:12:41 -0400 (EDT)
Bruce Momjian <pgman@candle.pha.pa.us>
Re: Plans for solving the VACUUM problem
Bruce Momjian <pgman@candle.pha.pa.us> writes:
> I am confused why we can't implement subtransactions as part of our
> command counter?  The counter is already 4 bytes long.  Couldn't we
> rollback to counter number X-10?

That'd work within your own transaction, but not from outside it.
After you commit, how will other backends know which command-counter
values of your transaction to believe, and which not?

			regards, tom lane

Fri, 18 May 2001 23:15:13 -0400
Tom Lane <tgl@sss.pgh.pa.us>
Re: Plans for solving the VACUUM problem 
> Bruce Momjian <pgman@candle.pha.pa.us> writes:
> > I am confused why we can't implement subtransactions as part of our
> > command counter?  The counter is already 4 bytes long.  Couldn't we
> > rollback to counter number X-10?
> 
> That'd work within your own transaction, but not from outside it.
> After you commit, how will other backends know which command-counter
> values of your transaction to believe, and which not?

Seems we would have to store the command counters for the parts of the
transaction that committed, or the ones that were rolled back.  Yuck.

I hate to add UNDO complexity just for subtransactions.

Hey, I have an idea.  Can we do subtransactions as separate transactions
(as Tom mentioned), and put the subtransaction id's in the WAL, so they
an be safely committed/rolledback as a group?

-- 
  Bruce Momjian                        |  http://candle.pha.pa.us
  pgman@candle.pha.pa.us               |  (610) 853-3000
  +  If your life is a hard drive,     |  830 Blythe Avenue
  +  Christ can be your backup.        |  Drexel Hill, Pennsylvania 19026

Fri, 18 May 2001 23:29:55 -0400 (EDT)
Bruce Momjian <pgman@candle.pha.pa.us>
Re: Plans for solving the VACUUM problem
Bruce Momjian <pgman@candle.pha.pa.us> writes:
> Hey, I have an idea.  Can we do subtransactions as separate transactions
> (as Tom mentioned), and put the subtransaction id's in the WAL, so they
> an be safely committed/rolledback as a group?

It's not quite that easy: all the subtransactions have to commit at
*the same time* from the point of view of other xacts, or you have
consistency problems.  So there'd need to be more xact-commit mechanism
than there is now.  Snapshots are also interesting; we couldn't use a
single xact ID per backend to show the open-transaction state.

WAL doesn't really enter into it AFAICS...

			regards, tom lane

Fri, 18 May 2001 23:43:42 -0400
Tom Lane <tgl@sss.pgh.pa.us>
Re: Plans for solving the VACUUM problem 
> Bruce Momjian <pgman@candle.pha.pa.us> writes:
> > Hey, I have an idea.  Can we do subtransactions as separate transactions
> > (as Tom mentioned), and put the subtransaction id's in the WAL, so they
> > an be safely committed/rolledback as a group?
> 
> It's not quite that easy: all the subtransactions have to commit at
> *the same time* from the point of view of other xacts, or you have
> consistency problems.  So there'd need to be more xact-commit mechanism
> than there is now.  Snapshots are also interesting; we couldn't use a
> single xact ID per backend to show the open-transaction state.

Yes, I knew that was going to come up that you have to add a lock to the
pg_log that is only in affect when someone is commiting a transaction
with subtransactions.  Normal transactions get read/sharedlock, while
subtransaction needs exclusive/writelock.

Seems a lot easier than UNDO.  Vadim you mentioned UNDO would allow
space reuse for rolledback transactions, but in most cases the space
reuse is going to be for old copies of committed transactions, right? 
Were you going to use WAL to get free space from old copies too?

Vadim, I think I am missing something.  You mentioned UNDO would be used
for these cases and I don't understand the purpose of adding what would
seem to be a pretty complex capability:

> 1. Reclaim space allocated by aborted transactions.

Is there really a lot to be saved here vs. old tuples of committed
transactions?

> 2. Implement SAVEPOINTs.
>    Just to remind -:) - in the event of error discovered by server
>    - duplicate key, deadlock, command mistyping, etc, - transaction
>    will be rolled back to the nearest implicit savepoint setted
>    just before query execution; - or transaction can be aborted by
>    ROLLBACK TO <savepoint_name> command to some explicit savepoint
>    setted by user. Transaction rolled back to savepoint may be
>    continued.

Discussing, perhaps using multiple transactions.

> 3. Reuse transaction IDs on postmaster restart.

Doesn't seem like a huge win.

> 4. Split pg_log into small files with ability to remove old ones (which
>    do not hold statuses for any running transactions).

That one is interesting.  Seems the only workaround for that would be to
allow a global scan of all databases and tables to set commit flags,
then shrink pg_log and set XID offset as start of file.

-- 
  Bruce Momjian                        |  http://candle.pha.pa.us
  pgman@candle.pha.pa.us               |  (610) 853-3000
  +  If your life is a hard drive,     |  830 Blythe Avenue
  +  Christ can be your backup.        |  Drexel Hill, Pennsylvania 19026

Fri, 18 May 2001 23:57:01 -0400 (EDT)
Bruce Momjian <pgman@candle.pha.pa.us>
Re: Plans for solving the VACUUM problem
> > Bruce Momjian <pgman@candle.pha.pa.us> writes:
> > > Hey, I have an idea.  Can we do subtransactions as separate transactions
> > > (as Tom mentioned), and put the subtransaction id's in the WAL, so they
> > > an be safely committed/rolledback as a group?
> > 
> > It's not quite that easy: all the subtransactions have to commit at
> > *the same time* from the point of view of other xacts, or you have
> > consistency problems.  So there'd need to be more xact-commit mechanism
> > than there is now.  Snapshots are also interesting; we couldn't use a
> > single xact ID per backend to show the open-transaction state.
> 
> Yes, I knew that was going to come up that you have to add a lock to the
> pg_log that is only in affect when someone is commiting a transaction
> with subtransactions.  Normal transactions get read/sharedlock, while
> subtransaction needs exclusive/writelock.

I was wrong here.  Multiple backends can write to pg_log at the same
time, even subtraction ones.  It is just that no backend can read from
pg_log during a subtransaction commit.  Acctually, they can if the are
reading a transaction status that is less than the minium active
transaction id, see GetXmaxRecent().

Doesn't seem too bad.

-- 
  Bruce Momjian                        |  http://candle.pha.pa.us
  pgman@candle.pha.pa.us               |  (610) 853-3000
  +  If your life is a hard drive,     |  830 Blythe Avenue
  +  Christ can be your backup.        |  Drexel Hill, Pennsylvania 19026

Sat, 19 May 2001 08:12:28 -0400 (EDT)
Bruce Momjian <pgman@candle.pha.pa.us>
Re: Plans for solving the VACUUM problem
> Bruce Momjian <pgman@candle.pha.pa.us> writes:
> > Hey, I have an idea.  Can we do subtransactions as separate transactions
> > (as Tom mentioned), and put the subtransaction id's in the WAL, so they
> > an be safely committed/rolledback as a group?
> 
> It's not quite that easy: all the subtransactions have to commit at
> *the same time* from the point of view of other xacts, or you have
> consistency problems.  So there'd need to be more xact-commit mechanism
> than there is now.  Snapshots are also interesting; we couldn't use a
> single xact ID per backend to show the open-transaction state.

OK, I have another idea about subtransactions as multiple transaction
ids.

I realize that the snapshot problem would be an issue, because now
instead of looking at your own transaction id, you have to look at
multiple transaction ids.  We could do this as a List of xid's, but that
will not scale well.

My idea is for a subtransaction backend to have its own pg_log-style
memory area that shows which transactions it owns and has
committed/aborted.  It can have the log start at its start xid, and can
look in pg_log and in there anytime it needs to check the visibility of
a transaction greater than its minium xid.  16k can hold 64k xids, so it
seems it should scale pretty well.  (Each xid is two bits in pg_log.)

In fact, multi-query transactions are just a special case of
subtransactions, where all previous subtransactions are
committed/visible.  We could use the same pg_log-style memory area for
multi-query transactions, eliminating the command counter  and saving 8
bytes overhead per tuple.

Currently, the XMIN/XMAX command counters are used only by the current
transaction, and they are useless once the transaction finishes and take
up 8 bytes on disk.

So, this idea gets us subtransactions and saves 8 bytes overhead.  This
reduces our per-tuple overhead from 36 to 28 bytes, a 22% reduction!

-- 
  Bruce Momjian                        |  http://candle.pha.pa.us
  pgman@candle.pha.pa.us               |  (610) 853-3000
  +  If your life is a hard drive,     |  830 Blythe Avenue
  +  Christ can be your backup.        |  Drexel Hill, Pennsylvania 19026

Sat, 19 May 2001 08:23:37 -0400 (EDT)
Bruce Momjian <pgman@candle.pha.pa.us>
Re: Plans for solving the VACUUM problem
Bruce Momjian <pgman@candle.pha.pa.us> writes:
> In fact, multi-query transactions are just a special case of
> subtransactions, where all previous subtransactions are
> committed/visible.  We could use the same pg_log-style memory area for
> multi-query transactions, eliminating the command counter  and saving 8
> bytes overhead per tuple.

Interesting thought, but command IDs don't act the same as transactions;
in particular, visibility of one scan to another doesn't necessarily
depend on whether the scan has finished.

Possibly that could be taken into account by having different rules for
"do we think it's committed" in the local pg_log than the global one.

Also, this distinction would propagate out of the xact status code;
for example, it wouldn't do for heapam to set the "known committed"
bit on a tuple just because it's from a previous subtransaction of the
current xact.  Right now that works because heapam knows the difference
between xacts and commands; it would still have to know the difference.

A much more significant objection is that such a design would eat xact
IDs at a tremendous rate, to no purpose.  CommandCounterIncrement is a
cheap operation now, and we do it with abandon.  It would not be cheap
if it implied allocating a new xact ID that would eventually need to be
marked committed.  I don't mind allocating a new xact ID for each
explicitly-created savepoint, but a new ID per CommandCounterIncrement
is a different story.

			regards, tom lane

Sat, 19 May 2001 11:13:11 -0400
Tom Lane <tgl@sss.pgh.pa.us>
Re: Plans for solving the VACUUM problem 
> Hm.  On the other hand, relying on WAL for undo means you cannot drop
> old WAL segments that contain records for any open transaction.  We've
> already seen several complaints that the WAL logs grow unmanageably huge
> when there is a long-running transaction, and I think we'll see a lot
> more.
> 
> It would be nicer if we could drop WAL records after a checkpoint or two,
> even in the presence of long-running transactions.  We could do that if
> we were only relying on them for crash recovery and not for UNDO.

As you understand this is old, well-known problem in database practice,
described in books. Two ways - either abort too long running transactions
or (/and) compact old log segments: fetch and save (to use for undo)
records of long-running transactions and remove other records. Neither
way is perfect but nothing is perfect at all -:)

> 1. Space reclamation via UNDO doesn't excite me a whole lot, if we can
> make lightweight VACUUM work well.  (I definitely don't like the idea

Sorry, but I'm going to consider background vacuum as temporary solution
only. As I've already pointed, original PG authors finally became
disillusioned with the same approach. What is good in using UNDO for 1.
is the fact that WAL records give you *direct* physical access to changes
which should be rolled back.

> that after a very long transaction fails and aborts, I'd have to wait
> another very long time for UNDO to do its thing before I could get on
> with my work.  Would much rather have the space reclamation happen in
> background.)

Understandable, but why other transactions should read dirty data again
and again waiting for background vacuum? I think aborted transaction
should take some responsibility for mess made by them -:)
And keeping in mind 2. very long transactions could be continued -:)

> 2. SAVEPOINTs would be awfully nice to have, I agree.
> 
> 3. Reusing xact IDs would be nice, but there's an answer with a lot less
> impact on the system: go to 8-byte xact IDs.  Having to shut down the
> postmaster when you approach the 4Gb transaction mark isn't going to
> impress people who want a 24x7 commitment, anyway.

+8 bytes in tuple header is not so tiny thing.

> 4. Recycling pg_log would be nice too, but we've already discussed other
> hacks that might allow pg_log to be kept finite without depending on
> UNDO (or requiring postmaster restarts, IIRC).

We did... and didn't get agreement.

> I'm sort of thinking that undoing back to a savepoint is the only real
> usefulness of WAL-based UNDO. Is it practical to preserve the WAL log
> just back to the last savepoint in each xact, not the whole xact?

No, it's not. It's not possible in overwriting systems at all - all
transaction records are required.

> Another thought: do we need WAL UNDO at all to implement savepoints?
> Is there some way we could do them like nested transactions, wherein
> each savepoint-to-savepoint segment is given its own transaction number?
> Committing multiple xact IDs at once might be a little tricky, but it
> seems like a narrow, soluble problem.

Implicit savepoints wouldn't be possible - this is very convenient
feature I've found in Oracle.
And additional code in tqual.c wouldn't be good addition.

> Implementing UNDO without creating lots of performance issues looks
> a lot harder.

What *performance* issues?!
The only issue is additional disk requirements.

Vadim



Sat, 19 May 2001 23:36:34 -0700
"Vadim Mikheev" <vmikheev@sectorbase.com>
Re: Plans for solving the VACUUM problem 
"Vadim Mikheev" <vmikheev@sectorbase.com> writes:
>> 1. Space reclamation via UNDO doesn't excite me a whole lot, if we can
>> make lightweight VACUUM work well.

> Sorry, but I'm going to consider background vacuum as temporary solution
> only. As I've already pointed, original PG authors finally became
> disillusioned with the same approach.

How could they become disillusioned with it, when they never tried it?
I know of no evidence that any version of PG has had backgroundable
(non-blocking-to-other-transactions) VACUUM, still less within-relation
space recycling.  They may have become disillusioned with the form of
VACUUM that they actually had (ie, the same one we've inherited) --- but
please don't call that "the same approach" I'm proposing.

Certainly, doing VACUUM this way is an experiment that may fail, or may
require further work before it really works well.  But I'd appreciate it
if you wouldn't prejudge the results of the experiment.

>> Would much rather have the space reclamation happen in
>> background.)

> Understandable, but why other transactions should read dirty data again
> and again waiting for background vacuum? I think aborted transaction
> should take some responsibility for mess made by them -:)

They might read it again and again before the failed xact gets around to
removing the data, too.  You cannot rely on UNDO for correctness; at
most it can be a speed/space optimization.  I see no reason to assume
that it's a more effective optimization than a background vacuum
process.

>> 3. Reusing xact IDs would be nice, but there's an answer with a lot less
>> impact on the system: go to 8-byte xact IDs.

> +8 bytes in tuple header is not so tiny thing.

Agreed, but the people who need 8-byte IDs are not running small
installations.  I think they'd sooner pay a little more in disk space
than risk costs in performance or reliability.

>> Another thought: do we need WAL UNDO at all to implement savepoints?
>> Is there some way we could do them like nested transactions, wherein
>> each savepoint-to-savepoint segment is given its own transaction number?

> Implicit savepoints wouldn't be possible - this is very convenient
> feature I've found in Oracle.

Why not?  Seems to me that establishing implicit savepoints is just a
user-interface issue; you can do it, or not do it, regardless of the
underlying mechanism.

>> Implementing UNDO without creating lots of performance issues looks
>> a lot harder.

> What *performance* issues?!
> The only issue is additional disk requirements.

Not so.  UNDO does failed-transaction cleanup work in the interactive
backends, where it necessarily delays clients who might otherwise be
issuing their next command.  A VACUUM-based approach does the cleanup
work in the background.  Same work, more or less, but it's not in the
clients' critical path.

BTW, UNDO for failed transactions alone will not eliminate the need for
VACUUM.  Will you also make successful transactions go back and
physically remove the tuples they deleted?

			regards, tom lane

Sun, 20 May 2001 13:09:45 -0400
Tom Lane <tgl@sss.pgh.pa.us>
Re: Plans for solving the VACUUM problem 
> >> 1. Space reclamation via UNDO doesn't excite me a whole lot, if we can
> >> make lightweight VACUUM work well.
> 
> > Sorry, but I'm going to consider background vacuum as temporary solution
> > only. As I've already pointed, original PG authors finally became
> > disillusioned with the same approach.
> 
> How could they become disillusioned with it, when they never tried it?
> I know of no evidence that any version of PG has had backgroundable
> (non-blocking-to-other-transactions) VACUUM, still less within-relation
> space recycling.  They may have become disillusioned with the form of
> VACUUM that they actually had (ie, the same one we've inherited) --- but
> please don't call that "the same approach" I'm proposing.

Pre-Postgres'95 (original) versions had vacuum daemon running in
background. I don't know if that vacuum shrinked relations or not
(there was no shrinking in '95 version), I know that daemon had to
do some extra work in moving old tuples to archival storage, but
anyway as you can read in old papers in the case of consistent heavy
load daemon was not able to cleanup storage fast enough. And the
reason is obvious - no matter how optimized your daemon will be
(in regard to blocking other transactions etc), it will have to
perform huge amount of IO just to find space available for reclaiming.

> Certainly, doing VACUUM this way is an experiment that may fail, or may
> require further work before it really works well. But I'd appreciate it
> if you wouldn't prejudge the results of the experiment.

Why not, Tom? Why shouldn't I say my opinion?
Last summer your comment about WAL, may experiment that time, was that
it will save just a few fsyncs. It was your right to make prejudment,
what's wrong with my rights? And you appealed to old papers as well, BTW.

> > Understandable, but why other transactions should read dirty data again
> > and again waiting for background vacuum? I think aborted transaction
> > should take some responsibility for mess made by them -:)
> 
> They might read it again and again before the failed xact gets around to
> removing the data, too.  You cannot rely on UNDO for correctness; at
> most it can be a speed/space optimization. I see no reason to assume
> that it's a more effective optimization than a background vacuum
> process.

Really?! Once again: WAL records give you *physical* address of tuples
(both heap and index ones!) to be removed and size of log to read
records from is not comparable with size of data files.

> >> Another thought: do we need WAL UNDO at all to implement savepoints?
> >> Is there some way we could do them like nested transactions, wherein
> >> each savepoint-to-savepoint segment is given its own transaction number?
> 
> > Implicit savepoints wouldn't be possible - this is very convenient
> > feature I've found in Oracle.
> 
> Why not?  Seems to me that establishing implicit savepoints is just a
> user-interface issue; you can do it, or not do it, regardless of the
> underlying mechanism.

Implicit savepoints are setted by server automatically before each
query execution - you wouldn't use transaction IDs for this.

> >> Implementing UNDO without creating lots of performance issues looks
> >> a lot harder.
> 
> > What *performance* issues?!
> > The only issue is additional disk requirements.
> 
> Not so. UNDO does failed-transaction cleanup work in the interactive
> backends, where it necessarily delays clients who might otherwise be
> issuing their next command.  A VACUUM-based approach does the cleanup
> work in the background. Same work, more or less, but it's not in the
> clients' critical path.

Not same work but much more and in the critical pathes of all clients.
And - is overall performance of Oracle or Informix worse then in PG?
Seems delays in clients for rollback doesn't affect performance so much.
But dirty storage does it.

> BTW, UNDO for failed transactions alone will not eliminate the need for
> VACUUM.  Will you also make successful transactions go back and
> physically remove the tuples they deleted?

They can't do this, as you know pretty well. But using WAL to get TIDs to
be deleted is considerable, no?

Vadim



Sun, 20 May 2001 14:00:48 -0700
"Vadim Mikheev" <vmikheev@sectorbase.com>
Re: Plans for solving the VACUUM problem 
> Were you going to use WAL to get free space from old copies too?

Considerable approach.

> Vadim, I think I am missing something.  You mentioned UNDO would be used
> for these cases and I don't understand the purpose of adding what would
> seem to be a pretty complex capability:

Yeh, we already won title of most advanced among simple databases, -:)
Yes, looking in list of IDs assigned to single transaction in tqual.c is much
easy to do than UNDO. As well as couple of fsyncs is easy than WAL.

> > 1. Reclaim space allocated by aborted transactions.
> 
> Is there really a lot to be saved here vs. old tuples of committed
> transactions?

Are you able to protect COPY FROM from abort/crash?

Vadim



Sun, 20 May 2001 14:13:37 -0700
"Vadim Mikheev" <vmikheev@sectorbase.com>
Re: Plans for solving the VACUUM problem
"Vadim Mikheev" <vmikheev@sectorbase.com> writes:
> Really?! Once again: WAL records give you *physical* address of tuples
> (both heap and index ones!) to be removed and size of log to read
> records from is not comparable with size of data files.

You sure?  With our current approach of dumping data pages into the WAL
on first change since checkpoint (and doing so again after each
checkpoint) it's not too difficult to devise scenarios where the WAL log
is *larger* than the affected datafiles ... and can't be truncated until
someone commits.

The copied-data-page traffic is the worst problem with our current
WAL implementation.  I did some measurements last week on VACUUM of a
test table (the accounts table from a "pg_bench -s 10" setup, which
contains 1000000 rows; I updated 20000 rows and then vacuumed).  This
generated about 34400 8k blocks of WAL traffic, of which about 33300
represented copied pages and the other 1100 blocks were actual WAL
entries.  That's a pretty massive I/O overhead, considering the table
itself was under 20000 8k blocks.  It was also interesting to note that
a large fraction of the CPU time was spent calculating CRCs on the WAL
data.

Would it be possible to split the WAL traffic into two sets of files,
one for WAL log records proper and one for copied pages?  Seems like
we could recycle the pages after each checkpoint rather than hanging
onto them until the associated transactions commit.

>> Why not?  Seems to me that establishing implicit savepoints is just a
>> user-interface issue; you can do it, or not do it, regardless of the
>> underlying mechanism.

> Implicit savepoints are setted by server automatically before each
> query execution - you wouldn't use transaction IDs for this.

If the user asked you to, I don't see why not.

			regards, tom lane

Sun, 20 May 2001 17:25:47 -0400
Tom Lane <tgl@sss.pgh.pa.us>
Re: Plans for solving the VACUUM problem 
On Sun, 20 May 2001, Vadim Mikheev wrote:

> > >> 1. Space reclamation via UNDO doesn't excite me a whole lot, if we can
> > >> make lightweight VACUUM work well.
> >
> > > Sorry, but I'm going to consider background vacuum as temporary solution
> > > only. As I've already pointed, original PG authors finally became
> > > disillusioned with the same approach.
> >
> > How could they become disillusioned with it, when they never tried it?
> > I know of no evidence that any version of PG has had backgroundable
> > (non-blocking-to-other-transactions) VACUUM, still less within-relation
> > space recycling.  They may have become disillusioned with the form of
> > VACUUM that they actually had (ie, the same one we've inherited) --- but
> > please don't call that "the same approach" I'm proposing.
>
> Pre-Postgres'95 (original) versions had vacuum daemon running in
> background. I don't know if that vacuum shrinked relations or not
> (there was no shrinking in '95 version), I know that daemon had to
> do some extra work in moving old tuples to archival storage, but
> anyway as you can read in old papers in the case of consistent heavy
> load daemon was not able to cleanup storage fast enough. And the
> reason is obvious - no matter how optimized your daemon will be
> (in regard to blocking other transactions etc), it will have to
> perform huge amount of IO just to find space available for reclaiming.
>
> > Certainly, doing VACUUM this way is an experiment that may fail, or may
> > require further work before it really works well. But I'd appreciate it
> > if you wouldn't prejudge the results of the experiment.
>
> Why not, Tom? Why shouldn't I say my opinion?
> Last summer your comment about WAL, may experiment that time, was that
> it will save just a few fsyncs. It was your right to make prejudment,
> what's wrong with my rights? And you appealed to old papers as well, BTW.

If its an "experiment", shouldn't it be done outside of the main source
tree, with adequate testing in a high load situation, with a patch
released to the community for further testing/comments, before it is added
to the source tree?  From reading Vadim's comment above (re:
pre-Postgres95), this daemonized approach would cause a high I/O load on
the server in a situation where there are *alot* of UPDATE/DELETEs
happening to the database, which should be easily recreatable, no?  Or,
Vadim, am I misundertanding?



Sun, 20 May 2001 18:29:03 -0300 (ADT)
The Hermit Hacker <scrappy@hub.org>
Re: Plans for solving the VACUUM problem 
The Hermit Hacker <scrappy@hub.org> writes:
> If its an "experiment", shouldn't it be done outside of the main source
> tree, with adequate testing in a high load situation, with a patch
> released to the community for further testing/comments, before it is added
> to the source tree?

Mebbe we should've handled WAL that way too ;-)

Seriously, I don't think that my proposed changes need be treated with
quite that much suspicion.  The only part that is really intrusive is
the shared-memory free-heap-space-management change.  But AFAICT that
will be a necessary component of *any* approach to getting rid of
VACUUM.  We've been arguing here, in essence, about whether a background
or on-line approach to finding free space will be more useful; but that
still leaves you with the question of what you do with the free space
after you've found it.  Without some kind of shared free space map,
there's not anything you can do except have the process that found the
space do tuple moving and file truncation --- ie, VACUUM.  So even if
I'm quite wrong about the effectiveness of a background VACUUM, the FSM
code will still be needed: an UNDO-style approach is also going to need
an FSM to do anything with the free space it finds.  It's equally clear
that the index AMs have to support index tuple deletion without
exclusive lock, or we'll still have blocking problems during free-space
cleanup, no matter what drives that cleanup.  The only part of what
I've proposed that might end up getting relegated to the scrap heap is
the "lazy vacuum" command itself, which will be a self-contained and
relatively small module (smaller than the present commands/vacuum.c,
for sure).

Besides which, Vadim has already said that he won't have time to do
anything about space reclamation before 7.2.  So even if background
vacuum does end up getting superseded by something better, we're going
to need it for a release or two ...

			regards, tom lane

Sun, 20 May 2001 17:57:15 -0400
Tom Lane <tgl@sss.pgh.pa.us>
Re: Plans for solving the VACUUM problem 
At 01:09 PM 20-05-2001 -0400, Tom Lane wrote:
>>> 3. Reusing xact IDs would be nice, but there's an answer with a lot less
>>> impact on the system: go to 8-byte xact IDs.
>
>> +8 bytes in tuple header is not so tiny thing.
>
>Agreed, but the people who need 8-byte IDs are not running small
>installations.  I think they'd sooner pay a little more in disk space
>than risk costs in performance or reliability.

An additional 4 (8?) bytes per tuple to increase the "mean time before
problem " 4 billion times sounds good to me.

Cheerio,
Link.


Mon, 21 May 2001 09:28:06 +0800
Lincoln Yeoh <lyeoh@pop.jaring.my>
Re: Plans for solving the VACUUM problem 
> > Really?! Once again: WAL records give you *physical* address of tuples
> > (both heap and index ones!) to be removed and size of log to read
> > records from is not comparable with size of data files.
> 
> You sure?  With our current approach of dumping data pages into the WAL
> on first change since checkpoint (and doing so again after each
> checkpoint) it's not too difficult to devise scenarios where the WAL log
> is *larger* than the affected datafiles ... and can't be truncated until
> someone commits.

Yes, but note mine "size of log to read records from" - each log record
has pointer to previous record made by same transaction: rollback must
not read entire log file to get all records of specific transaction.

> >> Why not?  Seems to me that establishing implicit savepoints is just a
> >> user-interface issue; you can do it, or not do it, regardless of the
> >> underlying mechanism.
> 
> > Implicit savepoints are setted by server automatically before each
> > query execution - you wouldn't use transaction IDs for this.
> 
> If the user asked you to, I don't see why not.

Example of one of implicit savepoint usage: skipping duplicate key insertion.
Using transaction IDs when someone want to insert a few thousand records?

Vadim



Sun, 20 May 2001 19:27:07 -0700
"Vadim Mikheev" <vmikheev@sectorbase.com>
Re: Plans for solving the VACUUM problem 
> If its an "experiment", shouldn't it be done outside of the main source
> tree, with adequate testing in a high load situation, with a patch
> released to the community for further testing/comments, before it is added
> to the source tree?  From reading Vadim's comment above (re:
> pre-Postgres95), this daemonized approach would cause a high I/O load on
> the server in a situation where there are *alot* of UPDATE/DELETEs
> happening to the database, which should be easily recreatable, no?  Or,
> Vadim, am I misundertanding?

It probably will not cause more IO than vacuum does right now.
But unfortunately it will not reduce that IO. Cleanup work will be spreaded
in time and users will not experience long lockouts but average impact
on overall system throughput will be same (or maybe higher).
My point is that we'll need in dynamic cleanup anyway and UNDO is
what should be implemented for dynamic cleanup of aborted changes.
Plus UNDO gives us natural implementation of savepoints and some
abilities in transaction IDs management, which we may use or not
(though, 4. - pg_log size management - is really good thing).

Vadim



Sun, 20 May 2001 19:57:48 -0700
"Vadim Mikheev" <vmikheev@sectorbase.com>
Re: Plans for solving the VACUUM problem 
> Seriously, I don't think that my proposed changes need be treated with
> quite that much suspicion.  The only part that is really intrusive is

Agreed. I fight for UNDO, not against background vacuum -:)

> the shared-memory free-heap-space-management change.  But AFAICT that
> will be a necessary component of *any* approach to getting rid of
> VACUUM.  We've been arguing here, in essence, about whether a background
> or on-line approach to finding free space will be more useful; but that
> still leaves you with the question of what you do with the free space
> after you've found it.  Without some kind of shared free space map,
> there's not anything you can do except have the process that found the
> space do tuple moving and file truncation --- ie, VACUUM.  So even if
> I'm quite wrong about the effectiveness of a background VACUUM, the FSM
> code will still be needed: an UNDO-style approach is also going to need
> an FSM to do anything with the free space it finds.  It's equally clear

Unfortunately, I think that we'll need in on-disk FSM and that FSM is
actually the most complex thing to do in "space reclamation" project.

> Besides which, Vadim has already said that he won't have time to do
> anything about space reclamation before 7.2.  So even if background
> vacuum does end up getting superseded by something better, we're going
> to need it for a release or two ...

Yes.

Vadim



Sun, 20 May 2001 20:06:15 -0700
"Vadim Mikheev" <vmikheev@sectorbase.com>
Re: Plans for solving the VACUUM problem 
"Vadim Mikheev" <vmikheev@sectorbase.com> writes:
> Unfortunately, I think that we'll need in on-disk FSM and that FSM is
> actually the most complex thing to do in "space reclamation" project.

I hope we can avoid on-disk FSM.  Seems to me that that would create
problems both for performance (lots of extra disk I/O) and reliability
(what happens if FSM is corrupted?  A restart won't fix it).

But, if we do need it, most of the work needed to install FSM APIs
should carry over.  So I still don't see an objection to doing
in-memory FSM as a first step.


BTW, I was digging through the old Postgres papers this afternoon,
to refresh my memory about what they actually said about VACUUM.
I was interested to discover that at one time the tuple-insertion
algorithm went as follows:
  1. Pick a page at random in the relation, read it in, and see if it
     has enough free space.  Repeat up to three times.
  2. If #1 fails to find space, append tuple at end.
When they got around to doing some performance measurement, they
discovered that step #1 was a serious loser, and dropped it in favor
of pure #2 (which is what we still have today).  Food for thought.

			regards, tom lane

Mon, 21 May 2001 00:32:42 -0400
Tom Lane <tgl@sss.pgh.pa.us>
Re: Plans for solving the VACUUM problem 
"Vadim Mikheev" <vmikheev@sectorbase.com> writes:
> It probably will not cause more IO than vacuum does right now.
> But unfortunately it will not reduce that IO.

Uh ... what?  Certainly it will reduce the total cost of vacuum,
because it won't bother to try to move tuples to fill holes.
The index cleanup method I've proposed should be substantially
more efficient than the existing code, as well.

> My point is that we'll need in dynamic cleanup anyway and UNDO is
> what should be implemented for dynamic cleanup of aborted changes.

UNDO might offer some other benefits, but I doubt that it will allow
us to eliminate VACUUM completely.  To do that, you would need to
keep track of free space using exact, persistent (on-disk) bookkeeping
data structures.  The overhead of that will be very substantial: more,
I predict, than the approximate approach I proposed.

			regards, tom lane

Mon, 21 May 2001 10:06:35 -0400
Tom Lane <tgl@sss.pgh.pa.us>
Re: Plans for solving the VACUUM problem 


Tom Lane wrote:

> 
> Hm.  On the other hand, relying on WAL for undo means you cannot drop
> old WAL segments that contain records for any open transaction.  We've
> already seen several complaints that the WAL logs grow unmanageably huge
> when there is a long-running transaction, and I think we'll see a lot
> more.
> 
> It would be nicer if we could drop WAL records after a checkpoint or two,
> even in the presence of long-running transactions.  We could do that if
> we were only relying on them for crash recovery and not for UNDO.

In Oracle the REDO and UNDO are separate.  REDO in oracle is limited in 
size to x log files y big (where x and y are parameters at database 
creation).  These x log files are reused in a round robin way with 
checkpoints forced when wrapping around.

REDO in oracle is done by something known as a 'rollback segment'.  
There are many rollback segments.  A transaction is assigned one 
rollback segment to write its UNDO records to.  Transactions are 
assigned to a rollback segment randomly (or you can explicitly assign a 
transaction to a particular rollback segment if you want).  The size of 
rollback segments are limited and transactions are aborted if they 
exceed that size.  This is why oracle has the option to assign a 
specific rollback segment to a transaction, so if you know you are going 
to update/insert tons of stuff you want to use an appropriately sized 
rollback segment for that transaction.

Things I like about the Oracle approach vs current WAL REDO and proposed 
UNDO:

1 Sizes allocated to REDO and UNDO in Oracle are known and 
configurable.  WAL sizes are unknown and not constrained.
2 Oracle allows for big transactions by allowing them to use 
specifically sizied rollback segments to handle the large transaction.
While WAL could be enhanced to fix 1, it appears difficult to have 
different limits for different types of transactions as Oracle supports 
in 2.

Thinks I don't like about the Oracle approach:

1 Not only updates, but also long running queries can be aborted if the 
rollback segment size it too small, as the undo is necessary to create 
an snapshot of the state of the database at the time the query started.

thanks,
--Barry

> 


Mon, 21 May 2001 15:49:30 -0700
Barry Lind <barry@xythos.com>
Re: Plans for solving the VACUUM problem


Mikheev, Vadim wrote:

> 
> Ok, last reminder -:))
> 
> On transaction abort, read WAL records and undo (rollback)
> changes made in storage. Would allow:
> 
> 1. Reclaim space allocated by aborted transactions.
> 2. Implement SAVEPOINTs.
>    Just to remind -:) - in the event of error discovered by server
>    - duplicate key, deadlock, command mistyping, etc, - transaction
>    will be rolled back to the nearest implicit savepoint setted
>    just before query execution; - or transaction can be aborted by
>    ROLLBACK TO <savepoint_name> command to some explicit savepoint
>    setted by user. Transaction rolled back to savepoint may be continued.
> 3. Reuse transaction IDs on postmaster restart.
> 4. Split pg_log into small files with ability to remove old ones (which
>    do not hold statuses for any running transactions).
> 
> Vadim

This is probably not a good thread to add my two cents worth, but here 
goes anyway.

The biggest issue I see with the proposed UNDO using WAL is the issue of 
large/long lasting transactions.  While it might be possible to solve 
this problem with some extra work.  However keep in mind that different 
types of transactions (i.e. normal vs bulk loads) require different 
amounts of time and/or UNDO.  To solve this problem, you really need per 
transaction limits which seems difficult to implement.

I have no doubt that UNDO with WAL can be done.  But is there some other 
way of doing UNDO that might be just as good or better?

Part of what I see in this thread reading between the lines is that some 
believe the solution to many problems in the long term is to implement 
an overwriting storage manager.  Implementing UNDO via WAL is a 
necessary step in that direction.  While others seem to believe that the 
non-overwriting storage manager has some life in it yet, and may even be 
the storage manager for many releases to come.  I don't know enough 
about the internals to have any say in that discussion, however the 
grass isn't always greener on the other side of the fence (i.e. an 
overwriting storage manager will come with its own set of problems/issues).

So let me throw out an idea for UNDO using the current storage manager.  
First let me state that UNDO is a bit of a misnomer, since undo for 
transactions is already implemented.  That is what pg_log is all about.  
The part of UNDO that is missing is savepoints (either explicit or 
implicit), because pg_log doesn't capture the information for each 
command in a transaction.  So the question really becomes, how to 
implement savepoints with current storage manager?

I am going to lay out one assumption that I am making:
1) Most transactions are either completely successful or completely 
rolled back
  (If this weren't true, i.e. you really needed savepoints to partially 
rollback changes, you couldn't be using the existing version of 
postgresql at all)

My proposal is:
  1) create a new relation to store 'failed commands' for transactions. 
   This is similar to pg_log for transactions, but takes it to the 
command level.  And since it records only failed commands (or ranges of 
failed commands), thus most transactions will not have any information 
in this relation per the assumption above.
   2) Use the unused pg_log status (3 = unused, 2 = commit, 1 = abort, 0 
= inprocess) to mean that the transaction was commited but some commands 
were rolled back (i.e. partial commit)
   Again for the majority of transactions nothing will need to change, 
since they will still be marked as committed or aborted.
   3) Code that determines whether or not a tuple is committed or not 
needs to be aware of this new pg_log status, and look in the new 
relation to see if the particular command was rolled back or not to 
determine the commited status of the tuple.  This subtly changes the 
meaning of HEAP_XMIN_COMMITTED and related flags to reflect the 
transaction and command status instead of just the transaction status.

The runtime cost of this shouldn't be too high, since the committed 
state is cached in HEAP_XMIN_COMMITTED et al, it is only the added cost 
for the pass that needs to set these flags, and then there is only added 
cost in the case that the transaction wasn't completely sucessful (again 
my assumption above).

Now I have know idea if what I am proposing is really doable or not.  I 
am just throwing this out as an alternative to WAL based 
UNDO/savepoints.  The reason I am doing this is that to me it seems to 
leverage much of the existing infrastructure already in place that 
performs undo for rolledback transactions (all the tmin, tmax, cmin, 
cmax stuff as well as vacuum).  Also it doesn't come with the large WAL 
log file problem for large transactions.

Now having said all of this I realize that this doesn't solve the 4 
billion transaction id limit problem, or the large size of the pg_log 
file with large numbers of transactions.

thanks,
--Barry


> 


Mon, 21 May 2001 17:18:18 -0700
Barry Lind <barry@xythos.com>
Re: Plans for solving the VACUUM problem