WIP: generalized index constraints

On Sun, 2009-07-05 at 17:28 -0700, Jeff Davis wrote:

This is a follow up to my old proposal here:

http://archives.postgresql.org/pgsql-hackers/2008-06/msg00404.php

Any input is appreciated (design problems, implementation, language
ideas, or anything else). I'd like to get it into shape for the July
15 commitfest if no major problems are found.

I was concerned that your definition of concurrently inserted didn't
seem to match the size of the shared memory array required.

How will you cope with a large COPY? Surely there can be more than one
concurrent insert from any backend?

It would be useful to see a real example of what this can be used for.

I think it will be useful to separate the concepts of a constraint from
the concept of an index. It seems possible to have a UNIQUE constraint
that doesn't help at all in locating rows, just in proving that the rows
are unique.

--
Simon Riggs www.2ndQuadrant.com
PostgreSQL Training, Services and Support

On Mon, Jul 6, 2009 at 11:56 AM, Simon Riggs<simon@2ndquadrant.com> wrote:

How will you cope with a large COPY? Surely there can be more than one
concurrent insert from any backend?

He only needs to handle inserts for the period they're actively being
inserted into the index. Once they're in the index he'll find them
using the index scan. In other words this is all a proxy for the way
btree locks index pages while it looks for a unique key violation.

I'm a bit concerned about the use of tid. You might have to look at a
lot of heap pages to check for conflicts. I suppose they're almost
certainly all in shared memory though. Also, it sounds like you're
anticipating the possibility of dead entries in the array but if you
do then you need to store the xmin also to protect against a tuple
that's been vacuumed and had its line pointer reused since. But I
don't see the necessity for that anyways since you can just clean up
the entry on abort.

--
greg
http://mit.edu/~gsstark/resume.pdf

On Mon, Jul 06, 2009 at 11:56:41AM +0100, Simon Riggs wrote:

On Sun, 2009-07-05 at 17:28 -0700, Jeff Davis wrote:

This is a follow up to my old proposal here:

http://archives.postgresql.org/pgsql-hackers/2008-06/msg00404.php

Any input is appreciated (design problems, implementation,
language ideas, or anything else). I'd like to get it into shape
for the July 15 commitfest if no major problems are found.

I was concerned that your definition of concurrently inserted didn't
seem to match the size of the shared memory array required.

How will you cope with a large COPY? Surely there can be more than
one concurrent insert from any backend?

It would be useful to see a real example of what this can be used
for.

Constraints like "these intervals can't overlap" would be one. It's
handy in calendaring applications, for example.

I think it will be useful to separate the concepts of a constraint
from the concept of an index. It seems possible to have a UNIQUE
constraint that doesn't help at all in locating rows, just in
proving that the rows are unique.

Interesting idea. Are you thinking of this in terms of things the
planner can do once it knows a set is all distinct values, or...?

Cheers,
David.
--
David Fetter <david@fetter.org> http://fetter.org/
Phone: +1 415 235 3778 AIM: dfetter666 Yahoo!: dfetter
Skype: davidfetter XMPP: david.fetter@gmail.com

Remember to vote!
Consider donating to Postgres: http://www.postgresql.org/about/donate

On Mon, 2009-07-06 at 12:28 +0100, Greg Stark wrote:

He only needs to handle inserts for the period they're actively being
inserted into the index. Once they're in the index he'll find them
using the index scan. In other words this is all a proxy for the way
btree locks index pages while it looks for a unique key violation.

Exactly, that was my design:

/*
* We have to find all tuples, even those not visible
* yet. Other transactions may have inserted many tuples (or
* the transaction might be a prepared transaction), so there
* may be some tuples that are not in the shared memory
* structure and not visible.
*/

I'm a bit concerned about the use of tid. You might have to look at a
lot of heap pages to check for conflicts. I suppose they're almost
certainly all in shared memory though.

That was my hope.

The 8.4 bulk insert code might defeat that to some degree, however.
Maybe that could be disabled when inserting into an index with
constraints? I didn't think about it before, but the bulk insert buffer
ring would affect unique btrees, too, right?

Also, it sounds like you're
anticipating the possibility of dead entries in the array but if you
do then you need to store the xmin also to protect against a tuple
that's been vacuumed and had its line pointer reused since. But I
don't see the necessity for that anyways since you can just clean up
the entry on abort.

