Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Low I/O Index Build Method for Bipartite Variable Length Files

IP.com Disclosure Number: IPCOM000104169D
Original Publication Date: 1993-Mar-01
Included in the Prior Art Database: 2005-Mar-18
Document File: 4 page(s) / 195K

Publishing Venue

IBM

Related People

Holm, ML: AUTHOR [+3]

Abstract

Bipartite variable length files house data in two separate partitions; one contains the fixed length portion of the records while the other contains the variable length portion. Since the data in the variable length portion of the file is not necessarily in the same order as that of the fixed length portion, an index build of a bipartite file can result in many more disk I/O's on the variable length portion of the file than encountered to page the corresponding fixed length portion. Thus, an index build operation over a bipartite variable length file can take significantly longer than a similar operation on an equally sized fixed length file since, in the former case, the number of disk I/O's is much greater.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 23% of the total text.

Low I/O Index Build Method for Bipartite Variable Length Files

      Bipartite variable length files house data in two separate
partitions; one contains the fixed length portion of the records
while the other contains the variable length portion.  Since the data
in the variable length portion of the file is not necessarily in the
same order as that of the fixed length portion, an index build of a
bipartite file can result in many more disk I/O's on the variable
length portion of the file than encountered to page the corresponding
fixed length portion.  Thus, an index build operation over a
bipartite variable length file can take significantly longer than a
similar operation on an equally sized fixed length file since, in the
former case, the number of disk I/O's is much greater.  The following
is a method which will improve the performance of indexes built over
bipartite variable length files by significantly reducing the number
of I/O's on the variable length partition.

      This method is based on the following concurrent index build
algorithm for fixed length files.

1.  The pool size available for the build is determined and the
    amount of index tree structure that can be contained in this pool
    is calculated.  The index keys will first be inserted into a
    series of relatively small indexes, called mini-indexes.  Each of
    these mini-indexes fits almost precisely in the pool being used
    for the index build.  As one mini-index approaches the available
    pool size (excluding overhead for code, data records, etc.), it
    is asynchronously purged from the pool and another is created and
    begins being populated.  Only pages from the new mini-index are
    now referenced.  Previously created mini-indexes will only be
    referenced after all of the index's keys have been built and
    inserted into mini-indexes.  The method for building a single
    mini-index is as follows:

    o   A block of data records is asynchronously paged into
        mainstore.  This is the next block of records to be processed
        and it replaces, through exchange bring, the previous block
        of records that has just been processed.  The current block
        of records is going to be processed now.  Note that the I/O
        for the next block of records is overlapped with the
        processing of the current block.

    o   A key is built for the first record in the current block of
        records.

    o   The key is inserted into the current mini-index.

    o   When the current block of records is exhausted, it becomes
        the previous block and the next block becomes the current
        block.  Step 1a above is then repeated.

2.  All the keys that will be in the index are now in a series of
    mini-indexes.  Keys will now be retrieved from the mini-indexes
    and inserted into the...