Support for WITH RECURSIVE queries

[bendlas]

Recursive queries are a feature of standard SQL that allows iteration.

Consider a table storing a tree.

CREATE TABLE nodes (
  node_id serial NOT NULL PRIMARY KEY,
  type character(16),
  parent integer REFERENCES nodes
);

Recursive queries make it possible to traverse the whole tree in one request, like get all folders:

WITH RECURSIVE folders (node_id) AS (
 SELECT 16 -- start node

  UNION -- this may also be UNION ALL

 SELECT sub.node_id -- step relation
    FROM nodes sub JOIN folders ON (sub.parent = folders.node_id)
 WHERE sub.type = 'folder'
) -- the step relation is iteratated and UNIONed onto folders until it yields no more rows
SELECT folder_info.name -- body relation 
   FROM folder_info JOIN folders USING (node_id);

The body relation generates the actual return value of the WITH RECURSIVE query.

Contrary to regular WITH queries, which are just sugar for subselects, WITH RECURSIVE queries can not be emulated (save for PL/SQL procedures and the like)

With that technique one can drastically reduce the number of roundtrips when e.g. doing reports on a graph structure (and using a database that actually supports it, i.e. postgres and oracle, nevermind that it's in the standard).

To properly support it, you would need some construct that establishes a lexical binding for the recursive relation, since the step relation and the body relation may refer to it.

For reference, see http://www.postgresql.org/docs/9.0/static/queries-with.html

A proof of concept implementation: https://gist.github.com/763393