Relational database system and method for query processing using early aggregation

• US 6,115,705 A
• Filed: 05/19/1997
• Issued: 09/05/2000
• Est. Priority Date: 05/19/1997
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Larson, Per-.ANG.ke
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Coby, Frantz
• Application Number:
  US08/858,864
• Time in Patent Office: 1,205 Days
• Field of Search: 707/1, 707/2, 707/3, 707/4
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24556 Aggregation; Duplicate elimination
• CPC Class Codes: G06F 16/24561 Intermediate data storage techniques for performance improvement
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation

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.

Claims

1. 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.

2. A relational database system as recited in claim 1, wherein the query processor partitions the data records using a hash partitioning process.

3. 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.

4. 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.

5. 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.

6. 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.

7. 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.

8. A relational database system as recited in claim 1, wherein the available space is configured as a pool of memory pages.

9. A relational database system as recited in claim 8, wherein the query processor initially allocates at least one memory page per bucket.

10. 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.

11. 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.

12. 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.

13. 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.

14. 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.

15. 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.

16. 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.

17. 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.

18. A relational database system as recited in claim 13, wherein the available space is configured as a pool of memory pages.

19. A relational database system as recited in claim 18, wherein the query processor initially allocates at least one memory page per bucket.

20. A relational database system as recited in claim 18, wherein the query processor dynamically moves empty memory pages among the buckets.

21. 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.

22. 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.

23. 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.

24. 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.

25. 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.

26. 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.

27. 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.

28. 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.

29. A relational database computer program as recited in claim 28, wherein the partitioning code partitions the data records using a hash partitioning process.

30. A relational database computer program as recited in claim 28, wherein the victim selection code selects the data record with the least absorption rate.

31. 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.

32. 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.

33. 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.

34. A query processing program as recited in claim 33, further configured to remove the data record that is least recently aggregated.

35. A query processing program as recited in claim 33, further configured to remove the data record from any one of the partitions.

36. A relational database computer program embodied on a computer-readable medium comprising the query processing program as recited in claim 33.

37. 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.

38. A query processing program as recited in claim 37, further configured to remove the data record that has the least absorption rate.

39. A query processing program as recited in claim 37, further configured to remove the data record that is least recently aggregated.

40. A relational database computer program embodied on a computer-readable medium comprising the query processing program as recited in claim 37.

41. 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.

42. 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.

43. A relational database computer program embodied on a computer-readable medium comprising the query processing program as recited in claim 41.

44. 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.

45. A method as recited in claim 44, wherein the partitioning step comprises the step of partitioning the data records using a hash partitioning process.

46. 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.

47. A method as recited in claim 44, wherein the selecting step comprises the step of selecting the data record with the least absorption rate.

48. 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.

49. A computer programmed to perform the steps in the method as recited in claim 44.

50. A computer-readable medium having computer-executable instructions for performing the steps in the method as recited in claim 44.

51. 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.

52. 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.

53. 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.

54. 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.

55. 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.

56. A computer programmed to perform the steps in the method as recited in claim 51.

57. A computer-readable medium having computer-executable instructions for performing the steps in the method as recited in claim 51.