Thread: 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@j-davis.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@j-davis.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@j-davis.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@sigaev.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@sigaev.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 consultwith original value (may be visibility too) - keys are overlapped (consistentFn returns true and needRecheck flag is false): heap visit is needed only for checkingvisibility If you don't store keys in shared memory, then you should consult with heap for each stored key. -- Teodor Sigaev E-mail: teodor@sigaev.ru WWW: http://www.sigaev.ru/