How Does Oracle Perform Math?
June 14, 2006
No, this article is not about the math behind Oracle's pricing scheme. The question posed in the title has to do with the calculator math, which comes with Oracle. Over the past 30 years, calculators have evolved from expensive novelties to inexpensive, largely ignored dust collectors. What calculators routinely do today dwarfs by many orders of magnitude what a TI-50, the de facto Cadillac of non-HP/non-RPN calculators, could do back in 1976. Oracle's built-in functions rival most of today's scientific and financial calculators, and this functionality is what the title is about.
Suppose you and some of your friends decided to build a bigger and better relational database management system. Aside from the expected functionality with respect to data management, you would, of course, build in the same type of calculator functions you see in Oracle. The question is, then, how do you make your new database perform calculator-type functions? Let's take a look at a common function: the LN(x) natural logarithm function. The natural log function is a good example because like other functions, there is typically more than one way to compute an output for a given input.
Application Requirements for the Calculator
The good news is that the wheel has already been invented, but the bad news is that you have to reverse engineer it for your proposed RDBMS. The LN function, as described in the Oracle Database SQL Reference 10g Release 2 (10.2) guide, returns the natural logarithm of n, where n is greater than 0. As you no doubt recall from high school algebra classes, the base of the LN function is e, and e to what power results in a value equal to zero (or something less than zero)? Like the LOG function (using 10 as its base), the only possible range of values for power(e,x) or power(10,x) is something strictly positive (i.e., greater than zero), so there is no number "x" that can result in power(e,x) being less than or equal to zero.
How well, that is, how fast and how accurate, does Oracle compute, say, the natural log of 2? An answer of out to 40 decimal places in about 1/100th of a second is what you are competing against.
As a comparison, the Windows calculator computes LN(2) to be 0.69314718055994530941723212145818. An illustration between this and the Oracle computed value is useful, and one can see the values match at the 32nd decimal place when the Oracle value is rounded as such.
Now that we know what is produced, the next question concerns how it is produced. Any number of sites on the Internet or appendices in Calculus textbooks, to name two sources, typically shows formulas as seen below.
All of these formulas are well within the realm of being coded in PL/SQL. Let's try two of them: the second one and the next to last one (where ln[(1+x)/(1-x)] is shown).
The First Candidate Function
Substituting 2 for x in the first of our examples results in the what may already be a familiar formula of:
LN(2) = 1 1/2+ 1/3 1/4 + 1/5 1/6 + 1/7 1/8 + ...
A common technique in numerical analysis is to use an error value or level as a stopping criterion. The error value, when reached, will stop the computational process because the computed value has been deemed "close enough" to a desired target. The target can be the previous computed value, meaning that the difference between the nth and the n-1st values is "close enough" to stop, or that the difference between the current value and a specified value is now less than the error level. The PL/SQL block shown below is one way to test how fast we can compute LN(2).
Before you compile and run this, how many iterations, that is, how big is "i" when v_error = 0.0005 is used, does it take to stop? Would you believe more than 1000 iterations are required?
Take note of two things here. First is the amount of time, and the second is that the error level is only 5/10,000ths, which may seem close, but is relatively far away from the Oracle computed value. The results of minimizing the error level looks as follows:
The initial conclusion about the performance is that each additional decimal place requires 10 times as many iterations as its predecessor.
Another area related to performance concerns convergence. Do results converge towards the true value, and if so, how fast do they converge? Our candidate function is an alternating sign type of function, so results (generally speaking) will bound the true value of LN(2). One output will be more and the other less is one way to frame how the values appear. A second conclusion about the current alternating sign function is that it converges slowly. It took almost 12 minutes to reach the stopping level of .000000005, and the Oracle (and Windows) functions were practically instantaneous with a much greater level of precision. Let's try the other candidate formula and see how it compares.
The Second Candidate Function
The first several terms of ln[(1+x)/(1-x)] are:
LN [(1+x)/(1-x)] = 2[3-1 + 3-3/3 + 3-5/5 + 3-7/7 + ... ]
In this case, "x" is not 2, but rather, some value which makes (1+x)/(1-x) equal to 2. A value of x=1/3 does the trick, and a procedure for computing LN(2) is shown below. Some of the computational steps for LN(2) are already built in (that's why all the 3's appear in the formula above and in the v_sum variable below).
The table below shows that the "ln2b" procedure ("b" meaning this is the "b" version; the first one was the "a" version) costs one more iteration for each additional decimal place, but the time to run is what counts the most here. The ln2b version of the LN(x) function appears to be competitive with the performance offered by Oracle.
So, that's one function down, 12 more to go when considering sin, cos, tan, exp and other transcendental functions included in Oracle.
Three performance factors to consider when coding your RDBMS's built-in functions are speed, convergence, and accuracy. A fast function that converges to an inaccurate value may be just as bad as a function that tends to converge to a very accurate value, but takes forever to do so. You can imagine the fun ("fun" being relative, of course) 1950's era computer scientists had when coding algorithms for use in the first mainframes. Numerical analysis played a key role in choosing which algorithm or mathematical approach should be used for a given problem. Without the benefit of this type of work over the past 50 years, how would you compute cos(∏) today? That is actually a double-edged question, because not only is the cosine function involved, but so is deriving a value for pi. We take Oracle's built-in numeric functions for granted, just like the way we do desktop calculators, but thankfully, they are quite performant in the sense of speed, convergence, and accuracy.