PostgreSQLの with recursive をMySQLでエミュレートする

alkoshikawa 2,248views 更新:2014年3月13日

PostgreSQLで

create table empl (
    id serial primary key,
    name text,
    boss text default null
);

insert into empl (name, boss) values ('Paul',null);
insert into empl (name, boss) values ('Luke','Paul');
insert into empl (name, boss) values ('Kate','Paul');
insert into empl (name, boss) values ('Marge','Kate');
insert into empl (name, boss) values ('Edith','Kate');
insert into empl (name, boss) values ('Pam','Kate');
insert into empl (name, boss) values ('Carol','Luke');
insert into empl (name, boss) values ('John','Luke');
insert into empl (name, boss) values ('Jack','Carol');
insert into empl (name, boss) values ('Alex','Carol');

というテーブルがあるとします。

with recursive t(level,path,boss,name) as (
        select 0,name,boss,name from empl where boss is null
    union
        select
            level + 1,
            path || ' > ' || empl.name,
            empl.boss,
            empl.name 
        from 
            empl join t 
                on empl.boss = t.name
) select * from t order by path;
 level |            path            | boss  | name
-------+----------------------------+-------+-------
     0 | Paul                       |       | Paul
     1 | Paul > Kate                | Paul  | Kate
     2 | Paul > Kate > Edith        | Kate  | Edith
     2 | Paul > Kate > Marge        | Kate  | Marge
     2 | Paul > Kate > Pam          | Kate  | Pam
     1 | Paul > Luke                | Paul  | Luke
     2 | Paul > Luke > Carol        | Luke  | Carol
     3 | Paul > Luke > Carol > Alex | Carol | Alex
     3 | Paul > Luke > Carol > Jack | Carol | Jack
     2 | Paul > Luke > John         | Luke  | John

という結果がでます。

これをMySQLでやろうとすると

create table empl (
    id integer auto_increment,
    name text,
    boss text default null,
    key (id)
);

insert into empl (`name`, `boss`) values ('Paul',null);
insert into empl (`name`, `boss`) values ('Luke','Paul');
insert into empl (`name`, `boss`) values ('Kate','Paul');
insert into empl (`name`, `boss`) values ('Marge','Kate');
insert into empl (`name`, `boss`) values ('Edith','Kate');
insert into empl (`name`, `boss`) values ('Pam','Kate');
insert into empl (`name`, `boss`) values ('Carol','Luke');
insert into empl (`name`, `boss`) values ('John','Luke');
insert into empl (`name`, `boss`) values ('Jack','Carol');
insert into empl (`name`, `boss`) values ('Alex','Carol');

delimiter |

CREATE PROCEDURE WITH_EMULATOR(
recursive_table varchar(100), # name of recursive table
initial_SELECT varchar(21845), # seed a.k.a. anchor
recursive_SELECT varchar(21845), # recursive member
final_SELECT varchar(21845), # final SELECT on UNION result
max_recursion int unsigned, # safety against infinite loop, use 0 for default
create_table_options varchar(21845) # you can add CREATE-TABLE-time options
# to your recursive_table, to speed up initial/recursive/final SELECTs; example:
# "(KEY(some_column)) ENGINE=MEMORY"
)

