Re: Proposal: GiST constraints

I would like to consider adding constraints to GiST indexes. I think it
is possible to add constraints that are more sophisticated than just
UNIQUE. My use case is a non-overlapping constraint, but I think it's
possible for this to be more general.

The idea is to make an array in shared memory with size equal to
max_connections. Each element of the array would hold the oid of an
index, and a tid.

When inserting into a GiST index, take out a lock on the array, and scan
it for other tuples being concurrently inserted into the same index, and
execute some function to determine if any tuples conflict (using the tid
stored in the array). Then, check the visibility of the tuple at that
tid. If the conflicting tuple is live, release the lock on the array and
abort. If the tuple is dead, set the array entry to be invalid, make an
entry in the array, and release the lock. If the tuple has an xmin or
xmax that's still in progress, release the lock on the array, block
waiting on the appropriate xid, and then try again. If no conflicts
exist in the array, make an entry in the array, and release the lock.

Then, search the GiST index using the same function to determine if
conflicts exist in the index. If conflicts exist in the index, check the
visibility information for the tuple and proceed, wait or abort (in the
same way as above). If no conflicts exist, insert.

This should work fine for multi-column indexes where the constraints for
each column are different. For instance, unique and non-overlapping
could be mixed.

I spoke about this idea with several people at EAST and PGCon. In
particular, Teodor had the good idea to store the tid in the array,
rather than the value, to make the idea more general to types of
different sizes.

Thoughts, ideas?

Regards,
Jeff Davis

Jeff Davis <pgsql(at)j-davis(dot)com> writes:
> I would like to consider adding constraints to GiST indexes. I think it
> is possible to add constraints that are more sophisticated than just
> UNIQUE. My use case is a non-overlapping constraint, but I think it's
> possible for this to be more general.

I would like to see something that replaces the current btree-only kluge
for UNIQUE, if we're going to try to do something "general". IOW, don't
think of this as GiST-specific.

regards, tom lane

On Mon, 2008-06-09 at 13:28 -0400, Tom Lane wrote:
> Jeff Davis <pgsql(at)j-davis(dot)com> writes:
> > I would like to consider adding constraints to GiST indexes. I think it
> > is possible to add constraints that are more sophisticated than just
> > UNIQUE. My use case is a non-overlapping constraint, but I think it's
> > possible for this to be more general.
>
> I would like to see something that replaces the current btree-only kluge
> for UNIQUE, if we're going to try to do something "general". IOW, don't
> think of this as GiST-specific.
>

I was concerned that the BTree kludge would outperform what I am
suggesting for the case of UNIQUE, and might therefore still be
necessary.

My proposal requires an extra index lookup, because in GiST a
conflicting tuple isn't necessarily found near the place it might be
inserted. Maybe that cost is not too high, because for the case of BTree
UNIQUE it would just be accessing the same pages twice (once to test for
conflicts, and once to insert).

I'm not sure exactly what you have in mind when you say "kludge". My
proposal doesn't solve the problem of "update foo set a = a + 1", in
which the UNIQUE constraint may fail when it should succeed. I don't see
how that problem can be solved without deferring the constraint checking
until the end of the statement, which sounds costly.

Regards,
Jeff Davis

Jeff Davis <pgsql(at)j-davis(dot)com> writes:
> On Mon, 2008-06-09 at 13:28 -0400, Tom Lane wrote:
>> I would like to see something that replaces the current btree-only kluge
>> for UNIQUE, if we're going to try to do something "general". IOW, don't
>> think of this as GiST-specific.

> I'm not sure exactly what you have in mind when you say "kludge".

Well, there are at least three things not to like about the btree UNIQUE
implementation:

1. It's btree-specific and can't be shared by other index AMs that might
wish to implement constraints.

2. It involves the index AM reaching into the heap, which is at the
least a serious failure of modularity.

3. There's no way to implement a deferred uniqueness check, nor even to
handle the within-statement conflict problem.

It looks to me like the same knocks can be laid on your proposal.

Now admittedly I don't have a solution that addresses these objections
(much less one that does it without losing any performance) but I'm
hesitant to see us building new features in this area without any idea
how we will fix these things --- especially #3, which is a SQL-spec
violation as well as a frequent user complaint. I'd like to have at
least a design plan for fixing these things, so we know whether we are
painting ourselves (further) into a corner.

regards, tom lane

On Mon, 2008-06-09 at 21:00 -0400, Tom Lane wrote:
> 1. It's btree-specific and can't be shared by other index AMs that might
> wish to implement constraints.
>

This can be solved by my proposal, but I just don't know how it would
apply to something like GIN, for instance. It could replace the unique
constraint for BTree, but I'm not sure it would perform as well. It's
not that my proposal is GiST-specific, it's just that is the only use
case I can think of that is an improvement.

> 2. It involves the index AM reaching into the heap, which is at the
> least a serious failure of modularity.

