Thread: new module contrib/tree for 7.2 ?
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.18Taiwanese | Top/World/Taiwanese | 276566 | 18.19Tamil |
Top/World/Tamil | 276567 | 18.20Telugu | Top/World/Telugu | 276568 | 18.21Thai
| Top/World/Thai | 276601 | 18.22Ukrainian | Top/World/Ukrainian |
276602| 18.23Vietnamese | Top/World/Vietnamese | 276603 | 18.24Japanese |
Top/World/Japanese | 268629 | 18.31Kiswahili | Top/World/Kiswahili | 268630 |
18.32Afrikaans | Top/World/Afrikaans | 256813 | 18.1Italiano | Top/World/Italiano
| 266163 | 18.30Interlingua | Top/World/Interlingua | 266144 | 18.29Indonesia |
Top/World/Indonesia | 265859 | 18.28Croatian | 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
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
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, Pennsylvania19026
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
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, Pennsylvania19026
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, Pennsylvania19026