Hybrid hash join process

US6263331A · kind A · utility

Assignee

• Unisys Corporation · US

Inventors

• Lee-Chin Hsu Liu · San Jose, US
• Lowell L. Baerenwald · Eagan, US
• James M. Plasek · Shoreview, US
• Michael S. Jende · White Bear Lake, US
• Kenji Yoneda

Key dates

• Filing date: Jul 30, 1998
• Grant date: Jul 17, 2001
• Expiry date: Jul 30, 2018

Classification

• Technology area (CPC Y): Emerging Cross-Sectional Technologies
• CPC primary: Y10S707/99934
• WIPO field: Computer technology
• WIPO sector: Electrical engineering

Abstract

A hybrid hash join process joins data rows from two tables which have at least one common data column by partitioning the data rows based on the values in the common data column(s), creating data structures to decrease search time for matching rows, and recovering full data buffers using a unique buffer management methodology. A smaller one of the two tables is designated as an outer table and a larger one of the two tables as an inner table. The hybrid hash join process determines which rows in the inner and outer tables satisfy a selection criteria; the rows that satisfy the selection criteria are referred to as inner hit rows and outer hit rows. The hybrid hash join process assigns the inner and outer hit rows to corresponding inner and outer partitions, respectively. Buffer overflow in the outer partitions is handled by linking empty buffers to the outer partitions until all buffers are used. Buffer space is recovered by writing outer hit rows for a selected partition to mass storage. Buffer overflow in the inner partitions is handled by either writing the inner rows in the buffer to mass storage or by searching the corresponding outer partition for matches. The outer hit rows …