WITH RECURSIVE patches 0818 - Mailing list pgsql-hackers

Hi,

Here is the latest WITH RECURSIVE patches against CVS HEAD. Besides
syncing to CVS HEAD, followings are main differences from previous
one:

1) Enhance sgml docs. Patches contributed by Jeff Davis.

2) Fix bug with plans using HashAggregate. Hash tables should be
   recreated if recursive scan is used. Otherwise goes into infinite
   recursion.

Also I include an implementation doc slightly enhanced previous one.
--
Tatsuo Ishii
SRA OSS, Inc. Japan
1. What is WITH [RECURSIVE] queries?

WITH clause allows to define a table expression being valid within a
same SELECT statement. The table expression is called "Common Table
Expression"(CTE). The use case for CTE is similar to VIEW but it is
more handy than VIEW. Unlike VIEW you do not need to define a VIEW
beforehand.

CTE allows to use recursive quries. To use a recursive query, you need
to add RECURSIVE keyword. Here is an example for WITH RECURSIVE clause
usage. Table "department" represents the structure of an organization.

CREATE TABLE department (
    id INTEGER PRIMARY KEY,  -- department ID
    parent_department INTEGER REFERENCES department, -- upper department ID
    name TEXT -- department name
);

INSERT INTO department VALUES (0, NULL, 'ROOT');
INSERT INTO department VALUES (1, 0, 'A');
INSERT INTO department VALUES (2, 1, 'B');
INSERT INTO department VALUES (3, 2, 'C');
INSERT INTO department VALUES (4, 2, 'D');
INSERT INTO department VALUES (5, 0, 'E');
INSERT INTO department VALUES (6, 4, 'F');
INSERT INTO department VALUES (7, 5, 'G');

-- department structure represented here is as follows:
--
-- ROOT-+->A-+->B-+->C
--      |         |
--      |         +->D-+->F
--      +->E-+->G

To extract all departments under A, following recursive query can be
used:

WITH RECURSIVE subdepartment AS
(
    -- non recursive term
    SELECT * FROM department WHERE name = 'A'

    UNION ALL

    -- recursive term
    SELECT d.* FROM department AS d, subdepartment AS sd
        WHERE d.parent_department = sd.id
)
SELECT * FROM subdepartment ORDER BY name;

The meaning of the query above can be explained as follows.

Let IT be an intermediate table. Let WT be a work table. Let RT be a
result table.

1) initialize

Execute non recursive term (SELECT * FROM department WHERE name = 'A')
and assign the result to RT and WT.

RT = WT = ('A')

Make IT empty.

IT = ()

2) execute recursive query

Replace subdepartment with WT and execute recursive term (SELECT d.*
FROM WT AS d, subdepartment AS sd WHERE d.parent_department =
sd.id) and assign the result to IT.
Add IT to RT. Assign IT to WT. Make IT empty.

3) Check if recursion is ended

If IT is empty in 2), execution of recursion is ended. Return RT.

Otherwise go to 2).

"subdepartment" is a CTE including a recursive expression since it
referes itself within its definition. In the above query first non
recursive term is evaluted. Then recursive term is evaluated and the
result is added to the prevoius result set over and over until there's
no more data to process. Finally the last SELECT is excuted and data
is extracted from the result set.

2. Implementation details

- Parsing recursive queries

To represent CTE, new structure member "withClause" is added to
SelectStmt structure which is used to store parsed information of a
SELECT stament. The definition of withClause is as follows:

/*
 * WithClause -
 *     reprensentation of WITH clause
 */
typedef struct WithClause
{
    NodeTag        type;            /* T_WithClause */
    List        *subquery;        /* subquery list (list of RangeSubselect) */
    bool        recursive;        /* true = WITH RECURSIVE */
} WithClause;

If RECURSIVE key word is not given, CTE is just converted to a
WithClause.subquery and WithClause.recursive is set to false.

