System and method for performing joins and self-joins in a database system

A method for joining one or more input tables comprised of records stored in a storage medium in a database system which includes said storage medium and at least one memory having a storage capacity smaller than necessary to store at least one of said input tables, said method using a join index indicative of records to be joined and having an index entry for each record to be included in an output resulting from said join, and comprising the steps of:

• (a) allocating an array of partitions with partition identifiers based on each of said index entries in said join index in said at least one memory;
• (b) separately processing said plurality of input tables by reading each said input tables into one of said at least one memory and matching each said record in said input tables to one of said partitions during said joining;
• and
• (c) writing join results for each one of said input tables into separate output files responsive to said partition identifiers.

An apparatus for joining a plurality of input tables comprised of records in a database system using a join index indicative of records to be joined and having an index entry for each record to be included in an output resulting from said join, said apparatus comprising:

• (a) means for allocating an array of partitions including assigning partition identifiers in a memory responsive to each said index entry in said join index;
• (b) means for reading said join index and for sequentially reading said input tables during said join;
• (c) means for processing said input tables using said allocated array of partitions and corresponding partition identifiers;
• and
• (d) means for writing said records to separate output files responsive to said corresponding partition identifier for each said input table.

A database system capable of performing join operations on one or more input tables using a join index, comprising:

• (a) at least one central processing unit;
• (b) a main memory partitionable into a plurality of partitions identified by a partition identifier;
• (c) a storage medium separate from such main memory;
• (d) at least one input tables stored in said storage medium;
• (e) a join index stored in said storage medium indicating corresponding entries of said at least one table to be joined, wherein said main memory partitions are responsive to each of said corresponding entries in said join index;
• (f) a plurality of output files, wherein each one of said output files corresponds to only one of said at least one input table;
• (g) wherein at least one of said processing unit processes said join operation by reading each of said at least one input table from said storage medium, processing said at least one input table in said main memory using said partitions and partition identifiers, and writing said join operation's results for each said input table to said corresponding output files.