Once upon a time, I worked at a startup originally called “mavn”, which we renamed to “The Ordering.app”.

That particular company was first and foremost a Django shop. We did everything in the Django Admin (we had some Common Lisp microservices, but that’s a different story). One frequently simply doesn’t have time to write the custom admin of one’s dreams, and so we had a fancy PythonPostgresAdmin with roles and all sorts of bells and whistles programmed in in the spirit of “come on, look: this hack solves the problem completely and we can continue to defer writing our own administration UI”.

Believe it or not, this worked for over nine years.

We used django-mptt to build trees of menu items and trees of modifiers to represent our customers menus. It worked great when it worked, and when it didn’t work it broke in dramatic ways, which earned it the affectionately derogatory nickname of “muppet”. We even had a custom slack emoji for it! It could be a real nightmare to work with at times, especially on very very large menus, or when working on brands with many many locations, each with their own individual menus.

The biggest and most obnoxious kicking-in-the-sensitive-parts that the muppet ever delivered emerged from a ruinic circle at the intersection of harried startup software development and open source plugins for an open source framework. Trinque picked django-mptt up off the shelf, qualified that it satisfied our requirements at the time, wrote a reasonable amount of integration around it, and moved on to the next burning fire. This is a super reasonable, and broadly accepted strategy in startup software engineering: solve the problems you have today (primarily the business ones) and for the love of potatoes, don’t solve problems that you don’t yet have. My personal corollary is that when you are finally motivated to actually get out of the hammock and code up a solution, that solution must be adequate for the next 2 years of scaling. You are not allowed to continue to refine it, you are not allowed to tack on anything but the most compelling changes in scope, no no no no no. You may fix bugs, but your solution has to make the entire class of problem go away.

The concrete caltrop over which we tripped was reordering of MPTT trees. A brief technical digression, and then back to the story.

django-mptt identifies each tree with a tree_id column in the database. All trees are ordered relative to each other. Our multitenancy strategy was to segregate in the Django admin with some…clever and also inscrutable monkeypatching that let folks view and edit a subset of the entire database based on their roles and the permissions granted to those roles. Yes, there are better approaches, and even better approaches for the django-admin case, but see the above guidelines for writing software in the startup context: solve the current business problem. Multitenancy was solved in the context of the Django admin, the business ran on the Django admin, other unrelated problems were solved in the Django admin, the Django admin wasn’t going anywhere shy of a really compelling case (and nor should it have!).

Consider a long-standing customer of good repute with a scaling restaurant business. Their menu contains items that date back to the very beginning of our company’s formation, since they graciously acted as a pilot customer and were so enchanted with the product they signed up as a paying customer. Lo, many years have passed since their menu was first configured, and they have added an item, the legendary Catburger to that menu. They want that menu item to show up in their menu before the also-legendary Fried Hair.

In the admin UI, this company’s employees get a tidy list of their menu items (conveniently and robustly scoped per role and permissions), ordered in the way they want them in the ordering UI. Under the hood, all of their menu items are ordered relative to each other using the django-mptt tree_id for each menu item (this menu structure might also have root nodes that are “burgers” and “slime molds” and “tardigrades” and their children be orderable items; what matters for this case is that the root nodes exist and have tree_ids). The Fried Hair item dates back seven years, so its tree_id is very low, perhaps even double digits in the database! Meanwhile, the Catburger is of much more recent vintage, and may have a tree_id in the hundreds of thousands.

If our customer’s employee attempts to put the Catburger before the Fried Hair in the database Catburger‘s new tree_id must be lower than that of Fried Hair. The naive implementation is to (in a transaction, for while we may hack in our underwear we are not actually barbarians), capture the current tree_id of Fried Hair, capture the current tree_id of Catburger, set the tree_id of Catburger to that of Fried Hair, and then (here’s the problematic bit) increment the tree_id’s of everything between the original Catburger and Fried Hair tree_ids.

This was an expensive operation. If memory serves, in our pathological cases it could touch over 90% of the rows in our menu item or menu modifier tables. Very bad.

We considered adding an additional column to define client-scoped ordering of trees so that we could avoid having to renumbering entire tables’ tree_id columns for operations that in theory should have been scoped to that particular client. We didn’t see a clear path to implementing this in the context of django-mptt, so we went with a much more DB-centric approach that stuck to my principle of completely solving the problem in such a way that it never rears its head again.

Instead of naively incrementing the tree_ids of everything between the moving node and the node it needs to appear before, I implemented a dynamic menu defragging routine that ran before django-mptt took over and moved the nodes relative to each other.

The algorithm (although that strikes me as a pretentious word to use here) is as follows:

