Horton

Thread

  1. new module contrib/tree for 7.2 ?

    Oleg Bartunov <oleg@sai.msu.su> — 2002-01-25T14:08:38Z

    Hi,

Is't late to submit new contrib module for 7.2 ?
It's almost ready and tested, we have to write README.tree.

New module creates new data types 'tree', 'treequery' for tree-like data and
provides indexed access methods using Btree or GiST.
Node represents as a path to the root, so record like '3.4' means
4-th child of 3-rd child of the root node.
Due-to bit-representation there is a limitation to the number of
children - 64 and defined in compile time (valid values - 8,16,32,64).
For practical purposes 64 children looks quite enough.
insert,delete operations should be ok, while move operations
is a pain - one should update all paths of children nodes.
But search is very fast, we use data from Open Directory catalog (www.dmoz.org)
for testing:

Select all countries:

dmoz64=# explain analyze select * from dmoz where tid <* '18.*.0';
NOTICE:  QUERY PLAN:

Index Scan using tid_g_idx on dmoz  (cost=0.00..1094.10 rows=277 width=100) (actual time=3.54..23.76 rows=56 loops=1)
Total runtime: 23.96 msec

EXPLAIN
dmoz64=#

       name         |             strid             |   id   |  tid
---------------------+-------------------------------+--------+-------
 Tagalog             | Top/World/Tagalog             | 276537 | 18.18
 Taiwanese           | Top/World/Taiwanese           | 276566 | 18.19
 Tamil               | Top/World/Tamil               | 276567 | 18.20
 Telugu              | Top/World/Telugu              | 276568 | 18.21
 Thai                | Top/World/Thai                | 276601 | 18.22
 Ukrainian           | Top/World/Ukrainian           | 276602 | 18.23
 Vietnamese          | Top/World/Vietnamese          | 276603 | 18.24
 Japanese            | Top/World/Japanese            | 268629 | 18.31
 Kiswahili           | Top/World/Kiswahili           | 268630 | 18.32
 Afrikaans           | Top/World/Afrikaans           | 256813 | 18.1
 Italiano            | Top/World/Italiano            | 266163 | 18.30
 Interlingua         | Top/World/Interlingua         | 266144 | 18.29
 Indonesia           | Top/World/Indonesia           | 265859 | 18.28
 Croatian            | Top/World/Croatian            | 257063 | 18.12
....................................................................



	Regards,
		Oleg
_____________________________________________________________
Oleg Bartunov, sci.researcher, hostmaster of AstroNet,
Sternberg Astronomical Institute, Moscow University (Russia)
Internet: oleg@sai.msu.su, http://www.sai.msu.su/~megera/
phone: +007(095)939-16-83, +007(095)939-23-83

  2. Re: new module contrib/tree for 7.2 ?

    Tom Lane <tgl@sss.pgh.pa.us> — 2002-01-25T15:26:07Z

    Oleg Bartunov <oleg@sai.msu.su> writes:
> Is't late to submit new contrib module for 7.2 ?

Sorry, too late.  I've been lax on a lot of other questions, but large
chunks of new code are *not* going in at this point, contrib or no.
Save it for 7.3.

			regards, tom lane

  3. Re: new module contrib/tree for 7.2 ?

    Hannu Krosing <hannu@tm.ee> — 2002-01-25T16:03:27Z

    Oleg Bartunov wrote:
> 
> Hi,
> 
> Is't late to submit new contrib module for 7.2 ?
> It's almost ready and tested, we have to write README.tree.
> 
> New module creates new data types 'tree', 'treequery' for tree-like data and
> provides indexed access methods using Btree or GiST.
> Node represents as a path to the root, so record like '3.4' means
> 4-th child of 3-rd child of the root node.
> Due-to bit-representation there is a limitation to the number of
> children - 64 and defined in compile time (valid values - 8,16,32,64).

How hard it would be to automatically expand it so that 65th node will 
make it flow over to next bitfield and the whole level will then 
accommodate 64*64 = 4096 child nodes ?

> For practical purposes 64 children looks quite enough.
> insert,delete operations should be ok, while move operations
> is a pain - one should update all paths of children nodes.
> But search is very fast, we use data from Open Directory catalog (www.dmoz.org)
> for testing:

Could you send it to me for personal testing if it is not accepted to
contrib for 7.2 ?

