Selectivity estimation for query execution planning in a database

A system for estimating selectivity for query execution planning, the system comprising:

• a computing device having a processor and a memory;
• wherein the memory stores an optimizer engine and a query estimator, wherein the optimizer engine and the query estimator, when executed by the processor, are operable to:
• generate, for data stored in a database in a memory, a one-dimensional value distribution for each of a plurality of attributes of the data;
• generate a multidimensional histogram, wherein the multidimensional histogram includes the one-dimensional value distributions for the plurality of attributes of the data;
• convert the multidimensional histogram to a one-dimensional histogram by assigning each bucket of the multidimensional histogram to corresponding buckets of the one-dimensional histogram and ordering the corresponding buckets according to a space-filling curve;
• determine one or more bucket ranges of the one-dimensional histogram by mapping the query conditions on the one-dimensional histogram;
• and
• estimate the selectivity of the query by estimating how many data values in the one or more bucket ranges will meet the query conditions.

A computer program product comprising a computer readable storage medium having program code embodied therewith, the program code comprising computer readable program code configured for:

• generating, for data stored in a database in a memory, a one-dimensional value distribution for each of a plurality of attributes of the data;
• generating a multidimensional histogram, wherein the multidimensional histogram includes the one-dimensional value distributions for the plurality of attributes of the data;
• converting the multidimensional histogram to a one-dimensional histogram by assigning each bucket of the multidimensional histogram to corresponding buckets of the one-dimensional histogram and ordering the corresponding buckets according to a space-filling curve;
• determining one or more bucket ranges of the one-dimensional histogram by mapping the query conditions on the one-dimensional histogram;
• and
• estimating the selectivity of the query by estimating how many data values in the one or more bucket ranges will meet the query conditions.