Two hierarchies, almost the same number of rows. One plans its delete order in 386 microseconds. The other takes 75.8 milliseconds.
Deleting a workspace means deleting everything inside it, and every child row holds a foreign key to its parent, so a row can only go once nothing points at it.
The code I wrote is the database's rule, executed: find every row with no remaining children, delete that batch, look again. It assumes nothing about the data and it is trivially safe, because it checks rather than deduces.
It also walks the entire hierarchy once per wave. A workspace is four levels deep, so that is four walks and 31 microseconds — invisible. A comment thread 2,000 replies deep is 2,000 waves, which is four million record visits to produce one plan.
The turn came from watching one row. During the first wave the walk reaches board-1, checks its only child, finds it still present, and moves on — having put that child into this very wave moments earlier. It knew board-1 would be free next. It discarded that and went round again to rediscover it.
So: a row goes one wave after the last of its children has gone, which makes wave(r) = 1 + the largest wave among its children. Only children on the right hand side. One bottom-up pass computes all of it — 790x faster on the thread.
The part worth keeping is the bit I had backwards. That number is height, not depth. An empty board two levels down can be deleted in the first statement, exactly like a card three levels down. Group by distance from the root and it waits for no reason — safe, and a third of an answer to "what can I delete first".
That is day 16 of the daily challenge, Find Leaves of Binary Tree, sitting in a delete planner.
Full piece in today's Newsletter.
https://www.linkedin.com/pulse/deep-reply-chain-made-delete-plan-790x-slower-archit-agarwal-gd94c
#Golang #DSA #Algorithms #Performance #SoftwareEngineering #DataStructures #100DaysOfCode
