Patent US5845113A successfully refreshed from Google Patents.
US5845113A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method for external sorting in shared-nothing parallel architectures
Assignee: International Business Machines Corp
•
Filing: 1992-10-27
•
Granted: 1998-12-01
•
Expires: 2012-10-27
Abstract
Abstract A system and method is provided for distributed relational databases for parallel sorting of a relation wherein the relation is a set of tuples to be sorted on multiple sort sites which completely decouples the return phase from the sort phase in order to eliminate the merge phase. The method involves selecting one coordinator site from any of the available logical sites, then generating and sorting a local sample on each of the available storage sites before sending the local random sample from each storage site to the designated coordinator site wherein the local random samples are merged to provide a single global sample. The coordinator site determines the global interval key values based on the global sample. The interval key values being determined such that each interval fits in a single sort site's main memory, wherein the tuples between two interval key values define the interval. The interval key values are sent to the various storage sites wherein each storage site scans its portion of the relation in order to determine for each tuple the assigned interval and its corresponding sort site before sending each tuple to the assigned sort site. At each sort site the tuples are stored in temporary files using a single temporary file for each interval whereafter repeating, for each interval on each sort site, the steps of reading an interval and performing an in-memory sort in any fashion of the interval read before sending the tuples of the sorted interval to the sink site.
Inventors
- 👤 Arun N. Swami
- 👤 Honesty C. Young
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-06 17:08
CPC Classifications
G; G06; G06F; G06F7/00; G06F7/22; G06F7/24; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99937
Claims Analysis
Total Claims: 45
Claim 1
Independent Claim
139 words
A method for parallel sorting of a relation which is to be sorted on multiple sort sites and then sent to a single sink site, the relation including a plurality of tuples, the tuples being distributed over a plurality of storage sites, each sort site having at least a predetermined memory capacity, the method comprising the steps of: determining a set of global interval key values and intervals therebetween, such that each interval fits in the predetermined memory capacity of a single sort site notwithstanding that the number of global interval key values might exceed the number of sort sites; scanning at each storage site the relation distributed thereto, determining for each tuple an assigned interval and the corresponding sort site; and sending each tuple to the assigned sort site; whereby the tuples are sorted over the sort sites.
Claim 2
Independent Claim
139 words
A method for parallel sorting of a relation which is to be sorted on multiple sort sites and then sent to a single sink site, the relation including a plurality of tuples, the tuples being distributed over a plurality of storage sites, each sort site having at least a predetermined memory capacity, the method comprising the steps of: determining a set of global interval key values and intervals therebetween, such that each interval fits in the predetermined memory capacity of a single sort site notwithstanding that the number of global interval key values might exceed the number of sort sites; scanning at each storage site the relation distributed thereto, determining for each tuple an assigned interval and the corresponding sort site; and sending each tuple to the assigned sort site; whereby the tuples are sorted over the sort sites.
Claim 3
Dependent Claim
35 words
A method as defined in claim 1 further comprising the step of determining the global interval key values based on a global sample of the tuples of the relation on the plurality of storage sites.
Claim 4
Dependent Claim
52 words
A method as defined in claim 1 further comprising the step of repeating for each interval on each sort site the steps of: a) reading an interval; b) performing an in-memory sort in any fashion of the interval read; and c) sending the tuples of the sorted interval to the sink site.
Claim 5
Dependent Claim
80 words
A method as defined in claim 1 wherein the method steps of generating and sorting a local sample and sending the local random sample from each storage site to the designated coordinator site and merging the local random samples at one storage site proceed concurrently with the steps of generating and sorting a local sample and sending the local random sample from each storage site to the designated coordinator site and merging the local random samples at another storage site.
Claim 6
Dependent Claim
22 words
A method as defined in claim 1 wherein the sort site corresponding to an interval is determined in a round robin fashion.
Claim 7
Dependent Claim
43 words
A method as defined in claim 1 the steps off: each sort site sorting one interval at a time, and storing the tuples at each sort site, in temporary files, using a single temporary file for each interval, prior to sorting the interval.
Claim 8
Dependent Claim
33 words
A method as defined in claim 6 wherein the method steps of reading, sorting, and sending the sorted tuples to the sink site proceed concurrently at different ones of the multiple sort sites.
Claim 9
Dependent Claim
25 words
A method as defined in claim 1 further comprising the step of selecting one of the multiple sort sites to serve as a coordinator site.
Claim 10
Dependent Claim
38 words
A method as defined in claim 8 further comprising the step of determining the global interval key values at the selected coordinator site and sending from the coordinator site the global interval key values to the storage sites.
Claim 11
Dependent Claim
53 words
A method as defined in claim 8 further comprising the steps of: generating and sorting a local sample on each storage site; sending a local random sample from each storage site to the selected coordinator site; and merging the local random samples on the designated coordinator site to provide a single global sample.
Claim 12
Dependent Claim
90 words
A method as defined in claim 10 wherein the method steps of generating and sorting a local sample and sending the local random sample from each storage site to the designated coordinator site and merging the local random samples on the designated coordinator site at one storage site, proceed concurrently with the steps of generating and sorting a local sample and sending the local random sample from each storage site to the designated coordinator site and merging the local random samples on the designated coordinator site at another storage site.
Claim 13
Dependent Claim
27 words
A method as defined in claim 1 wherein the set of tuples to be sorted are distributed from a set of initial sites to the storage sites.
Claim 14
Dependent Claim
21 words
A method as defined in claim 12 wherein the distribution of the tuples to the storage sites occurs in any fashion.
Claim 15
Dependent Claim
22 words
A method as defined in claim 13 wherein the distribution of the tuples to the storage sites occurs in a uniform fashion.
Claim 16
Dependent Claim
22 words
A method as defined in claim 13 wherein the distribution of the tuples to the storage sites occurs in a random fashion.
Claim 17
Dependent Claim
151 words
A computer program product for use in a node of a distributed database computer system having a plurality of nodes configured in a network, the nodes including a plurality of sort sites, each of the sort sites having a main memory, and each sort site having at least a predetermined memory capacity, for sorting of a relation wherein the relation is distributed over a plurality of storage sites and wherein the sorted relation is sent to a single sink site, the computer program product comprising: a) a recording medium; b) means recorded on said medium for instructing the distributed database computer system to determine global interval key values such that each interval fits in the predetermined memory capacity of a single sort site, notwithstanding that the number of a global interval key values might exceed the number of sort sites, wherein the tuples between two global key values define an interval.
Claim 18
Dependent Claim
151 words
A computer program product for use in a node of a distributed database computer system having a plurality of nodes configured in a network, the nodes including a plurality of sort sites, each of the sort sites having a main memory, and each sort site having at least a predetermined memory capacity, for sorting of a relation wherein the relation is distributed over a plurality of storage sites and wherein the sorted relation is sent to a single sink site, the computer program product comprising: a) a recording medium; b) means recorded on said medium for instructing the distributed database computer system to determine global interval key values such that each interval fits in the predetermined memory capacity of a single sort site, notwithstanding that the number of a global interval key values might exceed the number of sort sites, wherein the tuples between two global key values define an interval.
Claim 19
Dependent Claim
36 words
A computer program product as defined in claim 16 further comprising means, recorded on said medium, for instructing the distributed data base computer system to determine the global interval key values based on a global sample.
Claim 20
Dependent Claim
50 words
A computer program product as defined in claim 16 further comprising means, recorded on said medium, for instructing the distributed data base computer system to determine the global interval key values at the coordinator site and sending from the coordinator site the global interval key values to the storage sites.
Claim 21
Dependent Claim
65 words
A computer program product as defined in claim 16 further comprising means, recorded on said medium, for instructing the distributed data base computer system to repeat for each interval on each sort site the steps of: a) reading an interval; b) performing an in-memory sort in any fashion of the interval read; and c) sending the tuples of the sorted interval to the sink site.
Claim 22
Dependent Claim
32 words
A computer program product as defined in claim 16 further comprising means, recorded on said medium, for instructing the distributed data base computer system to select one coordinator site from any site.
Claim 23
Dependent Claim
69 words
A computer program product as defined in claim 20 further comprising means, recorded on said medium, for instructing the distributed data base computer system to generate and to sort a local sample on each storage site, to send the local random sample from each storage site to the selected coordinator site, and to merge the local random samples on the selected coordinator site to provide a single global sample.
Claim 24
Dependent Claim
66 words
A computer program product as defined in claim 16 wherein: each sort site includes means for storing one interval at a time; and the computer program product further comprises means, recorded on said medium, for instructing the distributed data base computer system to store the tuples at each sort site in temporary files using a single temporary file for each interval, prior to sorting the interval.
Claim 25
Dependent Claim
45 words
A computer program product as defined in claim 22 further comprising means, recorded on said medium, for instructing the distributed data base computer system to sort, and to send the sorted tuples to the sink site proceed concurrently at different ones of the storage sites.
Claim 26
Dependent Claim
57 words
A computer program product as defined in claim 16 further comprising means, recorded on said medium, for instructing the distributed data base computer system to scan at each storage site the relation distributed thereto and to determine for each tuple the assigned interval and the corresponding sort site and sending each tuple to the assigned sort site.
Claim 27
Dependent Claim
63 words
A computer program product as defined in claim 24 further comprising means, recorded on said medium, for instructing the distributed data base computer system to generate and to sort a local sample, to send the local random sample from each storage site to the designated coordinator site, and to merge the local random samples proceed concurrently at different ones of the storage sites.
Claim 28
Dependent Claim
71 words
A computer program product as defined in claim 24 further comprising means, recorded on said medium, for instructing the distributed data base computer system to send the global interval key values to the storage sites, to scan at each storage site the relation distributed thereto, to determine the assigned interval, and to store at each sort site the tuples in temporary files proceed concurrently at different ones of the storage sites.
Claim 29
Dependent Claim
181 words
A distributed relational database system for parallel sorting of a relation which is a set of tuples to be sorted on multiple sites, the system comprising: a) an interconnection network; b) one or more logical sites, each site having a least one processor with memory thereon in communication with the interconnection network, the logical sites including i) one or more storage sites, ii) two or more sort sites, each sort site having at least a predetermined memory capacity, iii) one or more sink sites, and iv) at least one coordinator site; and c) an executable program for performing a parallel sort, comprising the steps of: determining global interval key values such that interval fits in the predetermined memory capacity of a single sort site, notwithstanding that the number of global interval key values might exceed the number of sort sites, wherein the tuples between two global key values define an interval, scanning the relation distributed to each storage site, determining for each tuple an assigned interval and a corresponding assigned sort site, and sending each tuple to the assigned sort site.
Claim 30
Dependent Claim
181 words
A distributed relational database system for parallel sorting of a relation which is a set of tuples to be sorted on multiple sites, the system comprising: a) an interconnection network; b) one or more logical sites, each site having a least one processor with memory thereon in communication with the interconnection network, the logical sites including i) one or more storage sites, ii) two or more sort sites, each sort site having at least a predetermined memory capacity, iii) one or more sink sites, and iv) at least one coordinator site; and c) an executable program for performing a parallel sort, comprising the steps of: determining global interval key values such that interval fits in the predetermined memory capacity of a single sort site, notwithstanding that the number of global interval key values might exceed the number of sort sites, wherein the tuples between two global key values define an interval, scanning the relation distributed to each storage site, determining for each tuple an assigned interval and a corresponding assigned sort site, and sending each tuple to the assigned sort site.
Claim 31
Dependent Claim
38 words
A system as defined in claim 27 wherein the executable program comprises the further step of determining the global interval key based on a global sample of the tuples of the relation on the plurality of storage sites.
Claim 32
Dependent Claim
23 words
A system as defined in claim 27 wherein the global interval key values are sent from the coordinator site to the storage sites.
Claim 33
Dependent Claim
19 words
A system as defined in claim 27 wherein the coordinator site is selected from among the multiple sort sites.
Claim 34
Dependent Claim
53 words
A system as defined in claim 30 wherein a local sample is generated and sorted on each storage site site, the local random sample is sent from each storage site to the selected coordinator site, and the local random samples are merged on the selected coordinator site to provide a single global sample.
Claim 35
Dependent Claim
43 words
A system as defined in claim 17 wherein, for each interval on each sort site, the executable program includes reading the interval, performing and an in-memory sort of the interval read, and sending the tuples of the sorted interval to the sink site.
Claim 36
Dependent Claim
28 words
A system as defined in claim 27 wherein the logical sites further comprise a set of initial sites wherein the set of tuples to he sorted initially reside.
Claim 37
Dependent Claim
21 words
A system as defined in claim 27 wherein the distribution of the tuples to the storage sites occurs in any fashion.
Claim 38
Dependent Claim
48 words
A system as defined in claim 17, further comprising: means, operable at each sort site, for sorting one interval at a time, and means for storing the tuples at each sort site in temporary files using a single temporary file for each interval, prior to sorting the interval.
Claim 39
Dependent Claim
96 words
A system as defined in claim 35, wherein the executable program steps of sending the assignment of intervals to the storage sites, scanning at each storage site the relation distributed thereto and determining the assigned interval, and storing at each sort site the tuples in temporary files at one storage site proceed concurrently with the executable program steps of sending assignment of intervals to the storage sites, scanning at each storage site the relation distributed thereto and determining the assigned interval, and storing at each sort site the tuples in temporary files at another storage site.
Claim 40
Dependent Claim
235 words
A sort node, for use in a distributed relational database, the distributed relational database having a plurality of nodes configured in a network, the network including a plurality of sort sites and a sink site, each of the sort sites corresponding with a respective interval, and each sort site having at least a predetermined memory capacity, the respective intervals being defined as falling between adjacent ones of a sequence of interval key values, the sort node comprising: a) processor means for processing executable steps; b) memory means, associated with said processor means, for storing data; c) storage means for storing database information; d) communication hardware means for enabling said sort node to communicate across said network; e) means for receiving a set of global interval key values and intervals therebetween, such that a predetermined one of the intervals corresponds with said sort node and fits within the predetermined memory capacity of a respective one of the sort sites, notwithstanding that the number of a global interval key values might exceed the number of sort sites; f) means for storing tuples in temporary files at said sort node; and g) means for repeating, for each interval on each of the sort sites, the executable steps of: 1) reading an interval; 2) performing an in-memory sort of the tuples stored, for the internal read; and 3) sending the tuples of the sorted interval to the sink site.
Claim 41
Dependent Claim
235 words
A sort node, for use in a distributed relational database, the distributed relational database having a plurality of nodes configured in a network, the network including a plurality of sort sites and a sink site, each of the sort sites corresponding with a respective interval, and each sort site having at least a predetermined memory capacity, the respective intervals being defined as falling between adjacent ones of a sequence of interval key values, the sort node comprising: a) processor means for processing executable steps; b) memory means, associated with said processor means, for storing data; c) storage means for storing database information; d) communication hardware means for enabling said sort node to communicate across said network; e) means for receiving a set of global interval key values and intervals therebetween, such that a predetermined one of the intervals corresponds with said sort node and fits within the predetermined memory capacity of a respective one of the sort sites, notwithstanding that the number of a global interval key values might exceed the number of sort sites; f) means for storing tuples in temporary files at said sort node; and g) means for repeating, for each interval on each of the sort sites, the executable steps of: 1) reading an interval; 2) performing an in-memory sort of the tuples stored, for the internal read; and 3) sending the tuples of the sorted interval to the sink site.
Claim 42
Dependent Claim
235 words
A storage node, for use in a distributed relational database, the distributed relational database having a plurality of nodes configured in a network, the network including a designated coordinator site and a plurality of sort sites, each sort site having at least a predetermined memory capacity, the storage node comprising: a) processor means for processing executable steps; b) memory means, associated with said processor means, for storing data; c) storage means for storing database information; d) communication hardware means for enabling said storage node to communicate across said network, e) means for generating and sorting a local sample at said storage node; f) means for sending the local random sample from said storage node to the designated coordinator site; g) means for receiving a relation, the relation including a sequence of interval key values, intervals being defined between adjacent ones of the sequence of interval key values, such that each interval fits in the predetermined memory capacity of a single sort site, notwithstanding that the number of global interval key values might exceed the number of sort sites, each of the intervals corresponding with a respective one of the sort sites; h) means for scanning the relation and for determining, for each of a set of tuples to be sorted, an interval within which the tuple falls, and the corresponding sort site; and i) means for sending each tuple to another site across said network.
Claim 43
Dependent Claim
235 words
A storage node, for use in a distributed relational database, the distributed relational database having a plurality of nodes configured in a network, the network including a designated coordinator site and a plurality of sort sites, each sort site having at least a predetermined memory capacity, the storage node comprising: a) processor means for processing executable steps; b) memory means, associated with said processor means, for storing data; c) storage means for storing database information; d) communication hardware means for enabling said storage node to communicate across said network, e) means for generating and sorting a local sample at said storage node; f) means for sending the local random sample from said storage node to the designated coordinator site; g) means for receiving a relation, the relation including a sequence of interval key values, intervals being defined between adjacent ones of the sequence of interval key values, such that each interval fits in the predetermined memory capacity of a single sort site, notwithstanding that the number of global interval key values might exceed the number of sort sites, each of the intervals corresponding with a respective one of the sort sites; h) means for scanning the relation and for determining, for each of a set of tuples to be sorted, an interval within which the tuple falls, and the corresponding sort site; and i) means for sending each tuple to another site across said network.
Claim 44
Dependent Claim
198 words
A coordinator node, for use in a distributed relational database, the distributed relational database having a plurality of nodes configured in a network, the network including a plurality of other sites, the plurality of other sites including a plurality of sort sites, each of the sort sites having a main memory including at least a predetermined memory capacity, the coordinator node comprising: a) processor means for processing executable steps; b) memory means, associated with said processor means, for storing data; c) storage means for storing database information; d) communication hardware means for enabling said coordinator node to communicate across said network; e) means for merging local random samples on said coordinator node to provide a single global sample; f) means for determining a sequence of global key values such that the tuples between two adjacent ones of the sequence of global key values define a respective interval, and each respective interval fits in the predetermined memory capacity of a respective one of the sort sites, notwithstanding that the number of global interval key values might exceed the number of sort sites, and g) means for sending the global interval key values to the other sites across said network.
Claim 45
Dependent Claim
198 words
A coordinator node, for use in a distributed relational database, the distributed relational database having a plurality of nodes configured in a network, the network including a plurality of other sites, the plurality of other sites including a plurality of sort sites, each of the sort sites having a main memory including at least a predetermined memory capacity, the coordinator node comprising: a) processor means for processing executable steps; b) memory means, associated with said processor means, for storing data; c) storage means for storing database information; d) communication hardware means for enabling said coordinator node to communicate across said network; e) means for merging local random samples on said coordinator node to provide a single global sample; f) means for determining a sequence of global key values such that the tuples between two adjacent ones of the sequence of global key values define a respective interval, and each respective interval fits in the predetermined memory capacity of a respective one of the sort sites, notwithstanding that the number of global interval key values might exceed the number of sort sites, and g) means for sending the global interval key values to the other sites across said network.
References Cited (Backward Citations)
US4210961B1
Cited
US4210961A
Cited
US4559612A
Cited
US4595995A
Cited
US4520456A
Cited
US4567572A
Cited
US4575798A
Cited
US4809214A
Cited
US4799152A
Cited
US4766534A
Cited
US5086408A
Cited
US5146590A
Cited
US5179699A
Cited
GB2235798A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-11-30 | 2002-06-01 | 2002-12-01 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-11-30 | 2006-06-01 | 2006-12-01 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-11-30 | 2010-06-01 | 2010-12-01 | $7700.00 | Window Closed / Lapsed |