BEGIN
  declare new_rows int unsigned;
  declare show_progress int default 0; # set to 1 to trace/debug execution
  declare recursive_table_next varchar(120);
  declare recursive_table_union varchar(120);
  declare recursive_table_tmp varchar(120);
  set recursive_table_next  = concat(recursive_table, "_next");
  set recursive_table_union = concat(recursive_table, "_union");
  set recursive_table_tmp   = concat(recursive_table, "_tmp");
  # If you need to reference recursive_table more than
  # once in recursive_SELECT, remove the TEMPORARY word.
  SET @str = # create and fill T0
    CONCAT("CREATE TEMPORARY TABLE ", recursive_table, " ",
    create_table_options, " AS ", initial_SELECT);
  PREPARE stmt FROM @str;
  EXECUTE stmt;
  SET @str = # create U
    CONCAT("CREATE TEMPORARY TABLE ", recursive_table_union, " LIKE ", recursive_table);
  PREPARE stmt FROM @str;
  EXECUTE stmt;
  SET @str = # create T1
    CONCAT("CREATE TEMPORARY TABLE ", recursive_table_next, " LIKE ", recursive_table);
  PREPARE stmt FROM @str;
  EXECUTE stmt;
  if max_recursion = 0 then
    set max_recursion = 100; # a default to protect the innocent
  end if;
  recursion: repeat
    # add T0 to U (this is always UNION ALL)
    SET @str =
      CONCAT("INSERT INTO ", recursive_table_union, " SELECT * FROM ", recursive_table);
    PREPARE stmt FROM @str;
    EXECUTE stmt;
    # we are done if max depth reached
    set max_recursion = max_recursion - 1;
    if not max_recursion then
      if show_progress then
        select concat("max recursion exceeded");
      end if;
      leave recursion;
    end if;
    # fill T1 by applying the recursive SELECT on T0
    SET @str =
      CONCAT("INSERT INTO ", recursive_table_next, " ", recursive_SELECT);
    PREPARE stmt FROM @str;
    EXECUTE stmt;
    # we are done if no rows in T1
    select row_count() into new_rows;
    if show_progress then
      select concat(new_rows, " new rows found");
    end if;
    if not new_rows then
      leave recursion;
    end if;
    # Prepare next iteration:
    # T1 becomes T0, to be the source of next run of recursive_SELECT,
    # T0 is recycled to be T1.
    SET @str =
      CONCAT("ALTER TABLE ", recursive_table, " RENAME ", recursive_table_tmp);
    PREPARE stmt FROM @str;
    EXECUTE stmt;
    # we use ALTER TABLE RENAME because RENAME TABLE does not support temp tables
    SET @str =
      CONCAT("ALTER TABLE ", recursive_table_next, " RENAME ", recursive_table);
    PREPARE stmt FROM @str;
    EXECUTE stmt;
    SET @str =
      CONCAT("ALTER TABLE ", recursive_table_tmp, " RENAME ", recursive_table_next);
    PREPARE stmt FROM @str;
    EXECUTE stmt;
    # empty T1
    SET @str =
      CONCAT("TRUNCATE TABLE ", recursive_table_next);
    PREPARE stmt FROM @str;
    EXECUTE stmt;
  until 0 end repeat;
  # eliminate T0 and T1
  SET @str =
    CONCAT("DROP TEMPORARY TABLE ", recursive_table_next, ", ", recursive_table);
  PREPARE stmt FROM @str;
  EXECUTE stmt;
  # Final (output) SELECT uses recursive_table name
  SET @str =
    CONCAT("ALTER TABLE ", recursive_table_union, " RENAME ", recursive_table);
  PREPARE stmt FROM @str;
  EXECUTE stmt;
  # Run final SELECT on UNION
  SET @str = final_SELECT;
  PREPARE stmt FROM @str;
  EXECUTE stmt;
  # No temporary tables may survive:
  SET @str =
    CONCAT("DROP TEMPORARY TABLE ", recursive_table);
  PREPARE stmt FROM @str;
  EXECUTE stmt;
  # We are done :-)
END|

delimiter ;
CALL WITH_EMULATOR(
  "t",
  "select 0 as level,name as path, boss, name from empl where boss is null",
  "select level + 1, concat(concat(path, ' > '), empl.name), empl.boss, empl.name from empl join t on empl.boss = t.name",
  "select * from t order by path",
  "0",
  ""
);
| level | path                       | boss  | name  |
+-------+----------------------------+-------+-------+
|     0 | Paul                       | NULL  | Paul  |
|     1 | Paul > Kate                | Paul  | Kate  |
|     2 | Paul > Kate > Edith        | Kate  | Edith |
|     2 | Paul > Kate > Marge        | Kate  | Marge |
|     2 | Paul > Kate > Pam          | Kate  | Pam   |
|     1 | Paul > Luke                | Paul  | Luke  |
|     2 | Paul > Luke > Carol        | Luke  | Carol |
|     3 | Paul > Luke > Carol > Alex | Carol | Alex  |
|     3 | Paul > Luke > Carol > Jack | Carol | Jack  |
|     2 | Paul > Luke > John         | Luke  | John  |

となります。

ただし実行速度には非常に大きな差があるため、MySQLでは再帰検索は可能な限り使用しないほうが良さそうです。

参考

http://guilhembichot.blogspot.co.uk/2013/11/with-recursive-and-mysql.html

ログイン / 新規登録してコメントする

このソースコードをストックして後で利用したり、作業に利用したソースコードをまとめることができます。

こちらもお役に立つかもしれません