International Business Machines Corporation

Paul K-w Lee

Zvi Yosef Yehudai

A system for storing sortwork data in a storage subsystem to maximize parallelism during subsequent merging operations. One implementation of the invention employs a computing system with a sort/merge application module and a storage subsystem such as a RAID arrangement. Each DASD unit preferably includes multiple disks in a vertically-stacked array, and each disk is configured with at least one track. Each disk corresponds to one disk of each of the other DASD units. A group of identically-sized locations from identically-positioned tracks of corresponding disks from each DASD unit forms. And, the aggregate of all identically-positioned tracks from all disks in all DASD units makes up a logical array cylinder. To perform sorting and merging operations in accordance with the invention, the sort/merge application module first internally sorts a data packet to generate a string. The string is then stored in the storage subsystem, with a particular storage scheme that maximizes the parallelism of subsequent merge operations. Specifically, the string is stored such that, after all strings have been stored, each string will be evenly striped across disks of all DASD units after all data has been sorted and stored in the disk storage subsystem. Striping is most advantageously made in a diagonal pattern with wrap-around. Moreover, string size permitting, striping is preferably confined to a single logical array cylinder to minimize actuator movement in reading and writing to the disks. Storage is accomplished such that each logical block contains one string-block from each string, and each string-block within a logical block has the same order relative to its string as the other string-blocks to their corresponding strings.

System for parallel striping of multiple ordered data strings onto a

In a recursive distributive sort of records according to their key fields, a method for distributing keys to form one or more subgroups and collecting them to preserve or maintain an order among the subgroups. The distribution is accomplished by comparing each key field against an extrinsic attribute and then assigning the key to a subgroup or bucket. The collection sequence preserves the overall key field order. A Dynamic Branching Table (DBT) for governing the ordering of buckets during the collection phase is initially populated with NO-OP instructions. During the distribution phase, a CALL instruction replaces the NO-OP in the sorted order DBT position upon the first occurrence of a distinguishable character in the key character sequence being scanned. An address pointer, pointing to the corresponding bucket, is then inserted in a Bucket Pointer Table (BPT) indexed to the DBT. During the collection phase, the DBT is executed and the empty buckets are skipped by NO-OP execution, while the populated buckets are processed by subroutine CALL execution.

Growing community of inventors

San Jose, CA, United States of America

Paul K-w Lee