We need to reach into the heap for visibility information, if we're to
implement any constraints at all. Also, we have to test against values
being inserted by other concurrent transactions, and those values can
be variable in size. What other mechanism do we have to share those
variable-sized values among several backends?

> 3. There's no way to implement a deferred uniqueness check, nor even to
> handle the within-statement conflict problem.

This is the big one.

> Now admittedly I don't have a solution that addresses these objections
> (much less one that does it without losing any performance) but I'm
> hesitant to see us building new features in this area without any idea
> how we will fix these things --- especially #3, which is a SQL-spec
> violation as well as a frequent user complaint. I'd like to have at
> least a design plan for fixing these things, so we know whether we are
> painting ourselves (further) into a corner.

I'll see if I can come up with something. I agree that's an important
problem to solve. Does anyone know how other DBMSs do this? I found this
thread from the TODO:

http://archives.postgresql.org/pgsql-hackers/2006-09/msg01458.php

Regards,
Jeff Davis

> I would like to consider adding constraints to GiST indexes. I think it
> is possible to add constraints that are more sophisticated than just
> UNIQUE. My use case is a non-overlapping constraint, but I think it's
> possible for this to be more general.
Sounds good

> The idea is to make an array in shared memory with size equal to
> max_connections. Each element of the array would hold the oid of an
> index, and a tid.

Just notice: due to GiST's organization it can store type not the same as in
indexed column and even type is the same, value may be lossy compressed. So
comparing two values from index it's possible to say that they are not
overlapped or MAY be overlapped.

> Then, search the GiST index using the same function to determine if
> conflicts exist in the index. If conflicts exist in the index, check the
> visibility information for the tuple and proceed, wait or abort (in the
> same way as above). If no conflicts exist, insert.
>

Again, table for matching two value by equality and overlap operator, each value
is taken from index or from heap:
| heap value | index value
------------+-------------+-------------
heap value | yes | yes(lossy!)
index value | yes(lossy!) |yes-equality, no-overlap

equality(index value, index value) - is a GISTSTATE->equalFn method.

Next, you will need to define by some ways about semantic meaning of operation,
i.e. '=' - is equal operation, '&&' - is overlap operation.
Equal operation can be determined by corresponding BTree opclass, but I don't
have an idea how to determine overlap operation.

> This should work fine for multi-column indexes where the constraints for
> each column are different. For instance, unique and non-overlapping
> could be mixed.

Hmm, isn't it too complicated? Look, you suggest something like following (Btree
example):
CREATE INDEX idx ON table USING BTREE ( col1, col2 unique);

Is col2 should be unique across the whole index or just for the same col1?

--
Teodor Sigaev E-mail: teodor(at)sigaev(dot)ru
WWW: http://www.sigaev.ru/

> This can be solved by my proposal, but I just don't know how it would
> apply to something like GIN, for instance. It could replace the unique
Hmm, your proposal isn't applicable to GIN, because GIN stores a lot of keys for
only one value to be indexed.

> being inserted by other concurrent transactions, and those values can
> be variable in size. What other mechanism do we have to share those
> variable-sized values among several backends?
In theory, any indexed value in index (for GiST, after compression) should fit
into page at least.

--
Teodor Sigaev E-mail: teodor(at)sigaev(dot)ru
WWW: http://www.sigaev.ru/

On Tue, 2008-06-10 at 16:59 +0400, Teodor Sigaev wrote:
> > This can be solved by my proposal, but I just don't know how it would
> > apply to something like GIN, for instance. It could replace the unique
> Hmm, your proposal isn't applicable to GIN, because GIN stores a lot of keys for
> only one value to be indexed.

Right. I can't think of a good reason to constrain a GIN index, but I
think it is possible using this scheme.

> > being inserted by other concurrent transactions, and those values can
> > be variable in size. What other mechanism do we have to share those
> > variable-sized values among several backends?
> In theory, any indexed value in index (for GiST, after compression) should fit
> into page at least.
>

So are you saying we should dedicate one page multiplied by
max_connections in shared memory? It's possible to do it that way, but
we still have to check the heap for visibility information, at least.

Regards,
Jeff Davis

>> In theory, any indexed value in index (for GiST, after compression) should fit
>> into page at least.
> So are you saying we should dedicate one page multiplied by
> max_connections in shared memory? It's possible to do it that way, but

Yes, we could. Storing index keys in shared memory allows minimize access to
heap. So, when new key is coming, you should check overlap with each stored keys
in shared memory. For each check result will be one of the following points:
- keys are not overlapped: you don't need to go to the heap. Suppose, this will
be most frequent result in typical usecases.
- keys may be overlapped (consistentFn returns true and needRecheck flag is
true): you should go to the heap to consult with original value (may be
visibility too)
- keys are overlapped (consistentFn returns true and needRecheck flag is false):
heap visit is needed only for checking visibility

If you don't store keys in shared memory, then you should consult with heap for
each stored key.
--
Teodor Sigaev E-mail: teodor(at)sigaev(dot)ru
WWW: http://www.sigaev.ru/