halostatue

software development with ruby in Toronto

• Home
• About
• flow

Complex Data Structures in PL/SQL
Sunday, 10 November 2002

Posted by austin in: Technology, trackback

In an ideal software development project, the development environment (that is, the languages, tools, and libraries) will be chosen that best suits the nature of the problem domain and the skills of the professionals involved. In the real world, the development environment is dictated by any number of constraints. The most common is that the project is a modification to or enhancement of an existing project. Just because one cannot – for whatever reason – use the language most suited to the solution does not mean that one can’t take lessons from those languages.

At one of my previous jobs, I worked on a project where the code was written in PL/SQL called by a C driver. 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. (Most of the time, however, this prejudice is present because the developers involved do not know the language itself.) 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. (If you aren’t familiar with PL/SQL, see the accompanying article.)

As useful as it is, PL/SQL is not without its limitations, mostly surrounding complex data structures. These limitations presented what seemed to be an insurmountable roadblock to the project, but the time-frame of this subproject did not allow for the language to be changed to one where the data structures required could be represented more ‘naturally.’

The subsystem in question 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. Table 1 shows how records for a five-day period might be present in the database. Figure 1 shows how these records could be considered on a timeline, which is how these values must be considered by the program.

Figure 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, it was 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. Table 2 shows how the data needs to be reorganized on a daily basis. Figure 2 shows the same information against a timeline. Compared against figure 1, the way that the records have been massaged becomes clear.

The easiest 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 table 2 and adds the resulting records to a daily summary table. This solution has three major problems with it:

1. 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).
2. 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.
3. 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.

Figure 2: Sample Data Converted into Daily Records

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 figure 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, which would produce an array like the one shown in figure 3.

typedef struct item_rec
{
  char    grouping[4];
  double  value;
} item_rec;

typedef struct day_rec
{
  int       date; /* an integer in yyymmdd format */
  item_rec* item_list;
} day_rec;

day_rec* day_list;

Figure 3: An array containing dynamically resized arrays

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 project¹. 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 (2^nd 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”) 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 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.

Figure 3 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. Figure 4 shows the modified structure graphically.

Figure 4: An array pointing to linked lists

typedef struct item_rec
{
  char              grouping[4];
  double            value;
  struct item_rec*  next;
} item_rec;

typedef struct day_rec
{
  int       date; /* an integer in yyymmdd format */
  item_rec* item_list;
} day_rec;

day_rec* day_list;

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” 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 figure 4 to a vector structure, I get something that looks like figure 5; example 3 gives the data structures (in PL/SQL) to implement it. 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.

Figure 5: The PL/SQL data structure – an array pointing to a linked list created from another sparse array.

The lists in question must be treated as an inseparable pair. The “real” 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.

The Solution

TYPE day_rec IS RECORD
    (day_date   DATE,
     item_head  BINARY_INTEGER);

TYPE day_tab IS TABLE OF day_rec
    INDEX BY BINARY_INTEGER;

TYPE item_rec IS RECORD
    (type_code  VARCHAR(3),
     amount     NUMBER,
     next_item  BINARY_INTEGER,
     prev_item  BINARY_INTEGER);

TYPE item_tab IS TABLE OF item_rec
    INDEX BY BINARY_INTEGER;

Source Listings

Listing 1: Data Split Package (data_split_pkg.sql)

-- Licensed under the Mozilla Public Licence 1.1

CREATE OR REPLACE PACKAGE data_split AS
  info_data_split_pkg CONSTANT VARCHAR2(120) := 'Version 1.0';

  PROCEDURE process_data
    (start_date IN  DATE DEFAULT SYSDATE,
     end_date   IN  DATE DEFAULT SYSDATE,
     debug      IN  BOOLEAN DEFAULT FALSE);
END data_split;

Listing 2: Data Split Package Body (data_split_pkg_body.sql)

-- Licensed under the Mozilla Public Licence 1.1

