duick.com Advantage Gen / COOL:Gen Index

Historical overview

Paging through lists of data is a time-honored tradition in the Information Technology world and over time, many methods for accomplishing this paging have been used. While paging forward is relatively simple, paging backwards has always been a bit more involved.

One paging technique reads the database from beginning to end and stores the key for the first item on each page in a separate repeating group. It then uses those keys to rebuild each page when paging backwards. Variations include algorithms to handle cases such as an item being added to the list since the page was first built and its key stored. These tend to be very complex and difficult to maintain.

Another technique decrements the starting value for the read each until the proper number of records to fill the page are returned. If the result isn’t correct (the read went too far back or not far enough) the starting value is decremented again and the process starts over.

Time for a change

These techniques have two things in common - they are complex and they do not fully address the needs of a dynamic environment - one in which items can added or deleted at will. With the power of the latest hardware and software, especially database engines, it is time to find a simpler and more universal way to page through information. The basic requirements are:

Start at any point in the data store.
Page backward or forward to the end of the database without asking the user to enter a new starting value.
Automatically adjust for additions and deletions performed by other transactions.
Have minimal overhead, both for database access and for program construction and maintenance.
Work in both block mode and GUI (Graphical User Interface) environments.
Be scaleable to work in any situation, simple enough to provide a good answer for small tables and robust enough to work with very large tables

A new way to page

As noted in the introduction, paging forward has always been simple. The standard method for a READ EACH NEXT module, expressed in IEF style pseudo-code, looks like this:

Set subscript of repeating_group to 0
(one less than the start of the page)
= READ EACH entity
\| SORTED BY ascending key
\|		(sort going up)
\| WHERE entity key greater than key of last item on current page
\|	(start the next page at the next higher item)
\| Set subscript of repeating_group to subscript of repeating_group + 1
\|	(point to the next higher position on the page)
\|-- If subscript of repeating_group \| greater than MAX of repeating_group
\| \|	(there are more items than will fit on the page - set an indicator and get out of the read loop)
\| \|
\| \| Set export plus_flag to ‘+’
<-- Escape
\|--
\|
\| Move entity to export repeating_group entity
=

Notice that one more item is read than will fit in the list. This enables the ‘More data’ indicator or control, whatever it might be, from a ‘+’ on a 3270 block mode screen to the ‘more data’ button on the AOL browser on the Internet. An explicit subscript is used since the implicit method only allows a READ_EACH until the repeating group is full, and to have this control we need to read one beyond full.

Since this works so well for paging forward, what happens if we turn it upside-down and try paging backwards? In other words, read backwards (sort descending) and fill the page from the bottom to the top. Let’s have a look - here is the code for the READ EACH PREVIOUS module:

Set subscript of repeating_group to MAX of repeating_group + 1
(one more than the end of the page - we are starting at the bottom)
= READ EACH entity
\| SORTED BY descending key
\|		(sort going down)
\| WHERE entity key less than key of the first item on current page
\|	(start the next page at the next lower item)
\| Set subscript of repeating_group to subscript of repeating_group - 1
\|	(point to the next lower position on the page)
\| -- If subscript of repeating_group less than 1
\| \|	(there are more items than will fit on the page - set an indicator and get out of the read loop)
\| \|
\| \| Set export minus_flag to ‘-’
<-- Escape
\|--
\|
\| Move entity to export repeating_group entity
=

Now let’s try ‘playing computer’ with the code. Assume a database with a very simple index - a single number and the following entries:

Let’s further assume a window/screen that displays 5 entries and that it is currently displaying items 070 through 110. If the page back button is pressed the sequence of events is:

It looks like the code works in this specific case, but what happens if we start with record 020? Record 020 would go on line 5, Record 010 would go on line 4 and then we would be out of records before we were out of lines.

There actually are a few situations where this would be desirable behavior, but in most cases the user would want to have record 010 on line 1 and the rest following in order.

The easiest way to cause that to happen is to add a use statement to call the READ EACH NEXT action block. It will start at the beginning of the database (Record 010), read the rest in order and place them starting on the first line to the end of the screen.

The use statement can be triggered by the subscript. If it is not less than 2, the view was not filled and the READ EACH NEXT action block should be called.

It may be counter-intuitive, but DB/2 and other relational databases don’t really care whether they are asked to sort ascending or descending, especially on indexes. The sort overhead only applies to the number of records returned to fill the repeating group and that is usually fewer than 20-25.

If, however, you are working in an IMS or other non-relational environment and are reading forward on a primary key (identifier), you will need to add a "9’s complement" index to read backwards as efficiently as forward. Creating a "9’s complement" index is just a matter of subtracting the real key from high-values and storing the result in the "descending index" when creating a record.

There is a third component needed, in addition to the READ EACH NEXT and READ EACH PREVIOUS components previously described. It is the READ EACH STARTING AT component and it is identical to the READ EACH NEXT module with two exceptions.

The first is that the read qualifier needs to say greater than or equal to in order to start with a specified key. This is used for both user entered starting values or values selected from a list.

The second is that the READ EACH STARTING AT component has to support the ‘More previous’ control. Since the module could be started at any point in the database, it must look for any record with a lower index than the starting value. If one is found, the ‘More previous’ flag is set or the page back button is enabled.

These three components, taken together, form the Universal Paging Algorithm (UPA). When used together as described, they will simplify the original construction and the on-going maintenance of any system that delivers lists of sorted data to users. As always, we are anxious to hear about your experiences and discoveries in the application of this algorithm.