One Table, Any Number of Tiers

Every quote on Quote Catalog came from somewhere, and the somewhere had a shape. A line from Better Call Saul came from an episode, which sat in a season, which belonged to the show. A lyric came from a song, on an album, by an artist like Stevie Ray Vaughan. A line from a movie came from the movie, and that was the whole tree. Three tiers of one kind, three tiers of another, one tier, all of them sources we wanted to attribute properly and build pages around.

The obvious design is a table per tier: shows, seasons, episodes, artists, albums, songs, movies. It’s easy to read and easy to explain, and every new kind of source is a new table, a new migration and a new set of joins. A podcast is two more tables. A book with chapters is two more. A quote now has to point at one of seven tables, which means seven nullable foreign keys or a reference the database can’t check.

We put all of it in one table instead, and the number of tiers stopped being a question for the schema. It was a question for the data, and the same table could hold any hierarchy at all, in any shape, without adding a table to match it. Why this design? It grows with different taxonomies, a show’s three tiers, an artist’s three and a movie’s one, and whatever shape the next kind of source turns out to have, without growing a new table for every new hierarchy. And with careful indexing, it stays performant, because every question the site asks of it lands on an index built for that question. The technique underneath it is old, older than most of the people I’ve worked with have been writing SQL, and the way we combined it has been close to lost to time. I’ve looked for a write-up of this exact design and haven’t found one, which is most of the reason I’m writing it down. The exact indexes we shipped are the part I can’t swear to, so where this gets into indexing, it’s the indexes the design asks for.

The Old Ways to Store a Tree

SQL has never been good at trees. The simplest way to store one is to give each row its parent’s ID, usually called the adjacency model, and it’s easy to write and miserable to read, because every extra level is another self-join. In a 2002 article for SQLTeam, Rob Volk put it plainly: you need to join the table to itself once per level, “not an attractive option if you have 5 or more levels,” and SQL Server at the time had no recursive join to do it for you (Volk).

The well-known alternative was Joe Celko’s nested set model, which he wrote about in his columns and later collected in Trees and Hierarchies in SQL for Smarties. It’s also known as modified preorder tree traversal, the name it went by in a widely shared SitePoint tutorial from the same era (Van Tulder). The idea is to walk the tree once, depth first, and number every node twice, once on the way in and once on the way out. Those two numbers are usually called lft and rgt. Every node’s descendants are the nodes whose numbers fall between its own.

Volk, who preferred a different approach, still gave nested sets their due. They’re “very efficient and [make] it extremely easy to pull out trees/subtrees from the table.” His complaint was everything else: “the complexity required to do relatively simple tasks, like adding, deleting, or moving nodes,” and the fact that “even finding an employee’s immediate supervisor or subordinates requires 3 self-joins AND a subquery!”

Our Table

What we built was a hybrid that answered Volk’s complaint. We kept the parent pointer from the adjacency model, so immediate parents and children are a single lookup. We kept the nested-set numbers, so whole subtrees are a single range. We stored the depth, so the tier of any node is a column rather than a calculation. And we added the thing none of the textbook examples needed, a column saying what kind of thing each node is. Simplified, it looked something like this:

CREATE TABLE Sources (
    Id        INT AUTO_INCREMENT PRIMARY KEY,
    ParentId  INT NULL REFERENCES Sources (Id),
    Kind      VARCHAR(20) NOT NULL,   -- 'show', 'season', 'episode', 'artist', 'album', 'song', 'movie'
    Title     VARCHAR(200) NOT NULL,
    Slug      VARCHAR(200) NOT NULL,      -- 'better-call-saul', 'season-2', 'switch'
    Depth     TINYINT UNSIGNED NOT NULL,
    Lft       INT NOT NULL,
    Rgt       INT NOT NULL
);

Here’s a slice of it, with a few kinds of sources in it at once, drawn as the tree the rows describe. The number on the left of each node is its Lft and the number on the right is its Rgt, written by a walk that starts at Better Call Saul, goes down through every season and episode, and back out again. Select any node to see what its range covers.

Depth 0Depth 1Depth 2Left corner: Lft · right corner: Rgt

Select a node to see the query for everything under it.

A show is three tiers deep, an artist three and a movie one, and the table doesn’t care. A quote got a single source ID and pointed at whatever level it came from, the episode if we knew it, the show if we didn’t. A new kind of source was new rows with a new Kind, not new tables. Every source, at every depth, used the same page template, the same breadcrumbs and the same attribution code, because they were all the same kind of record.

