In this article I'm going to show you how do implement a depth-first search using a stored procedure written in Perl inside the PostgreSQL database server.
Depth-first search is an advanced algorithm for quickly traversing all nodes in a tree (like, e.g., a filesystem). In this example we're going to store our tree in a database using a very simple structure. The method I'm going to show you will also allow you to use separate sort order for each node in the tree. As you might know, databases that support SQL99 recursive queries (WITH keyword) can probably do all of this with regular SQL, but the query is not very easy to read and understand.
The problem I'm trying to solve is basically to indent each record as we print it out with the required number of spaces so that it looks like a tree instead of a flat table. Because this is insanely time consuming to do client-side as the tree increases in size, I'm going to show you how to do it with just one single SQL query.
The database structure we're going to use is very simple:
CREATE TABLE tree (
id UUID NOT NULL DEFAULT uuid_generate_v4(),
name VARCHAR(100) NOT NULL,
created TIMESTAMP NOT NULL DEFAULT current_timestamp,
Let's assume that you have a Ubuntu or Debian machine running that has PostgreSQL 8.3 available in the repositories. The reason I'm suggesting version 8.3 is that it has built-in support for the UUID datatype and a contrib module for generating them. This way we don't need to muck around with sequences for our primary keys.
Let's assume you're logged in as a user with full sudo access. Run this code to install the necessary packages needed for the examples:
$ sudo aptitude install postgresql-8.3 postgresql-plperl-8.3 postgresql-contrib-8.3 libdbd-pg-perl gidentd
This is what the different packages do, in case you need to look for them on other OSes:
- postgresql-8.3: The database server itself and the client libraries.
- postgresql-plperl-8.3: Support for perl stored procedures in postgresql.
- postgresql-contrib-8.3: Has the uuid_generate_v4() function.
- libdbd-pg-perl: DBD::Pg cpan module, why not use the included one?
- gidentd: With this one we can use the default ident authentication for local postgresql users, quite handy on a development box.
After this you need to create a database user (role) for you to create databases. This command will make a user with the same name as the user you're logged in as. This is just a very quick way to enable ident authentication for your user with minimum hassle. The arguments mean: no-superuser (-S), create-database (-d) and no-roles (-R). Invert the case if you want to give yourself more/less rights.
$ sudo -H -u postgres createuser -S -d -R $(whoami)
After that we're ready to create our database and populate it with necessary defaults. Then we install the procedural language into our database, and finally install the uuid generator functions. The UUID functions must be added to the database as a database superuser because they're written in C.
$ createdb -E UNICODE test
$ createlang plperl test
$ sudo -H -u postgres psql -1 test -f /usr/share/postgresql/8.3/contrib/uuid-ossp.sql
In case you're wondering what that -1 argument is, it means to run everything in a transaction.
Next thing is to create our test database. I'm going to assume that you put the above mentioned table definition in the file schema.sql.
$ psql -1 test -f schema.sql
Okay, so now we have a nice little table that we can fill with some data. Since you're probably as lazy as I am and don't want to create a lot of data yourself I've prepared a small chunk of map data you can play with.
It's available here: http://files.smidsrod.no/example_data.sql
Import it quickly like this:
$ wget -q -O - http://files.smidsrod.no/example_data.sql | psql -a -1 test
The -a option is there so that you can quickly see the results from the import.
If you've looked closely at the data you will see that it implements a simple tree structure with several roots (all the records with empty parent_id). In this example I won't make use of the url attribute, but it's in there for a future article I'm planning to write. I've also included some UTF-8 data just for fun.
By now you're probably getting a little bit bored with all of this mundane database stuff. Let's get on with what I really wanted to show you!
To be able to return data in a smart way we need a custom datatype. This is trivially simple to create in postgresql. Save it as node.sql and import (you should be getting the hang of this now):
CREATE TYPE "public"."node" AS (
The DFS (Depth-First-Search) algorithm is a bit large, so just install it quickly from http://files.smidsrod.no/depth_first_search.sql.
$ wget -q -O - http://files.smidsrod.no/depth_first_search.sql| psql -1 test
Now you should be able to run this simple query to get a set of data suitable for creating a tree.
$ psql -1 test -c 'select tree.name,tt.node_id,tt.node_level from traverse_tree(null) tt JOIN tree ON node_id=tree.id;'
Just to demonstrate how useful this is you can try to run traverse_tree.pl and look at the output.
$ wget -q -O - http://files.smidsrod.no/traverse_tree.pl.txt | perl
f2880759-6b8e-494f-add9-69edfad07fab United States
Voila! Problem solved with only one query transmitted to the database that does all the work.
Next week I'll show you how to convert this dataset to an HTML unordered list.