CREATE OR REPLACE PACKAGE BODY data_split AS
  info_data_split_body CONSTANT VARCHAR2(120) := 'Version 1.0';

  TYPE data_value_tab IS TABLE OF data_values%ROWTYPE
    INDEX BY BINARY_INTEGER;

  TYPE day_rec IS RECORD
    (day_date   DATE,
     item_head  BINARY_INTEGER);

  TYPE day_tab IS TABLE OF day_rec
    INDEX BY BINARY_INTEGER;

  TYPE item_rec IS RECORD
    (type_code  VARCHAR(3),
     amount     NUMBER,
     next_item  BINARY_INTEGER,
     prev_item  BINARY_INTEGER);

  TYPE item_tab IS TABLE OF item_rec
    INDEX BY BINARY_INTEGER;

  debug_on    BOOLEAN := FALSE;

  PROCEDURE pl(lo IN  VARCHAR) IS
  BEGIN
    IF (debug_on) THEN
      DBMS_OUTPUT.PUT_LINE(lo);
    END IF;
  END pl;

  -- This loads the records that started, ended, were contained in, or
  -- contained the specified start and end date. Split records will pull
  -- only the pieces we need.
  PROCEDURE load_records
    (date_start IN      DATE,
     date_end   IN      DATE,
     value_list IN OUT  data_value_tab) IS

    CURSOR get_values_cur
      (start_date_in  DATE,
       end_date_in    DATE) IS
      SELECT dv.type_code, TRUNC(dv.start_date) start_date,
             TRUNC(dv.end_date) end_date, dv.amount
        FROM data_values dv
       WHERE TRUNC(dv.start_date) BETWEEN start_date_in
                                      AND end_date_in
          OR start_date_in BETWEEN TRUNC(dv.start_date)
                               AND (dv.end_date)
          OR TRUNC(dv.end_date) BETWEEN start_date_in
                                    AND end_date_in
          OR end_date_in BETWEEN TRUNC(dv.start_date)
                             AND TRUNC(dv.end_date);

    value_idx   BINARY_INTEGER := 0;
  BEGIN
    -- Initialise the value list.
    value_list.DELETE;

    FOR gvlc IN get_values_cur(date_start, date_end)
    LOOP
      value_idx := value_idx + 1;
      value_list(value_idx) := gvlc;
      pl('#         : ' || value_idx);
      pl('type_code : ' || gvlc.type_code);
      pl('dates     : ' || gvlc.start_date ||
            ' − ' || gvlc.end_date);
      pl('amount    : ' || gvlc.amount);
    END LOOP;
  END load_records;

  PROCEDURE split_records
    (start_date IN     DATE,
     end_date   IN     DATE,
     value_list IN     data_value_tab,
     day_list   IN OUT day_tab,
     item_list  IN OUT item_tab) IS

    value_idx       BINARY_INTEGER;
    item_idx        BINARY_INTEGER := 0;

    prev_idx        BINARY_INTEGER;
    link_idx        BINARY_INTEGER;

    rec_days        PLS_INTEGER;
    rec_days_amt    NUMBER;
    first_jul_day   BINARY_INTEGER;
    last_jul_day    BINARY_INTEGER;
    test_date       DATE;

  BEGIN
    -- Initialise values
    day_list.DELETE;
    item_list.DELETE;

    pl('# of values: ' || value_list.COUNT);
    value_idx := value_list.FIRST;

    WHILE (value_idx IS NOT NULL)
    LOOP
      pl('Processing Value Record: ' || value_idx);

      -- Get the first day and last day in Julian terms.
      first_jul_day := TO_NUMBER(TO_CHAR(value_list(value_idx).start_date,
        'J'));
      last_jul_day := TO_NUMBER(TO_CHAR(value_list(value_idx).end_date,
        'J'));

      -- Figure out the amount per day.
      rec_days_amt := value_list(value_idx).amount /
        (last_jul_day − first_jul_day + 1);

      pl('Value Record ' || value_list(value_idx).type_code ||
         ' [' || first_jul_day || ' − ' || last_jul_day ||
         ': ' || rec_days_amt || ' per day]');

      FOR jul_idx IN first_jul_day .. last_jul_day
      LOOP
        pl('Julian: ' || jul_idx);
        test_date := TO_DATE(TO_CHAR(jul_idx), 'J');

        -- Make sure that we're within the boundaries.
        IF (    (test_date >= start_date)
            AND (test_date <= end_date)) THEN
          pl('In Date Boundaries');

          -- If we are, start applying the amount per day.
          IF (day_list.EXISTS(jul_idx)) THEN
            -- We've found a list already extant at the
            -- current date. Reuse it.
            pl('Day exists.');
            item_idx := day_list(jul_idx).item_head;
            prev_idx := NULL;
            link_idx := NULL;

            -- Look for our type_code.
            WHILE (item_idx IS NOT NULL)
            LOOP
              IF (item_list(item_idx).type_code =
                  value_list(value_idx).type_code) THEN
                -- Found a matching record.
                link_idx := item_idx;
                item_idx := NULL;
                pl('Matching record found at ' || item_idx);
              ELSE
                prev_idx := item_idx;
                item_idx := item_list(prev_idx).next_item;
              END IF;
            END LOOP;

            -- No such type_code, add a new record.
            IF (link_idx IS NULL) THEN
              item_idx := NVL(item_list. LAST, 0) + 1;
              item_list(item_idx).type_code :=
                value_list(value_idx).type_code;
              item_list(item_idx).amount := rec_days_amt;
              item_list(item_idx).prev_item := prev_idx;
              item_list(item_idx).next_item := NULL;
              item_list(prev_idx).next_item := item_idx;
              pl('New record added.');
            ELSE -- We have a match: increase it by the daily amount.
              item_list(link_idx).amount :=
                item_list(link_idx).amount + rec_days_amt;
              pl('Existing record increased.');
            END IF;
          ELSE -- No charges yet at this date.
            item_idx := NVL(item_list. LAST, 0) + 1;
            day_list(jul_idx).day_date := test_date;
            day_list(jul_idx).item_head := item_idx;
            item_list(item_idx).type_code :=
              value_list(value_idx).type_code;
            item_list(item_idx).amount := rec_days_amt;
            item_list(item_idx).prev_item := NULL;
            item_list(item_idx).next_item := NULL;
            pl('New date and record added.');
          END IF;
        END IF;
      END LOOP;

      value_idx := value_list.NEXT(value_idx);
    END LOOP;
    pl('# of days : ' || day_list.COUNT);
    pl('# of items: ' || item_list.COUNT);
  END split_records;

  PROCEDURE save_records
    (day_list   IN day_tab,
     item_list  IN item_tab) IS

    day_idx     BINARY_INTEGER;
    item_idx    BINARY_INTEGER;

  BEGIN
    pl('# of days : ' || day_list.COUNT);
    pl('# of items: ' || item_list.COUNT);
    day_idx := day_list.FIRST;

    WHILE (day_idx IS NOT NULL)
    LOOP
      pl('Processing day [' || day_idx || ', ' ||
         TO_CHAR(TO_DATE(day_idx, 'J'), 'YYYY-MM-DD') ||
         '].');
      item_idx := day_list(day_idx).item_head;
      WHILE (item_idx IS NOT NULL)
      LOOP
        pl('Item [' || item_idx || ']: [' ||
           item_list(item_idx).type_code || ': ' ||
           item_list(item_idx).amount || ']');

        INSERT
          INTO data_output(data_date, type_code, amount)
        VALUES (day_list(day_idx).day_date,
                item_list(item_idx).type_code,
                item_list(item_idx).amount);

        item_idx := item_list(item_idx).next_item;
      END LOOP;

      day_idx := day_list.NEXT(day_idx);
    END LOOP;
  END save_records;

  PROCEDURE process_data
    (start_date IN  DATE DEFAULT SYSDATE,
     end_date   IN  DATE DEFAULT SYSDATE,
     debug      IN  BOOLEAN DEFAULT FALSE) IS

    v_list  data_value_tab;
    d_list  day_tab;
    i_list  item_tab;

  BEGIN
    debug_on := debug;
    pl('Start : ' || start_date);
    pl('Stop  : ' || end_date);
    load_records(start_date, end_date, v_list);
    split_records(start_date, end_date, v_list, d_list, i_list);
    save_records(d_list, i_list);
  END process_data;