-------------
Hannu

  4. Re: new module contrib/tree for 7.2 ?

    Don Baccus <dhogaza@pacifier.com> — 2002-01-25T16:55:02Z

    Hannu Krosing wrote:

> Oleg Bartunov wrote:
> 
>>Hi,
>>
>>Is't late to submit new contrib module for 7.2 ?
>>It's almost ready and tested, we have to write README.tree.
>>
>>New module creates new data types 'tree', 'treequery' for tree-like data and
>>provides indexed access methods using Btree or GiST.
>>Node represents as a path to the root, so record like '3.4' means
>>4-th child of 3-rd child of the root node.
>>Due-to bit-representation there is a limitation to the number of
>>children - 64 and defined in compile time (valid values - 8,16,32,64).
>>
> 
> How hard it would be to automatically expand it so that 65th node will 
> make it flow over to next bitfield and the whole level will then 
> accommodate 64*64 = 4096 child nodes ?


Hmmm...the OpenACS 4 tree implementation uses BIT VARYING for the key. 
The first 128 immediate children of a node have a one-byte key (leading 
0 and 7 bits for the key), the next 2 billionish immediate children have 
four-byte keys (leading 1 and 31 bits for the key).  After that you get 
no more immediate children but two billion plus seems sufficient!

Many trees have no nodes with more than 128 immediate children, of 
course, so these always have keys with one byte per level.  Being able 
to handle essentially "infinitely flat" trees without intervention is 
awfully nice, though.

Using "between" and a simple set of functions you can get btree-indexed 
access to all subtrees.  Getting the set of parents for a node is a bit 
more tricky - we use a recursive SQL function to build the set of parent 
keys.  This is almost clean using CREATE OR REPLACE in PG 7.2 - you 
first define the function with a dummy body, then do the C OR R with the 
real body.   The C OR R allows you to recursively reference the function 
since it was previously defined with a dummy body ...

If you want to grab the subtree and spit out the rows in order (as in 
grabbing rows to display a folder/file style hierarchy) a simple "order 
by" on the key works, and there's a "treelevel()" function that can be 
used to drive indention.


This has been well-tested on a handful of OpenACS 4/PG production 
websites and gives fast, indexed, tree operations.

I had looked at doing something like Oleg's describing but fell upon BIT 
VARYING and the fact that byte-aligned/byte-multiple lengthed bit 
strings are handled efficiently internally (having source to your RDBMS 
is so nice at times).  The advantage of this is that no non-standard 
type, operators for indexing, etc need to be added to PG.  There are 
just some PL/pgSQL functions and triggers on the tree table (to build 
the keys on insert/update).

When I find some time I thought I'd bundle this up and make it available 
separately but at the moment you have to grab the OpenACS 4 tarball.

Hannu or anyone else, if you're curious shoot me some private e-mail and 
  I'll tell you where to grab the pieces.


-- 
Don Baccus
Portland, OR
http://donb.photo.net, http://birdnotes.net, http://openacs.org

  5. Re: new module contrib/tree for 7.2 ?

    Bruce Momjian <pgman@candle.pha.pa.us> — 2002-01-25T17:04:58Z

    This has been saved for the 7.3 release:

	http://candle.pha.pa.us/cgi-bin/pgpatches2

---------------------------------------------------------------------------

