Why Faceted Navigation is Hard

I was thinking about the relational model today, and I realized that a lot of people probably don't realize that faceted navigation is an example of an application that simply doesn't fit comfortably in the relational model. It also occurs to me that most of you don't care. But I'm going to tell you why anyway.

Faceted navigation is built on faceted classification, which is conceptually very simple. You've got two things: records and categories, and those two things have a many-to-many relationship.

I like to work with concrete examples, so let's take the US states as our dataset. We've got one record for each state. For our categories, let's use adjacent states. That means Massachusetts has the following categories: adjoins-NH, adjoins-VT, adjoins-CT, adjoins-RI, and adjoins-NY. Obviously there are a lot of states that belong to the adjoins-NY category: Pennsylvania, New Jersey, Connecticut, Massachusetts, and Vermont. So clearly this is many-to-many. That's faceted classification.

You can think of each category as a predicate that defines a subset of records -- all the records that have that category. Faceted navigation is based on taking as input a given set of categories, and producing as output all the categories that, if you added them to the input set, would define a smaller, yet non-empty, record set. For example, if I start with the set of states that adjoin Massachusetts, then I could narrow down to states that also adjoin Rhode Island, or states that also adjoin Vermont. But I couldn't narrow down to states that also adjoin California, since that would create an empty record set.

In math terms, if S is the input set of selected categories, then what you want is the set of categories c such that c is not in s, and such that there exists at least one record r such that r has c and r also has every category in S. Or, more tersely:

    {c : (∃r : c(r) ∧ (∀s in S : s(r)))} - S

If you map this to a straightforward relational structure, and then try to use SQL to compute the set described above, you will find that you basically end up thrashing the database to the point that you'd do better to suck out the entire database into memory and forget SQL entirely.

The problem is that SQL isn't really capable of expressing set intersections. Suppose we merely want to get the set of records that have our input set of selected categories. We'd have to do something like this:

  SELECT DISTINCT record_id FROM Facets WHERE 
          record_id in (SELECT record_id FROM Facets WHERE category_id=1) 
      AND record_id in (SELECT record_id FROM Facets WHERE category_id=2)    
      AND ...

No database that I know of will implement the above query efficiently, even though they could -- all they would need to do is intersect the index for category ids 1 and 2. But even if the above query were done efficiently, we're still not done. What we actually want is not a list of records, but a list of categories that would provide further refinements:

  SELECT DISTINCT category_id FROM Facets WHERE
      record_id in (
          SELECT record_id FROM Facets WHERE
                   record_id in (SELECT record_id FROM Facets WHERE category_id=1)
               AND record_id in (SELECT record_id FROM Facets WHERE category_id=2)
               AND ...)

And we're still not done, because we want to remove categories that, if we added them to the input category set, wouldn't reduce the size of our record set. That is, we want to remove "redundant" categories. I'm not even going to bother working that into the above SQL query, because it's more likely you'd implement it as a second pass, in order to keep from increasing the exponent on the query processor's big-O processing time.

It's interesting to note that every text search engine is optimized for handling the first SQL query -- text search is all about intersecting sets of documents, where those sets are defined as all the documents that contain a given word. There's a reason that relational databases aren't usually used to implement text search. For example, SQL Server requires you to explicitly state which fields you want indexed for full-text search.

Hmmm... It might be interesting to see if I could abuse SQL Server's full-text search support to get it to support faceted navigation...