3 ms·

Firefox bookmarks have nested folders in an arbitrary depth tree, so a recursive CTE might be faster; https://www.google.com/search?q=Firefox+bookmarks+%22CT

Firefox bookmarks have nested folders in an arbitrary depth tree, so a recursive CTE might be faster; https://www.google.com/search?q=Firefox+bookmarks+%22CTE%22 https://www.google.com/search?q=Firefox+bookmarks+%22CTE%22 (Edit) "Bug 1452376 - Replace GetDescendantFolders with a recursive subquery" https://hg.mozilla.org/integration/autoland/rev/827cc04dacce https://hg.mozilla.org/integration/autoland/rev/827cc04dacce "Recursive Queries Using Common Table Expressions" https://gist.github.com/jbrown123/b65004fd4e8327748b650c77383bf553 https://gist.github.com/jbrown123/b65004fd4e8327748b650c7738...

leeoniya 2y ago
storing the tree as an MPTT/NestedSet would massively simplify this, without any subquery shenanigans. https://en.m.wikipedia.org/wiki/Nested_set_model https://en.m.wikipedia.org/wiki/Nested_set_model https://imrannazar.com/articles/modified-preorder-tree-traversal https://imrannazar.com/articles/modified-preorder-tree-trave...
- jitl 2y ago
  Well the read query has simpler syntax with MPTT but implementing the whole structure is more complicated and any re-organization like moving a folder around requires rewriting a lot of rows. Although it doesn’t apply to the Firefox use-case, I’ve never understood how this technique can be applied to anything but the most trivially sized, roughly immutable trees. What do you do in a production system when two people move two different node in the tree? It seems to need all kinds of complicated locks.
- westurner 2y ago
  There are at least five ways to store a tree in PostgreSQL, for example: adjacency list, nested sets like MPTT Modified Preorder Tree Traversal, nested intervals, Materialized Paths, ltree, JSON E.g. django-mptt : https://github.com/django-mptt/django-mptt/blob/main/mptt/models.py https://github.com/django-mptt/django-mptt/blob/main/mptt/mo... : indexed_attrs = (mptt_meta.tree_id_attr,) field_names = ( mptt_meta.left_attr, mptt_meta.right_attr, mptt_meta.tree_id_attr, mptt_meta.level_attr, ) Nested set model: https://en.wikipedia.org/wiki/Nested_set_model https://en.wikipedia.org/wiki/Nested_set_model : > The nested interval model stores the position of the nodes as rational numbers expressed as quotients (n/d).

leeoniya 2y ago

storing the tree as an MPTT/NestedSet would massively simplify this, without any subquery shenanigans. https://en.m.wikipedia.org/wiki/Nested_set_model https://en.m.wikipedia.org/wiki/Nested_set_model https://imrannazar.com/articles/modified-preorder-tree-traversal https://imrannazar.com/articles/modified-preorder-tree-trave...

jitl 2y ago
Well the read query has simpler syntax with MPTT but implementing the whole structure is more complicated and any re-organization like moving a folder around requires rewriting a lot of rows. Although it doesn’t apply to the Firefox use-case, I’ve never understood how this technique can be applied to anything but the most trivially sized, roughly immutable trees. What do you do in a production system when two people move two different node in the tree? It seems to need all kinds of complicated locks.
westurner 2y ago
There are at least five ways to store a tree in PostgreSQL, for example: adjacency list, nested sets like MPTT Modified Preorder Tree Traversal, nested intervals, Materialized Paths, ltree, JSON E.g. django-mptt : https://github.com/django-mptt/django-mptt/blob/main/mptt/models.py https://github.com/django-mptt/django-mptt/blob/main/mptt/mo... : indexed_attrs = (mptt_meta.tree_id_attr,) field_names = ( mptt_meta.left_attr, mptt_meta.right_attr, mptt_meta.tree_id_attr, mptt_meta.level_attr, ) Nested set model: https://en.wikipedia.org/wiki/Nested_set_model https://en.wikipedia.org/wiki/Nested_set_model : > The nested interval model stores the position of the nodes as rational numbers expressed as quotients (n/d).