RFP: Recursive query in 8.4

Hi,

As I promised before we would like to propose implementing the
recursive query as defined in the standard for PostgreSQL 8.4.

The work is supported by Sumitomo Electric Information Systems Co.,
Ltd. (http://www.sei-info.co.jp/) and SRA OSS, Inc. Japan
(http://www.sraoss.co.jp).

1. Overview

We propose to implement the recursive query (WITH RECURSIVE clause)
defined in SQL:1999 and later. With the recursive query, one can
easily inquire the data expressed as tree and graph structures. The
actual syntax we prefer is the one defined in SQL:2008 (it's not
published yet, but I have a closest draft).

We do not propose the WITH clause without RECURSIVE key word here
since someone else has already made a proposal for this.
(http://archives.postgresql.org/pgsql-patches/2008-01/msg00105.php)

2. Example

For those who are not familiar with the recursive query, I include an
example:

CREATE TABLE department (
id INT PRIMARY KEY,
parent_department INT REFERENCES department,
name TEXT
);

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, 4, 'G');

This will represent a tree structure of an organization:

ROOT ---> A ---> B ---> C ---> F
| |
| +----> D
|
+-----> E ---> G

If you want to extract all departments "under" A, you could use a
recursive query:

WITH RECURSIVE subdepartment AS
(
--
SELECT * FROM department WHERE id = 'A'

UNION ALL

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

This will return A, B, C, D and F.

2. The syntax

As described above, we refers to the SQL:2008's WITH RECURSIVE clause syntax.

WITH RECURSIVE clause ::=

WITH RECURSIVE <query name> AS ( <table subquery> )
[ SEARCH clause | CYCLE clause ]
<SELECT body>

In the example above, <query name> is "subdepartment" and <table
subquery> is SELECTs in pareses.

<table subquery> must have one or more "anchor" expressions. This is
required by the standard.

The anchor expressions are consisted with "none recursive term"
(SELECT * FROM department WHERE id = 'A') + UNION ALL + "recursive
term" (SELECT d.* FROM department AS d, subdepartment AS sd WHERE d.id
= sd.parent_department). <SELECT body> is "SELECT * FROM subdepartment".

Note that the standard allows to use an UNION without ALL. However
this proposal only allow UNION ALL due to an implementation reason.

Other limitations required by the standard include:

- aggregate functions are not allowed in the recursive term

- GROUP BY is not allowed in the recursive term

- outer joins are not allowed in the recursive term

3. Processing a recursive query

If a WITH clause includes a recursive referencing cycle, we call the
set of <with list elements> as "partition". In the example above,
there is a partition in which subdepartment referees to itself. We
limit number of list elements in a partition up to 1, which means it
should be a self reference.

While processing a recursive query, we start with a partition which
does not depend on any other partitions.

There is a working table WT and an intermediate table RT to evaluate a
partition. We implement WT and RT using tuplestore.

The algorithm is shown below.

[using the width first search]

1. evaluate non recursive term or partition depending on other
partitions and assign the result to RT

2. execute recursive terms

2.1 WT := RT
2.2 while WT is not empty repeat 2.3 to 2.6. if WT is empty returns RT
2.3 replace the name of recursive term with WT
2.4 evaluate the recursive term and store into WT
2.5 append WT to RT
2.6 go back to 2.2

Pseudo code shown below.

1. RT := none recursive query result
2. for i = 1..N (N = number of partitions)
2.1 WT := RT
2.2 while !empty(WT); do
2.3 subdepartment := WT
2.4 WT := result of recursive term
2.5 RT := WT UNION ALL RT
2.6 done

Execution trace shown below.

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

UNION ALL

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

1)
RT = {'A'} WT = {'A'}

2)
SELECT d.* FROM department AS d, WT({'A'}) AS sd
WHERE d.id = sd.parent_id

WT = {'B'}

RT = RT({'A'}) UNION ALL(*) WT({'B'})
=> RT = {'A', 'B'}

3)
SELECT d.* FROM department AS d, WT({'B', 'C'}) AS sd
WHERE d.id = sd.parent_id

=> WT = {'C', 'D'}

RT = RT({'A', 'B'}) UNION ALL WT({'C', 'D'})
=> RT = {'A', 'B', 'C', 'D'}

4)
SELECT d.* FROM department AS d, WT({'B', 'C'}) AS sd
WHERE d.id = sd.parent_id

=> WT = {'F'}

RT = RT({'A', 'B', 'C', 'D'}) UNION ALL WT({'F'})
=> RT = {'A', 'B', 'C', 'D', 'F'}

