Skip to content

Instantly share code, notes, and snippets.

@nmmmnu
Created March 11, 2019 09:30
Show Gist options
  • Save nmmmnu/b271d16e5ba53e758d4232e420d6a0f2 to your computer and use it in GitHub Desktop.
Save nmmmnu/b271d16e5ba53e758d4232e420d6a0f2 to your computer and use it in GitHub Desktop.
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;
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment