Row-wise IN BETWEEN comparison in a single SQL statement

Question

Given the following tables:

CREATE TABLE tree (
    id serial NOT NULL,
    name character varying NOT NULL,
    type integer,
    lft integer NOT NULL,
    rgt integer NOT NULL )

CREATE TABLE item (
    id serial NOT NULL,
    name character varying NOT NULL,
    tree_id integer
    CONSTRAINT fk_tree FOREIGN KEY (tree_id) REFERENCES tree (id) )

Columns lft and rgt on table tree are populated using the modified preorder tree traversal (MPTT) algorithm.

Is it possible to get all items attached to tree nodes with type=x and all their descendants all in a single query?

Normally, I'd do it in two separate queries like this:

SELECT lft, rgt FROM tree WHERE type = x;
/* assume it returns two rows: ((10, 20), (27, 30)) */

SELECT item.id, item.name FROM item JOIN tree ON (tree_id = tree.id)
WHERE ((lft >= 10 AND rgt <= 20) OR (lft >= 27 AND rgt <= 30);

The point is that I can only execute a single SQL statement (in a PostgreSQL Database, if it matters). Can you do this with some sort of subquery?

Thanks for any hints.

Answer 1

SELECT  item.*
FROM    tree tm
JOIN    tree tc
ON      tc.lft >= tm.lft
        AND tc.rgt <= tm.rgt
JOIN    item
ON      item.tree_id = tc.id
WHERE   tm.type = x

You may want to consider the parent-child model that is much easier to manage.

See these articles in my blog on how to implement it in PostgreSQL 8.3 and below:

• Hierarchical queries in PostgreSQL

, and in PostgreSQL 8.4:

• PostgreSQL 8.4: preserving order for hierarchical query

Answer 2

Well, if you have problems with writing queries to given data structure, perhaps you should consider using some other data structure? Nested sets (what you showed in here) look cool, but are a major pain when writing queries to them.

Perhaps you could use something like this (disclosure: it's a post on my blog).