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

Table File Partition Algorithm for Disk Workload Balancing

IP.com Disclosure Number: IPCOM000108316D
Original Publication Date: 1992-May-01
Included in the Prior Art Database: 2005-Mar-22
Document File: 4 page(s) / 149K

Publishing Venue

IBM

Related People

Schwendemann, W: AUTHOR [+2]

Abstract

A high frequency of access to a table file on a busy disk can lead to a disk I/O contention problem. The I/O contention problem will impact the performance of database applications.

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

Table File Partition Algorithm for Disk Workload Balancing

       A high frequency of access to a table file on a busy
disk can lead to a disk I/O contention problem. The I/O contention
problem will impact the performance of database applications.

      The solution is to partition the table file into a set of
smaller files and distribute them to other disks to balance the
workload of disks so that the I/O contention problem can be
eliminated.
ASSUMPTIONS
  o  A table consists of a set of table files.
  o  Records in the table are physically stored onto the disks in a
sequential order, based on the value of a key of the table.
  o  The table file is uniformly accessed by database applications.
  o  A table file can reside on only one disk.
  o  Disks contain only database related information (i.e., disks are
dedicated to database activity).
GIVEN INPUT TO THE ALGORITHM
N         total number of disks that are available.
P         totals number of disk accesses (i.e., I/O operations) for
all disks.
DISK_ACCESS[I] number of "accesses" for disk[i]. The range is 1<= i
<=N
DISK_CAPACITY[I] "storage capacity" for disk[i].
   The range is 1<= i <=N
M         total number of table files with high frequency of access
needed to be partitioned.
TABLE_FILE_ACCESS[J] number of "table file accesses" for table_
file[j].  The range is  1 <= j <= m.
TABLE_FILE_LOCATION[J] the disk upon which table_file[j] is located.
The range is  1 <= j <= m.
TABLE_FILE_SIZE[J] " file size" for table_ file[j].  The range is  1
<= j <= m.
ALGORITHM FOR REDISTRIBUTING TABLE FILES TO IMPROVE DISK WORKLOAD
INITIALIZATION:
1. Initially, the number of files processed for partitioning is zero.
         files_processed = 0 2.  There is a flag for each table file
and it will be set when the file is processed for partitioning.
         for i = 1 to m
         {
            table_file_flag[i] = 0
         }
STEPS:
1.  For all table files that need to be partitioned, find the most
active table file.
       most_active_table_file = MAX( table_file_access[i]), where 1
<= i <= m and file[i] has not been processed yet.
2.  Subtract the number of accesses of the most_active_table_file
from the workload of the disk on which it resides.
         disk_access[j]
         = disk_access[j] - table_file_access[most_active_table_file]
         where j = table_file_location[most_active_table_file]
3.  Find the most inactive disk to which the table file of the prior
step will be moved.
         least_active_disk = MIN(disk_access[i]) , 1<= i <= N
4.  Calculate the size of the fragment which will be carved out from
the most active file and moved to the least active disk by the
following formula:
         fragment_size = table_file_size[most_active_table_file]*
           MIN(1,((P/N)-disk_access[least_active_disk])/
                 ...