If RECURSIVE key word is given, the raw parse tree stored in
WithClause.subquery represents a subquery which is an UNION ALL of a
non recursive term and a recursive term (set operation other than
UNION ALL between a non recursive term and a recursive term is not
allowed).  WithClause.subquery.subquery.larg represents "SELECT * FROM
department WHERE name = 'A'" and WithClause.subquery.subquery.rarg
represents "SELECT d.* FROM department AS d, subdepartment AS sd WHERE
d.parent_department = sd.id" in the example above.

- Analyzing recursive queries

To analyze CTEs, we add following new members "p_ctenamespace",
"p_recursive_namespace", and "p_in_with_clause" to ParseState structure.

p_ctenamespace is a namespace for non recursive CTEs and a list of
RangeSubselects. Here is an excerption from comments of ParseState:

 * [1] Note that p_ctenamespace is a namespace for "relations" but distinct
 *     from p_relnamespace. p_ctenamespace is a list of relations that can be
 *     referred to in a FROM or JOIN clause (in addition to normal tables and
 *     views). p_relnamespace is the list of relations which already have been
 *     listed in such clauses and therefore can be referred to in qualified
 *     variable references. Also, note that p_ctenamespace is a list of
 *     RangeSubselects, not a list of range table entries.

p_recursive_namespace is a namespace for recursive CTEs and is a list
of RangeRecursive. RangeRecursive is a newly introduced strucure:

/*
 * RangeRecursive - recursive call appearing in a FROM clause
 */
typedef struct RangeRecursive
{
    NodeTag        type;
    Node       *subquery;        /* the untransformed sub-select clause */
    Alias       *alias;            /* table alias & optional column aliases */
    List       *coldeflist;        /* list of ColumnDef nodes to describe result */
    Node        *non_recursive_term;    /* analyze result of non recusive term */
    bool        recursive;        /* true if recursive query */
} RangeRecursive;

ParseState.p_rtable is a list of RangeTblEntry. To process CTEs, new
members "self_reference" and "non_recursive_query" are added to
RangeTblEntry.

    /*
     * Fields valid for a RECURSIVE CTE (else NIL)
     */
    bool        self_reference; /* delay analyzing SelectStmt */
    Query        *non_recursive_query; /* non-recursive term */

If a CTE using "RECURSIVE" keyword is not actually recursive,
"recursive" is set to false and the CTE is treated as a subquery and
added to ParseState.p_rtable.

If the CTE referes to itself, analyzing will be delayed,
self_reference is set to true, and non_recurisve_term are filled.

It is possible that more than one CTE elements (query names) exist.

WITH RECURSIVE x AS (SELECT * from y),
                y AS (SELECT * FROM pg_class)
  SELECT * FROM x;

In this case we should analyze y first since x depends on y. To find
such dependency information, a topological sort is performed.
See makeDependencyGraph() for more details.

Next we check if the recursive query is follow the SQL standard.
Following example queries are not allowed by the standard.

- non-recursive term and recursive term must be combined with UNION ALL
WITH RECURSIVE x(n) AS (SELECT 1 UNION SELECT n+1 FROM x)
    SELECT * FROM x;

WITH RECURSIVE x(n) AS (SELECT 1 INTERSECT SELECT n+1 FROM x)
    SELECT * FROM x;

- non-recursive term does not exist

WITH RECURSIVE x(n) AS (SELECT n FROM x)
    SELECT * FROM x;

-  recursive term must be in the left hand side
WITH RECURSIVE x(n) AS (SELECT n FROM x UNION ALL SELECT 1)
    SELECT * FROM x;

- LEFT JOIN in the right hand side of recursive term not allowed
WITH RECURSIVE x(n) AS (SELECT a FROM y WHERE a = 1
    UNION ALL
    SELECT x.n+1 FROM y LEFT JOIN x ON x.n = y.a WHERE n < 10)
SELECT * FROM x;

- RIGHT JOIN in the left hand side of recursive term not allowed
WITH RECURSIVE x(n) AS (SELECT a FROM y WHERE a = 1
    UNION ALL
    SELECT x.n+1 FROM x RIGHT JOIN y ON x.n = y.a WHERE n < 10)
