WITH RECURSIVE and MySQL

[2017 update: MySQL 8.0.1 now features SQL-standard CTE syntax; more information is here ; the entry below, from 2013, shows how to work around the absence of CTEs in older MySQL versions.]

If you have been using certain DBMSs, or reading recent versions of the SQL standard, you are probably aware of the so-called "WITH clause" of SQL.
Some call it Subquery Factoring. Others call it Common Table Expression (CTE). In its simplest form, this feature is a kind of "boosted derived table".

Assume that a table T1 has three columns:

CREATE TABLE T1(
YEAR INT, # 2000, 2001, 2002 ...
MONTH INT, # January, February, ...
SALES INT # how much we sold on that month of that year
);
Now I want to know the sales trend (increase/decrease), year after year:

SELECT D1.YEAR, (CASE WHEN D1.S>D2.S THEN 'INCREASE' ELSE 'DECREASE' END) AS TREND
FROM
  (SELECT YEAR, SUM(SALES) AS S FROM T1 GROUP BY YEAR) AS D1,
  (SELECT YEAR, SUM(SALES) AS S FROM T1 GROUP BY YEAR) AS D2
WHERE D1.YEAR = D2.YEAR-1;
Both derived tables are based on the same subquery text, but usually a DBMS is not smart enough to recognize it. Thus, it will evaluate "SELECT YEAR, SUM(SALES)... GROUP BY YEAR" twice! A first time to fill D1, a second time to fill D2. This limitation is sometimes stated as "it's not possible to refer to a derived table twice in the same query".
Such double evaluation can lead to a serious performance problem. Using WITH, this limitation does not exist, and the following statement evaluates the subquery only once:

WITH D AS (SELECT YEAR, SUM(SALES) AS S FROM T1 GROUP BY YEAR)
SELECT D1.YEAR, (CASE WHEN D1.S>D2.S THEN 'INCREASE' ELSE 'DECREASE' END) AS TREND
FROM
 D AS D1,
 D AS D2
WHERE D1.YEAR = D2.YEAR-1;
This already demonstrates one benefit of WITH.
In MySQL, WITH is not yet supported. But it can be emulated with a view:

CREATE VIEW D AS (SELECT YEAR, SUM(SALES) AS S FROM T1 GROUP BY YEAR);
SELECT D1.YEAR, (CASE WHEN D1.S>D2.S THEN 'INCREASE' ELSE 'DECREASE' END) AS TREND
FROM
 D AS D1,
 D AS D2
WHERE D1.YEAR = D2.YEAR-1;
DROP VIEW D;
Instead of a view, I could as well create D as a normal table. But not as a temporary table, because in MySQL a temporary table cannot be referred twice in the same query, as mentioned in the manual.

After this short introduction, showing the simplest form of WITH, I would like to turn to the more complex form of WITH: the RECURSIVE form.
According to the SQL standard, to use the recursive form, you should write WITH RECURSIVE. However, looking at some other DBMSs, they seem to not require the RECURSIVE word.
WITH RECURSIVE is a powerful construct. For example, it can do the same job as Oracle's CONNECT BY clause (you can check out some example conversions between both constructs).
Let's walk through an example, to understand what WITH RECURSIVE does.

Assume you have a table of employees (this is a very classical example of WITH RECURSIVE):

CREATE TABLE EMPLOYEES (
ID INT PRIMARY KEY,
NAME VARCHAR(100),
MANAGER_ID INT,
INDEX (MANAGER_ID),
FOREIGN KEY (MANAGER_ID) REFERENCES EMPLOYEES(ID)
);
INSERT INTO EMPLOYEES VALUES
(333, "Yasmina", NULL),
(198, "John", 333),
(29, "Pedro", 198),
(4610, "Sarah", 29),
(72, "Pierre", 29),
(692, "Tarek", 333);
In other words, Yasmina is CEO, John and Tarek report to her. Pedro reports to John, Sarah and Pierre report to Pedro.
In a big company, they would be thousands of rows in this table.

Now, let's say that you would like to know, for each employee: "how many people are, directly and indirectly, reporting to him/her"? Here is how I would do it. First, I would make a list of people who are not managers: with a subquery I get the list of all managers, and using NOT IN (subquery) I get the list of all non-managers:

