0

I'm trying to implement a hierarchy using closure tables maintained by triggers. I'm using MySQL 5.6. I know we should move out of the 90s and use a database that actually supports CTEs, but this is what we're stuck with for now.

I've written this simple test database and procedures for now that seems to work:

drop table if exists WATCHLIST_FOLDERS_TBL;
create table WATCHLIST_FOLDERS_TBL (
  ID bigint unsigned not null primary key comment 'Unique ID for folder',
  PARENT_ID bigint unsigned not null comment 'ID of parent folder, or 0 if no parent folder',
  NAME varchar(200) not null,
  index (PARENT_ID)
);

drop table if exists USER_WATCHLIST_TBL;
create table USER_WATCHLIST_TBL (
  ID bigint unsigned not null primary key comment 'unique ID for watchlist',
  PARENT_ID bigint unsigned not null comment 'ID of parent folder, or 0 if no parent folder',
  NAME varchar(200) not null,
  index (PARENT_ID)
);

drop table if exists FOLDER_TO_CHILD_FOLDERS_TBL;
create table FOLDER_TO_CHILD_FOLDERS_TBL (
  PARENT_ID bigint not null,
  CHILD_ID bigint not null,
  DEPTH tinyint not null,
  unique key (PARENT_ID, CHILD_ID),
  index (CHILD_ID)
);

drop table if exists FOLDER_TO_CHILD_WATCHLISTS_TBL;
create table FOLDER_TO_CHILD_WATCHLISTS_TBL (
  FOLDER_ID bigint not null,
  WATCHLIST_ID bigint not null,
  DEPTH tinyint not null,
  unique key (FOLDER_ID, WATCHLIST_ID),
  index (WATCHLIST_ID)
);

drop trigger if exists INSERT_FOLDER_TRG;
drop trigger if exists DELETE_FOLDER_TRG;
drop trigger if exists CHECK_CYCLE_TRG;
drop trigger if exists UPDATE_FOLDER_TRG;
drop trigger if exists INSERT_WATCHLIST_TRG;
drop trigger if exists DELETE_WATCHLIST_TRG;
drop trigger if exists UPDATE_WATCHLIST_TRG;

drop procedure if exists INSERT_FOLDER_PRC;
drop procedure if exists DELETE_FOLDER_PRC;
drop procedure if exists CHECK_CYCLE_PRC;
drop procedure if exists UPDATE_FOLDER_PRC;
drop procedure if exists INSERT_WATCHLIST_PRC;
drop procedure if exists DELETE_WATCHLIST_PRC;

-- =====================================================================================================================
-- added folder: when a new folder is added, insert it and all parents into the FOLDER_TO_CHILD_FOLDERS_TBL table.
-- =====================================================================================================================

create procedure INSERT_FOLDER_PRC(in newId bigint)
  begin
    declare parent bigint;
    declare curDepth tinyint default 1;
    select PARENT_ID into parent from WATCHLIST_FOLDERS_TBL where ID = newId;
    while parent <> 0 do
      insert into FOLDER_TO_CHILD_FOLDERS_TBL (PARENT_ID, CHILD_ID, DEPTH) values (parent, newId, curDepth);
      select PARENT_ID into parent from WATCHLIST_FOLDERS_TBL where ID = parent;
      set curDepth = curDepth + 1;
    end while;
  end;
create trigger INSERT_FOLDER_TRG after insert on WATCHLIST_FOLDERS_TBL for each row call INSERT_FOLDER_PRC(new.ID);

-- =====================================================================================================================
-- Deleted folder: delete this folder and all its children from FOLDER_TO_CHILD_FOLDERS_TBL and
-- FOLDER_TO_CHILD_WATCHLISTS_TBL. We  hope that the applicaiton will delete the child folders and child watchlists
-- themselves; we only clean up the secondary tables. Note that if the folders/watchlists don't get deleted, this may
-- end up in a bad state, but since we need to do extra processing on deletes (ie history log, notification queue, etc)
-- we don't want to use a trigger do delete them and accidently delete other useful stuff.
-- =====================================================================================================================

