# US 10,120,905 B2 · Efficient determination of join paths via cardinality estimation > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 10,120,905 B2 - Document ID: US10120905B2 - Status: Granted - Kind: B2 - Application number: 14/578,841 - Filed: 2014-12-22 - Published: 2016-06-23 - Granted: 2018-11-06 - Earliest claimed: 2014-12-22 - Assignees: Amazon Technologies, Inc. - Applicants: Amazon Technologies, Inc. - Inventors: Anurag Windlass Gupta; Timothy Andrew Rath; Srinivasan Sundar Raghavan; Santosh Kalki - Web page: https://patentgrep.com/patent/US10120905B2 ## CPC - G06F 16/2456: {Join operations} - G06F 16/275: {Synchronous replication} - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract A probabilistic counting structure such as a hyperloglog may be formed during a table scan for each of a selected set of columns. The columns may be selected based on an initial estimate of relatedness, which may be based on data types of the respective columns. An estimated cardinality of an intersection or union of columns may be formed based on an intersection of the probabilistic data structures. A join path may be determined based on the estimated cardinality of an intersection or union of the columns. ## Claims ### Claim 1 A system for identifying analytical relationships in transactional data, the system comprising: one or more computing nodes maintaining a table comprising a plurality of rows; one or more memories having stored thereon computer-readable instructions that, upon execution by a computing device, cause the system at least to: select a first column and a second column of the plurality of rows, wherein the first and second columns are selected based at least in part on a first estimate of relatedness between the first and second columns; form a first hyperloglog based at least in part on a first plurality of fields in the plurality of rows, the first plurality of fields corresponding to the first column; form a second hyperloglog based at least in part on a second plurality of fields in the plurality of rows, the second plurality of fields corresponding to the second column; calculate an intersection of the first hyperloglog and the second hyperloglog; and identify a join path between the first column and the second column based at least in part on a second estimate of coincidence between fields of the first plurality of fields and fields of the second plurality of fields, the second estimate based at least in part on the intersection. ### Claim 2 (depends on 1) The system of claim 1, further comprising one or more memories having stored thereon computer-readable instructions that, upon execution by the one or more computing nodes, cause the system at least to: form the first estimate of relatedness based on a data type common to the first column and the second column. ### Claim 3 (depends on 1) The system of claim 1, further comprising one or more memories having stored thereon computer-readable instructions that, upon execution by the one or more computing nodes, cause the system at least to: identify the join path by at least comparing the second estimate of coincidence for the first and second columns to an additional estimate of coincidence for two or more additional columns. ### Claim 4 (depends on 1) The system of claim 1, further comprising one or more memories having stored thereon computer-readable instructions that, upon execution by the one or more computing nodes, cause the system at least to: form the second estimate of coincidence by at least subtracting the intersection of the first hyperloglog and the second hyperloglog from a union of the first hyperloglog and the second hyperloglog. ### Claim 5 (depends on 1) The system of claim 1, further comprising one or more memories having stored thereon computer-readable instructions that, upon execution by the one or more computing nodes, cause the system at least to: form a plurality of hyperloglogs by at least performing a first scan of the plurality of rows; and form the first hyperloglog by at least performing a second scan of the plurality of rows, wherein a size of the first hyperloglog is greater than sizes of hyperloglogs in the plurality of hyperloglogs formed during the first scan. ### Claim 6 A non-transitory computer-readable storage medium having stored thereon instructions that, upon execution by one or more computing devices, cause the one or more computing devices at least to: form a first probabilistic counting structure based at least in part on a first plurality of fields in a plurality of rows, the first plurality of fields corresponding to a first column of the plurality of rows; form a second probabilistic counting structure based at least in part on a second plurality of fields in the plurality of rows, the second plurality of fields corresponding to a second column of the plurality of rows; calculate an intersection of the first and second probabilistic counting structures; and identify a join path between the first column and the second column based at least in part on an estimate of coincidence between fields of the first plurality of fields and fields of the second plurality of fields, the estimate of coincidence based at least in part on the intersection. ### Claim 7 (depends on 6) The non-transitory computer-readable storage medium of claim 6, comprising further instructions that, upon execution by the one or more computing devices, cause the one or more computing devices to at least: select the first column and the second column for forming the first and second probabilistic counting structures based at least in part on a data type common to the first and second columns. ### Claim 8 (depends on 6) The non-transitory computer-readable storage medium of claim 6, comprising further instructions that, upon execution by the one or more computing devices, cause the one or more computing devices to at least: identify the join path by at least comparing the estimate of coincidence for the first and second columns to an additional estimate of coincidence for two or more additional columns. ### Claim 9 (depends on 6) The non-transitory computer-readable storage medium of claim 6, comprising further instructions that, upon execution by the one or more computing devices, cause the one or more computing devices to at least: form the estimate of coincidence by at least subtracting the intersection of the first and second probabilistic counting structures from a union of the first and second probabilistic counting structures. ### Claim 10 (depends on 6) The non-transitory computer-readable storage medium of claim 6, wherein the estimate of coincidence is based at least in part on a count of fields not included in the intersection. ### Claim 11 (depends on 6) The non-transitory computer-readable storage medium of claim 6, comprising further instructions that, upon execution by the one or more computing devices, cause the one or more computing devices to at least: form the first probabilistic counting structure by at least performing a first scan of the plurality of rows and a second scan of the plurality of rows, wherein a size of the first probabilistic counting structure is increased for the second scan. ### Claim 12 (depends on 6) The non-transitory computer-readable storage medium of claim 6, comprising further instructions that, upon execution by the one or more computing devices, cause the one or more computing devices to at least: calculate the intersection by at least combining corresponding buckets in the first and second probabilistic counting structures. ### Claim 13 (depends on 6) The non-transitory computer-readable storage medium of claim 6, wherein the probabilistic counting structure comprises at least one of a loglog, a hyperloglog, a bloom filter, or a min-hash. ### Claim 14 A computer-implemented method for identifying analytical relationships in transactional data, the method comprising: forming, in a memory of a computing device, a first probabilistic counting structure based at least in part on scanning a first plurality of fields corresponding to a first column, the first plurality of fields stored on a one or more storage devices communicatively coupled to the computing device; forming, in the memory of the computing device, a second probabilistic counting structure based at least in part on a second plurality of fields corresponding to a second column, the second plurality of fields stored on the one or more storage devices; calculating an intersection of the first and second probabilistic counting structures; and identifying a join path between the first column and the second column based at least in part on an estimate of coincidence between fields of the first plurality of fields and fields of the second plurality of fields, the estimate of coincidence based at least in part on the intersection. ### Claim 15 (depends on 14) The computer-implemented method of claim 14, further comprising: selecting the first column and the second column for forming the first and second probabilistic counting structures based at least in part on a data type common to the first and second columns. ### Claim 16 (depends on 14) The computer-implemented method of claim 14, further comprising: identifying the join path by at least comparing the estimate of coincidence for the first and second columns to an additional estimate of coincidence for two or more additional columns. ### Claim 17 (depends on 14) The computer-implemented method of claim 14, further comprising: forming the estimate of coincidence by subtracting the intersection of the first and second probabilistic counting structures from a union of the first and second probabilistic counting structures. ### Claim 18 (depends on 14) The computer-implemented method of claim 14, wherein the estimate of coincidence is based at least in part on a probabilistically determined count of fields not included in the intersection. ### Claim 19 (depends on 14) The computer-implemented method of claim 14, further comprising: forming a hierarchy based at least in part on the identified join path. ### Claim 20 (depends on 14) The computer-implemented method of claim 14, further comprising: calculating the intersection by at least combining corresponding buckets in the first and second probabilistic counting structures.