Apparatus and method for aggregate indexes

• US 6,487,546 B1
• Filed: 08/27/1998
• Issued: 11/26/2002
• Est. Priority Date: 08/27/1998
• Status: Expired due to Term

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle Corporation
• Inventors: Witkowski, Andrew
• Primary Examiner(s): Coby, Frantz
• Application Number:
  US09/141,345
• Time in Patent Office: 1,552 Days
• Field of Search: 707/1, 707/2, 707/3, 707/4, 707/5, 707/7, 707/100, 707/103.R, 707/104.1, 707/104
• US Class Current: 1/1
• CPC Class Codes: G06F 16/284 Relational databases
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99937 Sorting
• CPC Class Codes: Y10S 707/99944 Object-oriented database structure
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

An aggregate index is used for accessing an aggregate value associated with one or more rows of a database table. The aggregate values are stored in the index entries of the index, thus allowing determination of aggregate values without accessing the underlying database table. The aggregate index is created by determining an aggregate value associated with an index entry, and storing the aggregate value with the index entry. The aggregate value is determined by accessing information corresponding to the index entry and processing the information. In the case of an index entry in the form of a branch node, the information might be aggregate values from other nodes, or values of items in the database pointed to by the index entries that are leaf nodes. The aggregate values may be stored in index entries of any type of index.

Claims

1. A method for storing aggregate information in an entry of a database index for a database table, comprising:

storing, in the entry that corresponds to a key value, information that indicates where two or more database table rows that have the key value are located in the database table;

computing first aggregate information based on an aggregate operation and said two or more database table rows; and

storing the first aggregate information in the entry.

2. The method of claim 1, further including:

accessing values in the two or more database table rows; and

wherein the step of computing the first aggregate information is performed by performing the aggregate operation based on the values.

3. The method of claim 1, further including:

accessing second aggregate information stored in the entry; and

wherein the step of computing the first aggregate information uses the second aggregate information.

4. The method of claim 1, wherein the first aggregate information represents a sum of values stored in a column of the two or more database table rows.

5. The method of claim 1, wherein the first aggregate information represents an average of values stored in a column of the two or more database table rows.

6. The method of claim 1, wherein the first aggregate information represents a count of the two or more database table rows.

7. The method of claim 1, wherein the first aggregate information represents a minimum among values stored in a column of the two or more database table rows.

8. The method of claim 1, wherein the first aggregate information represents a maximum among values stored in a column of the two or more database table rows.

61. The method of claim 1, wherein the step of storing, in the entry that corresponds to the key value, information that indicates where said two or more database table rows that have the key value are located in the database table comprises the step of:

storing, in the entry that corresponds to the key value, information that specifies a row identifier that identifies where said two or more database table rows that have the key value are located in the database table.

62. The method of claim 1, wherein the step of computing the first aggregate information comprises the step of:

computing the first aggregate information based on the aggregate operation and at least one value from each of said two or more database table rows.

9. A computer-readable medium having stored thereon sequences of instructions for storing aggregate information in an entry of a database index for a database table, the sequences of instructions including instructions which, when executed by a processor, cause the processor to perform the steps of:

storing, in the entry that corresponds to a key value, information that indicates where two or more database table rows that have the key value are located in the database table;

computing first aggregate information based on an aggregate operation and said two or more database table rows; and

storing the first aggregate information in the entry.

10. The computer-readable medium of claim 9, further including instructions for:

accessing values in the two or more database table rows; and

wherein the instructions for computing the first aggregate information include instructions for performing the aggregate operation based on the values.

11. The computer-readable medium of claim 9, further including instructions for:

accessing second aggregate information stored in the entry; and

wherein the instructions for computing the first aggregate information use the second aggregate information.

12. The computer-readable medium of claim 9, wherein the first aggregate information represents a sum of values stored in a column of the two or more database table rows.

13. The computer-readable medium of claim 9, wherein the first aggregate information represents an average of values stored in a column of the two or more database table rows.

14. The computer-readable medium of claim 9, wherein the first aggregate information represents a count of the two or more database table rows.

15. The computer-readable medium of claim 9, wherein the first aggregate information represents a minimum among values stored in a column of the two or more database table rows.

16. The computer-readable medium of claim 9, wherein the first aggregate information represents a maximum among values stored in a column of the two or more database table rows.

63. The computer-readable medium of claim 9, wherein the instructions for storing, in the entry that corresponds to the key value, information that indicates where said two or more database table rows that have the key value are located in the database table include instructions for:

storing, in the entry that corresponds to the key value, information that specifies a row identifier that identifies where said two or more database table rows that have the key value are located in the database table.

64. The computer-readable medium of claim 9, wherein the instructions for computing the first aggregate information include instructions for:

computing the first aggregate information based on the aggregate operation and at least one value from each of said two or more database table rows.

17. A method for storing aggregate information in a first entry of a database index for a database table, comprising:

storing, in the first entry that corresponds to a range of key values, information that indicates where two or more database table rows that have respective key values are located in the database table, wherein each of said key values is within the range of key values;