Can you tell me a little more specifically the problem you're worried
about? If the tuple has been VACUUMed and removed, then the TID search
will either find a tuple, and do a spurious constraint check against it;
or not find a tuple, and just move on.

I could have the commit and abort paths clear the entry, which might
optimize away some of the TransactionIdIsInProgress() calls for
transactions that ended normally. But that didn't strike me as a big
cost compared to the index scan.

Regards,
Jeff Davis

On Mon, 2009-07-06 at 11:56 +0100, Simon Riggs wrote:

I think it will be useful to separate the concepts of a constraint from
the concept of an index. It seems possible to have a UNIQUE constraint
that doesn't help at all in locating rows, just in proving that the rows
are unique.

That would be interesting. Do you have a use case? Checking the
constraint would surely be slower in a lot of cases.

I could imagine different constraint-checking schemes that could be fast
against a heap. For instance, if it's greater than the max or less than
the min value, that would be cheap to check. That might be an
interesting way to handle the constraint for a sequence-generated
column, or timestamp column that is always ascending.

However, the problem is I don't see a lot of room for a practical use
case. In the above situations, you'd almost certainly want indexes
anyway: what's the point of a sequence number unless you're going to do
lookups? And if you have an ascending timestamp column, I would think
that you might do range lookups occasionally (which will be even better
because the heap will be clustered).

Regards,
Jeff Davis

On Mon, 2009-07-06 at 07:30 -0700, David Fetter wrote:

It would be useful to see a real example of what this can be used
for.

Constraints like "these intervals can't overlap" would be one. It's
handy in calendaring applications, for example.

Exactly, you already know my use case ;) My goal is a "temporal key",
where you can't have overlapping intervals of time, e.g. the constraint
"nobody can be two places at the same time".

I think it will be useful to separate the concepts of a constraint
from the concept of an index. It seems possible to have a UNIQUE
constraint that doesn't help at all in locating rows, just in
proving that the rows are unique.

Interesting idea. Are you thinking of this in terms of things the
planner can do once it knows a set is all distinct values, or...?

I think that's an orthogonal idea.

It's a good idea though, I would like the planner to be smarter about
those kinds of things. A simple example is that if a table has a
non-partial unique constraint anywhere, then "select * from foo union
select * from foo" can be transformed into "select * from
foo" (eliminating the expensive union).

Regards,
Jeff Davis

On Mon, Jul 6, 2009 at 4:57 PM, Jeff Davis<pgsql@j-davis.com> wrote:

Exactly, you already know my use case ;) My goal is a "temporal key",
where you can't have overlapping intervals of time, e.g. the constraint
"nobody can be two places at the same time".

Incidentally to handle non-overlapping ranges you don't need GIST, you
can actually use a plain btree. Since there are no overlapping ranges
the ranges have a complete ordering and you can get that by just
sorting by either endpoint. To enforce the constraint you only have to
compare with the previous and following element in the btree.

--
greg
http://mit.edu/~gsstark/resume.pdf

On Mon, 2009-07-06 at 17:02 +0100, Greg Stark wrote:

On Mon, Jul 6, 2009 at 4:57 PM, Jeff Davis<pgsql@j-davis.com> wrote:

Exactly, you already know my use case ;) My goal is a "temporal key",
where you can't have overlapping intervals of time, e.g. the constraint
"nobody can be two places at the same time".

Incidentally to handle non-overlapping ranges you don't need GIST, you
can actually use a plain btree. Since there are no overlapping ranges
the ranges have a complete ordering and you can get that by just
sorting by either endpoint. To enforce the constraint you only have to
compare with the previous and following element in the btree.

What if you have an entire index full of overlapping dead tuples, and a
few live ones? How would search work?

Regards,
Jeff Davis

On Mon, 2009-07-06 at 08:50 -0700, Jeff Davis wrote:

On Mon, 2009-07-06 at 11:56 +0100, Simon Riggs wrote:

I think it will be useful to separate the concepts of a constraint from
the concept of an index. It seems possible to have a UNIQUE constraint
that doesn't help at all in locating rows, just in proving that the rows
are unique.

That would be interesting. Do you have a use case? Checking the
constraint would surely be slower in a lot of cases.

