System and method for performing joins and self-joins in a database system
First Claim
1. A method for joining in a database system one or more input tables comprised of records stored in a storage medium using a join index indicative of records to be joined and having an index entry for each record to be included an output resulting from said join, said method comprising the steps of:
- (a) allocating an array of partitions in a memory responsive to said index entries of each said input table in said join index;
(b) reading said join index;
(c) storing said join index entries corresponding to each of said input tables and a corresponding partition identifier to temporary files associated with said allocated partitions;
(d) reading in turn said index entries and said corresponding partition identifier in each of said temporary files and sorting each said temporary file;
(e) sequentially reading portions of said tables only if said portion includes a record identified in said sorted temporary file; and
(f) writing said read records in accordance with an order of said corresponding partition identifiers to separate output files associated with each said input table.
2 Assignments
0 Petitions
Accused Products
Abstract
A technique for efficiently joining multiple large tables in a database system which utilizes a join index. The technique uses a join index and minimizes the number of input/output operations while maximizing the use of the small main memory through a buffer allocation process based on the join index entries. The technique uses multi-dimensional partitioning and assigns partition identifiers to each buffer which are used to coordinate the resultant output files when the technique is complete. The output is vertically fragmented with one fragment for each input table which further allows the individual processing of each input table. The technique performs self-joins in a very efficient manner by requiring the records of the input table to be read only once.
-
Citations
39 Claims
-
1. A method for joining in a database system one or more input tables comprised of records stored in a storage medium using a join index indicative of records to be joined and having an index entry for each record to be included an output resulting from said join, said method comprising the steps of:
-
(a) allocating an array of partitions in a memory responsive to said index entries of each said input table in said join index; (b) reading said join index; (c) storing said join index entries corresponding to each of said input tables and a corresponding partition identifier to temporary files associated with said allocated partitions; (d) reading in turn said index entries and said corresponding partition identifier in each of said temporary files and sorting each said temporary file; (e) sequentially reading portions of said tables only if said portion includes a record identified in said sorted temporary file; and (f) writing said read records in accordance with an order of said corresponding partition identifiers to separate output files associated with each said input table. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17)
-
-
18. 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. - View Dependent Claims (19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30)
-
-
31. 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. - View Dependent Claims (32, 33, 34)
-
-
35. 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. - View Dependent Claims (36, 37, 38, 39)
-
Specification