5 ms·

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 paren

by evv 4y ago

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.

rocqua 4y ago
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.
barrkel 4y ago
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.
- SnowHill9902 4y ago
  Doesn’t feel natural in Postgres. I’d check an auxiliary table nodes_nodes (integer, integer) having an index of all ancestor-descendants.
  - evv 4y ago
    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.
    - SnowHill9902 4y ago
      In your current implementation you either have no unique constraint or it is a more particular case of UNIQUE(ancestor, descendant).
pdenton 4y ago
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.
- evv 4y ago
  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
radiospiel 4y ago
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"

by evv 4y ago

rocqua 4y ago

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.

barrkel 4y ago

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.

SnowHill9902 4y ago
Doesn’t feel natural in Postgres. I’d check an auxiliary table nodes_nodes (integer, integer) having an index of all ancestor-descendants.
- evv 4y ago
  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.
  - SnowHill9902 4y ago
    In your current implementation you either have no unique constraint or it is a more particular case of UNIQUE(ancestor, descendant).

pdenton 4y ago

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.

evv 4y ago
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

radiospiel 4y ago

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"