Restartable method to reorganize DB2 tablespace records by determining new physical positions for the records prior to moving using a non sorting technic

An improved method to dramatically reduce the time required to reorganize DB2 tablespaces and index files by not utilizing conventional sort techniques. Viewing access is allowed during the reorganization process by setting the files to read only status. The process is basically non-destructive, allowing a prompt return to the original state, and is checkpointed, allowing restarting at selected intervals. Briefly, the original table and indices are considered as A files and read into memory. New row IDs or RIDs are developed using a non-sorting technique so that the proper order of the data is developed. After the new RIDs have been developed, both the clustering index and the row data are read out of memory and written to a new table and clustering index files in the proper order as B files. Then any remaining non-clustering indices are reorganized using non-sorting techniques in a similar fashion.

BACKGROUND OF THE INVENTION 
1. Field of the Invention 
The invention relates to reorganizing database data and index files, 
particularly DB2 tablespaces, into key order without utilizing 
conventional sorting procedures, while allowing the tablespaces to be 
viewed during reorganization and allowing prompt recovery or restarting of 
the process if interrupted before completion. 
2. Description of the Related Art 
Databases are used on computers for a myriad of reasons. In many cases the 
databases are extremely large, having entries in the millions. When 
databases reach this size, and the information is needed in a 
transactional or real time basis, mainframe computers are utilized. 
International Business Machines Corp. (IBM) has developed a database 
environment referred to as DB2 for use on its mainframes. Given IBM`s high 
market percentage in mainframes, DB2 is clearly the leading database 
system. 
A tablespace is the DB2 term used to identify a database. Tablespaces can 
be simple, segmented or partitioned. In a simple tablespace, the data is 
kept in one file and there may be a clustering index and other indices. A 
clustering index is the index where the keys are kept in sequential order 
and the data is preferably kept in this same order. In a segmented 
tablespace, many different logical data files or tables are kept in a 
single file and there may be a clustering index and other indices for each 
logical data file. There are no indices directed to multiple logical 
files. In a partitioned tablespace, the data is kept in different files, 
but there is a clustering index for each file. There may be additional 
indices directed to all of the partitions. 
DB2 uses a balanced tree index structure. In this structure, root, tree and 
leaf pages are used, with each page at each level containing the same 
number of entries, except of course the last one. The leaf pages are the 
lowest level and each contains a number of entries referring to the actual 
data records contained in the DB2 data tables. Each leaf page is 
maintained in internal logical order automatically by DB2. Tree pages are 
the next level up, and are used to indicate the logical order of the leaf 
pages. For large databases, there may be many several layers of tree 
pages, a higher level of tree pages referencing a lower level of tree 
pages. Ultimately the number of tree pages is reduced such that all the 
entries or references fit into a single page referred to as the root page. 
As in leaf pages, within each tree or root page the entries are kept in 
logical order by DB2. 
The data tables or files are organized into pages. The first page of each 
table is a header page. The second page and certain pages thereafter are 
referred to as space map pages. The header page contains information 
relating to the entire table while the space map pages include information 
relevant to free space in a following number of data pages. The actual 
frequency of the space map pages is based on tablespace characteristics 
and is well known. The remaining pages are data pages. Up to 255 rows or 
records of data may be present in a single page. The actual number of rows 
depends on the size of the row and the size of the page. Each row receives 
a unique identifier, referred to as the RID, which identifies the page 
number and relative row number in that page. 
One problem with any database is that the physical location of the various 
pages often becomes quite scattered. This is true for the data pages in 
the tables and the leaf pages in the indices. A disorganization also 
develops between the clustering index and the data, so that the table data 
is no longer physically in its intended logical order. This scattering 
results in reduced performance as now the storage device must move between 
widely scattered physical locations if logically sequential operations are 
to be performed. This is true of whatever type of Direct Access Storage 
Device (DASD) is used to store the file. Therefore the files need to be 
reorganized periodically so that the logical and physical ordering of the 
pages better correspond, thereby improving performance of operations. 
IBM provides utilities with DB2 to reorganize the entire tablespace and 
just the index files. Several other third-party DB2 utility providers also 
have tablespace and index reorganization packages. These packages usually 
operate in the same manner. First, the entire file, either tablespace or 
index, is read in physical order. Each page in the file is then separated 
into its component record entries. Next, the record entries are sorted by 
key value using a conventional sort package. Finally, the sorted records 
are rewritten back into the file. While this process may sound simple, it 
must be understood that quite often there are hundreds of thousands to 
millions of entries in the file. When this number of entries is 
considered, then the process becomes quite time consuming, particularly 
the sorting step. The third party packages are faster than IBM's utility, 
but primarily because the sort packages used are more efficient and also 
because they use standard available sort package facilities, such as sort 
exits to reduce intermediate file I/O. So even in those cases the process 
is quite tedious and is done less frequently than desirable, so overall 
database performance suffers. Therefore it is desirable to have a 
significantly faster DB2 table and index reorganization method, so that 
the tables and indices can be reorganized more frequently and overall 
operations made more efficient. 
Additionally, because the reorganization procedures often take large 
amounts of time, it would be desirable to access the files for viewing 
purposes, if not for updating purposes, during the reorganization. 
Further, should for some reason the process be stopped before completion, 
it would be desirable to have several alternatives to become fully 
operational without redoing the entire process. 
SUMMARY OF THE INVENTION 
The present invention relates to an improved method to dramatically reduce 
the time required to reorganize tablespaces and index files, particularly 
those as used by DB2. Additionally, the operations allow viewing access 
during the reorganization process; are non-destructive, allowing a prompt 
return to the original state; and are checkpointed, allowing restarting at 
selected intervals to avoid having to completely restart the process. 
Briefly, the process is started by flushing any pending operations and 
setting all of the files in the tablespace to read only status. By using 
read only status, viewing access is allowed during the reorganization 
process. The first clustering index of the tablespace is then determined 
and the tablespace reordering and clustering index reorganization sequence 
is started. The original table and indices are considered as A files and 
read into memory. New row IDs or RIDs are developed as described below so 
that the order of the data is developed. After the new RIDs have been 
developed, both the clustering index and the row data are read out of 
memory and written to a new table and clustering index files in the proper 
order as B files. After the completion of writing the B files, checkpoints 
are placed to indicate sequencing of events. 
If the tablespace is partitioned and there are any certain non-clustering, 
non-partitioned indices, then a series of AMS statements are developed and 
executed which rename all of these A or original files to C or temporary 
files as soon as the first reorganization of any single partition is 
completed. This is done as the indices will now be unusable because the 
references will no longer be correct. These AMS statements are then 
executed and checkpointed. Next, all files which need to be renamed are 
determined and written to a list. All of the table files are then stopped 
to allow exclusive access. Next, a series of AMS statements are built to 
do the renaming operations. Specifically, a series of statements are built 
to rename all of the A or original files to X or old files. Then a series 
of statements are developed renaming all B or new files to A files. 
Finally, a series of statements are made deleting all of the X files, thus 
effectively completing the task. After these statements have been 
developed they are executed and after execution, all checkpoints for the 
partition are removed. If there are any more partitions remaining, then 
control returns to the tablespace reordering and clustering index 
reorganization sequence to proceed with the next partition. This loop 
continues until all partitions have been processed. Thus, by use of the 
original and new files, the original can remain in a read only state until 
the new file process is complete. This allows viewing during almost the 
entire reorganization process and the process can be returned to the 
original state if possible or can be restarted from approximately where it 
was halted. 
If the tablespace is not partitioned or after all partitions have had their 
tables reordered and clustering indices reorganized, then any remaining 
non-clustering indices are reorganized. This sequence is described in 
detail in the detailed description. Simply, again the original files are 
read into memory and the new files as they are written out are written 
into B files. In this manner the original A or C files are always 
remaining until after the development of the new files. After the new 
files have been developed, the files are renamed as described above. 
The restarting process reviews the various check points and presence of the 
various A, C, X or B files and based on the checkpoint status and the 
presence of the various files, properly proceeds from the interrupted 
portion onward. 
The tables and clustering indices are reordered in a different manner then 
the non-clustering indices. The non-clustering indices will be described 
first. 
As a first general operation, the logical order of the leaf pages is 
determined by accessing the index tree. A buffer is used to receive the 
physical page number of the leaf pages in logical order. This buffer is 
then transposed into a physical order buffer, with the logical order value 
associated with the physical order value. After this, a large buffer is 
set aside in memory to receive a copy of all the leaf pages in the index 
file. The index file is then read in a sequential operation. As each 
physical page is read, the transposed or physical order buffer is accessed 
to find the proper logical page. If a leaf page has just been read, it is 
then placed in the large buffer in its logical position. When the entire 
index file is read and the leaf pages written to the large buffer, the 
large buffer is in a reorganized logical order. These leaf pages are then 
sequentially written to the new or B index file, referencing a buffer 
containing a translation between the old and new RID values so that the 
new RID values are written into the index, with the tree pages 
interspersed as they are filled. When the write operations are completed, 
the B or new index file replaces the A or old index file as described 
above. 
Preferably the writing of the B index file can occur concurrently with the 
filling of the large buffer. As the beginning of the buffer becomes 
filled, the beginning entries can be written to the new index file, so 
that the write process is effectively racing the read and fill processes. 
If the index is not badly scattered, the concurrence can further reduce 
the total required time of the reorganization process. 
As noted, table and clustering index reorganization proceeds somewhat 
differently. If a simple tablespace, a segmented tablespace having just a 
single table or a partitioned tablespace, then the clustering index for 
the particular table or partition is first reorganized basically as 
discussed above. Then a second or TSRID2 buffer is set up in order of the 
new index that has columns for the old RID and the new RID values. As the 
data is read sequentially from clustering index buffer, the old RID value 
is written to the old RID column of the TSRID2 buffer and the row numbers 
are monitored to determine the maximum row number. Then another buffer, 
the TSRID1 buffer, is developed having a number of slots equal to the 
number of pages times the maximum row number. Finally, a table buffer is 
set up having an area to receive the actual data in a compressed format. 
The table data is then read into this table buffer in sequential order, 
skipping any empty pages and saving the data. The length for each row is 
transferred to the proper slot in the TSRID1 buffer. A pointer is then 
placed at the beginning of the TSRID2 buffer, which is then read 
sequentially to obtain the old RID value which is used to calculate a slot 
in the TSRID1 buffer, and the row length is obtained. If an overflow RID 
is indicated, the actual row length is obtained using the overflow RID 
value. With the row length obtained, new RID values can be sequentially 
assigned from the beginning of the table and placed in both the TSRID1 and 
TSRID2 buffers. Header and space map pages are developed as necessary in a 
separate area in the table buffer as the necessary information is 
available. This process is continues through the entire TSRID2 buffer. The 
TSRID1 data space is then written to a file and checkpointed for recovery 
or restart reasons. The clustering index as reorganized is then written to 
a B file, effectively using the writing steps defined above. Then the 
table B file is opened for sequential operations and the header page and 
first space map page are written. Then using the TSRID2 data space in 
sequential order as an ordering element, the old RID value is used to 
reference the actual page data from the table buffer, which is then 
written in this order, along with the new RID numbers as stored in the 
TSRID2 buffer. The space map pages are written as necessary. After this 
process has been completed, sequential access to the table B file is 
closed and completion of the table B write operation is indicated. 
Segmented files proceed slightly differently, in that first a TSRID3 buffer 
having a column to receive the row length and two additional slots for 
each page is set up. The table buffer having areas for the row data and 
header and space map pages is also setup. Further, cell range lists are 
setup for each table. The table data is then read into the table buffer in 
physical order. Additionally, the row length is placed in the TSRID3 
buffer at the same time, with the row count for each page being placed in 
the page slots. Additionally, the cell range lists are maintained for each 
separate table in the segmented tablespace. If there is no clustering 
index, reference is simply made to the cell range lists and the page 
lengths from the TSRID3 buffer, new RID values are assigned and replace 
the length value in the TSRID3 buffer, with space map pages being built as 
appropriate. The table data is then saved in a FIFO queue. This process is 
repeated for each table. 
If the table has a clustering index, then the index is then reorganized as 
above, the TSRID2 buffer being filled to obtain the old and new RID 
values. Proceeding sequentially through the TSRID2 buffer, the page length 
is obtained from the TSRID3 data space, with new RID values then being 
assigned and placed in the TSRID2 buffer, with space map pages being 
developed as appropriate. Again the table is saved in a FIFO queue for 
writing. Finally, after this step is completed, the clustering index is 
written out, with translation of the RIDs occurring as described above. 
This process also repeats until all tables have been completed. 
Once the last table is completed, the table B file is opened for sequential 
operation and the header and first space map pages are written. Then the 
row data is written out in sequential order using either the TSRID3 
buffer, if it is not an indexed table, or using the TSRID2 buffer to 
determine the old RID and new RID numbers. After all the data values have 
been retrieved from memory and written to the table B files for all 
tables, sequential access is closed and a checkpoint is completed. 
Therefore the reorganization is also performed without a conventional 
sorting process, greatly speeding up operations.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT 
Referring now to FIGS. 1A and 1B, a tablespace reorganization sequence 300 
according to the present invention is illustrated. The tablespace 
reorganization sequence 300 commences at step 302, where all the various 
buffers in the computer relating to the tablespace are flushed so that 
there are no pending operations, particularly write operations, to the 
tablespace. Control proceeds to step 304, where all of the files in the 
original tablespace are set as read only. This read only status allows 
viewing access to the tablespace but does not allow updates as that would 
interfere with the reorganization process. However, by making the 
tablespace read only, at least viewing rights are provided so that 
complete blocking of the tablespace is not necessary and some operations 
can be performed. Control then proceeds to step 306, where the first 
clustering index of the tablespace is read. There may be tablespaces where 
no clustering indexes are used, but that is a very simple case and is not 
addressed in this description. Control proceeds to step 308, where a 
tablespace reorder and clustering index reorganization sequence 400a, 400b 
is commenced. This sequence will be described in summary shortly below as 
sequence 400a and in great detail further below as sequence 400b. 
After the sequence 400a, 400b has been started, control proceeds to step 
310 to determine if this is a partitioned tablespace. If so, control 
proceeds step 312 to determine if there are any non-clustering, 
multi-partition indices, that is, any indices directed not to a single 
partition but rather to all of the partitions. If so, control proceeds to 
step 314 to determine if this branch has been previously taken. If not, 
control proceeds to step 316, where a series of AMS statements for 
renaming the indices are built. Specifically, the indices are to be 
renamed from what are referred to as the A or original files to C or 
temporary files. This must be done at this time because after the first 
table reorder is commenced, the non-clustering, multi-partition indices 
will no longer be proper and therefore can not be utilized, even for just 
view access. After the AMS statements have been built, control proceeds to 
step 318 where a checkpoint is written to a checkpoint file to indicate 
that the A to C rename execution has started. An INCONSISTENT STATE flag 
is also set in the checkpoint file for later use. Control then proceeds to 
step 320, where the AMS statements are started. 
Control proceeds from step 320 or from step 312 if there are no 
non-clustering, multi-partition indices or step 314 if the process has 
previously been performed, to step 326, where a list of files relating to 
the particular partition or table is written to a file referred to as the 
rename member list. This is the list of files relating to the particular 
table, such as the clustering index and other partition or segment 
indices, that need to be renamed as part of the process. Control proceeds 
to step 328 where a checkpoint is written to indicate starting of the 
renaming phase. Control proceeds to step 330, where all of the tables and 
indices are stopped so that exclusive access is granted for the renaming 
steps. This is necessary because when renaming is operating, even viewing 
access must be disabled. However, the steps are relative quick and 
therefore this is not considered to a major burden, with view access 
provided for the predominant portion of the entire process. Control 
proceeds to step 332, where a series of AMS statements are built. The 
first series of statements renames all of the A files, i.e. the original 
files, to X files. Then there are a series of AMS statements relating to 
conditional testing to determine if there were any failures during the 
renaming operation of A to X. If so, the tests cause aborting of the 
operation. The next series of statements that are built relate to renaming 
all of the B files, i.e. all of the newly created files developed by the 
reordering and reorganization sequences, to A files. i.e. to the names of 
the original files. Next is a series of conditional test statements to 
determine if there were any failures during the proceeding renaming 
operations and causing aborting if so. The final series of AMS statements 
built are those that delete of all X files. 
Control then proceeds to step 334 where the AMS statement file is started. 
During operation of the process started at step 334 all of the original 
files will have been named to temporary X files, all of the new files will 
be named to the A files and then all of the temporary X files will be 
deleted. By the completion of the process, all of the original files will 
be completely replaced with all of the new, reordered sequential files. 
Control then proceeds to step 336, where the appropriate checkpoints are 
removed from the checkpoint file so that should operations have to be 
restarted, as described below, there is no indication that this process is 
not fully completed. Further, a flag called the STEP.sub.-- MUST.sub.-- 
COMPLETE flag is set in the checkpoint file, as once the process of step 
334 has started, all of the operations must complete. Control then 
proceeds to step 322 to determine if the last partition has been finished. 
If not, then control proceeds to step 324, where the next clustering index 
for the tablespace is read. Control then proceeds to step 308 where the 
tablespace reorder and clustering index reorganization is started for that 
particular partition. 
If this was not a partitioned tablespace as determined in step 310 or the 
last partition had been finished as determined in step 322, control 
proceeds to step 340. In step 340 the index reorganization sequence 100 is 
started for each of the remaining non-clustering indices, including any 
non-clustering, multi-partition indices. Control then proceeds to step 342 
where the checkpoint file is read to determine the files that have to be 
renamed and these are placed in a rename member list for each index. 
Control proceeds to step 344, where starting of the renaming phase is 
written to the checkpoint file to allow later restarting. Control proceeds 
to step 346, where all of the tables and indices are stopped to allow 
exclusive access. Control proceeds to step 348, where a series of AMS 
statements similar to those in step 332 are developed. Control proceeds to 
step 350, where the AMS statements built in step 348 are started. Control 
then proceeds to step 352, where once again the checkpoints are removed 
from the checkpoint file and the STEP.sub.-- MUST.sub.-- COMPLETE flag is 
set. Control then proceeds to step 354, which indicates that the task is 
completed. 
A simplified version of the table reorder sequence 400a is shown in FIG. 2. 
A simplified version is used here for illustrative purposes, with more 
detail provided below in the description of sequence 400b. In step 402 the 
tablespace, that is the data, is defined to be data set A and is read into 
the memory of the computer. There are various steps in step 404 which then 
logically assign new record IDs or RIDs to each of the rows of the 
tablespace data which have been read. In step 406 in this simplified 
format a table referred to as TSRID1 buffer for the clustering index which 
is being reordered is built. This is a table which is in indexed order and 
will include the new RID value for each row of data. When the buffer has 
been completed, it is written to disk for later use. Control proceeds to 
step 408, where a checkpoint is written, indicating completion of the 
TSRID1 buffer development operation. After this is done, the tablespace 
data is written out in step 410 in its new order as data set B. Control 
then proceeds to step 412 where a checkpoint is written to indicate 
completion of the data set B operation. Step 412 is a return or complete 
operation. The various steps of this sequence 400a are actually more 
detailed but are provided in this simplified version to show that the 
original data space is read in from the original or A file and is written 
out as a new B data set to allow the restarting operations as will be 
described below. 
The restart tablespace reorg sequence 500 is shown in FIGS. 3A, 3B and 3C. 
The sequence 500 is utilized in case the tablespace reorganization 
operations do not complete once they have been started. This is not an 
unusual event because of the great length and complexity of the various 
tablespaces. Because of the millions of records which may be in a 
tablespace, even given the speed of the technique according to the present 
invention, it still a multi-hour process in many cases and thus numerous 
events can occur which could cause the sequences to stop prior to 
completion. Once operation has stopped before completion, it is desirable 
to be able to go back and restart the process, either by recovering and 
going back as quickly as possible to operational status or by restarting 
the process from approximately the failure point so that prior efforts do 
not have to be completely duplicated. 
The sequence 500 commences operation at step 502 to determine if the rename 
sequence for each of the indices had been started. This is done by 
reviewing the checkpoint file. As noted above, once a particular index or 
table has been finished, the checkpoints are deleted from the checkpoint 
file so that only tables or indices which are interrupted during execution 
will have checkpoint entries. If the rename start has been checkpointed, 
control proceeds to step 504, where the rename member list is read and a 
pointer set to the beginning. Control then proceeds to step 506 to 
determine if there had been a prior restart or recover. Again it is quite 
possible that the restart procedure itself could be terminated abnormally, 
which may result in different operations upon a second or repetitive 
restart. If there was no prior restart or recover, control proceeds to 
step 508 to determine if the restart or the recover option has been 
selected. Generally a recover operation is one deemed to request getting 
the system fully operational as quickly as possible, while a restart 
operation is one requesting to restart the terminated operation and 
complete the reorganization. 
If a prior restart was indicated in step 506 or a restart was indicated in 
step 508, control proceeds to step 510 to determine if the A to C rename 
checkpoint exists. If so, control proceeds to step 512 to determine if the 
A to C renaming process had completed. If not, control proceeds to step 
514 where the A to C renaming process is continued to completion. If the A 
to C rename checkpoint did not exist in step 510, the rename was complete 
in step 512 or after step 514, control proceeds to step 515 to determine 
if the B to A rename checkpoint exists. If not, control proceeds to step 
531. If so, control proceeds to step 516 to check for the presence of A 
and B files. As will be recalled, the A files are the original files and 
the B files are the newly completed reorganized files. If both exist, 
control proceeds to step 518, where AMS statements are built to rename the 
particular A files to X files. Control then proceeds to step 520, which is 
also where control proceeds if no A files are found. In step 520 AMS 
statements are built to rename the particular B files which are present to 
A files. Control then proceeds to step 522, which is also where control 
proceeds if there were no B files as determined in step 516. In step 522 
AMS statements are built to delete all of the X files are present. Control 
then proceeds to step 524 to determine if this was the last entry in the 
particular rename member list. If not, control proceeds to step 526 where 
the next entry in the rename member list is reviewed and control returns 
to step 516 to complete this process. 
If this was the last entry in the rename member list, control proceeds to 
step 528 where all of the table and indices are stopped to allow exclusive 
access. Control then proceeds to step 530 where the AMS statements are 
executed and the appropriate checkpoints are removed from the checkpoint 
file. Control then proceeds to step 532 to determine if any partition or 
tablespace has been completed. If not, control proceeds to step 533 to 
determine if a restart or recover operation is in process. If a recover, 
control proceeds to step 558. If a restart, control proceeds to step 534 
where the tablespace reorganization procedure must be restarted from the 
beginning. If the partition write was complete, control proceeds to step 
536 to determine if the TSRID1 buffer had been written to disk, indicating 
a certain level of completion of the index and table operations. If so, 
the TSRID1 buffer is reloaded into memory in step 538. In step 540, a test 
is made to determine if there was an error loading the TSRID1 file. If so, 
control proceeds to step 542, which is also where control proceeds if the 
TSRID1 file had not been written in step 536. In step 542 a determination 
is made whether any indices are yet to be completed and there are further 
yet to do. If so, control proceeds to step 544 to determine if the 
STEP.sub.-- MUST.sub.-- COMPLETE flag is set. If so, control proceeds to 
step 546 as this is an error condition. If not, control proceeds to step 
534 where the tablespace reorganization is restarted. 
If there was no error in loading the file in step 540 or there were no 
indices yet to do in step 542, control proceeds to step 547 to determine 
if a restart or recover operation is in progress. If a restart, control 
proceeds to step 548, where the object checkpoints, table or index as the 
case may be, are reviewed and a list of objects not yet completed is 
developed. If a recover in step 547, control proceeds to step 549 where 
the list is developed only of all non-partitioned indices. Control 
proceeds from steps 548 and 549 to step 550, where a rename member list is 
rebuilt from the completed checkpoints. Control then proceeds to step 552 
to determine if there is a clustering index. If not, control proceeds to 
step 340 in the tablespace reorganization sequence 300 to complete the 
operations. If there is a clustering index, control proceeds to step 326 
where the clustering index operations are performed. 
If in step 502 it was determined that the rename start had not been 
checkpointed, control proceeds to step control proceeds to step 531. In 
step 531 the checkpoint file is read and then control proceeds to step 
532. 
If in steps 506 or 508 it was determined that recover was requested or 
previously done, control proceeds to step 562 to determine if the A to C 
rename checkpoint exists. If so, control proceeds to step 564 to determine 
if the A to C checkpoint completion has been indicated. If not, control 
proceeds to step 566 where the C files are renamed to A files and control 
then proceeds to step 558 to delete all of the B files. If the A to C 
renaming has been completed, control proceeds to step 568 to determine if 
the STEP.sub.-- MUST.sub.-- COMPLETE flag is set. If so, control proceeds 
to step 516 as a recover can only occur by completion of the 
reorganization process. If the STEP.sub.-- MUST.sub.-- COMPLETE flag was 
not set in step 568, control proceeds to step 566. 
If the A to C checkpoint did not exist in step 562, control proceeds to 
step 563 to determine if the B to A checkpoint exists. If not, control 
proceeds to step 531. If so, control proceeds to step 572 to determine if 
there are any X files. If not, control proceeds to step 574 where AMS 
statements are built to delete the B files. If so, control proceeds to 
step 574 to determine if there are any B files. If not, control proceeds 
to step 578 where AMS statements are built to delete the A files and to 
rename the X files to A files. If there are B files, control process to 
step 580 to determine if there are any A files. If not, control proceeds 
to step 582 to develop a series of AMS statements to rename all of the X 
files to A files and to build AMS statements to delete all of the B files. 
If there are A files in step 580, control proceeds to step 584 as this is 
an error condition. After steps 574, 578 or 582, control proceeds to step 
586 to determine if this was the last entry in the rename member list. If 
not, control proceeds to step 588 where the next entry is obtained and 
control returns to step 582. If it was the last entry control proceeds to 
step 528. 
Various detailed reorganization and reordering sequences are utilized. 
Those will be explained at this time. First, the non-clustering index 
reorganization is explained to illustrate an exemplary reorganization 
procedure for the index, followed by the detailed operation of the table 
reordering and clustering reorganization process. It is noted that no 
conventional sort techniques are used, and basically only sequential 
access is used when reading or writing files, thus greatly improving 
speeds, both in file access and in reordering. 
Referring now to FIG. 4, a balanced tree structure such as used in a DB2 
index file is shown. A root page R is at the top of the tree and contains 
entries directing to the two tree pages T1 and T2. Each of the tree pages 
T1 and T2 contain a plurality of entries which point to various leaf pages 
L1-L5. Each leaf page then also finally contains a series of entries which 
directly point to the table space pages in the table with which the index 
is associated. It is understood that in a DB2 file the entries in each 
individual leaf page L1-L5 are kept in logical order by the DB2 system 
itself. Similarly, the entries in each of the tree pages T1 and T2 and the 
root page R are also similarly automatically kept ordered in logical order 
within the page itself. 
FIG. 5 is a sequential representation of a DB2 index file, which is a VSAM 
data set in either ESDS or LDS format. It is understood that when various 
initials are utilized, these are considered well known to those skilled in 
the art of IBM mainframes and DB2 and thus the full acronym may not be 
provided. The index file, generally referred to by the letter I, in FIG. 5 
has a first page 0 which is a header page. This header page contains 
particular information needed to indicate to the various packages and 
programs, most particularly to the operating system of the machine, the 
type of file and other related information. The second page of the index 
file I is a space map which indicates which particular subsequent pages in 
the file are currently active for that particular index file, these pages 
either being tree pages or leaf pages. The third page, page 2, is the root 
page R. The remaining pages in the index file I are tree, leaf, empty and 
unused pages in whatever order has developed through the use of the DB2 
indexing process. 
FIG. 6 illustrates the organization of information inside a particular root 
or tree page. The page starts with a header which contains various control 
information needed by DB2. Following this is a series of page number and 
key value entries, with the final entry being a single page number entry 
and the page concluding with an EOP or end of page indicator. For each of 
the series of page number and key value entries, the page number indicates 
the particular physical page which contains the next level down in the 
tree structure and the key value indicates the highest index key value 
contained in that particular page. The final page number in the particular 
root or tree page does not need a key value, as no further reference is 
necessary to higher key values. It is of course understood that if the 
index is sufficiently small, no tree pages are actually present and the 
root page can actually be a leaf page, but this is an unusual condition in 
that the database is then very small. A much more conventional structure, 
as indicated before, has multiple layers of tree pages between the root 
page and the leaf pages. If the particular structure of the index file had 
three levels, then the root page would indicate the appropriate number of 
references to specific tree pages, which tree pages would then also 
contain entries to another level of tree pages, which tree pages would 
then finally point to the leaf pages. It is also noted that for the 
examples in this specification show only a very limited number of entries 
in each page for simplicity. It is understood that in actual use a DB2 
index file root or tree page will contain up to 1000 entries depending on 
the length of the key value, while the leaf files may contain up to 800 
entries as described below, though normally a tree page has approximately 
100 entries and a leaf page has approximately 70 entries. 
FIGS. 7A and 7B illustrate the two various arrangements of leaf pages 
allowable in a DB2 index file. In the version shown in FIG. 7A, referred 
to as a segmented leaf page LS, the page contains a header which contains 
control information, followed by a subpage directory, which is a series of 
offsets to the particular subpages contained in the particular page and to 
the various high key values. Then follows a series of subpages followed by 
an end of page indicator. Shown below the leaf page LS is a single subpage 
SP which also contains a header for control information and a plurality of 
entries which are the actual index values. It is understood that each of 
the subpages has the structure as in the subpage SP. FIG. 7B shows an 
alternative non-segmented leaf page LN. The non-segmented leaf page LN 
contains a header for the necessary control information and then simply a 
plurality of entries which are the index entries. Therefore FIGS. 6, 7A 
and 7B show the structure of the various page entries present in the index 
file I. 
FIG. 8 is an exemplary representation showing particular root and tree 
pages R, T1 and T2, wherein the particular physical page numbers have been 
illustrated. Again it is noted that this is a very simple example 
utilizing only 13 leaf pages, 2 tree pages and a single root page. Of 
course, in a typical index file there would be thousands to hundreds of 
thousands to millions of these particular pages. However, the particular 
example is used to indicate the method of the preferred embodiment in a 
much more clear and concise format. In the example of FIG. 8, the root 
page R is page 2 of the index file I as indicated. The first page number 
entry, i.e. the first logical tree page, is page 9. Proceeding then to the 
tree page at page 9, which is tree page T1, tree page T1 contains a series 
of page number entries. These page number entries are the particular leaf 
pages in logical order. The six entries in the particular tree page T1 are 
the physical number of the particular page of the leaf page, while the 
ordering is from first to last within the particular tree page T1. 
Similarly, the second tree page T2, which is physical page 5 in the 
example of FIG. 8, contains five leaf page entries contained in logical 
order. It can be seen that the physical order of the entries in both the 
tree pages T1 and T2 and the root page R do not bear any necessary 
physical relationship at this time. This often develops during use of a 
particular database in DB2 as items are deleted, rearranged, added and so 
forth. Looking at the structure of FIG. 8, it can be seen that if a direct 
access storage device (DASD) were to try and access the various leaf pages 
in logical order, then the device would be skipping from page 8 to page 10 
to page 3 to page 6 and so on in the index file I. All of this random 
access movement is necessarily slower then the various sequential 
movements. For example, in the case of a disk drive unit the head would 
have to be moved to several different locations, i.e. there would be 
numerous seek requests across several tracks. This is one of the slower 
operations of a disk drive, so performance of the DB2 system would be 
reduced. 
FIG. 9 shows the development of the first buffer, a logical order buffer 
LB, utilized in the preferred embodiment. The buffer LB is preferably has 
a length of the number of leaf pages, in the case of FIG. 9, 11 pages. 
This buffer LB contains the association of the logical relationship of a 
particular leaf page to its physical relationship. This is developed by 
scanning down from the root page R through the various tree pages T1 and 
T2 in the following sequence. Looking at the root page R, the entries in 
FIG. 8 indicate tree pages at physical pages 9 and 5. Proceeding to page 
9, this is tree page T1, which then has entries 8, 10, 3, 6, 11 and 4. 
After processing of this tree page T1 has been completed, physical page 5, 
which is tree page T2, is processed. Tree page T2, has in logical order 
the leaf pages 7, 14, 15, 12, and 13. Referencing then physical page 8, a 
review indicates that page 8 and thus the pages on that level are leaf 
pages and we have reached the effective bottom of the tree. Therefore the 
particular buffer LB shown in FIG. 9 has a number 8 for the physical page 
of the logically first leaf page in the first position. The buffer LB then 
proceeds to contain 10, 3, 6, 11, 4, 7, 14, 15, 12, and 13 as that is the 
order indicated in the tree pages T1 and T2. These leaf page values are 
then entered into the buffer LB of FIG. 9 in order. Therefore the buffer 
LB contains in each effective logical position the physical page location 
of the particular leaf page having that logical ranking. 
The buffer LB is shown transposed or converted into a physical buffer PB in 
FIG. 10. The physical buffer PB is preferably first cleared so that the 
various tree and root entries do not receive valid data values and then 
the logical buffer LB is transposed. The transposition of the logical 
buffer LB to the physical buffer PB is such that the logical buffer LB is 
scanned and the logical page value is placed into the physical page number 
location in the physical buffer PB. For instance, physical location 8 
receives the value 1 to indicate that it is the first logical ordered leaf 
page. This process proceeds for all the entire leaf pages. It is noted 
that in FIG. 10 that there are various zeroes indicating empty entries in 
the physical buffer. These are the locations of the empty pages, the 
various system pages, the root page and the various tree pages. For 
example pages 2, 5 and 9 are the root and tree pages. 
With this buffer PB then developed, a large buffer B is set aside in the 
memory space of the computer to receive the leaf page information. This 
large buffer set aside in the memory space has a number of pages equal to 
the number of leaf pages which are contained in the index file I. In the 
example, 15 leaf pages are shown in FIG. 11A when in actuality only 11 are 
necessary for the index file I of FIG. 8. With the physical buffer PB 
developed, the index file I is then read sequentially. Sequential 
operations are preferred as this the fastest operation for the DASD 
device. As the index file I is read sequentially, the particular physical 
page number of each leaf page is compared against the logical value as 
indicated by the physical buffer PB. If the value is 0, the not defined 
value, then this is an empty page, a system page, a root page or a tree 
page and is not to be entered into the large buffer B. In the given 
example of the physical buffer PB in FIG. 10, the first valid entry is 
physical page 3, which is also logical page 3. This particular leaf page 
is then written into page 3 of the large buffer B. Therefore physical page 
3 has been written into what is logical page 3 of the large buffer B, as 
shown in FIG. 11A. 
Proceeding, the next value read is physical page 4, which is logical page 
6. Thus the leaf page 4 is placed into the large buffer B page 6 as shown 
in FIG. 11B, so that logical ordering is beginning to occur. The next page 
read from the index file I is page 5 and there is a zero value in the 
physical buffer PB, so this is a tree page. The next physical page read is 
page 6, which has an associated logical value of 4 and therefore as shown 
in FIG. 11C the contents of leaf page 6 are placed in memory space page 4. 
This proceeds on through the various pages as shown in the sequence FIGS. 
11D-11K. By FIG. 11K the entire index file I has been read, so that all 
the actual leaf page information is present in the large buffer B in its 
proper logical order, having been read from the physical location and 
transferred according to the physical buffer PB into the desired logical 
location. Therefore the large buffer B as indicated in FIG. 11K has all of 
the leaf pages in proper logical order. 
It is then appropriate to write the leaf pages back to a new index file, 
building the particular root and tree pages as they fill up. Therefore the 
new index file structure would be as shown in FIG. 12. Again the root page 
R is always page 2, while in this case the first tree page T1 is page 9. 
It is noted that the particular entries in tree page T1 are the various 
leaf pages and they are in sequential order, i.e. 3, 4, 5, 6, 7 and 8. As 
the 8th page was the final leaf page for the particular tree page T1, and 
it filled the tree page, then the tree page T1 is written in page 9. 
Beginning at page 10 is the next series of sequential leaf pages. After 
they have all be written, in the example then the tree page T2 is written 
to page 14, which completes the operation of writing the particular index 
file. It is again noted that in actual use this writing process will be 
significantly more complex as there will be numerous levels of trees. 
Therefore it can be seen through the processes shown from FIG. 9 to FIG. 10 
to FIGS. 11A-11K and then to FIG. 12 that the leaf pages have been very 
quickly and very simply transferred so that the index file is reorganized 
from its original physically scattered logical order to a sequential 
physical and logical order so that DASD operations are greatly enhanced 
for logical traverses through the index file I. Therefore operations of 
the DB2 system are enhanced as desired. It is also noted that no 
conventional sort operation is used but rather only reads through the 
various tree levels to determine the leaf logical order, then a sequential 
reading of the leaf pages into memory followed by a writing from memory 
into an index file which was developed. It is noted that the two major 
DASD operations, the read to obtain all of the leaf pages and the write to 
develop the new index file, are both sequential operations. No major 
random operations are necessary after the development of the logical 
buffer LB. This greatly enhances performance, particularly as compared to 
a sorting operation which often utilizes many random accesses of the DASD 
device. 
The flowcharts of FIGS. 13A, 13B, 14A and 14B illustrate sequences utilized 
to practice the method described above. The index reorganization sequence 
100 is commenced to reorganize or reorder the particular index file. In 
step 102 the computer obtains the name of the particular index to be 
organized. In step 104 DB2 is called to determine the actual file name of 
the index file so that other system tools can be used to determine 
information about the index file. The file name is the A or C file, as 
appropriate. In step 105, if the INCONSISTENT STATE flag is set and the 
index is a non-partitioned index, the file name is changed from an A file 
to a C file. Having obtained the actual file name and done any necessary 
renaming, in step 106 the various system functions present on the computer 
are utilized to determine the actual DASD location of the index file and 
its size. This is so that simple file operations can be utilized without 
having to use the actual DB2 operations. Control then proceeds to step 
108, where the index file is opened for random access. This is necessary 
to develop the tree page structure so that the logical buffer LB can be 
developed. 
Control proceeds to step 110, where page 2, the root page, is read. In step 
112 a determination is made as to whether page 2 is a leaf page. If so, 
this is a very small file. In the more conventional case, it is not a leaf 
page and control proceeds to step 114 to determine the number of pages 
immediately below what is now a root page. This is done by reading the 
number of particular page number entries in the root page. Then a first 
buffer is set up having that number of pages. After setting up the buffer 
in step 116, control proceeds to step 118 where the page numbers of the 
tree pages in logical order are written into this buffer. This then 
provides a first ordering of the tree, i.e. which branches are to be read 
first. Control then proceeds to step 120 so that a next level buffer can 
be developed. Preferably the buffer size is reserved according to the 
formula 
EQU n=p(4049/(k+3)+1) 
where n is the number of pages at the next level, p is the number of pages 
at the current level and k is the length of the key field used in the 
particular index file. This allows an estimated buffer size that is at 
least as long as necessary to allow development of the ordering. 
Control then proceeds to step 122 to read the first page indicated by the 
current level buffer written in step 118. If this particular page is a 
leaf page as determined in step 124, then the tree has been fully 
traversed and the information present in the current level buffer is the 
logical mapping, so that the current level buffer is the logical buffer 
LB. If this is not the case and it is another tree page, at least one more 
level must be traversed and so control proceeds to step 126 where the page 
numbers in logical order for the current tree page of the current level 
are read and placed into the next level buffer which has been developed. 
The current tree page is incremented so that the next actual tree page is 
read. Control then proceeds to step 128 to determine if the last tree page 
in the current level was read. If not, control returns to step 126. By 
this manner the entire current tree level is traversed until all of the 
pages in logical order at the next lower level are present in logical 
order in the next level buffer being filled. 
If the last tree page had been read in step 128, control returns to step 
120 where the next level buffer is again developed. Control proceeds to 
step 122 to again read the first page indicated by the current level 
buffer. In this case it is assumed to be a leaf page as we have traversed 
to the end and control then proceeds to step 130, which is also where 
control proceeds from step 112 if the root page was indeed was a leaf 
page. In step 130 the physical buffer PB is set up such that one word is 
present for each page in the index file and all the values in the physical 
buffer PB are zeroed to allow indication of the various root and tree 
pages when the index file is read. Control then proceeds to step 132 (FIG. 
13B) where the transposition from the logical buffer LB to the physical 
buffer PB is performed. This is the transposition as shown from FIG. 9 to 
FIG. 10. After the transposition has been completed in step 132, control 
proceeds to step 134 where the index file is closed as a random access 
file and is opened as a sequential access file to allow fast and optimal 
reading of the index file I. Control then proceeds to step 136 where a 
non-clustering index write routine 200 (FIG. 14A) is commenced. As the 
particular entries will have to ultimately be written to a new index file, 
the B file, it is desirable that the various write operations occur as 
concurrently as possible with the particular read operations where the 
large buffer is filled. In the normal case the particular index files can 
be quite long and generally are not horribly disorganized, so it is 
usually possible to begin writing the early portions of the index file 
structure and the early leaf pages while the order sequence 100 is 
completing the final pages. This allows some overlapping given the length 
of the particular index files and helps speed overall operations. 
Control then proceeds to step 138 where the large buffer B is set aside in 
the memory, with one page set aside per leaf page of the index file. 
Control then proceeds to step 140 where a mapping table is set up with one 
byte available per leaf page. The values of the map table are also cleared 
in step 140. The map table is used as a pointer to indicate whether a 
particular page in the large buffer B has been filled. This is used by the 
write sequence 200 to determine when the next block of leaf pages can be 
written to the new index file. Control then proceeds to step 142 where the 
next page in the current index file which is being reorganized is 
sequentially read. Control proceeds to step 144 where the physical page 
number is used as a look up into the physical buffer PB to determine the 
logical order of this particular leaf page. Control proceeds to step 146 
to determine if the page is a tree page. If so, control proceeds to step 
148. If not, control proceeds to step 150 where the leaf page is written 
into the logical page number location in the large buffer B and a value of 
FF is written to the associated map table location to indicate that this 
page in the large buffer B has been occupied. Control then proceeds to 
step 148, where the sequential page number is incremented. Control then 
proceeds to step 152 to determine if the last page in the index file has 
been read. If not, control returns to step 142 and the process continues 
until all of the leaf pages have been read in physical order and placed in 
logical order in the large buffer B. If the last page was read, control 
proceeds to step 154 which is the end of the order sequence 100. 
As noted above, the index write sequence 200 (FIG. 14A) is used to write 
the leaf pages which have been placed into the large buffer B back into a 
new index file which is then converted to be the index file that has been 
reorganized. The non-clustering index write sequence 200 commences at step 
202 where the names of the new or B and old or A index files are obtained. 
Control proceeds to step 204 to determine the actual file name of the old 
index file, in a manner similar to that of step 104. Control proceeds to 
step 206 where the actual file size and type of the old index file is 
obtained in a manner like that of step 106. Control proceeds to step 208 
where a new or B index file of the same type and size, but having a 
different name, is set up. This new index file will become the reorganized 
index file. Control then proceeds to step 210, where this B index file is 
set up for sequential write operations. In step 212 the header information 
and space map information is written to pages 0 and 1. Control then 
proceeds to step 214 where a dummy root page is written to page 2 of the 
new index file. As the root page is not determined until one of the last 
steps, as it is the highest level and all the tree pages must have been 
developed, a dummy must be written in this case to allow the sequential 
operations. Control then proceeds to step 216 where a map table pointer is 
set to a value of 1. This is so that tracking through the map table can be 
developed. Control then proceeds to step 218 where the next 16 table 
entries in the map table are checked to determine if they are all equal to 
the value FF. If not, control proceeds to step 220 (FIG. 14B) to determine 
if all of the input pages have been processed. If not, control proceeds to 
step 222 to wait momentarily as now the write sequence 200 has gotten 
ahead of the read operation and placement in memory of the order sequence 
100. Control proceeds from step 222 to step 218 so that this process 
continues until 16 entries are available. 
If 16 entries were available in step 218, control proceeds to step 224, 
where the map table value is incremented by 16 and a pointer is indicated 
to a first buffer which is used to build leaf pages. Control then proceeds 
to step 226 where the 16 leaf pages are obtained from the large buffer B 
and provided to a DB2 rebuild operation and finally written sequentially 
to the new index file. It is noted that any RID values contained in the 
index must first be translated from old RID values to new RID values 
before the values are written as the RID values will change because the 
data table is also being reorganized. The translation is done using either 
the TSRID1 or TSRID3 buffers described below. Control then proceeds to 
step 228 to add the highest key value contained for those particular 16 
leaf pages to the tree page of the next level up which is slowly being 
developed. Control then proceeds to step 230 to determine if the 
particular tree page which is being developed is full. If so, control 
proceeds to step 232 where the tree page is then written to the index 
file. If not, control proceeds to step 234 to determine if any more of the 
16 input pages which are being transferred are present. If so, control 
proceeds to step 226 and the leaf page is rebuilt according to DB2 format 
and written sequentially. If there are no more pages from the 16 
particular pages being written, control proceeds to step 220 to again 
determine if all the input pages are completed. Assuming they are not, 
control proceeds to step 222 and then to step 218 so that in this manner 
the write sequence 200 generally tracks and walks up the large buffer B 
until all of the leaf pages have been written. 
If in step 220 all of the input pages have been processed, control proceeds 
to step 236 where the final leaf page is written to the index file. 
Control then proceeds to step 238 where this last leaf page is written to 
the previous prior level up tree page. Control then proceeds to step 240 
to determine if the if the tree page was a root page. If the tree page 
which has now been completed is not a root page, control proceeds to step 
242 where the tree page is written into the new index file. Control then 
returns to step 238 where this final entry is then placed into the tree 
page at again the next level up and control then proceeds to step 240. 
This loop is continued until finally all of the tree pages have been 
completed and the final entry is ready to be made into the root page. 
When the root page receives its final entry, control proceeds from step 240 
to step 244 where the new index file is closed as a sequential write and 
is opened as a random write because now it is time to write the 
appropriate root page. Control then proceeds to step 246 where the 
developed root page is written to page 2 of the index file I. Control 
proceeds to step 248 where random access to the new index file is closed 
and then on to step 250 where the memory utilized by the large buffer, the 
map table and various other buffers is released. Control then proceeds to 
step 252 where the completion of the write operation is checkpointed. 
Control then proceeds to step 254 which is the end of the write sequence 
200. 
In a possible enhancement, it may be appropriate to scan the logical buffer 
LB and obtain the first few logical leaf pages in a random fashion before 
beginning the sequential operation of step 142 and on. One appropriate 
case for this operation would be when a high percentage of the first 
logical pages are near the physical end of the index file. If this is the 
case, the write sequence 200 will have little actual concurrency with the 
order sequence 100, as the write sequence 200 would have to wait until the 
end of the index file is read into the large buffer B before the first 16 
entries are available for writing to the new index file. In this case, 
where there is a great disparity between logical and physical order for a 
short period, it may be more efficient to randomly read some leaf pages to 
allow greater actual concurrency between the order and write sequences 100 
and 200 and a reduced total time. 
A disorganized table is a tablespace is shown in FIG. 15A. The row entries 
represent the key values of the clustering index, which should in order in 
an organized table. Again note that only a very simple example is utilized 
for illustrative purposes. FIG. 15B represents the table in organized or 
order form, where the records or data are sequentially organized. FIGS. 
16A and 16B show representations of a clustering index or CLIX buffer for 
the table of FIGS. 15A and 15B. FIG. 16A shows the CLIX buffer in 
disorganized format, wherein the keys are sequential but the RIDs are 
jumbled. FIG. 16B shows the CLIX buffer if the table were properly 
organized. The CLIX buffer is one buffer utilized during the table reorder 
and clustering index reorganization process. 
The detailed tablespace reorder sequence 400b (FIG. 17A) commences at step 
1402 where a determination is made as to the type of tablespace. If it is 
a simple tablespace, a segmented tablespace with a single table or a 
partitioned tablespace, control proceeds to step 1404 where the clustering 
index of the particular table being reordered is determined. Control then 
proceeds to step 1406 where steps 104 to 134 and 138 to 152 of the 
non-clustering index reorganization sequence 100 are performed to develop 
the required order of the keys in the clustering index. This thus provides 
the CLIX buffer which includes the key numbers in sequence and the 
associated old RID numbers. Control then proceeds to step 1408 where a 
TSRID2 buffer is set up as two columns, the first for the old RID number 
and the second for the new RID number, the number of rows equalling the 
number of rows in the table. While this information could be obtained from 
the CLIX buffer, the use of the TSRID2 buffer is preferred for speed 
reasons. Each entry in the CLIX buffer may actually be quite large, as the 
key may have a maximum length of 256 bytes, while the TSRID2 buffer uses 
only 4 bytes per column entry or 8 bytes per row. This smaller size 
greatly improves processing speeds. Control then proceeds to step 1410 
where the CLIX buffer is read sequentially to obtain the old RID value, 
which is written to the old RID column of the TSRID2 buffer, thus properly 
sequencing the TSRID2 buffer. Concurrently with this reading and writing 
operation the RID values are monitored for the largest relative row number 
in any particular page and this row number is assigned to a variable 
referred to as MAXMAPID. 
Control then proceeds to step 1412 where a TSRID1 buffer is constructed 
having a number of slots in the buffer equal to the number of pages of the 
particular table times the MAXMAPID variable value. Control then proceeds 
to step 1414, where a table buffer is set up in memory having an area for 
the data. Control then proceeds to step 1416 where the table data is 
sequentially read into the table buffer in physical order, skipping any 
empty pages and saving the data according to a compressed format in the 
reserved memory area. 
As the total size of the table data can be large, space saving techniques 
are preferably used when the data is stored. The preferred technique 
includes grouping pages into segments of 16 pages each, with each segment 
starting on a 32 byte boundary. The relative number of this 32 byte 
boundary is saved in a memory area referred to as the segment reference 
table. The segment reference table thus contains one word per 16 pages of 
table data and the value is the relative 32 byte cell number where a 
particular segment begins. Each segment area in turn begins with 16 one 
word offsets to the beginning of the data for that page relative to the 
beginning of the segment. Therefore, to find the beginning of the data for 
a particular page, the page number is divided by 16 and this value 
multiplied by 4 to provide the offset into the segment reference table. 
The value at this location is the cell number to the particular segment 
data which, when multiplied by 32, is the offset into the table data where 
the segment begins. Any remainder from dividing the page number by 16 is 
the relative page number of the segment and when multiplied by 4 is the 
offset into the segment header which is used to obtain the offset in the 
segment which indicates where the actual page data begins. Thus a 
particular page can be accessed without searching using only a few 
computations. 
The data for the particular page is saved in a format which also allows 
access to an individual row without searching. As DB2 keeps MAPIDs at the 
end of each page, the MAPIDs being two byte offsets computed from the 
beginning of the page for each of the table rows. It is noted that the 
MAPIDs are numbered sequentially from the end of the page forward. The 
MAPIDs can then be used for computation purposes. Preferably the MAPIDs 
are placed at the beginning of each page of data, after a prefix which 
indicates the length of the MAPID section. To access a specific row of 
data, the process determines the MAPID by determining the page address 
plus the prefix value minus twice the row number. The MAPID value, plus 
the page address plus the page length minus 20 produces the address to the 
actual row data. Therefore a particular row within a page can also be 
determined without searching. 
Additionally in step 1416, the length of each row is copied in order from 
the table buffer to the TSRID1 buffer unless the RID value indicates an 
overflow row, a row which has been replaced and cannot fit in the 
originally allotted space, in which case an OVERFLOW flag is written. This 
will allow later reference to determine the actual RID value for the 
overflow row. Alternatively, if the row is a deleted row, a DELETED flag 
is written and the row is not written to the table buffer. The TSRID1 
buffer slot location is determined by multiplying the page number, as 
indicated in the RID, times the MAXMAPID variable and adding the row 
number. The CLIX, TSRID2 and TSRID1 buffers are shown in a simple example 
in FIG. 18. 
Control proceeds from step 1418 to step 1420 (FIG. 17B) where a pointer is 
set to the beginning of the TSRID2 buffer. Control then proceeds to read 
the TSRID2 buffer to contain the old RID value and then to calculate the 
slot in the particular TSRID1 buffer as noted above to obtain the record 
length for that row. Control proceeds to step 1424 to determine if the 
OVERFLOW flag was set. If so, control proceeds to step 1426 where the 
overflow RID value is used to retrieve the actual row length from the 
table row data, entry calculated as noted above. The actual overflow RID 
value is saved in the TSRID2 buffer slot as the old RID value. After step 
1426 or if there is not an overflow RID as indicated in step 1424, control 
proceeds to step 1428 where the row length value is used to assign a new 
RID value for each row. The row length is utilized because a particular 
page has only a given size and once the given page has been filled up, a 
new page must be used. Thus the row lengths are added for each page until 
an overflow occurs, at which time a new page is allocated. As this task 
proceeds, the relative row number is determined by the entry number in the 
page and the page number is tracked in an incrementing manner. However, if 
the DELETED flag is set, then the TSRID2 buffer also receives the DELETED 
flag and a new RID value is not determined. 
After the new RID value has been obtained in step 1428, it is saved as the 
new RID value in the TSRID1 and TSRID2 buffer slots for that row. Note 
that this replaces the page length value in the TSRID1 buffer. This 
process is shown in intermediate and final state in FIGS. 19A and 19B. 
Note that new RID values are being added to the TSRID2 buffer and new RID 
values are replacing row lengths in the TSRID1 buffer. Control then 
proceeds to step 1430, where header page and space map pages are 
constructed in a separate memory area when there is sufficient data to 
develop the particular page. The header page is developed immediately upon 
the first operation and the space map pages are developed as pages are 
filled up. Control then proceeds to step 1432 where the pointer to the 
TSRID2 buffer is incremented. Control proceeds to step 1434 to determine 
if the RID calculation operation using the TSRID2 buffer has been 
completed. If not, control returns to step 1422 and the sequence is 
performed until the entire TSRID2 buffer has been traversed and all of the 
new RID values have been determined. 
When all the new RID values have been determined, control proceeds to step 
1436 where the TSRID1 buffer is written to a file and completion of the 
TSRID1 buffer is checkpointed. It is noted that the TSRID1 file thus 
contains the new RIDs in the sequential order of the keys. Control then 
proceeds to step 1438 where steps 202 to 252 are performed for the 
clustering index, noting of course that the old RID values are translated 
to the new RID values by reference to the new RID column in TSRID2 buffer 
for each particular key. Control then proceeds to step 1440, where a table 
B file is opened for sequential operation. In step 1442 the header page 
and the first space map page are written to the table B. Proceeding then 
to step 1444, the row data is written in order for the space map page, 
using the TSRID2 buffer in sequential order as the source of the old RID 
value, with the old RID value being utilized to calculate the entry into 
the memory area for the particular row of data. The MAPIDs are developed 
as the write operation progresses. Any gaps in the new RID numbers as 
noted in the TSRID2 buffer are free pages with all data in the row being 0 
this process continues until the next space map page is to be written. 
Control then proceeds to step 1445 to determine if all the pages have been 
written. If not, control proceeds to step 1446 where the next space map 
page is retrieved from memory and written to the table B file. Control 
then proceeds to step 1444 and the data for that page is written. This 
process repeats until all the data has been written. Control proceeds from 
step 1445 to step 1448 when all the pages have been written. In step 1448 
sequential access to the table B file is closed and the completion of the 
table B write operation is checkpointed. 
If it was determined in step 1402 that this is a segmented tablespace with 
multiple tables, control proceeds to step 1450 where a table buffer is set 
up having an area to receive the actual data. Additionally, an area is set 
up for a TSRID3 buffer, with that buffer having one column with slots for 
each row and an additional two slots for each page. Control then proceeds 
to step 1452, where the table data is sequentially read into the table 
buffer in physical order, skipping any empty columns and saving the data 
according to the compressed format discussed above. At the same time, the 
length of the particular row or the overflow RID value is placed in the 
TSRID3 buffer slot. The row count for each page is placed in the page slot 
and a cell range list for each separate table is maintained. A cell range 
list keeps track of the pages in each segment. An exemplary TSRID3 buffer 
is shown in FIG. 20A. Control then proceeds to step 1454, where a pointer 
is set to indicate the first segment or table. Control then proceeds to 
step 1456 to determine if this is an indexed table. If not, control 
proceeds to step 1458. In step 1458 by referencing the cell range list and 
the page length in the TSRID3 buffer, new RID values are assigned as noted 
above, which then replace the length value in the TSRID3 buffer, building 
the space map pages as appropriate and saving those in memory. This is 
illustrated in FIG. 20B where an intermediate state of reorganizing the 
table of FIG. 20A is shown. Control proceeds to step 1460 where the table 
is saved in the FIFO queue. Control then proceeds to step 1462, where the 
pointer value is incremented. Control proceeds to step 1464 to determine 
if the last table was completed. If not, control returns to step 1456. 
If in step 1456 it was determined that this was an indexed table, control 
proceeds to step 1466 where steps 104 to 134 and 138 to 152 are executed 
to develop the required order of the keys in a CLIX buffer. Control 
proceeds to step 1468, where a TSRID2 buffer is set up, having columns for 
the old RID and the new RID values for each row. Control proceeds to step 
1470, where the old RID values are read sequentially from the CLIX buffer 
and written to the old RID column of the TSRID2 buffer. Control proceeds 
to step 1472, where by proceeding sequentially through the TSRID2 buffer 
and obtaining the page length from the TSRID3 buffer using the old RID 
value to indicate position in the buffers, new RID values are assigned and 
placed in the TSRID2 and TSRID3 buffers. This process is shown in sequence 
from FIG. 21A, where all of the values have been placed in the buffers; to 
FIG. 21B, where an intermediate state is shown; and to FIG. 21C, the final 
state of the buffers. Additionally, the space map pages are built as 
appropriate and saved in memory. Control proceeds to step 1474, where the 
table is saved in the FIFO queue. Control then proceeds to step 1476, 
where steps 202 to 252 are performed for the clustering index, noting that 
the old RID values are translated to the new RID values by using the 
TSRID2 buffer. Control then proceeds to step 1462. 
If at steps 1464 the last table was completed, control proceeds to step 
1482 where a table B file is opened for sequential operation and to step 
1484, where a pointer is set to the first table. Control proceeds to step 
1486 to determine if this was an indexed table. If not, control proceeds 
to step 1488, where the header page and the first space map page are 
written to the table B file. Control then proceeds to step 1490, where the 
row data is written in order for the first pace map page using the TSRID3 
buffer in sequential order and filing in the MAPIDs as progressing as 
discussed above. In this case the old RID values are based on the position 
in the TSRID3 buffer and are used with the page table list to obtain 
particular row data. Any gaps in new RID numbers are filed by free pages 
with all zeros until the next space map page is to be written. Control 
then proceeds to step 1491 to determine if all the pages have been 
written. If not, control proceeds to step 1492, where the next space map 
page is written to the table B file. Step 1490 is then re-executed and 
this continues until all pages have been written. When all the pages have 
been written, control proceeds from step 1491 to step 1504, where the 
pointer value is incremented. Control proceeds to step 1506 to determine 
if the last table is completed. If not, control returns to step 1486. 
If in step 1486 it was determined that it was an indexed table, control 
proceeds to step 1498, where the header page and the first space map page 
are written to the table B file. Control then proceeds to step 1500, where 
the row data is written in order for the first space map page using the 
TSRID2 buffer in sequential order as the source of the old RID value. The 
old RID value is used to calculate into the memory area to determine the 
length of the row data for determining new RID values. Any MAPIDs are 
developed as the process is progressing. Any gaps in the new RID numbers 
are filled in by free pages with all zeros, until the next space map page 
is to be written. Control then proceeds to step 1501 to determine if all 
the pages have been written. If not, control proceeds to step 1502, where 
the next space map page is written and then to step 1500 to repeat the 
page data writing operation. When all the data pages have been written, 
control proceeds from step 1501 to step 1504. If not, control returns to 
step 1486. If step 1506 determines that the last table has been completed, 
control proceeds to step 1508 where sequential access to the table B file 
is closed and the completion of the table B write operation is 
checkpointed. Control then proceeds to step 1510, which is a completion or 
end of the sequence. 
As previously stated, all of the operations to the table data to and from 
DASD are performed sequentially, thus greatly improving DASD performance. 
Further, no conventional sorting is done, which is a very cumbersome and 
slow process. Thus a second means of speed improvement is provided. 
Similar statements can be made for the operations with the clustering 
index. Various tests have shown a performance improvement of three to six 
times over conventional tablespace reorganization procedures. 
The above-description has made only minor reference to the actual threads 
and multi-tasking that can be utilized. This was done for purposes of 
simplifying the explanation. As conventionally done in mainframe 
operation, many of the illustrated operations may actually be executing 
concurrently or started for operation, which then proceeds according to 
the operating system scheduling process. This concurrency may require 
certain tests in certain sequences to prevent overrunning, but this is 
conventional and can readily be provided by one skilled in the art. 
Further, the above description has focused on DB2 tablespaces, but similar 
techniques can be used for databases developed in other formats, 
particularly tree-structured formats. 
The foregoing disclosure and description of the invention are illustrative 
and explanatory thereof, and various changes in the method of operation 
may be made without departing from the spirit of the invention.