System for generating predicate-weighted histograms
AssigneeSQL Sentry, Inc.
InventorsFred Warren Frost, Gregory H. Gonzalez, John Brooke Philpott, Richard L. Taylor, JR.
Life of this patent
Estimating the term…
Abstract
Embodiments of the present invention provide a method, computer program-product, and system for generating predicate-weighted histograms in a database management system. Further, the methods, computer program-products and systems in accordance with the present invention generate histograms that are biased towards the predicate literals of the queries that are submitted to the database management system. The resulting histograms will improve query performance by generating histograms with greater resolution near predicate literals that represent the queries submitted to the database management system.
Claims20
A method for generating a histogram, the method comprising the steps of:
- (a) initialize a working histogram for a data column, the data column comprising a plurality of data values, wherein the working histogram comprises a plurality of rows, each row corresponding to a unique data value from the plurality of data values;
- (b) capture one or more queries, wherein the one or more queries comprise one or more predicate literals;
- (c) generate a weight vector based on the predicate literals, wherein the weight vector comprises a plurality of weight values, each weight value corresponding to one of the plurality of rows of the working histogram;
- (d) calculate a cost value for each row of the working histogram, wherein each cost value is determined at least in part on an information loss and the weight value corresponding to one of the rows of the working histogram;
- (e) identify a first row in the working histogram having a lowest cost value of the plurality of rows in the working histogram;
- and
- (f) merge the first row of the working histogram with a second row of the working histogram.
A computer-program product for generating a histogram, wherein the computer program product is embodied on at least one non-transitory computer-readable medium having computer-readable program code portions embodied therein, the computer-readable program code portions comprising executable portions configured to:
- (a) initialize a working histogram for a data column, the data column comprising a plurality of data values, wherein the working histogram comprises a plurality of rows, each row corresponding to a unique data value from the plurality of data values;
- (b) capture one or more queries, wherein the one or more queries comprise one or more predicate literals;
- (c) generate a weight vector based on the predicate literals, wherein the weight vector comprises a plurality of weight values, each weight value corresponding to one of the plurality of rows of the working histogram;
- (d) calculate a cost value for each row of the working histogram, wherein each cost value is determined at least in part on an information loss and the weight value corresponding to one of the rows of the working histogram;
- (e) identify a first row in the working histogram having a lowest cost value of the plurality of rows in the working histogram;
- and
- (f) merge the first row of the working histogram with a second row of the working histogram.
A system for generating histograms, the system comprising:
- a memory device with computer-readable program code stored thereon;
- a communication device;
- a processing device operatively coupled to the memory device and the communication device, wherein the processing device is configured to execute the computer-readable program code to:
- (a) initialize a working histogram for a data column, the data column comprising a plurality of data values, wherein the working histogram comprises a plurality of rows, each row corresponding to a unique data value from the plurality of data values;
- (b) capture one or more queries, wherein the one or more queries comprise one or more predicate literals;
- (c) generate a weight vector based on the predicate literals, wherein the weight vector comprises a plurality of weight values, each weight value corresponding to one of the plurality of rows of the working histogram;
- (d) calculate a cost value for each row of the working histogram, wherein each cost value is determined at least in part on an information loss and the weight value corresponding to one of the rows of the working histogram;
- (e) identify a first row in the working histogram having a lowest cost value of the plurality of rows in the working histogram;
- and
- (f) merge the first row of the working histogram with a second row of the working histogram.
Dependencies are inferred from the claim text.