I could imagine different constraint-checking schemes that could be fast
against a heap. For instance, if it's greater than the max or less than
the min value, that would be cheap to check. That might be an
interesting way to handle the constraint for a sequence-generated
column, or timestamp column that is always ascending.

Yes.

However, the problem is I don't see a lot of room for a practical use
case. In the above situations, you'd almost certainly want indexes
anyway: what's the point of a sequence number unless you're going to do
lookups? And if you have an ascending timestamp column, I would think
that you might do range lookups occasionally (which will be even better
because the heap will be clustered).

In many cases, people add unique indexes solely to allow replication to
work correctly. The index itself may never be used, especially in high
volume applications.

How do you handle uniqueness within a stream? Presumably it is possible
and useful to have a stream of data that can be guaranteed unique, yet a
stream would never be uniquely targeted for lookups because of the
volume of data involved.

--
Simon Riggs www.2ndQuadrant.com
PostgreSQL Training, Services and Support

On Mon, Jul 6, 2009 at 6:20 PM, Jeff Davis<pgsql@j-davis.com> wrote:

On Mon, 2009-07-06 at 17:02 +0100, Greg Stark wrote:

On Mon, Jul 6, 2009 at 4:57 PM, Jeff Davis<pgsql@j-davis.com> wrote:

Exactly, you already know my use case ;) My goal is a "temporal key",
where you can't have overlapping intervals of time, e.g. the constraint
"nobody can be two places at the same time".

Incidentally to handle non-overlapping ranges you don't need GIST, you
can actually use a plain btree. Since there are no overlapping ranges
the ranges have a complete ordering and you can get that by just
sorting by either endpoint. To enforce the constraint you only have to
compare with the previous and following element in the btree.

What if you have an entire index full of overlapping dead tuples, and a
few live ones? How would search work?

I should clarify I didn't mean you could implement it in SQL using
Postgres btrees. I just meant that a tree data structure was
sufficient, you don't need the power of GIST. It's probably easier to
implement it in GIST in Postgres since it's there though.

So it would work just like regular btrees, you only consider it a
conflict if there's a live value that conflicts.

--
greg
http://mit.edu/~gsstark/resume.pdf

On Mon, 2009-07-06 at 18:27 +0100, Simon Riggs wrote:

In many cases, people add unique indexes solely to allow replication to
work correctly. The index itself may never be used, especially in high
volume applications.

Interesting. Maybe we should at least try to leave room for this feature
to be added later. I agree that, from a theoretical perspective,
requiring a UNIQUE constraint to use an index is wrong. For one thing,
you can't ensure the uniqueness without defining some total order
(although you can define an arbitrary total order for cases with no
meaningful total order).

How do you handle uniqueness within a stream? Presumably it is possible
and useful to have a stream of data that can be guaranteed unique, yet a
stream would never be uniquely targeted for lookups because of the
volume of data involved.

[ Simon is asking me because I work for Truviso, but my response is not
officially from Truviso ]

There are a few cases worth mentioning here. First, if you have a stream
that's backed by a table, you can use a table constraint. Second, you
might choose to have an "in-order" constraint (not necessary, the system
can fix out-of-order data), which could be a unique constraint that's
very cheap to test.

Additionally, this is not strictly a constraint, but if you have
downstream operators, like COUNT(DISTINCT...), that can be seen as being
similar to a constraint. These will often be over a limited span of
time, say, a minute or an hour, and we can keep the necessary state. If
there are a huge number of distinct values there, then it's a challenge
to avoid keeping a lot of state.

There are a few other specialized methods that we can use for specific
use-cases.

Regards,
Jeff Davis

CREATE INDEX test_idx ON test USING gist
(i CONSTRAINT =, c CONSTRAINT &&);

which would avoid the need for updating the catalog, of course.

Hmm, looks like "index"-fied table's constrains

--
Teodor Sigaev E-mail: teodor@sigaev.ru
WWW: http://www.sigaev.ru/

Jeff Davis <pgsql@j-davis.com> writes:

On Mon, 2009-07-06 at 18:27 +0100, Simon Riggs wrote:

In many cases, people add unique indexes solely to allow replication to
work correctly. The index itself may never be used, especially in high
volume applications.

Interesting. Maybe we should at least try to leave room for this feature
to be added later. I agree that, from a theoretical perspective,
requiring a UNIQUE constraint to use an index is wrong. For one thing,
you can't ensure the uniqueness without defining some total order
(although you can define an arbitrary total order for cases with no
meaningful total order).

