Selectivity prediction with compressed histograms in a parallel processing database system

• US 6,477,523 B1
• Filed: 12/03/1999
• Issued: 11/05/2002
• Est. Priority Date: 12/03/1999
• Status: Expired due to Term

• Current Assignee: Teradata US, Inc. (Teradata Corporation)
• Original Assignee: NCR Corporation
• Inventors: Chiang, Kuorong
• Primary Examiner(s): Metjahic, Safet
• Assistant Examiner(s): Alaubaidi, Haythim J.
• Application Number:
  US09/454,798
• Time in Patent Office: 1,068 Days
• Field of Search: 700/29, 707/103.R, 707/2, 705/36
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24532 of parallel queries
• CPC Class Codes: G06F 16/24545 Selectivity estimation or determination
• CPC Class Codes: G06F 16/2462 Approximate or statistical queries
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing

Abstract

A method, apparatus, and article of manufacture for generating statistics for use by a relational database management system. A global aggregate spool is generated for each of a plurality of partitions of a subject table that are spread across a plurality of processing units of a computer system. Each of the global aggregate spools is scanned to generate summary records. The summary records are then merged to generate interval records for a compressed histogram of the subject table, wherein the compressed histogram includes both equal-height intervals and high-biased intervals. The compressed histogram can then be analyzed to estimate the cardinality associated with one or more search conditions of a user query or other SQL statement. Compared to a strictly equal-height histogram, the compressed histogram allows the relational database management system to more accurately estimate the cardinality associated with various search conditions. As a result, the relational database management system can better optimize the execution of the user query.

Claims

1. A method for generating statics for records stored in a subject table in a computer system, comprising:

(a) generating a global aggregate spool for each of a plurality of partitions of a subject table stored on the computer system, wherein the partitions are stored across a plurality of processing units of the computer system;

(b) constructing one or more summary records from each of the global aggregate spools;

(c) generating one or more interval records from the summary records;

(d) constructing a compressed histogram from the interval records, wherein the compressed histogram includes both equal-height intervals and high-biased intervals; and

(e) analyzing the compressed histogram to estimate cardinality associated with one or more search conditions.

2. The method of claim 1, wherein the generating step (a) is performed simultaneously and in parallel by the processing units.

3. The method of claim 1, wherein the constructing step (b) is performed simultaneously and in parallel by the process units.

4. The method of claim 1, wherein the generating step (c) is performed by a coordinator processing unit.

5. The method of claim 1, wherein the constructing step (d) is performed by simultaneously and in parallel by the participating processing units and a coordinator processing unit.

6. The method of claim 1, wherein each of the interval records is comprised of one or more fields selected from a group comprising Values, Mode, ModeFreq, MaxVal, and Rows fields.

7. The method of claim 6, wherein values stored in the fields identify intervals as either equal-height intervals or high-biased intervals.

8. The method of claim 6, wherein the Values field in the high-biased interval represents a number of loners in the interval.

9. The method of claim 8, wherein the Mode field in the high-biased interval represents a first loner for the interval when the Values field represents the number of loners in the interval.

10. The method of claim 9, wherein the MaxVal field in the high-biased interval represents a second loner for the interval when the Mode field represents the first loner in the interval and the Values field represents the number of loners in the interval.

11. The method of claim 10, wherein the ModeFreq field in the high-biased interval represents a count of rows for the first loner.

12. The method of claim 11, wherein the Rows field in the high-biased interval represents a count of rows for the second loner.

13. The method of claim 6, wherein the Mode field in the high-biased interval represents a smaller loner.

14. The method of claim 6, wherein the ModeFreq field in the high-biased interval represents a number of rows having a modal value.

15. The method of claim 6, wherein the MaxVal field in the high-biased interval represents a maximum value for the interval.

16. The method of claim 6, wherein the Values field in the equal-heights interval represents a total number of values for all non-modal values in the interval.

17. The method of claim 6, wherein the Mode field in the equal-heights interval represents a most frequent value in the interval.

18. The method of claim 6, wherein the ModeFreq field in the equal-heights interval represents a number of rows having a modal value.

