Patent US5983215A successfully refreshed from Google Patents.
US5983215A
Expired / Lapsed
US
⏱️ 0.0 years remaining
System and method for performing joins and self-joins in a database system
Assignee: Columbia University
•
Filing: 1997-05-08
•
Granted: 1999-11-09
•
Expires: 2017-05-08
Abstract
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.
Inventors
- 👤 Kenneth A. Ross
- 👤 Hui Lei
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-08 03:08
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/20; G06F16/24; G06F16/245; G06F16/2455; G06F16/24553; G06F16/24561; G06F16/24558; G06F16/2456; Y; Y10; Y10S; Y10S707/00; Y10S707/964; Y10S707/966; Y10S707/971; Y10S707/972; Y10S707/99931; Y10S707/99932
Claims Analysis
Total Claims: 43
Claim 1
Independent Claim
178 words
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.
Claim 2
Independent Claim
178 words
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.
Claim 3
Dependent Claim
23 words
The method of claim 1, wherein said allocation step substantially equally distributes said records of said input tables among said array of partitions.
Claim 4
Dependent Claim
18 words
The method of claim 2, wherein said allocations steps includes reading said join index to determine the allocation.
Claim 5
Dependent Claim
18 words
The method of claim 1, wherein an optimal number of partitions is determined for said array of partitions.
Claim 6
Dependent Claim
15 words
The method of claim 1, wherein each of said input tables are read only once.
Claim 7
Dependent Claim
14 words
The method of claim 1, further comprising the step of generating the join index.
Claim 8
Dependent Claim
18 words
The method of claim 1, wherein at least one of said input tables is larger than said memory.
Claim 9
Dependent Claim
15 words
The method of claim 1, wherein said records are read as part of data blocks.
Claim 10
Dependent Claim
19 words
The method of claim 1, further including the step of locally selecting at least one of the input files.
Claim 11
Dependent Claim
15 words
The method of claim 1, further including the step of locally selecting said join index.
Claim 12
Dependent Claim
28 words
The method of claim 1, wherein said join index further includes additional records which are included in said output files of at least one of said input tables.
Claim 13
Dependent Claim
22 words
The method of claim 1, wherein said step of sorting each said temporary file includes sorting a plurality of temporary files together.
Claim 14
Dependent Claim
19 words
The method of claim 1, wherein said join operation includes a self-join for at least one said input table.
Claim 15
Dependent Claim
18 words
The method of claim 13, wherein said allocating step allocates said partitions using duplicate conditions for said self-join.
Claim 16
Dependent Claim
27 words
The method of claim 14, wherein said reading said index entry step further comprises reading said index entry for said duplicate condition prior to said sorting step.
Claim 17
Dependent Claim
13 words
The method of claim 1, wherein said allocation step uses a multi-recursion allocation.
Claim 18
Dependent Claim
17 words
The method of claim 16, wherein said multi-recursion allocation re-partitions a portion of said array of partitions.
Claim 19
Independent Claim
168 words
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.
Claim 20
Independent Claim
168 words
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.
Claim 21
Dependent Claim
21 words
The method of claim 18, wherein said input tables are read into one of said memories only once during said joining.
Claim 22
Dependent Claim
20 words
The method of claim 18, wherein said join results are written to said output files only once during said joining.
Claim 23
Dependent Claim
23 words
The method of claim 18, wherein said allocation step substantially equally distributes said records of said input tables among said array of buffers.
Claim 24
Dependent Claim
18 words
The method of claim 18, wherein said allocations step includes reading said join index to determine said allocation.
Claim 25
Dependent Claim
14 words
The method of claim 18 further comprising the step of generating the join index.
Claim 26
Dependent Claim
15 words
The method of claim 18, wherein said separate output files are connected by file pointers.
Claim 27
Dependent Claim
26 words
The method of claim 18, wherein said join index further includes additional records which are included in said output file of one of said input tables.
Claim 28
Dependent Claim
19 words
The method of claim 18, wherein said join operation includes a self-join operation for at least one input table.
Claim 29
Dependent Claim
18 words
The method of claim 26, wherein said allocating step allocates said partitions using duplicate conditions for said self-join.
Claim 30
Dependent Claim
16 words
The method of claim 27, further comprising performing said allocation step prior to said processing step.
Claim 31
Dependent Claim
13 words
The method of claim 18, wherein said allocation step uses a multi-recursion allocation.
Claim 32
Dependent Claim
17 words
The method of claim 29, wherein said multi-recursion allocation re-partitions a portion of said array of partitions.
Claim 33
Independent Claim
128 words
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.
Claim 34
Independent Claim
128 words
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.
Claim 35
Dependent Claim
19 words
The apparatus of claim 31, wherein said reading means reads each said input table only once during said join.
Claim 36
Dependent Claim
20 words
The apparatus of claim 31, wherein said allocation means allocates said partitions using duplicate conditions for a performing a self-join.
Claim 37
Dependent Claim
24 words
The apparatus of claim 31, further comprising an input/output device for enabling parallel processing of said join with at least one other said apparatus.
Claim 38
Dependent Claim
183 words
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.
Claim 39
Dependent Claim
183 words
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.
Claim 40
Dependent Claim
26 words
The system in claim 35, wherein said main memory's storage capacity is smaller than at least one of said input tables stored in said storage medium.
Claim 41
Dependent Claim
21 words
The system in claim 35, wherein said join index is generated by said central processing unit prior to said join operation.
Claim 42
Dependent Claim
23 words
The system of claim 35, wherein said at least one processing unit reads each said input table only once during said join operation.
Claim 43
Dependent Claim
17 words
The system of claim 35, wherein said partitions are allocated using duplicate conditions for performing a self-join.
References Cited (Backward Citations)
US5121494A
Cited
US5241648A
Cited
US5325525A
Cited
US5551031A
Cited
US5557791A
Cited
US5345585A
Cited
US5408654A
Cited
US5666525A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-11-08 | 2003-05-10 | 2003-11-09 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-11-08 | 2007-05-10 | 2007-11-09 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-11-08 | 2011-05-10 | 2011-11-09 | $7700.00 | Window Closed / Lapsed |