· 6 years ago · Mar 15, 2019, 01:24 PM
1drop table if exists users;
2create table users(
3 id int primary key,
4 up int,
5 up_dir enum('L','R'),
6 lc int,
7 rc int,
8 lcount int not null default 0,
9 rcount int not null default 0
10
11 index up on users(up),
12 index lc on users(lc),
13 index lr on users(lr)
14);
15
16
17/*
18
19 1
20 2 3
21 4 5 6 7
228 9 10 11 12 13 14 15
23
24*/
25
26
27insert into users(id, up, lc, rc) values
28( 1, NULL, 2, 3),
29
30( 2, 1, 4, 5),
31( 3, 1, 6, 7),
32
33( 4, 2, 8, 9),
34( 5, 2, 10, 11),
35
36( 6, 3, 12, 13),
37( 7, 3, 14, 15),
38
39( 8, 4, NULL, NULL),
40( 9, 4, NULL, NULL),
41(10, 5, NULL, NULL),
42(11, 5, NULL, NULL),
43
44(12, 6, NULL, NULL),
45(13, 6, NULL, NULL),
46(14, 7, NULL, NULL),
47(15, 7, NULL, NULL)
48;
49
50
51
52-- ================================== --
53
54
55
56/* Throws an exception */
57
58DROP PROCEDURE IF EXISTS __raise_exception;
59DELIMITER $$$
60CREATE PROCEDURE __raise_exception(IN v_msg varchar(200))
61BEGIN
62 DECLARE v_prefix varchar(200) default 'Opps - ';
63
64 SET v_prefix = concat(v_prefix, v_msg);
65
66 SIGNAL SQLSTATE '45000' SET MESSAGE_TEXT = v_prefix;
67END$$$
68DELIMITER ;
69
70
71/* Shows an exception */
72
73DROP PROCEDURE IF EXISTS __show_exception;
74DELIMITER $$$
75CREATE PROCEDURE __show_exception()
76BEGIN
77 GET DIAGNOSTICS CONDITION 1
78 @s1 = RETURNED_SQLSTATE, @s2 = MESSAGE_TEXT;
79
80 select 'Excepton' as msg, @s1 as num, @s2 as msg;
81END$$$
82DELIMITER ;
83
84
85/* Check if numbers are equals */
86
87DROP PROCEDURE IF EXISTS __equals2;
88DELIMITER $$$
89CREATE PROCEDURE __equals2(IN v_a int, IN v_b1 int, IN v_b2 int, IN v_msg varchar(200))
90BEGIN
91 IF v_a not in (v_b1, v_b2) THEN
92 call __raise_exception(v_msg);
93 END IF;
94END$$$
95DELIMITER ;
96
97
98/* Check if numbers are equals */
99
100DROP PROCEDURE IF EXISTS __equals;
101DELIMITER $$$
102CREATE PROCEDURE __equals(IN v_a int, IN v_b int, IN v_msg varchar(200))
103BEGIN
104 call __equals2(v_a, v_b, v_b, v_msg);
105END$$$
106DELIMITER ;
107
108
109/* update the user direction and checks result */
110
111DROP PROCEDURE IF EXISTS _users_update_direction;
112DELIMITER $$$
113CREATE PROCEDURE _users_update_direction(IN v_direction enum('L','R'), IN v_user_id int)
114BEGIN
115 IF v_user_id is not NULL THEN
116 update users
117 set
118 up_dir = v_direction
119 where
120 id = v_user_id;
121
122 call __equals2(ROW_COUNT(), 0, 1, concat('update ', v_direction, ' ', v_direction));
123 END IF;
124END$$$
125DELIMITER ;
126
127
128
129-- ================================== --
130
131
132
133/* insert / update rows in tree_metadata */
134
135DROP PROCEDURE IF EXISTS _users_metadata_update;
136DELIMITER $$$
137CREATE PROCEDURE _users_metadata_update(IN v_user_id int)
138BEGIN
139
140 -- insert new metadata
141 insert into users_tree_metadata(user1, user2)
142 with recursive users_tree(id, up, lc, rc, deep)
143 as (
144 select u.id, u.up, u.lc, u.rc, 1 from users u where id = v_user_id
145 union all
146 select u.id, u.up, u.lc, u.rc, users_tree.deep + 1 from users u, users_tree where u.id = users_tree.up
147 )
148 select v_user_id, id from users_tree;
149
150END$$$
151DELIMITER ;
152
153
154
155-- ================================== --
156
157
158
159/* rebuilds *ALL* rows in tree_metadata */
160
161DROP PROCEDURE IF EXISTS users_metadata_build;
162DELIMITER $$$
163CREATE PROCEDURE users_metadata_build()
164BEGIN
165 DECLARE v_finished int default 0;
166
167 DECLARE v_user_id int;
168 DECLARE v_user_lc int;
169 DECLARE v_user_rc int;
170
171 DECLARE my_cursor cursor for
172 select id, lc, rc from users;
173
174 DECLARE continue handler for not found
175 set v_finished = 1;
176
177 START TRANSACTION;
178
179 delete from users_tree_metadata;
180
181 OPEN my_cursor;
182
183 loop_label: LOOP
184
185 FETCH my_cursor INTO v_user_id, v_user_lc, v_user_rc;
186
187 IF v_finished THEN
188 LEAVE loop_label;
189 END IF;
190
191 call _users_metadata_update(v_user_id);
192
193 call _users_update_direction('L', v_user_lc);
194 call _users_update_direction('R', v_user_rc);
195
196 END LOOP;
197
198 CLOSE my_cursor;
199
200 COMMIT;
201
202END$$$
203DELIMITER ;
204
205
206
207-- ================================== --
208
209
210
211/* rebuilds *ALL* all directions in users */
212
213DROP PROCEDURE IF EXISTS users_dir_update;
214DELIMITER $$$
215CREATE PROCEDURE users_dir_update()
216BEGIN
217 DECLARE v_finished int default 0;
218
219 DECLARE v_user_id int;
220 DECLARE v_user_lc int;
221 DECLARE v_user_rc int;
222
223 DECLARE my_cursor cursor for
224 select id, lc, rc from users;
225
226 DECLARE continue handler for not found
227 set v_finished = 1;
228
229 START TRANSACTION;
230
231 OPEN my_cursor;
232
233 loop_label: LOOP
234
235 FETCH my_cursor INTO v_user_id, v_user_lc, v_user_rc;
236
237 IF v_finished THEN
238 LEAVE loop_label;
239 END IF;
240
241 call _users_update_direction('L', v_user_lc);
242 call _users_update_direction('R', v_user_rc);
243
244 END LOOP;
245
246 CLOSE my_cursor;
247
248 COMMIT;
249
250END$$$
251DELIMITER ;
252
253
254
255-- ================================== --
256
257
258
259DROP PROCEDURE IF EXISTS users_dir_find;
260DELIMITER $$$
261CREATE 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)
262BEGIN
263 DECLARE v_finished int default 0;
264
265 -- In MySQL there are no cursors from dynamic statements,
266 -- so we will use unions.
267 -- There are not much penalty for doing this way.
268 -- also if in transaction, will lock all records,
269 DECLARE my_cursor cursor for
270 with recursive _tree(id, up, lc, rc, deep)
271 as (
272 select u.id, u.up, u.lc, u.rc, 1 from users u where id = v_user_id
273 FOR UPDATE
274 union all
275 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'
276 FOR UPDATE
277 union all
278 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'
279 FOR UPDATE
280 )
281 select id from _tree;
282
283 DECLARE continue handler for not found
284 set v_finished = 1;
285
286 OPEN my_cursor;
287
288 -- loop over all records and get last one.
289 -- if in transaction,
290 -- FOR UPDATE will lock the records.
291 loop_label: LOOP
292
293 FETCH my_cursor INTO v_pos_user_id;
294
295 IF v_finished THEN
296 LEAVE loop_label;
297 END IF;
298
299 -- debug slow down...
300 -- select sleep(0.1);
301
302 -- debug
303 IF v_debug THEN
304
305 select 'Via node' as msg, users.* from users where id = v_pos_user_id;
306
307 END IF;
308
309 END LOOP;
310
311 CLOSE my_cursor;
312
313 -- debug
314 select 'Found at pos' as msg, users.* from users where id = v_pos_user_id;
315
316END$$$
317DELIMITER ;
318
319
320
321DROP PROCEDURE IF EXISTS users_dir_insert;
322DELIMITER $$$
323CREATE 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)
324BEGIN
325 DECLARE v_pos_user_id int;
326
327 DECLARE EXIT HANDLER FOR SQLEXCEPTION
328 BEGIN
329 SET v_success:=0;
330
331 ROLLBACK;
332
333 -- debug
334 call __show_exception();
335 END;
336
337 SET v_direction = upper(v_direction);
338
339 SET v_success:=1;
340
341 START TRANSACTION;
342
343 -- find_left will lock all records,
344 -- so nobody can inject new node on same place.
345 call users_dir_find(v_direction, v_parent_user_id, v_pos_user_id, v_debug);
346
347 insert into users
348 set
349 id = v_new_user_id ,
350 up = v_pos_user_id ,
351 up_dir = v_direction ;
352
353 -- update metadata
354 call _users_metadata_update(v_new_user_id);
355
356 IF v_direction = 'L' THEN
357
358 update users
359 set
360 lc = v_new_user_id
361 where
362 id = v_pos_user_id and
363 lc is NULL;
364
365 call __equals(ROW_COUNT(), 1, 'insert on the L');
366
367 ELSE -- v_direction = 'R'
368
369 update users
370 set
371 rc = v_new_user_id
372 where
373 id = v_pos_user_id and
374 rc is NULL;
375
376 call __equals(ROW_COUNT(), 1, 'insert on the R');
377
378 END IF;
379
380 COMMIT;
381
382 -- debug
383 select v_success, users.* from users where id = v_new_user_id;
384
385END$$$
386DELIMITER ;
387
388
389
390-- ================================== --
391
392
393
394DROP PROCEDURE IF EXISTS users_count_insert;
395DELIMITER $$$
396CREATE 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)
397BEGIN
398 DECLARE v_finished int default 0;
399
400 DECLARE v_pos_user_id int;
401 DECLARE v_pos_user_up_dir enum('L','R');
402 DECLARE v_pos_dir enum('L','R');
403
404 -- will lock all records, except first one.
405 DECLARE my_cursor cursor for
406 with recursive _tree(id, up, up_dir, deep)
407 as (
408 select u.id, u.up, u.up_dir, 1 from users u where id = v_user_id
409 union all
410 select u.id, u.up, u.up_dir, _tree.deep + 1 from users u, _tree where u.id = _tree.up
411 FOR UPDATE
412 )
413 select id, up_dir from _tree;
414
415 DECLARE EXIT HANDLER FOR SQLEXCEPTION
416 BEGIN
417 SET v_success:=0;
418
419 ROLLBACK;
420
421 -- debug
422 call __show_exception();
423 END;
424
425 DECLARE continue handler for not found
426 set v_finished = 1;
427
428 SET v_success:=1;
429
430 START TRANSACTION;
431
432 OPEN my_cursor;
433
434 loop_label: LOOP
435
436 set v_pos_dir:=v_pos_user_up_dir;
437
438 FETCH my_cursor INTO v_pos_user_id, v_pos_user_up_dir;
439
440 IF v_finished THEN
441 LEAVE loop_label;
442 END IF;
443
444 -- first record *always* exists and id is v_user_id
445 IF v_pos_user_id = v_user_id THEN
446 -- ITERATE is continue
447 ITERATE loop_label;
448 END IF;
449
450 IF v_pos_dir = 'L' THEN
451
452 update users set lcount = lcount + v_count where id = v_pos_user_id;
453
454 ELSE -- v_pos_dir = 'R'
455
456 update users set rcount = rcount + v_count where id = v_pos_user_id;
457
458 END IF;
459
460 -- this might fail and rollback
461 insert into users_tree_log values(v_payment_id, v_user_id, v_pos_user_id, v_pos_dir, v_count);
462
463 IF v_debug THEN
464
465 select 'Via node' as msg, v_pos_user_id, /* v_pos_user_up_dir, */ v_pos_dir;
466
467 END IF;
468
469 END LOOP;
470
471 CLOSE my_cursor;
472
473 COMMIT;
474
475END$$$
476DELIMITER ;
477
478
479
480-- ================================== --
481
482
483
484DROP PROCEDURE IF EXISTS users_dir_get;
485DELIMITER $$$
486CREATE 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)
487BEGIN
488 DECLARE v_finished int default 0;
489
490 DECLARE v_pos_user_id int;
491 DECLARE v_pos_user_up_dir enum('L','R');
492 DECLARE v_pos_dir enum('L','R');
493
494 -- will lock all records, except first one.
495 DECLARE my_cursor cursor for
496 with recursive _tree(id, up, up_dir, deep)
497 as (
498 select u.id, u.up, u.up_dir, 1 from users u where id = v_user_id
499 union all
500 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
501 )
502 select id, up_dir from _tree;
503
504 DECLARE continue handler for not found
505 set v_finished = 1;
506
507 SET v_direction:=NULL;
508
509 OPEN my_cursor;
510
511 loop_label: LOOP
512
513 set v_pos_dir:=v_pos_user_up_dir;
514
515 FETCH my_cursor INTO v_pos_user_id, v_pos_user_up_dir;
516
517 IF v_finished THEN
518 LEAVE loop_label;
519 END IF;
520
521 -- first record *always* exists and id is v_user_id
522 IF v_pos_user_id = v_user_id THEN
523 -- ITERATE is continue
524 ITERATE loop_label;
525 END IF;
526
527 IF v_pos_user_id = v_user_id_parent THEN
528
529 set v_direction:=v_pos_dir;
530
531 select 'Found' as msg, v_pos_user_id, v_pos_dir;
532
533 LEAVE loop_label;
534
535 END IF;
536
537 IF v_debug THEN
538
539 select 'Via node' as msg, v_pos_user_id, /* v_pos_user_up_dir, */ v_pos_dir;
540
541 END IF;
542
543 END LOOP;
544
545 COMMIT;
546
547END$$$
548DELIMITER ;
549
550
551
552-- ================================== --
553
554
555
556select "Done, you are awesome ;)" as msg;