pg.ddx.io  pgsql-sql@postgresql.org mailing list archive  
help / color / mirror / Atom feed
Tree structure index usage
2+ messages / 2 participants
[nested] [flat]

* Tree structure index usage
@ 2001-12-29 20:06 Aasmund Midttun Godal <postgresql@envisity.com>
  2002-01-02 19:38 ` Re: Tree structure index usage Josh Berkus <josh@agliodbs.com>
  0 siblings, 1 reply; 2+ messages in thread

From: Aasmund Midttun Godal @ 2001-12-29 20:06 UTC (permalink / raw)
  To: pgsql-sql

I have a tree structure like:

CREATE TABLE my_tree (
	id SERIAL PRIMARY KEY,
	dir INTEGER references my_tree ON DELETE CASCADE ON UPDATE CASCADE,
	name TEXT,
	UNIQUE(name, dir)
);

Then I have a function is_parent(integer, integer), it will tell you if the second integer (id) is a sub directory of the first (regardless of the number of levels).

now obviously is_parent  does some queries itself.

and someone may choose to update the dir value of a row.

is there any way I can create an efficient index on this structure/function?

The only way I have come up with, is to create an auxilliary table which basically looks like this:

CREATE TABLE my_tree_is_parent (
	is_parent boolean,
	dir INTEGER REFERENCES my_tree,
	id INTEGER,
	PRIMARY KEY (dir, id)
);

and the appropriate triggers to populate and update the table according to modifications in my_tree, however, albeit giving some performance increase (in some cases), it complicates the queries a lot and makes the whole system a lot less userfriendly.

any ideas?

Regards,

Aasmund Midttun Godal

aasmund@godal.com - http://www.godal.com/
+47 40 45 20 46



^ permalink  raw  reply  [nested|flat] 2+ messages in thread

* Re: Tree structure index usage
  2001-12-29 20:06 Tree structure index usage Aasmund Midttun Godal <postgresql@envisity.com>
@ 2002-01-02 19:38 ` Josh Berkus <josh@agliodbs.com>
  0 siblings, 0 replies; 2+ messages in thread

From: Josh Berkus @ 2002-01-02 19:38 UTC (permalink / raw)
  To: Aasmund Midttun Godal <postgresql@envisity.com>; pgsql-sql

Aasmund,

> CREATE TABLE my_tree (
>  id SERIAL PRIMARY KEY,
>  dir INTEGER references my_tree ON DELETE CASCADE ON UPDATE CASCADE,
>  name TEXT,
>  UNIQUE(name, dir)
> );
> 
> Then I have a function is_parent(integer, integer), it will tell you
> if the second integer (id) is a sub directory of the first
> (regardless of the number of levels).
> 
> now obviously is_parent  does some queries itself.
> 
> and someone may choose to update the dir value of a row.
> 
> is there any way I can create an efficient index on this
> structure/function?

Hmmm.  Seperate indexes on ID and DIR should be sufficient for most
purposes.  More complex approaches are only likely to slow things down.
How many records do you have?  How many levels to the tree structure?

For an excellent discussion of efficient construction and queryin of
tree structures, see Joe Celko's "SQL for Smarties."

-Josh

______AGLIO DATABASE SOLUTIONS___________________________
                                       Josh Berkus
  Complete information technology      josh@agliodbs.com
   and data management solutions       (415) 565-7293
  for law firms, small businesses        fax 621-2533
    and non-profit organizations.      San Francisco



^ permalink  raw  reply  [nested|flat] 2+ messages in thread


end of thread, other threads:[~2002-01-02 19:38 UTC | newest]

Thread overview: 2+ messages (download: mbox mbox.gz follow: Atom feed)
-- links below jump to the message on this page --
2001-12-29 20:06 Tree structure index usage Aasmund Midttun Godal <postgresql@envisity.com>
2002-01-02 19:38 ` Josh Berkus <josh@agliodbs.com>

This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox