In the last article, I argued that:
- A schedule conflict is a typical business problem.
- The later you try to resolve a schedule conflict, the more costly it is to resolve.
- In particular, there is a big jump in the cost the moment after conflicting data is recorded.
- Therefore, it’s best for the DBMS itself to enforce the constraint, because only the DBMS can avoid the conflict effectively before the conflict is recorded.
Then, I opened up a discussion to see how people are dealing with these schedule conflicts. In the comments I received at the end of the article, as well as other anecdotes from conferences, user groups, mailing lists, and my own experience, the solutions fall into a few categories:
- The rate of conflicts is so low that the costs are not important. For instance, you may make 0.1% of your customers unhappy, and need to refund them, but perhaps that’s a cost you’re willing to pay.
- The application receives so few requests that performance is not an object, and serialization of all requests is a viable option. The serialization is done using big locks and a read-check-write cycle. Even if performance is not an object, these applications sometimes run into maintenance problems or unexpected outages because of the big locks required.
- You can break the time slices into manageable chunks, e.g. one day chunks aligned at midnight. This kind of solution is highly specific to the business, reduces the flexibility of the business, and often requires a substantial amount of custom, error-prone procedural code.
- Complex procedural code: usually a mix of application code, functions in the DBMS, row-level locking, static data in tables that only exists for the purposes of row-level locks, etc. This kind of solution is generally very specific to the application and the business, requires lots of very error-prone custom procedural code, is difficult to adequately test, and it’s hard to understand what’s going on in the system at any given time. Hunting down sporadic performance problems would be a nightmare.
Those solutions just aren’t good enough. We use relational database systems because they are smart, declarative, generally useful for many problems, and maintainable (Note: these principles contrast with NoSQL, which is moving in the opposite direction — more on that in another article).
[UPDATE: The following project has been committed for the next release of PostgreSQL; the feature is now called "Exclusion Constraints"; and the new version of PostgreSQL will be called 9.0 (not 8.5). See the documentation under the heading "EXCLUDE".]
The project that I’ve been working on for PostgreSQL 8.5 is called “Operator Exclusion Constraints“. These are a new type of constraint that most closely resembles the UNIQUE constraint, because one tuple can preclude the existence of other tuples. With a UNIQUE constraint on attribute A of a table with attributes (A, B, C), the existence of the tuple (5, 6, 7) precludes the existence of any tuple (5, _, _) in that table at the same time. This is different from a foreign key, which requires the existence of a tuple in another table; and different from a CHECK constraint which rejects tuples independently from any other tuple in any table (and the same goes for NOT NULL).
The same semantics as a UNIQUE constraint can be easily specified as an Operator Exclusion Constraint, with a minor performance penalty at insert time (one additional index search, usually only touching pages that are already in cache). Exclusion constraints are more general than UNIQUE, however. For instance, with a complex type such as CIRCLE, you can specify that no two circles in a table overlap — which is a constraint that is impossible to specify otherwise (without resorting to the poor solutions mentioned above).
This applies to temporal keys very nicely. First, get the PERIOD data type, which allows you a better way to work with periods of time (sets of time, really), rather than points in time. Second, you need to install the btree_gist contrib module. Then, use an exclusion constraint like so:
[UPDATE 2010-03-09: Syntax updated to reflect the version of this project committed for PostgreSQL 9.0. ]
CREATE TABLE room_reservation ( name TEXT, room TEXT, during PERIOD, EXCLUDE USING gist (room WITH =, during WITH &&) );
That will prevent two reservations on the same room from overlapping. There are a few pieces to this that require explanation:
&&is the “overlaps” operator for thePERIODdata type.USING gisttells PostgreSQL what kind of index to create to enforce this constraint. The operators must map to search strategies for this index method, and searching for overlapping periods requires a GiST index.- Because we are using GiST, we need GiST support for equality searches for the
TEXTdata type, which is the reason we need the btree_gist contrib module. - Conflicts will only occur if two tuples have equal room numbers, and overlapping periods of time for the reservation.
This solution:
- Performs well under light and heavy contention. Not quite as well as a UNIQUE constraint, but much better than the alternatives, and without the surprises you might get from using big locks. Note that the constraint will be enforced at some point, so ignoring the problem is not a high-performance alternative (interpersonal communication has higher latency than a computer).
- Is declarative. The implementation shows through a little bit — the user will know that an index is being used, for instance — but it’s a relatively simple declaration. As a consequence, it’s not very error-prone from the schema designer’s standpoint.
- Is not specific to the business. You don’t have to decide on an appropriate time slice (e.g. one hour, one day, etc.); you don’t have to try to partition locks in creative ways; you don’t have to write procedural code (in the database system or application); and you don’t have to come up with interesting ways to detect a conflict or notify the user.
Temporal keys are just one part of the support required for effective temporal data management inside the DBMS. However, it’s one of the most important pieces that requires support from the core engine, and cannot be implemented as a module.
Obviously the EXCLUDES constraint is more general, and easier for the user to implement, so that’s awesome, but I think the following solution works as well for this specific instance.
DROP TABLE IF EXISTS room_reservation CASCADE;
CREATE TABLE room_reservation (
whom TEXT NOT NULL,
room TEXT NOT NULL,
beginning TIME WITHOUT TIME ZONE NOT NULL,
until TIME WITHOUT TIME ZONE NOT NULL
);
CREATE OR REPLACE FUNCTION dont_overlap_reservations() RETURNS trigger AS $$
DECLARE
overlaps text;
BEGIN
SELECT whom INTO overlaps
FROM room_reservation
WHERE room = NEW.room
AND beginning NEW.beginning
LIMIT 1;
IF FOUND THEN
RETURN NULL;
ELSE
RETURN NEW;
END IF;
END;
$$ LANGUAGE plpgsql;
– WARNING
– multiple triggers on a single table are called in alphabetical
– order so lets name our trigger something z-ish
CREATE TRIGGER zzz_no_overlap
BEFORE INSERT OR UPDATE ON room_reservation
FOR EACH ROW
EXECUTE PROCEDURE dont_overlap_reservations();
INSERT INTO room_reservation (whom,room,beginning,until)
VALUES (‘Ashley’, ’2B’, ’8:00′, ’9:00′);
INSERT INTO room_reservation (whom,room,beginning,until)
VALUES (‘Brett’, ’2B’,’10:00′, ’13:00′);
INSERT INTO room_reservation (whom,room,beginning,until)
VALUES (‘Chris’, ’2B’,’14:00′, ’15:00′);
INSERT INTO room_reservation (whom,room,beginning,until)
VALUES (‘Dale’, ’2B’,’17:00′, ’18:00′);
INSERT INTO room_reservation (whom,room,beginning,until)
VALUES (‘Eden’, ’2B’,’12:00′, ’16:00′);
Sorry, forgot to escape the greater than and less than operators, the function should be
CREATE OR REPLACE FUNCTION dont_overlap_reservations() RETURNS trigger AS $$
DECLARE
overlaps text;
BEGIN
SELECT whom INTO overlaps
FROM room_reservation
WHERE room = NEW.room
AND beginning = NEW.beginning
LIMIT 1;
IF FOUND THEN
RETURN NULL;
ELSE
RETURN NEW;
END IF;
END;
$$ LANGUAGE plpgsql;
Plus, obviously, you would use a timestamp rather than a time,
and it’s probably a good idea to declare (room,beginning,until) as the primary key. For more than five rows an index might be useful.
Wow! I did it again!
CREATE OR REPLACE FUNCTION dont_overlap_reservations() RETURNS trigger AS $$
DECLARE
overlaps text;
BEGIN
SELECT whom INTO overlaps
FROM room_reservation
WHERE room = NEW.room
AND beginning <= NEW.until
AND until >= NEW.beginning
LIMIT 1;
IF FOUND THEN
RETURN NULL;
ELSE
RETURN NEW;
END IF;
END;
$$ LANGUAGE plpgsql;
Tom, interesting post. Good solutions thinking.
The trigger method, as described, doesn’t correctly handle concurrent inserts. That illustrates my main concern which is that there is too much code there and it is likely to have errors – I think you showed that in the number of posts taken as well. Anyhow, it is certainly slower than the in-database approach Jeff has designed.
Jeff,
PERIOD needs some more docs and test cases as well.
The docs that are there describe PERIOD as a “set” rather than as two endpoints, which is how all examples are laid out. I think a PERIOD should have two endpoints (+/- infinity included). If you have need for a more fancy datatype it can have a slightly different name. So the next() and prior() functions just look a little overcooked. Better to have just from() and to() or similar.
Think it would be useful to have the default as the first endpoint is inclusive and the second point is exclusive, so they stack together neatly by default.
Also think it would be useful to have a way to specify the granularity of the PERIOD. In many cases a period is expressed only in days, not timestamps. For example in your hotel room example you don’t book a hotel room for an exact second, you book one night at a time. Of course, some hotels do book by the hour, but very few by the second. It wouldn’t be much use for businesses to refuse a booking because there was a 10ms overlap between 2 5 day bookings – nor would anybody really want to record that detail.
So perhaps we need DATEPERIOD (2 DATEs) and TIMEPERIOD (2 TIMESTAMPs). It might be useful to be able to specify this like PERIOD(INTERVAL), so you can book holiday cottages in weeks, scaffolding by month etc.. Whatever the business needs.
Simon,
A period defines a contiguous set of values but we can define it by the end points. The defaults are inclusive start, exclusive end.
I think if you gave from() a little more thought, you’d change your mind.
I agree with you on being able to define the granularity. But my thought is that it would have to be set at the database level rather than say at the column level.
I’d like to generalize the concept so that we’ll be able to define a range of ints, dates, timestamps, numeric, etc.
Yes. I’ve been focusing on the core engine changes required, and Scott is working on the data types and their semantics.
As a default, that’s fine. But there are cases where you want an inclusive end time, as well.
Scott had the same idea. I think this can be accomplished with a CHECK constraint, like
CHECK ( first(during) = date_trunc('hour', first(during)) AND next(during) = date_trunc('hour', next(during)) )but it would be nice to make it a little easier to express.
Simon,
I don’t know if you have access to the postgresqlconference.org site. If you do check out Scott Baileys talk on his temporal extensions to Postgres:
http://www.postgresqlconference.org/2009/west/talks/temporal_data
It is based on his CHRONOS project:
http://sourceforge.net/projects/chronosdb/
The extensions cover some of the points you raised.
I tend to agree that millisecond precision might be overkill, but who is to know to what purpose Postgres will be put. I would not doubt that there is someone who would ask for this type of precision if you were to not provide it.
I know for certain that there are applications out there that definitely are down to the hour, as I found out returning my car an hour late to Avis Rent A Car. 
Anyway, I would suggest (or maybe second) the notion of finest granularity by default, and a mechanism (as you propose), to back off on the precision as needed.
One concern I have for the PERIOD data type is the issue of whether the interval represented is open or closed i.e. is the endpoint included in the set of times ? In maths
intervals are represented using brackets (3..4) – open, doesn’t include 3 or 4, just times in between; [3..4] closed, the set of times explicitly includes 3 and 4 or mixed (3..4] 3 is not included but 4 is.
This is important since in a schedule two appointments will have a gap between them if the intervals are open (2..4),(4..6) implies nothing scheduled at 4 or will overlap if tey are closed [2..4],[4..6] double booking at 4. The correct solution is to use mixed intervals e.g (2..4], (4..6] now the complete interval is covered but there is no overlap.
There are many other cases where this is an issue, in fact it is an issue for any grouped data from a continuous set. If we want temporal keys to be sound we would need a solution that caters for this.
The type input function reads the inclusivity/exclusivity as you would expect. [2009-01-01-2009-02-01) does not include the final endpoint, but does include the starting point. (2009-01-01, 2009-02-01] does not include the start point but does include the end point. () and [] are also allowed.