25.4 Tuning Your Algorithms

Chapter 25
Tuning PL/SQL Applications

 

---

Tuning algorithms is a very application-specific activity. There is no general rule to be applied, and I have no generic tips. Instead, in this section I offer two "case studies" of tuning exercises I performed on some real-world code. Following those explorations are more general suggestions for writing optimized PL/SQL code.

25.4.1 There Are No Sacred Cows

In many places in this book, I recommend that you follow the principle of top-down design in building your applications and even single modules. This step-by-step process almost guarantees that you will come up with the most modular, logical solution to your problem. Unfortunately, that solution may not always be the most efficient performer. In such situations, you need to be ready to switch gears, tear down what you have built, and reconstruct it to improve performance.

In other words, you must be creative and, in some cases, even take a counter-intuitive approach to achieve the required performance levels in your application. Do not hang onto code just because you happened to have stayed up too late too many nights in a row to get it "just right." If it doesn't do the job, don't hesitate to scrap your implementation and try again.

Consider the build_pv_lease_schedule procedure shown below:

PROCEDURE build_pv_lease_schedule /* Construct present value lease schedule over 20 years. */ IS    /* Temporary variable to hold lease accumulation. */    pv_total_lease NUMBER(9);    /* Table structure to hold the lease accumulations. */    TYPE pv_table_type IS TABLE OF NUMBER(9) INDEX BY BINARY_INTEGER;    pv_table pv_table_type; BEGIN    FOR year_count in 1 .. 20    LOOP       /* Reset the lease amount for this year. */       pv_total_lease := 0;       /*       || Build the PV based on the remaining years       || plus the fixed and variable amounts.       */       FOR year_count2 in year_count..20       LOOP          /* Add annual total lease amount to cummulative. */          pv_total_lease :=             pv_total_lease +             pv_of_fixed (year_count2) +             pv_of_variable (year_count2);       END LOOP;       /* Add the annual PV to the table. */       pv_table (year_count) := pv_total_lease;    END LOOP; END;

This module constructs a schedule of lease payments for a store and saves them in a PL/SQL table. For each of 20 years, the lease amount is calculated as the sum of lease amounts for the remaining years. The total lease for year 10, in other words, would consist of the lease amounts (fixed and variable) for years 10 through 20. The procedure reflects this logic directly and simply with nested loops:

FOR year_count IN 1 .. 20 LOOP    FOR year_count2 IN year_count .. 20    LOOP       ... computation ...    END LOOP; END LOOP;

The build_pv_lease_schedule procedure is clean, direct, and to the point. The only problem with this code it that it took six seconds to calculate the 20 values in the lease schedule. This was simply too long a time, combined as it was with several other operations. A new approach was needed and I was asked to come up with alternatives.

One reason that I was brought in to perform the review is that it can be very difficult for a program's author to be creative about new ways of doing things. I have found that once I write something, once I feel I have reached a resolution, and once I see it in a printout, that particular approach entraps me, limiting my vision.

The nested loop technique was such a natural fit for this algorithm that it took an outsider to break away from this construct to tune the code. Now that you have seen this technique, can you see a more efficient way to perform this calculation?

My first step in analyzing and correcting the procedure was to be aware of just how many computations the program performed to come up with its answer. For each of the 20 years, the inner loop performs 20-N +1 calculations. So over 20 years, the nested loop performs:

20 + 19 + 18 + ... + 3 + 2 + 1 = 210 calculations of annual lease amounts

to come up with the 20 accumulated lease amounts. Well, that's a lot of activity! No wonder it takes six seconds. The question in my mind then became: are all these calculations necessary? They would certainly all be required if each computation were unique, that is, not repeated during the nested loop execution. This is not, however, the case. In fact, many of the computations are exactly the same. For year 1, I calculate the annual lease amounts for years 1 through 20 to produce the year 1 accumulation. For year 2, I calculate the annual lease amount for years 2 through 20, and so on. For each year N, in other words, I calculate the annual lease amount for that year N times. Furthermore, within each execution of the inner loop, I am simply summing up the annual lease amounts for the subset of the full 20 years, as shown here:

