Estimating the number of distinct entities from a set of records of a database system

A non-transitory machine-readable storage medium that provides instructions that, if executed by a processor for estimating a number of distinct entities in a plurality of records of a database system, will cause said processor to perform operations comprising:

• for each one of a subset of records from the plurality of records:
• generating, based on a set of one or more match rules, a set of match rule keys, wherein each match rule from the set of match rules defines a match between records, and wherein each match rule key from the set of match rule keys includes at least a key field value,
• determining, based on the match rule keys, a high order key for the record, and
• incrementing a counter associated with the high order key;
• and
• determining a sum of a number of counters that have a non-zero value as an estimate of the distinct entities in the plurality of records, wherein the counters include the counter associated with the high order key of each one of the subset of records.

A machine for estimating a number of distinct entities in a plurality of records of a database system, the machine comprising:

• a non-transitory machine-readable storage medium that provides instructions that, if executed by a processor, will cause the machine to perform operations comprising,
• for each one of a subset of records from the plurality of records:
• generating, based on a set of one or more match rules, a set of match rule keys, wherein each match rule from the set of match rules defines a match between records, and wherein each match rule key from the set of match rule keys includes at least a key field value,
• determining, based on the match rule keys, a high order key for the record, and
• incrementing a counter associated with the high order key;
• and
• determining a sum of a number of counters that have a non-zero value as an estimate of the distinct entities in the plurality of records, wherein the counters include the counter associated with the high order key of each one of the subset of records.