Notice the arithmetic in the numbers. Better Call Saul has Lft 1 and Rgt 12, so it has (12 − 1 − 1) / 2 = 5 descendants, its two seasons and three episodes. A leaf, whether it’s an episode, a song or a whole movie, always has Rgt exactly one more than Lft. The tree’s whole shape is in two integers per row.

Any Shape, One Table

It’s worth saying plainly, because the media examples undersell it. Nothing in this table is about shows, seasons or albums. It holds a hierarchy, any hierarchy, in any shape, and the shape lives in the rows.

A podcast is two tiers, a show and its episodes, with no seasons in between. A book can be four, book, part, chapter and section. A speech is one. And the shapes don’t have to be regular inside a single tree, either. A show can have specials that hang directly off the show, outside any season, sitting at depth one next to seasons whose episodes sit at depth two. An artist can have albums with songs under them and singles directly underneath the artist. Each of those is a parent pointer, a depth and a pair of nested-set numbers, the same as everything else, so every one of them uses the same queries, the same indexes, the same breadcrumbs and the same URL pattern.

Here’s what that looks like as URLs, every one of them served by the same route and the same page template, built from the slugs of a node and its ancestors:

1. /1. i-have-a-dreama speech, one tier
2. HHHardcore History/1. hardcore-history/2. supernova-in-the-east-ia podcast, two tiers, no seasons
3. BCBetter Call Saul/1. better-call-saul/2. season-2/3. switcha show, three tiers
4. /1. war-and-peace/2. volume-1/3. part-1/4. chapter-1a book, four tiers
5. SSherlock/1. sherlock/2. series-1/3. a-study-in-pinkan episode inside a series
6. SSherlock/1. sherlock/2. the-abominable-bridea special, straight under the show
7. FOFrank Ocean/1. frank-ocean/2. blonde/3. nightsa song on an album
8. FOFrank Ocean/1. frank-ocean/2. chanela single, straight under the artist

Look at the last four. Sherlock’s special and Sherlock’s episodes are in the same tree at different depths, and so are Frank Ocean’s single and his album tracks. Nothing about the table, the query or the route had to know that in advance. The URL is as deep as that particular branch of the tree, and no deeper.

The table-per-tier design can’t do that without changing. Every new shape means new tables to match the hierarchy, a podcast-episodes table, a book-parts table, a specials table that has to point at shows instead of seasons, and a quote table with one more foreign key every time. In one table, a new shape is just a new arrangement of rows. You never add a table to match a hierarchy, because the hierarchy was never in the tables to begin with.

Count it out for just the sources on this page:

Table per tier                                   One table
-----------------------------------------------  ---------
speeches                                     1    sources
podcasts, podcast_episodes                   2
shows, seasons, episodes, specials           4
movies                                       1
books, volumes, parts, chapters              4
artists, albums, songs, singles              4
-----------------------------------------------  ---------
16 tables                                         1 table

Sixteen tables, and since a quote can come from any level of any of them, the quotes table needs sixteen nullable foreign keys, with a rule somewhere that exactly one of them is set. The single table replaces all sixteen with one SourceId.

Reading It

Every read the site needed was one of four questions, and each one had a direct answer.

Everything under a node, like every season and episode of Better Call Saul, is a numeric range, no recursion and no string matching:

SELECT Id, Kind, Title, Depth
FROM Sources
WHERE Lft > @Lft AND Rgt < @Rgt
ORDER BY Lft;

Ordering by Lft returns them in tree order, show, season, its episodes, next season, so the page can render straight down the result. The direct children of a node, the seasons of a show or the songs on an album, come from the parent pointer. The breadcrumbs on a quote page are the reverse range, every node whose numbers surround the current one, in walk order. That same query builds the URL. Each row carries its own slug, and the slugs of a node and its ancestors, read top to bottom, are the path, across however many levels the source has:

-- the path to Switch: better-call-saul / season-2 / switch
SELECT Slug
FROM Sources
WHERE Lft <= @Lft AND Rgt >= @Rgt
ORDER BY Lft;