create procedure DELETE_FOLDER_PRC(in folderId bigint)
  begin

    --  get all child folders and watchlists into a temporary table -- we need to do this because we can't directly
    --  reference the tables while stuff is being deleted from them
    drop temporary table if exists childFoldersTmp;
    drop temporary table if exists childWatchlistsTmp;
    create temporary table childFoldersTmp (ID bigint not null) engine = memory;
    create temporary table childWatchlistsTmp (ID bigint not null) engine = memory;
    insert into childFoldersTmp select CHILD_ID from FOLDER_TO_CHILD_FOLDERS_TBL where PARENT_ID = folderId;
    insert into childWatchlistsTmp select WATCHLIST_ID from FOLDER_TO_CHILD_WATCHLISTS_TBL where FOLDER_ID = folderId;

    --  wipe out all remnants of myself and all of my children from the table
    --  (if it's a move, then these will eventually be replaced)
    --  need to do these in seperate calls instead of using or because https://bugs.mysql.com/bug.php?id=10327
    delete from FOLDER_TO_CHILD_FOLDERS_TBL where CHILD_ID = folderId or PARENT_ID = folderId or CHILD_ID in (select ID from childFoldersTmp);
    delete from FOLDER_TO_CHILD_FOLDERS_TBL where PARENT_ID in (select ID from childFoldersTmp);
    delete from FOLDER_TO_CHILD_WATCHLISTS_TBL where WATCHLIST_ID in (select ID from childWatchlistsTmp);

    --  cleanup temp tables
    drop temporary table childFoldersTmp;
    drop temporary table childWatchlistsTmp;
  end;
create trigger DELETE_FOLDER_TRG before delete on WATCHLIST_FOLDERS_TBL for each row call DELETE_FOLDER_PRC(old.ID);

-- =====================================================================================================================
-- Cycle checking -- cannot move a folder into itself or into one of its children.
-- =====================================================================================================================

create procedure CHECK_CYCLE_PRC(in folderid bigint, in newParentId bigint)
  begin
    if folderid = newParentId or newParentId in (select CHILD_ID from FOLDER_TO_CHILD_FOLDERS_TBL where PARENT_ID = folderid) then
      signal sqlstate '45000' set message_text = 'Folder cycle! A folder cannot be moved inside itself or one of its children.';
    end if;
  end;
create trigger CHECK_CYCLE_TRG before update on WATCHLIST_FOLDERS_TBL for each row call CHECK_CYCLE_PRC(new.ID, new.PARENT_ID);

-- =====================================================================================================================
-- Modified folder: this one is incredibly ugly. We find all its child folders and all its child watchlists, remove
-- them totally, then re-insert them one by one. Because of how awful mysql is, this is the only way to loop.
-- =====================================================================================================================

create procedure UPDATE_FOLDER_PRC(in folderid bigint)
  begin
    declare done boolean default false;
    declare childId, parentId bigint;
    declare foldersCursor cursor for select ID from childFoldersTmp;
    declare watchlistsCursor cursor for select ID, PARENT_ID from childWatchlistsTmp;
    declare continue handler for not found set done = true;

    --  this is similar to the tables we create for update, but we also want to get teh parent ID of all watchlists
    drop temporary table if exists childFoldersTmp;
    drop temporary table if exists childWatchlistsTmp;
    create temporary table childFoldersTmp (ID bigint not null) engine = memory;
    create temporary table childWatchlistsTmp (ID bigint not null, PARENT_ID bigint not null) engine = memory;
    insert into childFoldersTmp select CHILD_ID from FOLDER_TO_CHILD_FOLDERS_TBL where PARENT_ID = folderid;
    insert into childWatchlistsTmp select FOLDER_TO_CHILD_WATCHLISTS_TBL.WATCHLIST_ID, USER_WATCHLIST_TBL.PARENT_ID
       from FOLDER_TO_CHILD_WATCHLISTS_TBL join USER_WATCHLIST_TBL on FOLDER_TO_CHILD_WATCHLISTS_TBL.WATCHLIST_ID = USER_WATCHLIST_TBL.ID
       where FOLDER_TO_CHILD_WATCHLISTS_TBL.FOLDER_ID = folderid;

    --  these should be identical to the delete procedure above
    delete from FOLDER_TO_CHILD_FOLDERS_TBL where CHILD_ID = folderid or PARENT_ID = folderid or CHILD_ID in (select ID from childFoldersTmp);
    delete from FOLDER_TO_CHILD_FOLDERS_TBL where PARENT_ID in (select ID from childFoldersTmp);
    delete from FOLDER_TO_CHILD_WATCHLISTS_TBL where WATCHLIST_ID in (select ID from childWatchlistsTmp);

    --  add folder itself back
    call INSERT_FOLDER_PRC(folderid);

    --  if we had any children, we need to recursively add them (they'll figure out their own hierarchy)
    open foldersCursor;
    foldersLoop: loop
      fetch foldersCursor into childId;
      if done then
        leave foldersLoop;
      end if;
      call INSERT_FOLDER_PRC(childId);
    end loop;
    close foldersCursor;

    --  ditto for watchlists
    set done = false;
    open watchlistsCursor;
    watchlistsLoop: loop
      fetch watchlistsCursor into childId, parentId;
      if done then
        leave watchlistsLoop;
      end if;
      call INSERT_WATCHLIST_PRC(childId, parentId);
    end loop;
    close watchlistsCursor;

    drop temporary table childFoldersTmp;
    drop temporary table childWatchlistsTmp;
  end;
create trigger UPDATE_FOLDER_TRG after update on WATCHLIST_FOLDERS_TBL
for each row
  begin
    if old.PARENT_ID <> new.PARENT_ID then
      call UPDATE_FOLDER_PRC(new.ID);
    end if;
  end;

-- =====================================================================================================================
-- Added a new watchlist. Similar to the new folder procedure, we want to traverse its hierarchy and add a reference
-- for each of its parents.
-- =====================================================================================================================

create procedure INSERT_WATCHLIST_PRC(in watchlistId bigint, in parent bigint)
  begin
    declare curDepth tinyint default 1;
    while parent <> 0 do
      insert into FOLDER_TO_CHILD_WATCHLISTS_TBL (FOLDER_ID, WATCHLIST_ID, DEPTH) values (parent, watchlistId, curDepth);
      select PARENT_ID into parent from WATCHLIST_FOLDERS_TBL where ID = parent;
      set curDepth = curDepth + 1;
    end while;
  end;
create trigger INSERT_WATCHLIST_TRG after insert on USER_WATCHLIST_TBL for each row call INSERT_WATCHLIST_PRC(new.ID, new.PARENT_ID);

-- =====================================================================================================================
-- deleted a watchlist. this one's easy, since a watchlist will always be a leaf node.
-- =====================================================================================================================

create procedure DELETE_WATCHLIST_PRC(in watchlistId bigint)
  begin
    delete from FOLDER_TO_CHILD_WATCHLISTS_TBL where WATCHLIST_ID = watchlistId;
  end;
create trigger DELETE_WATCHLIST_TRG before delete on USER_WATCHLIST_TBL for each row call DELETE_WATCHLIST_PRC(old.ID);

-- =====================================================================================================================
-- updated a watchlist. since it's always a leaf node, a simple delete then insert should suffice.
-- =====================================================================================================================

create trigger UPDATE_WATCHLIST_TRG after update on USER_WATCHLIST_TBL
for each row
  begin
    if old.PARENT_ID <> new.PARENT_ID then
      call DELETE_WATCHLIST_PRC(old.ID);
      call INSERT_WATCHLIST_PRC(new.ID, new.PARENT_ID);
    end if;
  end;

-- =====================================================================================================================
-- views
-- =====================================================================================================================

drop view if exists testFoldersView;
create view testFoldersView as
  select parent.NAME as PARENT_NAME, child.NAME as CHILD_NAME
   from FOLDER_TO_CHILD_FOLDERS_TBL
     join WATCHLIST_FOLDERS_TBL parent on FOLDER_TO_CHILD_FOLDERS_TBL.PARENT_ID = parent.ID
     join WATCHLIST_FOLDERS_TBL child on FOLDER_TO_CHILD_FOLDERS_TBL.CHILD_ID = child.ID
   order by FOLDER_TO_CHILD_FOLDERS_TBL.PARENT_ID;

drop view if exists testWatchlistsView;
create view testWatchlistsView as
  select parent.NAME as FOLDER_NAME, child.NAME as WATCHLIST_NAME
    from FOLDER_TO_CHILD_WATCHLISTS_TBL
      join WATCHLIST_FOLDERS_TBL parent on FOLDER_TO_CHILD_WATCHLISTS_TBL.FOLDER_ID = parent.ID
      join USER_WATCHLIST_TBL child on FOLDER_TO_CHILD_WATCHLISTS_TBL.WATCHLIST_ID = child.ID
    order by FOLDER_TO_CHILD_WATCHLISTS_TBL.FOLDER_ID;

-- =====================================================================================================================
-- test data
-- =====================================================================================================================

delete from WATCHLIST_FOLDERS_TBL;
insert into WATCHLIST_FOLDERS_TBL (ID, PARENT_ID, NAME) values
  (1, 0, 'Power Users'),
  (2, 0, 'Powerless Users'),
  (3, 1, 'Sitcom Characters'),
  (4, 1, 'Engineers'),
  (5, 2, 'Philosophers'),
  (6, 0, 'Inactive Users'),
  (7, 1, 'Adventurers'),
  (8, 3, 'Seinfeld Characters'),
  (9, 4, 'Electrical Engineers'),
  (10, 8, 'Supporting Cast'),
  (11, 2, 'Politicians'),
  (12, 8, 'Jerry\'s Girlfriends'),
  (13, 8, 'George\'s Girlfriends'),
  (14, 10, 'Recurring Cast Members'),
  (15, 14, 'Rivals'),
  (16, 15, 'Other Comedians'),
  (17, 16, 'Bad Comedians'),
  (18, 0, 'Government Users'),
  (19, 1, 'Historical Figures'),
  (20, 13, 'Ones he had trouble breaking up with');

insert into USER_WATCHLIST_TBL (ID, PARENT_ID, NAME) values
  (1, 0, 'Superman'),
  (2, 10, 'Soup Nazi'),
  (3, 15, 'Newman'),
  (4, 2, 'Plato'),
  (5, 0, 'Lone Ranger'),
  (6, 2, 'Aristotle'),
  (7, 14, 'Tim Whatley'),
  (8, 9, 'Nikola Tesla'),
  (9, 17, 'Kenny Banya'),
  (10, 19, 'Napoleon Bonaparte'),
  (11, 19, 'Genghis Khan'),
  (12, 2, 'Enki'),
  (13, 2, 'Anu'),
  (14, 13, 'Susan'),
  (15, 7, 'Vasco de Gama'),
  (16, 8, 'Elaine');

-- these ones should move their kids with them
-- update WATCHLIST_FOLDERS_TBL set PARENT_ID = 2 where ID = 10;
-- update WATCHLIST_FOLDERS_TBL set PARENT_ID = 16 where ID = 7;

-- this one throws an error
-- update WATCHLIST_FOLDERS_TBL set PARENT_ID = 15 where ID = 8;

However, I'm very worried about the synchronization of all this and making sure we don't end up in a bad state if multiple queries are running concurrently. Because we have multiple nodes that could be accessing the database, concurrency at the application level is very tricky (we would need to use redis or something for locks, which I'd rather not do).

I can use GET_LOCK and RELEASE_LOCK with a named lock, or I can use table locking. My fear with these methods is: what will happen if something goes wrong? The lock is held for the length of the session, right? We're using connection pooling (some services using Apache DBCP and others using Hikari), which reuses connections, and even without that, we might have transactions that do multiple operations. Since MySQL lacks any finally mechanism, I'm afraid we might get into some sort of deadlock situation.

What's the best way to implement concurrency with this approach? Note that I only care about concurrency within the triggers/update process itself. It would be nice if other clients don't read an intermediate state, but it's not the end of the world. As long as it's eventually consistent, I can handle phantom/stale/whatever reads from clients that aren't doing updates.


CONTEXT: this isn't exactly a closure table. We need to have the full hierarchy in these other tables for quick access. For example, we need to be able to do joins on the complete set of parents (since stuff like permissions are inherited by sub-folders, so if a user has access to a parent, they have access to all subfolders). Therefore, the FOLDER_TO_CHILD_FOLDERS_TBL and FOLDER_TO_CHILD_WATCHLISTS_TBL (sorry about the naming conventions; I don't control that part) need to have a record of every item and every child of that item (transitively).

Basically, we need to be able to check if a user tries to access a folder 5 levels deep what level of access that user has access to it, which can be granted at any level of the hierarchy. We also need to do some aggregations/sorting on stuff that joining the subfolders table would be helpful for (ie "sort on total number of items in this folder and all its subfolders").

The reason there are two tables is that we have one table for folders, and one for items. Folders and items have different ID spaces. Think of it like a filesystem with directories and files treated separately. A file ("watchlist") can't have any children, but a folder can have either folders or files as children.

The code I posted above works for this. My concern is just with the concurrency and correctness in the face of multiple simultaneous clients.

  • I have a little hard time following your approach. A closure table can be implemented in a single table, and it doesn't require a while loop for the depth. Since you didn't explain what you are doing exactly, you might need that approach, but I would check if you can simplify it, especially since, despite of using a lot of code, you still have a lot of "we hope that the application will do the rest"-requirements (which might introduce inconsistency-problems too). Simplifying your approach might automatically reduce possible inconsistency.. – Solarflare Nov 1 '17 at 12:31
  • @Solarflare - Basically, we need a table where we can easily query "what are all the children (transitively) of this folder" and "what are all the parents/ancestors (transitively) of this folder". The closure table approach in the linked article only supports a limited depth (1-2 levels), but this will have the full depth. – Robert Fraser Nov 1 '17 at 17:55
  • No, a closure table supports an unlimited depth. It's special feature is that it allows you to query for depth-dependent conditions (e.g. "all children that are 1 level down from a set of nodes") - to show e.g. a webshop category tree with all 1st level children (and parents) of filtered categories. That feature is "paid for" by having a lot of rows (one row per parent/depth). If you don't need that, a different approach is a nested set (mentioned in your article with broken link), using one row per node. Or other models – Solarflare Nov 2 '17 at 8:05
  • To be more specific for closure tables: for each hierarchy (you seem to have two indepentent trees here), you will usually use a table with the values (e.g. (id, foldername), no parentid - it's just to normalize the names) and the closure table itself ((parentid,childid,depth)). You can then apply operations on it (usually 1 - 2 updates/inserts per operation like add, move, delete - no loops or temp tables required. See e.g. insert-operation and especially the link to Bills slides there for more code/examples/explanations/other models). – Solarflare Nov 2 '17 at 8:22
  • @Solarflare that's exactly the tables I have here. There's not two hierarchies. One table contains folders (the hierarchical objects) and the other contains watchlists (leaf nodes). The parent ID is there, and we resolve the closures inside triggers. – Robert Fraser Nov 3 '17 at 0:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.