On Thu, May 7, 2009 at 6:31 PM, Simon Riggs <si...@2ndquadrant.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 -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers