Re: Unique constraints for non-btree indexes

On Wed, Jan 18, 2006 at 04:18:10PM -0500, Tom Lane wrote:
> I think the generalization that would be appropriate for GIST is that
> a "unique" index guarantees there are no two entries x, y such that
> x ~ y, where ~ is some boolean operator nominated by the opclass. We'd
> probably have to insist that ~ is commutative (x ~ y iff y ~ x).

Commutative, that's the criteria I was looking for. To be senseble for
this purpose, the operator has to be commutative (the commutator is
itself). This works for b-tree by including = and excluding < and >.
Similarly for GiST indexes, contains no, overlaps yes. That's a fairly
easy test.

> Concurrent insertion into a unique GIST index seems a bit nasty. In
> btree we can identify a unique page to lock for any given key value
> to ensure that no one else is concurrently inserting a conflicting
> key, thus usually allowing concurrent insertions of different keys.
> But I don't see how you do that for an arbitrary ~ operator.

Well, the best I could come up with was to just do the insert for value
X and then do a full index scan for X across the given constraint
operator (~). Any matches would need to go through the
check_unique_index function as defined earlier. The only issue is that
we can't really do easy optimisation. In the case of deferred
constraints you can't even remember where in the tree you were because
new keys could be added anywhere so you always have to do from the top.

The issue I get is deadlocks:

1. Process A inserts value X
2. Process B inserts value Y (where X ~ Y is true)
3. Process A begins scan, finds Y and waits for B
4. Process B begins scan, finds X and waits for A

Oops. The only way I can think of solving that is by marking the
entries tentative until the scan is complete and provide a way of
resolving conflicts between two tentative entries. Requires more
thinking.

Have a nice day,
--
Martijn van Oosterhout <kleptog(at)svana(dot)org> http://svana.org/kleptog/
> Patent. n. Genius is 5% inspiration and 95% perspiration. A patent is a
> tool for doing 5% of the work and then sitting around waiting for someone
> else to do the other 95% so you can sue them.