Say you are writing an online reservation system. The first requirement you’ll encounter is that no two reservations may overlap (i.e. no schedule conflicts). But how do you prevent that?

It’s worth thinking about your solution carefully. My claim is that no existing SQL DBMS has a good solution to this problem before PostgreSQL 9.0, which has just been released. This new release includes a feature called Exclusion Constraints (authored by me), which offers a good solution to a class of problems that includes the “schedule conflict” problem.

I previously wrote a two part series (Part 1 and Part 2) on this topic. Chances are that you’ve run into a problem similar to this at one time or another, and these articles will show you the various solutions that people usually employ in the real world, and the serious problems and limitations of those approaches.

The rest of this article will be a brief introduction to Exclusion Constraints to get you started using a much better approach.

First, install PostgreSQL 9.0 (the installation instructions are outside the scope of this article), and launch psql.

Then, install two modules: “temporal” (which provides the PERIOD data type and associated operators) and “btree_gist” (which provides btree functionality via GiST).

Before installing these modules, make sure that PostgreSQL 9.0 is installed and that the 9.0 pg_config is in your PATH environment variable. Also, $SHAREDIR meas the directory listed when you run pg_config --sharedir.

To install Temporal PostgreSQL:

1. download the tarball
2. unpack the tarball, go into the directory, and type “make install“
3. In psql, type: \i $SHAREDIR/contrib/period.sql

To install BTree GiST (these directions assume you installed from source, some packages may help here, like Ubuntu’s “postgresql-contrib” package):

1. Go to the postgresql source “contrib” directory, go to btree_gist, and type “make install“.
2. In psql, type: \i $SHAREDIR/contrib/btree_gist.sql

Now that you have those modules installed, let’s start off with some basic Exclusion Constraints:

DROP TABLE IF EXISTS a;
CREATE TABLE a(i int);
ALTER TABLE a ADD EXCLUDE (i WITH =);

That is identical to a UNIQUE constraint on a.i, except that it uses the Exclusion Constraints mechanism; it even uses a normal BTree to enforce it. The performance will be slightly worse because of some micro-optimizations for UNIQUE constraint, but only slightly, and the performance characteristics should be the same (it’s just as scalable). Most importantly, it behaves the same under high concurrency as a UNIQUE constraint, so you don’t have to worry about excessive locking. If one person inserts 5, that will prevent other transactions from inserting 5 concurrently, but will not interfere with a transaction inserting 6.

Let’s take apart the syntax a little. The normal BTree is the default, so that’s omitted. The (i WITH =) is the interesting part, of course. It means that one tuple TUP1 conflicts with another tuple TUP2 if TUP1.i = TUP2.i. No two tuples may exist in the table if they conflict. In other words, there are no two tuples TUP1 and TUP2 in the table, such that TUP1.i = TUP2.i. That’s the very definition of UNIQUE, so that shows the equivalence. NULLs are always permitted, just like with UNIQUE constraints.

Now, let’s see if they hold up for multi-column constraints:

DROP TABLE IF EXISTS a;
CREATE TABLE a(i int, j int);
ALTER TABLE a ADD EXCLUDE (i WITH =, j WITH =);

The conditions for a conflicting tuple are ANDed together, just like UNIQUE. So now, in order for two tuples to conflict, TUP1.i = TUP2.i AND TUP1.j = TUP2.j. This is strictly a more permissive constraint, because conflicts require both conditions to be met. Therefore, this is identical to a UNIQUE constraint on (a.i, a.j).

What can we do that UNIQUE can’t? Well, for starters we can use something other than a normal BTree, such as Hash or GiST (for the moment, GIN is not supported, but that’s only because GIN doesn’t support the full index AM API; amgettuple in particular):

DROP TABLE IF EXISTS a;
CREATE TABLE a(i int, j int);
ALTER TABLE a ADD EXCLUDE USING gist (i WITH =, j WITH =);
-- alternatively using hash, which doesn't support
-- multi-column indexes at all
ALTER TABLE a ADD EXCLUDE USING hash (i WITH =);

So now we can do UNIQUE constraints using hash or gist. But that’s not a real benefit, because a normal btree is probably the most efficient way to support that, anyway (Hash may be in the future, but for the moment it doesn’t use WAL, which is a major disadvantage).

The difference really comes from the ability to change the operator to something other than “=“. It can be any operator that is:

• Commutative
• Boolean
• Searchable by the given index access method (e.g. btree, hash, gist).

For BTree and Hash, the only operator that meets those criteria is “=”. But many data types (including PERIOD, CIRCLE, BOX, etc.) support lots of interesting operators that are searchable using GiST. For instance, “overlaps” (&&).

Ok, now we are getting somewhere. It’s impossible to specify the constraint that no two tuples contain values that overlap with eachother using a UNIQUE constraint; but it is possible to specify such a constraint with an Exclusion Constraint! Let’s try it out.

DROP TABLE IF EXISTS b;
CREATE TABLE b (p PERIOD);
ALTER TABLE b ADD EXCLUDE USING gist (p WITH &&);
INSERT INTO b VALUES('[2009-01-05, 2009-01-10)');
INSERT INTO b VALUES('[2009-01-07, 2009-01-12)'); -- causes ERROR

Now, try out various combinations (including COMMITs and ABORTs), and try with concurrent sessions also trying to insert values. You’ll notice that potential conflicts cause transactions to wait on eachother (like with UNIQUE) but non-conflicting transactions proceed unhindered. A lot better than LOCK TABLE, to say the least.

To be useful in a real situation, let’s make sure that the semantics extend nicely to a more complete problem. In reality, you generally have several exclusive resources in play, such as people, rooms, and time. But out of those, “overlaps” really only makes sense for time (in most situations). So we need to mix these concepts a little.

CREATE TABLE reservation(room TEXT, professor TEXT, during PERIOD);

-- enforce the constraint that the room is not double-booked
ALTER TABLE reservation
    ADD EXCLUDE USING gist
    (room WITH =, during WITH &&);

-- enforce the constraint that the professor is not double-booked
ALTER TABLE reservation
    ADD EXCLUDE USING gist
   (professor WITH =, during WITH &&);

Notice that we actually need to enforce two constraints, which is expected because there are two time-exclusive resources: professors and rooms. Multiple constraints on a table are ORed together, in the sense that an ERROR occurs if any constraint is violated. For the academic readers out there, this means that exclusion constraint conflicts are specified in disjunctive normal form (consistent with UNIQUE constraints).

The semantics of Exclusion Constraints extend in a clean way to support this mix of atomic resources (rooms, people) and resource ranges (time). Try it out, again with a mix of concurrency, commits, aborts, conflicting and non-conflicting reservations.

Exclusion constraints allow solving this class of problems quickly (in a couple lines of SQL) in a way that’s safe, robust, generally useful across many applications in many situations, and with higher performance and better scalability than other solutions.

Additionally, Exclusion Constraints support all of the advanced features you’d expect from a system like Postgres9: deferrability, applying the constraint to only a subset of the table (allows a WHERE clause), or using functions/expressions in place of column references.