> > How?  The scenario Vadim is pointing out is where the disk 
> > drive writes a changed data block in advance of the WAL log
> > entry describing the change. Then power drops and the WAL
> > entry never gets made. At restart, how will you realize that
> > that data block now contains data you don't want? There's not
> > even a log entry telling you you need to look at it, much less
> > one that tells you what should be in it.
> 
> OK. In that case, recent transactions that were acknowledged to user 
> programs just disappear. The database isn't corrupt, but it doesn't
> contain what the user believes is in it.

Example.

1. Tuple was inserted into index.
2. Looking for free buffer bufmgr decides to write index block.
3. Following WAL core rule bufmgr first calls XLogFlush() to write
   and fsync log record related to index tuple insertion.
4. *Beliving* that log record is on disk now (after successful fsync)
   bufmgr writes index block.

If log record was not really flushed on disk in 3. but on-disk image of
index block was updated in 4. and system crashed after this then after
restart recovery you'll have unlawful index tuple pointing to where?
Who knows! No guarantee that corresponding heap tuple was flushed on
disk.

Isn't database corrupted now?

Vadim

Fri, 12 Jan 2001 16:38:37 -0800
"Mikheev, Vadim" <vmikheev@SECTORBASE.COM>
RE: CRCs
"Mikheev, Vadim" <vmikheev@SECTORBASE.COM> writes:
> If log record was not really flushed on disk in 3. but on-disk image of
> index block was updated in 4. and system crashed after this then after
> restart recovery you'll have unlawful index tuple pointing to where?
> Who knows! No guarantee that corresponding heap tuple was flushed on
> disk.

This example doesn't seem very convincing.  Wouldn't the XLOG entry
describing creation of the heap tuple appear in the log before the one
for the index tuple?  Or are you assuming that both these XLOG entries
are lost due to disk drive malfeasance?

			regards, tom lane

Fri, 12 Jan 2001 19:48:39 -0500
Tom Lane <tgl@sss.pgh.pa.us>
Re: CRCs 
On Fri, Jan 12, 2001 at 04:38:37PM -0800, Mikheev, Vadim wrote:
> Example.
> 1. Tuple was inserted into index.
> 2. Looking for free buffer bufmgr decides to write index block.
> 3. Following WAL core rule bufmgr first calls XLogFlush() to write
>    and fsync log record related to index tuple insertion.
> 4. *Believing* that log record is on disk now (after successful fsync)
>    bufmgr writes index block.
> 
> If log record was not really flushed on disk in 3. but on-disk image of
> index block was updated in 4. and system crashed after this then after
> restart recovery you'll have unlawful index tuple pointing to where?
> Who knows! No guarantee that corresponding heap tuple was flushed on
> disk.
> 
> Isn't database corrupted now?

Note, I haven't read the WAL code, so much of what I've said is based 
on what I know is and isn't possible with logging, rather than on 
Vadim's actual choices.  I know it's *possible* to implement a logging 
database which can maintain consistency without need for strict write 
ordering; but without strict write ordering, it is not possible to 
guarantee durable transactions.  That is, after a power outage, such 
a database may be guaranteed to recover uncorrupted, but some number 
(>= 0) of the last few acknowledged/committed transactions may be lost.

Vadim's implementation assumes strict write ordering, so that (e.g.) 
with IDE disks a corrupt database is possible in the event of a power 
outage.  (Database and OS crashes don't count; those don't keep the 
blocks from finding their way from on-disk buffers to disk.)  This is 
no criticism; it is more efficient to assume strict write ordering, 
and a database that can lose (the last few) committed transactions 
has limited value.

To achieve disk write-order independence is probably not a worthwhile 
goal, but for systems that cannot provide strict write ordering (e.g., 
most PCs) it would be helpful to be able to detect that the database 
has become corrupted.  In Vadim's example above, if the index were to
contain not only the heap blocks' numbers, but also their CRCs, then 
the corruption could be detected when the index is used.  When the 
block is read in, its CRC is checked, and when it is referenced via 
the index, the two CRC values are simply compared and the corruption
is revealed. 

On a machine that does provide strict write ordering, the CRCs in the 
index might be unnecessary overhead, but they also provide cross-checks
to help detect corruption introduced by bugs and whatnot.

Or maybe I don't know what I'm talking about.  

Nathan Myers
ncm@zembu.com

