Re: Serializable Isolation without blocking

On Thu, May 7, 2009 at 6:31 PM, Simon Riggs <simon(at)2ndquadrant(dot)com> wrote:
> Each user must compare against work performed by all other users. O(N).
>
> There are N users, so O(N^2).

i think this logic only works if you must scan every item for every
other user every time. If you have data structures like binary trees
or whatever to fine any matching predicate locks or intent locks or
whatever we're calling them then you can hopefully find them in faster
than O(N) time.

I'm not sure you can do better than a full linear search though. If I
do something like "SELECT count(*) FROM tab WHERE
complex_function(a,b) = 5"

And then you "INSERT INTO tab (a,b) VALUES (1,2)". How would you store
any record of the fact that there's a serialization failure iff
complex_function(1,2)=5 in any way that lets you look it up in any way
other than evaluating complex_function for every set of values
inserted?

--
greg