Index on parent/child hierarchy

On Wed, Jan 25, 2012 at 11:54 AM, Jason Armstrong <ja@riverdrums.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?

Something like this...

WITH RECURSIVE subtree(depth, id, parent, type_id) AS (
SELECT 0, id, parent, type_id FROM uuid.master WHERE id = X
UNION
SELECT depth+1, m.id, m.parent, m.type_id
FROM subtree t, uuid.master m
WHERE m.parent = t.id
)
SELECT count(*)
FROM subtree
WHERE type_id = 4;

Add an index on id

--
 Simon Riggs                   http://www.2ndQuadrant.com/
 PostgreSQL Development, 24x7 Support, Training & Services

On Wed, Jan 25, 2012 at 5:54 AM, Jason Armstrong <ja@riverdrums.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

Hey,

2012/1/25 Merlin Moncure <mmoncure@gmail.com>

On Wed, Jan 25, 2012 at 5:54 AM, Jason Armstrong <ja@riverdrums.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.

On Sun, Jan 29, 2012 at 5:55 AM, Dmitriy Igrishin <dmitigr@gmail.com> wrote:

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

yeah -- good point.

merlin