MySQL Tree Works.sql

drop table if exists users;
create table users(
   id     int primary key,
   up     int,
   up_dir enum('L','R'),
   lc     int,
   rc     int,
   lcount int not null default 0,
   rcount int not null default 0

   index up on users(up),
   index lc on users(lc),
   index lr on users(lr)
);


/*

         1
   2           3
 4    5     6     7
8 9 10 11 12 13 14 15

*/


insert into users(id, up, lc, rc) values
( 1,  NULL,    2,    3),

( 2,     1,    4,    5),
( 3,     1,    6,    7),

( 4,     2,    8,    9),
( 5,     2,   10,   11),

( 6,     3,   12,   13),
( 7,     3,   14,   15),

( 8,     4, NULL, NULL),
( 9,     4, NULL, NULL),
(10,     5, NULL, NULL),
(11,     5, NULL, NULL),

(12,     6, NULL, NULL),
(13,     6, NULL, NULL),
(14,     7, NULL, NULL),
(15,     7, NULL, NULL)
;



-- ================================== --



/* Throws an exception */

DROP PROCEDURE IF EXISTS __raise_exception;
DELIMITER $$$
CREATE PROCEDURE __raise_exception(IN v_msg varchar(200))
BEGIN
   DECLARE v_prefix varchar(200) default 'Opps - ';

   SET v_prefix = concat(v_prefix, v_msg);

   SIGNAL SQLSTATE '45000' SET MESSAGE_TEXT = v_prefix;
END$$$
DELIMITER ;


/* Shows an exception */

DROP PROCEDURE IF EXISTS __show_exception;
DELIMITER $$$
CREATE PROCEDURE __show_exception()
BEGIN
      GET DIAGNOSTICS CONDITION 1
         @s1 = RETURNED_SQLSTATE, @s2 = MESSAGE_TEXT;

      select 'Excepton' as msg, @s1 as num, @s2 as msg;
END$$$
DELIMITER ;


/* Check if numbers are equals */

DROP PROCEDURE IF EXISTS __equals2;
DELIMITER $$$
CREATE PROCEDURE __equals2(IN v_a int, IN v_b1 int, IN v_b2 int, IN v_msg varchar(200))
BEGIN
   IF v_a not in (v_b1, v_b2) THEN
      call __raise_exception(v_msg);
   END IF;
END$$$
DELIMITER ;


/* Check if numbers are equals */

DROP PROCEDURE IF EXISTS __equals;
DELIMITER $$$
CREATE PROCEDURE __equals(IN v_a int, IN v_b int, IN v_msg varchar(200))
BEGIN
   call __equals2(v_a, v_b, v_b, v_msg);
END$$$
DELIMITER ;


/* update the user direction and checks result */

DROP PROCEDURE IF EXISTS _users_update_direction;
DELIMITER $$$
CREATE PROCEDURE _users_update_direction(IN v_direction enum('L','R'), IN v_user_id int)
BEGIN
   IF v_user_id is not NULL THEN
      update users
      set
         up_dir = v_direction
      where
        id = v_user_id;

      call __equals2(ROW_COUNT(), 0, 1, concat('update ', v_direction, ' ', v_direction));
   END IF;
END$$$
DELIMITER ;



-- ================================== --



/* insert / update rows in tree_metadata */

DROP PROCEDURE IF EXISTS _users_metadata_update;
DELIMITER $$$
CREATE PROCEDURE _users_metadata_update(IN v_user_id int)
BEGIN

   -- insert new metadata
   insert into users_tree_metadata(user1, user2)
   with recursive users_tree(id, up, lc, rc, deep)
   as (
      select u.id, u.up, u.lc, u.rc, 1                   from users u where id = v_user_id
      union all
      select u.id, u.up, u.lc, u.rc, users_tree.deep + 1 from users u, users_tree where u.id = users_tree.up
   )
   select v_user_id, id from users_tree;

END$$$
DELIMITER ;



-- ================================== --



/* rebuilds *ALL* rows in tree_metadata */

DROP PROCEDURE IF EXISTS users_metadata_build;
DELIMITER $$$
CREATE PROCEDURE users_metadata_build()
BEGIN
   DECLARE v_finished int default 0;

   DECLARE v_user_id  int;
   DECLARE v_user_lc  int;
   DECLARE v_user_rc  int;

   DECLARE my_cursor cursor for
      select id, lc, rc from users;

   DECLARE continue handler for not found
      set v_finished = 1;

   START TRANSACTION;

      delete from users_tree_metadata;

      OPEN my_cursor;

      loop_label: LOOP

         FETCH my_cursor INTO v_user_id, v_user_lc, v_user_rc;

         IF v_finished THEN
            LEAVE loop_label;
         END IF;

         call _users_metadata_update(v_user_id);

         call _users_update_direction('L', v_user_lc);
         call _users_update_direction('R', v_user_rc);

      END LOOP;

      CLOSE my_cursor;

   COMMIT;