5)
SELECT d.* FROM department AS d, WT({'B', 'C'}) AS sd
WHERE d.id = sd.parent_id

=> WT = {}

RT = RT({'A', 'B', 'C', 'D', 'F'}) UNION ALL WT({}) <--(1)
=> RT = {'A', 'B', 'C', 'D', 'F'}

6)
Since WT is empty, the execution stops. RT = {'A', 'B', 'C', 'D', F'} (the result)

(1) Actually we do not execute UNION ALL. We use tuplestore_puttuple()
to add results to RT.

4. About GUC parameters

We do not add new GUC parameters.

5. Limitation with PostgreSQL

1) we do not implement SEARCH clause and CYCLE clause. This is because
we need array of rows to implement them. Note that there's no
support for array of rows in PostgreSQL.

2) we only allow UNION ALL while appending none recursive term and
recursive terms. This is because it's difficult to remove
duplications using tuplestore. Note that Firebird and MS SQL support
only UNION as well.

[1] http://www.firebirdsql.org/rlsnotesh/rlsnotes210.html#rnfb210-cte
[2] http://msdn2.microsoft.com/en-us/library/ms186243.aspx

3) no support for mutually recursive queries

In the parser we throw an error if there's a mutually recursive query.

rec1 -> rec2 -> rec1 -> ...

Note that Firebird and MS SQL do not support mutually recursive
queries either.

6. Problems

1) while processing recursive queries, we repeat JOIN operations many
times. JOIN methods can be nested loop, merge join, or hash join.
Depending on the number of rows and etc., the optimal join method
may vary. However we have no way to change the join method
dynamically according to increasing the number of rows.

2) it's not clear for the planner how to estimate the cost of
recursive queries.
--
Tatsuo Ishii
SRA OSS, Inc. Japan

Tatsuo Ishii <ishii(at)postgresql(dot)org> wrote:

> 5. Limitation with PostgreSQL
>
> 1) we do not implement SEARCH clause and CYCLE clause. This is because
> we need array of rows to implement them. Note that there's no
> support for array of rows in PostgreSQL.

What is difference between "array of rows" and
Arrays of composite types, that is new feature in 8.3 ?

=# CREATE TABLE foo (i integer);
CREATE TABLE
=# CREATE TABLE bar (foos foo[]); -- *here*
CREATE TABLE

Regards,
---
ITAGAKI Takahiro
NTT Open Source Software Center

> Tatsuo Ishii <ishii(at)postgresql(dot)org> wrote:
>
> > 5. Limitation with PostgreSQL
> >
> > 1) we do not implement SEARCH clause and CYCLE clause. This is because
> > we need array of rows to implement them. Note that there's no
> > support for array of rows in PostgreSQL.
>
> What is difference between "array of rows" and
> Arrays of composite types, that is new feature in 8.3 ?
>
> =# CREATE TABLE foo (i integer);
> CREATE TABLE
> =# CREATE TABLE bar (foos foo[]); -- *here*
> CREATE TABLE

Will check. Thanks for pointing it out.
--
Tatsuo Ishii
SRA OSS, Inc. Japan

On Tue, Feb 19, 2008 at 3:36 AM, Tatsuo Ishii <ishii(at)postgresql(dot)org> wrote:
> We propose to implement the recursive query (WITH RECURSIVE clause)
> defined in SQL:1999 and later. With the recursive query, one can
> easily inquire the data expressed as tree and graph structures. The
> actual syntax we prefer is the one defined in SQL:2008 (it's not
> published yet, but I have a closest draft).

I am sure you are aware of various ad hoc approaches that are
currently possible. The recursive clause seems to generalize these
approaches.

Do you expect that your proposed solution will have performance
advantages over solutions like using recursive functions and (for tree
organized data) arrays?

merlin

> On Tue, Feb 19, 2008 at 3:36 AM, Tatsuo Ishii <ishii(at)postgresql(dot)org> wrote:
> > We propose to implement the recursive query (WITH RECURSIVE clause)
> > defined in SQL:1999 and later. With the recursive query, one can
> > easily inquire the data expressed as tree and graph structures. The
> > actual syntax we prefer is the one defined in SQL:2008 (it's not
> > published yet, but I have a closest draft).
>
> I am sure you are aware of various ad hoc approaches that are
> currently possible. The recursive clause seems to generalize these
> approaches.
>
> Do you expect that your proposed solution will have performance
> advantages over solutions like using recursive functions and (for tree
> organized data) arrays?

I hope so. But the first thing I would like to do is, to implement the
right thing (i.e. following the standard).

