Of course, memoization is not necessarily the best way to speed up a function. Some languages provide memoization support natively or via easily added libraries, but PL/pgSQL offers no such facility. This means adding a fair bit of code to memoize the function. You have something fast, but also something slightly more difficult to maintain.
There's another approach to determining the Fibonacci number for a particular position in the sequence that involves neither recursion nor memoization. Execute a loop
fib_for number of times and keep track of the calculation each time through. How does that look?
CREATE OR REPLACE FUNCTION fib_fast( 1 fib_for integer 2 ) RETURNS integer AS $$ 3 DECLARE 4 ret integer := 0; 5 nxt integer := 1; 6 tmp integer; 7 BEGIN 8 FOR num IN 1..fib_for LOOP 9 tmp := ret; 10 ret := nxt; 11 nxt := tmp + nxt; 12 END LOOP; 13 14 RETURN ret; 15 END; 16 $$ LANGUAGE plpgsql; 17
Everything should look familiar up through line eight, but notice the declaration of multiple variables in the
DECLARE block and the initial values assigned to two of them. The new variables,
tmp, will track the Fibonacci numbers through each iteration of the loop.
Speaking of the loop, it begins on line nine. All loops in PL/pgSQL use the
LOOP keyword and end with
END LOOP. A loop can begin with nothing more than
LOOP, in which case it will be an infinite loop (break out of it with the
EXIT keyword). Otherwise, there are a couple of different approaches to looping in PL/pgSQL, including
WHILE (such as
WHILE foo IS NULL LOOP) and
FOR loop is the only context in PL/pgSQL where you can use a variable without predeclaring it in the
DECLARE block. The form used here (there are other forms--for iterating over rows in a
SELECT query, for example), uses the variable
num, which is automatically created as a read-only integer variable that exists only in the scope of the loop, to loop
fib_for times. This example doesn't actually use
num in the loop, but I thought you should know that it could.
The only thing that happens inside the loop is assignment. The
ret variable once again keeps track of the return value, while
nxt track the previous and next values in the sequence. That's it. Once the loop has run through all of its iterations, the function returns the last value stored in
How does the use of the loop affect performance?
try=% explain analyze select fib_fast(26); QUERY PLAN ------------------------------------------------------------------------------------ Result (cost=0.00..0.01 rows=1 width=0) (actual time=0.433..0.433 rows=1 loops=1) Total runtime: 0.485 ms (2 rows)
It's over four times faster than the cached version, mainly because there are no longer any queries to an external table. It'll be faster with lower numbers and slower with higher numbers because the
fib_for argument determines the number of iterations required. (Any number over 45 won't work at all because the return values will be too big for PostgreSQL integers. If you need them that big, use
Of course these functions are not very practical (except as teaching examples), unless for some reason you need to calculate Fibonacci numbers in your database. The real advantages of PL/pgSQL become apparent when you use it to simplify situations where client code must typically make numerous database calls to satisfy a data pattern. In the interests of illustrating such practical PL/pgSQL, my next article will demonstrate how to write PL/pgSQL functions to simplify the management of ordered many-to-many relationships.
My thanks for David Fetter for suggesting the memoized version of
fib() as an illustrative example for this article, and to Mark Jason Dominus and his terrific Higher Order Perl for an excellent discussion and examples of the Fibonacci sequence functions. I'd also like to thank AndrewSN for providing feedback on a draft of this article.
Return to ONLamp.com.