END data_split;

Listing 3: Schema (data_split_tables.sql)

-- Licensed under the Mozilla Public Licence 1.1
CREATE TABLE data_values
  (type_code  CHAR(3) CONSTRAINT nn_data_values_tc NOT NULL,
   start_date DATE    DEFAULT SYSDATE CONSTRAINT nn_data_values_sd NOT NULL,
   end_date   DATE    DEFAULT SYSDATE CONSTRAINT nn_data_values_ed NOT NULL,
   amount     NUMBER  DEFAULT 0 CONSTRAINT nn_data_values_am NOT NULL,
   PRIMARY KEY pk_data_values (type_code, start_date, end_date));

CREATE TABLE data_output
  (data_date  DATE    DEFAULT SYSDATE CONSTRAINT nn_data_output_dd NOT NULL,
   type_code  CHAR(3) CONSTRAINT nn_data_output_do NOT NULL,
   amount     NUMBER  DEFAULT 0 CONSTRAINT nn_data_output_am NOT NULL,
   PRIMARY KEY pk_data_output (data_date, type_code));

ALTER SESSION SET NLS_DATE_FORMAT = 'yyyymmdd';

INSERT
  INTO data_values(type_code, start_date, end_date, amount)
VALUES ('ABC', '20010601', '20010601', 1);