Oleg Bartunov wrote:
> Hi,
> 
> Is't late to submit new contrib module for 7.2 ?
> It's almost ready and tested, we have to write README.tree.
> 
> New module creates new data types 'tree', 'treequery' for tree-like data and
> provides indexed access methods using Btree or GiST.
> Node represents as a path to the root, so record like '3.4' means
> 4-th child of 3-rd child of the root node.
> Due-to bit-representation there is a limitation to the number of
> children - 64 and defined in compile time (valid values - 8,16,32,64).
> For practical purposes 64 children looks quite enough.
> insert,delete operations should be ok, while move operations
> is a pain - one should update all paths of children nodes.
> But search is very fast, we use data from Open Directory catalog (www.dmoz.org)
> for testing:
> 
> Select all countries:
> 
> dmoz64=# explain analyze select * from dmoz where tid <* '18.*.0';
> NOTICE:  QUERY PLAN:
> 
> Index Scan using tid_g_idx on dmoz  (cost=0.00..1094.10 rows=277 width=100) (actual time=3.54..23.76 rows=56 loops=1)
> Total runtime: 23.96 msec
> 
> EXPLAIN
> dmoz64=#
> 
>        name         |             strid             |   id   |  tid
> ---------------------+-------------------------------+--------+-------
>  Tagalog             | Top/World/Tagalog             | 276537 | 18.18
>  Taiwanese           | Top/World/Taiwanese           | 276566 | 18.19
>  Tamil               | Top/World/Tamil               | 276567 | 18.20
>  Telugu              | Top/World/Telugu              | 276568 | 18.21
>  Thai                | Top/World/Thai                | 276601 | 18.22
>  Ukrainian           | Top/World/Ukrainian           | 276602 | 18.23
>  Vietnamese          | Top/World/Vietnamese          | 276603 | 18.24
>  Japanese            | Top/World/Japanese            | 268629 | 18.31
>  Kiswahili           | Top/World/Kiswahili           | 268630 | 18.32
>  Afrikaans           | Top/World/Afrikaans           | 256813 | 18.1
>  Italiano            | Top/World/Italiano            | 266163 | 18.30
>  Interlingua         | Top/World/Interlingua         | 266144 | 18.29
>  Indonesia           | Top/World/Indonesia           | 265859 | 18.28
>  Croatian            | Top/World/Croatian            | 257063 | 18.12
> ....................................................................
> 
> 
> 
> 	Regards,
> 		Oleg
> _____________________________________________________________
> Oleg Bartunov, sci.researcher, hostmaster of AstroNet,
> Sternberg Astronomical Institute, Moscow University (Russia)
> Internet: oleg@sai.msu.su, http://www.sai.msu.su/~megera/
> phone: +007(095)939-16-83, +007(095)939-23-83
> 
> 
> ---------------------------(end of broadcast)---------------------------
> TIP 5: Have you checked our extensive FAQ?
> 
> http://www.postgresql.org/users-lounge/docs/faq.html
> 

-- 
  Bruce Momjian                        |  http://candle.pha.pa.us
  pgman@candle.pha.pa.us               |  (610) 853-3000
  +  If your life is a hard drive,     |  830 Blythe Avenue
  +  Christ can be your backup.        |  Drexel Hill, Pennsylvania 19026

  6. Re: new module contrib/tree for 7.2 ?

    Bruce Momjian <pgman@candle.pha.pa.us> — 2002-02-23T02:25:57Z

    Oleg, can you send over a patch?

---------------------------------------------------------------------------

Oleg Bartunov wrote:
> Hi,
> 
> Is't late to submit new contrib module for 7.2 ?
> It's almost ready and tested, we have to write README.tree.
> 
> New module creates new data types 'tree', 'treequery' for tree-like data and
> provides indexed access methods using Btree or GiST.
> Node represents as a path to the root, so record like '3.4' means
> 4-th child of 3-rd child of the root node.
> Due-to bit-representation there is a limitation to the number of
> children - 64 and defined in compile time (valid values - 8,16,32,64).
> For practical purposes 64 children looks quite enough.
> insert,delete operations should be ok, while move operations
> is a pain - one should update all paths of children nodes.
> But search is very fast, we use data from Open Directory catalog (www.dmoz.org)
> for testing:
> 
> Select all countries:
> 
> dmoz64=# explain analyze select * from dmoz where tid <* '18.*.0';
> NOTICE:  QUERY PLAN:
> 
> Index Scan using tid_g_idx on dmoz  (cost=0.00..1094.10 rows=277 width=100) (actual time=3.54..23.76 rows=56 loops=1)
> Total runtime: 23.96 msec
> 
> EXPLAIN
> dmoz64=#
> 
>        name         |             strid             |   id   |  tid
> ---------------------+-------------------------------+--------+-------
>  Tagalog             | Top/World/Tagalog             | 276537 | 18.18
>  Taiwanese           | Top/World/Taiwanese           | 276566 | 18.19
>  Tamil               | Top/World/Tamil               | 276567 | 18.20
>  Telugu              | Top/World/Telugu              | 276568 | 18.21
>  Thai                | Top/World/Thai                | 276601 | 18.22
>  Ukrainian           | Top/World/Ukrainian           | 276602 | 18.23
>  Vietnamese          | Top/World/Vietnamese          | 276603 | 18.24
>  Japanese            | Top/World/Japanese            | 268629 | 18.31
>  Kiswahili           | Top/World/Kiswahili           | 268630 | 18.32
>  Afrikaans           | Top/World/Afrikaans           | 256813 | 18.1
>  Italiano            | Top/World/Italiano            | 266163 | 18.30
>  Interlingua         | Top/World/Interlingua         | 266144 | 18.29
>  Indonesia           | Top/World/Indonesia           | 265859 | 18.28
>  Croatian            | Top/World/Croatian            | 257063 | 18.12
> ....................................................................
> 
> 
> 
> 	Regards,
> 		Oleg
> _____________________________________________________________
> Oleg Bartunov, sci.researcher, hostmaster of AstroNet,
> Sternberg Astronomical Institute, Moscow University (Russia)
> Internet: oleg@sai.msu.su, http://www.sai.msu.su/~megera/
> phone: +007(095)939-16-83, +007(095)939-23-83
> 
> 
> ---------------------------(end of broadcast)---------------------------
> TIP 5: Have you checked our extensive FAQ?
> 
> http://www.postgresql.org/users-lounge/docs/faq.html
> 