I don't see any reason that the proposal gets less performance than
existing functions. Moreover the proposal could better cooperate with
the optimizer since it can feed more info to it. Any ideas to enhance
the performance are welcome.
--
Tatsuo Ishii
SRA OSS, Inc. Japan

Tatsuo Ishii wrote:
>> On Tue, Feb 19, 2008 at 3:36 AM, Tatsuo Ishii <ishii(at)postgresql(dot)org> wrote:
>>
> I hope so. But the first thing I would like to do is, to implement the
> right thing (i.e. following the standard).
>
> I don't see any reason that the proposal gets less performance than
> existing functions. Moreover the proposal could better cooperate with
> the optimizer since it can feed more info to it. Any ideas to enhance
> the performance are welcome.
>

I agree about following the standard but I think it's true that the
standard creates some challenges for the optimizer.

The standard recursive query syntax is quite general. It can represent
arbitrary non-linear recursive queries including possibly mutually
recursive queries, for example. The challenge is that there are no extra
hints when you have the more usual case of a simple linear recursion.

You really do want to discover such linear recursive structures because
you can use simpler algorithms and recover memory sooner if you know you
have a linear recursive query. You can also support the SEARCH and CYCLE
clauses to do depth-first searches which you can't do for arbitrary
recursive queries. I also don't have much hope for good optimizer
estimates for general recursive queries but for linear recursive queries
we can probably do better.

But I think it's actually easier to implement the general case than the
special nodes to handle the linear case more efficiently. To handle the
general case we need the memoize node to handle recursive loops in the
plan and then we can use otherwise normal plan nodes.

My plan was to implement the general case first, then look for ways to
add intelligence in the planner to discover linearity and add new paths
to take advantage of it.

> Tatsuo Ishii wrote:
> >> On Tue, Feb 19, 2008 at 3:36 AM, Tatsuo Ishii <ishii(at)postgresql(dot)org> wrote:
> >>
> > I hope so. But the first thing I would like to do is, to implement the
> > right thing (i.e. following the standard).
> >
> > I don't see any reason that the proposal gets less performance than
> > existing functions. Moreover the proposal could better cooperate with
> > the optimizer since it can feed more info to it. Any ideas to enhance
> > the performance are welcome.
> >
>
> I agree about following the standard but I think it's true that the
> standard creates some challenges for the optimizer.
>
> The standard recursive query syntax is quite general. It can represent
> arbitrary non-linear recursive queries including possibly mutually
> recursive queries, for example. The challenge is that there are no extra
> hints when you have the more usual case of a simple linear recursion.

I seems the standard does not allow non-linear recursive queries. In
the SQL:2008 draft pp.380:

7.13 <query expression>

Syntax Rules 2) g) iv)

"If WLE_i is recursive, then WLE_i shall be linearly recursive."

So now the problem is, how to detect the non-linear recursive queries
and reject them.

> You really do want to discover such linear recursive structures because
> you can use simpler algorithms and recover memory sooner if you know you
> have a linear recursive query. You can also support the SEARCH and CYCLE
> clauses to do depth-first searches which you can't do for arbitrary
> recursive queries. I also don't have much hope for good optimizer
> estimates for general recursive queries but for linear recursive queries
> we can probably do better.
>
> But I think it's actually easier to implement the general case than the
> special nodes to handle the linear case more efficiently. To handle the
> general case we need the memoize node to handle recursive loops in the
> plan and then we can use otherwise normal plan nodes.
>
> My plan was to implement the general case first, then look for ways to
> add intelligence in the planner to discover linearity and add new paths
> to take advantage of it.
>

> > Tatsuo Ishii <ishii(at)postgresql(dot)org> wrote:
> >
> > > 5. Limitation with PostgreSQL
> > >
> > > 1) we do not implement SEARCH clause and CYCLE clause. This is because
> > > we need array of rows to implement them. Note that there's no
> > > support for array of rows in PostgreSQL.
> >
> > What is difference between "array of rows" and
> > Arrays of composite types, that is new feature in 8.3 ?
> >
> > =# CREATE TABLE foo (i integer);
> > CREATE TABLE
> > =# CREATE TABLE bar (foos foo[]); -- *here*
> > CREATE TABLE
>
> Will check. Thanks for pointing it out.

Yes, I agree with that the 8.3's new feature might be used to
implement SEARCH clause and CYCLE clause. Problem is, it requres that
the named composite type (the standard's term is "row type") is
previously defined. Maybe we need "anonymous" row type?
--
Tatsuo Ishii
SRA OSS, Inc. Japan