END$$$
DELIMITER ;



-- ================================== --



/* rebuilds *ALL* all directions in users */

DROP PROCEDURE IF EXISTS users_dir_update;
DELIMITER $$$
CREATE PROCEDURE users_dir_update()
BEGIN
   DECLARE v_finished int default 0;

   DECLARE v_user_id  int;
   DECLARE v_user_lc  int;
   DECLARE v_user_rc  int;

   DECLARE my_cursor cursor for
      select id, lc, rc from users;

   DECLARE continue handler for not found
      set v_finished = 1;

   START TRANSACTION;

      OPEN my_cursor;

      loop_label: LOOP

         FETCH my_cursor INTO v_user_id, v_user_lc, v_user_rc;

         IF v_finished THEN
            LEAVE loop_label;
         END IF;

         call _users_update_direction('L', v_user_lc);
         call _users_update_direction('R', v_user_rc);

      END LOOP;

      CLOSE my_cursor;

   COMMIT;

END$$$
DELIMITER ;



-- ================================== --



DROP PROCEDURE IF EXISTS users_dir_find;
DELIMITER $$$
CREATE PROCEDURE users_dir_find(IN v_direction enum('L','R'), IN v_user_id int, OUT v_pos_user_id int, IN v_debug int)
BEGIN
   DECLARE v_finished int default 0;

   -- In MySQL there are no cursors from dynamic statements,
   -- so we will use unions.
   -- There are not much penalty for doing this way.
   -- also if in transaction, will lock all records,
   DECLARE my_cursor cursor for
      with recursive _tree(id, up, lc, rc, deep)
      as (
         select u.id, u.up, u.lc, u.rc, 1              from users u where id = v_user_id
         FOR UPDATE
         union all
         select u.id, u.up, u.lc, u.rc, _tree.deep + 1 from users u, _tree where u.id = _tree.lc and v_direction = 'L'
         FOR UPDATE
         union all
         select u.id, u.up, u.lc, u.rc, _tree.deep + 1 from users u, _tree where u.id = _tree.rc and v_direction = 'R'
         FOR UPDATE
      )
      select id from _tree;

   DECLARE continue handler for not found
      set v_finished = 1;

   OPEN my_cursor;

   -- loop over all records and get last one.
   -- if in transaction,
   -- FOR UPDATE will lock the records.
   loop_label: LOOP

      FETCH my_cursor INTO v_pos_user_id;

      IF v_finished THEN
         LEAVE loop_label;
      END IF;

      -- debug slow down...
      -- select sleep(0.1);

      -- debug
      IF v_debug THEN

         select 'Via node' as msg, users.* from users where id = v_pos_user_id;

      END IF;

   END LOOP;

   CLOSE my_cursor;

   -- debug
   select 'Found at pos' as msg, users.* from users where id = v_pos_user_id;

END$$$
DELIMITER ;



DROP PROCEDURE IF EXISTS users_dir_insert;
DELIMITER $$$
CREATE PROCEDURE users_dir_insert(IN v_direction enum('L','R'), IN v_parent_user_id int, IN v_new_user_id int, OUT v_success int, IN v_debug int)
BEGIN
   DECLARE v_pos_user_id int;

   DECLARE EXIT HANDLER FOR SQLEXCEPTION
   BEGIN
      SET v_success:=0;

      ROLLBACK;

      -- debug
      call __show_exception();
   END;

   SET v_direction = upper(v_direction);

   SET v_success:=1;

   START TRANSACTION;

      -- find_left will lock all records,
      -- so nobody can inject new node on same place.
      call users_dir_find(v_direction, v_parent_user_id, v_pos_user_id, v_debug);

      insert into users
      set
         id	= v_new_user_id	,
         up	= v_pos_user_id	,
         up_dir = v_direction   ;

      -- update metadata
      call _users_metadata_update(v_new_user_id);

      IF v_direction = 'L' THEN

         update users
         set
            lc = v_new_user_id
         where
            id = v_pos_user_id     and
            lc is NULL;

         call __equals(ROW_COUNT(), 1, 'insert on the L');

      ELSE -- v_direction = 'R'

         update users
         set
            rc = v_new_user_id
         where
            id = v_pos_user_id     and
            rc is NULL;

         call __equals(ROW_COUNT(), 1, 'insert on the R');

      END IF;

   COMMIT;

   -- debug
   select v_success, users.* from users where id = v_new_user_id;