-- 
  Bruce Momjian                        |  http://candle.pha.pa.us
  pgman@candle.pha.pa.us               |  (610) 853-3000
  +  If your life is a hard drive,     |  830 Blythe Avenue
  +  Christ can be your backup.        |  Drexel Hill, Pennsylvania 19026

  7. Re: new module contrib/tree for 7.2 ?

    Oleg Bartunov <oleg@sai.msu.su> — 2002-02-23T08:46:59Z

    On Fri, 22 Feb 2002, Bruce Momjian wrote:

>
> Oleg, can you send over a patch?
>

As soon as I write documentation :-) I hope I could use this weekend

	Oleg

> ---------------------------------------------------------------------------
>
> Oleg Bartunov wrote:
> > Hi,
> >
> > Is't late to submit new contrib module for 7.2 ?
> > It's almost ready and tested, we have to write README.tree.
> >
> > New module creates new data types 'tree', 'treequery' for tree-like data and
> > provides indexed access methods using Btree or GiST.
> > Node represents as a path to the root, so record like '3.4' means
> > 4-th child of 3-rd child of the root node.
> > Due-to bit-representation there is a limitation to the number of
> > children - 64 and defined in compile time (valid values - 8,16,32,64).
> > For practical purposes 64 children looks quite enough.
> > insert,delete operations should be ok, while move operations
> > is a pain - one should update all paths of children nodes.
> > But search is very fast, we use data from Open Directory catalog (www.dmoz.org)
> > for testing:
> >
> > Select all countries:
> >
> > dmoz64=# explain analyze select * from dmoz where tid <* '18.*.0';
> > NOTICE:  QUERY PLAN:
> >
> > Index Scan using tid_g_idx on dmoz  (cost=0.00..1094.10 rows=277 width=100) (actual time=3.54..23.76 rows=56 loops=1)
> > Total runtime: 23.96 msec
> >
> > EXPLAIN
> > dmoz64=#
> >
> >        name         |             strid             |   id   |  tid
> > ---------------------+-------------------------------+--------+-------
> >  Tagalog             | Top/World/Tagalog             | 276537 | 18.18
> >  Taiwanese           | Top/World/Taiwanese           | 276566 | 18.19
> >  Tamil               | Top/World/Tamil               | 276567 | 18.20
> >  Telugu              | Top/World/Telugu              | 276568 | 18.21
> >  Thai                | Top/World/Thai                | 276601 | 18.22
> >  Ukrainian           | Top/World/Ukrainian           | 276602 | 18.23
> >  Vietnamese          | Top/World/Vietnamese          | 276603 | 18.24
> >  Japanese            | Top/World/Japanese            | 268629 | 18.31
> >  Kiswahili           | Top/World/Kiswahili           | 268630 | 18.32
> >  Afrikaans           | Top/World/Afrikaans           | 256813 | 18.1
> >  Italiano            | Top/World/Italiano            | 266163 | 18.30
> >  Interlingua         | Top/World/Interlingua         | 266144 | 18.29
> >  Indonesia           | Top/World/Indonesia           | 265859 | 18.28
> >  Croatian            | Top/World/Croatian            | 257063 | 18.12
> > ....................................................................
> >
> >
> >
> > 	Regards,
> > 		Oleg
> > _____________________________________________________________
> > Oleg Bartunov, sci.researcher, hostmaster of AstroNet,
> > Sternberg Astronomical Institute, Moscow University (Russia)
> > Internet: oleg@sai.msu.su, http://www.sai.msu.su/~megera/
> > phone: +007(095)939-16-83, +007(095)939-23-83
> >
> >
> > ---------------------------(end of broadcast)---------------------------
> > TIP 5: Have you checked our extensive FAQ?
> >
> > http://www.postgresql.org/users-lounge/docs/faq.html
> >
>
>

	Regards,
		Oleg
