# US 2020/0401595 A1 · Estimating the number of distinct entities from a set of records of a database system > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 2020/0401595 A1 - Document ID: US20200401595A1 - Status: Published application - Kind: A1 - Application number: 16/449,333 - Filed: 2019-06-21 - Published: 2020-12-24 - Earliest claimed: 2019-06-21 - Assignees: salesforce.com, inc. - Applicants: Salesforce.com, inc. - Inventors: Arun Kumar Jagota - Web page: https://patentgrep.com/patent/US20200401595A1 ## CPC - G06F 16/24554: {Unary operations; Data partitioning operations} - G06F 16/252: {between a Database Management System and a front-end application} - G06F 16/24564: {Applying rules; Deductive queries} - G06F 16/288: {Entity relationship models} - G06F 16/23: Updating - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract A method and system for estimating a number of distinct entities in a set of records are described. For each one of a subset of records, a set of match rule keys are generated based on a set of match rules. Each match rule from the set of match rules defines a match between records, and each match rule key from the set of match rule keys includes at least a key field value. A high order key for the record is determined based on the match rule keys, and a counter associated with the high order key is incremented. When each record from the subset of records has been processed by determining the match rule keys, and incrementing the counter(s) of the high order keys, a sum of a number of counters that have a non-zero value is performed to estimate the distinct entities in the records. ## Claims ### Claim 1 A method of estimating a number of distinct entities in a plurality of records of a database system, the method 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. ### Claim 2 (depends on 1) The method of claim 1 further comprising: for each one of the subset of records from the plurality of records: responsive to determining that a set of one or more sub-keys for the record includes at least one sub-key that is different from the high order key, wherein each one from the set of sub-keys is based at least in part on a match rule key from the set of match rule keys and is formed from fewer key field values than all key field values of the high order key, decrementing one or more sub-key counters, wherein each one of the sub-key counters is associated with a respective sub-key from the set of sub-keys. ### Claim 3 (depends on 2) The method of claim 2, wherein the set of sub-keys includes the set of match rule keys and a set of intermediary composite keys, wherein each one from the set of intermediary composite keys includes fewer key fields than the high order key and more key fields than each one of the set of match rule keys, and wherein each one from the set of the intermediary composite keys are formed by key fields from at least two match rule keys. ### Claim 4 (depends on 1) The method of claim 1 further comprising: for at least one of the plurality of records: responsive to determining that no match rule key can be generated based on the match rule keys for the at least one of the plurality of records, incrementing a no-match rule key counter. ### Claim 5 (depends on 1) The method of claim 1, wherein the high order key includes at least a first key field value of a first one of the set of match rule keys and at least a second key field value of a second one of the set of match rule keys. ### Claim 6 (depends on 1) The method of claim 1, wherein the high order key includes all distinct key fields from all non-null match rule keys generated from a record. ### Claim 7 (depends on 1) The method of claim 1, wherein each match rule from the set of match rules identifies a set of fields, and wherein generating the set of match rule keys for a record includes: for each match rule from the set of match rules: generating a respective set of key field values from a set of field values of the records that correspond to the set of fields identified in the match rule key, and generating a match rule key that corresponds to the match rule when all the respective set of key field values are non-null. ### Claim 8 (depends on 1) The method of claim 1, further comprising: defining the set of match rules, wherein for each match rule from the set of match rules is nonredundant with other match rules from the set of match rules. ### Claim 9 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. ### Claim 10 (depends on 9) The non-transitory machine-readable storage medium of claim 9, wherein the operations further comprise: for each one of the subset of records from the plurality of records: responsive to determining that a set of one or more sub-keys for the record includes at least one sub-key that is different from the high order key, wherein each one from the set of sub-keys is based at least in part on a match rule key from the set of match rule keys and is formed from fewer key field values than all key field values of the high order key, decrementing one or more sub-key counters, wherein each one of the sub-key counters is associated with a respective sub-key from the set of sub-keys. ### Claim 11 (depends on 10) The non-transitory machine-readable storage medium of claim 10, wherein the set of sub-keys includes the set of match rule keys and a set of intermediary composite keys, wherein each one from the set of intermediary composite keys includes fewer key fields than the high order key and more key fields than each one of the set of match rule keys, and wherein each one from the set of the intermediary composite keys are formed by key fields from at least two match rule keys. ### Claim 12 (depends on 9) The non-transitory machine-readable storage medium of claim 9, wherein the operations further comprise: for at least one of the plurality of records: responsive to determining that no match rule key can be generated based on the match rule keys for the at least one of the plurality of records, incrementing a no-match rule key counter. ### Claim 13 (depends on 9) The non-transitory machine-readable storage medium of claim 9, wherein the high order key includes at least a first key field value of a first one of the set of match rule keys and at least a second key field value of a second one of the set of match rule keys. ### Claim 14 (depends on 9) The non-transitory machine-readable storage medium of claim 9, wherein the high order key includes all distinct key fields from all non-null match rule keys generated from a record. ### Claim 15 (depends on 9) The non-transitory machine-readable storage medium of claim 9, wherein each match rule from the set of match rules identifies a set of fields, and wherein generating the set of match rule keys for a record includes: for each match rule from the set of match rules: generating a respective set of key field values from a set of field values of the records that correspond to the set of fields identified in the match rule key, and generating a match rule key that corresponds to the match rule when all the respective set of key field values are non-null. ### Claim 16 (depends on 9) The non-transitory machine-readable storage medium of claim 9, wherein the operations further comprise: defining the set of match rules, wherein for each match rule from the set of match rules is nonredundant with other match rules from the set of match rules. ### Claim 17 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. ### Claim 18 (depends on 17) The machine of claim 17, wherein the operations further comprise: for each one of the subset of records from the plurality of records: responsive to determining that a set of one or more sub-keys for the record includes at least one sub-key that is different from the high order key, wherein each one from the set of sub-keys is based at least in part on a match rule key from the set of match rule keys and is formed from fewer key field values than all key field values of the high order key, decrementing one or more sub-key counters, wherein each one of the sub-key counters is associated with a respective sub-key from the set of sub-keys. ### Claim 19 (depends on 18) The machine of claim 18, wherein the set of sub-keys includes the set of match rule keys and a set of intermediary composite keys, wherein each one from the set of intermediary composite keys includes fewer key fields than the high order key and more key fields than each one of the set of match rule keys, and wherein each one from the set of the intermediary composite keys are formed by key fields from at least two match rule keys. ### Claim 20 (depends on 17) The machine of claim 17, wherein the operations further comprise: for at least one of the plurality of records: responsive to determining that no match rule key can be generated based on the match rule keys for the at least one of the plurality of records, incrementing a no-match rule key counter. ### Claim 21 (depends on 17) The machine of claim 17, wherein the high order key includes at least a first key field value of a first one of the set of match rule keys and at least a second key field value of a second one of the set of match rule keys. ### Claim 22 (depends on 17) The machine of claim 17, wherein the high order key includes all distinct key fields from all non-null match rule keys generated from a record. ### Claim 23 (depends on 17) The machine of claim 17, wherein each match rule from the set of match rules identifies a set of fields, and wherein generating the set of match rule keys for a record includes: for each match rule from the set of match rules: generating a respective set of key field values from a set of field values of the records that correspond to the set of fields identified in the match rule key, and generating a match rule key that corresponds to the match rule when all the respective set of key field values are non-null. ### Claim 24 (depends on 17) The machine of claim 17, wherein the operations further comprise: defining the set of match rules, wherein for each match rule from the set of match rules is nonredundant with other match rules from the set of match rules.