EXPLAIN EXTENDED

How to create fast database queries

Archive for December 24th, 2010

PostgreSQL: parametrizing a recursive CTE

with 2 comments

Answering questions asked on the site.

Jan Suchal asks:

We've started playing with PostgreSQL and recursive queries. Looking at example that does basic graph traversal from http://www.postgresql.org/docs/9.0/static/queries-with.html.

We would like to have a view called paths defined like this:

WITH RECURSIVE
        search_graph(id, path) AS
        (
        SELECT  id, ARRAY[id]
        FROM    node
        UNION ALL
        SELECT  g.dest, sg.path || g.dest
        FROM    search_graph sg
        JOIN    graph g
        ON      g.source = sg.id
                AND NOT g.dest = ANY(sg.path)
        )
SELECT  path
FROM    search_graph

By calling

SELECT  *
FROM    paths
WHERE   path[1] = :node_id

we would get all paths from a certain node.

The problem here is with performance. When you want this to be quick you need to add a condition for the anchor part of the UNION like this:

WITH RECURSIVE
        search_graph(id, path) AS
        (
        SELECT  id, ARRAY[id]
        FROM    node
        WHERE   id = :node_id
        UNION ALL
        SELECT  g.dest, sg.path || g.dest
        FROM    search_graph sg
        JOIN    graph g
        ON      g.source = sg.id
                AND NOT g.dest = ANY(sg.path)
        )
SELECT  path
FROM    search_graph

Now it's perfectly fast, but we cannot create a view because that would only contain paths from one specific node.

Any ideas?

An often overlooked feature of PostgreSQL is its ability to create set-returning functions and use them in SELECT list.

The record will be cross-joined with the set returned by the function and the result of the join will be added to the resultset.

This is best demonstrated with generate_series, probably a most used PostgreSQL set-returning function.
Read the rest of this entry »

Written by Quassnoi

December 24th, 2010 at 11:00 pm

Posted in PostgreSQL