A lot of developers, in my experience, don't think much of PL/SQL because they believe that it performs slowly, or because its functionality is limited. For this project, PL/SQL performed the tasks (mostly data manipulation) as fast or faster than an equivalent C implementation could have done because there were fewer context switches and no network communication involved. (Developers unfamiliar with PL/SQL can reference the original article's sidebar for a brief introduction. It is loosely based on Ada.)
The problem for which I had to develop a solution required that the time-series data be viewed in ways which are not supported by Oracle SQL queries on the original data; it was necessary to restructure the data. This turned out to be more of a problem than I had originally anticipated, and the eventual solution to the problem came from an interesting combination of techniques. In the end, I adapted data structures that are more naturally represented in languages like C, C++, and Java in PL/SQL.
The Shape of the Problem
The data was stored in the database as multiple records representing the data class, the starting and ending dates, and the value. Records could have any value (positive or negative) that spans any amount of time. Multiple entries of the same data class for overlapping time periods could be present. Data 1, below, shows how records for a five-day period might be represented.
Type : Value : Dates
ABC:1:06/01/01 - 06/01/01
DEF:15:06/01/01 - 06/05/01
ABC:3:06/01/01 - 06/03/01
GHI:10:06/02/01 - 06/03/01
Data 1: Sample Data
This particular program needed to divide and combine the records such that there was one record for each data class per day, containing the portions of values which occurred on that day. If a record crossed multiple days, the program needed to see it within the daily summary for each of the days in which it existed and only for the proportion of the record that existed in that day. That is, because record GHI spans two days, the program has to treat it as if it were two separate GHI records, each of value 5. Similarly, there will be a total of three ABC records; the first record will have value 2 because that is the total of the portions of ABC records on that date. Data 2 shows how the data needs to be reorganized on a daily basis.
Type : Value : Date
Data 2: Sample Data Converted into Daily Records
The ideal way to handle this problem would be to make it so that as each record is added to the original table, a trigger is fired that does the record division as noted in data 2 and adds the resulting records to a daily summary table. This solution has three major problems with it:
- The source table from which the original records were pulled was a very high volume table (and significantly larger than the sample data shown). Performing the split on a per-insert basis is computationally expensive, as each data class was generally expected to have at least one record and more likely several records each day (note that the examples given in this article assume only a single data source).
- The total volume of the data in the source table was very high, and the daily summary table would be at least as large, and most likely several times larger than the source table. Since these values are computed and are used in a single subsystem (this one) only, it didn't make sense to use that much storage for what was essentially a temporary table.
- Each of the records in the data source table had a limited lifespan; once the analysis had been run on the record successfully, the analyzing program would never see it again. This would have increased the volume of the summary table unacceptably, because the summaries would have to be differentiated by visibility.
Without a temporary summary table, there was no way to do solve this problem with SQL queries (after all, the temporary summary table solved the problem of the data structure), so I needed to approach this programmatically. The data structure immediately suggested by data 2 is an array of daily records, each of which has a dynamically-resized array of item records. If I were using a C-like language, I might use data structures like example 1 to solve this.
Example 1: The C Array
typedef struct item_rec
typedef struct day_rec
int date; /* an integer in yyymmdd format */
The Limitations of the Language
This realization was very good, except for the fact that I couldn't rewrite the program in C or C++ for this project1. As stated previously, there was no time to explore that option. The answer had to be reached, quickly, with the tools available. The simple solution was not an option because the PL/SQL limitations around complex data structures. PL/SQL simply does not support nested collections. The array of structures containing arrays would not work in PL/SQL.
I looked through my library of PL/SQL books for a hint on how to solve this problem, but no one had publicly tackled this problem. There was, however, a hint toward a possible solution in Programming PL/SQL (2nd Edition) [Feuerstein 1998]. Steve Feuerstein has noted and lamented this limitation of PL/SQL, and he presented a section on how fixed-size multi-dimensional arrays could be simulated. He presented this as a package allowing the developer to predefine (almost "allocate&8221;) an array of size r × c complete with accessor functions. Because the implementation is hidden in the body of the package, it looks and works much like a two-dimensional array in other languages.
The technique presented was to use a PL/SQL INDEX BY BINARY_INTEGER memory table and map the two-dimensional array to this single table. The position of an element at [m, n] in an array of r × c elements are found in the index-by table with the forumula:
i := ((m × (c − 1)) + n)
That is, in a 10 × 10 array, position [7, 3] is at position 66 [= ((7 × (10 − 1)) + 3)] in a single-dimensional array of size 100. Similar calculations could be used for more than two dimensions, but it only works when you have fixed-size dimensions. There are other limitations best explained by Mr Feuerstein in his book.
As noted earlier, the problem to be solved had an indeterminate number of columns (dates) and rows (data class entries per day), so this technique could not offer a solution. It did, however, offer some ideas on how more complex data structures might be emulated in PL/SQL.
The Shape of the Solution
Part of the problem that I faced when originally implementing this was that I was letting my knowledge of PL/SQL and its limitations dictate where I was willing to look for solutions. I knew that because I couldn't do nested arrays, I didn't look as closely as I should have at first. However, PL/SQL is a general-purpose language where one can define new data types, so it's simply a matter of needing to adapt to the limitations. To consider how I might do this, I considered alternative options in C-like languages, knowing that I could able to adapt the solution to PL/SQL.
Example 1 represents the data as it might be implemented in C. It's a single array (day_list) where each entry in that array is linked to another array (item_list). Because it needed to be a dynamically resizable array, I would probably implement it as item_rec *item_list, a pointer to an item. If I allocated memory in increments of sizeof(item_rec), then I could able to take advantage of C pointer arithmetic and treat the pointer as if it were an array -- making it an implicitly linked list.
Most people don't consier an array to be a linked list because it doesn't act like one. While most arrays or vectors are implemented as contiguous memory blocks, this is not necessarily the case. Any given vector class could be implemented as a contiguous memory block or a linked list and the programmer using that vector class should never know the difference. The linking relationship in an array is based on proximity, not on an explicit link. If I modified the item_rec definition to include an explicit link to the next item in the array, as in example 2, then the linked-list relationship becomes explicit, allowing me to consider the implementation of the solution from a different angle.
Example 2: The C Linked-List
typedef struct item_rec
typedef struct day_rec
int date; /* an integer in yyymmdd format */
Further analysis of the problem revealed that this particular problem did not need the biggest strength of arrays: random access to the records stored in an array. I only needed to access the records in date order and then in the order in which they appeared in the database, so sequential access was sufficient, making it very clear that a linked-list was most likely to lead to the "correct&8221; implementation. It does not, however, reach the solution, becuase PL/SQL only has automatic memory management and references are only allowed to SQL cursor variables (in Oracle8i). Since there is no way to allocate memory programmatically like one would with malloc or new, I needed a modified approach for PL/SQL.
As it happens, PL/SQL has three different collection types, and only one of them is an array in the traditional sense (the varying array, VARRAY). Varying arrays and object tables are the newest additions to the PL/SQL language and are present to support the Oracle8i object-relational extensions. Both data types are very useful, but they are Oracle8i-specific features and are not available in Oracle7; they also require more effort and planning to use than the normal PL/SQL index-by tables. Both varying arrays and object tables are close in interface to arrays in other languages (the developer is responsible for extending the array to add values to the end of the array, and the indexes are always created in order).
The third type of collection in PL/SQL, the index-by table, was my only option in Oracle7, but index-by tables are still probably the optimal choice for this sort of problem. Index-by tables are sparse tables indexed by a binary integer value. A sparse table is rather like a set or a Perl hash (using integer keys): only one value may exist at any given index. Unlike varying arrays and object tables, index-by tables automatically allocate the space required for the variables in the collection, more like a vector class than a C array. Index values may be non-contiguous (e.g., 1, 2, 5, 7). If the keys are created contiguously, they look and act in many ways like a C array, but otherwise they allow for smart indexing just as a set or hash allows.
Because index-by tables can be non-contiguous, PL/SQL provides alternate means for navigating them. There are four methods associated with index-by tables: FIRST, NEXT, PREV, and LAST. Using FIRST or LAST will provide the index of the first or last entry in the table, respectively. NEXT and PREV are called with a parameter (e.g., day_list.NEXT(day_idx)) of the index for which you wish to find the next (or previous) index value. If there is nothing in the table, FIRST and LAST will return NULL; if there is no record that exists after (before) the requested index, NEXT (PREV) will return NULL. One other interesting behaviour in a non-contiguous sparse table is that the index value provided as a parameter for NEXT or PREV does not need to represent a value that actually exists. In this way, I can have an index-by table that has values at [5, 10, 15, 20] and NEXT(7) will return 10. The possibilities for this are extensive and exciting.
Using NEXT and PREV with an index-by table makes it appear to work much like a doubly linked list, so if I consider the binary integer type as if it were a pointer, I can interweave several linked lists within a single contiguous vector.
By mapping the linked list from example 2 to a vector structure, I get something that looks like example 3 in PL/SQL. The first index-by table (day_list) contains an index reference to the head of its item list, which is an entry in the second index-by table (item_list). The item records have index references to the next item in its chain, with a NULL value representing the end of the chain for that particular entry. In this way, I'm using the random-access nature of array indexing to my advantage while sequentially winding my way through my linked-list imposed on top of the index-by table.
Example 3: The PL/SQL Linked-Array
TYPE day_rec IS RECORD
TYPE day_tab IS TABLE OF day_rec
INDEX BY BINARY_INTEGER;
TYPE item_rec IS RECORD
TYPE item_tab IS TABLE OF item_rec
INDEX BY BINARY_INTEGER;
The lists in question must be treated as an inseparable pair. The "real&8221; lists must be declared in one place and one place only. In Oracle7 or Oracle8, then it is in your best interest to declare these as private package global (not public package global, unless you want the users of your package messing with these values and possibly messing up your linked list). You can declare these in a function and pass them around as a pair to other functions that use them, but you must remember that if one of them is IN OUT the other must be IN OUT as well. It's not recommended that you do this for large data sets that are transformed in this way unless you're using Oracle8i and can use the NOCOPY keyword to pass these tables by reference between functions and procedures.
I have provided a sample implementation that reads a data value table (like table 1), parses the values according to the rules stated above (assuming a single data source) into the structures shown in example 3, and then writes the resulting data to a summary table (like table 2). In the real application for which this technique was used, the summary is kept only in memory while analysis is performed, and then only the results of the analysis are saved (in part because the summary is easily replicable). I have written the code such that a portion of the dates required can be returned in the summary table. The results are different if run for 2001-06-01--2001-06-05 and 2001-06-03--2001-06-04.
Listing 1 provides the specification for my package. I have only provided the one function as publicly visible because there is no need to expose the intimate operational details.
Listing 2 defines three different data types: data_value_tab, which is used exclusively for the storage of the incoming data in load_data; day_tab, which defines the daily list of values; and item_tab, which defines the list to which the linked list will be mapped. Special attention should be paid to how I use the index in day_tab later in the code: it illustrates the flexibility of the sparse index-by table.
I provide a simple wrapper procedure, pl, that wraps the Oracle built-in package DBMS_OUTPUT procedure PUT_LINE. This isn't absolutely required, and other debug mechanisms can be used as desired. Following pl, there are three more private functions that are called by the implementation of process_data: load_records, split_records, and save_records.
load_records reads the values from the DATA_VALUE table. Because I wanted this to be able to interpret partial values, I did not immediately start splitting the records into the data structures that I discovered solve the overall problem.
split_records is the meat of the program. After determining the number of data values, it gets the first and last date as Julian day values. This conversion is significant. It gives us the number of days between the two dates (last − first + 1) and the per diem amount (amount ÷ (last − first + 1). More importantly for the day_list, it gives us a smart index for use with our index-by. The index value represents the date on which the item_list will be used. Because we may get values out of date order or where there might be gaps in the date order that would be filled by division, it allows us to fill in the blanks as we need to, not as the code forces us to.
Thus, for each date in the duration of the data value, we check to see if it's in the requested boundaries. If it is, then we manage our item_list. If the date hasn't been added yet, we know that this partial value is going to be our first entry on the item_list and we process it as such. If we find that this date does exist, then we need to see if this particular type_code has already been added to the list -- and if it hasn't, we add the value to the end of the item_list and make the required links from the previous item in the list to the current item in the list. If the type_code already exists for the date in question, then we simply add onto the existing record. In this way, we obtain a structure in memory that looks substantially like example 3 and will allow us to produce the required summary data at will, though in a given order for the day or days in question. The key act of item creation is found here:
item_idx := NVL(item_list.LAST, 0) + 1;
From here, we get the last item that was created on the list (and if the list is empty, we get a NULL value that gets transformed to 0 by NVL) and add one to the item. In this way, we're adding to the item vector incrementally, but we're maintaining the relationship in the management of the prev_item and next_item values in the record we're dealing with.
Finally, save_records walks through the day_list records (which need not be contiguous, but in the sample data are contiguous) and then follows the item_list chain for each day, saving it to the database in the DATA_OUTPUT table. This table is the summary table that I noted would be prohibitive space-wise, and the number of records produced suggests this very clearly: ten output records are created in DATA_OUTPUT for four input records. This procedure demonstrates the navigation of both non-contiguous index-by tables and the linked list that I've placed on top of a contiguous index-by table.
This technique could be made more programmatic by writing it in a package -- encapsulating the functionality so that it appears to be an object --but each type of list would require its own package, because the details of the data can't be generalized (as PL/SQL has no template support) even though the techniques used in this article are highly portable.
It's difficult, sometimes, to think outside of the language that you're working with. Reaching beyond the limitations of the language I was using allowed me to quickly solve the problem at hand without undertaking a change in language that would have had a prohibitive cost in time and effort. With languages like Java and C++, the option to import techniques from other languages is easier because the languages are easily extended to handle new data structures with user-defined data types, but as long as a language supports a minimum set of features (user-definable types and arrays that can be composed of user-definable types), this particular implementation could be carried to any programming language at all.
One of the reasons I try to stay aware of the capability and use of several programming languages is so that I have a variety of ways of looking at a problem. Because of this tendency, I was able to identify the way that I might solve this problem with the limited time available for the project. I intend to use this experience to remind me of the necessity of constantly looking elsewhere for the ideas to solve the problems at hand -- and creatively applying the ideas that I find with the capabilities of the language of the problem at hand.
If you're not familiar with the PL/SQL programming language and would like to read further, I heartily recommend any book by Steve Feuerstein and published by O'Reilly. In particular, Programming in PL/SQL (2nd Edition) and Oracle Built-In Packages are extremely valuable. They also have pocket guides that summarise the main points of usage that are useful.