Outer Loop Year Number	Years Over Which Lease Amounts are Summed in Inner Loop
1	Year 1 + Year 2 + ... + Year 20
2	Year 2 + ... + Year 20
...
18	Year 18 + Year 19 + Year 20
19	Year 19 + Year 20
20	Year 20

From this table you can see that the difference between the total amount for year N and the total amount for year N-1 is the lease amount for year N. Starting with year 1, it then becomes clear that the total lease amounts are all reductions from that year 1 total. From this understanding, I found that I could generate the accumulated lease amounts for each year by substracting from the full 20-year accumulation, rather than having to build it up each time anew.

With this approach, I would build my lease schedule in two phases: first, for each year, calculate the annual lease amount and save that value. Simultaneously, add that value to the 20-year accumulation. In pseudo-code I have:

FOR year_count IN 1 .. 20 LOOP    save annual lease amount    add annual lease amount to 20-year accumulated total END LOOP;

Once I have my 20-year accumulation and my 20 individual annual lease amounts, I can produce the 19 other accumulations as follows:

copy 20-year total to accumulated total variable FOR year_count IN 2 .. 20 LOOP    subtract annual lease amount from accumulated total    save difference to PL/SQL table END LOOP;

In other words, for year 2, subtract the annual lease amount of year 2 from the 20-year total. This is the 19-year accumulation. For year 3, subtract the annual lease amount of year 3 from the 19-year total. This is the 18-year accumulation. And so on.

With this approach, shown in full PL/SQL glory below, I perform only 20 lease computations and then another 20 simple subtractions, down from 210 lease computations:

PROCEDURE build_pv_lease_schedule IS    pv_total_lease NUMBER(9) := 0;    TYPE pv_table_type IS TABLE OF NUMBER(9) INDEX BY BINARY_INTEGER;    pv_table pv_table_type; BEGIN    /*    || Build the 20-year accumulated total and save each    || of the annual lease amounts to the PL/SQL table. Notice that    || pv_table (N) is set to the annual lease amount for year N-1.    */    FOR year_count in 1 .. 20    LOOP       one_year_pv :=          pv_of_fixed (year_count) + pv_of_variable (year_count);       pv_total_lease := pv_total_lease + one_year_pv;       IF year_count < 20       THEN          pv_table (year_count+1) := one_year_pv;       END IF;    END LOOP;    /* Save the 20-year total in the first row. */    pv_table (1) := pv_total_lease;    /* For each of the remaining years... */    FOR year_count IN 2 .. 20    LOOP       /* Subtract the annual amount from the remaining total. */       pv_total_lease := pv_total_lease - pv_table (year_count);       /*       || Save the Nth accumulation to the table (this writes right       || over the annual lease amount, which is no longer needed.       || I get double use out of the pv_table in this way.       */       pv_table (year_count) := pv_total_lease;    END LOOP; END;

By converting the nested loop to a sequence of two distinct loops, I cut down the elapsed time of this procedure from six seconds to three seconds. Both approaches produce the same number. The first technique was the more obvious and straightforward of the two. It did not, however, minimize the amount of effort required to produce the computations. It took careful analysis and rewriting both to preserve the correct values and to optimize the performance.

One should never underestimate the value of code review. In the process of having this chapter reviewed, both Eric Givler and Kannan Muthukkaruppan were quick to point out an even simpler and faster solution to this problem:

PROCEDURE build_pv_lease_schedule IS    pv_total_lease number(9) := 0;    one_year_pv number(9) := 0;    type pv_table_type IS TABLE OF NUMBER(9) INDEX BY BINARY_INTEGER;    pv_table pv_table_type; BEGIN    FOR year_count IN REVERSE 1..20    LOOP       one_year_pv := pv_of_fixed(year_count) +                      pv_of_variable(year_count);       pv_total_lease := pv_total_lease + one_year_pv;       pv_table (year_count) := pv_total_lease;    END LOOP; END build_pv_lease_schedule;            

I was at first resistant to accepting that this use of a REVERSE FOR LOOP gets the job done. Eric, fortunately, did not give up and finally I was convinced. You just start from the last year and go backwards accumulating the values, completely eliminating the need for two different loops and much extraneous processing!