Hacker News Reader

Comment by evv | Hacker News Reader

I have struggled to implement a tree structure in PG with nullable unique values.

Consider a "docs" table where each doc has a unique name, under a given parent doc. A null parent would be a top-level doc, and top-level docs just have a unique name. This didn't work before, and would hopefully be addressed by PG15.

I'm not sure if null parents really represent a "problem with my data", or if the tree structure was too exotic for PG to support properly.

How I got around it: hardcode a certain root doc ID, then the parent column can be NOT NULL. But this felt janky because the app has to ensure the root node exists before it can interact with top-level docs. Plus there were edge cases introduced with the root doc.

View on HN

When I store tree-structured data in a relational database I generally add a 'path' column which is a denormalized string containing the names of all the parents with a path separator between.

The biggest reason is it makes finding all descendants very fast with a prefix search (foo/bar/%) on the path column when it's indexed. It's not unusual to want to find or update all descendants because descendants are usually related. If you don't have a path column, then you need to write a recursive CTE, which is Slow, or recurse in your application, which is normally even slower. The reason they're slow is they require a number of seeks which is exponential in the depth of the tree.

It also makes lookup of a node from the path fast, and producing a qualified path to a node fast, but these costs are linear in path length.

Anyway, this path column is also a good place to put your unique constraint.

If you don't want to restrict names from containing the path separator, you can escape application-side. For example, if using '/' as a path separator, consider '::' to escape ':' and ':s' to escape '/' - don't use your path separator in the escape or it'll muck up prefix searches.

Doesn’t feel natural in Postgres. I’d check an auxiliary table nodes_nodes (integer, integer) having an index of all ancestor-descendants.

Agree its a bit unnatural, but it seems workable. My problem with the auxiliary table is, I wouldn't know how to implement the unique constraint.

In your current implementation you either have no unique constraint or it is a more particular case of UNIQUE(ancestor, descendant).

The way I'd do this, is by separating concerns into separate tables. If you have a table with (id, name) and a table with (id, parent_id), any doc with a parent will have a corresponding record in the second table.

Interesting! But where can you implement the UNIQUE constraint for doc names under a given parent? I guess your application code would need to handle that

Thanks for this example! As I was reading the post, I was thinking "cool, and feels like a thing people would expect, but does it have a real world usecase?".

This feels like an actual real-world thing people might want to do where indeed you'd want to have a single NULL value.

You might want to look at a unique partial index: "CREATE UNIQUE INDEX foo ON pages(name, parent_id) WHERE parent_id IS NOT NULL"

Reply on news.ycombinator.com