Tuesday, November 4, 2008

Fuzzy date matching in PostgreSQL

As part of one of my side-projects, I wanted a way for users of a web site to search for events by date, but with some flexibility. I also wanted users who are creating events to be able to express uncertainty about the dates on which they happened.
For example, if I record an event that happened sometime in September 1998, I can say it happened on September 15th, 1998 +/- 15 days. That should then be included in the results of a query for events that happened on October 1st, 1998 +/ 1 month, or June 1st, 1998 +/- 6 months, or even September 10th, 1998 +/- 1 day. An exact date would be represented as +/- 0 days.
One way to visualise these is as line segments on a literal date line, stretching from the past into the future, with a mark per day. PostgreSQL's spatial types can be used to represent this in an indexable way. First of all, we'll create a composite type to represent fuzzy dates:
CREATE TYPE fuzzydate AS (midpoint date, fuzziness interval);
The midpoint and fuzziness fields should be self-explanatory. Next, we create a function that will take a fuzzydate and convert it into a box. (PostgreSQL doesn't have an 'overlaps' operator for line segments, so I chose to use zero-height boxes.) The function calculates the start and end dates of the date range, and uses extract to convert them into epoch times (the number of seconds since the beginning of 1970). These are then divided by 86400 to get the number of days since 1970. These values form the x coordinates of the returned box.
CREATE FUNCTION GeometricDate(fd fuzzydate) RETURNS box AS $$
    start_day integer;
    end_day integer;
    start_day := extract(epoch from fd.midpoint - fd.fuzziness)::integer / 86400;
    end_day := extract(epoch from fd.midpoint + fd.fuzziness)::integer / 86400;
    RETURN box(point(start_day, 0), point(end_day, 0));
Now we can now perform a query like this:
SELECT GeometricDate(('2008-11-04', '2 days'));
to get a result like (14189,0),(14185,0), so let's create a table that we can perform our date range queries on:
  id serial PRIMARY KEY,
  name varchar(100),
  fdate fuzzydate
Note that the fdate column is only storing the original midpoint and fuzziness. So where is the geometric representation? Well, PostgreSQL allows us to index not just a column, but the results of applying a function to a column:
CREATE INDEX events_fdate_index ON events USING gist (GeometricDate(fdate));
Now we can use the geometric date in a query like this one, which says "give me all the events that were within 10 days before or after November 3rd, 2008":
SELECT * FROM events WHERE GeometricDate(fdate) && GeometricDate('2008-11-03', '10 days');
The really important thing to note here is that GeometricDate is not being called for every row in the table. The result of GeometricDate is taken directly from the index we created, and it's the IMMUTABLE flag on the function that tells PostgreSQL that it's okay to do this.

Thursday, August 7, 2008

Parameterised classes in Python

Recently, when working with Django, I wanted to create a class that would automatically render instances of a model as an editable HTML table. I used a Django-esque approach to defining the table columns, such that it was similar to Model and Form classes:

class ProductTable(Table):
    _model = Product
    name = TextWidget()
    description = TextWidget()
    size = DropDownWidget()

The underscore in _model is there to prevent a name collision with the column names, but it's a bit ugly. If I was strictly following the Django approach, I probably would have added an inner class:

class ProductTable(Table):
    class Meta:
        _model = Product

    name = TextWidget()
    description = TextWidget()
    size = DropDownWidget()

But that's a lot of extra noise. What I really wanted was something more like template classes in C++.

template <class Model>
class Table : public TableBase {
  // ...

class ProductTable : public Table<Product> {
  // ...

If Python supported class decorators, I could have just put @model(Product) before the class definition. The approach I chose is to inherit from a class dynamically generated by a function that takes the parameter I need, so my ProductTable class now becomes:

class ProductTable(Table(Product)):
    name = TextWidget()
    description = TextWidget()
    size = DropDownWidget()

Much nicer! Now it pretty much reads as 'a ProductTable is a kind of Table (a Product one)', which makes sense. To support this, I have a Table function that looks like this:

def Table(model):
    class TableDynamicBase(TableBase):
        _model = model
    return TableDynamicBase

TableBase contains whatever was in the original Table base class (which in my case was some unrelated metaclass magic).

Wednesday, August 6, 2008

Introduction to Django

I haven't had any kind of personal web site for ages, but I recently wrote an article, Introduction to Django, for Digital Web magazine, so I thought I'd put a quick something up here as a point of contact.