computing first aggregate information based on an aggregate operation and said two or more database table rows; and

storing the first aggregate information in the first entry.

18. The method according to claim 17, further including:

accessing second aggregate information stored in a second entry of the database index; and

wherein the step of computing the first aggregate information uses the second aggregate information.

19. The method according to claim 17, further including:

accessing data in one or more database table rows having respective key values in the range of key values; and

wherein the step of computing the first aggregate information uses the data.

20. The method of claim 17, wherein the first aggregate information represents an average of values stored in a column of the two or more database table rows.

21. The method of claim 17, wherein the first aggregate information represents a count of the two or more database table rows.

22. The method of claim 17, wherein the first aggregate information represents a minimum among values stored in a column of the two or more database table rows.

23. The method of claim 17, wherein the first aggregate information represents a maximum among values stored in a column of the two or more database table rows.

57. The method of claim 17, wherein the first aggregate information represents a sum of values stored in a column of the two or more database table rows.

65. The method of claim 17, wherein the step of storing, in the first entry that corresponds to the range of key values, information that indicates where said two or more database table rows that have respective key values are located in the database table comprises the step of:

storing, in the first entry that corresponds to the range of key values, information that specifies a row identifier that identifies where said two or more database table rows that have respective key values are located in the database table.

66. The method of claim 17, wherein the step of computing the first aggregate information comprises the step of:

computing the first aggregate information based on the aggregate operation and at least one value from each of said two or more database table rows.

24. A computer-readable medium having stored thereon sequences of instructions for storing aggregate information in a first entry of a database index for a database table, the sequences of instructions including instructions which, when executed by a processor, cause the processor to perform the steps of:

storing, in the first entry that corresponds to a range of key values, information that indicates where two or more database table rows that have respective key values are located in the database table, wherein each of said key values is within the range of key values;

computing first aggregate information based on an aggregate operation and said two or more database table rows; and

storing the first aggregate information in the first entry.

25. The computer-readable medium of claim 24, further including:

accessing second aggregate information stored in a second entry of the database index; and

wherein the instructions for computing the first aggregate information use the second aggregate information.

26. The computer-readable medium of claim 24, further including instructions for:

accessing data in one or more database table rows having respective key values in the range of key values; and

wherein the instructions for computing the first aggregate information use the data.

27. The computer-readable medium of claim 24, wherein the first aggregate information represents an average of values stored in a column of the two or more database table rows.

28. The computer-readable medium of claim 24, wherein the first aggregate information represents a count of the two or more database table rows.

29. The computer-readable medium of claim 24, wherein the first aggregate information represents a minimum among values stored in a column of the two or more database table rows.

30. The computer-readable medium of claim 24, wherein the first aggregate information represents a maximum among values stored in a column of the two or more database table rows.

58. The computer-readable medium of claim 24, wherein the first aggregate information represents a sum of values stored in a column of the two or more database table rows.

67. The computer-readable medium of claim 24, wherein the instructions for storing, in the first entry that corresponds to the range of key values, information that indicates where said two or more database table rows that have respective key values are located in the database table include instructions for:

storing, in the first entry that corresponds to the range of key values, information that specifies a row identifier that identifies where said two or more database table rows that have respective key values are located in the database table.

68. The computer-readable medium of claim 24, wherein the instructions for computing the first aggregate information include instructions for:

computing the first aggregate information based on the aggregate operation and at least one value from each of said two or more database table rows.

31. A method for accessing aggregate information stored in an entry of a database index for a database table, comprising:

storing, in the entry that corresponds to a key value, information that indicates where two or more database table rows that have the key value are located in the database table;

receiving a database query requiring information based on said two or more database table rows;

accessing aggregate information from the entry; and

providing an aggregate value using the aggregate information.

32. The method of claim 31, wherein the database index is implemented as a tree and the step of accessing includes:

traversing the database index to a leaf node containing the aggregate information.

33. The method of claim 31, wherein the database index is implemented as a tree and the step of accessing includes:

traversing the database index to a branch node containing the aggregate information.

34. The method of claim 31, wherein the aggregate information represents an average of values stored in a column of the two or more database table rows.

35. The method of claim 31, wherein the aggregate information represents a count of the two or more database table rows.

36. The method of claim 31, wherein the aggregate information represents a minimum among values stored in a column of the two or more database table rows.

37. The method of claim 31, wherein the aggregate information represents a maximum among values stored in a column of the two or more database table rows.

59. The method of claim 31, wherein the aggregate information represents a sum of values stored in a column of the two or more database table rows.

69. The method of claim 31, wherein the step of storing, in the entry that corresponds to the key value, information that indicates where said two or more database table rows that have the key value are located in the database table comprises the step of:

storing, in the entry that corresponds to the key value, information that specifies a row identifier that identifies where said two or more database table rows that have the key value are located in the database table.

70. The method of claim 31, wherein the step of receiving the database query requiring the aggregate value comprises the step of:

