Re: Index on parent/child hierarchy

Hey,

2012/1/25 Merlin Moncure <mmoncure(at)gmail(dot)com>

> On Wed, Jan 25, 2012 at 5:54 AM, Jason Armstrong <ja(at)riverdrums(dot)com>
> wrote:
> > Hi
> >
> > I'm looking for advice on the best way to index a table that is defined
> as:
> >
> > create table uuid.master(id uuid, parent uuid references
> > uuid.master(id), type_id smallint, primary key(id));
> >
> > Besides the primary key, I have these two indices on the table too:
> > CREATE INDEX master_parent_idx ON uuid.master(parent);
> > CREATE INDEX master_type_idx ON uuid.master(type_id);
> >
> > I have data arranged in four levels (ie type_id is from 1 to 4):
> >
> > 1. id=A type_id=1
> > 2. id=B parent=A type_id=2
> > 3. id=C parent=B type_id=3
> > 4. id=D parent=C type_id=4
> > 2. id=E parent=A type_id=2
> > 3. id=F parent=E type_id=3
> > 4. id=G parent=F type_id=4
> > 4. id=H parent=F type_id=4
> > 4. id=I parent=F type_id=4
> > 3. id=J parent=E type_id=3
> > 4. id=K parent=J type_id=4
> >
> > I want to count all type_id=4 for a particular type_id=1 uuid.
> >
> > I use this query:
> >
> > SELECT count(t4.id)
> > FROM uuid.master AS t4
> > INNER JOIN uuid.master AS t3 ON t4.parent=t3.id
> > INNER JOIN uuid.master AS t2 ON t3.parent=t2.id
> > INNER JOIN uuid.master AS t1 ON t2.parent=t1.id
> > WHERE t1.id=UUID
> >
> > Apart from creating a separate table to keep track of the counts, is
> > there a good way to index the table to help?
>
> If your data is organized as a tree, tends to run deep (causing many
> recursion joins), and you often make sweeping subset operations
> starting from a parent node, and your data isn't too heavily updated,
> you might want to consider materialized path organization instead of
> parent/child. Both arrays and strings work for that.
>
> id=I parents=A,E,F type_id=4
>
> SELECT count(*) FROM uuid.master WHERE parents LIKE 'A,E%' and type_id = 4;
>
> The point here is that you can exploit the tree structure with a btree
> index. Before we got recursive queries, this was often the best way
> to do it, but now it's kind of a niche solution to be used when
> certain things fall into place.
>
> merlin
>
Another approarch is to use ltree. It's easy and robust.
http://www.postgresql.org/docs/9.1/static/ltree.html

--
// Dmitriy.