An episode’s page lives at /better-call-saul/season-2/switch, a song’s at /stevie-ray-vaughan/texas-flood/pride-and-joy and a movie’s at /the-princess-bride. One query, one route pattern and one page template cover all three, because the URL is as deep as the tree is and no deeper. It also means a slug only has to be unique among its siblings. Texas Flood is both a Stevie Ray Vaughan album and the title track on it, and the two pages never collide, because one lives at /stevie-ray-vaughan/texas-flood and the other at /stevie-ray-vaughan/texas-flood/texas-flood. And every show, every album or every season is the type column, which is what made a generic table fast for specific questions. With an index on Kind and Depth, “all shows” is a seek, not a scan:

CREATE INDEX IX_Sources_Kind     ON Sources (Kind, Depth);
CREATE INDEX IX_Sources_Range    ON Sources (Lft, Rgt);
CREATE INDEX IX_Sources_Children ON Sources (ParentId);

Microsoft describes the same two ways of indexing a tree in its documentation for SQL Server’s hierarchyid type. A depth-first index keeps “all nodes in the subtree of a node” together, and a breadth-first index keeps “all direct children of a node” together (Microsoft). The nested-set range is the depth-first index and the parent pointer is the breadth-first one, built by hand, in a database that has never had anything like hierarchyid.

What It Cost

The price of nested sets is writes. Adding a node means making room for it, shifting the Lft and Rgt of every node to its right by two. That’s why Volk disliked them, and on a tree that changes constantly it’s a real cost. Ours didn’t. Shows gain a season once a year and an episode once a week, albums are finished when they’re released, and a movie never grows. A quote archive is written rarely and read constantly, which is the trade nested sets are built for.

The other cost is integrity. A table per tier lets the database enforce that an episode’s parent is a season, because the foreign key points at the seasons table. In one table, every parent is just another row, and nothing in the schema stops an episode from hanging off an album. Those rules move into the code that writes the tree, and they need tests like any other code.

Why It Was Lost

Part of why designs like this faded is that the databases caught up. Quote Catalog ran on MySQL, and MySQL had no recursive queries at all until version 8.0, released in April 2018 (MySQL). Before that, walking a parent pointer meant a self-join per level or a loop in application code, which is exactly the problem Volk was writing about for SQL Server in 2002. Storing the tree’s shape as numbers was how you got subtrees in a single query. Now MySQL documents WITH RECURSIVE, where “a recursive common table expression is one having a subquery that refers to its own name” (MySQL), and SQL Server has had recursive queries since 2005 and a built-in hierarchyid path type since 2008. Most hierarchy tutorials since then teach one of those.

What neither the old articles nor the new documentation covers is the part that made ours useful, different kinds of things at different depths in one tree. Nearly every example models one kind of thing, employees or files. The interesting exception is Microsoft’s own basic hierarchyid example, which mixes continents, countries, states and cities, with Bahia, a state, sitting beside Brasília, a city. Microsoft’s comment on its own data is that the hierarchy “isn’t internally consistent,” and that “users must decide if this type of hierarchy is appropriate for their use.” For us that inconsistency was the feature. A show and a movie aren’t supposed to have the same depth.

The Modern Way

If I built this today on Postgres, I’d keep the single table, the type column and the depth, and replace the nested-set numbers with ltree, a built-in type “for representing labels of data stored in a hierarchical tree-like structure” (PostgreSQL). A label can contain letters, digits, underscores and hyphens, which means the slugs are already valid labels, and the URL path and the tree path become the same thing:

CREATE EXTENSION ltree;

CREATE TABLE sources (
  id     BIGSERIAL PRIMARY KEY,
  kind   TEXT NOT NULL,
  title  TEXT NOT NULL,
  path   LTREE NOT NULL UNIQUE   -- 'sherlock.series-1.a-study-in-pink'
);

CREATE INDEX sources_path_gist ON sources USING GIST (path);
CREATE INDEX sources_kind ON sources (kind, nlevel(path));

Every read from earlier is one operator. <@ asks whether the left side “is a descendant of right (or equal),” and @> whether it “is an ancestor of right (or equal),” and a GiST index on the path serves both:

-- everything under Sherlock, specials and series alike
SELECT * FROM sources WHERE path <@ 'sherlock';

-- the breadcrumb and the URL for one episode, top to bottom
SELECT title, path FROM sources
WHERE path @> 'sherlock.series-1.a-study-in-pink'
ORDER BY nlevel(path);

-- the direct children of a show
SELECT * FROM sources WHERE path ~ 'sherlock.*{1}';