Sat, 13 Jan 2001 02:47:53 -0800
ncm@zembu.com (Nathan Myers)
Re: CRCs
ncm@zembu.com (Nathan Myers) writes:
> To achieve disk write-order independence is probably not a worthwhile 
> goal, but for systems that cannot provide strict write ordering (e.g., 
> most PCs) it would be helpful to be able to detect that the database 
> has become corrupted.  In Vadim's example above, if the index were to
> contain not only the heap blocks' numbers, but also their CRCs, then 
> the corruption could be detected when the index is used.  When the 
> block is read in, its CRC is checked, and when it is referenced via 
> the index, the two CRC values are simply compared and the corruption
> is revealed. 

A row-level CRC might be useful for this, but it would have to be on
the data only (not the tuple commit-status bits).  It'd be totally
impractical with a block CRC, I think.  To do it with a block CRC, every
time you changed *anything* in a heap page, you'd have to find all the
index items for each row on the page and update their copies of the
heap block's CRC.  That could easily turn one disk-write into hundreds,
not to mention the index search costs.  Similarly, a check value that is
affected by tuple status updates would enormously increase the cost of
marking tuples committed or dead.

Instead of a partial row CRC, we could just as well use some other bit
of identifying information, say the row OID.  Given a block CRC on the
heap page, we'll be pretty confident already that the heap page is OK,
we just need to guard against the possibility that it's older than the
index item.  Checking that there is a valid tuple at the slot indicated
by the index item, and that it has the right OID, should be a good
enough (and cheap enough) test.

			regards, tom lane

Sat, 13 Jan 2001 12:49:34 -0500
Tom Lane <tgl@sss.pgh.pa.us>
Re: CRCs 
On Sat, Jan 13, 2001 at 12:49:34PM -0500, Tom Lane wrote:
> ncm@zembu.com (Nathan Myers) writes:
> > ... for systems that cannot provide strict write ordering (e.g., 
> > most PCs) it would be helpful to be able to detect that the database 
> > has become corrupted.  In Vadim's example above, if the index were to
> > contain not only the heap blocks' numbers, but also their CRCs, then 
> > the corruption could be detected when the index is used.  ...
> 
> A row-level CRC might be useful for this, but it would have to be on
> the data only (not the tuple commit-status bits).  It'd be totally
> impractical with a block CRC, I think.   ...

I almost wrote about an indirect scheme to share the expected block CRC
value among all the index entries that need it, but thought it would 
distract from the correct approach:

> Instead of a partial row CRC, we could just as well use some other bit
> of identifying information, say the row OID.   ...

Good.  But, wouldn't the TID be more specific?  True, it would be pretty
unlikely for a block to have an old tuple with the right OID in the same
place.  Belt-and-braces says check both :-).  Either way, the check seems 
independent of block CRCs.   Would this check be simple enough to be safe
for 7.1? 

Nathan Myers
ncm@zembu.com

Sat, 13 Jan 2001 15:33:59 -0800
ncm@zembu.com (Nathan Myers)
Re: CRCs
ncm@zembu.com (Nathan Myers) writes:
>> Instead of a partial row CRC, we could just as well use some other bit
>> of identifying information, say the row OID.   ...

> Good.  But, wouldn't the TID be more specific?

Uh, the TID *is* the pointer from index to heap.  There's no redundancy
that way.

> Would this check be simple enough to be safe for 7.1? 

It'd probably be safe, but adding OIDs to index tuples would force an
initdb, which I'd rather avoid at this stage of the cycle.

			regards, tom lane

Sat, 13 Jan 2001 23:20:30 -0500
Tom Lane <tgl@sss.pgh.pa.us>
Re: CRCs 
On Sunday 14 January 2001 04:49, Tom Lane wrote:

> A row-level CRC might be useful for this, but it would have to be on
> the data only (not the tuple commit-status bits).  It'd be totally
> impractical with a block CRC, I think.  To do it with a block CRC, every
> time you changed *anything* in a heap page, you'd have to find all the
> index items for each row on the page and update their copies of the
> heap block's CRC.  That could easily turn one disk-write into hundreds,
> not to mention the index search costs.  Similarly, a check value that is
> affected by tuple status updates would enormously increase the cost of
> marking tuples committed or dead.

Ah, finally. Looks like we are moving in circles (or spirals ;-) )Remember 
that some 3-4 months ago I requested help from this list several times 
regarding a trigger function that implements a crc only on the user defined 
attributes? I wrote one in pgtcl which was slow and had trouble with the C 
equivalent due to lack of documentation. I still believe this is that useful 
that it should be an option in Postgresand not a user defined function.

Horst

Sun, 14 Jan 2001 21:39:40 +1100
Horst Herb <hherb@malleenet.net.au>
Re: CRCs