Re: implementing a database log

"Christoph Rupp" <cruppstahl_at_gmail.com> wrote in message news:d1a87b0a-6bde-46c2-a154-670ddf693669_at_2g2000hsn.googlegroups.com...
> On Apr 24, 4:11 pm, "Brian Selzer" <br..._at_selzer-software.com> wrote:
>> If you start out with a set of records and you know what is to be
>> inserted,
>> updated, and deleted, you can compute the resulting set of records. If
>> you
>> start out with the resulting set of records, and you know what was
>> inserted,
>> updated and deleted in order to arrive at that result, then you can
>> compute
>> the original set of records. For simplicity, even if it isn't
>> necessarily
>> the most efficient, what is updated could be implemented as a set of
>> ordered
>> pairs of records, tying each original record to its replacement. So the
>> log
>> would consist of a sequence of triples (D, U, I) separated by transaction
>> markers where D is a set of records that were deleted, U is a set of
>> pairs
>> of records that were updated, and I is a set of records that were
>> inserted.
>>
>> Now, provided that the log is written before the database--that is, (1)
>> write the triple to the log, (2) write the database, (3) write the
>> transaction marker in the log--, it should be possible to determine
>> whether
>> or not what was written to the log actually made it into the database,
>> and
>> thus it should be possible to roll back any uncommitted transaction.
>
> what about page splits in the index tree? and page merges? You would
> need special log entries for this, and therefore special rollback
> mechanisms to undo a page split/merge.
>

Not necessarily. Once you've identified which records might have been affected by uncommitted transactions, you could determine which index pages could have been affected and check them for consistency, repairing or rebuilding them if necessary. Once you know which index pages might have been affected and thus which key values, a scan through the table could yield the current offsets of each record associated with an affected key value, making it possible to verify and if necessary reconstruct only the affected portion of the indexes. It would certainly take more processing power during recovery than a brute-force method such as recording all index pages affected by a transaction, but with much less log storage requirements and therefore better throughput for normal operations. Received on Fri Apr 25 2008 - 22:50:23 CEST