Selectivity prediction with compressed histograms in a parallel processing database system

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.

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.