This seems a bit pointless. There is certainly not any use case for a
constraint without an enforcement mechanism (or at least none the PG
community is likely to consider legitimate ;-)). And it's not very
realistic to suppose that you'd check a constraint by doing a seqscan
every time. Therefore there has to be an index underlying the
constraint somehow. Jeff's complaint about total order is not an
argument against having an index, it's just pointing out that btree is
not the only possible type of index. It's perfectly legitimate to
imagine using a hash index to enforce uniqueness, for example. If hash
indexes had better performance we'd probably already have been looking
for a way to do that, and wanting some outside-the-AM mechanism for it
so we didn't have to duplicate code from btree.

Also, if hash indexes were a realistic alternative to btree for this,
we'd already have come up against the problem that the CONSTRAINT syntax
doesn't provide any way to specify what kind of index you want to use
underneath the constraint. I think it might be interesting to turn
around Jeff's syntax sketch and provide a way to say that a CONSTRAINT
declaration should depend on some previously added index, eg
something like

ALTER TABLE tab ADD CONSTRAINT UNIQUE (col1, col2) USING index

Not sure how that squares exactly with the question of variant
definitions of uniqueness semantics (as opposed to purely implementation
decisions like hash vs btree). But it's a different way to come at it.

regards, tom lane

On Tue, 2009-07-07 at 13:22 -0400, Tom Lane wrote:

ALTER TABLE tab ADD CONSTRAINT UNIQUE (col1, col2) USING index

This would be very useful, though perhaps only because we do not have
REINDEX CONCURRENTLY.

It is likely to be useful in the future to allow an index with N
columns, yet which can provide uniqueness with < N of those columns.
This capability is known as covered indexes and will be important if
Heikki writes his index-only scan code.

--
Simon Riggs www.2ndQuadrant.com
PostgreSQL Training, Services and Support

On Tue, 2009-07-07 at 13:22 -0400, Tom Lane wrote:

Jeff Davis <pgsql@j-davis.com> writes:

On Mon, 2009-07-06 at 18:27 +0100, Simon Riggs wrote:

In many cases, people add unique indexes solely to allow replication to
work correctly. The index itself may never be used, especially in high
volume applications.

Interesting. Maybe we should at least try to leave room for this feature
to be added later. I agree that, from a theoretical perspective,
requiring a UNIQUE constraint to use an index is wrong. For one thing,
you can't ensure the uniqueness without defining some total order
(although you can define an arbitrary total order for cases with no
meaningful total order).

This seems a bit pointless. There is certainly not any use case for a
constraint without an enforcement mechanism (or at least none the PG
community is likely to consider legitimate ;-)). And it's not very
realistic to suppose that you'd check a constraint by doing a seqscan
every time. Therefore there has to be an index underlying the
constraint somehow.

I think the idea has been misconstrued.

Obviously a constraint requires an enforcement mechanism. That doesn't
imply that the enforcement mechanism must be fully usable as an index.

The example being discussed was enforcing uniqueness on monotonically
increasing columns. If we knew that a column value was GENERATED ALWAYS
using a sequence, then we could simply skip the uniqueness check
altogether. No index, yet an enforced unique constraint.

Yes, we would need to understand the relationship between the sequence
and the table and throw an error in certain sequence update cases (and
we may need to check those with a seq scan). But that seems a small
price to pay for the avoidance of a potentially very large index that
may have no purpose.

--
Simon Riggs www.2ndQuadrant.com
PostgreSQL Training, Services and Support

On Tue, Jul 7, 2009 at 6:22 PM, Tom Lane<tgl@sss.pgh.pa.us> wrote:

This seems a bit pointless.  There is certainly not any use case for a
constraint without an enforcement mechanism (or at least none the PG
community is likely to consider legitimate ;-)).  And it's not very
realistic to suppose that you'd check a constraint by doing a seqscan
every time.  Therefore there has to be an index underlying the
constraint somehow.

I'm not entirely convinced that running a full scan to enforce
constraints is necessarily such a crazy idea. It may well be the most
efficient approach after a major bulk load. And consider a read-only
database where the only purpose of the constraint is to inform the
optimizer that it can trust the property to hold.

That said this seems like an orthogonal issue to me.