1. Encode the threshold count of nodes affected by a proposed reorder that would trigger a defrag (this is probably best done with a conservative WHAG^[1]Wild Hairy Arbitrary Guess, if you can’t swizzle it at execution time and metric how different thresholds affect reordering time)
2. Calculate the count of trees scoped to the client)
3. Calculate the number of nodes that would be affected by the user-proposed reordering
4. If the number of affected nodes is less than the threshold defined in (1), return control to the MPTT library for node reordering since the count of nodes affected by its reordering implementation is below the threshold that we care about
5. Find the first gap in the sequence of tree_ids that is equal to or larger than the number of trees under consideration for move OR the last unused tree_id if no suitable gap is found
6. Renumber all of the trees scoped to the client to sequentially occupy the beginning of the identified gap, preserving their current order
7. Return control to the MPTT library for node reordering, now that the count of nodes that will be affected by its reordering implementation is of a reasonable size

Tradeoff analysis:

• This algorithm introduces gaps as large tree sequences that can’t be defragged to the front of the tree_id sequence will be moved to the end of the sequence
• Smaller client-scoped tree-reorderings will over time consume the large gaps that are left over when large menus are defragged to the end of the tree_id sequence
• Defragging only runs when the count of affected nodes is higher than our chosen threshold, which will reduce churn on the table
• MPTT implementations are already complicated, and this defragging implementation: a) is not generic and b) adds complexity to a complex element of our system
• We cannot submit this patch upstream, as it is tightly coupled to our (dubious) multitenancy dependency on django-mptt

A rather good hack that I was pleased to invent, write and ship. It fixed the problem we faced, which was surprise reorders locking various MPTT tables in our production DB stemming from entirely normal and ordinary user interactions. It solved this problem for us forever. However, it’s not a general performance solution to MPTT woes, and so it’s not going to all of a sudden make MPTT (or nested sets, the formal implementation of which MPTT is a subset).

Many thanks to Tobias Petry, whose post Store Trees As Materialized Paths triggered an email exchange which in turn inspired this blog post.

Coda

I asked ChatGPT to write a PL/pgSQL function that identifies all the gaps in an imaginary table’s imaginary integer tree_id column, and this is what it spat out:

CREATE OR REPLACE FUNCTION find_missing_gaps()
RETURNS TABLE (gap_start integer, gap_end integer) AS $$
BEGIN
    RETURN QUERY
    WITH all_ids AS (
        SELECT generate_series(MIN(tree_id), MAX(tree_id)) AS id
        FROM my_table
    ),
    missing_groups AS (
        SELECT MIN(id) AS gap_start, MAX(id) AS gap_end
        FROM all_ids
        WHERE NOT EXISTS (SELECT 1 FROM my_table WHERE tree_id = id)
        GROUP BY id - ROW_NUMBER() OVER (ORDER BY id)
        HAVING COUNT(*) > 1
    )
    SELECT gap_start, gap_end
    FROM missing_groups
    ORDER BY gap_start;

    RETURN;
END;
$$ LANGUAGE plpgsql;

If I squint, it looks pretty good, but now I want to see some tests. Here’s what our favorite cat^[2]“chat GPT” in French sounds like “chat, j’ai pété!”, which translates to approximately “cat, I farted!” has to say when asked to write a test:

CREATE OR REPLACE FUNCTION test_find_missing_gaps()
RETURNS VOID AS $$
DECLARE
    missing_gaps RECORD;
BEGIN
    -- Create a temporary table for testing purposes
    CREATE TEMPORARY TABLE test_my_table (
        tree_id integer
    );

    -- Insert some data into the table
    INSERT INTO test_my_table (tree_id)
    VALUES (1), (2), (3), (5), (6), (7), (9), (10), (20), (90), (666);

    -- Define the expected result set
    CREATE TEMPORARY TABLE expected_result (
        gap_start integer,
        gap_end integer
    );

    INSERT INTO expected_result (gap_start, gap_end)
    VALUES (4, 4), (8, 8), (11, 19), (21, 89), (91, 665);

    -- Call the function being tested
    SELECT * FROM find_missing_gaps() INTO TEMP missing_gaps;

    -- Check if the result matches the expected result
    IF NOT EXISTS (
        SELECT *
        FROM missing_gaps
        EXCEPT
        SELECT *
        FROM expected_result
    ) AND NOT EXISTS (
        SELECT *
        FROM expected_result
        EXCEPT
        SELECT *
        FROM missing_gaps
    ) THEN
        RAISE NOTICE 'Test passed!';
    ELSE
        RAISE EXCEPTION 'Test failed!';
    END IF;

    -- Clean up the temporary objects
    DROP TABLE test_my_table;
    DROP TABLE expected_result;
END;
$$ LANGUAGE plpgsql;

Exercise for the reader to determine if the tests pass.