SELECT ID, NAME, MANAGER_ID, 0 AS REPORTS
FROM EMPLOYEES
WHERE ID NOT IN (SELECT MANAGER_ID FROM EMPLOYEES WHERE MANAGER_ID IS NOT NULL);
Then I would insert the results into a new table named EMPLOYEES_EXTENDED; EXTENDED stands for "extended with more information", the new information being the fourth column named REPORTS: it is a count of people who are reporting directly or indirectly to the employee. Because  we have listed people who are not managers, they have a value of 0 in the REPORTS column.
Then, we can produce the rows for "first level" managers (the direct managers of non-managers):

SELECT M.ID, M.NAME, M.MANAGER_ID, SUM(1+E.REPORTS) AS REPORTS
FROM EMPLOYEES M JOIN EMPLOYEES_EXTENDED E ON M.ID=E.MANAGER_ID
GROUP BY M.ID, M.NAME, M.MANAGER_ID;
Explanation: for a row of M (that is, for an employee), the JOIN will produce zero or more rows, one per non-manager directly reporting to the employee.
Each such non-manager contributes to the value of REPORTS for his manager, through two numbers: 1 (the non-manager himself), and the number of direct/indirect reports of the non-manager (i.e. the value of REPORTS for the non-manager).
Then I would empty EMPLOYEES_EXTENDED, and fill it with the rows produced just above, which describe the first level managers.
Then the same query should be run again, and it would produce information about the "second level" managers. And so on.
Finally, at one point Yasmina will be the only row of EMPLOYEES_EXTENDED, and when we run the above SELECT again, the JOIN will produce no rows, because E.MANAGER_ID will be NULL (she's the CEO). We are done.

It's time for a recap: EMPLOYEES_EXTENDED has been a kind of "temporary buffer", which has successively held non-managers, first level managers, second level managers, etc. We have used recursion. The answer to the original problem is: the union of all the successive content of EMPLOYEES_EXTENDED.
Non-managers have been the start of the recursion, which is usually called "the anchor member" or "the seed". The SELECT query which moves from one step of  recursion to the next one, is the "recursive member". The complete statement looks like this:

WITH RECURSIVE
# The temporary buffer, also used as UNION result:
EMPLOYEES_EXTENDED
AS
(
  # The seed:
  SELECT ID, NAME, MANAGER_ID, 0 AS REPORTS
  FROM EMPLOYEES
  WHERE ID NOT IN (SELECT MANAGER_ID FROM EMPLOYEES WHERE MANAGER_ID IS NOT NULL)
UNION ALL
  # The recursive member:
  SELECT M.ID, M.NAME, M.MANAGER_ID, SUM(1+E.REPORTS) AS REPORTS
  FROM EMPLOYEES M JOIN EMPLOYEES_EXTENDED E ON M.ID=E.MANAGER_ID
  GROUP BY M.ID, M.NAME, M.MANAGER_ID
)
# what we want to do with the complete result (the UNION):
SELECT * FROM EMPLOYEES_EXTENDED;
MySQL does not yet support WITH RECURSIVE, but it is possible to code a generic stored procedure which can easily emulate it. Here is how you would call it:

CALL WITH_EMULATOR(
"EMPLOYEES_EXTENDED",
"
  SELECT ID, NAME, MANAGER_ID, 0 AS REPORTS
  FROM EMPLOYEES
  WHERE ID NOT IN (SELECT MANAGER_ID FROM EMPLOYEES WHERE MANAGER_ID IS NOT NULL)
",
"
  SELECT M.ID, M.NAME, M.MANAGER_ID, SUM(1+E.REPORTS) AS REPORTS
  FROM EMPLOYEES M JOIN EMPLOYEES_EXTENDED E ON M.ID=E.MANAGER_ID
  GROUP BY M.ID, M.NAME, M.MANAGER_ID
",
"SELECT * FROM EMPLOYEES_EXTENDED",
0,
""
);
You can recognize, as arguments of the stored procedure, every member of the WITH standard syntax: name of the temporary buffer, query for the seed, query for the recursive member, and what to do with the complete result. The last two arguments - 0 and the empty string - are details which you can ignore for now.

Here is the result returned by this stored procedure:

+------+---------+------------+---------+
| ID   | NAME    | MANAGER_ID | REPORTS |
+------+---------+------------+---------+
|   72 | Pierre  |         29 |       0 |
|  692 | Tarek   |        333 |       0 |
| 4610 | Sarah   |         29 |       0 |
|   29 | Pedro   |        198 |       2 |
|  333 | Yasmina |       NULL |       1 |
|  198 | John    |        333 |       3 |
|  333 | Yasmina |       NULL |       4 |
+------+---------+------------+---------+
7 rows in set
Notice how Pierre, Tarek and Sarah have zero reports, Pedro has two, which looks correct... However, Yasmina appears in two rows! Odd? Yes and no. Our algorithm starts from non-managers, the "leaves" of the tree (Yasmina being the root of the tree). Then our algorithm looks at first level managers, the direct parents of leaves. Then at second level managers. But Yasmina is both a first level manager (of the nonmanager Tarek) and a third level manager (of the nonmanagers Pierre and Sarah). That's why she appears twice in the final result: once for the "tree branch" which ends at leaf Tarek, once for the tree branch which ends at leaves Pierre and Sarah. The first tree branch contributes 1 direct/indirect report. The second tree branch contributes 4. The right number, which we want, is the sum of the two: 5. Thus we just need to change the final query, in the CALL:

CALL WITH_EMULATOR(
"EMPLOYEES_EXTENDED",
"
  SELECT ID, NAME, MANAGER_ID, 0 AS REPORTS
  FROM EMPLOYEES
  WHERE ID NOT IN (SELECT MANAGER_ID FROM EMPLOYEES WHERE MANAGER_ID IS NOT NULL)
",
"
  SELECT M.ID, M.NAME, M.MANAGER_ID, SUM(1+E.REPORTS) AS REPORTS
  FROM EMPLOYEES M JOIN EMPLOYEES_EXTENDED E ON M.ID=E.MANAGER_ID
  GROUP BY M.ID, M.NAME, M.MANAGER_ID
",
"
  SELECT ID, NAME, MANAGER_ID, SUM(REPORTS)
  FROM EMPLOYEES_EXTENDED
  GROUP BY ID, NAME, MANAGER_ID
",
0,
""
);
And here is finally the proper result:

+------+---------+------------+--------------+
| ID   | NAME    | MANAGER_ID | SUM(REPORTS) |
+------+---------+------------+--------------+
|   29 | Pedro   |        198 |            2 |
|   72 | Pierre  |         29 |            0 |
|  198 | John    |        333 |            3 |
|  333 | Yasmina |       NULL |            5 |
|  692 | Tarek   |        333 |            0 |
| 4610 | Sarah   |         29 |            0 |
+------+---------+------------+--------------+
6 rows in set
Let's finish by showing the body of the stored procedure. You will notice that it does heavy use of dynamic SQL, thanks to prepared statements. Its body does not depend on the particular problem to solve, it's reusable as-is for other WITH RECURSIVE use cases. I have added comments inside the body, so it should be self-explanatory. If it's not, feel free to drop a comment on this post, and I will explain further. Note that it uses temporary tables internally, and the first thing it does is dropping any temporary tables with the same names.

# Usage: the standard syntax:
#   WITH RECURSIVE recursive_table AS
#    (initial_SELECT
#     UNION ALL
#     recursive_SELECT)
#   final_SELECT;
# should be translated by you to 
# CALL WITH_EMULATOR(recursive_table, initial_SELECT, recursive_SELECT,
#                    final_SELECT, 0, "").

# ALGORITHM:
# 1) we have an initial table T0 (actual name is an argument
# "recursive_table"), we fill it with result of initial_SELECT.
# 2) We have a union table U, initially empty.
# 3) Loop:
#   add rows of T0 to U,
#   run recursive_SELECT based on T0 and put result into table T1,
#   if T1 is empty
#      then leave loop,
#      else swap T0 and T1 (renaming) and empty T1
# 4) Drop T0, T1
# 5) Rename U to T0
# 6) run final select, send relult to client

# This is for *one* recursive table.
# It would be possible to write a SP creating multiple recursive tables.

delimiter |

CREATE PROCEDURE WITH_EMULATOR(
recursive_table varchar(100), # name of recursive table
initial_SELECT varchar(65530), # seed a.k.a. anchor
recursive_SELECT varchar(65530), # recursive member
final_SELECT varchar(65530), # final SELECT on UNION result
max_recursion int unsigned, # safety against infinite loop, use 0 for default
create_table_options varchar(65530) # 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"); 
  # Cleanup any previous failed runs
  SET @str =
    CONCAT("DROP TEMPORARY TABLE IF EXISTS ", recursive_table, ",",
    recursive_table_next, ",", recursive_table_union,
    ",", recursive_table_tmp);
  PREPARE stmt FROM @str;
  EXECUTE stmt; 
 # 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 ;

Update from 2017:

MySQL now supports recursive CTEs natively, since version 8.0.1 (see here).

However, while working on the development of this feature, I discovered something which I didn't know back when I wrote this blog in 2013: that GROUP BY is not allowed in the recursive member, neither in the SQL Standard nor in other main DBMSs. So I have not allowed it in MySQL either. That means that my proposed query using WITH RECURSIVE, above, has to be modified: aggregation has to be done outside of the CTE's generation. So here is a modified query: starting with all employees of the company, the first iteration connects them to their boss, producing rows of the form "employee X is managed by Y" (X and Y are IDs); the second iteration connects that row to the boss of Y, producing rows of the form "employee X is indirectly managed by Z"; the third iteration connects it to the boss of Z: "employee X is indirectly managed by T". When the CTE is done, by reading it we can find the list of all people who are indirectly managed by Z (for example), and, with grouping, produce a group of Z and its count of reports; that's the job of the second CTE, which is non-recursive (and can thus use aggregation). Finally, we join that with the table of employees to get names instead of IDs, for clarity. We use a left join so we get rows for non-managers too, and COALESCE for those get a count of reports of 0 instead of NULL (easier to read). All in all:

WITH RECURSIVE
EMPLOYEES_EXTENDED
AS
(
  SELECT ID, NAME, MANAGER_ID
  FROM EMPLOYEES
UNION ALL
  SELECT E.ID, E.NAME, M.MANAGER_ID
  FROM EMPLOYEES M JOIN EMPLOYEES_EXTENDED E ON M.ID=E.MANAGER_ID
),
REPORTS_COUNT (ID, REPORTS)
AS
( SELECT MANAGER_ID, COUNT(*) FROM EMPLOYEES_EXTENDED GROUP BY MANAGER_ID )
SELECT EMPLOYEES.*, COALESCE(REPORTS,0) FROM EMPLOYEES LEFT JOIN REPORTS_COUNT
ON EMPLOYEES.ID = REPORTS_COUNT.ID;
and here is the result:

+------+---------+------------+---------------------+
| ID   | NAME    | MANAGER_ID | COALESCE(REPORTS,0) |
+------+---------+------------+---------------------+
|   29 | Pedro   |        198 |                   2 |
|   72 | Pierre  |         29 |                   0 |
|  198 | John    |        333 |                   3 |
|  333 | Yasmina |       NULL |                   5 |
|  692 | Tarek   |        333 |                   0 |
| 4610 | Sarah   |         29 |                   0 |
+------+---------+------------+---------------------+
6 rows in set (0.04 sec)
And here is the equivalent using WITH_EMULATOR if your MySQL is older than 8.0:


CALL WITH_EMULATOR(
"EMPLOYEES_EXTENDED",
"SELECT ID, NAME, MANAGER_ID FROM EMPLOYEES",
"SELECT E.ID, E.NAME, M.MANAGER_ID
FROM EMPLOYEES M JOIN EMPLOYEES_EXTENDED E ON M.ID=E.MANAGER_ID",
"SELECT EMPLOYEES.*, COALESCE(REPORTS,0) FROM
EMPLOYEES LEFT JOIN
 ( SELECT MANAGER_ID AS ID, COUNT(*) AS REPORTS FROM
   EMPLOYEES_EXTENDED GROUP BY MANAGER_ID ) AS REPORTS_COUNT
ON EMPLOYEES.ID = REPORTS_COUNT.ID",
0,
""
);

Commentaires

  1. Great ! Thanks !!!!! It might be very helpfull !

    RépondreSupprimer
  2. How to find dependencies of a whole DataBase in mysql,

    like here I have Sales database and I want to get dependencies of whole Database with Level as well.

    Like below link Image::
    http://i.stack.imgur.com/eeNlo.png

    RépondreSupprimer
  3. I want to use your RECURSIVE MySQL method. How I have write all three queries.

    RépondreSupprimer
  4. Irfan: I'd need more details to understand what you're aiming at.

    RépondreSupprimer
  5. I actually need replica of this WITH function which is in SQLServer::

    with Fkeys as (

    select distinct

    OnTable = OnTable.name
    ,AgainstTable = AgainstTable.name

    from

    sysforeignkeys fk

    inner join sysobjects onTable
    on fk.fkeyid = onTable.id

    inner join sysobjects againstTable
    on fk.rkeyid = againstTable.id

    where 1=1
    AND AgainstTable.TYPE = 'U'
    AND OnTable.TYPE = 'U'
    -- ignore self joins; they cause an infinite recursion
    and OnTable.Name <> AgainstTable.Name
    )

    ,MyData as (

    select
    OnTable = o.name
    ,AgainstTable = FKeys.againstTable

    from

    sys.objects o

    left join FKeys
    on o.name = FKeys.onTable

    where o.type = 'U'

    )

    ,MyRecursion as (

    -- base case
    select
    TableName = OnTable
    ,Lvl = 1
    from
    MyData
    where 1=1
    and AgainstTable is null

    -- recursive case
    union all select
    TableName = OnTable
    ,Lvl = r.Lvl + 1
    from
    MyData d
    inner join MyRecursion r
    on d.AgainstTable = r.TableName
    )
    select
    Lvl = max(Lvl)
    ,TableName

    from
    MyRecursion

    group by
    TableName
    order by
    1 asc
    ,2 asc

    RépondreSupprimer
  6. you and copy and past this function with any particular Database and and would easily understand what I need. I'm in a very quick need of this for MySQL. Please help me out.

    RépondreSupprimer
  7. did u (Uilhem Bichot) look into it.

    RépondreSupprimer
  8. Hi. I guess you should first create a temporary table to contain fkeys:
    create temporary table fkeys select ... ;
    then another one to contain mydata. Then the RECURSIVE part:
    call with_emulator(
    "myrecursion",
    "",
    "",
    etc);
    you can check the blog for the exact arguments to give to with_emulator(). I recommend using a low value of max_recursion as a safety for your first tests.

    RépondreSupprimer
  9. Hi Guilhem,
    Thank you for this info!! This could be huge for a project I'm working on, but I need some additional help. My "EMPLOYEES" table needs to be created as a temporary table, and my "seed" table needs to be limited to the results from EMPLOYEES where value=userInput.

    In real terms, my EMPLOYEES table (named tempAll) is a list of all Issues with dependencies defined, created on-the-fly/temp. The seed table will then be:
    create temporary table seed (SourceKey varchar(50), SourceID int, SourceStatus DECIMAL(18,0), SourceAssign varchar(50), SUMMARY varchar(1000), state varchar(50)
    , DestKey varchar(50), DestID int , DestStatus DECIMAL(18,0), DestAssign varchar(50));
    insert into seed
    select distinct(a.SourceKey), a.SourceID, a.SourceStatus, a.SourceAssign, a.SUMMARY, a.state, a.DestKey, a.DestID, a.DestStatus, a.DestAssign
    from tempAll a
    where a.SourceKey=upper(inpIssue);

    Can you help me set this up?

    RépondreSupprimer
    Réponses
    1. After filling the "seed" table as you described
      (with CREATE and INSERT), then the 2nd argument to "CALL WITH_EMULATOR" could be:
      "select * from seed".

      Supprimer
  10. Thanks Guilhem... But where do I include the user-entered inpIssue value for the seed table (last line... WHERE a.SourceKey=upper(inpIssue);? I tried to make it an additional argument but that did not work.

    RépondreSupprimer
    Réponses
    1. You can do create a new stored procedure:
      - which takes an "inpIssue" argument,
      - and creates the tmp table "seed" and fills it, using the value of inpIssue
      - and does
      CALL WITH_EMULATOR(...);

      Supprimer
  11. Thanks again. I believe I have that working, but I get a permissions error for EMPLOYEES_EXTENDED_tmp. This table is not formed using the 'create temporary table' command, but rather via the 'alter table... rename' command. Is this command failing to make EMPLOYEES_EXTENDED_tmp a temporary table?

    RépondreSupprimer
  12. Johnny: we'd go faster if you showed me the complete SQL you're using, with the error you get. Let's do it privately by email (find my email by searching in
    http://upstream.rosalinux.ru/changelogs/mysql/5.5.21/changelog.html for example).

    RépondreSupprimer
  13. Hi Guilhem Bichot,

    I have a nested set traversal problem and would like to implement the same in MySQL. Below is the standalone script to achieve the tree structure. How do we do this in MySQL? I am new to this database. please help

    WITH TEMP (child,parent,value) AS (
    SELECT 1, 0, 'a' UNION ALL
    SELECT 2, 1, 'b' UNION ALL
    SELECT 3, 1, 'c' UNION ALL
    SELECT 4, 2, 'd' UNION ALL
    SELECT 5, 3, 'e' UNION ALL
    SELECT 6, 4, 'f' UNION ALL
    SELECT 7, 4, 'g' UNION ALL
    SELECT 8, 5, 'h' UNION ALL
    SELECT 9, 5, 'i' UNION ALL
    SELECT 10, 6, 'j' UNION ALL
    SELECT 11, 6, 'k' UNION ALL
    SELECT 12, 6, 'l' UNION ALL
    SELECT 13, 8, 'm' UNION ALL
    SELECT 14, 8, 'n' UNION ALL
    SELECT 15, 8, 'o' UNION ALL
    SELECT 16, 10, 'p' UNION ALL
    SELECT 17, 14, 'q' UNION ALL
    SELECT 18, 16, 'r' UNION ALL
    SELECT 19, 17, 's' UNION ALL
    SELECT 20, 18, 'tc' UNION ALL
    SELECT 21, 18, 'tb' UNION ALL
    SELECT 22, 18, 'ta' UNION ALL
    SELECT 23, 19, 'ub' UNION ALL
    SELECT 24, 19, 'ua' UNION ALL
    SELECT 25, 19, 'uc' UNION ALL
    SELECT 26, 20, 'va' UNION ALL
    SELECT 27, 20, 'vc' UNION ALL
    SELECT 28, 20, 'vb' UNION ALL
    SELECT 29, 24, 'w' UNION ALL
    SELECT 30, 27, 'x' )

    RépondreSupprimer

  14. SELECT j1.parent j1p, j1.value j1val,j1.child j1c,
    j2.child j2c,j2.value j2val,
    j3.child j3c,j3.value j3val,
    j4.child j4c,
    j5.child j5c,
    j6.child j6c,
    j7.child j7c,
    j8.child j8c,
    j9.child j9c,
    j10.child j10c,
    CASE WHEN j10.child IS NULL THEN
    CASE WHEN j9.child IS NULL THEN
    CASE WHEN j8.child IS NULL THEN
    CASE WHEN j7.child IS NULL THEN
    CASE WHEN j6.child IS NULL THEN
    CASE WHEN j5.child IS NULL THEN
    CASE WHEN j4.child IS NULL THEN
    CASE WHEN j3.child IS NULL THEN
    CASE WHEN j2.child IS NULL THEN j1.value
    ELSE j2.value END
    ELSE j3.value END
    ELSE j4.value END
    ELSE j5.value END
    ELSE j6.value END
    ELSE j7.value END
    ELSE j8.value END
    ELSE j9.value END
    ELSE j10.value END AS v1,
    CASE WHEN j10.child IS NULL THEN
    CASE WHEN j9.child IS NULL THEN
    CASE WHEN j8.child IS NULL THEN
    CASE WHEN j7.child IS NULL THEN
    CASE WHEN j6.child IS NULL THEN
    CASE WHEN j5.child IS NULL THEN
    CASE WHEN j4.child IS NULL THEN
    CASE WHEN j3.child IS NULL THEN
    CASE WHEN j2.child IS NULL THEN CAST(NULL AS INT)
    ELSE j2.value END
    ELSE j3.value END
    ELSE j4.value END
    ELSE j5.value END
    ELSE j6.value END
    ELSE j7.value END
    ELSE j8.value END
    ELSE j9.value END AS v2,
    CASE WHEN j10.child IS NULL THEN
    CASE WHEN j9.child IS NULL THEN
    CASE WHEN j8.child IS NULL THEN
    CASE WHEN j7.child IS NULL THEN
    CASE WHEN j6.child IS NULL THEN
    CASE WHEN j5.child IS NULL THEN
    CASE WHEN j4.child IS NULL THEN j1.value
    ELSE j2.value END
    ELSE j3.value END
    ELSE j4.value END
    ELSE j5.value END
    ELSE j6.value END
    ELSE j7.value END
    ELSE j8.value END AS v3,
    CASE WHEN j10.child IS NULL THEN
    CASE WHEN j9.child IS NULL THEN
    CASE WHEN j8.child IS NULL THEN
    CASE WHEN j7.child IS NULL THEN
    CASE WHEN j6.child IS NULL THEN
    CASE WHEN j5.child IS NULL THEN j1.value
    ELSE j2.value END
    ELSE j3.value END
    ELSE j4.value END
    ELSE j5.value END
    ELSE j6.value END
    ELSE j7.value END AS v4,
    CASE WHEN j10.child IS NULL THEN
    CASE WHEN j9.child IS NULL THEN
    CASE WHEN j8.child IS NULL THEN
    CASE WHEN j7.child IS NULL THEN
    CASE WHEN j6.child IS NULL THEN j1.value
    ELSE j2.value END
    ELSE j3.value END
    ELSE j4.value END
    ELSE j5.value END
    ELSE j6.value END AS v5,
    CASE WHEN j10.child IS NULL THEN
    CASE WHEN j9.child IS NULL THEN
    CASE WHEN j8.child IS NULL THEN
    CASE WHEN j7.child IS NULL THEN j1.value
    ELSE j2.value END
    ELSE j3.value END
    ELSE j4.value END
    ELSE j5.value END AS v6,
    CASE WHEN j10.child IS NULL THEN
    CASE WHEN j9.child IS NULL THEN
    CASE WHEN j8.child IS NULL THEN j1.value
    ELSE j2.value END
    ELSE j3.value END
    ELSE j4.value END AS v7,
    CASE WHEN j10.child IS NULL THEN
    CASE WHEN j9.child IS NULL THEN j1.value
    ELSE j2.value END
    ELSE j3.value END AS v8,
    CASE WHEN j10.child IS NULL THEN j1.value
    ELSE j2.value END AS v9,
    j1.value v10
    FROM temp j1
    LEFT JOIN temp j2 ON j1.parent = j2.child
    LEFT JOIN temp j3 ON j2.parent = j3.child
    LEFT JOIN temp j4 ON j3.parent = j4.child
    LEFT JOIN temp j5 ON j4.parent = j5.child
    LEFT JOIN temp j6 ON j5.parent = j6.child
    LEFT JOIN temp j7 ON j6.parent = j7.child
    LEFT JOIN temp j8 ON j7.parent = j8.child
    LEFT JOIN temp j9 ON j8.parent = j9.child
    LEFT JOIN temp j10 ON j9.parent = j10.child
    ORDER BY v1,v2,v3,v4,v5,v6,v7,v8,v9,v10;

    RépondreSupprimer
  15. Réponses
    1. realspirituals: it's likely possible with WITH_EMULATOR:
      - in your seed SELECT put the initial node of your list
      - in your recursive SELECT, join the temporary table with your list.
      You can check the EMPLOYEES example above, it uses the same idea.

      Supprimer
  16. Hi, Guilhem!

    You write:
    1. "you can check out some example conversions between both constructs"
    but link is not valid

    2. "and a third level manager (of the nonmanagers Pierre, Tarek and Sarah)"
    must be
    "and a third level manager (of the nonmanagers Pierre and Sarah)"

    3. "once for the tree branch which ends at leaves Pierre, Tarek and Sarah."
    must be
    "once for the tree branch which ends at leaves Pierre and Sarah."

    4. "# No temporary tables may survive:
    SET @str =
    CONCAT("DROP TEMPORARY TABLE ", recursive_table);"
    must be
    "# No temporary tables may survive:
    SET @str =
    CONCAT("DROP TEMPORARY TABLE ", recursive_table, ", ", recursive_table_union);"

    Thank you for good article.

    RépondreSupprimer
    Réponses
    1. Hello Vasiliy!
      Thanks for the thorough proof-reading :-)
      1. Yes, the blog which I was pointing to, is closed now; I replaced it with a link to an archived page.
      2. and 3. fixed.
      4. Actually the table "recursive_table_union" doesn't exist when the procedure ends because it has been renamed by this:
      # Final (output) SELECT uses recursive_table name
      SET @str =
      CONCAT("ALTER TABLE ", recursive_table_union, " RENAME ", recursive_table);
      PREPARE stmt FROM @str;
      EXECUTE stmt;

      Supprimer
    2. There is translate of your article in russian language – http://sqlinfo.ru/articles/info/22.html
      Looking forward to your new articles.

      Supprimer
    3. Thank you Vasiliy, you're doing a lot of work! Yes, there will be more CTE articles soon.

      Supprimer
  17. Thanks for providing this informative information. it is very useful you may also refer- http://www.s4techno.com/blog/2016/08/07/interview-questions-of-mysql/

    RépondreSupprimer
  18. Hi Guilhem.
    Thanks for that post.
    Actually, with constructs now work on mysql.
    Thus, the with construction do not allow aggregate functions and group by statements in the recursive part. So I am stuck... How would I fix this ?

    RépondreSupprimer
    Réponses
    1. Hi. Yes, per the SQL standard, WITH RECURSIVE behaves as you say. So my examples above, while they worked with the stored procedure, have to be rewritten in a different way to work with WITH RECURSIVE; in short, the aggregation has to be taken out of the WITH() block, to the query which reads the CTE. I'll try to get you an example soon.

      Supprimer
    2. I just added, in this blog page, towards the end, a paragraph about the problem ("Update from 2017") and a suggested query.

      Supprimer
  19. Hi Guilhem,
    Thank you for mysql query with CALL function. You made my day ;) almost ;)
    I've an issue, query run pretty well, but total numbers are not correct for me ;(

    my query is

    CALL WITH_EMULATOR(
    "bolt_accounts_extended",
    "
    SELECT managerid, NAME, parentid, 0 AS reports
    FROM bolt_accounts
    WHERE managerid NOT IN (SELECT parentid FROM bolt_accounts WHERE parentid IS NOT NULL and datechanged between date_format(now(),'%Y-%m-%d 00:00:00') and date_format(now(),'%Y-%m-%d 23:59:59'))
    and datechanged between date_format(now(),'%Y-%m-%d 00:00:00') and date_format(now(),'%Y-%m-%d 23:59:59')
    ",
    "
    SELECT M.managerid, M.NAME, M.parentid, SUM(1+E.REPORTS) AS REPORTS
    FROM bolt_accounts M JOIN bolt_accounts_extended E ON M.managerid=E.parentid
    where M.datechanged between date_format(now(),'%Y-%m-%d 00:00:00') and date_format(now(),'%Y-%m-%d 23:59:59')
    GROUP BY M.managerid, M.NAME, M.parentid
    ",
    "
    SELECT managerid, NAME, parentid, SUM(REPORTS)
    FROM bolt_accounts_extended
    GROUP BY managerid, NAME, parentid
    ",
    0,
    ""
    )

    I use datechanged to sort managerid accounts are they active, or they were deleted from PARENT system.
    So The query runs smooth, it returns 913 record (the exact number how much active managerid is!).
    But after, when I check records, I can see that the HEAD of managers, having sum of all managerid's = 1049, but we know the true number = 913. I tried to understand, where recursive get wrong, but have no luck.
    Could you help me or explaine why it happened?

    RépondreSupprimer
  20. Hello. I don't see anything wrong in your query. I suggest testing against MySQL 8.0 which has native support for WITH RECURSIVE (with no need for a stored procedure), to see if results are the same (but be sure to check the "Update from 2017" section first). Debugging the stored procedure itself (if it has a bug) would require access to a reduced, public testcase with data.

    RépondreSupprimer
    Réponses
    1. Oh man, just tried WITH RECURSIVE on my local laptop and it works well and VERY FAST! ;))

      WITH RECURSIVE
      EMPLOYEES_EXTENDED
      AS
      (
      SELECT managerid, NAME, parentid
      FROM bolt_accounts
      where datechanged between date_format(now(),'%Y-%m-%d 00:00:00') and date_format(now(),'%Y-%m-%d 23:59:59')
      UNION ALL
      SELECT E.managerid, E.NAME, M.parentid
      FROM bolt_accounts M JOIN EMPLOYEES_EXTENDED E ON M.managerid=E.parentid
      ),
      REPORTS_COUNT (managerid, REPORTS)
      AS
      ( SELECT parentid, COUNT(*) FROM EMPLOYEES_EXTENDED GROUP BY parentid )
      SELECT BA.managerid, BA.name, BA.parentid, REPORTS FROM bolt_accounts BA JOIN REPORTS_COUNT
      ON BA.managerid = REPORTS_COUNT.managerid

      right now it returns only 198 managerids
      but all numbers - correct!

      So 1st question: how can I force it to run on mysql 5.6 ver and return proper values?
      2nd - why WITH RECURSIVE returned only 198 managerid's, it should return 913

      Supprimer
    2. 2nd question - done, 198 managerids who has REPORTERS >= 1

      Supprimer
  21. Regarding the 1st question, alas without any public test data to reproduce the problem, it's next to impossible to tell what's going wrong.

    RépondreSupprimer
    Réponses
    1. I will msg you via email, thank you.

      Supprimer
    2. Just to post a public update: the simplest solution that we found to Albert's problem, is to take the example of WITH RECURSIVE in the post, and make an equivalent with WITH_EMULATOR; that works and does the job in MySQL 5.x. Updated the post to mention this.

      Supprimer
  22. Ce commentaire a été supprimé par un administrateur du blog.

    RépondreSupprimer

Enregistrer un commentaire

Posts les plus consultés de ce blog

Faster subqueries with materialization