INSERT
  INTO data_values(type_code, start_date, end_date, amount)
VALUES ('DEF', '20010601', '20010605', 15);

INSERT
  INTO data_values(type_code, start_date, end_date, amount)
VALUES ('ABC', '20010601', '20010603', 3);

INSERT
  INTO data_values(type_code, start_date, end_date, amount)
VALUES ('GHI', '20010602', '20010603', 10);

COMMIT;

Listing 4: Data (test_data_split.sql)

-- Licensed under the Mozilla Public Licence 1.1
BEGIN
  DELETE
    FROM data_output;

  data_split.process_data(TO_DATE('20010601', 'yyyymmdd'), TO_DATE('20010605', 'yyyymmdd'), TRUE);
  data_split.process_data(TO_DATE('20010601', 'yyyymmdd'), TO_DATE('20010603', 'yyyymmdd'));

  COMMIT;
EXCEPTION
  WHEN OTHERS THEN
    DBMS_OUTPUT.PUT_LINE('CODE: ' || SQLCODE);
    DBMS_OUTPUT.PUT_LINE('MSG : ' || SQLERRM);
END;

SELECT *
  FROM data_output
 ORDER BY type_code;

• Categories

  • Apple
    • iPhone
  • HaloStatue
  • Humor
  • Personal
    • Recipes
  • Politics
  • Ruby
    • Archive
    • Ruby PDF
    • RubyConf
    • Ruwiki
    • TRUG
  • Technology
  • Toronto
  • Twitter

• Archives

  Select Month April 2009  (2) March 2009  (2) January 2009  (1) November 2008  (1) September 2008  (2) August 2008  (1) July 2008  (1) June 2008  (1) March 2008  (3) December 2007  (2) November 2007  (7) October 2007  (11) September 2007  (4) August 2007  (2) April 2007  (2) March 2007  (1) February 2007  (2) November 2006  (1) October 2006  (7) September 2006  (5) August 2006  (3) July 2006  (3) June 2006  (2) May 2006  (3) April 2006  (1) January 2006  (1) October 2004  (2) September 2004  (3) May 2003  (1) February 2003  (1) November 2002  (2)

• 

• Meta

  • Log in
  • Entries RSS
  • Comments RSS
  • WordPress.org

• Feeds

• Full
• Comments