Re: [HACKERS] proposals for LLL, part 1 - Mailing list pgsql-hackers

I am retaining your entire message here for reference.

I have a good solution for this.  It will require only 4k of shared
memory, and will have no restrictions on the age or number of
transactions.

First, I think we only want to implement "read committed isolation
level", not serialized.  Not sure why someone would want serialized.

OK, when a backend is looking at a row that has been committed, it must
decide if the row was committed before or after my transaction started.
If the transaction commit id(xmin) is greater than our current xid, we
know we should not look at it because it is for a transaction that
started after our own transaction.

The problem is for transactions started before our own (have xmin's less
than our own), and may have committed before or after our transaction.

Here is my idea.  We add a field to the shared memory Proc structure
that can contain up to 32 transaction ids.  When a transaction starts,
we spin though all other open Proc structures, and record all
currently-running transaction ids in our own Proc field used to store up
to 32 transaction ids.  While we do this, we remember the lowest of
these open transaction ids.

This is our snapshot of current transactions at the time our transaction
starts.  While analyzing a row, if it is greater than our transaction
id, then the transaction was not even started before our transaction.
If the xmin is lower than the min transaction id that we remembered from
the Proc structures, it was committed before our transaction started.
If it is greater than or equal to the min remembered transaction id, we
must spin through our stored transaction ids.  If it is in the stored
list, we don't look at the row, because that transaction was not
committed when we started our transaction.  If it is not in the list, it
must have been committed before our transaction started.  We know this
because if any backend starting a transaction after ours would get a
transaction id higher than ours.

Comments?

> Ok, I'm not sure that LLL will appear in 6.4 but it's good time to
> discuss about it.
>
> First, PostgreSQL is multi-version system due to its
> non-overwriting storage manager. And so, first proposal is use
> this feature (multi-versioning) in LLL implementation.
>
> In multi-version systems access methods don't use locks to read
> consistent data and so readers don't block writers, writers don't
> block readers and only the same-row writers block writers. In such
> systems access methods returns snapshot of data as they were in
> _some_ point in time. For read committed isolation level this
> moment is the time when statement began. For serialized isolation
> level this is the time when current transaction began.
>
> Oracle uses rollback segments to reconstract blocks that were
> changed after statement/transaction began and so statement sees
> only data that were committed by then.
>
> In our case we have to analyze tuple xmin/xmax to determine _when_
> corresponding transaction was committed in regard to the last
> transaction (LCX) that was committed when statement/transaction
> began.
>
> If xmin/xmax was committed before LCX then tuple
> insertion/deletion is visible to statement, else - not visible.
>
> To achieve this, the second proposal is to use special SCN -
> System Change Number (C) Oracle :) - that will be incremented by 1
> by each transaction commit. Each commited transaction will have
> corresponding SCN (4 bytes -> equal to sizeof XID).
>
> We have to keep XID --> SCN mapping as long as there is running
> transaction that is "interested" in XID: when transaction begins
> it will determine the first (the oldest) running transaction XID
> and this will be the minimum XID whose SCN transaction would like
> to know.
>
> Access methods will have to determine SCN for xmin/xmax only if
> FRX <= xmin/xmax <= LSX, where FRX is XID of first (oldest)
> running transactions and LSX is last started transaction - in the
> moment when statement (for read committed) or transaction (for
> serialized) began. For such xmin/xmax their SCNs will be compared
> with SCN determined in the moment of statement/transaction
> begin...
>
> Changes made by xmin/xmax < FRX are visible to
> statement/transaction, and changes made by xmin/xmax > LSX are not
> visible. Without xmin/xmax SCN lookup.
>
> For XID --> SCN mapping I propose to use the simplest schema:
> ordered queue of SCNs (or something like this) - i.e. keep SCNs
> for all transactions from the first one whose SCN could be
> required by some running transaction to the last started.
>
> This queue must be shared!
>
> The size of this queue and average number of commits/aborts per
> second will define how long transactions will be able to run.  30
> xacts/sec and 400K of queue will enable 30 - 60 minuts running
> transactions...
>
> Keeping queue in shared memmory may be unacceptable in some
> cases... mmap or shared buffer pool could be used to access queue.
> We'll see...
>
> Also note that Oracle has special READ ONLY transactions mode.
> READ ONLY transactions are disallowed to change anything in the
> database. This is good mode for pg_dump (etc) long running
> applications. Because of no one will be "interested" in SCN of
> READ ONLY transactions - such transactions can make private copy
> of the queue part and after this queue could be truncated...
>
> Having 4 bytes per SCN enable to use special values to mark
> corresponding transaction as running or aborted and avoid pg_log
> lookup when we need in both SCN and state of transaction.
>
> ...Well, it's time to sleep :)
>
> To be continued...
>
> Comments ?
>
> Vadim
>
>


--
Bruce Momjian                          |  830 Blythe Avenue
maillist@candle.pha.pa.us              |  Drexel Hill, Pennsylvania 19026
  +  If your life is a hard drive,     |  (610) 353-9879(w)
  +  Christ can be your backup.        |  (610) 853-3000(h)