19. The method of claim 6, wherein the MaxVal field in the equal-heights interval represents a maximum value covered by the interval.

20. The method of claim 6, wherein the Rows field in the equal-heights interval represents a total number of rows for non-modal values in the interval.

21. The method of claim 1, wherein the summary record includes both a distinct value from the subject table and a number of rows in the subject table having the distinct value.

22. The method of claim 1, wherein a partition of the global aggregate spool resides on each of the processing units.

23. The method of claim 22, wherein each row of the global aggregate spool includes both a distinct value from the subject table and a number of rows in the subject table having the distinct value.

24. The method of claim 22, further comprising scanning the global aggregate spool to identify loners.

25. The method of claim 24, wherein a loner is a distinct value satisfying the condition:

$f\ge <br><br>\frac{T}{L}$

where f=frequency of the loner, T is a total number of rows in the subject table, and L is a maximum number of loners.

26. An apparatus for generating statistics for records stored in a subject table in a computer system, comprising:

(a) a computer system;

(b) logic, performed by the computer system, for;

(1) generating a global aggregate spool for each of a plurality of partitions of a subject table stored on the computer system, wherein the partitions are stored across a plurality of processing units of the computer system;

(2) constructing one or more summary records from each of the global aggregate spools;

(3) generating one or more interval records from the summary records;

(4) constructing a compressed histogram from the interval records, wherein the compressed histogram includes both equal-height intervals and high-biased intervals; and

(5) analyzing the compressed histogram to estimate cardinality associated with one or more search conditions.

27. The apparatus of claim 26, wherein the logic for generating (1) is performed simultaneously and in parallel by the processing units.

28. The apparatus of claim 26, wherein the logic for constructing (2) is performed simultaneously and in parallel by the processing units.

29. The apparatus of claim 26, wherein the logic for generating (3) is performed by a coordinator processing unit.

30. The apparatus of claim 26, wherein the logic for constructing (4) is performed by simultaneously and in parallel by the participating processing units and a coordinator processing unit.

31. The apparatus of claim 26, wherein each of the interval records is comprised of one or more fields selected from a group comprising Values, Mode, ModeFreq, MaxVal, and Rows fields.

32. The apparatus of claim 31, wherein values stored in the fields identify intervals as either equal-height intervals or high-biased intervals.

33. The apparatus of claim 31, wherein the Values field in the high-biased interval represents a number of loners in the interval.

34. The apparatus of claim 33, wherein the Mode field in the high-biased interval represents a first loner for the interval when the Values field represents the number of loners in the interval.

35. The apparatus of claim 34, wherein the MaxVal field in the high-biased interval represents a second loner for the interval when the Mode field represents the first loner in the interval and the Values field represents the number of loners in the interval.

36. The apparatus of claim 35, wherein the ModeFreq field in the high-biased interval represents a count of rows for the first loner.

37. The apparatus of claim 36, wherein the Rows field in the high-biased interval represents a count of rows for the second loner.

38. The apparatus of claim 31, wherein the Mode field in the high-biased interval represents a smaller loner.

39. The apparatus of claim 31, wherein the ModeFreq field in the high-biased interval represents a number of rows having a modal value.

40. The apparatus of claim 31, wherein the MaxVal field in the high-biased interval represents a maximum value for the interval.

41. The apparatus of claim 31, wherein the Values field in equal-heights interval represents a total number of values for all non-modal values in the interval.

42. The apparatus of claim 31, wherein the Mode field in the equal-heights interval represents a most frequent value in the interval.

43. The apparatus of claim 31, wherein the ModeFreq field in the equal-heights interval represents a number of rows having a modal value.

44. The apparatus of claim 31, wherein the MaxVal field in the equal-heights interval represents a maximum value covered by the interval.

45. The apparatus of claim 31, wherein the Rows field in the equal-heights interval represents a total number of rows for non-modal values in the interval.

46. The apparatus of claim 26, wherein the summary record includes both a distinct value from the subject table and a number of rows in the subject table having the distinct value.