SELECT * FROM x;

- FULL JOIN in a recursive term not allowed
WITH RECURSIVE x(n) AS (SELECT a FROM y WHERE a = 1
    UNION ALL
    SELECT x.n+1 FROM x FULL JOIN y ON x.n = y.a WHERE n < 10)
SELECT * FROM x;

- WHERE clause having subqury which uses recursive name in a recursive
  term not allowed
WITH RECURSIVE x(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM x
                          WHERE n IN (SELECT * FROM x))
  SELECT * FROM x;

- GROUP BY, HAVING in a recursive term not allowed
WITH RECURSIVE x(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM x GROUP BY n)
  SELECT * FROM x;

-- aggregate functions a recursive term not allowed
WITH RECURSIVE x(n) AS (SELECT 1 UNION ALL SELECT count(*) FROM x)
  SELECT * FROM x;

In addition to above restrictions, we add more restrictions:

- ORDER BY in a recursive query not allowed
WITH RECURSIVE x(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM x ORDER BY 1)
  SELECT * FROM x;

- LIMIT OFFSET in a recursive query not allowed
WITH RECURSIVE x(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM x LIMIT 10 OFFSET 1)
  SELECT * FROM x;

- FOR UPDATE in a recursive query not allowed
WITH RECURSIVE x(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM x FOR UPDATE)
  SELECT * FROM x;

- target list having subquery which uses recursive name in a recursive term not allowed
WITH RECURSIVE x(id) AS (values (1)
    UNION ALL
    SELECT (SELECT * FROM x) FROM x WHERE id < 5
) SELECT * FROM x;

- mutual recursive call is not supported
WITH RECURSIVE
  x (id) AS (SELECT 1 UNION ALL SELECT id+1 FROM y WHERE id < 5),
  y (id) AS (SELECT 1 UNION ALL SELECT id+1 FROM x WHERE id < 5)
SELECT * FROM x;

Note that SQL Server and Firebird do not allow mutual recursive query
either (Oracle does not support WITH RECURSIVE at this point by the way).

Tables defined in WITH RECURSIVE clause are identified as
RTE_RECURSIVE out of RTEKind in the RangeTblEntry in the parse tree
nodes.  A name space "p_recursive_namespace", whose structure type is
RangeRecursive, is added to in ParseState structure.

typedef struct RangeRecursive
{
    NodeTag        type;
    Node       *subquery; /* whole subquery */
    Alias       *alias;            /* table alias & optional column aliases */
    List       *coldeflist;        /* list of ColumnDef nodes */
    Node       *non_recursive_term; /* analyze result of non recursive term */
    bool       recursive; /* true if recursive */
} RangeRecursive;

non_recursive_term keeps the result of analyzing on non recursive
term.  Using this, the type of recursive query is inferenced.


- Rewriter

The changes applied to the rewriter is small. fireRIRrules()
recursively expand subqueries. We just do the same thing if it's a
recurisve query.

- Generating a plan

New plan node "Recursion" and "Recursive scan" are added.  Recusion
plan is the top level plan for execution of WITH RECURSIVE query. In
the example below, Recursion plan represents the execution plan for
"SELECT * FROM subdepartment" part. Recursion plan always has "Append"
subplan which represents the execution plan for "UNION ALL" for non
recursive part and recursive part. Plan for non recursive part is
nothing special and is an ordinary plan generated according to the non
recursive query part. Recursive scan represents the plan for recursive
part.

Below is an example EXPLAIN output.

EXPLAIN WITH RECURSIVE subdepartment AS
(
    -- non recursive term
    SELECT * FROM department WHERE name = 'A'

    UNION ALL

    -- recursive term
    SELECT d.* FROM department AS d, subdepartment AS sd
        WHERE d.parent_department = sd.id
)
SELECT * FROM subdepartment;

                                    QUERY PLAN
