Re: Serializable Isolation without blocking

On Thu, 2009-05-07 at 10:56 -0500, Kevin Grittner wrote:
> > It's clear that any new-theory solution will cost significantly more
> > as the number of users increases, at least O(N^2), whereas simply
> > waiting is only O(N), AFAICS.
>
> I'm not following your reasoning on the O(N^2). Could you explain why
> you think it would follow that curve?

Each user must compare against work performed by all other users. O(N).

There are N users, so O(N^2).

With reasonable tuning we can make that work with 10 users each checking
the other's data, but with a 100 we'll end up spending more time
checking for aborts (and aborting) than we would if we had just queued
up for it.

If you want this, the simplest implementation is to quite literally
allow only a single SERIALIZABLE txn onto the system at any time. All
other SERIALIZABLEs queue. Note that simple serialization requires no
special handling for aborted transactions. Implementing that will be
fast, proving it works is trivial and it seems will work better in the
general case.

Yeh, it sucks for medium arrival rate transactions, but its great for
low or high arrival rate transactions. The new model is good for medium
arrival rates only and will take a lot of work to implement, correctly
and sufficiently optimally to keep the applicability window wide enough
to justify the effort.

Optimising it would basically entail implementing the equivalent of
block-level locking.

--
Simon Riggs www.2ndQuadrant.com
PostgreSQL Training, Services and Support