new module contrib/tree for 7.2 ?

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

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

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

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

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

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

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