Re: lazy snapshots?

On Wed, Oct 20, 2010 at 8:11 PM, Robert Haas <robertmhaas(at)gmail(dot)com> wrote:
>> so it's
>> not exploiting that resource at all.  I'm imagining that the kernel of a
>> snapshot is just a WAL position, ie the end of WAL as of the time you
>> take the snapshot (easy to get in O(1) time).  Visibility tests then
>> reduce to "did this transaction commit with a WAL record located before
>> the specified position?".  You'd need some index datastructure that made
>> it reasonably cheap to find out the commit locations of recently
>> committed transactions, where "recent" means "back to recentGlobalXmin".
>> That seems possibly do-able, though I don't have a concrete design in
>> mind.
>
> Interesting.  O(1) snapshots would be great.  I need to think about
> this more before commenting on it, though.

I spent a bunch of time thinking about this, and I don't see any way
to get the memory usage requirements down to something reasonable.
The problem is that RecentGlobalXmin might be arbitrarily far back in
XID space, and you'll need to know the LSN of every commit from that
point forward; whereas the ProcArray requires only constant space. To
put this another way, for any given snapshot, the "interesting" XIDs
are the top-level XIDs between the its xmin and xmax; the number of
those that are invisible to the snapshot is bounded, but the total
number is unbounded. To make this work, you'd need an inexpensive way
of finding the set of transactions which committed after a given LSN
with XIDs less than the snapshot's xmax. Another idea for making that
work is to keep a table of the <min-LSN, max-xmax> pairs for every
snapshot in the system and only track exactly those commits that are
relevant, but it seems hard to think about how to maintain that data
structure, and hard also to prune the table of tracked commits as
snapshots are released.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company