Inserting a new episode is one row with one path, and nothing else in the table moves, which removes the cost Volk disliked about nested sets. MySQL, which is what Quote Catalog actually ran on, has no ltree. It doesn’t need one. The modern MySQL version keeps the same single table and gets the same result two ways, and I’d use both.

The first is to store the path yourself. The URL path is already the materialized path of the tree, so make it a column, index it, and let MySQL derive the depth from it:

CREATE TABLE sources (
  id         BIGINT AUTO_INCREMENT PRIMARY KEY,
  parent_id  BIGINT NULL,
  kind       VARCHAR(20) NOT NULL,
  title      VARCHAR(200) NOT NULL,
  path       VARCHAR(512) CHARACTER SET ascii COLLATE ascii_bin NOT NULL, -- 'sherlock/series-1/a-study-in-pink'
  depth      TINYINT UNSIGNED AS (LENGTH(path) - LENGTH(REPLACE(path, '/', ''))) STORED,
  UNIQUE KEY uq_path (path),
  KEY ix_parent (parent_id),
  KEY ix_kind_depth (kind, depth),
  FOREIGN KEY (parent_id) REFERENCES sources (id)
);

A whole subtree is then a range on that index. Slugs are plain ASCII, so the column uses a binary ASCII collation, the paths sort byte by byte, and every path under sherlock/ sits in one contiguous run of the index, starting at sherlock/ and ending just before sherlock0, since 0 is the character right after /:

-- everything under Sherlock, series and specials alike: one index range scan
SELECT * FROM sources WHERE path >= 'sherlock/' AND path < 'sherlock0';

-- a page by its URL: one unique lookup
SELECT * FROM sources WHERE path = 'sherlock/series-1/a-study-in-pink';

A prefix LIKE 'sherlock/%' would usually compile to the same range, and MySQL’s documentation says a B-tree index “can be used for LIKE comparisons if the argument to LIKE is a constant string that does not start with a wildcard character” (MySQL). But LIKE has a reputation for being slow, because the moment someone writes '%sherlock%' it is, and the explicit range can’t be broken that way.

The second is the recursive query MySQL added in 8.0, for anything the path doesn’t answer directly, like walking up from a node to build its breadcrumbs with titles:

WITH RECURSIVE ancestors AS (
  SELECT id, parent_id, title, depth FROM sources WHERE id = ?
  UNION ALL
  SELECT s.id, s.parent_id, s.title, s.depth
  FROM sources s JOIN ancestors a ON s.id = a.parent_id
)
SELECT title FROM ancestors ORDER BY depth;

For a tree three or four levels deep, that walk is a handful of primary-key lookups. Inserting a node is one row with its parent and its path, and nothing else moves, so the write cost that made nested sets awkward is gone. The one thing the path asks of you is that a node’s path changes if its parent does. For media sources, where an episode never moves to another show, that almost never happens.

Takeaways

If I were modeling sources again, I’d still put them in one table, because the thing that changed most often was what kinds of sources we had, and a single table makes that a data change instead of a schema change. I’d keep all three ways of reading the tree, a parent pointer for children, nested-set numbers for subtrees and a depth for tiers, because each one makes a different question cheap. I’d add the type column with an index, because that’s what makes a generic table fast for specific questions. I’d only reach for nested sets on a tree that’s read far more than it’s written, and today I’d reach for a stored path before either, ltree on Postgres or an indexed path column on MySQL. And I’d write down how it was indexed while I still remembered, which is the part I didn’t do the first time.

The number of tiers belonged in the data. The schema only had to know that sources have parents, depths and a place in the walk.

Sources

1. Rob Volk, “More Trees & Hierarchies in SQL,” SQLTeam.com, May 2002
2. Gijs Van Tulder, “Storing Hierarchical Data in a Database,” SitePoint
3. Joe Celko, Joe Celko’s Trees and Hierarchies in SQL for Smarties, Morgan Kaufmann, 2004
4. Microsoft, “Hierarchical Data (SQL Server),” Microsoft Learn
5. MySQL, “Changes in MySQL 8.0.11,” release notes, April 2018
6. MySQL, “WITH (Common Table Expressions),” MySQL 8.0 Reference Manual
7. PostgreSQL, “ltree,” PostgreSQL documentation
8. MySQL, “Comparison of B-Tree and Hash Indexes,” MySQL 8.0 Reference Manual