473,545 Members | 2,081 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

Recursing tree data in PL/pgSQL

Hi,

I've been scouring the net and reading the PostgreSQL docs for a while
now trying to learn how to create a recursive function in PL/pgSQL
that will return a whole subtree given a starting node. I wanted to
share my summary results here. Maybe this will help someone and save
them from doing a bunch of research (like I had to do :). For the
record, this is the first thing I've ever written in PL/pgSQL,
although I do have significant SQL experience. If any PostgreSQL
developers are reading this, you should implement a "CONNECT BY /
PRIOR" SQL command like Oracle does. It turns all this stuff into a
2-line SQL query. No extra functions needed.

In this proof-of-concept, I just did a lame table that has a node and
a parent which points back to another node in the same table. No
actual content. Also note the function overloading for the helper to
make it take just one argument. I'm passing a depth argument in this
example even though I don't use it. Again...proof-of-concept. The
depth of recursion is often useful to know. You can do LPAD()s to
indent your tree, for example.

One thing that's not immediately obvious if you've never done this:
RETURN NEXT is used to build up a return set, one row at a time. When
you're done, you RETURN and it returns the built-up set.

I did a few benchmarks on this data set. I wrote an equivalent
recursive function in PHP such that a new SQL query was issued on each
level of recursion. I "SELECT node, parent FROM tree WHERE parent =
$root" in PHP, and for each row I recurse on the PHP function. Bear in
mind this is a very small dataset (9 rows) and also that the database
and PHP are running on the same Linux 2.4.20 box. It would be
interesting to re-benchmark this with a much, much larger dataset.
Below is the ratio of execution time of PHP to SQL recursion on a few
trials.

Hope this helps someone,
Travis

PHP / SQL: 1.5631495206638
PHP / SQL: 1.488893156209
PHP / SQL: 1.8263854296389
PHP / SQL: 2.6210461029564
CREATE TABLE tree (node INTEGER, parent INTEGER);
INSERT INTO tree(node,paren t) VALUES(1,0);
INSERT INTO tree(node,paren t) VALUES(2,0);
INSERT INTO tree(node,paren t) VALUES(3,1);
INSERT INTO tree(node,paren t) VALUES(4,3);
INSERT INTO tree(node,paren t) VALUES(5,4);
INSERT INTO tree(node,paren t) VALUES(6,2);
INSERT INTO tree(node,paren t) VALUES(7,6);
INSERT INTO tree(node,paren t) VALUES(8,6);
INSERT INTO tree(node,paren t) VALUES(9,2);

CREATE OR REPLACE FUNCTION getTree(INTEGER , INTEGER) RETURNS SETOF
tree AS '
DECLARE
root ALIAS FOR $1;
depth ALIAS FOR $2;
tempRow1 tree%ROWTYPE;
tempRow2 tree%ROWTYPE;
BEGIN
-- Using PostgreSQL 7.3.4.
-- Docs: http://www.postgresql.org/docs/7.3/static/plpgsql.html
-- See chapter 19, especially 19.6

FOR tempRow1 IN SELECT node, parent FROM tree WHERE parent = root
LOOP
RETURN NEXT tempRow1;
FOR tempRow2 IN SELECT node, parent FROM
getTree(tempRow 1.node, depth+1) LOOP
RETURN NEXT tempRow2;
END LOOP;
END LOOP;
RETURN;
END;
' LANGUAGE 'plpgsql';

CREATE OR REPLACE FUNCTION getTree(INTEGER ) RETURNS SETOF tree AS '
DECLARE
root ALIAS FOR $1;
tempRow tree%ROWTYPE;
BEGIN
FOR tempRow IN SELECT node, parent FROM getTree(root, 0) LOOP
RETURN NEXT tempRow;
END LOOP;
RETURN;
END;
' LANGUAGE 'plpgsql';

SELECT * FROM getTree(0);
node | parent
------+--------
1 | 0
3 | 1
4 | 3
5 | 4
2 | 0
6 | 2
7 | 6
8 | 6
9 | 2
(9 rows)