receiving the database query requiring the information based on at least one value from each of said two or more database table rows.

38. A computer-readable medium having stored thereon sequences of instructions for accessing aggregate information stored in an entry of a database index for a database table, the sequences of instructions including instructions which, when executed by a processor, cause the processor to perform the steps of:

storing, in the entry that corresponds to a key value, information that indicates where two or more database table rows that have the key value are located in the database table;

receiving a database query requiring information based on said two or more database table rows;

accessing aggregate information from the entry; and

providing an aggregate value using the aggregate information.

39. The computer-readable medium of claim 38, wherein the database index is implemented as a tree, and the instructions for accessing include instructions for:

traversing the database index to a leaf node containing the aggregate information.

40. The computer-readable medium of claim 38, wherein the database index is implemented as a tree, and the instructions for accessing include instructions for:

traversing the database index to a branch node containing the aggregate information.

41. The computer-readable medium of claim 38, wherein the aggregate information represents an average of values stored in a column of the two or more database table rows.

42. The computer-readable medium of claim 38, wherein the aggregate information represents a count of the two or more database table rows.

43. The computer-readable medium of claim 38, wherein the aggregate information represents a minimum among values stored in a column of the two or more database table rows.

44. The computer-readable medium of claim 38, wherein the aggregate information represents a maximum among values stored in a column of the two or more database table rows.

60. The computer-readable medium of claim 38, wherein the aggregate information represents a sum of values stored in a column of the two or more database table rows.

71. The computer-readable medium of claim 38, wherein the instructions for storing, in the entry that corresponds to the key value, information that indicates where said two or more database table rows that have the key value are located in the database table include instructions for:

storing, in the entry that corresponds to the key value, information that specifies a row identifier that identifies where said two or more database table rows that have the key value are located in the database table.

72. The computer-readable medium of claim 38, wherein the instructions for receiving the database query requiring the aggregate value include instructions for:

receiving the database query requiring the information based on at least one value from each of said two or more database table rows.

45. A method for updating aggregate information in an entry of a database index for a database table, comprising:

storing, in the entry that corresponds to a key value, information that indicates where two or more database table rows that have the key value are located in the database table;

storing aggregate information in the entry;

performing a database table operation related to the key value; and

updating the aggregate information in accordance with the database table operation.

46. The method of claim 45, wherein the step of performing the database table operation includes:

inserting a database table row into the database table.

47. The method of claim 45, wherein the step of performing the database table operation includes:

deleting a database table row from the database table.

48. The method of claim 45, wherein the step of performing the database table operation includes:

modifying a database table row in the database table.

49. The method of claim 45, wherein the step of updating the aggregate information includes:

reading first aggregate information from the entry;

computing second aggregate information using the first aggregate information and a value that is affected by the database table operation; and

storing the second aggregate information in the entry.

50. The method of claim 45, wherein the step of updating the aggregate information includes:

reading database table information from the two or more database table rows after completion of the database table operation;

computing new aggregate information based on the database table information; and

storing the new aggregate information in the entry.

73. The method of claim 45, wherein the step of storing, in the entry that corresponds to the key value, information that indicates where said two or more database table rows that have the key value are located in the database table comprises the step of:

storing, in the entry that corresponds to the key value, information that specifies a row identifier that identifies where said two or more database table rows that have the key value are located in the database table.

51. A computer-readable medium having stored thereon sequences of instructions for updating aggregate information in an entry of a database index for a database table, the sequences of instructions including instructions which, when executed by a processor, cause the processor to perform the steps of:

storing, in the entry that corresponds to a key value, information that indicates where two or more database table rows that have the key value are located in the database table;

storing aggregate information in the entry;

performing a database table operation related to the key value; and

updating the aggregate information in accordance with the database table operation.

52. The computer-readable medium of claim 51, wherein the instructions for performing the database table operation include instructions for:

inserting a database table row into the database table.

53. The computer-readable medium of claim 51, wherein the instructions for performing the database table operation include instructions for:

deleting a database table row from the database table.

54. The computer-readable medium of claim 51, wherein the instructions for performing the database table operation include instructions for:

modifying a database table row in the database table.

55. The computer-readable medium of claim 51, wherein the instructions for updating the aggregate information include instructions for:

reading first aggregate information from the entry;

computing second aggregate information using the first aggregate information and a value that is affected by the database table operation; and

storing the second aggregate information in the entry.

56. The computer-readable medium of claim 51, wherein the instructions for updating the aggregate information include instructions for:

reading database table information from the two or more database table rows after completion of the database table operation;

computing new aggregate information based on the database table information; and

storing the new aggregate information in the entry.

74. The computer-readable medium of claim 51, wherein the instructions for storing, in the entry that corresponds to the key value, information that indicates where said two or more database table rows that have the key value are located in the database table include instructions for:

storing, in the entry that corresponds to the key value, information that specifies a row identifier that identifies where said two or more database table rows that have the key value are located in the database table.