Jeff's complaint about total order is not an
argument against having an index, it's just pointing out that btree is
not the only possible type of index.  It's perfectly legitimate to
imagine using a hash index to enforce uniqueness, for example.  If hash
indexes had better performance we'd probably already have been looking
for a way to do that, and wanting some outside-the-AM mechanism for it
so we didn't have to duplicate code from btree.

I'm a bit at a loss why we need this extra data structure though. The
whole duplicated code issue seems to me to be one largely of code
structure. If we hoisted the heap-value rechecking code out of the
btree AM then the hash AM could reuse it just fine.

Both the hash and btree AMs would have to implement some kind of
"insert-unique-key" operation which would hold some kind of lock
preventing duplicate unique keys from being inserted but both btree
and hash could implement that efficiently by locking one page or one
hash value.

GIST would need something like this "store the key value or tid in
shared memory" mechanism. But that could be implemented as an external
facility which GIST then made use of -- just the way every part of the
system makes use of other parts. It doesn't mean we have to make
"prevent concurrent unique inserts" not the responsibility of the AM
which knows best how to handle that.

--
greg
http://mit.edu/~gsstark/resume.pdf

On Tue, 2009-07-07 at 18:36 +0100, Simon Riggs wrote:

On Tue, 2009-07-07 at 13:22 -0400, Tom Lane wrote:
It is likely to be useful in the future to allow an index with N
columns, yet which can provide uniqueness with < N of those columns.
This capability is known as covered indexes and will be important if
Heikki writes his index-only scan code.

My patch offers this capability, and the language I suggested would
support it.

In the current version of the patch, just use InvalidStrategy (0)
instead of, say, BTEqualStrategyNumber (3) for the attributes that you
don't want to be a part of the constraint. Some of the proper error
checking is not done yet, but it will work.

Regards,
Jeff Davis

Jeff Davis <pgsql@j-davis.com> writes:

On Tue, 2009-07-07 at 18:36 +0100, Simon Riggs wrote:

On Tue, 2009-07-07 at 13:22 -0400, Tom Lane wrote:
It is likely to be useful in the future to allow an index with N
columns, yet which can provide uniqueness with < N of those columns.
This capability is known as covered indexes and will be important if
Heikki writes his index-only scan code.

My patch offers this capability, and the language I suggested would
support it.

In the current version of the patch, just use InvalidStrategy (0)
instead of, say, BTEqualStrategyNumber (3) for the attributes that you
don't want to be a part of the constraint. Some of the proper error
checking is not done yet, but it will work.

I don't think this even approximates the need --- in particular it's not
clear what the semantics of combination across different index columns
are. I assume you've hot-wired it so that several BTEqualStrategyNumber
columns will work like a normal multicolumn uniqueness constraint (IOW
it's okay as long as at least one column is NULL or isn't equal). But
I'm not at all sure that's what I'd want for some other operator type.

Also, what happens if you want to use the same index to support more
than one logical constraint? This is impossible if you put the
information into pg_index, I think.

regards, tom lane

On Tue, 2009-07-07 at 14:57 -0400, Tom Lane wrote:

I don't think this even approximates the need --- in particular it's not
clear what the semantics of combination across different index columns
are. I assume you've hot-wired it so that several BTEqualStrategyNumber
columns will work like a normal multicolumn uniqueness constraint (IOW
it's okay as long as at least one column is NULL or isn't equal). But
I'm not at all sure that's what I'd want for some other operator type.

If any input attributes are NULL, the constraint automatically succeeds
(I think that follows the SQL philosophy). Perhaps we should be able to
override this behavior somehow?

Now, for each attribute where a constraint is defined, it becomes a new
scan key used in the index lookup to enforce the constraint. So, the
more attributes in the constraint, the more permissive the constraint
(just like UNIQUE).

I can't think of another good interpretation of the constraint. If a
constraint on (x,y) meant "x is unique, and y is unique", it would be
hard to scan the index for y's uniqueness. If you want to say that both
are independently unique, I believe that requires two indexes, and so it
would probably be best to just require the constraints to be specified
separately. Thoughts?

Also, what happens if you want to use the same index to support more
than one logical constraint? This is impossible if you put the
information into pg_index, I think.

I like the idea to store the information outside of pg_index. It means
that I don't have to build the index and check the constraint at the
same time. It would be more like adding a CHECK constraint.

Regards,
Jeff Davis