47. The apparatus of claim 26, wherein a partition of the global aggregate spool resides on each of the processing units.

48. The apparatus of claim 47, wherein each row of the global aggregate spool includes both a distinct value from the subject table and a number of rows in the subject table having the distinct value.

49. The apparatus of claim 48, wherein the logic further comprises logic for scanning the global aggregate spool to identify loners.

50. The apparatus of claim 49, wherein a loner is a distinct value satisfying the condition:

$f\ge <br><br>\frac{T}{L}$

where f=frequency of the loner, T is a total number of rows in the subject table, and L is a maximum number of loners.

51. An article of manufacture embodying logic for generating statistics for records stored in a subject table in a computer system, comprising:

(a) generating a global aggregate spool for each of a plurality of partitions of a subject table stored on the computer system, wherein the partitions are stored across a plurality of processing units of the computer system;

(b) constructing one or more summary records from each of the global aggregate spools;

(c) generating one or more interval records from the summary records;

(d) constructing a compressed histogram from the interval records, wherein the compressed histogram includes both equal-height intervals and high-biased intervals; and

(e) analyzing the compressed histogram to estimate cardinality associated with one or more search conditions.

52. The method of claim 51, wherein the generating step (a) is performed simultaneously and in parallel by the processing units.

53. The method of claim 51, wherein the constructing step (b) is performed simultaneously and in parallel by the processing units.

54. The method of claim 51, wherein the generating step (c) is performed by a coordinator processing unit.

55. The method of claim 51, wherein the constructing step (d) is performed by simultaneously and in parallel by the participating processing units and a coordinator processing unit.

56. The method of claim 51, wherein each of the interval records is comprised of one or more fields selected from a group comprising Values, Mode, ModeFreq, MaxVal, and Rows fields.

57. The method of claim 56, wherein values stored in the fields identify intervals as either equal-height intervals or high-biased intervals.

58. The method of claim 56, wherein the Values field in the high-biased interval represents a number of loners in the interval.

59. The method of claim 58, wherein the Mode field in the high-biased interval represents a first loner for the interval when the Values field represents the number of loners in the interval.

60. The method of claim 59, wherein the MaxVal field in the high-biased interval represents a second loner for the interval when the Mode field represents the first loner in the interval and the Values field represents the number of loners in the interval.

61. The method of claim 60, wherein the ModeFreq field in the high-biased interval represents a count of rows for the first loner.

62. The method of claim 61, wherein the Rows field in the high-biased interval represents a count of rows for the second loner.

63. The method of claim 56, wherein the Mode field in the high-biased interval represents a smaller loner.

64. The method of claim 56, wherein the ModeFreq field in the high-biased interval represents a number of rows having a modal value.

65. The method of claim 56, wherein the MaxVal field in the high-biased interval represents a maximum value for the interval.

66. The method of claim 56, wherein the Values field in the equal-heights interval represents a total number of values for all non-modal values in the interval.

67. The method of claim 56, wherein the Mode field in the equal-heights interval represents a most frequent value in the interval.

68. The method of claim 56, wherein the ModeFreq field in the equal-heights interval represents a number of tows having a modal value.

69. The method of claim 56, wherein the MaxVal field in the equal-heights interval represents a maximum value covered by the interval.

70. The method of claim 56, wherein the Rows field in the equal-heights interval represents a total number of rows for non-modal values in the interval.

71. The method of claim 51, wherein the summary record includes both a distinct value from the subject table and a number of rows in the subject table having the distinct value.

72. The method of claim 51, wherein a partition of the global aggregate spool resides on each of the processing units.

73. The method of claim 72, wherein each row of the global aggregate spool includes both a distinct value from the subject table and a number of rows in the subject table having the distinct value.

74. The method of claim 72, further comprising scanning the global aggregate spool to identify loners.

75. The method of claim 74, wherein a loner is a distinct value satisfying the condition:

$f\ge <br><br>\frac{T}{L}$

where f=frequency of the loner, T is a total number of rows in the subject table, and L is a maximum number of loners.