Thread: non-overlapping ranges constraint?

Suppose I have a table

  CREATE TABLE range (min int NOT NULL, max int NOT NULL, otherdata TEXT);

I want to make sure that no two tuples in this table describe
overlapping ranges, that is:

  tuple1.min<=tuple2.max AND tuple1.max>=tuple2.min

I arrived at doing the checking using a custom function:

  CREATE FUNCTION range_available(int, int) RETURNS bool AS
  'LOCK TABLE range;
  SELECT count(*)=0 FROM range WHERE min<= $2 AND max>= $1
    AND min != $1 AND max != $2;
  ' LANGUAGE 'sql';

  ALTER TABLE range ADD CONSTRAINT check_range
    CHECK (range_available(min, max));

This solves the probelm at hand but I have severe performance
problems. Inserts/deletes on the table are rare, as are modifications
to min and max, but the table is subject to mass-updates touching
otherdata and it appears that the check constraint is executed even
if neither min nor max are modified. Basically this turns updating
into an O(n^2) operation, as neither min<= $2 nor max >= $1
are particularly selective.

My question is whether there is a more elegant solution; since the
problem is essentially a geometric one, perhaps people storing
geometric objects know a generic solution? Additional fact:
in the "real" problem both min and max are of type timestamp.

Best regards
--
Helge Bahmann <bahmann@math.tu-freiberg.de>             /| \__
Network admin, systems programmer                      /_|____\
                                                     _/\ |   __)
$ ./configure                                        \\ \|__/__|
checking whether build environment is sane... yes     \\/___/ |
checking for AIX... no (we already did this)            |

On Fri, Feb 01, 2002 at 12:17:42PM +0100, Helge Bahmann wrote:
> This solves the probelm at hand but I have severe performance
> problems. Inserts/deletes on the table are rare, as are modifications
> to min and max, but the table is subject to mass-updates touching
> otherdata and it appears that the check constraint is executed even
> if neither min nor max are modified. Basically this turns updating
> into an O(n^2) operation, as neither min<= $2 nor max >= $1
> are particularly selective.

A maybe not elegant but performant solution:

Use a BEFORE INSERT/UPDATE TRIGGER, which checks if min resp. max were
modified and calls your range checking function only if necessary.

> My question is whether there is a more elegant solution; since the
> problem is essentially a geometric one, perhaps people storing
> geometric objects know a generic solution? Additional fact:
> in the "real" problem both min and max are of type timestamp.

Even if there is a more elegant solution, I would suppose to use a
BEFORE TRIGGER and not a CHECK constraint. The `more elegant'
solution, if any, would be based on certain sophisticated
indices. Index-based checks maybe would be more performant than your
simple check method, but no checks at all are even more performant ;-)

--
Holger Krug
hkrug@rationalizer.com