-----------------------------------------------------------------------------------
 Recursion on subdepartment  (cost=0.00..50.76 rows=12 width=40)
   ->  Append  (cost=0.00..50.64 rows=12 width=40)
         ->  Seq Scan on department  (cost=0.00..24.50 rows=6 width=40)
               Filter: (name = 'A'::text)
         ->  Hash Join  (cost=0.01..26.02 rows=6 width=40)
               Hash Cond: (d.parent_department = sd.id)
               ->  Seq Scan on department d  (cost=0.00..21.60 rows=1160 width=40)
               ->  Hash  (cost=0.00..0.00 rows=1 width=4)
                     ->  Recursive Scan on sd  (cost=0.00..0.00 rows=1 width=4)

The structure which represents Recursion plan is as follows:

typedef struct Recursion
{
    Scan    scan;
    Plan    *subplan;
    List    *subrtable;        /* temporary workspace for planner */
} Recursion;

The structure which represents RecursiveScan plan is as follows:

typedef struct RecursiveScan
{
    Scan        scan;
} RecursiveScan;


- Executor

To execute plans for CTEs, we add new members "es_tuplestorestate",
"es_rscan_tupledesc" and "es_disallow_tuplestore". es_tuplestorestate
is used to remember TupleStoreState of the working
table(WT). es_rscan_tupledesc is used to remeber the type information
of the tuples returned by the CTEs. es_disallow_tuplestore is not
actually used.

To manage recursive query execution state following structures are added.

typedef struct RecursionState
{
    ScanState    ss;
    PlanState  *subplan;        /* plan for non recursive query */
    bool recursive_empty; /* if recursive term does exist, true */
    Tuplestorestate *intermediate_tuplestorestate; /* intermediate table (IT) */
    Tuplestorestate *working_table;        /* working table (WT) */
    bool init_done; /* initialization flag */
} RecursionState;

typedef struct RecursiveScanState
{
    ScanState    ss;
    TupleDesc    tupdesc;
    Tuplestorestate **working_table;    /* working table */
} RecursiveScanState;

- Initializing Recursion Plan

This is done by ExecInitRecursion(). The working table (WT) is created
and its pointer is stored in RecusionState.working_table. The
imtermidiate table (IT) is created and its pointer is stored in
RecusionState.intermediate_tuplestorestate.

While the initialization WT created above must be used and pointer to
WT is stored in es_tuplestorestate in the master executor state
(Estate).

Type info for scan is taken from the non recursive query (saved in
RecursionState.subquery) and stored in RecursionState.ss and
Estate/es_rscan_tupledesc.

- Executing Recursion Plan

Recursion Plan is executed by ExecRecursion(). The work horse is
RecursionNext(). First it execute a plan for non recursive term and
the result is stored in WT. Then execute a plan for recursive term,
which is a subplan of the recursion plan. If the plan returns one or
more rows, they are store in IT. IT and WT are swapped and recreate
IT. If no row is returned, the recursion is ended and ExecRecursion()
returns NULL.

- Initializing RecursiveScan plan

This is very much same as the initialization of RecursionScan execpt
that type info for scan is taken from Estate.es_rscan_tupledesc which
is initialized by ExecInitRecursion().

- Executing RecursiveScan plan

Recursive scan is executed by ExecRecursiveScan(). The work horse is
RecursivescanNext().  It just eturns tuples store in WT. Work table is
stored in Estate structure.

- Miscellaneous changes in Executor

1) Hash join plan does not always recreate hash until hash join
   ended. If hash join has Recurisve Scan as its subplan, the hash
   needs to recreate. To solve the problem, "has_recursivescan" is
   added to PlanState structure, which is true if upper plan has
   RecursiveScan as a subplan and hash is recreated.

2) exec_append_initialize_next() is executed while processing
   recurision. The function is now a global one.

3. Limitations

1) SEARCH and CYCLE clauses are not implemented

2) Mutual recursion is not allowed

3) Only the last SELECT of UNION ALL can include self recursion name.

4) Cost of Recursion and Recursivescan plan are always 0.