Efficient determination of join paths via cardinality estimation
AssigneeAmazon Technologies, Inc.
InventorsAnurag Windlass Gupta, Timothy Andrew Rath, Srinivasan Sundar Raghavan, Santosh Kalki
Life of this patent
Estimating the term…
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.
Claims20
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.
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.
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.
Dependencies are inferred from the claim text.