END$$$
DELIMITER ;



-- ================================== --



DROP PROCEDURE IF EXISTS users_count_insert;
DELIMITER $$$
CREATE PROCEDURE users_count_insert(IN v_user_id int, IN v_payment_id int, IN v_count int, OUT v_success int, IN v_debug int)
BEGIN
   DECLARE v_finished int default 0;

   DECLARE v_pos_user_id     int;
   DECLARE v_pos_user_up_dir enum('L','R');
   DECLARE v_pos_dir         enum('L','R');

   -- will lock all records, except first one.
   DECLARE my_cursor cursor for
      with recursive _tree(id, up, up_dir, deep)
      as (
         select u.id, u.up, u.up_dir, 1              from users u where id = v_user_id
         union all
         select u.id, u.up, u.up_dir, _tree.deep + 1 from users u, _tree where u.id = _tree.up
         FOR UPDATE
      )
      select id, up_dir from _tree;

   DECLARE EXIT HANDLER FOR SQLEXCEPTION
   BEGIN
      SET v_success:=0;

      ROLLBACK;

      -- debug
      call __show_exception();
   END;

   DECLARE continue handler for not found
      set v_finished = 1;

   SET v_success:=1;

   START TRANSACTION;

      OPEN my_cursor;

      loop_label: LOOP

         set v_pos_dir:=v_pos_user_up_dir;

         FETCH my_cursor INTO v_pos_user_id, v_pos_user_up_dir;

         IF v_finished THEN
            LEAVE loop_label;
         END IF;

         -- first record *always* exists and id is v_user_id
         IF v_pos_user_id = v_user_id THEN
            -- ITERATE is continue
            ITERATE loop_label;
         END IF;

         IF v_pos_dir = 'L' THEN

            update users set lcount = lcount + v_count where id = v_pos_user_id;

         ELSE -- v_pos_dir = 'R'

            update users set rcount = rcount + v_count where id = v_pos_user_id;

         END IF;

         -- this might fail and rollback
         insert into users_tree_log values(v_payment_id, v_user_id, v_pos_user_id, v_pos_dir, v_count);

         IF v_debug THEN

            select 'Via node' as msg, v_pos_user_id, /* v_pos_user_up_dir, */ v_pos_dir;

         END IF;

      END LOOP;

      CLOSE my_cursor;

   COMMIT;

END$$$
DELIMITER ;



-- ================================== --



DROP PROCEDURE IF EXISTS users_dir_get;
DELIMITER $$$
CREATE PROCEDURE users_dir_get(IN v_user_id_parent int, IN v_user_id int, OUT v_direction enum('L','R'), IN v_debug int)
BEGIN
   DECLARE v_finished int default 0;

   DECLARE v_pos_user_id     int;
   DECLARE v_pos_user_up_dir enum('L','R');
   DECLARE v_pos_dir         enum('L','R');

   -- will lock all records, except first one.
   DECLARE my_cursor cursor for
      with recursive _tree(id, up, up_dir, deep)
      as (
         select u.id, u.up,                                    u.up_dir, 1              from users u where id = v_user_id
         union all
         select u.id, if(u.id = v_user_id_parent, NULL, u.up), u.up_dir, _tree.deep + 1 from users u, _tree where u.id = _tree.up
      )
      select id, up_dir from _tree;

   DECLARE continue handler for not found
      set v_finished = 1;

   SET v_direction:=NULL;

   OPEN my_cursor;

   loop_label: LOOP

      set v_pos_dir:=v_pos_user_up_dir;

      FETCH my_cursor INTO v_pos_user_id, v_pos_user_up_dir;

      IF v_finished THEN
         LEAVE loop_label;
      END IF;

      -- first record *always* exists and id is v_user_id
      IF v_pos_user_id = v_user_id THEN
         -- ITERATE is continue
         ITERATE loop_label;
      END IF;

      IF v_pos_user_id = v_user_id_parent THEN

         set v_direction:=v_pos_dir;

         select 'Found' as msg, v_pos_user_id, v_pos_dir;

         LEAVE loop_label;

      END IF;

      IF v_debug THEN

         select 'Via node' as msg, v_pos_user_id, /* v_pos_user_up_dir, */ v_pos_dir;

      END IF;

   END LOOP;

   COMMIT;

END$$$
DELIMITER ;



-- ================================== --



select "Done, you are awesome ;)" as msg;