_____________________________________________________________
Oleg Bartunov, sci.researcher, hostmaster of AstroNet,
Sternberg Astronomical Institute, Moscow University (Russia)
Internet: oleg@sai.msu.su, http://www.sai.msu.su/~megera/
phone: +007(095)939-16-83, +007(095)939-23-83

  8. Re: new module contrib/tree for 7.2 ?

    Bruce Momjian <pgman@candle.pha.pa.us> — 2002-03-08T01:16:26Z

    Sorry, didn't make 7.2, but can be added to 7.3 anytime.

---------------------------------------------------------------------------

Oleg Bartunov wrote:
> Hi,
> 
> Is't late to submit new contrib module for 7.2 ?
> It's almost ready and tested, we have to write README.tree.
> 
> New module creates new data types 'tree', 'treequery' for tree-like data and
> provides indexed access methods using Btree or GiST.
> Node represents as a path to the root, so record like '3.4' means
> 4-th child of 3-rd child of the root node.
> Due-to bit-representation there is a limitation to the number of
> children - 64 and defined in compile time (valid values - 8,16,32,64).
> For practical purposes 64 children looks quite enough.
> insert,delete operations should be ok, while move operations
> is a pain - one should update all paths of children nodes.
> But search is very fast, we use data from Open Directory catalog (www.dmoz.org)
> for testing:
> 
> Select all countries:
> 
> dmoz64=# explain analyze select * from dmoz where tid <* '18.*.0';
> NOTICE:  QUERY PLAN:
> 
> Index Scan using tid_g_idx on dmoz  (cost=0.00..1094.10 rows=277 width=100) (actual time=3.54..23.76 rows=56 loops=1)
> Total runtime: 23.96 msec
> 
> EXPLAIN
> dmoz64=#
> 
>        name         |             strid             |   id   |  tid
> ---------------------+-------------------------------+--------+-------
>  Tagalog             | Top/World/Tagalog             | 276537 | 18.18
>  Taiwanese           | Top/World/Taiwanese           | 276566 | 18.19
>  Tamil               | Top/World/Tamil               | 276567 | 18.20
>  Telugu              | Top/World/Telugu              | 276568 | 18.21
>  Thai                | Top/World/Thai                | 276601 | 18.22
>  Ukrainian           | Top/World/Ukrainian           | 276602 | 18.23
>  Vietnamese          | Top/World/Vietnamese          | 276603 | 18.24
>  Japanese            | Top/World/Japanese            | 268629 | 18.31
>  Kiswahili           | Top/World/Kiswahili           | 268630 | 18.32
>  Afrikaans           | Top/World/Afrikaans           | 256813 | 18.1
>  Italiano            | Top/World/Italiano            | 266163 | 18.30
>  Interlingua         | Top/World/Interlingua         | 266144 | 18.29
>  Indonesia           | Top/World/Indonesia           | 265859 | 18.28
>  Croatian            | Top/World/Croatian            | 257063 | 18.12
> ....................................................................
> 
> 
> 
> 	Regards,
> 		Oleg
> _____________________________________________________________
> Oleg Bartunov, sci.researcher, hostmaster of AstroNet,
> Sternberg Astronomical Institute, Moscow University (Russia)
> Internet: oleg@sai.msu.su, http://www.sai.msu.su/~megera/
> phone: +007(095)939-16-83, +007(095)939-23-83
> 
> 
> ---------------------------(end of broadcast)---------------------------
> TIP 5: Have you checked our extensive FAQ?
> 
> http://www.postgresql.org/users-lounge/docs/faq.html
> 

-- 
  Bruce Momjian                        |  http://candle.pha.pa.us
  pgman@candle.pha.pa.us               |  (610) 853-3000
  +  If your life is a hard drive,     |  830 Blythe Avenue
  +  Christ can be your backup.        |  Drexel Hill, Pennsylvania 19026