Skip to main content

ADR 0015: Pluggable Tree Strategies (Nested Set and Adjacency List)

Status​

Accepted

Context​

Previously, Framework M only supported the Nested Set model (via NestedSetMixin) for representing hierarchical (tree) structures in the database. The Nested Set model offers excellent read performance because subtrees can be queried using a simple range query (lft BETWEEN bounds). However, it has significant write performance bottlenecks:

  • Every insert or relocation requires locking and shifting the bounds of other rows in the table.
  • In write-heavy applications (e.g., tasks, folder structures, comments), this leads to lock contention, deadlocks, and slow response times.

To support write-heavy hierarchies, we needed to introduce the Adjacency List model (via parent pointers). We also wanted to establish a flexible pattern to support both tree styles transparently.

Decision​

We decided to implement a Pluggable Tree Strategy architecture based on the Strategy Pattern.

1. Strategy Protocol​

We defined a TreeStrategy protocol with hooks for:

  • before_insert(session, entity): Perform tree structural updates before insert.
  • before_update(session, entity, existing): Perform tree structural updates and cycle detection before update.
  • get_tree_statement(parent_id): Generate a SQLAlchemy select query returning the tree or subtree.

2. Nested Set Strategy​

The existing bounds-shifting, gap-opening, and loop validation logic was encapsulated inside NestedSetTreeStrategy.

3. Adjacency List Strategy​

We implemented AdjacencyListTreeStrategy which:

  • Needs no bounds shifting on inserts.
  • Uses recursive SQL Common Table Expressions (CTEs) to perform ancestry loop detection (the "Ancestor Trap" check) on updates/moves.
  • Uses recursive SQL CTEs to retrieve entire subtrees in a single query.

4. Dynamic Frontend Adapters​

The Desk frontend tree view component was updated to dynamically resolve its sorting order:

  • If the schema contains lft properties, it sorts by lft (Nested Set manual ordering).
  • Otherwise, it falls back to sorting by name or a custom configured orderField (Adjacency List).

5. Documentation over synchronous Migration Helpers​

To prevent developers from running unsafe table-wide locking migrations in production, we chose not to provide a synchronous migration helper in the framework. Instead, we document standard Zero Downtime Migration (ZDM) patterns to guide developers through multi-phase schema evolution.

Consequences​

  • Pros:
    • Developers can choose the right database pattern depending on read/write profiles.
    • Adjacency List inserts and updates do not require table-wide bound shifting.
    • The Strategy Pattern completely decouples repository and controller routes from the details of the tree model.
    • The frontend tree view works seamlessly with both strategies out of the box.
  • Cons:
    • The Adjacency List strategy requires recursive CTE support in the database engine (supported by SQLite, PostgreSQL, and MySQL 8.0+).
    • Transitioning between strategies in production requires a multi-phase ZDM data backfill instead of a single automated command.

References​