Distinct value estimation for query planning

A system for generating query plans based on statistical information regarding data stored in a distributed computing cluster, the system comprising:

• a processor;
• and
• a memory coupled to the processor, the memory including instructions stored thereon, which when executed by the processor cause the system to:
• process a dataset stored in the distributed computing cluster to scan a portion of a plurality of values included in the dataset;
• generate a plurality of buckets based on the scanning, a particular bucket of the plurality of buckets including:
• a value count indicator indicative of a quantity of a subset of the plurality of values scanned to generate the particular bucket;
• and
• a probabilistic estimator buffer, the probabilistic estimator buffer representative of an intermediate probabilistic estimation state, the probabilistic estimator buffer based on one or more fixed length hash values, each of the one or more fixed length hash values based on a hash function applied to a different one of the subset of the plurality of values;
• generate a plurality of data points based on the plurality of buckets, a particular data point based on the particular bucket including:
• a first data point component based on the value count indicator;
• and
• a second data point component based on the probabilistic estimator buffer;
• analyze the plurality of data points to estimate a number of distinct values in the dataset;
• generating and store statistical information based on the estimated number of distinct values in a metastore database of the distributed computing cluster;
• and
• generating a query plan based on the statistical information stored in the metastore database in response to receiving a query.

A system for performing queries on data stored in a distributed computing cluster, comprising:

• a distinct value estimator that estimates a number of distinct values associated with an attribute in a table stored in the distributed computing cluster without scanning all of a plurality of values associated with the attribute by:
• processing the table to scan a portion of the plurality of values associated with the attribute in the table;
• generating a plurality of buckets based on the scanning, a particular bucket of the plurality of buckets including:
• a value count indicator indicative of a quantity of a subset of the plurality of values scanned to generate the particular bucket;
• and
• a probabilistic estimator buffer representative of an intermediate probabilistic estimation state, the probabilistic estimator buffer based on one or more fixed length hash values, each of the one or more fixed length hash values based on a hash function applied to a different one of the subset of the plurality of values;
• generating a plurality of data points based on the plurality of buckets, a particular data point based on the particular bucket including:
• a first data point component based on the value count indicator;
• and
• a second data point component based on the probabilistic estimator buffer;
• generating a plot of the plurality of data points;
• fitting an objective function to the plot of the plurality of data points;
• and
• extrapolating the objective function to an estimated or known total number of values associated with the attribute in the table, wherein the estimate of the number of distinct values associated with the attribute in the table is based on the extrapolation;
• a metastore database that stores statistical information associated with data stored in the distributed computing cluster, the statistical information including distinct value estimates generated by the distinct value estimator;
• and
• a plurality of data nodes, each data node having:
• a query planner configured to parse queries from clients to create query plan fragments based on the statistical information stored in the metastore database;
• a query coordinator configured to distribute query plan fragments among one or more of the plurality of data nodes;
• and
• a query execution engine configured to execute query plan fragments to obtain intermediate results that are aggregated and returned to clients.