SELECT * FROM getTree(1);
node | parent
------+--------
3 | 1
4 | 3
5 | 4
(3 rows)

SELECT * FROM getTree(2);
node | parent
------+--------
6 | 2
7 | 6
8 | 6
9 | 2
(4 rows)
Jul 19 '05 #1
0 7162

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

12
6107
by: Pete..... | last post by:
Hi all. I have made a webpage where there is a webform where people can fill in their personel information: The code is below: I want to transfer the data to a postgreSQL database ( I have allready made the database with the neccesary tables, and I know how to connect to it ) but I really have no idea how I can transfer the data from...
4
2400
by: projecktzero | last post by:
Well, I've managed to get an image into a postgre database, but now I'm having trouble getting it out. #! /usr/bin/env python from pyPgSQL import PgSQL def main(): connectdb = PgSQL.connect('server:port:database:username:password') cur = connectdb.cursor()
19
6750
by: Christian Fowler | last post by:
I have a VERY LARGE pile of geographic data that I am importing into a database (db of choice is postgres, though may hop to oracle if necessary). The data is strictly hierarchical - each node has one, and only one parent. The depth should not exceed 6 or 7 levels. The initial import will have about 6 million leaves, and 3 million branches. I...
5
15058
by: D. Dante Lorenso | last post by:
I have a simple table that I'd like to query to pull out a heirarchy from a tree relationship. What is the best way to do this without a 'CONNECT BY' clause like Oracle has? Example mytable +----------+-----------+ | child_id | parent_id |
19
3789
by: snowdy | last post by:
I am using Interactive C with my handboard (68HC11) development system but I've got a problem that I am asking for help with. I am not new to C but learning all the time and I just cant see how to overcome this problem. Symptom: Programs fail ' Runtime error' which equates to a stack error. This is because my code is like going around and...
4
9004
by: Tarique Jawed | last post by:
Alright I needed some help regarding a removal of a binary search tree. Yes its for a class, and yes I have tried working on it on my own, so no patronizing please. I have most of the code working, even the removal, I just don't know how to keep track of the parent, so that I can set its child to the child of the node to be removed. IE - if...
8
1974
by: Steve Atkins | last post by:
I have an application where each user session opens and maintains a long-lived connection to the postgresql backend database. I need to keep a small amount of information (things like a unique session identifier, the application - as opposed to database - username and so on) that is local to each database session. It needs to be visible...
2
1923
by: elein | last post by:
When creating a new data type, what are the operators absolutely necessary for that type to particpate in a btree index? I know you need a "compare" that says = < or >= so does that mean that those three operators are the ones required? If you also know that answer for our implementation of R-trees that would also be helpful.
2
1607
by: Gellert, Andre | last post by:
Hello, I have following problem: A user "xy" shouldn't have any rights to a table, but needs data from the content of the table. My idea was to setup a PL/PGSQL procedure to fetch the data from the table, so that the user only is allowed to access the procedure. I also tried using a SQL function, but this doesn't work, too. Working with...
0
7468
marktang
by: marktang | last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main...
0
7401
by: Hystou | last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can effortlessly switch the default language on Windows 10 without reinstalling. I'll walk you through it. First, let's disable language...
1
7423
by: Hystou | last post by:
Overview: Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For...
0
7757
tracyyun
by: tracyyun | last post by:
Dear forum friends, With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the...
0
4945
by: conductexam | last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one. At the time of converting from word file to html my equations which are in the word document file was convert...
0
3450
by: TSSRALBI | last post by:
Hello I'm a network technician in training and I need your help. I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs. The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols. I succeeded, with both firewalls in...
0
3443
by: adsilva | last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
1
1014
muto222
by: muto222 | last post by:
How can i add a mobile payment intergratation into php mysql website.
0
704
bsmnconsultancy
by: bsmnconsultancy | last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.