Patent US6115705A successfully refreshed from Google Patents.
US6115705A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Relational database system and method for query processing using early aggregation
Assignee: Microsoft Technology Licensing LLC
•
Filing: 1997-05-19
•
Granted: 2000-09-05
•
Expires: 2017-05-19
Abstract
Abstract A relational database system has a non-volatile memory, a volatile memory for temporarily storing a set of data records, and a query processor. The volatile memory has an amount of available space for query processing that is segmented into multiple memory pages. Initially, these memory pages are empty and available in a pool for use by the query processor. The query processor establishes a partition table that defines multiple partitions. The query processor partitions incoming data records into the partitions according to a hashing function and stores the data records in memory pages associated with the partitions. As a new data record placed into a particular partition, the query processor attempts to aggregate the new data record with any like data record that already exists in the particular partition. If no like data record exists, the data record is stored separately on the memory page within the partition. In the event that a memory page of the partition becomes filled, the query processor retrieves an empty memory page from the free pool and assigns that empty memory page to the needy partition. In the event that no free memory pages are left in the pool, the query processor selects a memory page from any one of the partitions and writes the data records on the selected memory page to the non-volatile memory to free the memory page. The query processor selects the memory page according to selection criteria that favors output of full memory pages over partially filled memory pages and that favors memory pages with a low absorption rate. Data records with low activity are written to non-volatile memory in the interest of preserving data records with high absorption rates on the memory pages with the hope of absorbing future data records.
Inventors
- 👤 Per-Åke Larson
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-29 07:31
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/20; G06F16/24; G06F16/245; G06F16/2455; G06F16/24553; G06F16/24554; G06F16/24556; G06F16/24561; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99933; Y10S707/99934
Claims Analysis
Total Claims: 67
Claim 1
Independent Claim
156 words
A relational database system comprising: a non-volatile memory; a volatile memory for temporarily storing a set of data records, the volatile memory having an amount of space available for query processing; a query processor coupled to the non-volatile and volatile memories to process a query of the data records according to at least one query parameter, the query processor being configured to partition the data records into multiple buckets for query processing using the available space in the volatile memory; and the query processor being configured to aggregate data records having like query parameters and to occasionally select ones of the data records for writing to the non-volatile memory to free up part of the available space to receive additional data records, the query processor selecting the data records for writing to the non-volatile memory according to how likely the data records will aggregate, if left in the buckets, with the data records to be added.
Claim 2
Dependent Claim
156 words
A relational database system comprising: a non-volatile memory; a volatile memory for temporarily storing a set of data records, the volatile memory having an amount of space available for query processing; a query processor coupled to the non-volatile and volatile memories to process a query of the data records according to at least one query parameter, the query processor being configured to partition the data records into multiple buckets for query processing using the available space in the volatile memory; and the query processor being configured to aggregate data records having like query parameters and to occasionally select ones of the data records for writing to the non-volatile memory to free up part of the available space to receive additional data records, the query processor selecting the data records for writing to the non-volatile memory according to how likely the data records will aggregate, if left in the buckets, with the data records to be added.
Claim 3
Dependent Claim
22 words
A relational database system as recited in claim 1, wherein the query processor partitions the data records using a hash partitioning process.
Claim 4
Dependent Claim
28 words
A relational database system as recited in claim 1, wherein the query processor selects the data records having the least absorption rate for writing to the non-volatile memory.
Claim 5
Dependent Claim
29 words
A relational database system as recited in claim 1, wherein the query processor selects the data records that have been least recently aggregated for writing to the non-volatile memory.
Claim 6
Dependent Claim
41 words
A relational database system as recited in claim 1, wherein the query processor dynamically utilizes the available space among different ones of the buckets without requiring a specific quantity of available space be reserved for any particular one of the buckets.
Claim 7
Dependent Claim
44 words
A relational database system as recited in claim 1, wherein the query processor distinguishes between "unsafe" buckets from which the selected data records are written to the non-volatile memory and "safe" buckets that have not yet had data records written to the non-volatile memory.
Claim 8
Dependent Claim
47 words
A relational database system as recited in claim 1, wherein the query processor selects and writes at least one data record to the non-volatile memory in an event that addition of a new data record causes an overflow condition indicating that the available space will be exceeded.
Claim 9
Dependent Claim
21 words
A relational database system as recited in claim 1, wherein the available space is configured as a pool of memory pages.
Claim 10
Dependent Claim
22 words
A relational database system as recited in claim 8, wherein the query processor initially allocates at least one memory page per bucket.
Claim 11
Dependent Claim
28 words
A relational database system as recited in claim 8, wherein the query processor moves an empty memory page from one of the buckets to another of the buckets.
Claim 12
Dependent Claim
37 words
A relational database system as recited in claim 8, wherein when the query processor selects a data record to write to the non-volatile memory, the query processor writes a memory page that contains the selected data record.
Claim 13
Dependent Claim
72 words
A relational database system as recited in claim 8, wherein the query processor partitions the data records into memory pages associated with corresponding buckets, and in an event that addition of a new data record to one of the buckets causes an overflow condition indicating that all of the memory pages are full, the query processor selects the data records for writing to the non-volatile memory from any one of the buckets.
Claim 14
Dependent Claim
141 words
A relational database system comprising: a non-volatile memory; a volatile memory for temporarily storing a set of data records, the volatile memory having an amount of space available for query processing; a query processor coupled to the non-volatile and volatile memories to process a query of the data records according to at least one query parameter, the query processor being configured to partition the data records into multiple buckets for query processing using the available space in the volatile memory; and the query processor being configured to aggregate data records having like query parameters and to occasionally select ones of the data records for writing to the non-volatile memory to free up part of the available space to receive additional data records, the query processor selecting the data records for writing to the non-volatile memory from any one of the buckets.
Claim 15
Dependent Claim
141 words
A relational database system comprising: a non-volatile memory; a volatile memory for temporarily storing a set of data records, the volatile memory having an amount of space available for query processing; a query processor coupled to the non-volatile and volatile memories to process a query of the data records according to at least one query parameter, the query processor being configured to partition the data records into multiple buckets for query processing using the available space in the volatile memory; and the query processor being configured to aggregate data records having like query parameters and to occasionally select ones of the data records for writing to the non-volatile memory to free up part of the available space to receive additional data records, the query processor selecting the data records for writing to the non-volatile memory from any one of the buckets.
Claim 16
Dependent Claim
45 words
A relational database system as recited in claim 13, wherein the query processor selects the data records for writing to the non-volatile memory according to how likely the data records will aggregate, if left in the buckets, with the additional data records to be added.
Claim 17
Dependent Claim
28 words
A relational database system as recited in claim 13, wherein the query processor selects the data records having the least absorption rate for writing to the non-volatile memory.
Claim 18
Dependent Claim
29 words
A relational database system as recited in claim 13, wherein the query processor selects the data records that have been least recently aggregated for writing to the non-volatile memory.
Claim 19
Dependent Claim
50 words
A relational database system as recited in claim 13, wherein the query processor distinguishes between first ones of the buckets from which the selected data records are written to the non-volatile memory and second ones of the buckets that have not yet had data records written to the non-volatile memory.
Claim 20
Dependent Claim
21 words
A relational database system as recited in claim 13, wherein the available space is configured as a pool of memory pages.
Claim 21
Dependent Claim
22 words
A relational database system as recited in claim 18, wherein the query processor initially allocates at least one memory page per bucket.
Claim 22
Dependent Claim
21 words
A relational database system as recited in claim 18, wherein the query processor dynamically moves empty memory pages among the buckets.
Claim 23
Dependent Claim
37 words
A relational database system as recited in claim 18, wherein when the query processor selects a data record to write to the non-volatile memory, the query processor writes a memory page that contains the selected data record.
Claim 24
Dependent Claim
104 words
A relational database system comprising: a volatile memory for temporarily storing a set of data records for query processing; a query processor coupled to the volatile memory to process a query of the data records, the query processor being configured to partition the data records into multiple partitions using a hash partitioning table, the hash partitioning table having entries that reference the partitions; and the query processor being configured to create a second hash table separate from the partitioning table that has entries that reference individual data records within the partitions, the separate hash table being used to lookup matching data records for aggregation.
Claim 25
Dependent Claim
104 words
A relational database system comprising: a volatile memory for temporarily storing a set of data records for query processing; a query processor coupled to the volatile memory to process a query of the data records, the query processor being configured to partition the data records into multiple partitions using a hash partitioning table, the hash partitioning table having entries that reference the partitions; and the query processor being configured to create a second hash table separate from the partitioning table that has entries that reference individual data records within the partitions, the separate hash table being used to lookup matching data records for aggregation.
Claim 26
Dependent Claim
201 words
A relational database system comprising: a non-volatile memory; a volatile memory for temporarily storing a set of data records, the volatile memory having an amount of available space segmented into multiple memory pages; a query processor coupled to the non-volatile and volatile memories to process a series of data records, the query processor being configured to partition the data records into multiple partitions and store the data records in one or more memory pages associated with the partitions; as a new data record is processed into a particular partition, the query processor being configured to alternately aggregate the new data record with a like data record already existing in the particular partition or store the data record separately within the particular partition; in an event that a memory page of the particular partition becomes full, the query processor assigns an additional memory page to the particular partition; and in an event that no free memory pages are left to assign, the query processor selects a memory page from any one of the partitions, writes the data records on the selected memory page to the non-volatile memory to empty the memory page, and moves the emptied memory page to the particular partition.
Claim 27
Dependent Claim
201 words
A relational database system comprising: a non-volatile memory; a volatile memory for temporarily storing a set of data records, the volatile memory having an amount of available space segmented into multiple memory pages; a query processor coupled to the non-volatile and volatile memories to process a series of data records, the query processor being configured to partition the data records into multiple partitions and store the data records in one or more memory pages associated with the partitions; as a new data record is processed into a particular partition, the query processor being configured to alternately aggregate the new data record with a like data record already existing in the particular partition or store the data record separately within the particular partition; in an event that a memory page of the particular partition becomes full, the query processor assigns an additional memory page to the particular partition; and in an event that no free memory pages are left to assign, the query processor selects a memory page from any one of the partitions, writes the data records on the selected memory page to the non-volatile memory to empty the memory page, and moves the emptied memory page to the particular partition.
Claim 28
Dependent Claim
51 words
A relational database system as recited in claim 23, wherein the query processor selects the memory page according to selection criteria that favors output of full memory pages over partially filled memory pages and that favors memory pages with a low absorption rate over memory pages with a high absorption rate.
Claim 29
Dependent Claim
25 words
A relational database system as recited in claim 23, wherein the query processor moves empty memory pages among the partitions to satisfy incoming data records.
Claim 30
Dependent Claim
27 words
A relational database system as recited in claim 23, wherein the query processor transfers all memory pages from one of the partitions to others of the partitions.
Claim 31
Dependent Claim
47 words
A relational database system as recited in claim 23, wherein the query processor distinguishes between first partitions from which one or more memory pages are written to the non-volatile memory and second partitions that have not yet had any associated memory page written to the non-volatile memory.
Claim 32
Dependent Claim
84 words
A relational database computer program embodied on a computer-readable medium comprising: partitioning code to partition data records into multiple partitions; aggregation code to aggregate within respective partitions like data records; and victim selection code to select at least one data record to write to non-volatile memory to free space in the partitions for future data records, the victim selection code selecting the data record according to how likely that data record will aggregate, if left in its respective partition, with the future data records.
Claim 33
Dependent Claim
84 words
A relational database computer program embodied on a computer-readable medium comprising: partitioning code to partition data records into multiple partitions; aggregation code to aggregate within respective partitions like data records; and victim selection code to select at least one data record to write to non-volatile memory to free space in the partitions for future data records, the victim selection code selecting the data record according to how likely that data record will aggregate, if left in its respective partition, with the future data records.
Claim 34
Dependent Claim
23 words
A relational database computer program as recited in claim 28, wherein the partitioning code partitions the data records using a hash partitioning process.
Claim 35
Dependent Claim
24 words
A relational database computer program as recited in claim 28, wherein the victim selection code selects the data record with the least absorption rate.
Claim 36
Dependent Claim
25 words
A relational database computer program as recited in claim 28, wherein the victim selection code selects the data record that has been least recently aggregated.
Claim 37
Dependent Claim
29 words
A relational database system comprising: a memory; and a processing unit coupled to the memory and configured to execute the relational database computer program as recited in claim 28.
Claim 38
Dependent Claim
44 words
In a relational database system having data records that are partitioned into partitions and aggregated within the partitions, a query processing program executable on the relational database system to remove at least one data record that has the least absorption rate from a partition.
Claim 39
Dependent Claim
44 words
In a relational database system having data records that are partitioned into partitions and aggregated within the partitions, a query processing program executable on the relational database system to remove at least one data record that has the least absorption rate from a partition.
Claim 40
Dependent Claim
21 words
A query processing program as recited in claim 33, further configured to remove the data record that is least recently aggregated.
Claim 41
Dependent Claim
22 words
A query processing program as recited in claim 33, further configured to remove the data record from any one of the partitions.
Claim 42
Dependent Claim
20 words
A relational database computer program embodied on a computer-readable medium comprising the query processing program as recited in claim 33.
Claim 43
Dependent Claim
81 words
In a relational database system having data records that are partitioned into partitions and aggregated within the partitions, a query processing program executable on the relational database system to add data records to respective partitions until an overflow condition in a particular partition is reached indicating that that memory space available for the partitions is full, the query processing program removing at least one data record from any one of the partitions to free memory space to receive future data records.
Claim 44
Dependent Claim
81 words
In a relational database system having data records that are partitioned into partitions and aggregated within the partitions, a query processing program executable on the relational database system to add data records to respective partitions until an overflow condition in a particular partition is reached indicating that that memory space available for the partitions is full, the query processing program removing at least one data record from any one of the partitions to free memory space to receive future data records.
Claim 45
Dependent Claim
22 words
A query processing program as recited in claim 37, further configured to remove the data record that has the least absorption rate.
Claim 46
Dependent Claim
21 words
A query processing program as recited in claim 37, further configured to remove the data record that is least recently aggregated.
Claim 47
Dependent Claim
20 words
A relational database computer program embodied on a computer-readable medium comprising the query processing program as recited in claim 37.
Claim 48
Dependent Claim
37 words
In a relational database system having multiple memory pages for holding data records that are separated into predefined partitions, a query processing program executable on the relational database system to move empty memory pages among the partitions.
Claim 49
Dependent Claim
37 words
In a relational database system having multiple memory pages for holding data records that are separated into predefined partitions, a query processing program executable on the relational database system to move empty memory pages among the partitions.
Claim 50
Dependent Claim
50 words
A query processing program as recited in claim 41, further configured to aggregate the data records within the partitions wherein the partitions having the data records with the highest absorption rates tend to have associated more memory pages that the partitions having the data records with the lowest absorption rates.
Claim 51
Dependent Claim
20 words
A relational database computer program embodied on a computer-readable medium comprising the query processing program as recited in claim 41.
Claim 52
Independent Claim
65 words
A method for processing a query, comprising the following steps: partitioning data records into multiple partitions; aggregating within respective partitions like data records; and selecting at least one data record to write to non-volatile memory to free space in the partitions for future data records according to how likely that data record will aggregate, if left in its respective partition, with the future data records.
Claim 53
Independent Claim
65 words
A method for processing a query, comprising the following steps: partitioning data records into multiple partitions; aggregating within respective partitions like data records; and selecting at least one data record to write to non-volatile memory to free space in the partitions for future data records according to how likely that data record will aggregate, if left in its respective partition, with the future data records.
Claim 54
Dependent Claim
24 words
A method as recited in claim 44, wherein the partitioning step comprises the step of partitioning the data records using a hash partitioning process.
Claim 55
Dependent Claim
36 words
A method as recited in claim 44, wherein the aggregating step comprises the step of hashing each new data record to an entry in a hash table which references any like data records in the partitions.
Claim 56
Dependent Claim
24 words
A method as recited in claim 44, wherein the selecting step comprises the step of selecting the data record with the least absorption rate.
Claim 57
Dependent Claim
25 words
A method as recited in claim 44, wherein the selecting step comprises the step of selecting the data record that has been least recently aggregated.
Claim 58
Dependent Claim
15 words
A computer programmed to perform the steps in the method as recited in claim 44.
Claim 59
Dependent Claim
18 words
A computer-readable medium having computer-executable instructions for performing the steps in the method as recited in claim 44.
Claim 60
Dependent Claim
167 words
In a relational database system having multiple memory pages for holding data records that are separated into predefined partitions, a method for processing a query of the data records, comprising the following steps: partitioning a new data record into one of the partitions; if a like data record already exists in the partition, aggregating the new data record with the like data record and otherwise storing the data record separately within the partition; in an event that a memory page of the partition is full and cannot accept the new data entry, adding a next memory page to the partition; and in an event that no free memory pages are left to add, selecting a memory page from any one of the partitions according to a selection criteria that favors output of full memory pages over partially filled memory pages and that favors memory pages with low absorption rates and writing the data records on the selected memory page to non-volatile memory to empty the memory page.
Claim 61
Dependent Claim
167 words
In a relational database system having multiple memory pages for holding data records that are separated into predefined partitions, a method for processing a query of the data records, comprising the following steps: partitioning a new data record into one of the partitions; if a like data record already exists in the partition, aggregating the new data record with the like data record and otherwise storing the data record separately within the partition; in an event that a memory page of the partition is full and cannot accept the new data entry, adding a next memory page to the partition; and in an event that no free memory pages are left to add, selecting a memory page from any one of the partitions according to a selection criteria that favors output of full memory pages over partially filled memory pages and that favors memory pages with low absorption rates and writing the data records on the selected memory page to non-volatile memory to empty the memory page.
Claim 62
Dependent Claim
25 words
A method as recited in claim 51, wherein the partitioning step comprises the step of partitioning the new data record using a hash partitioning process.
Claim 63
Dependent Claim
25 words
A method as recited in claim 51, further comprising the step of moving the empty memory page to another partition to satisfy incoming data records.
Claim 64
Dependent Claim
26 words
A method as recited in claim 51, further comprising the step of transferring all memory pages from one of the partitions to others of the partitions.
Claim 65
Dependent Claim
43 words
A method as recited in claim 51, further comprising distinguishing between first partitions from which one or more memory pages are written to the non-volatile memory and second partitions that have not yet had any associated memory page written to the non-volatile memory.
Claim 66
Dependent Claim
15 words
A computer programmed to perform the steps in the method as recited in claim 51.
Claim 67
Dependent Claim
18 words
A computer-readable medium having computer-executable instructions for performing the steps in the method as recited in claim 51.
References Cited (Backward Citations)
US5055999A
Cited
US5548769A
Cited
US5367675A
Cited
US5742806A
Cited
US5584024A
Cited
US5655080A
Cited
US5864842A
Cited
US5832475A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-09-05 | 2004-03-06 | 2004-09-05 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-09-05 | 2008-03-06 | 2008-09-05 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-09-05 | 2012-03-06 | 2012-09-05 | $7700.00 | Window Closed / Lapsed |