Effective materialization strategy utilizing statistical set-theoretic approach for generation of multi-interval multi-column histogram and histograms in general

A system, comprising:

• a processor;
• and
• a non-transitory storage medium comprising instructions executable on the processor to:
• receive a command to generate histograms from data comprising a plurality of column groups;
• identify a superset from the plurality of column groups, the superset comprising a plurality of columns, and derive a parent-child relationship with subsets of the superset to reduce overhead by optimizing usage of computer resources;
• materialize, in a memory, a superset multi-column group for the superset;
• identify a first subset and a second subset of the superset from the plurality of column groups, the first subset comprising a first column group comprising multiple columns, and the second subset comprising a second column group comprising multiple columns;
• determine that a subset prefix column of the first subset is same as a superset prefix column of the superset;
• process the first subset of the superset to form a first grouped resultset without a sort operation in response to determining that the subset prefix column of the first subset is the same as the superset prefix column of the superset to reduce usage of the computer resources in forming the first grouped resultset;
• determine that a subset prefix column of the second subset is different from the superset prefix column of the superset;
• sort and merge, in the memory, the second subset of the superset to form a second grouped resultset in response to determining that the subset prefix column of the second subset is different from the superset prefix column of the superset;
• and
• generate a first histogram for the first grouped resultset of the first subset of the superset, and generate a second histogram for the second grouped resultset of the second subset of the superset, wherein the generating of the first and second histograms include cost determinations in terms of elapsed times for forming the superset and the subsets.

A non-transitory machine-readable storage medium comprising that upon execution cause a system to:

• receive a command to generate histograms from data comprising a plurality of column groups;
• identify a superset from the plurality of column groups, the superset comprising a plurality of columns, and derive a parent-child relationship with subsets of the superset to reduce overhead by optimizing usage of computer resources;
• materialize, in a memory, a superset multi-column group for the superset;
• identify a first subset and a second subset of the superset from the plurality of column groups, the first subset comprising a first column group, and the second subset comprising a second column group;
• determine that a subset prefix column of the first subset is same as a superset prefix column of the superset;
• process the first subset of the superset to form a first grouped resultset without a sort operation in response to determining that the subset prefix column of the first subset is the same as the superset prefix column of the superset to reduce usage of the computer resources in forming the first grouped resultset;
• determine that a subset prefix column of the second subset is different from the superset prefix column of the superset;
• sort and merge, in the memory, the second subset of the superset to form a second grouped resultset in response to determining that the subset prefix column of the second subset is different from the superset prefix column of the superset;
• and
• generate a first histogram for the first grouped resultset of the first subset of the superset, and generate a second histogram for the second grouped resultset of the second subset of the superset, wherein the generating of the first and second histograms include cost determinations in terms of elapsed times for forming the superset and the subsets.