Distributed histogram computation framework using data stream sketches and samples

A method performed by a computing system, the method comprising:

• performing by a control node:
• generating a statistical query task directed acyclic graph associated with a data set;
• dividing the statistical query task directed acyclic graph into a plurality of distributed queries respectively associated with distributions of the data set;
• and
• assigning the plurality of distributed queries to a plurality of processing nodes;
• performing, at least partially in parallel, by one or more of the plurality of processing nodes on each distribution:
• generating by each of the plurality of processing nodes, data structures that respectively store first data associated with respective frequencies of values, second data associated with a number of distinct values, and third data associated with a random sampling of the values;
• constructing, by each of the plurality of processing nodes, a histogram respectively based on the first data, the second data, and the third data of distributions processed by each of the plurality of processing nodes;
• transmitting, by each of the plurality of processing nodes to each other processing node, a count value indicative of a number of rows in respective distributions processed by each of the plurality of processing nodes;
• merging, by a first processing node of the plurality of processing nodes, data structures having the first data generated by the plurality of processing nodes, and data structures having the second data generated by the plurality of processing nodes;
• and
• merging, by a second processing node of the plurality of processing nodes, data structures having the third data generated by the plurality of processing nodes;
• and
• constructing, by a third processing node of the plurality of processing nodes, a global histogram of the data set based on the merged first data, the merged second data, and the merged third data.

A method performed by a computing system, the method comprising:

• performing a construction of a histogram by:
• determining information associated with the data set based on a scan of a data set;
• generating a first data structure, based on the information, that stores first data associated with respective frequencies of values in the data set;
• generating a second data structure, based on the information, that stores second data associated with a number of distinct values in the data set;
• generating a third data structure, based on the information, that stores third data associated with a random sampling of the values in the data set;
• and
• constructing the histogram based on the first data, the second data, and the third data;
• and
• deploying the histogram to a query optimizer configured to generate query plans based on a cardinality estimation associated with the histogram.