Pl/Perl Recursion

While solving the Perl Weekly Challenge 154, I provided a couple of possible solutions in Pl/Perl, the widely available Perl integration within PostgreSQL.
One task to solve, Padovan numbers, required to use recursion, and that is something not as simple as it could seem to implement using Pl/Perl.
Why?
Because Pl/Perl does not expose Perl objects, rather is a way to execute Perl within SQL objects (e.g., functions). What it means is that SQL objects are (clearly) the first class objects available, so you have always to use SQL functions to recurse.
Except when you don’t want to!

But let’s start simple and see how to solve the problem.

Padovan numbers

A Padovan number is a number defined as the sum of two preceeding numbers in the sequence. In particular:

• P(0) = P(1) = P(2) = 1, the first three elements of the sequence are equal;
• P(n) = P(n - 3) + P(n - 2)

This is great for recursion, because you can define a function in Pl/pgSQL as follows:

Translating to Pl/Perl and the problem of recursion

The above Pl/pgSQL function cannot be translated byte-by-byte to Pl/Perl; the following will not be possible:



In fact, the padovan_not_working is a function on the SQL side, and thus cannot be called by PlPerl as a Perl function.
One, ease, solution, could be to accept the fact that the resulting function is an SQL object and interact with it accordingly:



As you can see, the function invokes itself by means of an SQL query.

Using a closure

It is possible to use a closure to hold the reference to an anonymous code block, so that it is possible to implement the recursion as follows:



No need for queries, no need for external modules, but there are memory leaks due to the reference counting.

Using Sub::Recursive

There is a module, named Sub::Recursive that does exactly what I would like to go: allows to define an anonymous code block that can recursively invoke itself without any leak.
The only drawback is that the function must be run as Pl/Perl unsafe because it needs to load a module outside of the PostgreSQL server (and of course, the module must be on the system, cpanm is your friend!):



That’s it! No need for queries, no need for %_SHARED, no need for closures (apparently), just Perl!
But, there is the need for plperlu!
The module provides the special keyword recursive that accepts a code reference with the closure $REC that holds a reference to the code block itself.

Using %_SHARED ?

Another way to use recursion is by means of the Pl/Perl global hash %_SHARED, that is used to share whatever object you want across different functions. The idea is to share a function, so that it is possible to invoke it directly later on.
The implementation could be as follows:



The first function, plperl_padovan_init, installs a code reference $padovan into the global Pl/perl hash %_SHARED, so that other functions can obtain such code reference. The code is the same as in the other examples.
Then the function is explicitly invoked, so that the code reference is installed.
Later on, the plperl_padovan_shared function gets the code reference and use it as a normal function.

Quick and dirt comparison

I’ve done a very short one-launch comparison among the approaches, excluding the one based on %_SHARED because it is very similar to the approach using the pure recursion via code reference. Just for the records, asking to the %_SHARED based approach to compute the 50-th Padovan number requires around 0.5 secs that is, as expected, in line with the other similar approaches.
Increasing the Padovan number to compute makes the Perl approaches based on pure or Sub::Recursive really similar in terms of execution time. The approach that performs a query to use recursion is, as you can imagine, the slowest one and its performance decreases very quickly as the numbers grow. The following table summarizes times depending on the generated number:

Padovan number	Sub::Recursive	closure	query
10	12 ms	20.39 ms	17.61 ms
20	0.51 ms	18.18 ms	12 ms
30	1.2 ms	17.9 ms	27.99 ms
40	31.9 ms	30.01 ms	323.4 ms
50	0.50 secs	0.52 secs	5.9 secs
60	12.76 secs	10.35 secs	99.77 secs
65	35.09 secs	35.78 secs	385 secs
70	142 secs	145 secs	1580 secs
71	187.89 secs	196.24 secs	2122.8 secs

It is not possible to keep increasing the Padovan number because of integer overflow, therefore I would have to adjust the functions to return bigint, but in any case I’m not expecting much different result trends.

Conclusions

Recursion in Pl/Perl could be hard to implement and could require fancy approaches like the closure based ones. First of all, you need to decide if you can deal with untrusted languages: if so, probably installing a module is the easiest and rightmost approach. If you don’t want to deal with untrusted code, you need to decide if you prefer to use a pure Perl approach, in such case a code reference is the choice, or you want to have something that can be invoked by other languages. The latter means using a more SQL-toward approach, while the former means sticking with a code refence, either used immediatly or by means of some sort of shared storage.