[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, "" );